基于TD-error自適應(yīng)校正的深度Q學(xué)習(xí)主動采樣方法

白辰甲 劉 鵬 趙 巍 唐降龍

(哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院模式識別與智能系統(tǒng)研究中心 哈爾濱 150001)

強化學(xué)習(xí)[1](reinforcement learning, RL)是機器學(xué)習(xí)的重要分支.智能體在與環(huán)境的交互過程中根據(jù)當(dāng)前狀態(tài)選擇動作，執(zhí)行動作后轉(zhuǎn)移到下一個狀態(tài)并獲得獎勵.從智能體執(zhí)行動作到獲得獎勵的過程產(chǎn)生了一條“經(jīng)驗”，智能體從大量經(jīng)驗中學(xué)習(xí)，不斷改進策略，最大化累計獎勵.傳統(tǒng)強化學(xué)習(xí)方法適用于離散狀態(tài)空間，不能有效處理高維連續(xù)狀態(tài)空間中的問題.線性值函數(shù)近似或非線性值函數(shù)近似法將狀態(tài)與值函數(shù)之間的關(guān)系進行參數(shù)化表示[2]，可以處理高維狀態(tài)空間中的問題.其中，線性值函數(shù)近似有良好的收斂性保證，但往往需要人為提取狀態(tài)特征，且模型表達能力有限；非線性值函數(shù)近似沒有嚴(yán)格的收斂性證明，但具有強大的模型表達能力.Tesauro[3-4]將時序差分法(temporal difference, TD)與非線性值函數(shù)近似相結(jié)合，提出了TD-Gammon算法.該算法用前饋神經(jīng)網(wǎng)絡(luò)對狀態(tài)值函數(shù)進行估計，在西洋雙陸棋中達到了人類頂尖水平.

近年來，深度學(xué)習(xí)[5-6]與強化學(xué)習(xí)相結(jié)合[7]的非線性值函數(shù)近似方法在大規(guī)模強化學(xué)習(xí)中表現(xiàn)出良好性能.谷歌DeepMind團隊提出了“深度Q網(wǎng)絡(luò)”[8-9](deep Q-network, DQN)，DQN以圖像序列作為輸入，輸出對動作值函數(shù)的估計，策略表示為卷積神經(jīng)網(wǎng)絡(luò)的參數(shù).DQN在Atari 2600的大多數(shù)視頻游戲上的性能超過了人類專家水平.

對經(jīng)驗樣本的存儲和采樣是DQN的關(guān)鍵問題.DQN在訓(xùn)練中使用誤差梯度反向傳播算法，只有訓(xùn)練樣本集合滿足或近似滿足獨立同分布時才能正常收斂[10].然而，智能體與環(huán)境交互產(chǎn)生的樣本前后具有強相關(guān)性.為了消除樣本相關(guān)性，DQN使用經(jīng)驗池來存儲和管理樣本，在訓(xùn)練中從經(jīng)驗池中隨機取樣.DQN需要容量巨大的經(jīng)驗池(約106)，為了填充經(jīng)驗池，智能體需要頻繁地與環(huán)境進行交互.然而，智能體與環(huán)境交互的代價非常昂貴的，不僅表現(xiàn)在時間的消耗上，更表現(xiàn)在安全性、可控性、可恢復(fù)性等諸多方面[11].因此，研究如何對樣本進行高效采樣、減少智能體與環(huán)境的交互次數(shù)、改善智能體的學(xué)習(xí)效果，對深度強化學(xué)習(xí)研究有重要意義.

目前針對DQN樣本采樣問題的研究主要有2個方面：1)并行采樣和訓(xùn)練.使用多個智能體并行采樣和訓(xùn)練，用異步梯度法更新Q網(wǎng)絡(luò)[12-13]，其思想是通過并行采樣和訓(xùn)練來打破樣本之間的相關(guān)性.2)主動采樣.強調(diào)樣本之間的差異性[14]，為每個樣本設(shè)定優(yōu)先級，按優(yōu)先級進行采樣.Schaul等人[11]提出了優(yōu)先經(jīng)驗回放法(prioritized experience replay, PER)，經(jīng)驗池中樣本被采樣的概率與樣本的存儲優(yōu)先級成正比，存儲優(yōu)先級由經(jīng)驗池中樣本上次參與訓(xùn)練的TD-error決定.TD-error是樣本在使用TD算法更新時目標(biāo)值函數(shù)與當(dāng)前狀態(tài)值函數(shù)的差值，其中目標(biāo)值函數(shù)是立即獎勵與下一個狀態(tài)值函數(shù)之和.盡管PER算法在一定程度上提高了樣本的利用效率，但在包含大量樣本的經(jīng)驗池中，每個時間步僅有少量樣本可以參與Q網(wǎng)絡(luò)迭代，其余樣本無法參與訓(xùn)練，這些樣本的TD-error沒有跟隨Q網(wǎng)絡(luò)的更新而變化，導(dǎo)致樣本的存儲優(yōu)先級無法準(zhǔn)確反映經(jīng)驗池中TD-error的真實分布.

