楊 彤, 秦 進, 謝仲濤, 袁琳琳
1(貴州大學 計算機科學與技術學院, 貴陽 550025)
2(貴州開放大學 信息工程學院, 貴陽 550025)
深度強化學習[1]通過將深度學習[2]與強化學習[3]相結合, 在序貫決策問題上取得顯著進展. 例如Atari 2600視頻游戲[4]、棋盤游戲[5]、自動駕駛[6]等領域. 深度學習的引入解決了傳統(tǒng)強化學習在處理高維狀態(tài)空間時所遇到的問題, 通過使用線性或非線性函數(shù)對強化學習中的值函數(shù)進行表示, 能直接從高維狀態(tài)輸入中學習到策略.
即便深度強化學習在很多復雜環(huán)境中取得突破,但目前仍有一些問題影響著深度強化學習的發(fā)展[7]. 其中樣本效率問題是強化學習的挑戰(zhàn)之一, 強化學習的學習過程是通過智能體與環(huán)境的相互作用, 探索未知的區(qū)域并獲得數(shù)據(jù)樣本, 再根據(jù)所獲的數(shù)據(jù)樣本進策略更新. 因而強化學習的學習過程中沒有固定的數(shù)據(jù)集,需要通過智能體與環(huán)境進行大量交互獲取數(shù)據(jù)樣本,并依據(jù)樣本不斷改進策略, 最終才能適應環(huán)境以得到良好的策略. 這樣會導致智能體需要消耗極大的時間成本用于獲取數(shù)據(jù)樣本, 特別是在現(xiàn)實環(huán)境中, 會承擔很多風險與代價. 例如深度Q網絡[1]在Arcade Learning Environment (ALE)平臺的游戲中需要大概兩億幀的狀態(tài)轉移樣本(大約39天的實時游戲時間)來進行訓練才能達到人類水平; 在自動駕駛等領域應用深度強化學習算法時, 不能冒險嘗試多種情況, 使得獲得樣本的成本代價高; 在一些機器人控制研究中, 需要消耗大量的成本用于機器人與環(huán)境進行交互來獲取數(shù)據(jù)等.因此, 減少智能體與環(huán)境的交互次數(shù)顯得尤為重要. 同時 如何對經驗進行回放將會影響深度強化學習算法最終所訓練出的策略的優(yōu)劣, 選擇不同的數(shù)據(jù)樣本對學習最優(yōu)策略產生的影響也將不同. 深度Q網絡算法通過隨機選擇記憶回放單元中的樣本進行訓練, 這種方式能夠打破樣本之間的相關性, 為深度神 經網絡提供獨立同分布的樣本, 但對每個樣本進行同等對待的隨機抽樣方式顯得并不高效.
國內外研究者對以上問題開展了研究. 一些研究者認為缺乏有效的探索會導致所生成的數(shù)據(jù)樣本不能為學習最優(yōu)策略提供良好的幫助, 需要通過改變探索策略生成出更利于學習的數(shù)據(jù)樣本, 這樣能在一定程度上減少智能體與環(huán)境交互的次數(shù). 通過引入隨機性改變探索策略, Plappert等人[8]提出在參數(shù)空間加入適當?shù)脑肼暎?Fortunato等人[9]提出在參數(shù)空間與動作空間加入噪聲相結合的方法. 不同于非盲目式的改變探索策略, Bellemare等人[10]將對狀態(tài)的虛擬計數(shù)作為衡量不確定性的指標; Pathak等人[11]提出基于好奇心驅動的探索方法記錄對狀態(tài)的訪問次數(shù), 用于賦予內在獎勵以鼓勵智能體探索; 楊珉等人[12]使用貝葉斯線性回歸方法提高智能體的探索效率; 李超等人[13]根據(jù)智能體對于狀態(tài)空間的離散化程度改寫值函數(shù)形式, 基于該值函數(shù)對環(huán)境進行合理探索. 當然, 若能夠有效構建環(huán)境模型, 智能體將無需再與環(huán)境進行真實的交互,直接從擬合的環(huán)境模型中獲取數(shù)據(jù)樣本. Tangkaratt等人[14]提出學習控制的概率推理方法使用高斯過程對狀態(tài)轉移模型進行建模, 使用最小二乘條件密度來學習狀態(tài)轉移模型; Ha等人[15]構建神經網絡生成模型, 學習低維空間下的狀態(tài)表示的世界模型. 這些方法都是通過從智能體與環(huán)境交互的角度出發(fā)來提升樣本效率,忽略了如何在本身已獲得的數(shù)據(jù)樣本上, 減少智能體與環(huán)境的交互次數(shù). 因而, 在從與環(huán)境的交互中獲取數(shù)據(jù)樣本后, 如何高效利用樣本也會影響到樣本效率. Schaul等人[16]提出優(yōu)先經驗回放算法通過TD-error值賦予狀態(tài)轉移樣本不同的重要性; 趙英男等人[17]提出先以序列累計回報作為樣本優(yōu)先級再以TD-error分布構造優(yōu)先級的二次采樣的方式對樣本進行選擇; 朱斐等人[18]通過獎賞、時間步和采樣次數(shù)共同決定樣本的優(yōu)先級,使智能體能更有效的選擇動作; Lin等人[19]提出的序列記憶深度Q網絡算法通過存儲經驗的獎賞值對采樣到的狀態(tài)轉移樣本進行區(qū)別對待等. 但以上的采樣方式都是單個看待經驗回放單元中的狀態(tài)轉移樣本, 由于強化學習中的獎勵具有稀疏性與延遲性, 對單個樣本進行采樣時很容易采樣到不具有獎勵的狀態(tài)轉移樣本, 導致采樣效率低. 同時, 強化學習作為一種通過與環(huán)境交互、從環(huán)境狀態(tài)到動作映射的學習方式, 在學習過程中會產生無數(shù)條序列軌跡, 這些序列軌跡由多個樣本所組成, 并且每個序列樣本都會帶有獎賞值. Lee等人[20]在2019年提出的序列向后更新(Episodic Backward Update, EBU)算法, 不同于以往對狀態(tài)轉移樣本進行單個采樣的方式, 通過采樣整個序列軌跡由后向前更新對深度Q網絡進行訓練, 更快地傳播獎賞值, 提高了采樣效率.
遺傳算法作為求解最優(yōu)問題的常用算法, 能通過模擬生物在自然環(huán)境中的進化過程搜索全局最優(yōu)解.其中交叉操作能采用多種交叉方法以生成新的個體[21].當面臨深度強化學習中需要解決減少智能體與環(huán)境的交互次數(shù)的問題時, 運用能產生新個體的交叉算子, 進而對數(shù)據(jù)樣本數(shù)量進行擴充. 因此, 本文嘗試利用遺傳算法中的交叉算子, 作用于序列軌跡以產生新的序列樣本, 從而擴充序列樣本數(shù)量, 減小智能體與環(huán)境的交互次數(shù), 使智能體能獲得更優(yōu)策略. 在Playing Atari 2600視頻游戲驗證本方法, 實驗結果顯示該方法能獲得更高的平均獎賞值并提高樣本的利用率.
在強化學習中, 智能體通過與環(huán)境進行交互以達到最大化累計獎賞的目標, 整個學習過程使用馬爾科夫決策過程進行建模: 在每個離散的時間步t, 智能體從與環(huán)境的交互過程中獲得狀態(tài)的表示st, 依據(jù)當前策略π, 得到應采取的動作at, 執(zhí)行該動作得到即時獎勵rt并轉移到下一狀態(tài)st+1. 這個過程一直循環(huán)下去, 直到到達標志著智能體的任務結束時的終止狀態(tài), 意味著完成一個序列軌跡. 狀態(tài)轉移樣本表示為(st,at,rt,st+1),智能體從初始狀態(tài)到終止狀態(tài)的序列軌跡由狀態(tài)轉移樣本構成, 表示為: (s1,a1,r1,s2),···,(st,at,rt,st+1).
智能體在一個序列中狀態(tài)st所獲累計獎賞值定義為:

其中, 折扣因子γ ∈(0,1]用于調節(jié)不同狀態(tài)對累計獎賞值的影響程度. 強化學習的目的是學習到使得Gt期望值最大的策略, 動作值函數(shù)定義為:

由于狀態(tài)轉移概率未知, 可通過Q學習更新值函數(shù):

經過式(3)的不斷迭代, 最終狀態(tài)值函數(shù)Q(s,a) 會收斂到最優(yōu)值, 達到最大化累計序列獎賞值的目標.
在強化學習面對高維狀態(tài)空間時, 深度Q網絡[1]算法通過引入深度學習中的神經網絡對Q學習算法中的Q值進行參數(shù)化, 經驗回放機制為神經網絡的訓練提供數(shù)據(jù)樣本. 經驗回放單元D存儲了智能體在每個時間步生成的狀態(tài)轉移樣本 (st,at,rt,st+1), 此時, 狀態(tài)動作值函數(shù)更新方式為:

訓練過程中, 智能體從經驗回放單元中隨機選擇狀態(tài)轉移樣本執(zhí)行更新, 利用隨機梯度下降方法最小化損失函數(shù):

其中,

式(6)中, θ′為目標值函數(shù)網絡的參數(shù), 在一定的周期內將當前網絡參數(shù)復制給目標值函數(shù)網絡, 以保證學習過程的穩(wěn)定性.
EBU算法的主要工作是解決深度強化學習中的樣本效率問題. 主要有以下兩方面:
開國洪武,多昌明博大之音;成化以后,多臺閣雍容之作,久而千篇一律,愈演愈弊。四庫館臣認為,七子派結束了臺閣體的統(tǒng)治局面,“不可謂之無功”,[2]528但同時“割剝字句”[2]552“食古不化”[2]528,發(fā)展到后期,贗古之勢愈烈,以至于蓋棺定論——“古文一脈,自明代膚濫於七子”。[2]585
(1) 深度Q網絡通過均勻隨機選擇的方式對狀態(tài)轉移樣本進行采樣, 但在許多問題中, 智能體與環(huán)境交互所獲的獎勵往往具有稀疏性與延遲性, 該方式會使得抽樣到具有獎勵的狀態(tài)轉移樣本的概率很低. (2) 在訓練早期階段, 所有Q值初始化為0, 在使用式(4)對Q值進行更新時, 若下一狀態(tài)的Q值也為0, 會導致更新所獲信息無效. 因此, 該算法通過采樣一整個序列樣本進行訓練, 能保證至少一個帶有獎勵的狀態(tài)轉移樣本被采樣到, 同時, 在對Q值進行更新的時候, 從序列末尾往序列開始的方向進行更新, 使得更新過程能充分利用有效信息[11].
具體訓練過程中, 采樣一整個序列樣本后, 通過序列由后向前更新的方式賦予式(6)中的y值. 由于直接使用此y值會造成深度Q網絡的不穩(wěn)定問題, 通過引入調節(jié)因子 β降低影響, 更新方式為:

其中,k為序列時間步,值為從目標值函數(shù)網絡中獲取的值. 當 β=0時, 相當于一步更新的深度Q網絡; 當β=1時 , 容易產生過估計問題. 該算法分為固定 β值和自適應 β值兩種, 本文僅針對樣本問題, 選取固定 β值的算法進行研究.
強化學習作為基于行為的學習方式, 不同于依據(jù)正例與反例來告知應采取何種行為的監(jiān)督與非監(jiān)督學習, 需要通過試錯的決策過程來生成無數(shù)條序列軌跡,以用來發(fā)現(xiàn)最優(yōu)策略. 為了減少該決策過程所需消耗的成本與代價, 可采用遺傳交叉算子對序列軌跡進行擴充. 強化學習試錯的學習方式會使得序列軌跡中存在相似狀態(tài), 選擇這些相似狀態(tài)作為交叉點, 能產生出目前未出現(xiàn)過的序列軌跡, 以此用來擴充序列軌跡數(shù)量, 提高對當前樣本的利用率.
本文將智能體與環(huán)境交互產生的序列樣本作為染色體, 序列樣本中的狀態(tài)作為基因. 每次從經驗回放單元中選擇兩條染色體作為父代, 選取相似基因作為交叉點, 采用遺傳算法中的單點交叉算子, 交換父代基因生成兩個子代. 具體而言, 可如圖1所示, 經驗回放單元可表示為為經驗回放中的第i個序列, 在D中選擇兩個序列ei、ej, 判定與作為交叉點, 依據(jù)單點交叉生成新的與并存入D′中.

