一種最大置信上界經(jīng)驗采樣的深度Q網(wǎng)絡方法

朱 斐 吳 文 劉 全,3 伏玉琛,4

1(蘇州大學計算機科學與技術學院 江蘇蘇州 215006)2(江蘇省計算機信息處理技術重點實驗室(蘇州大學) 江蘇蘇州 215006)3(符號計算與知識工程教育部重點實驗室(吉林大學) 長春 130012)4 (常熟理工學院計算機科學與工程學院 江蘇常熟 215500) (zhufei@suda.edu.cn)

強化學習(reinforcement learning, RL)能完成從環(huán)境狀態(tài)到動作映射的自我學習過程[1]，智能體(agent)與環(huán)境交互，選擇并執(zhí)行動作，環(huán)境對此作出反應，進入下一個狀態(tài)，利用價值函數(shù)評估狀態(tài)，不斷調(diào)整策略，反復迭代，直到結(jié)束.強化學習通過尋求agent在環(huán)境中獲得的最大累積獎賞值，獲得最優(yōu)策略.強化學習是目前機器學習領域的研究熱點之一，已經(jīng)在優(yōu)化調(diào)度、游戲博弈等領域中得到了良好的應用[2-4].深度學習(deep learning, DL)是機器學習的另一個研究熱點，其基本思想是自主地從原始輸入數(shù)據(jù)中組合底層特征，形成更抽象的高層來表示屬性類別或特征.深度學習的一些方法已經(jīng)成功地應用于圖像處理、自然語言處理等多個領域[5-7].

目前，越來越多的任務以復雜數(shù)據(jù)為輸入，以求解最優(yōu)策略為目標.這就需要將深度學習和其他機器學習方法結(jié)合起來.谷歌人工智能團隊DeepMind將深度學習和強化學習結(jié)合在一起，形成了深度強化學習(deep reinforcement learning, DRL)，開啟了從感知到?jīng)Q策的端對端(end to end)的研究.深度Q網(wǎng)絡(deep Q-network, DQN)[8-9]是深度強化學習的一個著名方法，其結(jié)合了深度卷積神經(jīng)網(wǎng)絡(convolutional neural network, CNN)和強化學習中的Q學習(Q-learning)算法[10]，成功地用于解決高維輸入環(huán)境中學習策略的任務.深度Q網(wǎng)絡方法可以將未經(jīng)處理的圖片直接作為輸入，在處理視覺控制問題中具有通用性；在一些Atari 2600游戲中，深度Q網(wǎng)絡達到了能與人類玩家媲美的水平.

可是，傳統(tǒng)的強化學習算法存在著一些問題，使之不能很好地與深度學習方法結(jié)合.例如，在傳統(tǒng)的強化學習算法中，每觀察到一次狀態(tài)轉(zhuǎn)移就要更新一次參數(shù).這會帶來2個問題：1)參數(shù)更新在時間上是相關的；2)出現(xiàn)次數(shù)少的轉(zhuǎn)移樣本容易被忽視.而大多數(shù)深度學習算法需要滿足2個重要條件：1)訓練樣本之間的關聯(lián)程度低；2)訓練樣本在訓練期間可以被重復使用多次.經(jīng)驗回放(experience replay)方法可以較好地解決這些問題[11-12].經(jīng)驗回放方法將歷史樣本放到經(jīng)驗池中，每次選擇小批量(mini-batch)樣本計算損失函數(shù)并更新網(wǎng)絡參數(shù).深度Q網(wǎng)絡也使用了經(jīng)驗回放方法，agent可以在線地存儲和使用其與環(huán)境交互得到的歷史樣本.在每個時刻，agent等概率地抽取小批量的轉(zhuǎn)移樣本進行訓練，以保證小概率出現(xiàn)的樣本也能夠有機會保存在經(jīng)驗池中.經(jīng)驗回放方法打破了學習樣本中存在的關聯(lián)性，不僅使訓練過程更易于收斂，而且提高了數(shù)據(jù)的利用率.但是，經(jīng)驗回放方法僅簡單地使用等概率的方式對經(jīng)驗池中的數(shù)據(jù)進行采樣.事實上，在經(jīng)驗池中的轉(zhuǎn)移樣本對參數(shù)訓練的作用是有所不同的：有些轉(zhuǎn)移樣本會產(chǎn)生較大的作用，有些則反之.而經(jīng)驗回放方法的采樣方式很難區(qū)分不同樣本的重要性.Schaul等人[13]提出一種基于時間差分誤差(temporal difference error, TD-error)的優(yōu)先經(jīng)驗回放(prioritized experience replay, PER)的采樣方式，以TD-error評估樣本，認為TD-error大的樣本重要性程度高，應賦予較高的被選概率.該方法能更好地利用經(jīng)驗池中的重要樣本，但是由于經(jīng)驗池容量通常是固定的，且訓練時采用的批量樣本數(shù)量較少，因此會存在一些樣本未被使用就被舍棄的情況.這一不足使得樣本多樣性的要求無法得到滿足，結(jié)果使得學習效率低下.

