于 飛 郝建國 張中杰

(國防科技大學(xué)智能科學(xué)學(xué)院 湖南 長沙 410005)

0 引 言

近年來,算法的改進(jìn)、計(jì)算能力的進(jìn)步為機(jī)器學(xué)習(xí)帶來了長足的發(fā)展,但機(jī)器學(xué)習(xí)需要大量訓(xùn)練樣本支持限制了其在某些領(lǐng)域的發(fā)展。2016年以來,將深度學(xué)習(xí)與強(qiáng)化學(xué)習(xí)相結(jié)合的AlphaGo[1]擊敗世界圍棋冠軍,AlphaGo Zero[2]將深度強(qiáng)化學(xué)習(xí)進(jìn)一步與樹搜索的lookahead 機(jī)制相融合僅訓(xùn)練3天就擊敗了前輩AlphaGo,它們的出現(xiàn)將強(qiáng)化學(xué)習(xí)研究推向頂峰,使得強(qiáng)化學(xué)習(xí)受到極大的推動發(fā)展。

強(qiáng)化學(xué)習(xí)是一種有別于監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)的機(jī)器學(xué)習(xí)方法,它通過控制動作與環(huán)境交互獲得環(huán)境獎勵,利用獎勵值更新動作策略,以實(shí)現(xiàn)決策的優(yōu)化。 強(qiáng)化學(xué)習(xí)的兩個最重要的特征是試錯搜索和延遲獎勵[3]。

在強(qiáng)化學(xué)習(xí)過程中,Agent的目標(biāo)是在未知環(huán)境中通過試錯來獲得最大的獎勵。在未對環(huán)境進(jìn)行充分地探索前,Agent難以找到最優(yōu)的策略。因此存在如何根據(jù)環(huán)境狀態(tài)進(jìn)行動作選擇的問題,即探索(exploration)與利用(exploitation)問題[4]。

探索與利用的平衡不僅僅是強(qiáng)化學(xué)習(xí)中存在的困境,包括人類、動物等生物在任何未知環(huán)境中進(jìn)行決策都會存在探索與利用問題。一般認(rèn)為,如果行為在各個選項(xiàng)之間沒有重點(diǎn)的交替選擇,則認(rèn)為是探索。如果只在某些選項(xiàng)中進(jìn)行重點(diǎn)選擇且隨著時間的推移變得穩(wěn)定,則認(rèn)為是在利用。人類或動物在動作探索后會獲取某些信息或獎勵來指導(dǎo)下一次的動作探索[5]。

在強(qiáng)化學(xué)習(xí)中,Agent在強(qiáng)化學(xué)習(xí)過程中依據(jù)已有經(jīng)驗(yàn)選擇當(dāng)前最優(yōu)的動作,即貪婪地選擇動作認(rèn)為是利用。Agent在強(qiáng)化學(xué)習(xí)過程中隨機(jī)地進(jìn)行動作選擇認(rèn)為是在探索。

一方面,更多地探索未知的動作空間,可以獲得更多的信息以搜索全局最優(yōu)解,但探索過多會降低算法性能且會導(dǎo)致算法不收斂的情況。另一方面,過多的利用會因?qū)Νh(huán)境知識的未知而導(dǎo)致選擇次優(yōu)的行為。因此,如何平衡探索與利用之間的關(guān)系成為影響強(qiáng)化學(xué)習(xí)算法性能的關(guān)鍵。通常的辦法是ε-greedy策略和Softmax分布策略[3]。ε-greedy策略是在貪婪算法的基礎(chǔ)上增加了參數(shù)ε,當(dāng)ε為0時,ε-greedy策略就轉(zhuǎn)化為貪婪策略,ε由0逐漸增大至1的過程中,探索的程度逐漸增加;ε為1時,ε-greedy策略就轉(zhuǎn)化為隨機(jī)選擇動作。Sutton已經(jīng)證明了,ε-greedy策略性能優(yōu)于貪心策略。ε-greedy策略雖然一定程度上解決了探索與利用之間的問題,但由于參數(shù)ε固定,探索與利用的問題仍然存在,且存在參數(shù)ε難以設(shè)定,對非最優(yōu)動作之間不加區(qū)分等問題。Softmax分布策略依據(jù)動作的價值大小計(jì)算動作選擇概率,對不同價值的動作進(jìn)行了概率上的區(qū)分,克服了ε-greedy策略存在的不足,但是存在當(dāng)動作價值差距不大時無法區(qū)分最優(yōu)動作與其他動作且計(jì)算量較大的問題[6]。

