楊 珉，汪 潔

中南大學(xué) 信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410083

1 引言

強(qiáng)化學(xué)習(xí)領(lǐng)域最主要的三大問(wèn)題[1]分別是：（1）泛化；（2）如何平衡探索與利用之間的關(guān)系；（3）信用分配問(wèn)題（credit assignment problem）。近幾年的研究熱點(diǎn)主要集中在大規(guī)模狀態(tài)空間下的泛化問(wèn)題，并有了一個(gè)新的研究領(lǐng)域，名為深度強(qiáng)化學(xué)習(xí)[2]（deep reinforcement learning）。該領(lǐng)域的興起是從DeepMind團(tuán)隊(duì)提出DQN（deep Q-network）算法[3]后開始的，DQN算法最主要的貢獻(xiàn)就是將深度學(xué)習(xí)[4]和強(qiáng)化學(xué)習(xí)[5]結(jié)合起來(lái)，并通過(guò)經(jīng)驗(yàn)回放（experience replay）和目標(biāo)網(wǎng)絡(luò)機(jī)制來(lái)解決有關(guān)泛化的一些問(wèn)題[6]。此后，也有很多關(guān)于DQN算法的改進(jìn)版本被提出來(lái)[7-8]，這些算法主要關(guān)注的還是泛化問(wèn)題，而本文要探討的主要問(wèn)題是如何平衡探索與利用之間的關(guān)系。

機(jī)器學(xué)習(xí)領(lǐng)域中最熱門的監(jiān)督學(xué)習(xí)算法只能從人類收集到的數(shù)據(jù)中學(xué)習(xí)相關(guān)的模式，然而需要收集什么樣的數(shù)據(jù)，或者說(shuō)哪些數(shù)據(jù)是重要的還是需要人類來(lái)決定。強(qiáng)化學(xué)習(xí)可以通過(guò)選擇不同的動(dòng)作得到不同的觀察序列，然后根據(jù)得到的觀察序列學(xué)習(xí)相關(guān)的模式，也就是說(shuō)，在強(qiáng)化學(xué)習(xí)的范疇內(nèi)，需要算法來(lái)決定是選擇當(dāng)前最優(yōu)的動(dòng)作（利用）還是選擇有可能帶來(lái)長(zhǎng)期利益的動(dòng)作（探索）。然而DQN等算法使用的是簡(jiǎn)單的啟發(fā)式探索策略ε-貪婪，該策略只以ε(0 ≤ε≤1)的概率隨機(jī)選擇一個(gè)動(dòng)作，以此來(lái)達(dá)到探索的效果，然而這樣的探索策略是極其低效的。雖然DQN算法能在街機(jī)學(xué)習(xí)環(huán)境[9]（arcade learning environment）中達(dá)到甚至超過(guò)人類水平，但是在面對(duì)深度探索問(wèn)題（參見(jiàn)第4章）時(shí)，算法的時(shí)間復(fù)雜度為O(2N)。好的探索策略必須要考慮所選擇的動(dòng)作所帶來(lái)的信息增益，而信息主要是通過(guò)估計(jì)值的不確定程度來(lái)衡量的，那么只需引入概率思維就可以得到一個(gè)好的探索策略。其實(shí)早在1998年，Dearden等學(xué)者就提出了貝葉斯Q學(xué)習(xí)[10]來(lái)平衡探索與利用之間的關(guān)系。此后，也有其他研究人員提出了貝葉斯框架下的強(qiáng)化學(xué)習(xí)算法[11-12]，然而這些算法的計(jì)算過(guò)程比較復(fù)雜，而且無(wú)法和深度學(xué)習(xí)技術(shù)結(jié)合起來(lái)。貝葉斯強(qiáng)化學(xué)習(xí)和深度學(xué)習(xí)結(jié)合最主要的問(wèn)題是：在高維狀態(tài)空間下，得到神經(jīng)網(wǎng)絡(luò)參數(shù)的后驗(yàn)分布是棘手的（intractable）。本文的貢獻(xiàn)就在于提出了一種新的計(jì)算方法，該計(jì)算方法可以產(chǎn)生參數(shù)后驗(yàn)分布的樣本（參見(jiàn)第5章），將使用了該計(jì)算方法的深度強(qiáng)化學(xué)習(xí)算法統(tǒng)稱為貝葉斯深度強(qiáng)化學(xué)習(xí)算法。目前而言，該計(jì)算方法只適用于基于值的深度強(qiáng)化學(xué)習(xí)算法，同基于策略的深度強(qiáng)化學(xué)習(xí)算法的結(jié)合需要進(jìn)一步的研究。將Bootstrapped DQN[13]和該計(jì)算方法結(jié)合，得到新的算法BBDQN（Bayesian Bootstrapped DQN），并通過(guò)兩個(gè)環(huán)境下的實(shí)驗(yàn)來(lái)驗(yàn)證算法的探索效率，其中一個(gè)實(shí)驗(yàn)環(huán)境是具有深度探索結(jié)構(gòu)的格子世界；另一個(gè)實(shí)驗(yàn)環(huán)境是經(jīng)典控制問(wèn)題Mountain Car，該問(wèn)題本身不具備深度探索結(jié)構(gòu)，對(duì)其獎(jiǎng)勵(lì)函數(shù)稍作修改使其具備深度探索結(jié)構(gòu)，然后在修改后的Mountain Car上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果顯示BBDQN可以解決深度探索問(wèn)題，并且其探索效率要優(yōu)于使用隨機(jī)探索策略（即ε-貪婪）的DQN算法以及Bootstrapped DQN算法。

