隨機狀態(tài)下基于期望經(jīng)驗回放的Q學(xué)習(xí)算法

張 峰，錢 輝，董春茹，花 強

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

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

Qt(s,a))

(1)

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

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

1 經(jīng)驗回放

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

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

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

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

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

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

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

(2)

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

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

Qt(s,a)]

(3)

(4)

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

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

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

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

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

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

(5)

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

圖2 機器人隨機行走問題Fig.2 Robot random walk

3 實 驗

3.1 實驗設(shè)置

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

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

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

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

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

表1 最優(yōu)策略下動作價值

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

3.2 實驗結(jié)果

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

3.3 算法的進一步分析

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

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

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

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

表2 基于均勻回放的算法收斂后動作價值的誤差

表3 基于期望回放算法收斂后動作價值的誤差

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

結(jié) 語

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