針對此問題，本文提出了一種新型的采樣機制，有效地避免了上述問題.一方面，在采樣過程中利用最大置信上界(upper confidence bound, UCB)的基本思想[14]，提出了基于最大置信上界采樣算法(upper confidence bound sample, UCBS)，給經(jīng)驗池中未被使用過的樣本附加一個鼓勵項，提高其被選取的概率，從而保證樣本的多樣性；另一方面，增加能使agent學習到更多信息的樣本的被選概率.由于本文方法使用獎賞值來衡量agent從樣本中學習信息的優(yōu)劣，因此，本文方法會傾向于選擇可能獲得更高獎賞樣本，進而使agent能夠更快地學習到最優(yōu)策略.

1 相關工作

1.1 強化學習

在強化學習中，從時間步t開始到時間步T情節(jié)結(jié)束時所獲得的累積折扣獎賞定義為

(1)

其中，0≤γ≤1是折扣因子，表示未來獎賞對累積獎賞的影響力度.

在強化學習模型下，agent在時間步t的狀態(tài)xt下，執(zhí)行根據(jù)策略h選擇動作u，環(huán)境對智能體所執(zhí)行的動作給出反饋，給agent下一時間步的狀態(tài)xt+1和獎賞rt+1.強化學習模型框架示意圖如圖1所示:

Fig. 1 The diagram of reinforcement learning framework圖1 強化學習模型框架示意圖

在強化學習中，可以使用狀態(tài)動作值函數(shù)來評估策略.狀態(tài)動作值函數(shù)Qh(x,u)是指依據(jù)策略h，在當前狀態(tài)xt下執(zhí)行動作ut，直到情節(jié)結(jié)束所獲得的累積獎賞之和，Qh(x,u)可以表示為

Qh(x,u)=E[Rt|xt=x,ut=u,h],

(2)

其中，E表示期望.

狀態(tài)動作值函數(shù)Qh(x,u)遵循貝爾曼方程.根據(jù)貝爾曼方程獲得的時間步t+1的狀態(tài)動作值Qt+1(x,u)為

(3)

其中，Qt(x,u)是時間步t的狀態(tài)動作值.利用貝爾曼方程不斷迭代，狀態(tài)動作值最終收斂，從而得到最優(yōu)策略.

根據(jù)狀態(tài)遷移函數(shù)P是否已知，強化學習可以分為基于模型的動態(tài)規(guī)劃算法和基于無模型的強化學習算法；根據(jù)生成行為的策略和更新值函數(shù)是否相同，基于無模型的強化學習算法又分為同策略算法(on-policy)和異策略(off-policy)算法.深度Q網(wǎng)絡方法所用到的Q-learning算法就是一種典型的異策略算法[15].Q-learning算法的更新公式為

(4)

Q(xt,ut)=Q(xt,ut)+αδ,

(5)

其中，γ為折扣因子，δ為TD-error.Q-learning算法所學到的動作值函數(shù)是直接逼近最優(yōu)動作值函數(shù)而不依賴于其策略，簡化了算法的分析.

1.2 深度學習

深度學習的基礎是人工神經(jīng)網(wǎng)絡(artificial neural network, ANN)，由淺層學習發(fā)展而來.反向傳播(back propagation, BP)算法[16]是深度學習的基本算法.利用反向傳播算法可以讓一個人工神經(jīng)網(wǎng)絡從大量訓練樣本中學習到數(shù)據(jù)的分布式特征，從而對未知樣本進行預測.由多個隱藏層構(gòu)成的多層感知器(multi-layer perceptron, MLP)比淺層網(wǎng)絡特征表達的能力更強.