2 相關(guān)工作

強(qiáng)化學(xué)習(xí)算法的探索效率直接影響到算法的樣本效率，提高探索效率可以降低訓(xùn)練智能體所需的時(shí)間步數(shù)。貝葉斯最優(yōu)策略（Bayes-optimal policy）是衡量強(qiáng)化學(xué)習(xí)算法的探索效率的一個(gè)標(biāo)準(zhǔn)，然而計(jì)算貝葉斯最優(yōu)策略是棘手的，因?yàn)橛?jì)算時(shí)間隨問(wèn)題空間（狀態(tài)和動(dòng)作）呈指數(shù)級(jí)增長(zhǎng)[14]?？紤]探索效率方面的研究非常多，而最早提出的是Kearns和Singh[15]，他們的工作確認(rèn)了多項(xiàng)式時(shí)間的強(qiáng)化學(xué)習(xí)算法必須用到多周期探索（multi-period exploration）?；谒麄兊墓ぷ?，一系列表格（tabular）強(qiáng)化學(xué)習(xí)算法被提出來(lái)[16-22]，這些論文中提到的探索方法都要比ε-貪婪和玻爾茲曼探索要高效，但是這些方法都無(wú)法處理維數(shù)災(zāi)難（curse of dimensionality）。近幾年提出的處理大規(guī)模狀態(tài)空間的深度強(qiáng)化學(xué)習(xí)算法[3，23-24]偏向于使用ε-貪婪探索，這些算法在Atari街機(jī)游戲以及圍棋上能得到很好的結(jié)果，然而卻沒(méi)有任何實(shí)際方面的應(yīng)用，低效的探索效率使得這些算法只能在模擬環(huán)境中訓(xùn)練。

針對(duì)大規(guī)模狀態(tài)空間下的探索，有研究人員提出了模型學(xué)習(xí)算法[25]，該方法的問(wèn)題在于只能解決簡(jiǎn)單的模型類問(wèn)題，對(duì)于復(fù)雜的模型，該方法的計(jì)算也是棘手的。有研究人員提出了策略學(xué)習(xí)算法[26]，該類算法主要解決的是連續(xù)動(dòng)作空間問(wèn)題，如機(jī)器人控制，但是當(dāng)策略空間的大小是指數(shù)級(jí)的時(shí)候，該方法就無(wú)法保證探索的效率了。還有一類方法是根據(jù)偽計(jì)數(shù)（pseudocount）[27]或密度模型[28]給不常訪問(wèn)的狀態(tài)分配獎(jiǎng)勵(lì)，以此來(lái)達(dá)到鼓勵(lì)探索的目的。

如何保證算法的探索效率和泛化一直是強(qiáng)化學(xué)習(xí)的一個(gè)難題，也有研究人員想到了使用貝葉斯思想處理這一問(wèn)題，比如貝葉斯Q學(xué)習(xí)算法[10]，然而該算法只能處理狀態(tài)數(shù)量有限的問(wèn)題；還有Osband等人[29]提出的RLSVI（randomized least-square value iteration）算法，該算法只適用于線性函數(shù)逼近器，無(wú)法和神經(jīng)網(wǎng)絡(luò)這一非線性函數(shù)逼近器相結(jié)合；而Azizzadenesheli等人[30]提出的算法將神經(jīng)網(wǎng)絡(luò)作為特征提取器，將網(wǎng)絡(luò)的最后一層的輸入作為特征，然后使用貝葉斯線性回歸計(jì)算Q值。貝葉斯神經(jīng)網(wǎng)絡(luò)方面的研究一直未成為主流[31-32]，然而最近有復(fù)蘇的跡象，有許多關(guān)于量化數(shù)據(jù)集的不確定性的方法[33-35]被提出來(lái)，本文作者受到這些方法的啟發(fā)，提出了一種可以有效計(jì)算貝葉斯后驗(yàn)的深度強(qiáng)化學(xué)習(xí)算法。

3 背景知識(shí)

強(qiáng)化學(xué)習(xí)問(wèn)題通常建模為馬爾可夫決策過(guò)程，本文使用的馬爾可夫決策過(guò)程可以表示為(S,A,T,R,γ)，其中S為狀態(tài)空間；A為動(dòng)作空間且A(s),s∈S為狀態(tài)s下可用的動(dòng)作集；T為狀態(tài)轉(zhuǎn)移概率，T(st+1|st,at)表示在狀態(tài)st下采取動(dòng)作at后轉(zhuǎn)移到狀態(tài)st+1的概率；R為獎(jiǎng)勵(lì)函數(shù)，用Rs,a表示在狀態(tài)s下采取動(dòng)作a后得到的獎(jiǎng)勵(lì)分布的均值，用r表示狀態(tài)s下采取動(dòng)作a后得到的立即獎(jiǎng)勵(lì)（也可以理解為從獎(jiǎng)勵(lì)分布中得到的樣本），則有Rs,a=Ε[r|st=s,at=a]；γ∈[0,1)是折扣參數(shù)，用來(lái)控制未來(lái)獎(jiǎng)勵(lì)所占的權(quán)重。