為了進一步提高樣本的采樣效率，應(yīng)當(dāng)以更準(zhǔn)確的采樣優(yōu)先級在經(jīng)驗池中選擇樣本.本文研究發(fā)現(xiàn)，經(jīng)驗池中樣本距離上次被采樣的時間間隔越長，樣本的存儲TD-error偏離真實值越遠.由于長時間未被采樣的樣本數(shù)量巨大，導(dǎo)致存儲優(yōu)先級與真實優(yōu)先級的偏差較大.本文提出一種基于TD-error自適應(yīng)校正的主動采樣模型(active sampling method based on adaptive TD-error correction, ATDC-PER).該模型基于樣本回放周期和網(wǎng)絡(luò)狀態(tài)在樣本與優(yōu)先級偏差之間建立映射關(guān)系，實現(xiàn)對存儲優(yōu)先級的校正，在Q網(wǎng)絡(luò)每次訓(xùn)練中都使用校正后的優(yōu)先級在經(jīng)驗池中選擇樣本.本文提出的偏差模型參數(shù)是自適應(yīng)的，在訓(xùn)練中模型始終跟隨Q網(wǎng)絡(luò)的變化，對采樣優(yōu)先級的估計更為合理.實驗結(jié)果表明，校正后的優(yōu)先級符合經(jīng)驗池中樣本TD-error的分布，利用校正后的優(yōu)先級選擇樣本提高了樣本的利用效率，減少了智能體與環(huán)境的交互，同時改善了智能體的學(xué)習(xí)效果，獲得了更大的累計獎勵.

1 相關(guān)工作

1.1 強化學(xué)習(xí)

強化學(xué)習(xí)的目標(biāo)是最大化累計獎勵.智能體通過從經(jīng)驗中學(xué)習(xí)，不斷優(yōu)化狀態(tài)與動作之間的映射關(guān)系，最終找到最優(yōu)策略(policy).智能體與環(huán)境的交互過程可以用馬爾可夫決策過程[15](Markov decision processes， MDP)來建模.在周期型任務(wù)中，MDP包括一系列離散的時間步0,1,2,…,t,…,T，其中T為終止時間步.在時間步t，智能體觀察環(huán)境得到狀態(tài)的表示St，根據(jù)現(xiàn)有策略π選擇動作At并執(zhí)行.執(zhí)行動作后MDP到達下一個時間步t+1，智能體收到獎勵Rt+1并轉(zhuǎn)移到下一個狀態(tài)St+1.回報定義為折扣獎勵之和，智能體通過調(diào)整策略來最大化回報.動作狀態(tài)值函數(shù)是指智能體處于狀態(tài)s時執(zhí)行動作a，隨后按照策略π與環(huán)境交互直到周期結(jié)束所獲得的期望回報，記為Qπ(s,a).

最優(yōu)策略求解一般遵循“廣泛策略迭代”的思想，包含策略評價和策略提升[1].策略評價是已知策略計算值函數(shù)的過程，策略提升是已知值函數(shù)選擇最優(yōu)動作的過程.策略評價中值函數(shù)Qπ(s,a)的求解可以使用貝爾曼方程[15]轉(zhuǎn)換為遞歸形式

其中，r是立即獎勵，γ是折扣因子.值函數(shù)定義了在策略空間上的偏序關(guān)系，存在最優(yōu)策略π*優(yōu)于(或等同于)其他所有策略.

1.2 深度Q網(wǎng)絡(luò)

深度Q網(wǎng)絡(luò)[9](DQN)遵循Q-learning算法的更新法則，與線性值函數(shù)近似的不同之處在于DQN使用Q網(wǎng)絡(luò)來表示動作值函數(shù)，進而表示策略.Q網(wǎng)絡(luò)是由卷積層和全連接層組成的卷積神經(jīng)網(wǎng)絡(luò)(CNN).DQN的主要特點有2個：

1) 使用2個獨立的Q網(wǎng)絡(luò).分別使用θ和θ-代表Q網(wǎng)絡(luò)和目標(biāo)Q網(wǎng)絡(luò)的參數(shù)，每隔L個時間步將Q網(wǎng)絡(luò)的參數(shù)復(fù)制到目標(biāo)Q網(wǎng)絡(luò)中，即θ-←θ，隨后θ-在L個時間步內(nèi)保持不變.DQN中TD-error定義為

(1)

2) 使用經(jīng)驗池存儲和管理樣本，使用經(jīng)驗回放[25]選擇樣本.樣本存儲于經(jīng)驗池中，從經(jīng)驗池中隨機抽取批量樣本訓(xùn)練Q網(wǎng)絡(luò).使用經(jīng)驗回放可以消除樣本之間的相關(guān)性，使參與訓(xùn)練的樣本滿足或近似滿足獨立同分布.

在DQN的基礎(chǔ)上，Hasselt等人[26-27]指出，DQN在計算TD-error時使用相同的Q網(wǎng)絡(luò)來選擇動作和計算值函數(shù)會導(dǎo)致值函數(shù)的過高估計，進而提出了DDQN(double DQN)算法.該算法用Q網(wǎng)絡(luò)來選擇動作，用目標(biāo)Q網(wǎng)絡(luò)來估計值函數(shù)，從而消除了對值函數(shù)的過高估計，并提升了智能體的累計獎勵.DDQN中TD-error由式(2)計算：

(2)

此外，一些研究從不同角度提出了DQN的改進方法，主要思路可以分為：1)從探索和利用的角度[28-31]，將傳統(tǒng)強化學(xué)習(xí)中使用的探索與利用策略擴展到深度強化學(xué)習(xí)中，改進DQN中的ε-貪心策略.2)從網(wǎng)絡(luò)結(jié)構(gòu)的角度，使用競爭式網(wǎng)絡(luò)結(jié)構(gòu)[32]，分別估計動作值函數(shù)和優(yōu)勢函數(shù).3)從并行訓(xùn)練的角度[12-13]，消除樣本之間的相關(guān)性，同時加速訓(xùn)練.4)從減少訓(xùn)練中獎勵方差的角度[33]，使用多個迭代步的延遲估計Q值，使其更加穩(wěn)定.5)從模型之間知識遷移和多任務(wù)學(xué)習(xí)的角度[34-35]，擴展DQN的使用范圍.6)從視覺注意力的角度，使智能體在訓(xùn)練中將注意力集中于有價值的圖像區(qū)域[36].7)從主動采樣，減少與環(huán)境交互次數(shù)的角度[11]，使用基于TD-error的優(yōu)先經(jīng)驗回放來提高樣本的利用效率.