前饋網(wǎng)絡是一種常見的神經(jīng)網(wǎng)絡連接方式.前饋深度神經(jīng)網(wǎng)絡在每一層使用函數(shù)將一批輸入的集合傳輸?shù)捷敵鰧樱粩嗟卣{(diào)整網(wǎng)絡參數(shù)，優(yōu)化網(wǎng)絡.卷積神經(jīng)網(wǎng)絡就是一種經(jīng)典的前饋深度神經(jīng)網(wǎng)絡，通常包括卷積層、池化層和全連接層.卷積神經(jīng)網(wǎng)絡可以以圖片等高維數(shù)據(jù)為直接輸入，采用局部連接和共享權(quán)值的方式，減少了權(quán)值的數(shù)量，使得網(wǎng)絡易于優(yōu)化，也降低了過擬合的風險.Krizhevsky等人[17]提出的深度卷積神經(jīng)網(wǎng)絡使用非線性激活函數(shù)整流線性單元(rectified linear unit, ReLU)，加快了收斂速度并抑制了梯度消失問題.由于其采用純粹的監(jiān)督學習訓練方式，代替了“預訓練+微調(diào)”的方式，引起了基于卷積神經(jīng)網(wǎng)絡的深度學習研究熱潮，如Simonyan等人[18]提出的模型進一步提高了圖像的識別能力；He等人[19]提出了有152層深度的深度殘差網(wǎng)絡(deep residual network, DRN).

循環(huán)神經(jīng)網(wǎng)絡(recurrent neural network, RNN)隱藏層的結(jié)點有存儲歷史信息的功能，常被用于處理具有時序特性的問題[20].循環(huán)神經(jīng)網(wǎng)絡可以看成是一個共享同一參數(shù)的多層網(wǎng)絡，然后再根據(jù)時間序列展開計算.雖然循環(huán)神經(jīng)網(wǎng)絡可以“記憶”歷史信息，但是它難以保存相隔時間較長的信息.但是，循環(huán)神經(jīng)網(wǎng)絡存在梯度消失的不足.針對這些問題，研究人員提出了長短期記憶網(wǎng)絡(long short-term memory, LSTM)和門限循環(huán)單元[21](gated recurrent unit, GRU)，彌補了循環(huán)神經(jīng)網(wǎng)絡存在的缺陷.此外，還有一些研究人員運用其他的機制來改進循環(huán)神經(jīng)網(wǎng)絡，如將結(jié)合注意力機制與循環(huán)神經(jīng)網(wǎng)絡，使得網(wǎng)絡能記住歷史信息中的關鍵部分[22].

1.3 深度Q網(wǎng)絡

Mnih等人[9]在傳統(tǒng)強化學習中的Q學習算法和深度卷積神經(jīng)網(wǎng)絡的基礎上提出了深度Q網(wǎng)絡，用于處理基于視覺的控制任務，緩解了用非線性函數(shù)逼近器表示值函數(shù)時算法的不穩(wěn)定性.深度Q網(wǎng)絡結(jié)構(gòu)示意圖如圖2所示:

Fig. 2 The diagram of the architecture of deep Q network圖2 深度Q網(wǎng)絡結(jié)構(gòu)示意圖

深度Q網(wǎng)絡的輸入是已經(jīng)被預處理的4幅84×84圖片.第1層卷積層有32個8×8卷積核對圖片進行卷積操作，卷積步幅為4；第2層卷積層有64個4×4的卷積核，卷積步幅為2；最后一層卷積層有64個3×3的卷積核，卷積步幅為1.每一層卷積層后都有1個非線性激活函數(shù)ReLU，在3層卷積層后跟著2個全連接層，第1個全連接層擁有512個結(jié)點，第2個全連接層的結(jié)點數(shù)與動作數(shù)量一致.

深度Q網(wǎng)絡方法主要有2點改進:1)使用了經(jīng)驗回放方法，在每一個時間步t，agent將與環(huán)境交互產(chǎn)生的轉(zhuǎn)移樣本et=(xt,ut,rt,xt+1)存儲到經(jīng)驗池Dt={e1,e2,…,et}中.采用等概率方式在經(jīng)驗池中抽取出相同數(shù)量的轉(zhuǎn)移樣本.經(jīng)驗回放方法可以打破樣本之間的關聯(lián)性，使深度Q網(wǎng)絡能處理很多任務，如控制Atari 2600游戲.2)使用了2個網(wǎng)絡來分別表示當前值函數(shù)和目標值函數(shù)，其中，采用實時方式更新當前值網(wǎng)絡參數(shù)θ，而目標值網(wǎng)絡參數(shù)θ-則在L步后通過復制當前值網(wǎng)絡參數(shù)θ得到.在每一時間步t，通過不斷減小目標值函數(shù)和當前值函數(shù)之間的均方誤差來更新參數(shù)θ，損失函數(shù)為

(6)

進一步得到

(7)

式(7)并不需要計算所有的梯度，只要計算合適批量來優(yōu)化損失函數(shù).因此，可以選用隨機梯度下降的方法來計算.網(wǎng)絡參數(shù)根據(jù)損失函數(shù)梯度下降的方向調(diào)整

(8)

近年來，出現(xiàn)了以深度Q網(wǎng)絡為基礎的各種改進模型.針對強化學習算法Q-learning會出現(xiàn)樂觀估計動作值的問題，Van Hasselt等人[23]在雙Q學習算法(double Q-learning)[24]的基礎上提出了深度雙Q網(wǎng)絡(double deep Q-network, DDQN).該方法在計算目標網(wǎng)絡的Q值時使用了2套不同的參數(shù)，有效地避免了深度Q網(wǎng)絡過高估計動作值的問題.深度Q網(wǎng)絡通過采用重復4次相同動作減少動作選擇以有利于下一個狀態(tài).Lakshminarayanan等人[25]根據(jù)當前狀態(tài)重要性有所不同的特點，提出了動態(tài)跳幀的方法重復動作，有效地提高了模型的訓練效果.Wang等人[26]將深度Q網(wǎng)絡中卷積神經(jīng)網(wǎng)絡所提取的特征分為優(yōu)勢函數(shù)(advantage function)和與動作無關的狀態(tài)值函數(shù)，使用這2個函數(shù)來生成狀態(tài)值函數(shù)，提出了競爭深度Q網(wǎng)絡(dueling deep Q-network， DuDQN)，在不改變底層強化學習算法的情況下進一步提高了深度Q網(wǎng)絡的效果.