強(qiáng)化學(xué)習(xí)的目標(biāo)是學(xué)習(xí)一個(gè)策略使得智能體所獲得的折扣累積獎(jiǎng)勵(lì)最大化。用π來(lái)表示策略，且π(a|s)表示在狀態(tài)s下采取動(dòng)作a的概率。然后引入動(dòng)作值函數(shù)（Q函數(shù)）的概念，動(dòng)作值函數(shù)Qπ(s,a)表示在策略π下，智能體在狀態(tài)s下采取了動(dòng)作a后所能獲得的期望折扣累積獎(jiǎng)勵(lì)，即：

該方程也可以通過(guò)遞歸的形式表示出來(lái)：

用π*表示最優(yōu)策略，用Q*表示最優(yōu)動(dòng)作值函數(shù)。由于最優(yōu)策略就是能獲得最大折扣累積獎(jiǎng)勵(lì)的策略，因此可以將Q*函數(shù)寫為：

式（1）也稱作貝爾曼最優(yōu)方程（Bellman optimality equation），對(duì)于每一對(duì)s,a，都有一個(gè)方程，將所有這些方程聯(lián)合起來(lái)就得到了一個(gè)方程組，通過(guò)線性規(guī)劃方法可以求解這個(gè)方程組得到所有s,a對(duì)應(yīng)的最優(yōu)動(dòng)作值函數(shù)Q*(s,a)。也可以通過(guò)策略迭代（policy iteration）或者值迭代（value iteration）等動(dòng)態(tài)規(guī)劃方法求解最優(yōu)動(dòng)作值函數(shù)。最優(yōu)策略可以通過(guò)最優(yōu)動(dòng)作值函數(shù)表達(dá)出來(lái)，即對(duì)于所有狀態(tài)s，選擇該狀態(tài)下使得最優(yōu)動(dòng)作值函數(shù)最大的動(dòng)作，如果有多個(gè)動(dòng)作滿足這一條件，可以從這些動(dòng)作中隨機(jī)選擇一個(gè)。從式（1）中可以看到，這種方法需要已知環(huán)境模型——狀態(tài)轉(zhuǎn)移概率T和獎(jiǎng)勵(lì)函數(shù)R——才能計(jì)算出來(lái)，在不知道環(huán)境模型的情況下就需要通過(guò)其他方法來(lái)求最優(yōu)策略，比如Q學(xué)習(xí)算法。Q學(xué)習(xí)是通過(guò)迭代方式來(lái)計(jì)算最優(yōu)動(dòng)作值函數(shù)的，更新規(guī)則為：

其中，α為學(xué)習(xí)率，獎(jiǎng)勵(lì)r和下一狀態(tài)s'都是環(huán)境反饋給智能體的，在狀態(tài)空間和動(dòng)作空間有限的情況下，只要學(xué)習(xí)率序列滿足隨機(jī)近似條件且所有狀態(tài)-動(dòng)作對(duì)都能得到持續(xù)更新的情況下，該算法以概率1收斂到最優(yōu)值函數(shù)Q*[5]。

在大規(guī)模狀態(tài)空間下，傳統(tǒng)的強(qiáng)化學(xué)習(xí)算法Q學(xué)習(xí)不再適用，但是可以通過(guò)結(jié)合函數(shù)逼近技術(shù)來(lái)解決這一問(wèn)題。神經(jīng)網(wǎng)絡(luò)和強(qiáng)化學(xué)習(xí)的結(jié)合是近幾年研究的熱點(diǎn)，而DQN算法就是這方面的典范。當(dāng)使用神經(jīng)網(wǎng)絡(luò)時(shí)，動(dòng)作值函數(shù)可以表示為Qθ(s,a)，其中θ是神經(jīng)網(wǎng)絡(luò)的參數(shù)。通過(guò)與環(huán)境交互得到的反饋信息來(lái)計(jì)算目標(biāo)值：

有了目標(biāo)值和預(yù)測(cè)值就可以通過(guò)隨機(jī)梯度下降算法更新神經(jīng)網(wǎng)絡(luò)的參數(shù)θ，更新規(guī)則為：

如果直接這樣做的話，效果并不是很好，因?yàn)樯窠?jīng)網(wǎng)絡(luò)是監(jiān)督學(xué)習(xí)方法，要求各個(gè)訓(xùn)練樣本之間是相互獨(dú)立的，強(qiáng)化學(xué)習(xí)收集的樣本之間是相互關(guān)聯(lián)的，而且每次更新參數(shù)會(huì)影響到目標(biāo)值，導(dǎo)致目標(biāo)值不穩(wěn)定。正如DQN算法中所提到的，只需要兩個(gè)機(jī)制就可以緩解這一問(wèn)題：經(jīng)驗(yàn)回放和目標(biāo)網(wǎng)絡(luò)。經(jīng)驗(yàn)回放機(jī)制就是每次智能體與環(huán)境交互時(shí)，將該次交互的信息(s,a,r,s′)存入記憶池（replay buffer）中，每次更新時(shí)智能體從記憶池中隨機(jī)抽取一定數(shù)量的樣本，并用這些樣本來(lái)更新參數(shù)。目標(biāo)網(wǎng)絡(luò)機(jī)制就是智能體維護(hù)兩個(gè)Q網(wǎng)絡(luò)，一個(gè)網(wǎng)絡(luò)是用來(lái)選擇動(dòng)作并實(shí)時(shí)更新的，另一個(gè)網(wǎng)絡(luò)（目標(biāo)網(wǎng)絡(luò)）用來(lái)計(jì)算目標(biāo)值并且不會(huì)實(shí)時(shí)更新，每次更新時(shí)使用的目標(biāo)值可以表示為：

