于 飛 郝建國(guó) 張中杰
(國(guó)防科技大學(xué)智能科學(xué)學(xué)院 湖南 長(zhǎng)沙 410005)
近年來,算法的改進(jìn)、計(jì)算能力的進(jìn)步為機(jī)器學(xué)習(xí)帶來了長(zhǎng)足的發(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í)受到極大的推動(dòng)發(fā)展。
強(qiáng)化學(xué)習(xí)是一種有別于監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)的機(jī)器學(xué)習(xí)方法,它通過控制動(dòng)作與環(huán)境交互獲得環(huán)境獎(jiǎng)勵(lì),利用獎(jiǎng)勵(lì)值更新動(dòng)作策略,以實(shí)現(xiàn)決策的優(yōu)化。 強(qiáng)化學(xué)習(xí)的兩個(gè)最重要的特征是試錯(cuò)搜索和延遲獎(jiǎng)勵(lì)[3]。
在強(qiáng)化學(xué)習(xí)過程中,Agent的目標(biāo)是在未知環(huán)境中通過試錯(cuò)來獲得最大的獎(jiǎng)勵(lì)。在未對(duì)環(huán)境進(jìn)行充分地探索前,Agent難以找到最優(yōu)的策略。因此存在如何根據(jù)環(huán)境狀態(tài)進(jìn)行動(dòng)作選擇的問題,即探索(exploration)與利用(exploitation)問題[4]。
探索與利用的平衡不僅僅是強(qiáng)化學(xué)習(xí)中存在的困境,包括人類、動(dòng)物等生物在任何未知環(huán)境中進(jìn)行決策都會(huì)存在探索與利用問題。一般認(rèn)為,如果行為在各個(gè)選項(xiàng)之間沒有重點(diǎn)的交替選擇,則認(rèn)為是探索。如果只在某些選項(xiàng)中進(jìn)行重點(diǎn)選擇且隨著時(shí)間的推移變得穩(wěn)定,則認(rèn)為是在利用。人類或動(dòng)物在動(dòng)作探索后會(huì)獲取某些信息或獎(jiǎng)勵(lì)來指導(dǎo)下一次的動(dòng)作探索[5]。
在強(qiáng)化學(xué)習(xí)中,Agent在強(qiáng)化學(xué)習(xí)過程中依據(jù)已有經(jīng)驗(yàn)選擇當(dāng)前最優(yōu)的動(dòng)作,即貪婪地選擇動(dòng)作認(rèn)為是利用。Agent在強(qiáng)化學(xué)習(xí)過程中隨機(jī)地進(jìn)行動(dòng)作選擇認(rèn)為是在探索。
一方面,更多地探索未知的動(dòng)作空間,可以獲得更多的信息以搜索全局最優(yōu)解,但探索過多會(huì)降低算法性能且會(huì)導(dǎo)致算法不收斂的情況。另一方面,過多的利用會(huì)因?qū)Νh(huán)境知識(shí)的未知而導(dǎo)致選擇次優(yōu)的行為。因此,如何平衡探索與利用之間的關(guān)系成為影響強(qiáng)化學(xué)習(xí)算法性能的關(guān)鍵。通常的辦法是ε-greedy策略和Softmax分布策略[3]。ε-greedy策略是在貪婪算法的基礎(chǔ)上增加了參數(shù)ε,當(dāng)ε為0時(shí),ε-greedy策略就轉(zhuǎn)化為貪婪策略,ε由0逐漸增大至1的過程中,探索的程度逐漸增加;ε為1時(shí),ε-greedy策略就轉(zhuǎn)化為隨機(jī)選擇動(dòng)作。Sutton已經(jīng)證明了,ε-greedy策略性能優(yōu)于貪心策略。ε-greedy策略雖然一定程度上解決了探索與利用之間的問題,但由于參數(shù)ε固定,探索與利用的問題仍然存在,且存在參數(shù)ε難以設(shè)定,對(duì)非最優(yōu)動(dòng)作之間不加區(qū)分等問題。Softmax分布策略依據(jù)動(dòng)作的價(jià)值大小計(jì)算動(dòng)作選擇概率,對(duì)不同價(jià)值的動(dòng)作進(jìn)行了概率上的區(qū)分,克服了ε-greedy策略存在的不足,但是存在當(dāng)動(dòng)作價(jià)值差距不大時(shí)無法區(qū)分最優(yōu)動(dòng)作與其他動(dòng)作且計(jì)算量較大的問題[6]。
大量學(xué)者針對(duì)ε-greedy策略和Softmax分布策略存在的問題做了改進(jìn)和完善。文獻(xiàn)[7-9]均將計(jì)數(shù)機(jī)制引入到動(dòng)作探索中,來改善基礎(chǔ)方法在動(dòng)作探索中存在的不足。Guo等[10]將模擬退火(Simulated Annealing)算法中的Metropolis準(zhǔn)則引入Q-learning的動(dòng)作選擇機(jī)制,提出了SA-Q-learning算法。Chen等[11]將量子系統(tǒng)中兩個(gè)量子態(tài)之間的保真度作為反饋信息,提出了基于保真度的概率動(dòng)作選擇機(jī)制,基于此提出了基于保真度的概率Q-learning算法,并在量子系統(tǒng)中進(jìn)行了驗(yàn)證。陳啟軍等[12]針對(duì)強(qiáng)化學(xué)習(xí)存在的問題提出了“行動(dòng)分值”的概念,據(jù)此來進(jìn)行動(dòng)作選擇,并在行動(dòng)分值的基礎(chǔ)上優(yōu)化獎(jiǎng)勵(lì)函數(shù)。文獻(xiàn)[4, 13]將ε-greedy與Softmax結(jié)合來解決開發(fā)與利用的平衡問題,其中文獻(xiàn)[13]利用時(shí)間差分誤差來動(dòng)態(tài)調(diào)整ε參數(shù),而文獻(xiàn)[4]利用中長(zhǎng)期獎(jiǎng)勵(lì)的差異來動(dòng)態(tài)調(diào)整ε參數(shù)。
以上的動(dòng)作探索策略可以統(tǒng)一地歸為無向探索方法,另一類與之對(duì)應(yīng)的探索策略稱為有向探索[14]。Sledge等[15]利用各狀態(tài)中有關(guān)動(dòng)作的信息,將信息論的相關(guān)方法引入到強(qiáng)化學(xué)習(xí)的動(dòng)作探索中,以此啟發(fā)式方法來提高探索效率。李晨溪等[16]利用云推理模型,將先驗(yàn)知識(shí)、規(guī)則引入強(qiáng)化學(xué)習(xí),引導(dǎo)Agent的動(dòng)作選擇,減少動(dòng)作探索前期的盲目性。文獻(xiàn)[17-19]則是將先驗(yàn)知識(shí)引入到動(dòng)作探索策略中,來減少前期的無效探索以提高探索效率。
本文提出了一種新的動(dòng)作選擇策略。新策略定義了“動(dòng)作概率(action probability)”的概念,并據(jù)此進(jìn)行動(dòng)作偏好選擇,以解決探索與利用之間的平衡問題。最后通過實(shí)驗(yàn)驗(yàn)證了該方法的可行性。
許多強(qiáng)化學(xué)習(xí)問題都是基于馬爾可夫決策過程(MDP)提出的,一個(gè)MDP由元組(S,A,P,R,γ)構(gòu)成,其中:S為狀態(tài)集,A為動(dòng)作集,P為狀態(tài)轉(zhuǎn)移函數(shù)P:S×A×S→[0,1],R為獎(jiǎng)勵(lì)函數(shù)R:S×A→R,γ為折扣系數(shù)。
在每個(gè)時(shí)間步t,Agent觀察到狀態(tài)st∈S,依據(jù)策略π選擇動(dòng)作at∈A,與環(huán)境進(jìn)行交互,環(huán)境依概率轉(zhuǎn)移到新的狀態(tài)st+1,并給予Agent獎(jiǎng)勵(lì)R。這里對(duì)狀態(tài)的轉(zhuǎn)移做出了馬爾可夫假設(shè),即轉(zhuǎn)化到下一狀態(tài)的概率,只與當(dāng)前狀態(tài)有關(guān),與之前的狀態(tài)無關(guān)。
當(dāng)策略π(a|s)確定后,存在一個(gè)完整的狀態(tài)序列(s1,a1,r1,s2,a2,r2,…,st,at,rt)。強(qiáng)化學(xué)習(xí)的目的就是最大化序列獎(jiǎng)勵(lì)。
為了便于描述狀態(tài)之間的優(yōu)劣,強(qiáng)化學(xué)習(xí)引入了狀態(tài)價(jià)值函數(shù):
vπ(s)=Επ(Rt+1+γRt+2+γ2Rt+3+
…|St=s)
(1)
和動(dòng)作價(jià)值函數(shù):
qπ(s,a)=Επ(Rt+1+γRt+2+γ2Rt+3+
…|St=s,At=a)
(2)
由此可以得到兩個(gè)函數(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)價(jià)值函數(shù)與最優(yōu)動(dòng)作價(jià)值函數(shù)分別為:
(5)
(6)
這里以Q-learning算法為例。Q-learning算法[20]由Watkins在1989年最先提出,是一種不需要知道模型狀態(tài)轉(zhuǎn)移概率的模型無關(guān)(Model-free)算法,是一種時(shí)序差分離線控制算法。Q-learning是在知道環(huán)境狀態(tài)集S,動(dòng)作集A,即時(shí)獎(jiǎng)勵(lì)R的條件下,求解最優(yōu)動(dòng)作價(jià)值函數(shù)q*和最優(yōu)策略π*。此類問題的求解,與蒙特卡洛(Monte Carlo)類似均是采用值迭代的方法,通過值函數(shù)的更新,來更新策略,通過策略來產(chǎn)生新的狀態(tài)和即時(shí)獎(jiǎng)勵(lì),進(jìn)而更新值函數(shù)。
Q-learning算法使用兩個(gè)控制策略,一個(gè)策略用于選擇新的動(dòng)作,另一個(gè)策略用于更新值函數(shù)?;诋?dāng)前狀態(tài)S,依據(jù)動(dòng)作選擇策略選擇執(zhí)行動(dòng)作A,環(huán)境因此轉(zhuǎn)移到狀態(tài)S′,選擇狀態(tài)S′中價(jià)值最大的動(dòng)作A′更新值函數(shù)。Q-learning算法過程如圖 1所示, 其數(shù)學(xué)表示為:
Q(S,A))
(7)