上述這些改進后的模型都是基于卷積神經(jīng)網(wǎng)絡的.從卷積神經(jīng)網(wǎng)絡的結(jié)構(gòu)來看，每層神經(jīng)元的信號只能向上一層傳播，因此，如果不同時刻的子任務之間存在依賴關系，這些模型的效果表現(xiàn)就一般.Narasimhan等人[27]提出了深度循環(huán)Q網(wǎng)絡(deep recurrent Q-network, DRQN)，首次引入了長短期記憶網(wǎng)絡[28]，在處理一些帶有時序性的文本任務中表現(xiàn)良好.在此基礎上，Hausknecht等人[29]提出了深度循環(huán)Q學習算法(deep recurrent Q-learning, DRQ)，在處理部分可觀測Markov決策過程(partially observable Markov decision process, POMDP)問題時取得了良好的效果.

2 基于最大置信上界采樣的深度Q網(wǎng)絡模型

2.1 基于最大置信上界采樣

在深度Q網(wǎng)絡中，等概率采樣不能充分利用有價值的轉(zhuǎn)移樣本；而且在有限的經(jīng)驗池中，等概率采樣存在重復采用低價值樣本、遺漏重要樣本等問題，導致學習效率低下.

在強化學習中，研究人員通常認為那些取得較大獎賞的動作可以加速模型的學習，因此，本文增加了選取具有較大獎賞的動作的概率.然而，隨著選擇較大獎賞動作的概率逐漸提高，選取其他動作的概率就會不斷降低，這就有可能使算法陷入局部最優(yōu)；而且這樣做也無法保證樣本多樣性的要求.因此，亟需一種既可以充分利用大獎賞動作又能保證樣本多樣性的方法.

在強化學習中，由于動作值函數(shù)的估計值是未知的，因此需要進行適當?shù)奶剿?貪心(greedy)方法選擇當前狀態(tài)下獲得立即獎賞最多的動作.但是，貪心方法有可能會遺漏其他使得累積獎賞更大的動作.為了增加探索到未被發(fā)現(xiàn)的優(yōu)秀動作的概率，常常使用ε-貪心方法選擇動作.然而，ε-貪心方法未區(qū)分非貪心動作實際存在的重要性差異.Auer等人[14]提出了使用最大置信上界(UCB)思想解決多臂賭博機(multi-armed bandit)問題，在當前時刻選擇最優(yōu)動作和選擇未來最優(yōu)動作之間進行了優(yōu)化，有效地平衡了探索和利用的關系.受到該方法的啟發(fā)，針對經(jīng)驗重放方法所存在的問題，本文提出一種基于最大置信上界的優(yōu)先級采樣方法，通過提高獎賞較大的動作的被選概率，有效地增加了經(jīng)驗池中重要樣本被采樣的可能性；另一方面，通過提高未被選取樣本的被選概率，保證了數(shù)據(jù)采樣的多樣性.本文將上述采樣方法應用于深度Q網(wǎng)絡，構(gòu)建了一個基于最大置信上界采樣的深度Q網(wǎng)絡(upper confidence bound sampling deep Q-network, UCBS-DQN)，總體結(jié)構(gòu)如圖3所示.

Fig. 3 The diagram of the architecture of UCBS-DQN圖3 UCBS-DQN結(jié)構(gòu)示意圖

在UCBS-DQN方法中，當前值網(wǎng)絡的輸入是經(jīng)過灰度處理后的圖片,這些圖片經(jīng)過網(wǎng)絡的訓練后得到當前動作值函數(shù)，與目標值網(wǎng)絡中的最大動作值函數(shù)形成誤差函數(shù)，使用基于均方根的傳播方法(root mean square propagation, RMSProp)最小化誤差函數(shù)；從經(jīng)驗回放單元提取經(jīng)過處理后選擇的樣本，選擇動作；每間隔L步(通常L取較大值)將當前值網(wǎng)絡參數(shù)復制給目標值網(wǎng)絡參數(shù).圖3中的虛線部分是本文的改進之處.在每一次執(zhí)行動作后，計算樣本的優(yōu)先級并進行歸一化操作，給經(jīng)驗池中的樣本賦予優(yōu)先級，更新網(wǎng)絡所用樣本通過樣本特征抽取獲得.從圖3中可以看到，本文方法在從經(jīng)驗回放單元中抽取樣本時利用最大置信上界的思想，用新的方法給樣本賦予優(yōu)先級.對于每個樣本的選取概率更新公式為

(9)

(10)