其中，Qtarget表示目標(biāo)網(wǎng)絡(luò)，只有過(guò)了指定的時(shí)間步后，才將兩個(gè)網(wǎng)絡(luò)的參數(shù)同步一次。

4 深度探索問(wèn)題

文獻(xiàn)[10]中提到的鏈問(wèn)題就是一類深度探索問(wèn)題，本章將用該問(wèn)題來(lái)分析ε-貪婪策略和玻爾茲曼探索的探索效率。為了計(jì)算簡(jiǎn)便，對(duì)文獻(xiàn)[10]中的鏈問(wèn)題做出了一定的修改。

ε-貪婪探索就是有ε的概率從所有可用的動(dòng)作中隨機(jī)選擇一個(gè)，有1-ε的概率選擇就當(dāng)前而言最優(yōu)的動(dòng)作。玻爾茲曼探索選擇每個(gè)動(dòng)作的概率和動(dòng)作值函數(shù)的估計(jì)成正比，計(jì)算公式為：

Fig.1 Chain problem圖1 鏈問(wèn)題

使用一個(gè)鏈問(wèn)題來(lái)分析ε-貪婪探索和玻爾茲曼探索的探索效率，該問(wèn)題的狀態(tài)轉(zhuǎn)換圖如圖1所示，圖中每一條箭頭都對(duì)應(yīng)一個(gè)動(dòng)作以及獎(jiǎng)勵(lì)，該問(wèn)題的起始狀態(tài)為1，終止?fàn)顟B(tài)為N。假設(shè)每個(gè)周期（episode）的長(zhǎng)度H=N-1，并且無(wú)論在哪個(gè)狀態(tài)下，選擇動(dòng)作a會(huì)有0.2的概率失敗（失敗意味著選擇的動(dòng)作和實(shí)際動(dòng)作不一致），而動(dòng)作b是確定性的。這個(gè)問(wèn)題的最優(yōu)策略就是一直選擇動(dòng)作a，最優(yōu)策略每個(gè)周期所能得到的平均獎(jiǎng)勵(lì)就是該策略成功到達(dá)N的概率(1-0.2)N-1。無(wú)論是ε-貪婪探索還是玻爾茲曼探索，由于到達(dá)目標(biāo)狀態(tài)N之前沒(méi)有獎(jiǎng)勵(lì)（即獎(jiǎng)勵(lì)為0），因此所有狀態(tài)下動(dòng)作a和動(dòng)作b的估計(jì)值都是相等的，動(dòng)作選擇完全是隨機(jī)的，這種情況下通過(guò)探索到達(dá)狀態(tài)N的概率為(1-0.2)N-1×2-(N-1)，只需取該概率的倒數(shù)就能得到通過(guò)探索到達(dá)狀態(tài)N平均所需的周期數(shù)量，用l代表所需的周期數(shù)量，則有如下關(guān)系成立：

根據(jù)該不等式，可以確定使用ε-貪婪策略或玻爾茲曼探索的強(qiáng)化學(xué)習(xí)算法在面對(duì)鏈問(wèn)題之類的深度探索問(wèn)題時(shí)，其時(shí)間復(fù)雜度為O(2N)，其中N代表問(wèn)題的規(guī)模。

5 貝葉斯深度強(qiáng)化學(xué)習(xí)