1.3 優(yōu)先經(jīng)驗回放

Fig. 1 The main architecture of ATDC-PER model 圖1 本文方法(ATDC-PER)的總體結(jié)構(gòu)

優(yōu)先經(jīng)驗回放是一種有效的管理經(jīng)驗池的方法.原始的DQN算法在訓(xùn)練時不考慮經(jīng)驗池中樣本之間的差異，隨機抽取樣本進行訓(xùn)練，導(dǎo)致樣本的利用效率較低，智能體需要頻繁地與環(huán)境進行交互.針對這一問題，Schaul等人[11]提出了優(yōu)先經(jīng)驗回放法(PER)來估計每個樣本的優(yōu)先級，按照優(yōu)先級選擇樣本訓(xùn)練Q網(wǎng)絡(luò).樣本優(yōu)先級由樣本的TD-error分布決定.樣本的TD-error絕對值越大，在訓(xùn)練中造成的Q網(wǎng)絡(luò)損失越大，表明該樣本給Q網(wǎng)絡(luò)帶來的信息量越大，在Q網(wǎng)絡(luò)后續(xù)迭代中應(yīng)“優(yōu)先”選擇該樣本參與訓(xùn)練.PER算法的主要特點有3個：

1) 樣本優(yōu)先級基于樣本上次參與訓(xùn)練時的TD-error值.長時間未參與訓(xùn)練的樣本在經(jīng)驗池中存儲的TD-error長時間未更新，這些樣本的TD-error無法跟隨Q網(wǎng)絡(luò)的變化.只有上一個時間步參與訓(xùn)練的批量樣本的TD-error值被更新，然而這部分樣本僅占經(jīng)驗池中樣本的少數(shù).

2) 采樣時在優(yōu)先級的基礎(chǔ)上引入隨機性.完全按照優(yōu)先級進行采樣會降低樣本的多樣性，因此PER算法中引入隨機性，使樣本被抽取的概率與優(yōu)先級成正比，同時所有樣本都有機會被采樣.

3) 優(yōu)先級的引入相對于均勻抽樣改變了樣本的分布，引入了誤差.PER算法使用重要性采樣權(quán)重對誤差進行補償.在計算損失函數(shù)梯度時，需在原有梯度的基礎(chǔ)上乘以重要性采樣權(quán)重，按補償后的梯度進行更新.

PER算法[11]具有高度的靈活性，可與離策略的深度強化學(xué)習(xí)方法進行廣泛結(jié)合.例如，文獻[37-38]將PER算法和策略梯度法結(jié)合，提高了確定性策略梯度算法[39-40](deep deterministic policy gradient, DDPG)在仿真機器人控制中的數(shù)據(jù)利用效率；PER算法與深度Q學(xué)習(xí)的結(jié)合提高了經(jīng)驗池中樣本的利用效率，顯著減少了智能體與環(huán)境的交互次數(shù)，提升了智能體的最優(yōu)策略得分[11].

2 基于TD-error校正的主動采樣模型

PER算法的問題在于，經(jīng)驗池中存儲的TD-error值相對于Q網(wǎng)絡(luò)來說更新不及時，無法準(zhǔn)確反映樣本的優(yōu)先級.在每次迭代中Q網(wǎng)絡(luò)都會更新自身參數(shù)，而經(jīng)驗池僅可更新參與訓(xùn)練的批量樣本的TD-error值，此類樣本的數(shù)量約占經(jīng)驗池容量的0.1%.這導(dǎo)致大多數(shù)樣本的存儲TD-error無法跟隨Q網(wǎng)絡(luò)的變化，并進一步導(dǎo)致樣本在經(jīng)驗池中的存儲優(yōu)先級與“真實”優(yōu)先級之間存在偏差.本文分析了這種偏差對學(xué)習(xí)的影響，并闡述了依據(jù)真實或逼近真實的TD-error分布產(chǎn)生的優(yōu)先級來選擇樣本能夠使深度Q網(wǎng)絡(luò)以更高的效率收斂到最優(yōu)策略.

本文提出基于TD-error自適應(yīng)校正的主動采樣模型(ATDC-PER)來校正樣本的存儲優(yōu)先級，使用校正后的優(yōu)先級分布進行主動采樣，能夠提高經(jīng)驗池中樣本的利用效率.圖1是本文方法ATDC-PER的總體結(jié)構(gòu)，主要包括“偏差模型”和“優(yōu)先級校正”兩部分.其中，優(yōu)先級校正需在所有時間步進行，偏差模型則每隔D個時間步更新1次.2.1節(jié)使用引例說明TD-error及樣本優(yōu)先級分布對學(xué)習(xí)的作用，2.2節(jié)闡述ATDC-PER的建模過程，2.3節(jié)給出算法描述和復(fù)雜度分析.

2.1 TD-error偏差分析

本節(jié)用強化學(xué)習(xí)中的經(jīng)典問題平衡車[41](CartPole)為引例①https:gym.openai.comenvsCartpole-v0，說明PER算法中經(jīng)驗池的存儲TD-error與真實TD-error之間存在偏差，并分析TD-error分布對學(xué)習(xí)的作用.

CartPole的狀態(tài)表示為4維向量，包括桿的角度、桿運動的角速度、車的位置和車運動的速度，如圖2所示：

Fig. 2 The state of CartPole圖2 倒立擺的狀態(tài)表示