圖1 Q-learning算法拓?fù)鋱D
Watkins等[21]在1992年證明滿足以下條件:
(1) 獎(jiǎng)勵(lì)值有界|rn|≤R。
(2) 學(xué)習(xí)率0≤αn<1。

當(dāng)n→∞時(shí),Q(s,a)以概率1收斂為Q*(s,a)。
Q-learning算法步驟:
輸入:狀態(tài)集S,動(dòng)作集A,步長(zhǎng)α,衰減因子γ,迭代輪數(shù)T。
輸出:所有的狀態(tài)-動(dòng)作對(duì)Q(s,a)值。
初始化Q(s,a);
從1循環(huán)至T;
1) 初始化一個(gè)初始狀態(tài)s;
2) 依據(jù)探索策略選擇狀態(tài)s下執(zhí)行動(dòng)作a;
3) 執(zhí)行動(dòng)作a,得到新狀態(tài)s’和獎(jiǎng)勵(lì)r;
4) 更新動(dòng)作價(jià)值函數(shù):

5)s=s′;
6) 如果S′是終止?fàn)顟B(tài),當(dāng)前輪迭代完畢否則轉(zhuǎn)到步驟2)。
強(qiáng)化學(xué)習(xí)問題的解決就是要找到Agent與環(huán)境交互的最優(yōu)策略π*,尋找在各個(gè)狀態(tài)S下的最優(yōu)動(dòng)作價(jià)值函數(shù)q*使得在各個(gè)狀態(tài)S下選擇最優(yōu)的動(dòng)作,其數(shù)學(xué)式表示為:
(8)

