張 峰，錢 輝，董春茹，花 強(qiáng)

河北省機(jī)器學(xué)習(xí)與計(jì)算智能重點(diǎn)實(shí)驗(yàn)室，河北大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，河北保定071002

Q學(xué)習(xí)算法[1]是一種用來解決馬爾可夫決策問題[2]的流行算法．與動(dòng)態(tài)規(guī)劃的值迭代和策略迭代算法相比，Q學(xué)習(xí)算法能應(yīng)用于對(duì)模型未知的環(huán)境中，通過對(duì)環(huán)境采樣，基于Bellman最優(yōu)方程，采用Bootstrap方式來迭代更新狀態(tài)-動(dòng)作的Q值與最優(yōu)策略．Q學(xué)習(xí)算法的更新公式[2]為

Qt(s,a))

(1)

Q學(xué)習(xí)算法的收斂速度與經(jīng)驗(yàn)數(shù)量指數(shù)相關(guān)[3]．為進(jìn)一步提高Q學(xué)習(xí)算法的收斂速度，研究人員提出了很多Q學(xué)習(xí)更新算法. 如Q(λ)算法[4]、后向Q學(xué)習(xí)算法[5]等．但是這些改進(jìn)算法通常會(huì)將實(shí)時(shí)采樣數(shù)據(jù)更新后就丟棄，造成兩個(gè)問題：① 對(duì)于那些不容易被采樣的狀態(tài)，僅使用1次會(huì)造成數(shù)據(jù)利用效率降低；② Bellman方程中每個(gè)Q值的更新依賴于后續(xù)狀態(tài)中的Q值，使用逆序訪問序列的收斂速度更快，而標(biāo)準(zhǔn)形式的Q學(xué)習(xí)算法中Q值更新是按正序訪問序列方式更新的，收斂速度較慢．針對(duì)這些問題，LIN[6]提出經(jīng)驗(yàn)回放算法．隨后MINH等[7]將其擴(kuò)展到深度學(xué)習(xí)領(lǐng)域，提出深度Q網(wǎng)絡(luò)(deep Q-network, DQN)算法，通過構(gòu)造經(jīng)驗(yàn)池保存歷史經(jīng)驗(yàn)，再采用經(jīng)驗(yàn)回放的方法，在必要時(shí)再次使用歷史經(jīng)驗(yàn)．該算法打破了狀態(tài)轉(zhuǎn)移之間的強(qiáng)關(guān)聯(lián)性，不僅保證了監(jiān)督學(xué)習(xí)中數(shù)據(jù)獨(dú)立同分布的假設(shè)，還加快了算法收斂速度，提高了數(shù)據(jù)利用率．

目前關(guān)于深度強(qiáng)化學(xué)習(xí)的研究中，針對(duì)經(jīng)驗(yàn)回放主要采取兩種方式：① 均勻回放，即將采樣序列〈s,a,r,s′〉保存到經(jīng)驗(yàn)池中，等概率選擇經(jīng)驗(yàn)池中的經(jīng)驗(yàn)，并應(yīng)用式(1)更新Q值；② 優(yōu)先回放，即優(yōu)先回放TD-error值較大的經(jīng)驗(yàn)，以提高收斂速度，優(yōu)先回放的經(jīng)驗(yàn)結(jié)構(gòu)與均勻回放的經(jīng)驗(yàn)結(jié)構(gòu)一致．但是，這些方法只適用于狀態(tài)轉(zhuǎn)移確定的情況，當(dāng)系統(tǒng)的狀態(tài)轉(zhuǎn)移不確定時(shí)，兩種方法都不能保證回放經(jīng)驗(yàn)的狀態(tài)轉(zhuǎn)移分布與實(shí)際狀態(tài)轉(zhuǎn)移分布一致．另外，在DQN算法中，由于Q學(xué)習(xí)算法總是貪心地選擇后續(xù)狀態(tài)動(dòng)作對(duì)中的最大Q值，因此可能會(huì)出現(xiàn)Q值過估計(jì)現(xiàn)象[8]．為此，本研究提出一種新的采樣序列存儲(chǔ)結(jié)構(gòu)，改進(jìn)了迭代計(jì)算公式，并提出基于狀態(tài)-動(dòng)作對(duì)的期望Q值經(jīng)驗(yàn)回放方法．該方法在保證算法復(fù)雜度較低的情況下，實(shí)現(xiàn)對(duì)于環(huán)境狀態(tài)轉(zhuǎn)移的無(wú)偏估計(jì)，并在一定程度上減少了Q學(xué)習(xí)算法的過估計(jì)問題．