探索的好處可以用信息的價(jià)值估計(jì)，所謂信息的價(jià)值即指探索所獲得的信息導(dǎo)致未來(lái)決策質(zhì)量提升的程度，而如何量化探索所獲得的信息是關(guān)鍵。根據(jù)信息論，可以用探索所選擇的動(dòng)作的估值的不確定程度來(lái)計(jì)算該次探索所帶來(lái)的信息量。在文獻(xiàn)[10]中，就提出采用貝葉斯方法來(lái)維持這一信息，然而在該篇論文中，所討論的問(wèn)題的狀態(tài)動(dòng)作對(duì)的數(shù)量有限，可以通過(guò)記錄每一個(gè)狀態(tài)動(dòng)作對(duì)獲得的所有的回報(bào)，然后計(jì)算方差，再計(jì)算信息量。當(dāng)狀態(tài)動(dòng)作對(duì)數(shù)量過(guò)大時(shí)，強(qiáng)化學(xué)習(xí)會(huì)考慮結(jié)合泛化技術(shù)來(lái)解決這一問(wèn)題，如果使用的是線性函數(shù)逼近器，可以根據(jù)文獻(xiàn)[36]中提到的貝葉斯線性回歸來(lái)得到估值的方差。但是近幾年和深度學(xué)習(xí)相關(guān)的研究表明，神經(jīng)網(wǎng)絡(luò)強(qiáng)大的泛化能力遠(yuǎn)強(qiáng)于線性函數(shù)逼近器的泛化能力，因此結(jié)合深度學(xué)習(xí)和強(qiáng)化學(xué)習(xí)技術(shù)成了一大趨勢(shì)，并產(chǎn)生了一個(gè)新的研究領(lǐng)域被稱作深度強(qiáng)化學(xué)習(xí)。由于神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜，且參數(shù)數(shù)量十分龐大，無(wú)法通過(guò)文獻(xiàn)[36]中提到的計(jì)算方法來(lái)計(jì)算估值的方差，因此本文提出了一種新的計(jì)算方法。該方法在每一個(gè)時(shí)間步通過(guò)計(jì)算得到神經(jīng)網(wǎng)絡(luò)參數(shù)的后驗(yàn)分布的一個(gè)樣本，由于不同動(dòng)作的估值方差不同，方差高的動(dòng)作其信息量越大，同時(shí)其采樣值也可能更大，因此被選擇的概率也越高。舉個(gè)例子，有兩個(gè)動(dòng)作，其Q值服從高斯分布，由于動(dòng)作1被選擇的次數(shù)更多，因此其方差要小于動(dòng)作2，假設(shè)動(dòng)作1的方差為1，動(dòng)作2的方差為10，此外動(dòng)作1的歷史回報(bào)均值為3，動(dòng)作2的歷史回報(bào)均值為1，因此動(dòng)作1服從均值為3方差為1的高斯分布，而動(dòng)作2服從均值為1方差為10的高斯分布，結(jié)果就是動(dòng)作2由于方差大，其采樣值大于動(dòng)作1的采樣值的概率也更大。接下來(lái)詳細(xì)介紹如何在深度強(qiáng)化學(xué)習(xí)算法中應(yīng)用貝葉斯方法。

神經(jīng)網(wǎng)絡(luò)的輸入既可以是一維數(shù)組，也可以是二維矩陣，甚至可以是三維圖像。為了表示清晰，用x∈?d表示狀態(tài)特征，也就是神經(jīng)網(wǎng)絡(luò)的輸入值，加上目標(biāo)值y組成訓(xùn)練集，表示為。首先計(jì)算線性回歸模型參數(shù)的后驗(yàn)分布，稍后再將其擴(kuò)展到神經(jīng)網(wǎng)絡(luò)的情形下。模型參數(shù)表示為θ∈?d，且假設(shè)參數(shù)θ的先驗(yàn)分布為，觀察到的目標(biāo)值有一定噪聲，即yi=θTxi+wi，其中wi∝N(0,σ2)為噪聲，各個(gè)樣本的噪聲是相互獨(dú)立的。根據(jù)貝葉斯定理參數(shù)θ的后驗(yàn)分布可以表示為：

在貝葉斯理論中，p(D|θ)被稱為似然，p(θ)被稱為先驗(yàn)，p(D)被稱為證據(jù)。根據(jù)文獻(xiàn)[36]的推導(dǎo)，參數(shù)θ的后驗(yàn)分布服從均值為式（2）、協(xié)方差為式（3）的多元高斯分布：

其中，X∈?n×d為n個(gè)樣本輸入xi拼接后得到的矩陣，y∈?n為n個(gè)目標(biāo)值yi拼接后得到的向量。可以通過(guò)馬爾可夫鏈蒙特卡羅等方法推斷出該后驗(yàn)分布，但為了擴(kuò)展到非線性模型人工神經(jīng)網(wǎng)絡(luò)，將后驗(yàn)分布用另一種形式表示出來(lái)：

其中，δ∈?n是一個(gè)隨機(jī)向量，其每個(gè)分量δi都來(lái)自高斯分布N(0,σ2)，且各分量的采樣是相互獨(dú)立的，來(lái)自參數(shù)先驗(yàn)分布?？梢宰C明，和θ是等價(jià)的，因?yàn)椋?/p>

將貝葉斯方法和Bootstrapped DQN結(jié)合起來(lái)的方法稱作BBDQN算法，該算法的整體描述見(jiàn)算法1。

算法1BBDQN算法

輸入：折扣參數(shù)γ，批量大小n，學(xué)習(xí)器數(shù)量K，參數(shù)先驗(yàn)均值，參數(shù)先驗(yàn)方差λ，采樣間隔Tsample，目標(biāo)網(wǎng)絡(luò)更新間隔Ttarget。

6 實(shí)驗(yàn)分析

6.1 格子世界