(9)
因此,尋找最優(yōu)策略問題轉(zhuǎn)化為尋找在所有策略下產(chǎn)生的動(dòng)作狀態(tài)值函數(shù)中的最大者。
常用的方法中ε-greedy策略是最接近貪婪的動(dòng)作選擇策略,通常設(shè)置一個(gè)參數(shù)ε,以(1-ε)的概率選擇當(dāng)前最優(yōu)動(dòng)作,以ε的概率在所有動(dòng)作中隨機(jī)選擇,其公式表示為:

(10)
式中:m為狀態(tài)s下動(dòng)作集的大小。
而Softmax分布策略則是根據(jù)動(dòng)作值函數(shù)的大小來計(jì)算動(dòng)作選擇概率,將動(dòng)作的值函數(shù)轉(zhuǎn)化為范圍在[0,1]的概率分布,其數(shù)學(xué)表示為:
(11)
無論是ε-greedy策略還是Softmax分布策略,都是在迭代的過程中,使動(dòng)作值函數(shù)最大的動(dòng)作擁有最大的選擇概率?;诖?本文提出了基于動(dòng)作概率的選擇機(jī)制。
定義1動(dòng)作概率表示Agent在某個(gè)狀態(tài)下執(zhí)行某一動(dòng)作的概率值。狀態(tài)-動(dòng)作對(duì)的動(dòng)作概率初始值為該狀態(tài)的動(dòng)作集大小的倒數(shù),即:
(12)
式中:card(As)表示狀態(tài)s下動(dòng)作集As中動(dòng)作的個(gè)數(shù)。
動(dòng)作概率根據(jù)動(dòng)作的值函數(shù)大小進(jìn)行動(dòng)態(tài)調(diào)整。Agent在狀態(tài)S下,根據(jù)動(dòng)作概率選擇動(dòng)作A,執(zhí)行動(dòng)作后,Agent獲取獎(jiǎng)勵(lì)R,進(jìn)入狀態(tài)S′,并選擇值函數(shù)最大的動(dòng)作A′來更新價(jià)值函數(shù)。隨后,依據(jù)狀態(tài)S下各個(gè)動(dòng)作的值函數(shù)大小進(jìn)行排序,將動(dòng)作分成兩類:值函數(shù)最大的為一類;其余的為第二類。將第二類中各個(gè)動(dòng)作的動(dòng)作概率值減半平均加到最大類中。其更新的過程如圖2所示。