1 經(jīng)驗(yàn)回放

經(jīng)驗(yàn)回放通過agent對(duì)環(huán)境的多次采樣來提高強(qiáng)化學(xué)習(xí)算法的收斂速度并解決更加復(fù)雜的問題[7]．由于經(jīng)驗(yàn)可存儲(chǔ)在agent的經(jīng)驗(yàn)池中，減少了等待環(huán)境反饋的時(shí)間，減小了agent與環(huán)境交互的代價(jià)．相比策略梯度類算法[9]，基于經(jīng)驗(yàn)回放的值評(píng)估算法能將采樣效率提高約10倍[10]．與基于模型的算法不同的是，經(jīng)驗(yàn)回放機(jī)制的所有狀態(tài)轉(zhuǎn)移序列都來自真實(shí)環(huán)境，避免了因模型擬合準(zhǔn)確度問題而造成的偏差．

但是，在不確定性的系統(tǒng)中，即使agent執(zhí)行相同的動(dòng)作，agent觀察到的環(huán)境也可能會(huì)轉(zhuǎn)移到不同的狀態(tài)．與不同后續(xù)狀態(tài)的轉(zhuǎn)移概率不同，僅經(jīng)驗(yàn)回放選擇的狀態(tài)轉(zhuǎn)移分布與實(shí)際環(huán)境一致時(shí)，才能保證最終的Q值是準(zhǔn)確值．

DQN算法通過經(jīng)驗(yàn)回放減少了狀態(tài)轉(zhuǎn)移序列的相關(guān)性，并通過批量選擇經(jīng)驗(yàn)進(jìn)行小批量更新，并多次回放經(jīng)驗(yàn)，提高了經(jīng)驗(yàn)利用率[11]．為進(jìn)一步提升算法速度，優(yōu)先經(jīng)驗(yàn)回放[12]通過給每個(gè)狀態(tài)轉(zhuǎn)移序列加權(quán)，將權(quán)重設(shè)為TD-error的冪函數(shù)，再以大概率選擇回放TD-error值大的序列，從而加快收斂速度．但是，此方法會(huì)令狀態(tài)轉(zhuǎn)移分布與實(shí)際環(huán)境不一致，必須對(duì)經(jīng)驗(yàn)的更新值進(jìn)行修正，讓每個(gè)更新值都乘以重要性采樣權(quán)重[12]．當(dāng)每個(gè)經(jīng)驗(yàn)都需按權(quán)重回放時(shí)，又會(huì)極大地增加算法的復(fù)雜度．因此，為減少?gòu)?fù)雜度，在優(yōu)先經(jīng)驗(yàn)回放中新增了sum-tree結(jié)構(gòu)，用來保存經(jīng)驗(yàn)的回放優(yōu)先級(jí)，以實(shí)現(xiàn)快速獲取經(jīng)驗(yàn)．

由以上分析可見，均勻回放不需進(jìn)行重要性采樣加權(quán)，算法簡(jiǎn)單，但學(xué)習(xí)效率較慢．在經(jīng)驗(yàn)池足夠大的情況下，可認(rèn)為經(jīng)驗(yàn)的狀態(tài)轉(zhuǎn)移概率與環(huán)境一致，因此采用均勻經(jīng)驗(yàn)回放可近似保證狀態(tài)轉(zhuǎn)移分布與實(shí)際狀態(tài)轉(zhuǎn)移分布的一致性．基于優(yōu)先回放的Q學(xué)習(xí)算法學(xué)習(xí)效率有所提高，但是相對(duì)復(fù)雜，對(duì)于隨機(jī)性較大的動(dòng)態(tài)系統(tǒng)，優(yōu)先經(jīng)驗(yàn)回放打破了原有的經(jīng)驗(yàn)分布，用于處理不確定環(huán)境時(shí)，效果可能更差．因此，本研究通過改進(jìn)現(xiàn)有經(jīng)驗(yàn)存儲(chǔ)方式，設(shè)計(jì)基于期望經(jīng)驗(yàn)回放的Q學(xué)習(xí)算法．該方法在保證算法復(fù)雜度較低的情況下，可實(shí)現(xiàn)對(duì)于不確定環(huán)境狀態(tài)轉(zhuǎn)移的無(wú)偏估計(jì)，并保證用于計(jì)算Q值的狀態(tài)轉(zhuǎn)移概率與實(shí)際環(huán)境的狀態(tài)轉(zhuǎn)移概率一致．