圖1 序列樣本的交叉操作步驟
同時, 由于經驗回放單元中所存儲的序列是由智能體不斷與環(huán)境交互試錯生成, 因此每條序列的終態(tài)會存在大量相似性, 在選擇序列進行交叉操作時, 我們所選取的應是以不同狀態(tài)作為終態(tài)的序列軌跡, 以便利用遺傳算子的探索能力, 增加新生成的序列的多樣性. 如圖2所示, 在這個迷宮環(huán)境中, 綠色與藍色軌跡是智能體與環(huán)境交互生成, 且以不同的狀態(tài)作為結尾,黃色五角星為交叉狀態(tài)所在的位置, 紅色與橙色為交叉后生成的序列軌跡. 若選擇以相同狀態(tài)作為結尾的軌跡, 雖然也能產生新的序列, 但并沒有選擇以不同狀態(tài)作為結束的軌跡交叉而產生的序列軌跡的多樣性高.

圖2 迷宮環(huán)境中序列軌跡交叉圖
此外, 由式(1)計算每條序列的累計獎賞, 其可作為當前策略的評價指標, 累計獎賞值越大說明當前策略越優(yōu). 并且, 序列累計獎賞值越大的序列所包含的有效動作樣本越多[15], 意味著使用這些狀態(tài)轉移樣本會更有利于學習最優(yōu)策略. 因此, 對于利用交叉算子所生成的新序列, 我們僅保留序列累計獎賞變高的序列. 通過使用交叉算子生成的序列降低了數(shù)據(jù)樣本的生成成本, 增加了經驗回放單元中的序列數(shù)量.
當狀態(tài)空間巨大甚至無窮時, 一個狀態(tài)出現(xiàn)在兩個不同的序列軌跡中的概率非常低. 交叉點不必是兩個不同序列中的完全相同的狀態(tài), 而是兩個相似度高的狀態(tài). 是因為強化學習采用函數(shù)近似之后, 本質上就是對有限樣本上的經驗進行泛化, 把所訪問過的狀態(tài)的值推廣到新的近似狀態(tài)上.
深度Q網絡中采用直接將圖像作為輸入, 通過深度神經網絡提取出高層特征, 實現(xiàn)端到端的訓練方式.基于神經網絡提取的高層特征度量兩個狀態(tài)的相似度一方面降低了維度, 另一方面也抓住了所求解問題的狀態(tài)內在相似的內在本質. 這里, 用于特征提取的深度神經網絡結構如圖3所示.

圖3 對狀態(tài)抽取特征網絡圖
對序列軌跡中的狀態(tài)進行高層特征抽取后, 比較兩狀態(tài)特征之間的距離, 距離越大說明相似度越低, 距離越小則相似度越高. 依據(jù)式(8)計算特征之間的距離:

其中, ? (st)為通過深度神經網絡對狀態(tài)進行特征抽取后的結果.
強化學習作為利用試錯的方法解決序貫決策問題的學習方式, 每條序列軌跡都是智能體為了達到最終的學習目標所做出的嘗試, 經驗回放單元中存儲著智能體與環(huán)境實時交互所產生的序列軌跡. 與序列向后更新算法類似, 我們通過選擇整個序列的采樣技術, 使得深度Q網絡在訓練時采取從整個序列由后往前的狀態(tài)轉移樣本進行訓練.
通過使用對原始經驗回放單元中的序列軌跡進行交叉操作后, 將交叉生成的新的序列軌跡存儲在經驗回放單元D′之中, 得到了新的經驗回放單元D′.D′作為原始經驗回放單元D的補充, 在采樣過程中, 優(yōu)先采樣D中的序列, 再以一定的概率采樣新的經驗回放單元D′中的序列, 具體為隨機產生[0, 1]之間的隨機數(shù)σ,如果小于設置的參數(shù) μ, 則從經驗回放單元D中選擇序列樣本, 反之, 從D′中選擇.
本文提出的利用遺傳交叉算子(Genetic Crossover Operator, GCO)擴充序列樣本的方法是建立在序列向后更新(EBU)算法的基礎上, 為智能體在選擇序列樣本進行訓練時, 擴大序列樣本的選擇面, 增大序列樣本多樣性, 有利于獲得更優(yōu)質的策略. 具體算法如算法1.