式(9)中加入了樣本選取的不確定估計機制.當?shù)趇個樣本被選擇后，由于Ni出現(xiàn)在平方根項的分母上，因此，該樣本被選概率會隨著時間步而逐漸降低.另一方面，隨著訓練的進行，時間步t逐漸增加，其他樣本在之后時間步被選的概率也會提高.當?shù)趇個樣本中的獎賞為正獎賞時，即可認為該樣本為優(yōu)秀樣本.為了限制獎賞的影響力，且統(tǒng)一不同實驗中獎賞的度量尺度，本文將正獎賞設置為1，負獎賞設置為-1.這樣既提高了獎賞較大的樣本被選概率，又降低了獎賞較低樣本的出現(xiàn)概率.隨著步數(shù)的增加，時間步t的影響會越來越大.為了減緩時間步t的增長速度，更新式(9)中使用了對數(shù)函數(shù)，使時間步的影響力小于樣本獲得獎賞大小的影響力.本文方法還考慮了信息量較大的樣本以及未被選擇的樣本，保證了樣本的多樣性.

2.2 算法描述及分析

本文將基于最大置信上界的優(yōu)先級采樣應用于深度Q網(wǎng)絡，得到了基于最大置信上界采樣的深度Q學習方法，具體描述如算法1所示.

算法1. 基于最大置信上界采樣的深度Q學習方法(UCBS-DQN).

① 初始化：經(jīng)驗回放單元D中的容量N;抽樣樣本數(shù)量minibatch的大小為32；每個樣本初始概率pi=1N,i∈[1,N]；當前值網(wǎng)絡的參數(shù)為θ，目標值網(wǎng)絡的參數(shù)為θ-(θ=θ-)；選擇隨機動作概率為ε；i=0;時間步t=0.

② Repeat(對每一個情節(jié))：

初始化并預處理狀態(tài)序列φ1=φ(x1)；

③ Repeat(對于情節(jié)中的每個時間步)：

④ 用ε-貪心選擇隨機動作ui；

⑤ 執(zhí)行動作ui，得到一幅圖像oi+1和立即獎賞ri；

⑥ 設置xi+1=xi,ui,oi+1，并處理得到

φi+1=φ(xi+1)；

⑦ 將(φi,ui,ri,vi,φi+1)作為一個樣本存儲到D中；

⑧ Repeat(對每一個批次樣本)：

⑨ 隨機在[0,1]之間取值random()；

在算法1中，步⑨～⑩是基于最大置信上界采樣算法采樣的過程，通過優(yōu)先級計算，每個樣本的被選概率不同；步～是產(chǎn)生優(yōu)先級的過程，根據(jù)樣本的獎賞和被選次數(shù)設計優(yōu)先級；步計算損失函數(shù)的梯度.

2.3 復雜度分析

UCBS-DQN方法大致可以分為優(yōu)先級標簽提取、計算優(yōu)先級和模型求解3個階段，下面從這3個角度分析模型復雜度.

1) 優(yōu)先級標簽提取階段.在UCBS-DQN方法中，每一個情節(jié)中包含了若干時間步，在每個時間步中提取樣本優(yōu)先級標簽以更新網(wǎng)絡參數(shù).當經(jīng)驗池容量滿后不再變化，其大小為常數(shù).每個訓練批次提取樣本的數(shù)量為32，因此，提取樣本優(yōu)先級時模型空間復雜度為O(1)，時間復雜度都為O(n).此外，在UCBS-DQN方法中，需要從經(jīng)驗池中抽取樣本送入網(wǎng)絡進行訓練以更新參數(shù)，模型參數(shù)每隔L步更新一次且L取值較大(實驗中L=10 000)，其余時刻大部分用于執(zhí)行優(yōu)先級更新操作，因此網(wǎng)絡參數(shù)更新時間復雜度和空間復雜度都為O(1).

2) 計算優(yōu)先級階段.優(yōu)先級的計算是在游戲每個執(zhí)行動作之后，對經(jīng)驗池中樣本優(yōu)先級進行計算，在計算其優(yōu)先級時需要遍歷每一個樣本，再由樣本被選概率更新方式得到計算優(yōu)先級的時間復雜度為O(n).由于樣本上限為常數(shù)，因此其空間復雜度為O(1).

3) 模型求解階段.整個模型需要重復執(zhí)行M輪，因此，在模型求解階段算法時間復雜度為O(n).

由于優(yōu)先級標簽提取、計算優(yōu)先級和模型求解階段是層層嵌套的，因此，整體而言，UCBS-DQN方法的算法時間復雜度為O(n3).

經(jīng)過復雜度分析可知，本文提出的UCBS-DQN方法能夠通過消耗較小的空間和時間代價得到經(jīng)驗池樣本優(yōu)先級，并通過其被選概率選擇樣本.

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