智能體通過向小車施加+1或-1的力來盡力保持桿的平衡.在時間步t，如果桿與垂直方向的角度不超過15度且小車與中心的距離不超過2.4個單元，則獎勵為+1，否則獎勵為-1同時周期結(jié)束.設(shè)1個周期的時間步不超過200步，則智能體在1個周期內(nèi)所獲得的最大獎勵不超過200.用基于DDQN的PER算法來訓(xùn)練Q網(wǎng)絡(luò)，Q網(wǎng)絡(luò)是包含64個隱含層節(jié)點的3層全連接網(wǎng)絡(luò)，經(jīng)驗池容量為50 000.

PER算法中經(jīng)驗池用樣本集合E={e(1),e(2),…,e(m)}表示，其中序號為i的樣本e(i)=s(i),a(i),r(i),s′(i)∈E.PER算法在每次迭代時抽取E中的1個批量樣本進行訓(xùn)練.本文將樣本e(i)上次參與訓(xùn)練的TD-error值稱為樣本的存儲TD-error，記為δ(i).設(shè)當(dāng)前時間步為t，e(i)上次參與訓(xùn)練的時間步為t-τ(i)，則δ(i)由式(3)計算[27]：

(3)

由式(3)可知，存儲TD-error計算中使用的參數(shù)θt-τ(i)不是當(dāng)前Q網(wǎng)絡(luò)參數(shù)，而是τ(i)個時間步之前的參數(shù).在τ(i)個時間步內(nèi)Q網(wǎng)絡(luò)經(jīng)歷了τ(i)次參數(shù)迭代，而存儲TD-error值卻保持不變.這導(dǎo)致樣本的存儲TD-error與當(dāng)前Q網(wǎng)絡(luò)不匹配，且τ(i)的值越大，這種不匹配程度越高.新樣本加入經(jīng)驗池時τ(i)=1，每經(jīng)歷1個時間步，參與該時間步訓(xùn)練的樣本τ(i)置1，未參與該時間步訓(xùn)練的樣本τ(i)加1.由于經(jīng)驗池滿后新樣本會覆蓋老樣本，因此所有樣本τ(i)的取值范圍均在1到經(jīng)驗池樣本總量之間.圖3顯示了CartPole在訓(xùn)練周期為420時經(jīng)驗池樣本的τ(i)的分布，樣本按τ(i)由小到大排序，經(jīng)驗池中樣本總數(shù)為50 000.圖3表明，經(jīng)驗池中有大量樣本的τ(i)值較大，這些樣本長期沒有參與訓(xùn)練，δ(i)長期未更新.因此，存儲優(yōu)先級與當(dāng)前Q網(wǎng)絡(luò)的不匹配程度較高.

Fig. 3 Distribution of τ(i) in experience memory when training episode is 420圖3 訓(xùn)練周期為420時經(jīng)驗池中樣本的τ(i)的分布

(4)

p(i)=(|δ(i)|+ε)α,

(5)

(6)

其中ε和α均為常數(shù).樣本TD-error的絕對值越大，在采樣中樣本的優(yōu)先級就越高.

Fig. 4 Distribution of p(i) and in CartPole training when training episode is 180圖4 CartPole訓(xùn)練周期為180時p(i)和分布圖

(7)

圖5顯示了優(yōu)先級偏差的絕對值|Δp(i)|的分布，樣本仍按照p(i)由大到小排序.

Fig. 5 Distribution of |Δp(i)| in CartPole training when training episode is 180圖5 CartPole訓(xùn)練周期為180時|Δp(i)|的分布圖

圖4和圖5表明，PER算法中使用基于δ(i)的存儲優(yōu)先級進行主動采樣存在2個問題：

2)δ(i)的分布不能準(zhǔn)確反映經(jīng)驗池的真實情況.其中，當(dāng)|δ(i)|較大時，樣本被抽取的概率高，τ(i)值較小，期間Q網(wǎng)絡(luò)變化不明顯，優(yōu)先級偏差較小，此時可以使用存儲優(yōu)先級作為真實優(yōu)先級的近似估計；但當(dāng)|δ(i)|較小時，τ(i)值較大，Q網(wǎng)絡(luò)在τ(i)個時間步內(nèi)參數(shù)變化較大，導(dǎo)致存儲優(yōu)先級偏離真實優(yōu)先級的分布，此時基于δ(i)的存儲優(yōu)先級不能準(zhǔn)確反映經(jīng)驗池的情況.

Fig. 6 Training curve comparison using experience replay with p(i) and 圖6 使用p(i)和作為優(yōu)先級的訓(xùn)練曲線對比

2.2 ATDC-PER模型

真實優(yōu)先級和存儲優(yōu)先級的偏差分布具有穩(wěn)定性，所以ATDC-PER方法對偏差模型更新周期D的選取是不敏感的.真實優(yōu)先級與存儲優(yōu)先級的不同之處在于計算時使用的Q網(wǎng)絡(luò)參數(shù)不同，真實優(yōu)先級使用時刻t的Q網(wǎng)絡(luò)參數(shù)，而存儲優(yōu)先級使用t-τ(i)時刻的Q網(wǎng)絡(luò)參數(shù)，二者的區(qū)別在于τ(i)的分布.如圖3所示，τ(i)在經(jīng)驗池中呈現(xiàn)長尾分布，最小值為1，最大值為經(jīng)驗池樣本總量.在訓(xùn)練中經(jīng)驗池填充滿后容量不再發(fā)生變化，τ(i)分布具有穩(wěn)定性，因此偏差模型不需要頻繁更新.

ATDC-PER算法在訓(xùn)練過程中偏差模型分段更新的示意圖如圖7所示，橫軸代表訓(xùn)練時間步，縱軸代表智能體在周期內(nèi)的累計獎勵.偏差模型更新后的D個時間步內(nèi)均使用該模型進行優(yōu)先級校正，可以極大地減少時間開銷.