大量學(xué)者針對ε-greedy策略和Softmax分布策略存在的問題做了改進(jìn)和完善。文獻(xiàn)[7-9]均將計(jì)數(shù)機(jī)制引入到動作探索中,來改善基礎(chǔ)方法在動作探索中存在的不足。Guo等[10]將模擬退火(Simulated Annealing)算法中的Metropolis準(zhǔn)則引入Q-learning的動作選擇機(jī)制,提出了SA-Q-learning算法。Chen等[11]將量子系統(tǒng)中兩個量子態(tài)之間的保真度作為反饋信息,提出了基于保真度的概率動作選擇機(jī)制,基于此提出了基于保真度的概率Q-learning算法,并在量子系統(tǒng)中進(jìn)行了驗(yàn)證。陳啟軍等[12]針對強(qiáng)化學(xué)習(xí)存在的問題提出了“行動分值”的概念,據(jù)此來進(jìn)行動作選擇,并在行動分值的基礎(chǔ)上優(yōu)化獎勵函數(shù)。文獻(xiàn)[4, 13]將ε-greedy與Softmax結(jié)合來解決開發(fā)與利用的平衡問題,其中文獻(xiàn)[13]利用時間差分誤差來動態(tài)調(diào)整ε參數(shù),而文獻(xiàn)[4]利用中長期獎勵的差異來動態(tài)調(diào)整ε參數(shù)。

以上的動作探索策略可以統(tǒng)一地歸為無向探索方法,另一類與之對應(yīng)的探索策略稱為有向探索[14]。Sledge等[15]利用各狀態(tài)中有關(guān)動作的信息,將信息論的相關(guān)方法引入到強(qiáng)化學(xué)習(xí)的動作探索中,以此啟發(fā)式方法來提高探索效率。李晨溪等[16]利用云推理模型,將先驗(yàn)知識、規(guī)則引入強(qiáng)化學(xué)習(xí),引導(dǎo)Agent的動作選擇,減少動作探索前期的盲目性。文獻(xiàn)[17-19]則是將先驗(yàn)知識引入到動作探索策略中,來減少前期的無效探索以提高探索效率。

本文提出了一種新的動作選擇策略。新策略定義了“動作概率(action probability)”的概念,并據(jù)此進(jìn)行動作偏好選擇,以解決探索與利用之間的平衡問題。最后通過實(shí)驗(yàn)驗(yàn)證了該方法的可行性。

1 基于動作概率的動作探索策略

1.1 馬爾可夫決策過程

許多強(qiáng)化學(xué)習(xí)問題都是基于馬爾可夫決策過程(MDP)提出的,一個MDP由元組(S,A,P,R,γ)構(gòu)成,其中:S為狀態(tài)集,A為動作集,P為狀態(tài)轉(zhuǎn)移函數(shù)P:S×A×S→[0,1],R為獎勵函數(shù)R:S×A→R,γ為折扣系數(shù)。

在每個時間步t,Agent觀察到狀態(tài)st∈S,依據(jù)策略π選擇動作at∈A,與環(huán)境進(jìn)行交互,環(huán)境依概率轉(zhuǎn)移到新的狀態(tài)st+1,并給予Agent獎勵R。這里對狀態(tài)的轉(zhuǎn)移做出了馬爾可夫假設(shè),即轉(zhuǎn)化到下一狀態(tài)的概率,只與當(dāng)前狀態(tài)有關(guān),與之前的狀態(tài)無關(guān)。

1.2 強(qiáng)化學(xué)習(xí)

當(dāng)策略π(a|s)確定后,存在一個完整的狀態(tài)序列(s1,a1,r1,s2,a2,r2,…,st,at,rt)。強(qiáng)化學(xué)習(xí)的目的就是最大化序列獎勵。

為了便于描述狀態(tài)之間的優(yōu)劣,強(qiáng)化學(xué)習(xí)引入了狀態(tài)價值函數(shù):

vπ(s)=Επ(Rt+1+γRt+2+γ2Rt+3+

…|St=s)

(1)

和動作價值函數(shù):

qπ(s,a)=Επ(Rt+1+γRt+2+γ2Rt+3+

…|St=s,At=a)

(2)

由此可以得到兩個函數(shù)的貝爾曼方程:

vπ(s)=Επ(Rt+1+γvπ(St+1)|St=s)

(3)

qπ(s,a)=Επ(Rt+1+γqπ(St+1,At+1)|St=

s,At=a)