k=Te′-1 10) for to 1 do:?Q[Ak+1,k]←βyk+1+(1-β)?Q[Ak+1,k]11) yk←Rk+γmaxa∈AQ[a,k]12) 13) end for L(θ)=(y-Q(s,a;θ))2 θ 14) 計算損失函數(shù) ,并由梯度下降更新參數(shù);t%F 15) if ==0:θ′=θ 16) 17) end for eiej 18) 從經驗回放中選擇以不同狀態(tài)作為終態(tài)結束的序列,ei=<si0,ai0,ri0,si1,ai1,ri1,si2,···,siTi> ej=<sj 0,aj0,rj0,sj1,aj1,rj1,sj2,···,sjTj> d(sim,sjn)19) 選取序列ei, ej中 最小的兩個狀態(tài)作為交叉點20) 應用交叉算子生成新的序列樣本ej′=<sj0,aj0,rj0,sj1,···,sim,aim,···,siTi> ei′=<si0,ai0,ri0,si1,···,sjn,ajn,···,sjTj> ei′、ej′ D′21) 將 存入22) end for
該算法中, 4)-6)步為強化學習使用ε-greedy策略作為行為策略產生樣本, 并將樣本保存到經驗回放單元中; 7)-16)步是采樣序列樣本并進行訓練的過程, 其中7)-12)步為EBU算法過程, 通過從后向前倒序回放序列中的狀態(tài)轉移樣本進行訓練, 第7)步為控制采樣到本文所提出方法所生成的序列樣本的比例; 18)~20)步是通過交叉操作產生新的序列的過程, 從經驗回放單元中隨機選擇到兩條序列, 比較兩條序列的終態(tài)的高級特征是否相似, 選取終態(tài)差異較大的序列進行交叉, 其中第19)步為依據(jù)狀態(tài)的高級特征判斷出兩條序列的交叉點, 依據(jù)交叉點最終完成交叉, 生成出新的序列樣本.
本文采用ALE作為實驗驗證平臺. ALE中包含了大量各種類別的Playing Atari 2600游戲接口, 為研究深度強化學習提供了豐富內容, 許多改進的深度強化學習算法都在該平臺驗證. 采用Playing Atari 2600游戲中的9個控制問題驗證本文方法的有效性, 控制問題分別為Breakout、Space_invaders、Ms_pacman、Atlantis、Phoenix、Video_pinball、Assault、Asteriods.
將本文方法與NATURE-DQN[1]、EBU[20]算法進行對比, 其中NATURE-DQN的訓練過程是從經驗回放單元中隨機選擇樣本, 本文則是在利用序列樣本訓練的EBU算法基礎上應用所提出的方法. 具體參數(shù)設置為: 由于ALE所提供的游戲畫面大小統(tǒng)一為210×210, 為了方便訓練, 將圖像灰度化處理并將大小裁剪為84×84, 并將4幀圖像作為一個狀態(tài)看待; 由于每個Atari游戲獎勵設置不同, 實驗過程中對每個游戲所獲的獎勵進行統(tǒng)一化處理, 即將獎勵歸一化在[-1,1]之間; 在訓練過程中, 經驗回放單元初始化是沒有任何樣本存在, 兩個經驗回放單元大小設置為1000 000,在智能體與環(huán)境交互超過50 000步時再從經驗回放單元中選擇樣本進行訓練, 每次選擇樣本的個數(shù)為32的倍數(shù), 序列樣本的大小不足32的倍數(shù)時, 在往前選擇狀態(tài)轉移樣本進行填充; 使用ε-greedy策略作為智能體的行為策略, ε大小隨著步數(shù)從1遞減到0.1; 采用RMSProp方式更新網絡參數(shù), 動量設置為0.95; 折扣因子 γ 設置為0.99; 學習率設置為0.000 25; 選擇經驗回放單元D′的參數(shù) μ設置為0.9; 網絡結構與N3ATUREDQN相同, 使用三層卷積網絡與兩層全連接網絡構成, 第1層卷積具有32個大小為8×8的濾波器, 步長為4, 第2層卷積具有64個大小為4×4的濾波器, 步長為2, 第3層卷積具有64個大小為3×3的濾波器, 步長為1, 選取的激活函數(shù)為ReLU, 第1層全連接具有512個神經元, 第2層全連接神經元個數(shù)為當前游戲所對應的動作空間大?。?目標值網絡與該網絡結構相同, 每隔10 000步將當前網絡參數(shù)賦給目標值網絡.在對序列樣本進行交叉操作時, 使用三層卷積層與一層全連接層對狀態(tài)進行高層特征抽取, 判斷兩個狀態(tài)是否相似. 本文采用的EBU算法為文獻[20]中的算法2, 超參數(shù) β為0.5.
在實驗中, 3種方法均采用相同的實驗參數(shù), 圖4為實驗結果曲線圖, 橫坐標為epoch, 每個epoch包含62 500步, 即智能體與環(huán)境交互62 500次, 縱坐標為各方法中智能體結束一個epoch后測試30次序列的平均累計獎賞值, 獎賞值越高說明智能體所學習到的策略越優(yōu).
通過實驗結果可以看出, 本文提出的方法GCOEBU與NATURE-DQN和EBU算法相比, 在多數(shù)控制問題上能使用更少的與環(huán)境交互的次數(shù)獲得更高的獎賞值. 具體而言, 在圖4(a)-圖4(d)的Assault、Space_invader、Altantis、Phoenix控制問題上GCO-EBU算法能在訓練初期就能觀察到明顯效果, 說明相對于兩個對比算法, 我們對序列樣本數(shù)量的擴充為訓練提供了幫助, 使得智能體獲得了更高的平均獎賞值. 在圖4(e)Asteroids問題中, GCO-EBU在訓練初期效果低于對比算法, 但在訓練后期所獲獎賞值遠高于兩種方法,由于該問題在訓練初期序列軌跡終態(tài)相似度高, 利用交叉所生成的軌跡并未給序列樣本好的擴充, 而在訓練后期終態(tài)相似度大, 能生成出多樣性大的序列軌跡. 在圖4(f)-圖4(g) Breakout、Video_pinball問題上, 所獲獎賞值的曲線比較相似, 穩(wěn)定性低于其他問題, 這和兩個問題的游戲規(guī)則有關. Breakout問題上GCO-EBU優(yōu)于NATURE-DQN算法, 但和EBU算法相比卻沒有更大的改進, 這由于Breakout問題在游戲初期所獲的獎賞值是非常稀疏的, 導致在運用本文方法時, 所生成的序列樣本的累計獎賞值發(fā)生改變的情況過少, 因此未能達到很好擴充序列樣本的目的. 由Video_pinball問題的實驗結果圖也可看出, GCO-EBU與EBU相比的效果也并不明顯, 但整體而言, 本文所提出的方法還是能幫助智能體在相同時間內獲得更高的獎賞值. 在圖4(h) Ms_pacman問題上, GCO-EBU與EBU的實驗效果不如NATURE-DQN, 但本文的改進是建立在EBU算法上, 在訓練后期本文方法在相同的與智能體交互次數(shù)中所取得的獎賞值高于EBU.