Fig. 7 Interval update policy in ATDC-PER algorithm圖7 ATDC-PER算法的分段更新策略示意圖

2.2.1 偏差模型

從經(jīng)驗池中提取的樣本特征是偏差模型的輸入，真實優(yōu)先級和存儲優(yōu)先級之間的優(yōu)先級偏差作為樣本標(biāo)簽，是偏差模型的輸出.使用線性回歸模型對樣本特征與樣本標(biāo)簽之間的關(guān)系進行建模，通過最小化平方損失函數(shù)來求解模型參數(shù)w.

1) 樣本特征.樣本特征是針對單個樣本而言的.特征在訓(xùn)練中的經(jīng)驗池中保存且與優(yōu)先級偏差相關(guān).樣本特征包括：

(8)

(9)

(10)

(11)

Atari游戲Pong①https:gym.openai.comenvsPong-v0和Breakout②https:gym.openai.comenvsBreakout-v0在訓(xùn)練時間步為105時經(jīng)驗池中所有樣本的樣本特征,和樣本標(biāo)簽Δ的分布如圖8所示，樣本按照存儲優(yōu)先級排序，具體的設(shè)置將在實驗部分介紹.圖8表明，樣本的存儲優(yōu)先級和回放周期都與優(yōu)先級偏差Δ密切相關(guān).

Fig. 8 Distribution of feature , and label Δ in Pong and Breakout when t=105圖8 Pong和Breakout在t=105時樣本特征,和樣本標(biāo)簽Δ的分布

3) 偏差模型參數(shù)求解.使用回歸模型來對樣本特征和樣本標(biāo)簽之間的關(guān)系進行建模.由于樣本特征與樣本標(biāo)簽之間的關(guān)系明顯，因此使用線性回歸模型.同時，線性回歸模型在當(dāng)前的輸入輸出條件下存在閉式解，不需要使用梯度法迭代求解，時間開銷很小.

權(quán)重向量w的維度與特征x(i)的維度相同.根據(jù)線性回歸模型的定義，假設(shè)函數(shù)hw(x(i))表示為

(13)

設(shè)當(dāng)前經(jīng)驗池中樣本數(shù)為m，則全體樣本組成的特征矩陣X∈m×6，表示為

(14)

(15)

損失函數(shù)為平方誤差損失，記為J(w).經(jīng)驗池中所有樣本的平均損失表示為

(16)

參數(shù)向量w為使得損失J(w)取最小值的解.由于特征矩陣X的元素均大于0，w存在閉式解.經(jīng)推導(dǎo)可得，最小化損失函數(shù)J(w)的w的解為

w=(XTX)-1XTy.

(17)

2.2.2 優(yōu)先級校正

(18)

(19)

Fig. 9 Distribution of , and at step t=107 in Breakout training圖9 Breakout訓(xùn)練中t=107時,和分布

2.3 算法描述和復(fù)雜度分析

2.3.1 算法描述

ATDC-PER的算法流程如算法1所示.

算法1. ATDC-PER算法.

輸入：偏差模型特征階數(shù)K、偏差模型更新周期D、獎勵折扣因子γ、樣本批量大小k、學(xué)習(xí)率η、經(jīng)驗池容量N、偏差模型參數(shù)α、重要性權(quán)重β、訓(xùn)練終止時間步T、目標(biāo)Q網(wǎng)絡(luò)更新頻率L；

輸出：Q網(wǎng)絡(luò)參數(shù)；

初始化：經(jīng)驗池為空，批量梯度Δ=0，初始化Q網(wǎng)絡(luò)和目標(biāo)Q網(wǎng)絡(luò)參數(shù)為θ和θ-.

① 根據(jù)初始狀態(tài)S0，以ε-貪心選擇動作A0～πθ(S0)；

② fort=1 toTdo

③ 觀察到狀態(tài)St并獲得獎勵Rt；

④ 將經(jīng)驗序列(St-1,At-1,Rt,St)存儲到經(jīng)驗池中，并賦予當(dāng)前經(jīng)驗池中最大的優(yōu)先級；

⑤ ift%D==0

⑥ 樣本特征提取，構(gòu)造如式(14)所示的特征矩陣X；

⑧ 偏差模型求解，將偏差模型參數(shù)更新為w=(XTX)-1XTy；

⑨ end if

Q(Sj-1,Aj-1)；

其中行⑤～⑨是偏差模型更新的過程，需在t,t+D,t+2D,…等時間步計算經(jīng)驗池的樣本特征和優(yōu)先級偏差進行訓(xùn)練，求解模型參數(shù)w.行⑩是優(yōu)先級校正的過程，通過偏差模型得到樣本真實優(yōu)先級的估計.行在優(yōu)先級的基礎(chǔ)上加入隨機性，樣本被采樣的概率與優(yōu)先級成正比，同時所有樣本都有機會被采樣.行～計算損失函數(shù)的梯度，計算梯度時需在TD-error的基礎(chǔ)上乘以重要性權(quán)重(importance sampling weight)系數(shù)[42]，原因是按照優(yōu)先級采樣與均勻采樣相比會給梯度的計算帶來誤差，因此使用采樣概率的比值φ進行補償[11]，并使用全部樣本的φ的最大值進行規(guī)約，如式(20)所示.

φj=(N×P(j))-β,

(20)

其中,k=1,2,…,N,N為經(jīng)驗池容量，β是一個常數(shù)，P(j)為樣本e(j)的采樣優(yōu)先級在全體樣本中所占的比例，如式(21)所示.

(21)

2.3.2 復(fù)雜度分析