2 期望經(jīng)驗(yàn)回放

為解決優(yōu)先經(jīng)驗(yàn)回放所帶來的問題，本研究重點(diǎn)關(guān)注優(yōu)先回放算法造成的有偏回放以及復(fù)雜的數(shù)據(jù)結(jié)構(gòu)問題．為使經(jīng)驗(yàn)回放的狀態(tài)轉(zhuǎn)移分布與真實(shí)的狀態(tài)轉(zhuǎn)移分布一致，考慮以采樣獲得的狀態(tài)轉(zhuǎn)移頻率μn/n作為環(huán)境狀態(tài)轉(zhuǎn)移分布P的估計(jì)值．

由伯努利大數(shù)定律

(2)

可知，估計(jì)值μn/n為后續(xù)狀態(tài)分布概率的無(wú)偏估計(jì)．其中，ε為任意實(shí)數(shù)．因此可將此估計(jì)值帶入迭代公式，獲得動(dòng)作價(jià)值更好的估計(jì)．

采用這種經(jīng)驗(yàn)存儲(chǔ)結(jié)構(gòu)，可實(shí)現(xiàn)在特定狀態(tài)下執(zhí)行同一動(dòng)作時(shí)，無(wú)需更新整個(gè)經(jīng)驗(yàn)，只更新經(jīng)驗(yàn)池中后續(xù)狀態(tài)的訪問次數(shù)和即時(shí)回報(bào)期望值．每個(gè)經(jīng)驗(yàn)樣本相當(dāng)于一個(gè)完整的狀態(tài)轉(zhuǎn)移子樹，當(dāng)采樣次數(shù)足夠大時(shí)，可直接以等概率方式回放經(jīng)驗(yàn)，且多次回放經(jīng)驗(yàn)仍是無(wú)偏估計(jì)．更新公式修訂為

Qt(s,a)]

(3)

(4)

圖1 期望經(jīng)驗(yàn)回放算法

Fig.1 Expected memory replay-based
Q-learning algorithm

與原均勻經(jīng)驗(yàn)回放與優(yōu)先經(jīng)驗(yàn)回放算法相比， 本研究算法具有以下優(yōu)點(diǎn)：

2) 經(jīng)驗(yàn)池中的每個(gè)樣本包含多個(gè)序列，增加了經(jīng)驗(yàn)池的使用效率．

3) 每次經(jīng)驗(yàn)回放相當(dāng)于回放多個(gè)轉(zhuǎn)移序列的期望，經(jīng)驗(yàn)利用率比原均勻回放算法更高，而經(jīng)驗(yàn)池的結(jié)構(gòu)比優(yōu)先經(jīng)驗(yàn)回放更簡(jiǎn)單且易于實(shí)現(xiàn)．

4) 由于使用了后續(xù)狀態(tài)價(jià)值的期望，由式(5)可知，每次更新的TD-error 值都更穩(wěn)定，這在一定程度上減小了Q學(xué)習(xí)算法對(duì)動(dòng)作價(jià)值的過估計(jì)問題[13]．

(5)

在采用TD評(píng)估方式更新Q值的方法中，評(píng)估值的方差可分為立即回報(bào)方差、狀態(tài)轉(zhuǎn)移方差和后續(xù)估計(jì)值方差之和[14]．采用期望經(jīng)驗(yàn)回放，將使得狀態(tài)轉(zhuǎn)移方差變?yōu)?，加快了算法收斂速度．