圖4 NATURE-DQN、EBU與GCO-EBU在Atari游戲中的平均獎賞值
表1是3種算法在8個控制問題上的平均獎賞值的對比, 整體而言, 說明依據(jù)遺傳算子來擴大序列樣本數(shù)量, 增加序列樣本多樣性的方法, 能使得在智能體與環(huán)境的相同交互次數(shù)中, 探索到更多的序列, 提高樣本的利用率, 從而獲得更高的獎賞值, 得到更優(yōu)質的策略.

表1 NATURE-DQN、EBU與GCO-EBU在Atari游戲中的平均獎賞值得分
本文所提出的利用遺傳算法中的交叉算子作用于序列樣本的方法, 能增大深度強化學習算法的序列樣本數(shù)量, 減少智能體與環(huán)境的交互次數(shù), 提升樣本效率,使得智能體獲得更高的平均獎賞值, 最終導出更優(yōu)質策略. 通過ALE平臺上的8個Playing Atari游戲驗證了該方法的有效性. 目前僅在基于值函數(shù)的強化學習算法上驗證本方法, 今后的研究工作是將該方法應用于基于策略的強化學習算法, 通過擴充序列樣本的方式, 增大策略空間, 更好地服務于策略梯度算法, 使得策略能跳出局部最優(yōu)的困境.