ATDC-PER算法包括偏差模型和優(yōu)先級校正兩部分.根據(jù)分段更新策略，在執(zhí)行D次優(yōu)先級校正的同時會執(zhí)行一次偏差模型更新.由于偏差模型更新的時間復(fù)雜度較高，而優(yōu)先級校正僅執(zhí)行矩陣乘法和加法，時間復(fù)雜度低，所以分段更新策略可以使復(fù)雜度高的部分以極低的頻率執(zhí)行，從而減少時間開銷.

1) 偏差模型的復(fù)雜度分析.偏差模型更新包括樣本特征提取、樣本標(biāo)簽提取和模型求解3個階段，分析如下：

① 樣本特征提取.原始的樣本特征維度為2，提取K階多項式后的特征向量x(i)∈，特征矩陣X∈.其中，m的值不超過經(jīng)驗池總?cè)萘?，且在?jīng)驗池填充滿之后不再變化，是一個常數(shù).因此特征提取的時間復(fù)雜度和空間復(fù)雜度均為O(K2).

③ 偏差模型求解.模型求解階段的時間消耗集中在式(17)中對參數(shù)向量w的求解上.XTX∈，在此基礎(chǔ)上求逆的時間復(fù)雜度為Ο(K6)，空間復(fù)雜度為Ο(K2).

2) 優(yōu)先級校正的復(fù)雜度分析.優(yōu)先級校正階段在提取樣本特征Xt后與參數(shù)向量w執(zhí)行矩陣乘法，時間復(fù)雜度為Ο(K4)，空間復(fù)雜度為Ο(K2).

由于ATDC-EPR算法中間隔D個時間步偏差模型才更新一次，D的取值較大，其余時間步都僅執(zhí)行優(yōu)先級校正的操作，因此總體時間復(fù)雜度為Ο(K4)，空間復(fù)雜度為Ο(K2).另外，一般K=2時偏差模型就可以很好地估計優(yōu)先級偏差，此時求解參數(shù)w所需的逆矩陣(XTX)-1∈6×6，規(guī)模較小，可以快速求解.

經(jīng)過復(fù)雜度分析，本文提出的ATDC-PER算法以極小的時間和空間代價就可以在Q網(wǎng)絡(luò)每次迭代中校正經(jīng)驗池中樣本的存儲優(yōu)先級，使用校正后的優(yōu)先級選擇樣本.

3 實驗結(jié)果與分析

本節(jié)首先介紹實驗平臺和環(huán)境，隨后介紹ATDC-PER算法的參數(shù)選擇，通過對比實驗說明參數(shù)對性能的影響，最后從智能體的學(xué)習(xí)速度和最優(yōu)策略的質(zhì)量2方面對實驗結(jié)果進行分析.

3.1 實驗平臺描述

實驗使用基于Atari 2600游戲平臺Arcade Learning Environment(ALE)[43]的OpenAI集成環(huán)境[44].ALE平臺包含數(shù)十個視頻游戲，并對外提供接口.ALE平臺的挑戰(zhàn)在于游戲種類和數(shù)量豐富，包含益智類、體育類、策略類、射擊類、搏斗類等多種類型的游戲，需多個游戲中使用同一算法，在超參數(shù)固定的情況下，僅以原始屏幕圖像作為輸入進行學(xué)習(xí)和訓(xùn)練.

本文選擇ALE平臺中的19個游戲進行實驗，游戲的簡要介紹列于表1，各游戲界面如圖10所示.可以看出，游戲類型多樣，游戲的界面風(fēng)格不同，在訓(xùn)練中Q網(wǎng)絡(luò)的輸入不同.同時，每個游戲中智能體需完成的任務(wù)不同，即最終學(xué)習(xí)的策略也不同.

Table 1 A Brief Introduction to 19 Atari Games表1 19個Atari游戲的簡要介紹

Fig. 10 State representations of 19 Atari games圖10 19個Atari游戲的狀態(tài)表示

本文使用的計算平臺為戴爾PowerEdge T630塔式工作站，工作站配置2顆Intel Xeon E5-2609 CPU、4塊NVIDIA GTX-1080Ti顯卡(GPU)和64 GB內(nèi)存，每個游戲使用單獨的一塊顯卡進行訓(xùn)練.卷積神經(jīng)網(wǎng)絡(luò)基于Tensorflow[45]開源庫實現(xiàn)，本文核心代碼、實驗結(jié)果和測試視頻均可下載①http:pr-ai.hit.edu.cn20180510c1049a207703page.htm.

3.2 ATDC-PER參數(shù)選擇

ATDC-PER算法在全部游戲中使用相同的超參數(shù)集合，以驗證模型的通用性.ATDC-PER算法在PER算法的基礎(chǔ)上增加了2個超參數(shù)，分別是偏差模型更新周期D和偏差模型特征階數(shù)K，其余參數(shù)的設(shè)置與PER算法的設(shè)置相同.狀態(tài)表示為原始圖像預(yù)處理并疊加4幀組成的84×84×4的矩陣；Q網(wǎng)絡(luò)為3層卷積神經(jīng)網(wǎng)絡(luò)，輸出每個動作的值函數(shù)，目標(biāo)Q網(wǎng)絡(luò)的更新頻率設(shè)為40 000；鑒于不同游戲的分值計算方式不同，使用符號函數(shù)對獎勵進行規(guī)約；為了使訓(xùn)練更加穩(wěn)定，對回傳的梯度進行限制，使其不超過10.使用基于平方誤差損失的Adam優(yōu)化器進行訓(xùn)練，批量大小k=32，學(xué)習(xí)率設(shè)為10-4，折扣因子γ=0.99；探索因子在前400萬幀從1.0線性遞減至0.1，在隨后的時間步內(nèi)以之前速度的110線性遞減至0.01后保持不變；經(jīng)驗池容量設(shè)為106；優(yōu)先級計算中使用的參數(shù)α=0.6；重要性權(quán)重計算中使用的參數(shù)β初始值設(shè)為0.4，在訓(xùn)練中線性增加至1.0.