在本節(jié)中，首先介紹實驗所用平臺和實驗中所用參數(shù)；隨后，對深度Q網(wǎng)絡(DQN)、深度循環(huán)Q網(wǎng)絡(DRQN)、基于時間差分誤差的優(yōu)先經(jīng)驗回放(PER)以及本文提出的基于最大置信上界采樣的深度Q學習方法(UCBS-DQN)在部分Atari 2600游戲中的表現(xiàn)進行評估；最后，結(jié)合實驗結(jié)果和游戲特性分析UCBS-DQN方法的優(yōu)勢.

3.1 實驗平臺及實驗介紹

OpenAI是一家非營利性的人工智能研究公司，創(chuàng)立初衷是預防人工智能的災難性影響，同時為推動人工智能的發(fā)展發(fā)揮積極作用.OpenAI公司于2016年提出的Gym是一種用于開發(fā)和比較強化學習和深度強化學習算法的工具包，提供了各種Atari 2600游戲接口，包括策略類、動作類、桌游類、體育競技類等59種經(jīng)典游戲.Gym為人工智能研究人員提供了豐富且具有挑戰(zhàn)性的深度強化學習平臺.本文的實驗環(huán)境基于Gym的Atari 2600游戲環(huán)境.

本文的實驗比較了4種方法在4個Atari游戲中的效果，包括Seaquest游戲、Breakout游戲、Space Invader游戲和Assault游戲.1)Seaquest游戲是潛水艇對戰(zhàn)游戲,其獎賞來自于潛水艇擊殺潛艇類別和數(shù)量，若被其他潛艇子彈擊中，則游戲結(jié)束.在游戲中，潛水艇每隔一定時間都需要在海底獲得一個一次性的氧氣瓶，然后浮出水面吸收氧氣,當氧氣瓶中的氧氣耗盡時，游戲就結(jié)束.2)Breakout游戲是一種小球擊打磚塊的游戲,小球從下方開始擊打上方的磚塊，每成功擊打一次就獲得一個獎賞.擊打的位置不同，所獲得的獎賞也不同.通過控制屏幕底端的板塊來反彈小球，防止小球掉落,若小球掉落則宣告游戲結(jié)束.3)Space Invader游戲是操控一架只能在一條水平線上的戰(zhàn)斗機，消滅在畫面中的敵方飛機.若我方戰(zhàn)機被對方子彈打中，游戲就結(jié)束.4)在Assault游戲中，玩家操控飛機消滅源源不斷產(chǎn)生的敵機，隨著游戲的過程，敵機速度會越來越快，消滅飛機所獲獎賞也會相應提高，若我方飛機被子彈擊中，游戲就結(jié)束.

本文實驗使用Intel i7-7820X處理器，使用GTX 1080Ti圖形處理器對深度學習運算進行輔助加速計算.實驗中，使用強化學習模型對Atari 2600游戲進行建模，其中，距離時間步t最近的N幅視頻幀構(gòu)成了狀態(tài)xt=(st-N+1,st-N+2,…,st)∈X，agent從在動作集U中選擇一個動作ut={1,2,…,K}∈U，執(zhí)行后產(chǎn)生新的游戲畫面代表agent轉(zhuǎn)移到下一狀態(tài)xt+1，2幅畫面的得分差值即為獎賞rt.

3.2 參數(shù)設置

本文對比了DQN，DRQN，PER以及UCBS-DQN方法的性能.實驗中，4種方法均采用RMSProp方法更新參數(shù)，其動量參數(shù)設置為0.95.

在Gym包中，各個游戲所獲得的獎賞差異較大，這會影響到最終網(wǎng)絡輸出的Q值，進一步影響動作選擇.為了縮小Q值的范圍，實驗中將所有大于1的獎賞設置為1，所有小于-1的獎賞設為-1，處于[-1,1]之間的獎賞值不變.此外，當前網(wǎng)絡和目標網(wǎng)絡之間的誤差項也被控制在[-1,1]之間，這可以防止結(jié)果陷入局部最優(yōu)，提高系統(tǒng)穩(wěn)定性.

Gym提供的Atari 2600游戲圖像像素是210×160.為了方便圖像處理，將圖像像素預處理為84×84的灰度圖像，并以處理過后的4幅圖像作為網(wǎng)絡輸入.訓練時，如果一個動作僅執(zhí)行一次，則會使得策略在空間和時間上變化太快，從而導致網(wǎng)絡需要經(jīng)常選擇動作，而選擇動作需要根據(jù)深度網(wǎng)絡進行層層計算得到的結(jié)果來判斷，造成深度網(wǎng)絡計算所用時間遠遠大于網(wǎng)絡前向傳播的時間.因此，實驗重復采取4次當前動作，這樣既減少了計算量，又保持了動作序列的多樣性.在實現(xiàn)經(jīng)驗回放方法時，由于初始狀態(tài)的經(jīng)驗池缺乏樣本數(shù)據(jù)，故而在實驗的前50 000步對經(jīng)驗池進行填充.經(jīng)驗池的容量設置為最大存放100萬個樣本，每次從經(jīng)驗池中取出32個樣本放入網(wǎng)絡進行訓練.Q值更新的折扣率γ設置為0.99.由于在訓練后期，訓練步幅過大可能會導致算法不收斂，而此時使用ε-貪心方法探索也足以滿足需求，因此，實驗中每隔100 000步以每次下降4%的步長進行衰減：網(wǎng)絡更新參數(shù)α從0.005下降到0.000 25，ε-貪心策略的參數(shù)ε從1下降到0.1.