圖2 算法更新過程
Agent在完成一次動(dòng)作后,按照狀態(tài)動(dòng)作值函數(shù)的大小,更新動(dòng)作概率。其更新規(guī)則如下:
(13)
式中:m為變化率,表示動(dòng)作概率的變化速率;A*(s)為值函數(shù)最大的動(dòng)作集,ai為集合A*(s)中的動(dòng)作,aj為值函數(shù)非最大的動(dòng)作。
在初始階段,所有動(dòng)作概率是相等的,動(dòng)作選擇是隨機(jī)選擇。當(dāng)某一動(dòng)作探索過后,若此次探索導(dǎo)致其獎(jiǎng)勵(lì)值為負(fù)值,會(huì)使這一動(dòng)作的動(dòng)作概率值減半,其他動(dòng)作的動(dòng)作概率值增加,在探索初期,會(huì)使得動(dòng)作探索更傾向于選擇未執(zhí)行過的動(dòng)作。若探索導(dǎo)致動(dòng)作獎(jiǎng)勵(lì)為正,表明這次的探索是有益的探索,會(huì)使這個(gè)動(dòng)作的動(dòng)作概率增加,其他動(dòng)作的動(dòng)作概率降低,傾向于更多地選擇此動(dòng)作;但其他動(dòng)作仍存在探索的概率,可以防止動(dòng)作探索陷入局部最優(yōu)的情況發(fā)生。
例如,Agent在狀態(tài)s下的動(dòng)作空間A(s)={up, down, left, right}。先后經(jīng)歷了三次,分別選擇了{(lán)up}、{down}、{left},獲取的獎(jiǎng)勵(lì)值分別為-1、-2和1。其動(dòng)作概率的更新見表 1。

表1 動(dòng)作概率更新過程

續(xù)表1
基于動(dòng)作概率的Q-learning算法步驟如下:
輸入:狀態(tài)集S,動(dòng)作集A,步長(zhǎng)α,衰減因子γ,迭代輪數(shù)T。
輸出:所有的狀態(tài)-動(dòng)作對(duì)Q(s,a)值。

從1循環(huán)至T;
1) 初始化一個(gè)初始狀態(tài)s;
2) 依據(jù)探索策略選擇狀態(tài)s下執(zhí)行動(dòng)作a;
3) 執(zhí)行動(dòng)作a,得到新狀態(tài)s′和獎(jiǎng)勵(lì)r;
4) 更新動(dòng)作價(jià)值函數(shù):
5) 更新動(dòng)作概率:

6)s=s′;
7) 如果s′是終止?fàn)顟B(tài),當(dāng)前輪迭代完畢否則轉(zhuǎn)到步驟2)。
本文設(shè)置兩組對(duì)照實(shí)驗(yàn),分別為實(shí)驗(yàn)一和實(shí)驗(yàn)二。兩次實(shí)驗(yàn)均采用格子世界作為實(shí)驗(yàn)環(huán)境,不同之處在于實(shí)驗(yàn)一中障礙為固定的,實(shí)驗(yàn)二中為移動(dòng)障礙物,學(xué)習(xí)難度更大。在兩次實(shí)驗(yàn)中,分別采用了Q-learning算法和DeepSARSA算法以驗(yàn)證本文提出的動(dòng)作探索策略的靈活性,并與ε-greedy策略和Softmax分布策略做出對(duì)比。
實(shí)驗(yàn)采用強(qiáng)化學(xué)習(xí)中常用的迷宮世界為實(shí)驗(yàn)環(huán)境,其界面如圖3所示。