3.2.1 偏差模型更新周期

通過在Alien，Breakout，Pong的訓(xùn)練過程中使用不同的偏差模型更新周期D來測試參數(shù)D對Q網(wǎng)絡(luò)學(xué)習(xí)的影響.在訓(xùn)練過程中的時刻t訓(xùn)練偏差模型得偏差模型參數(shù)wt，使用不同的參數(shù)D，測試模型wt在位于時刻t+D的經(jīng)驗池樣本的平均損失，損失的計算如式(16)所示.不同的偏差模型更新周期D下的平均損失對比列如表2所示：

Table 2 Average Loss of Bias Model Trained in t Steps and Tested in t+D Steps Under Different D Values表2 比較不同D值下時刻t訓(xùn)練的偏差模型在時刻t+D測試的平均損失

由表2可知，隨著偏差模型更新周期D的增加，損失總體升高.但從數(shù)值上看，損失的升高并不明顯，特別是在105個時間步內(nèi)，因此實驗中將D的值設(shè)置為105.表2數(shù)據(jù)表明本文提出的偏差模型具有較強的泛化能力，對偏差模型更新周期D的選擇不敏感，偏差模型可以在訓(xùn)練后較長的時間步內(nèi)適用，同時也驗證了圖7所示的分段更新策略的合理性.

3.2.2 偏差模型特征階數(shù)

偏差模型的特征階數(shù)K越大，模型復(fù)雜度越高，訓(xùn)練誤差越小，但計算復(fù)雜度也隨之升高，同時可能引起過擬合.通過在游戲Alien，Breakout，Pong的訓(xùn)練過程中進行粗搜索來選擇K的值.實驗使用不同的K值進行訓(xùn)練，記錄多個位于偏差模型更新周期中心的經(jīng)驗池樣本，比較經(jīng)驗池樣本的平均損失，結(jié)果列于表3.表3中數(shù)據(jù)表明，隨著K值的增加，損失總體下降，但在K>2時損失的變化已經(jīng)不顯著，同時在Alien中K>3時有過擬合的趨勢.因此，綜合考慮損失和計算消耗，本文實驗將多項式特征的階數(shù)設(shè)為K=2.

Table 3 Average Loss at the Center of Renewal Period of Correction Model Under Different K Values表3 比較不同K值下處于偏差模型更新周期中心的經(jīng)驗池平均損失

3.3 對比實驗與分析

本文選擇2個基線算法進行對比，分別為DDQN[27]和優(yōu)先經(jīng)驗回放[11](PER).其中，DDQN算法中樣本沒有優(yōu)先級，在訓(xùn)練時從經(jīng)驗池中隨機取樣；PER算法在DDQN的基礎(chǔ)上為每個樣本設(shè)置存儲優(yōu)先級，存儲優(yōu)先級與樣本上次參與訓(xùn)練時的TD-error絕對值成正比，在采樣時根據(jù)存儲優(yōu)先級依概率選擇樣本.本文通過偏差模型對存儲優(yōu)先級進行校正，用校正后的真實優(yōu)先級的估計進行采樣，提高了樣本的利用效率.

算法的評價標(biāo)準(zhǔn)包括智能體的學(xué)習(xí)速度和智能體學(xué)習(xí)到的最優(yōu)策略的質(zhì)量.

3.3.1 智能體的學(xué)習(xí)速度

圖11顯示了19個Atari游戲的訓(xùn)練曲線，橫軸代表時間步，每個時間步智能體與ALE環(huán)境交互一次，ALE環(huán)境會產(chǎn)生一幀新的圖像.縱軸代表智能體在周期內(nèi)獲得的累計獎勵.在訓(xùn)練開始后，隨著迭代的進行，智能體的水平不斷提高，獎勵值不斷增大，達到峰值后神經(jīng)網(wǎng)絡(luò)的訓(xùn)練可能趨于過擬合，因此訓(xùn)練后期獎勵值可能會有波動.

ATDC-PER算法在19個游戲中的15個游戲收斂速度更快，能夠以更少的交互次數(shù)達到最大獎勵，如圖11所示.特別是在Breakout，DoubleDunk，Enduro，Pong，Robotank，UpNDown這6個游戲中

Fig. 11 Comparison of our method with PER [11] and DDQN [27] algorithms in training curve of 19 Atari games圖11 本文方法在19個Atari游戲中與PER[11]和DDQN[27]算法的訓(xùn)練曲線對比

速度提升明顯，分別如圖11(f)(j)(k)(m)(q)(s)所示，在訓(xùn)練的相同時間步，ATDC-PER算法中智能體的得分水平總體優(yōu)于DDQN和PER算法.圖11中的曲線表明，本文提出的ATDC-PER算法通過在訓(xùn)練中校正經(jīng)驗池樣本的存儲優(yōu)先級，提高了經(jīng)驗池樣本的利用效率，提升了智能體的學(xué)習(xí)速度，減少了智能體與環(huán)境的交互次數(shù)，使智能體以更少的迭代步收斂.

3.3.2 最優(yōu)策略的質(zhì)量