3.3 實驗結(jié)果分析

在實驗中，每種方法使用相同參數(shù)：采用500個訓練階段，每個訓練階段設置為10 000步.圖4顯示了各方法在4種不同游戲中所獲得的平均獎賞.從圖4中可以看出，UCBS-DQN方法的平均每情節(jié)獎賞高于其他3種方法.

從圖4(a)中Seaquest游戲的平均獎賞圖可以發(fā)現(xiàn)，面對這種復雜的環(huán)境，DQN和DRQN方法表現(xiàn)都不令人滿意;PER方法雖然通過使用TD-error優(yōu)先級提高了每情節(jié)獎賞，但需要經(jīng)歷240多個訓練階段之后才出現(xiàn)效果的提升;而UCBS-DQN方法在第100輪訓練階段的平均每情節(jié)獎賞就已經(jīng)是DQN方法的5倍、DRQN方法的4倍，效果得到了大幅提升.經(jīng)過分析可知，Seaquest游戲的上浮吸收氧氣情節(jié)需要一直執(zhí)行上浮動作，這些動作在當前階段得到的反饋較差，但卻是必須執(zhí)行的.因此，DQN和DRQN方法中，這些動作對平均獎賞值的提高作用有限.使用了TD-error優(yōu)先級的PER方法雖然比DQN和DRQN方法表現(xiàn)好，但該方法并不具備很好的探索其他訓練樣本的機制，導致了其效果需要在較多的訓練階段之后才能得到顯著的提升.而UCBS-DQN方法增加了那些不常被選擇的樣本的被選概率，加之引入跳幀機制，使得潛水艇能夠以大概率執(zhí)行上浮動作，保持更長的游戲時間，提高了平均每情節(jié)獎賞.

Fig. 4 The average reward of different approaches in different Atari games圖4 各方法在Atari游戲中的平均獎賞

從圖4(b)中Breakout游戲的平均獎賞圖可以發(fā)現(xiàn)，UCBS-DQN方法能更快地取得更好的效果，并且在訓練過程中的每情節(jié)獎賞一直高于其他3種方法.但是，UCBS-DQN方法所獲得的提升效果不如Seaquest游戲明顯.這是因為Breakout游戲環(huán)境較為簡單，其動作除去開局階段的開球，在游戲過程中只有左右移動和靜止，且其狀態(tài)數(shù)量也少于其他游戲，這使得經(jīng)驗池中樣本相似性增大.因此，UCBS-DQN方法使用未被選擇的樣本來訓練，其提升效果就受到限制.而另一方面，由于Breakout游戲狀態(tài)相似性較高，UCBS-DQN方法可以很快地找到較好的動作值函數(shù)，故而在訓練到第100輪左右時就有很好的成績，明顯優(yōu)于其他3種方法.

從圖4(c)中Space Invader游戲的平均獎賞圖可發(fā)現(xiàn)，UCBS-DQN方法較其他3種方法有顯著的提高.在經(jīng)歷了500個訓練階段后，UCBS-DQN方法所獲得的獎賞是DQN方法的3倍多、是DRQN方法的近4倍、是PER方法的2倍.而且可以看出，UCBS-DQN方法每階段所獲得的獎賞仍然處于一個上升的趨勢.這是因為Space Invader游戲中敵機數(shù)量已知且位置變化范圍不大，UCBS-DQN方法會以較高的概率選擇那些取得高獎賞值的樣本，因此，實驗中UCBS-DQN方法所獲得獎賞呈大幅上升趨勢.

從圖4(d)中Assault游戲的平均獎賞圖可以發(fā)現(xiàn)，UCBS-DQN方法表現(xiàn)依然突出，且在500輪訓練階段后依然保持著上升趨勢;雖然PER方法比DQN方法和DRQN方法好，但是，PER方法探索性能較差，很難發(fā)現(xiàn)未遇到的優(yōu)秀樣本，導致在經(jīng)歷了一段時間的提升后，PER方法中每情節(jié)所獲得的獎賞難以持續(xù)提高.而由于UCBS-DQN方法具有較強的探索能力，可以發(fā)現(xiàn)更多的優(yōu)秀動作，因此能保持良好的上升態(tài)勢.

通過上述4個實驗，可以得出UCBS-DQN方法取得效果顯著時的條件：1)在環(huán)境中存在著較難被探索到的且獎賞值較高的樣本，如Seaquest游戲環(huán)境中上浮獲取氧氣；2)環(huán)境中存在重復執(zhí)行某個動作依然能獲得較高獎賞的現(xiàn)象，如Space Invader游戲中擊打飛機的情況.值得注意的是，UCBS-DQN方法并非僅僅簡單地改變動作的被選概率來改善效果，而是考慮了更多的信息，通過對經(jīng)驗池中的元組進行選擇，以元組中的狀態(tài)(即經(jīng)過處理的圖像)為輸入進行網(wǎng)絡訓練，采用ε-貪心方法選擇動作，因此可以有效地降低陷入局部最優(yōu)的可能.