(4)

而最優(yōu)狀態(tài)價值函數(shù)與最優(yōu)動作價值函數(shù)分別為:

(5)

(6)

這里以Q-learning算法為例。Q-learning算法[20]由Watkins在1989年最先提出,是一種不需要知道模型狀態(tài)轉(zhuǎn)移概率的模型無關(guān)(Model-free)算法,是一種時序差分離線控制算法。Q-learning是在知道環(huán)境狀態(tài)集S,動作集A,即時獎勵R的條件下,求解最優(yōu)動作價值函數(shù)q*和最優(yōu)策略π*。此類問題的求解,與蒙特卡洛(Monte Carlo)類似均是采用值迭代的方法,通過值函數(shù)的更新,來更新策略,通過策略來產(chǎn)生新的狀態(tài)和即時獎勵,進(jìn)而更新值函數(shù)。

Q-learning算法使用兩個控制策略,一個策略用于選擇新的動作,另一個策略用于更新值函數(shù)。基于當(dāng)前狀態(tài)S,依據(jù)動作選擇策略選擇執(zhí)行動作A,環(huán)境因此轉(zhuǎn)移到狀態(tài)S′,選擇狀態(tài)S′中價值最大的動作A′更新值函數(shù)。Q-learning算法過程如圖 1所示, 其數(shù)學(xué)表示為:

Q(S,A))

(7)

圖1 Q-learning算法拓?fù)鋱D

Watkins等[21]在1992年證明滿足以下條件:

(1) 獎勵值有界|rn|≤R。

(2) 學(xué)習(xí)率0≤αn<1。

當(dāng)n→∞時,Q(s,a)以概率1收斂為Q*(s,a)。

Q-learning算法步驟:

輸入:狀態(tài)集S,動作集A,步長α,衰減因子γ,迭代輪數(shù)T。

輸出:所有的狀態(tài)-動作對Q(s,a)值。

初始化Q(s,a);

從1循環(huán)至T;

1) 初始化一個初始狀態(tài)s;

2) 依據(jù)探索策略選擇狀態(tài)s下執(zhí)行動作a;

3) 執(zhí)行動作a,得到新狀態(tài)s’和獎勵r;

4) 更新動作價值函數(shù):

5)s=s′;

6) 如果S′是終止?fàn)顟B(tài),當(dāng)前輪迭代完畢否則轉(zhuǎn)到步驟2)。

1.3 動作探索策略

強(qiáng)化學(xué)習(xí)問題的解決就是要找到Agent與環(huán)境交互的最優(yōu)策略π*,尋找在各個狀態(tài)S下的最優(yōu)動作價值函數(shù)q*使得在各個狀態(tài)S下選擇最優(yōu)的動作,其數(shù)學(xué)式表示為:

(8)

(9)

因此,尋找最優(yōu)策略問題轉(zhuǎn)化為尋找在所有策略下產(chǎn)生的動作狀態(tài)值函數(shù)中的最大者。

常用的方法中ε-greedy策略是最接近貪婪的動作選擇策略,通常設(shè)置一個參數(shù)ε,以(1-ε)的概率選擇當(dāng)前最優(yōu)動作,以ε的概率在所有動作中隨機(jī)選擇,其公式表示為:

(10)

式中:m為狀態(tài)s下動作集的大小。

而Softmax分布策略則是根據(jù)動作值函數(shù)的大小來計(jì)算動作選擇概率,將動作的值函數(shù)轉(zhuǎn)化為范圍在[0,1]的概率分布,其數(shù)學(xué)表示為:

(11)

無論是ε-greedy策略還是Softmax分布策略,都是在迭代的過程中,使動作值函數(shù)最大的動作擁有最大的選擇概率?；诖?本文提出了基于動作概率的選擇機(jī)制。

定義1動作概率表示Agent在某個狀態(tài)下執(zhí)行某一動作的概率值。狀態(tài)-動作對的動作概率初始值為該狀態(tài)的動作集大小的倒數(shù),即:

(12)

式中:card(As)表示狀態(tài)s下動作集As中動作的個數(shù)。

動作概率根據(jù)動作的值函數(shù)大小進(jìn)行動態(tài)調(diào)整。Agent在狀態(tài)S下,根據(jù)動作概率選擇動作A,執(zhí)行動作后,Agent獲取獎勵R,進(jìn)入狀態(tài)S′,并選擇值函數(shù)最大的動作A′來更新價值函數(shù)。隨后,依據(jù)狀態(tài)S下各個動作的值函數(shù)大小進(jìn)行排序,將動作分成兩類:值函數(shù)最大的為一類;其余的為第二類。將第二類中各個動作的動作概率值減半平均加到最大類中。其更新的過程如圖2所示。