圖2 機(jī)器人隨機(jī)行走問題Fig.2 Robot random walk

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

設(shè)計(jì)一個(gè)簡(jiǎn)單的帶有障礙的機(jī)器人行走環(huán)境(如圖 2)，并在此環(huán)境下分別測(cè)試原始Q學(xué)習(xí)算法、均勻回放算法、優(yōu)先回放算法及本研究算法收斂到最優(yōu)策略的速度．假設(shè)有一個(gè)機(jī)器人處在一個(gè)3行4列的網(wǎng)格中，其任務(wù)是到達(dá)位置12，在位置8處有一個(gè)陷阱，一旦機(jī)器人進(jìn)入則會(huì)損壞；位置6處有一根柱子，機(jī)器人若碰到柱子則會(huì)停在原地．網(wǎng)格周圍都是高墻，機(jī)器人碰到墻，就會(huì)停留在原地．

機(jī)器人可站在圖2的空白區(qū)域，可向上下左右走，但限于控制精度，僅有0.8的概率走到預(yù)定位置．例如，若機(jī)器人在位置 3往上走，則有 0.8 的概率走到位置 7，0.1 的概率走到位置 2或位置4；若機(jī)器人從位置 1往上走，則有 0.8 的概率走到位置 5，0.1 的概率走到位置 2和位置1．

任務(wù)目標(biāo)是在任意空白位置，求機(jī)器人行走到達(dá)位置 12的最佳軌跡．為使機(jī)器人避開陷阱，到達(dá)位置 12，可將到達(dá)位置 12 的回報(bào)設(shè)為 1 000，到達(dá)其他位置的回報(bào)設(shè)為 -1，折扣設(shè)為 1．同時(shí)，為提供一個(gè)比較的基準(zhǔn)，基于此設(shè)置，先利用值迭代算法求得該問題真實(shí)的最優(yōu)策略如圖 3．

圖3 機(jī)器人行走環(huán)境的最優(yōu)策略Fig.3 The optimal policy in the robot walk environment

根據(jù)Bellman最優(yōu)方程，得到最優(yōu)策略下對(duì)應(yīng)于各狀態(tài)動(dòng)作價(jià)值如表1．

表1 最優(yōu)策略下動(dòng)作價(jià)值

分別用經(jīng)典Q學(xué)習(xí)算法、帶均勻回放經(jīng)驗(yàn)、帶優(yōu)先經(jīng)驗(yàn)回放和動(dòng)作期望經(jīng)驗(yàn)回放的Q學(xué)習(xí)算法對(duì)機(jī)器人行走環(huán)境求解最優(yōu)策略，每種算法測(cè)試1 000 次，通過比較算法收斂到最優(yōu)策略所需的采樣數(shù)量，以及算法的收斂速度．

3.2 實(shí)驗(yàn)結(jié)果

由于不同算法適合的超參數(shù)不同，本研究對(duì)每個(gè)算法分別進(jìn)行多次實(shí)驗(yàn)，取其平均最優(yōu)結(jié)果，再統(tǒng)計(jì)各算法收斂到最優(yōu)策略時(shí)所需采樣次數(shù)的均值與標(biāo)準(zhǔn)差．收斂測(cè)試結(jié)果表明，經(jīng)典Q學(xué)習(xí)算法、隨機(jī)經(jīng)驗(yàn)回放算法、優(yōu)先經(jīng)驗(yàn)回放算法和期望經(jīng)驗(yàn)回放算法在各自最優(yōu)參數(shù)下，收斂到最優(yōu)策略所需的平均采樣次數(shù)及其標(biāo)準(zhǔn)差分別為(6 734±533)、(2 200±255)、(2 678±847)和(1 260±386) 次．可見，期望經(jīng)驗(yàn)回放算法收斂到最優(yōu)策略所需的平均采樣次數(shù)僅為原始Q學(xué)習(xí)算法的1/5、方差較小且收斂速度比均勻回放算法和優(yōu)先回放算法均提高了約50%．優(yōu)先回放算法使回放的狀態(tài)轉(zhuǎn)移分布與實(shí)際環(huán)境不一致，因此方差最大．(詳細(xì)測(cè)試結(jié)果請(qǐng)掃描論文頁(yè)末右下角二維碼查看．)為保證實(shí)驗(yàn)的可復(fù)現(xiàn)性，提供期望經(jīng)驗(yàn)回放算法取得最好結(jié)果的參數(shù)為：學(xué)習(xí)率α=0.005， 開始回放步數(shù)startStep=2 000，回放周期period=4，回放數(shù)量replaySize 從8遞增到 32，即在每回放100次后回放數(shù)量加4．實(shí)驗(yàn)表明，采用動(dòng)作期望經(jīng)驗(yàn)回放的方式，明顯提高了算法收斂到最優(yōu)策略的速度，對(duì)于動(dòng)態(tài)環(huán)境更有優(yōu)勢(shì)．