最優(yōu)策略反映智能體最終的學(xué)習(xí)結(jié)果，訓(xùn)練結(jié)束后使用最優(yōu)策略可以指導(dǎo)智能體在ALE環(huán)境中獲得良好表現(xiàn).ATDC-PER算法中策略表示為Q網(wǎng)絡(luò)參數(shù)，訓(xùn)練結(jié)束后智能體可以得到完整可復(fù)用的策略.訓(xùn)練過程中保存每個時間步所在周期的獎勵值，同時每隔105個時間步保存一次Q網(wǎng)絡(luò)參數(shù)，訓(xùn)練結(jié)束后選擇獎勵曲線平滑后處于峰值點的Q網(wǎng)絡(luò)參數(shù)作為最優(yōu)策略，通過測試最優(yōu)策略的質(zhì)量對學(xué)習(xí)效果進行評價.

最優(yōu)策略的評價方法與DDQN[27]中相同，首先，周期開始時智能體與環(huán)境隨機進行1～31次無動作交互，為測試提供隨機的初始狀態(tài).隨后，智能體按照最優(yōu)策略的ε-貪心策略選擇動作，探索因子為0.05.每個周期智能體與環(huán)境最多進行18 000個時間步的交互，策略的最終得分為100個測試周期得分的平均值.鑒于每個游戲的分值計算方式不同，使用式(22)在實際得分的基礎(chǔ)上計算規(guī)約得分.

(22)

其中,scorerandom為隨機智能體的得分，scorehuman為人類專家的得分，規(guī)約后的分值大于100%表明智能體的水平已經(jīng)超過了人類專家水平.

19個Atari游戲總體的最優(yōu)策略評價結(jié)果比較列于表4，單個游戲的評價結(jié)果列于表5.表5中隨機智能體(random)、人類專家(human)和DDQN算法的得分來源于文獻[27]，PER算法的得分來源于文獻[11].

Table 4 Summary of Normalized Score on All Games 表4 全部游戲的規(guī)約得分評價表 %

Table 5 Raw Scores and Normalized Scores on All Games表5 全部游戲的實際得分和規(guī)約得分表

3.3.3 綜合評價

表6顯示了19個Atari游戲中智能體學(xué)習(xí)速度和最優(yōu)策略質(zhì)量的綜合評價.結(jié)果表明，本文使用偏差模型校正后的真實優(yōu)先級的估計來選擇樣本能夠在訓(xùn)練中提升智能體的學(xué)習(xí)速度，同時提高最優(yōu)策略的質(zhì)量.本文算法在2種評價指標(biāo)下都取得最好成績的游戲達1419個，其中在1519個游戲中提升了智能體的學(xué)習(xí)速度，減少了智能體與環(huán)境的交互次數(shù)；在1519個游戲中改善了智能體的學(xué)習(xí)效果，提升了最優(yōu)策略的質(zhì)量.Boxing游戲比較簡單，3種算法均能收斂到接近最大獎勵值，本文算法和PER算法的收斂速度均略低于DDQN算法，但本文方法的最優(yōu)策略得分優(yōu)于其余2種算法，如圖11(e)所示.BeamRider，NameThisGame這2個游戲不同方法的訓(xùn)練曲線交錯上升，最后各算法達到的最優(yōu)策略質(zhì)量相似，均明顯超過了人類專家水平.RoadRunner中本文方法的收斂速度優(yōu)于DDQN和PER算法，最優(yōu)策略得分略低于PER算法.PrivateEye游戲較難，3種算法的最優(yōu)策略得分均不足人類專家得分的1%，均沒有得到較好的結(jié)果.

Table 6 Comprehensive Evaluation on All Games表6 全部游戲的綜合評價表

Note: ■ shows this method is the best among all of the comparison methods.

由表4和表5數(shù)據(jù)可知，ATDC-PER算法能夠在全部19個游戲中的15個游戲獲得更好的最優(yōu)策略.最優(yōu)策略規(guī)約得分的中位數(shù)相對于PER算法[11]提高12%，平均數(shù)提高83.3%.實驗結(jié)果表明，本文方法通過提高經(jīng)驗池中樣本的采樣效率，可以改善智能體的最終學(xué)習(xí)效果，使智能體收斂到更好的最優(yōu)策略.

4 結(jié) 論

深度Q學(xué)習(xí)中，基于優(yōu)先經(jīng)驗回放的方法在訓(xùn)練中樣本的存儲優(yōu)先級不能跟隨Q網(wǎng)絡(luò)迭代而更新，存儲優(yōu)先級不能準(zhǔn)確反映經(jīng)驗池中樣本TD-error分布的真實情況，從而降低了大量樣本的利用效率.使用樣本的真實優(yōu)先級對經(jīng)驗池樣本進行采樣能夠明顯提高經(jīng)驗池樣本的利用效率和學(xué)習(xí)的效果.

本文提出的基于TD-error自適應(yīng)校正的主動采樣方法，利用樣本的回放周期和Q網(wǎng)絡(luò)狀態(tài)能夠校正樣本的優(yōu)先級偏差，得到樣本真實優(yōu)先級的估計值，以極小的代價逼近真實優(yōu)先級的分布.偏差模型在訓(xùn)練過程中分段更新，且對更新周期不敏感，偏差模型特征階數(shù)較小時就可以很好地估計優(yōu)先級偏差，分段更新策略顯著降低了本文方法的計算復(fù)雜度.在Q網(wǎng)絡(luò)迭代的每個時間步使用校正后的優(yōu)先級進行采樣，能夠提升Q網(wǎng)絡(luò)訓(xùn)練中經(jīng)驗池樣本的利用效率.在Atari 2600中的實驗結(jié)果表明，使用本文方法進行主動采樣提升了智能體的學(xué)習(xí)速度，減少了智能體與環(huán)境的交互次數(shù)，同時改善了智能體的學(xué)習(xí)效果，提升了最優(yōu)策略的質(zhì)量.