首先在如圖2所示的格子世界中測(cè)試BBDQN算法的探索效率，白色部分的格子代表網(wǎng)格世界的規(guī)模，灰色格子為終止?fàn)顟B(tài)，由于空間限制，圖2中的格子世界的規(guī)模僅為4×4，而在實(shí)驗(yàn)中使用的格子世界的規(guī)模為20×20，但這并不妨礙使用圖2的小規(guī)模格子世界來(lái)描述其動(dòng)態(tài)模型。圖2中狀態(tài)S為起始狀態(tài)，且智能體一直保持一個(gè)向右行進(jìn)的速度+1，在每個(gè)狀態(tài)中可供選擇的動(dòng)作是up和down，即向上和向下，如果選擇向上，則下一步會(huì)到達(dá)當(dāng)前狀態(tài)的右上狀態(tài)，如果選擇向下，則下一步會(huì)到達(dá)當(dāng)前狀態(tài)的右下?tīng)顟B(tài)。如果智能體處于格子世界的底部，則向下動(dòng)作可以理解為貼墻行進(jìn)，此時(shí)下一狀態(tài)將處于當(dāng)前狀態(tài)的右方，如果在白色格子的右上角選擇動(dòng)作up就能到達(dá)灰色格子的頂部，并獲得+1的獎(jiǎng)勵(lì)，其他狀態(tài)都沒(méi)有獎(jiǎng)勵(lì)，因此要想獲得獎(jiǎng)勵(lì)必須一直選擇動(dòng)作up，然而動(dòng)作up是有代價(jià)的，該代價(jià)是和格子世界的規(guī)模相關(guān)的。假設(shè)格子世界的規(guī)模為N×N，則每一次選擇動(dòng)作up會(huì)帶來(lái)-0.01/N的獎(jiǎng)勵(lì)，而選擇動(dòng)作down沒(méi)有代價(jià)，獎(jiǎng)勵(lì)為0。其實(shí)該問(wèn)題就是第4章提到的鏈問(wèn)題的二維擴(kuò)展版本，可以將輸入表示為一個(gè)one-hot矩陣xi∈{0,1}N×N，矩陣中智能體所在的位置為1，其他位置全為0。在該實(shí)驗(yàn)中，將同使用ε-貪婪策略的DQN以及Bootstrapped DQN進(jìn)行比較，BBDQN算法用到的超參數(shù)顯示在表1中，其中0 ∈?d代表分量全為0的一個(gè)向量。

Fig.2 Gridworld with deep exploration structure圖2 具有深度探索結(jié)構(gòu)的格子世界

Table 1 Hyperparameters表1 超參數(shù)

實(shí)驗(yàn)結(jié)果顯示在圖3中，圖中是用遺憾（regret）來(lái)衡量算法性能的。遺憾是指最大累積獎(jiǎng)勵(lì)與實(shí)際累積獎(jiǎng)勵(lì)之間的差值，該指標(biāo)越小算法性能越好。因?yàn)镈QN一直沒(méi)有發(fā)現(xiàn)格子世界中存在獎(jiǎng)勵(lì)的區(qū)域，因此其累積獎(jiǎng)勵(lì)小于0，其遺憾在不斷地增長(zhǎng)。從圖3中可以看到，BBDQN只需不到2 000個(gè)周期就可以學(xué)習(xí)到最優(yōu)策略，而DQN在10 000個(gè)周期后都沒(méi)有學(xué)習(xí)到一個(gè)好的策略。事實(shí)上，進(jìn)行了100萬(wàn)個(gè)周期的實(shí)驗(yàn)，DQN依然沒(méi)有收斂。

Fig.3 Comparison of algorithm performance in Gridworld圖3 格子世界上算法性能比較

正如第4章所分析的那樣，使用ε-貪婪策略的DQN算法在面對(duì)深度探索問(wèn)題時(shí)，算法的時(shí)間復(fù)雜度為O(2N)。本文還測(cè)試了Bootstrapped DQN算法的性能，該算法的動(dòng)作選擇不是通過(guò)ε-貪婪實(shí)現(xiàn)的，而且該算法是通過(guò)在DQN的基礎(chǔ)上加入集成技術(shù)來(lái)提高其探索效率的[13]，但也無(wú)法在短期內(nèi)解決該深度探索問(wèn)題。Bootstrapped DQN和DQN在10 000個(gè)周期內(nèi)的遺憾只有微小的差異，該差異在圖3中看不出來(lái)，必須放大才能看出區(qū)別，具體地講，DQN在10 000個(gè)周期中累積的遺憾為9 922.02，Bootstrapped DQN為9 914.60。

圖3是當(dāng)格子世界的規(guī)模為20×20時(shí)，算法的性能曲線?？梢约僭O(shè)格子世界的規(guī)模為N×N，并分析算法探索效率和N之間的關(guān)系。和第4章一樣，用算法第一次發(fā)現(xiàn)獎(jiǎng)勵(lì)所需的周期數(shù)作為探索效率的衡量指標(biāo)，通過(guò)實(shí)驗(yàn)得到了6個(gè)數(shù)據(jù)樣本，顯示在表2中，其中l(wèi)表示算法第一次發(fā)現(xiàn)獎(jiǎng)勵(lì)所需的周期數(shù)量。為了表示出兩者之間的關(guān)系，用多項(xiàng)式回歸來(lái)擬合這6個(gè)點(diǎn)，表示如下：

其中，w1,w2,…,wm為m次多項(xiàng)式的參數(shù)，可以通過(guò)最小二乘法求出。測(cè)試了多個(gè)m值，發(fā)現(xiàn)當(dāng)m為3時(shí)，均方誤差最小，即兩者之間的關(guān)系可以通過(guò)3次多項(xiàng)式來(lái)近似，如下：

Table 2 The number of episodes required to find rewards表2 發(fā)現(xiàn)獎(jiǎng)勵(lì)所需的周期數(shù)