損失函數(shù)的損失值是衡量算法收斂速度的一個重要標準.本文使用式(6)計算了4種方法在不同游戲中損失函數(shù)的損失值，如圖5所示.

從圖5中可以看出，每一種方法在剛開始訓練時其損失值有一個上升的過程.而UCBS-DQN方法在短暫的上升之后，其損失值一直保持在一個非常低的狀態(tài).在Space Invader游戲和Assault游戲中，UCBS-DQN方法的損失值甚至持續(xù)降低，這是因為UCBS-DQN方法有較強的探索性，使得其能快速找到最優(yōu)策略.

好的方法不僅應該在訓練階段表現(xiàn)出上佳性能，而且能使用已經(jīng)訓練好的模型進行實際控制操作.為此，本文進行了實戰(zhàn)游戲測試.在測試過程中，agent使用訓練好的模型，完全控制實戰(zhàn)游戲，完成50 000步的測試，其中選擇動作依然采用ε-貪心策略.在之前的測試階段，通過選用ε-貪心策略來減少過擬合的可能，而此時模型已經(jīng)訓練完畢，因此，ε取較小數(shù)值，設為0.01.每個模型都進行20次獨立的測試，每次測試后獲得游戲每一個情節(jié)的平均獎賞、最大值、平均獎賞的方差和每50 000步可以運行的游戲輪數(shù)，如表1所示.

Fig. 5 The loss of different approaches in different games圖5 各方法損失值比較圖

GameApproachAverage rewardMaximal rewardVarianceRounds of gameBreakoutSeaquestSpace InvaderAssaultDQN2.8710.0 0.017900.2UCBS-DQN3.3520.00.014850.4DRQN2.8710.00.052513.5PER3.0412.00.021892.6DQN34.92200.03.18796.2UCBS-DQN150.45600.085.90472.8DRQN41.33120.07.16772.8PER129.86440.074.30487.2DQN116.54815.096.33547.5UCBS-DQN317.831195.0705.57350.8DRQN72.91500.02.19957.0PER162.66940.0169.30475.2DQN197.921302.0161.50327.6UCBS-DQN661.522142.03301.52178.4DRQN110.01525.068.95393.8PER411.831058.01065.28184.0

Notes: The bold values represent the maximum values in the average reward and maximal reward.

從表1中可以看出，UCBS-DQN方法在每情節(jié)所獲得的平均獎賞上都有不同程度的提高.在最大值這項指標上，UCBS-DQN方法的表現(xiàn)依然優(yōu)于其他方法.此外，UCBS-DQN方法在固定50 000步所獲得平均游戲輪數(shù)最少，說明其在平均每輪游戲中存活步數(shù)最長，訓練較為成功.

4 結(jié)束語

深度Q網(wǎng)絡及其相關改進方法在Atari游戲中有著很好的表現(xiàn)，證明可以較好地解決一些視覺感知類問題.然而，對于戰(zhàn)略性任務這些模型效果提高有限，主要原因在于環(huán)境中存在著需要長時間步才能表現(xiàn)出優(yōu)秀的狀態(tài).本文提出了一種基于最大置信上界采樣的UCBS-DQN方法，該方法通過對經(jīng)驗池進行優(yōu)先級采樣，可以有效地探索未知狀態(tài)，提高選擇優(yōu)秀狀態(tài)概率，在很大程度上能夠避免出現(xiàn)探索不到延遲獎賞的問題.本文通過4個Atari 2006實驗驗證了UCBS-DQN方法的有效性.

然而，從實驗結(jié)果中可以發(fā)現(xiàn)，DQN,DRQN,PER和UCBS-DQN這4種方法的穩(wěn)定性都不佳.因此，在如何提高模型穩(wěn)定性方面仍有工作可以繼續(xù)開展，可以采用監(jiān)督學習方法或經(jīng)驗來協(xié)助訓練出模型初始參數(shù)，然后再使用強化學習來更新策略.

ZhuFei, born in 1978. PhD and associate professor. Member of CCF. His main research interests include reinforcement learning, text mining and bioinformatics.

WuWen, born in 1994. Postgraduate of Soochow University. His main research interests include deep reinforcement learning and intelligence information processing (20164227051@stu.suda.edu.cn).

LiuQuan, born in 1969. PhD and professor. Member of CCF. His main research interests include reinforcement learning, and automated reasoning (quanliu@suda.edu.cn).

FuYuchen, born in 1968. PhD and professor. Member of CCF. His main research interests include reinforcement learning, intelligence information processing and deep Web (yuchenfu@cslg.edu.cn).