圖2 算法更新過程

Agent在完成一次動作后,按照狀態(tài)動作值函數(shù)的大小,更新動作概率。其更新規(guī)則如下:

(13)

式中:m為變化率,表示動作概率的變化速率;A*(s)為值函數(shù)最大的動作集,ai為集合A*(s)中的動作,aj為值函數(shù)非最大的動作。

在初始階段,所有動作概率是相等的,動作選擇是隨機(jī)選擇。當(dāng)某一動作探索過后,若此次探索導(dǎo)致其獎勵值為負(fù)值,會使這一動作的動作概率值減半,其他動作的動作概率值增加,在探索初期,會使得動作探索更傾向于選擇未執(zhí)行過的動作。若探索導(dǎo)致動作獎勵為正,表明這次的探索是有益的探索,會使這個動作的動作概率增加,其他動作的動作概率降低,傾向于更多地選擇此動作;但其他動作仍存在探索的概率,可以防止動作探索陷入局部最優(yōu)的情況發(fā)生。

例如,Agent在狀態(tài)s下的動作空間A(s)={up, down, left, right}。先后經(jīng)歷了三次,分別選擇了{(lán)up}、{down}、{left},獲取的獎勵值分別為-1、-2和1。其動作概率的更新見表 1。

表1 動作概率更新過程

續(xù)表1

基于動作概率的Q-learning算法步驟如下:

輸入:狀態(tài)集S,動作集A,步長α,衰減因子γ,迭代輪數(shù)T。

輸出:所有的狀態(tài)-動作對Q(s,a)值。

從1循環(huán)至T;

1) 初始化一個初始狀態(tài)s;

2) 依據(jù)探索策略選擇狀態(tài)s下執(zhí)行動作a;

3) 執(zhí)行動作a,得到新狀態(tài)s′和獎勵r;

4) 更新動作價值函數(shù):

5) 更新動作概率:

6)s=s′;

7) 如果s′是終止?fàn)顟B(tài),當(dāng)前輪迭代完畢否則轉(zhuǎn)到步驟2)。

2 實(shí)驗(yàn)與結(jié)果分析

本文設(shè)置兩組對照實(shí)驗(yàn),分別為實(shí)驗(yàn)一和實(shí)驗(yàn)二。兩次實(shí)驗(yàn)均采用格子世界作為實(shí)驗(yàn)環(huán)境,不同之處在于實(shí)驗(yàn)一中障礙為固定的,實(shí)驗(yàn)二中為移動障礙物,學(xué)習(xí)難度更大。在兩次實(shí)驗(yàn)中,分別采用了Q-learning算法和DeepSARSA算法以驗(yàn)證本文提出的動作探索策略的靈活性,并與ε-greedy策略和Softmax分布策略做出對比。

2.1 實(shí)驗(yàn)一

實(shí)驗(yàn)采用強(qiáng)化學(xué)習(xí)中常用的迷宮世界為實(shí)驗(yàn)環(huán)境,其界面如圖3所示。

圖3 迷宮世界

采用了21×9的方格表示,其中車輛表示Agent,旗幟表示迷宮出口,實(shí)心方格表示墻體。Agent動作空間A(s)={up, down, left, right},每次動作,Agent移動一個方格。當(dāng)Agent到達(dá)邊界時選擇朝向邊界的動作并不會使Agent離開地圖而是保持不動,當(dāng)Agent在墻體附近并選擇向墻體運(yùn)動時不會使Agent撞墻而是保持不動。

有關(guān)強(qiáng)化學(xué)習(xí)中參數(shù)設(shè)置,如表2所示。

表2 強(qiáng)化學(xué)習(xí)參數(shù)

2.2 實(shí)驗(yàn)一分析

實(shí)驗(yàn)分別使用ε-greedy策略、Softmax分布策略與動作概率策略進(jìn)行對比分析,其中ε-greedy策略分別采用ε值為0.1、0.2和0.3三個值,強(qiáng)化學(xué)習(xí)算法均采用Q-learning算法,以排除學(xué)習(xí)算法對不同探索策略的影響。每輪迭代不設(shè)置最大動作上限,共迭代500輪,每種策略運(yùn)行5次,采集5組數(shù)據(jù)進(jìn)行分析。