其中，參數(shù)保留小數(shù)點(diǎn)后兩位。因此，BBDQN算法在面對(duì)深度探索問(wèn)題時(shí)，算法的時(shí)間復(fù)雜度是多項(xiàng)式級(jí)別的，具體為O(N3)，優(yōu)于隨機(jī)探索策略ε-貪婪的時(shí)間復(fù)雜度O(2N)。

6.2 有關(guān)格子世界的進(jìn)一步分析

在圖3中DQN算法和Bootstrapped DQN算法比較起來(lái)沒(méi)有明顯的差別，但這并不代表兩個(gè)算法的探索效率是一樣的。事實(shí)上，Bootstrapped DQN算法的探索效率要比DQN更高。為了證明這一結(jié)論，進(jìn)行了一系列實(shí)驗(yàn)。

在上一節(jié)提到了格子世界的規(guī)模表示為N×N，學(xué)習(xí)器的個(gè)數(shù)用K表示，比較了當(dāng)K固定為10，N為{10，20，30}時(shí)各算法的性能。此外，又比較了當(dāng)N固定為20時(shí)，K為{10，20，30}時(shí)各算法的性能。當(dāng)格子世界的規(guī)模變小時(shí)，Bootstrapped DQN相較于DQN的優(yōu)越性就體現(xiàn)出來(lái)了。如圖4所示，當(dāng)K為10且N為10時(shí)，DQN算法的遺憾一直增長(zhǎng)，而Bootstrapped DQN和BBDQN在1 000個(gè)周期內(nèi)就找到了最優(yōu)策略。此外，當(dāng)學(xué)習(xí)器的數(shù)量增大時(shí)，Bootstrapped DQN相較于DQN的優(yōu)越性同樣能體現(xiàn)出來(lái)。如圖5所示，當(dāng)K為30且N為20時(shí)，Bootstrapped DQN算法在2 000個(gè)周期左右的時(shí)間點(diǎn)找到最優(yōu)策略。

Fig.4 Comparison of algorithm performance in Gridworld(N=10，K=10)圖4 格子世界（N=10，K=10）上算法性能比較

Fig.5 Comparison of algorithm performance in Gridworld(N=20，K=30)圖5 格子世界（N=20，K=30）上算法性能比較

所有實(shí)驗(yàn)的結(jié)果顯示在表3中，由于空間限制，Bootstrapped DQN在表中表示為BDQN。此外，6.1節(jié)的實(shí)驗(yàn)結(jié)果即表中K=10，N=20所示的結(jié)果。在表3中，能在10 000個(gè)周期內(nèi)學(xué)習(xí)到最優(yōu)策略的算法的遺憾用加粗字體顯示，可以看到DQN在所有的實(shí)驗(yàn)設(shè)置中都沒(méi)能在10 000個(gè)周期內(nèi)找到最優(yōu)策略，而Bootstrapped DQN只有當(dāng)K=10、N=10（格子世界的規(guī)模減?。┗騅=30、N=20（學(xué)習(xí)器的數(shù)量增加）時(shí)，才能在10 000個(gè)周期內(nèi)學(xué)習(xí)到最優(yōu)策略，而BBDQN在所有設(shè)置下都能在10 000個(gè)周期內(nèi)學(xué)習(xí)到最優(yōu)策略。從表3中還可以看出，當(dāng)格子世界的規(guī)模較小時(shí)（N=10），BBDQN算法和Bootstrapped DQN算法的性能相差不大，而且由于BBDQN加入了隨機(jī)初始化的先驗(yàn)網(wǎng)絡(luò)，BBDQN的性能甚至略低于Bootstrapped DQN，但是當(dāng)格子世界的規(guī)模增加時(shí)，本文提出的BBDQN算法的優(yōu)越性就愈發(fā)明顯，這也是BBDQN更適合解決深度探索問(wèn)題的體現(xiàn)；此外，BBDQN算法的性能并不會(huì)隨著學(xué)習(xí)器的數(shù)量增加而增加，這就意味著BBDQN的空間需求低于Bootstrapped DQN，因?yàn)閷W(xué)習(xí)器的數(shù)量越多，就需要越多的空間來(lái)存儲(chǔ)每個(gè)學(xué)習(xí)的參數(shù)，且這些算法都是使用神經(jīng)網(wǎng)絡(luò)作為函數(shù)逼近器，每個(gè)網(wǎng)絡(luò)的參數(shù)都是百萬(wàn)級(jí)的，而BBDQN并不像Bootstrapped DQN一樣要通過(guò)增加學(xué)習(xí)器的數(shù)量來(lái)提高算法性能（如表3所示），因此BBDQN的空間需求低于Bootstrapped DQN。

Table 3 Cumulative regret of each algorithm in 10 000 episodes表3 各算法在10 000個(gè)周期內(nèi)累積的遺憾

6.3 Mountain Car的變體

Mountain Car問(wèn)題如圖6所示，在該問(wèn)題中，小車的初始位置處于山底地區(qū)，目標(biāo)是到達(dá)右邊山頂，智能體接收到的狀態(tài)信號(hào)是目前所處的位置以及小車的速度，智能體有3個(gè)可供選擇的動(dòng)作，分別是左加速、不加速以及右加速，小車的動(dòng)態(tài)模型如下：