圖3 迷宮世界
采用了21×9的方格表示,其中車輛表示Agent,旗幟表示迷宮出口,實(shí)心方格表示墻體。Agent動(dòng)作空間A(s)={up, down, left, right},每次動(dòng)作,Agent移動(dòng)一個(gè)方格。當(dāng)Agent到達(dá)邊界時(shí)選擇朝向邊界的動(dòng)作并不會(huì)使Agent離開地圖而是保持不動(dòng),當(dāng)Agent在墻體附近并選擇向墻體運(yùn)動(dòng)時(shí)不會(huì)使Agent撞墻而是保持不動(dòng)。
有關(guān)強(qiáng)化學(xué)習(xí)中參數(shù)設(shè)置,如表2所示。

表2 強(qiáng)化學(xué)習(xí)參數(shù)
實(shí)驗(yàn)分別使用ε-greedy策略、Softmax分布策略與動(dòng)作概率策略進(jìn)行對(duì)比分析,其中ε-greedy策略分別采用ε值為0.1、0.2和0.3三個(gè)值,強(qiáng)化學(xué)習(xí)算法均采用Q-learning算法,以排除學(xué)習(xí)算法對(duì)不同探索策略的影響。每輪迭代不設(shè)置最大動(dòng)作上限,共迭代500輪,每種策略運(yùn)行5次,采集5組數(shù)據(jù)進(jìn)行分析。
圖4為5種探索策略經(jīng)過5次實(shí)驗(yàn)后得到的結(jié)果,為了防止出現(xiàn)單次數(shù)據(jù)對(duì)實(shí)驗(yàn)的影響,圖中數(shù)據(jù)為5次實(shí)驗(yàn)后取平均值得到。該迷宮地圖的最優(yōu)解為25步,動(dòng)作概率策略在迭代至40輪后開始收斂至最優(yōu)解,Softmax分布策略在迭代至60輪后開始收斂,ε-greedy策略同樣在迭代至60輪后開始收斂,但因ε值固定導(dǎo)致收斂效果較差。

圖4 不同探索策略最優(yōu)解比例
圖5為5種探索策略前200輪迭代中,迭代步數(shù)的箱式圖??梢钥闯?動(dòng)作概率策略和Softmax策略的中位數(shù)相近,ε-greedy策略的中位數(shù)要大于前兩種策略;動(dòng)作概率策略的探索步數(shù)較其他策略更加集中且步數(shù)最少。

圖5 不同探索策略迭代步數(shù)
實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)一類似,同樣為格子世界,如圖6所示。

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

表3 強(qiáng)化學(xué)習(xí)實(shí)驗(yàn)參數(shù)
此實(shí)驗(yàn),采用三種動(dòng)作探索策略,分別為ε-greedy策略、Softmax分布策略及本文提出的探索策略。并將三種動(dòng)作探索策略與深度強(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è)置最大動(dòng)作上限,共迭代1 000輪,每種策略運(yùn)行5次,采集5組數(shù)據(jù)進(jìn)行分析。
圖7為三種不同策略經(jīng)過迭代1 000輪迭代后最優(yōu)路徑占總迭代輪數(shù)的比例,其中最優(yōu)路徑以最高得分82分為準(zhǔn)。可以看出,本文提出的動(dòng)作探索策略在迭代至25輪左右,就探索至最優(yōu)路徑;Softmax分布探索策略在迭代至45輪左右,探索至最優(yōu)路徑;而ε-greedy探索策略在迭代至200輪左右,才可探索至最優(yōu)路徑。圖中的線條在80輪、400輪、600輪和800輪時(shí)發(fā)生明顯的抖動(dòng),說明算法陷入到局部最優(yōu)的情況,但是經(jīng)過一段時(shí)間的探索,Softmax探索和本文提出的探索策略均能跳出局部最優(yōu)的情況收斂至全局最優(yōu),但本文提出的探索策略收斂速度更快,且更加穩(wěn)定。

圖7 三種探索策略最優(yōu)解占比
表4給出了三種算法的實(shí)驗(yàn)結(jié)果。

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