圖4為5種探索策略經(jīng)過5次實(shí)驗(yàn)后得到的結(jié)果,為了防止出現(xiàn)單次數(shù)據(jù)對實(shí)驗(yàn)的影響,圖中數(shù)據(jù)為5次實(shí)驗(yàn)后取平均值得到。該迷宮地圖的最優(yōu)解為25步,動作概率策略在迭代至40輪后開始收斂至最優(yōu)解,Softmax分布策略在迭代至60輪后開始收斂,ε-greedy策略同樣在迭代至60輪后開始收斂,但因ε值固定導(dǎo)致收斂效果較差。

圖4 不同探索策略最優(yōu)解比例

圖5為5種探索策略前200輪迭代中,迭代步數(shù)的箱式圖?？梢钥闯?動作概率策略和Softmax策略的中位數(shù)相近,ε-greedy策略的中位數(shù)要大于前兩種策略;動作概率策略的探索步數(shù)較其他策略更加集中且步數(shù)最少。

圖5 不同探索策略迭代步數(shù)

2.3 實(shí)驗(yàn)二

實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)一類似,同樣為格子世界,如圖6所示。

圖6 格子世界

采用了10×10的方格表示,其中方塊為Agent,圓形為目標(biāo),三角形為障礙物。Agent動作空間與實(shí)驗(yàn)一一致,障礙物每兩個離散時間步會左移一格,到達(dá)邊界時變?yōu)橄喾捶较蛞苿?。其中?qiáng)化學(xué)習(xí)的相關(guān)參數(shù)設(shè)置,如表3所示。

表3 強(qiáng)化學(xué)習(xí)實(shí)驗(yàn)參數(shù)

2.4 實(shí)驗(yàn)二分析

此實(shí)驗(yàn),采用三種動作探索策略,分別為ε-greedy策略、Softmax分布策略及本文提出的探索策略。并將三種動作探索策略與深度強(qiáng)化學(xué)習(xí)DeepSARSA算法結(jié)合。其中,DeepSARSA采用三層全連接層的模型進(jìn)行訓(xùn)練。

本次實(shí)驗(yàn)中,為防止因ε值固定導(dǎo)致收斂效果差的情況發(fā)生,采用了參數(shù)值隨探索次數(shù)增大而降低的方法。ε初始值設(shè)為1,隨后根據(jù)探索次數(shù)不斷降低,直至降到0.01。

每輪迭代不設(shè)置最大動作上限,共迭代1 000輪,每種策略運(yùn)行5次,采集5組數(shù)據(jù)進(jìn)行分析。

圖7為三種不同策略經(jīng)過迭代1 000輪迭代后最優(yōu)路徑占總迭代輪數(shù)的比例,其中最優(yōu)路徑以最高得分82分為準(zhǔn)。可以看出,本文提出的動作探索策略在迭代至25輪左右,就探索至最優(yōu)路徑;Softmax分布探索策略在迭代至45輪左右,探索至最優(yōu)路徑;而ε-greedy探索策略在迭代至200輪左右,才可探索至最優(yōu)路徑。圖中的線條在80輪、400輪、600輪和800輪時發(fā)生明顯的抖動,說明算法陷入到局部最優(yōu)的情況,但是經(jīng)過一段時間的探索,Softmax探索和本文提出的探索策略均能跳出局部最優(yōu)的情況收斂至全局最優(yōu),但本文提出的探索策略收斂速度更快,且更加穩(wěn)定。

圖7 三種探索策略最優(yōu)解占比

表4給出了三種算法的實(shí)驗(yàn)結(jié)果。

表4 三種算法的實(shí)驗(yàn)結(jié)果

3 結(jié) 語

本文研究了強(qiáng)化學(xué)習(xí)中動作探索策略,介紹了現(xiàn)有的平衡探索與利用問題的多種算法,分析了它們存在的不足。提出了一種基于動作概率的動作探索策略,通過動態(tài)調(diào)整動作概率來進(jìn)行動作偏好選擇。并將動作探索策略分別與Q-learning和DeepSARSA結(jié)合。實(shí)驗(yàn)表明,該方法較現(xiàn)有算法能夠更快收斂至最優(yōu)解,探索步數(shù)分布更加集中且數(shù)量更少,且靈活性較大,可與多種強(qiáng)化學(xué)習(xí)算法結(jié)合。

下一步工作是將該動作概率探索策略應(yīng)用于連續(xù)狀態(tài)空間中,利用概率密度函數(shù)來表述動作概率,以拓展該策略的應(yīng)用范圍。