其中，x代表小車所處位置且有-1.2 ≤x≤0.6；v代表小車的速度且有-0.07 ≤v≤0.07；a代表智能體選擇的動(dòng)作，3個(gè)動(dòng)作[左加速，不加速，右加速]對(duì)應(yīng)的a值為[ 1,0,1]。當(dāng)小車到達(dá)左端位置即x=-1.2時(shí)速度將重置為0，如果小車位置大于0.5（即到達(dá)目標(biāo)區(qū)域）則該周期結(jié)束，進(jìn)入下一周期，如果小車在200個(gè)時(shí)間步內(nèi)還沒(méi)有到達(dá)右邊山頂，則強(qiáng)制結(jié)束該周期并進(jìn)入下一周期。該問(wèn)題的主要難點(diǎn)在于小車的動(dòng)力無(wú)法抵消重力，因此無(wú)法直接通過(guò)右加速到達(dá)右邊山頂，必須借助慣性才行。在原問(wèn)題中，小車每一個(gè)時(shí)間步都獲得-1的獎(jiǎng)勵(lì)，直到周期結(jié)束為止。

Fig.6 Mountain Car problem圖6 Mountain Car問(wèn)題

對(duì)原問(wèn)題的獎(jiǎng)勵(lì)信號(hào)做出修改，使其與深度探索問(wèn)題的結(jié)構(gòu)相吻合。每當(dāng)小車進(jìn)行加速，無(wú)論是左加速還是右加速，都需要一定的代價(jià)，即接收到一個(gè)負(fù)的獎(jiǎng)勵(lì)信號(hào)，和格子世界一樣，將其設(shè)置為-0.01/N，只不過(guò)這里的N是最優(yōu)策略到達(dá)右邊山頂所需的平均步數(shù)；如果不加速，則無(wú)需付出代價(jià)，即獎(jiǎng)勵(lì)為0；而一旦小車到達(dá)右邊山頂將接受到+1的獎(jiǎng)勵(lì)。實(shí)驗(yàn)結(jié)果如圖7所示，使用ε-貪婪探索的DQN算法其累積獎(jiǎng)勵(lì)一直小于0，代表該算法沒(méi)有找到包含獎(jiǎng)勵(lì)的區(qū)域，而Bootstrapped DQN和BBDQN算法在200個(gè)周期內(nèi)就發(fā)現(xiàn)了獎(jiǎng)勵(lì)區(qū)域。雖然Bootstrapped DQN一開始的累積獎(jiǎng)勵(lì)高于BBDQN，但在500個(gè)周期左右的時(shí)候BBDQN就超出Bootstrapped DQN了，而且增長(zhǎng)的速度（曲線斜率）也明顯快于Bootstrapped DQN。由于本文使用的BBDQN方法使用的先驗(yàn)網(wǎng)絡(luò)的參數(shù)是隨機(jī)初始化的，因此訓(xùn)練開始的時(shí)候BBDQN的累積獎(jiǎng)勵(lì)低只能說(shuō)明隨機(jī)初始化的先驗(yàn)網(wǎng)絡(luò)的參數(shù)和正確的值網(wǎng)絡(luò)的參數(shù)相差較遠(yuǎn)。

Fig.7 Comparison of algorithm performance on variant of Mountain Car圖7 Mountain Car的變體上的算法性能比較

7 結(jié)束語(yǔ)

結(jié)合近幾年興起的深度學(xué)習(xí)技術(shù)可以提高傳統(tǒng)強(qiáng)化學(xué)習(xí)算法的性能，然而這方面的進(jìn)展僅對(duì)強(qiáng)化學(xué)習(xí)中的泛化有幫助。強(qiáng)化學(xué)習(xí)和監(jiān)督學(xué)習(xí)最主要的區(qū)別就在于強(qiáng)化學(xué)習(xí)除了泛化外還存在兩個(gè)問(wèn)題：（1）平衡探索與利用之間的關(guān)系；（2）信用分配問(wèn)題。本文主要解決的探索利用困境這一問(wèn)題。結(jié)合貝葉斯方法可以提高強(qiáng)化學(xué)習(xí)算法的探索效率，幾十年前就有人做過(guò)這方面的研究，然而之前的方法無(wú)法適用于神經(jīng)網(wǎng)絡(luò)這類非線性模型，本文的貢獻(xiàn)就在于提出了一種能夠通過(guò)數(shù)值計(jì)算得到神經(jīng)網(wǎng)絡(luò)參數(shù)后驗(yàn)分布的樣本的方法，并將該計(jì)算方法和Bootstrapped DQN結(jié)合得到BBDQN算法。通過(guò)兩個(gè)環(huán)境下的實(shí)驗(yàn)證明了BBDQN算法的探索效率優(yōu)于使用ε-貪婪策略的DQN算法以及Bootstrapped DQN算法。

進(jìn)一步研究的方向是：本文計(jì)算Q函數(shù)參數(shù)后驗(yàn)分布的樣本的方法用于計(jì)算策略梯度（policy gradient）方法中策略函數(shù)πθ參數(shù)的后驗(yàn)分布的樣本時(shí)，能否有效提高策略梯度方法面對(duì)深度探索問(wèn)題時(shí)的探索效率。