3.3 算法的進(jìn)一步分析

在算法迭代過程中，所求策略總是會(huì)先收斂到一個(gè)次優(yōu)的策略．圖4給出了一個(gè)收斂過程中最先出現(xiàn)1個(gè)次優(yōu)策略的例子．

圖4 收斂過程中的次優(yōu)策略Fig.4 An example of suboptimal policy in convergence process

由圖4可見，此策略是到達(dá)目標(biāo)的最短路徑策略，直觀上是最優(yōu)策略．但在狀態(tài) 4 和 7 處，最短路徑策略風(fēng)險(xiǎn)較高，這是因?yàn)樗惴ǖ^程中分別對(duì)狀態(tài)4向左和狀態(tài)7向上的動(dòng)作產(chǎn)生了過估計(jì)．由式(4)可知，本研究算法對(duì)狀態(tài)4和7的動(dòng)作價(jià)值估計(jì)更穩(wěn)定，且在迭代過程中保留了動(dòng)作價(jià)值的序關(guān)系，保證了算法能夠快速收斂到最優(yōu)策略．

表 2和表3分別給出了基于均勻回放的Q學(xué)習(xí)算法和基于期望回放算法收斂到最優(yōu)策略后的平均動(dòng)作價(jià)值與真實(shí)動(dòng)作價(jià)值的誤差統(tǒng)計(jì)．

表2 基于均勻回放的算法收斂后動(dòng)作價(jià)值的誤差

表3 基于期望回放算法收斂后動(dòng)作價(jià)值的誤差

由表2和表3可見，當(dāng)算法收斂到最優(yōu)策略時(shí)，對(duì)于所有狀態(tài)，動(dòng)作期望回放算法最終的動(dòng)作價(jià)值比均勻回放算法的動(dòng)作價(jià)值要低，但都收斂到了最優(yōu)策略，說明動(dòng)作期望算法有效解決了Q學(xué)習(xí)算法的動(dòng)作價(jià)值過估計(jì)問題．

結(jié) 語(yǔ)

提出一種基于樹的經(jīng)驗(yàn)存儲(chǔ)結(jié)構(gòu)，并將隨機(jī)環(huán)境的后續(xù)狀態(tài)轉(zhuǎn)移頻次保留到經(jīng)驗(yàn)存儲(chǔ)的結(jié)構(gòu)中來估計(jì)實(shí)際環(huán)境的轉(zhuǎn)移分布，設(shè)計(jì)了具體算法．實(shí)驗(yàn)結(jié)果表明，該算法可行且有效．相比于原有經(jīng)驗(yàn)回放方式，本研究提出的基于期望的經(jīng)驗(yàn)回放模型存儲(chǔ)更加高效，數(shù)據(jù)利用率更高．由于算法采用了更穩(wěn)定的迭代計(jì)算公式，有效降低了Q學(xué)習(xí)算法的過估計(jì)問題，對(duì)于動(dòng)態(tài)系統(tǒng)的策略收斂速度更快．下一步，我們將深入研究包括如何用近似模型對(duì)狀態(tài)轉(zhuǎn)移概率進(jìn)行擬合，以及如何設(shè)計(jì)有效的算法以使算法收斂更加穩(wěn)定．另外，擬采用參考經(jīng)驗(yàn)回放的連續(xù)思想[15]對(duì)算法進(jìn)行擴(kuò)展.