一種加速時(shí)間差分算法收斂的方法

何斌 劉全,2,3,4 張琳琳 時(shí)圣苗 陳紅名 閆巖

強(qiáng)化學(xué)習(xí)是機(jī)器學(xué)習(xí)領(lǐng)域中最接近人類和動(dòng)物學(xué)習(xí)的方法[1],在機(jī)器人自主決策和學(xué)習(xí)、復(fù)雜動(dòng)態(tài)系統(tǒng)的優(yōu)化控制和自動(dòng)駕駛等領(lǐng)域中有著廣泛的應(yīng)用[2?5].強(qiáng)化學(xué)習(xí)算法分為基于模型和無(wú)模型兩種.基于模型的算法需要一個(gè)精確且完整的環(huán)境模型,而無(wú)模型算法沒有這個(gè)要求.無(wú)模型的強(qiáng)化學(xué)習(xí)算法中基于值函數(shù)的算法較為常用.該算法需要根據(jù)值函數(shù)得出最優(yōu)的策略.如果值函數(shù)無(wú)法準(zhǔn)確地被評(píng)估,或者評(píng)估的效率過(guò)低,那么將得不到最優(yōu)的策略,或者耗時(shí)過(guò)長(zhǎng).所以,一個(gè)精確和高效的值函數(shù)評(píng)估方法對(duì)于基于值函數(shù)的強(qiáng)化學(xué)習(xí)算法至關(guān)重要[6?7].

對(duì)于值函數(shù)評(píng)估問(wèn)題,經(jīng)典的解決方法是TD(Temporal difference methods)算法和MC(Monte Carlo methods)算法.其中,TD 算法可以像動(dòng)態(tài)規(guī)劃(Dynamic program)方法一樣使用自舉(Bootstrap)的方式,即利用已經(jīng)評(píng)估過(guò)的狀態(tài)值來(lái)進(jìn)行新的評(píng)估.這也使得TD 算法可以不需要等待情節(jié)結(jié)束,就可以進(jìn)行值函數(shù)的更新,從而實(shí)現(xiàn)了在線學(xué)習(xí)的方式.MC 算法必須等到情節(jié)結(jié)束后才能進(jìn)行值函數(shù)的更新,因而只能使用離線學(xué)習(xí)(Offline)的方式[1].但是如果TD 算法所利用的評(píng)估過(guò)的狀態(tài)值有偏差,那么評(píng)估的結(jié)果往往在真實(shí)值附近.另外,TD 算法的收斂效率很大程度上取決于初值和步長(zhǎng)參數(shù)的設(shè)定.優(yōu)秀的初值和恰當(dāng)?shù)牟介L(zhǎng)參數(shù)可以極大地縮小所需要策略迭代的次數(shù),但是初值的設(shè)定往往需要豐富的經(jīng)驗(yàn)和相關(guān)領(lǐng)域的專業(yè)知識(shí).對(duì)于步長(zhǎng)參數(shù)設(shè)定的問(wèn)題,有許多自動(dòng)設(shè)置步長(zhǎng)參數(shù)的算法可以解決[8?9].然而,盡管這些算法有許多理論上的優(yōu)勢(shì),但是由于其自身的復(fù)雜性和進(jìn)一步增加了TD 算法的時(shí)間復(fù)雜度而得不到廣泛的運(yùn)用,實(shí)際應(yīng)用中更多地采用固定步長(zhǎng)參數(shù)的方法[10].這也就造成了加速一個(gè)特定TD 算法收斂速率的方法的匱乏.

論文提出的ATDMC 方法是利用MC 算法的無(wú)偏的性質(zhì),在TD 算法完成一次值函數(shù)評(píng)估后,進(jìn)行值函數(shù)改進(jìn).即在廣義策略迭代中加入減少值函數(shù)和真實(shí)值函數(shù)的之間距離的步驟,使得在不改變TD 算法的在線學(xué)習(xí)的方式基礎(chǔ)上,加速算法的收斂.

文中第1 節(jié)描述了強(qiáng)化學(xué)習(xí)的相關(guān)基本概念和所用到的符號(hào)的定義.第2 節(jié)給出TD 算法的收斂速率的分析和ATDMC 方法的詳細(xì)推導(dǎo)過(guò)程.第3節(jié)用實(shí)驗(yàn)分別展示在同策略評(píng)估、異策略評(píng)估和控制三個(gè)方面的加速效果.最后一節(jié)給出結(jié)論和后續(xù)的工作方向.

1 強(qiáng)化學(xué)習(xí)相關(guān)基本概念

1.1 馬爾科夫決策過(guò)程

馬爾科夫決策過(guò)程(Markov decision process,MDP)是研究各種強(qiáng)化學(xué)習(xí)算法的理論基礎(chǔ),可以對(duì)大多數(shù)強(qiáng)化學(xué)習(xí)問(wèn)題進(jìn)行建模[11].這是因?yàn)镸DP 是在交互過(guò)程中學(xué)習(xí)以期達(dá)到某種目標(biāo)的問(wèn)題的框架,而強(qiáng)化學(xué)習(xí)問(wèn)題是指如何在和環(huán)境交互過(guò)程中使得收到的累計(jì)獎(jiǎng)賞最大化的問(wèn)題.其中,學(xué)習(xí)和決定動(dòng)作的對(duì)象稱為智能體(Agent),智能體交互的對(duì)象為環(huán)境.

MDP 是由一個(gè)4 元組 (S,A,R,P) 構(gòu)成.其中,S是指智能體在和環(huán)境進(jìn)行交互過(guò)程中,環(huán)境的所有狀態(tài)構(gòu)成的集合.A是指智能體采取的動(dòng)作構(gòu)成的集合,收到的獎(jiǎng)賞構(gòu)成的集合為R.P是由狀態(tài)轉(zhuǎn)移函數(shù)構(gòu)成.智能體和環(huán)境的一次交互是指智能體采取一個(gè)動(dòng)作(Action)后,環(huán)境返回一個(gè)獎(jiǎng)賞(Reward),然后智能體對(duì)環(huán)境進(jìn)行觀測(cè),得到一個(gè)新的狀態(tài)(State).為了表述簡(jiǎn)單,將一次完整的交互定義在時(shí)間步t發(fā)生,智能體所處的狀態(tài)記為S t,采取的動(dòng)作記為At,獲得的獎(jiǎng)賞記為Rt+1,到達(dá)的下一個(gè)狀態(tài)記為St+1.將由時(shí)間步 0 到終止時(shí)間步T的整個(gè)過(guò)程稱為一個(gè)情節(jié)(Episode).可見,一個(gè)情節(jié)中智能體經(jīng)過(guò)的狀態(tài)、采取的動(dòng)作和獲得的獎(jiǎng)賞構(gòu)成了一個(gè)序列:

將其中的獎(jiǎng)賞的累計(jì)求和稱為累計(jì)獎(jiǎng)賞.從狀態(tài)S t開始,直至結(jié)束狀態(tài)S T獲得的累計(jì)獎(jiǎng)賞定義為:

在一些強(qiáng)化學(xué)習(xí)任務(wù)中,最近獲得的獎(jiǎng)賞往往被賦予更大的權(quán)重值.因?yàn)橄啾扔谶^(guò)去獲得的獎(jiǎng)賞,新的獎(jiǎng)賞更值得關(guān)注.另外,當(dāng)情節(jié)的時(shí)間步較長(zhǎng)時(shí),Gt將會(huì)變?yōu)橐粋€(gè)比較大的值.對(duì)此,往往需要對(duì)獲得的獎(jiǎng)賞乘上一個(gè)折扣因子γ,來(lái)控制Gt的大小,則:

可見,如何使Gt最大化的問(wèn)題即為強(qiáng)化學(xué)習(xí)在MDP 框架下所要解決的問(wèn)題.

1.2 廣義策略迭代

廣義策略迭代(Generalized policy iteration,GPI)是強(qiáng)化學(xué)習(xí)中最一般的思想,幾乎所有的強(qiáng)化學(xué)習(xí)算法都可以描述成廣義策略迭代的形式.強(qiáng)化學(xué)習(xí)算法所要最大化的目標(biāo)G t的值是由在各個(gè)狀態(tài)下采取的動(dòng)作決定的,而在某個(gè)狀態(tài)采取何種動(dòng)作是由策略決定的.強(qiáng)化學(xué)習(xí)的目標(biāo)即為尋找一個(gè)策略使得Gt最大化,GPI 對(duì)此提供了具體思路.

GPI 可以分為策略評(píng)估(Policy evaluation)和策略改進(jìn)(Policy improvement)兩部分,由這兩部分交替進(jìn)行從而實(shí)現(xiàn)該思想.其中,策略評(píng)估是指在一個(gè)特定的狀態(tài)下,對(duì)遵循一個(gè)固定策略的智能體將會(huì)收到的累計(jì)獎(jiǎng)賞的期望進(jìn)行估值.對(duì)于一個(gè)給定的策略 π,從t時(shí)間步開始,獲得的累計(jì)獎(jiǎng)賞的期望記為:

這個(gè)值被稱為狀態(tài)S t的v值,也稱為S t在策略π的真實(shí)值.相應(yīng)地,如果在時(shí)間步采取的動(dòng)作為A t,那么獲得的累計(jì)獎(jiǎng)賞的期望為:

這個(gè)值也被稱為狀態(tài)動(dòng)作對(duì) (S t,A t) 的q值.由v值和q值的定義可知:

其中,π(A t|S t) 是在狀態(tài)S t采取動(dòng)作At的概率.

策略評(píng)估后,會(huì)根據(jù)評(píng)估出來(lái)的q值函數(shù)進(jìn)行策略改進(jìn).策略改進(jìn)一般采用?-greedy 算法,即最大的q值對(duì)應(yīng)的動(dòng)作被選取的概率為 1??,另外有?的概率任取一個(gè)動(dòng)作.一次策略評(píng)估和策略改進(jìn)形成了一次完整的策略迭代.下一輪迭代將根據(jù)新的策略繼續(xù)評(píng)估,然后再改進(jìn)策略.經(jīng)過(guò)多次策略迭代后,策略達(dá)到了穩(wěn)定的狀態(tài),各個(gè)狀態(tài)的值函數(shù)達(dá)到最大值.此時(shí)的策略稱為最優(yōu)策略,對(duì)應(yīng)的值函數(shù)稱為最優(yōu)值函數(shù),記為

1.3 TD 算法

TD 算法是強(qiáng)化學(xué)習(xí)中最核心的算法,可以用來(lái)評(píng)估v值和q值函數(shù).如果一些狀態(tài)的值函數(shù)已被評(píng)估過(guò)或是被賦予了初值(雖然初值可能是錯(cuò)誤的,但也可以視為被評(píng)估過(guò)),則可以利用這些評(píng)估過(guò)的值來(lái)評(píng)估其他狀態(tài)的值函數(shù).TD 算法會(huì)對(duì)每一個(gè)v值或者q值進(jìn)行賦初值,再利用這些初值進(jìn)行新的評(píng)估,然后進(jìn)行策略改進(jìn),不斷循環(huán)進(jìn)行從而實(shí)現(xiàn)GPI.

TD 算法策略迭代的過(guò)程可以看作是值函數(shù)不斷向v?靠近的過(guò)程.在具體的TD 算法中,v?是未知的值,往往被替換成相應(yīng)算法的目標(biāo)UTD.根據(jù)所利用的評(píng)估過(guò)的值函數(shù)是一步還是多步之后的狀態(tài)的值函數(shù),將TD 算法分為一步或n步TD.對(duì)于n步TD 算法而言,UTD為:

其中,V(S t+n) 為n步之后的狀態(tài)的v值的估計(jì)值,而這個(gè)值可能是錯(cuò)誤的.如果該值為對(duì)應(yīng)狀態(tài)的真實(shí)值,則顯然Gt:t+n的期望也為真實(shí)值.另外,n=1的情況即為一步TD 的UTD.利用n步TD 算法的目標(biāo),TD 算法的值函數(shù)的更新公式為:

其中,α為步長(zhǎng)參數(shù).

強(qiáng)化學(xué)習(xí)在處理狀態(tài)空間很大的問(wèn)題時(shí),往往采用函數(shù)逼近的方法.使用狀態(tài)的特征向量x(S t)和權(quán)重向量w來(lái)表示狀態(tài)的值函數(shù).在使用線性逼近方法的情況下,值函數(shù)記為:

顯然在函數(shù)逼近的條件下,并不一定存在一個(gè)權(quán)重向量w使得所有狀態(tài)的值都能等于對(duì)應(yīng)的vπ.所以,為了求出使得值函數(shù)和vπ之間的距離的平方和最小的w,將損失函數(shù)定義為:

由于vπ(S t) 值未知,將其替換為UTD. 那么TD算法的權(quán)重向量的更新公式定義為:

1.4 MC 算法

MC 算法是另外一種強(qiáng)化學(xué)習(xí)中評(píng)估值函數(shù)的算法.MC 算法的值函數(shù)的更新公式為:

其中,n是情節(jié)數(shù).從公式可見MC 算法的目標(biāo)為G t,而由Gt的定義可知Gt的值是整個(gè)情節(jié)中所有的獎(jiǎng)賞的累計(jì)和.也就意味著如果情節(jié)不結(jié)束,Gt的值都是未知的,從而使得MC 算法只能使用離線學(xué)習(xí)的方式.

從vπ的定義可知MC 算法的更新目標(biāo)G t的期望值為vπ,即Gt是vπ的無(wú)偏估計(jì).而TD 算法的目標(biāo)只有在V(S t+n) 為真實(shí)值的情況下,其期望值才等于真實(shí)值.再有,策略迭代開始時(shí)V(S t+n) 的值都為初值(往往都被設(shè)為0),距離真實(shí)值較遠(yuǎn).所以在初期,MC 算法的更新量Gt ?V(S t) 是大于TD 算法的更新量.另外,對(duì)于使用步長(zhǎng)參數(shù) 1/n的MC 算法和使用固定步長(zhǎng)參數(shù)的TD 算法,它們步長(zhǎng)參數(shù)的不同也使得策略迭代初期MC 算法的收斂速率更快.

2 ATDMC 方法

本節(jié)將通過(guò)分析得出影響TD 算法收斂速率的因素,然后通過(guò)減少這些因素的影響來(lái)加快TD 算法的收斂速率.

2.1 TD 算法的收斂速率

任取一個(gè)狀態(tài)S t,將其n+1 次更新后的估計(jì)值記為Vn+1,策略π下該狀態(tài)的真實(shí)值記為vπ. 將V n+1值和真實(shí)值之間距離的平方的期望定義為誤差en+1,則:

顯然en+1減小到0 的速率即為TD 算法收斂的速率.將TD 算法的更新公式代入式(13),得

假定UTD的期望等于vπ,將式(14)展開得:

整理得:

進(jìn)一步,展開得:

式(17)中e0是由初值所確定的,而UTD的方差則是由具體的TD 算法所決定的.隨著α →0 且n →∞,en+1逐步變小,最后收斂到0.可見,收斂的速率是由步長(zhǎng)參數(shù)、初值和TD 算法本身的性質(zhì)三者共同決定的.在實(shí)際使用TD 算法時(shí),往往采用固定的步長(zhǎng)參數(shù),en+1變?yōu)橐粋€(gè)有上界的量.如果設(shè)置步長(zhǎng)參數(shù)較小時(shí),等式的第一項(xiàng)收斂到0 的速率較慢,第二項(xiàng)一直保持為一個(gè)很小的值,所以最終的收斂的效果是速率慢,但是很穩(wěn)定.而如果步長(zhǎng)參數(shù)設(shè)置較大時(shí),第一項(xiàng)會(huì)很快收斂,第二項(xiàng)的值對(duì)算法的收斂速率起主要的影響作用,表現(xiàn)為雖然收斂速率快,但是波動(dòng)程度大.這一點(diǎn)與調(diào)試步長(zhǎng)參數(shù)的過(guò)往經(jīng)驗(yàn)是一致的,只有當(dāng)步長(zhǎng)參數(shù)設(shè)置適中時(shí),算法的效果才能達(dá)到最優(yōu).

對(duì)于一個(gè)給定的策略和一個(gè)固定的步長(zhǎng)參數(shù)條件下,如果想要加速TD 算法,D[U TD] 對(duì)于給定TD 算法是無(wú)法改變的,那么只有減少e n.雖然e0是由初值確定的,但是e1,e2,···等都是可以減小的.

2.2 TD 算法的目標(biāo)

在第2.1 節(jié)中,論文假定UTD的期望等于vπ,而在策略迭代初期該條件是不滿足的.實(shí)際上,在一個(gè)給定策略下,一個(gè)情節(jié)中不同時(shí)間步的同一狀態(tài)的TD 算法的目標(biāo)UTD構(gòu)成了一個(gè)不穩(wěn)定的序列(A non-stationary series).即在收斂之前,U TD的期望值一直在變化,直至收斂后,UTD的期望才能達(dá)到穩(wěn)定狀態(tài).假設(shè)所有狀態(tài)初值都為0,獎(jiǎng)賞都為正時(shí),構(gòu)成的序列如圖1 所示,圖中的點(diǎn)是U TD的估計(jì)值,圖中的線是由UTD的期望構(gòu)成.這也說(shuō)明在策略迭代初期,各個(gè)狀態(tài)的值和UTD之間的距離較小.并且加上步長(zhǎng)參數(shù)的作用,使得初期的收斂速率較慢.但是MC 方法的目標(biāo)是一個(gè)穩(wěn)定的序列,其期望值始終等于vπ.如果采用MC 算法的目標(biāo)作為再次更新的目標(biāo)則可以減小e n,從而加速收斂.

圖1 由 UTD 構(gòu)成的不穩(wěn)定序列Fig.1 A non-stationary series

2.3 ATDMC 方法的推導(dǎo)過(guò)程

根據(jù)前面兩節(jié)的分析,TD 算法在策略迭代初期收斂速率慢的問(wèn)題可以通過(guò)減小e n來(lái)解決.而MC 方法的目標(biāo)在策略迭代初期相較于TD 算法的目標(biāo)距離真實(shí)值更近,可以借助其來(lái)減小en. 對(duì)此,在一般的GPI 中加入值改進(jìn)的步驟,使得e n減小.改進(jìn)后的GPI 如圖2 所示.具體的方式是在TD 算法更新完成后,再以MC 算法的目標(biāo)作為新目標(biāo)來(lái)更新.

圖2 改進(jìn)后的GPIFig.2 The improved GPI

為了再以MC 算法的目標(biāo)進(jìn)行更新,線性函數(shù)逼近的方式下,將損失函數(shù)定義為:

其中,w為經(jīng)過(guò)TD 算法更新后的權(quán)重向量.對(duì)損失函數(shù)求w的偏導(dǎo):

觀察第二個(gè)等號(hào)后面的式子,可知r1x1可以在時(shí)間步1 求出,相應(yīng)地r T?1(x1+x2+···+x T?1)可以在情節(jié)結(jié)束前一個(gè)時(shí)間步求出.再令P i則:

可見,使用均攤跡只需要保存兩個(gè)變量P i和M i,然后在各個(gè)時(shí)間步不停地更新這兩個(gè)值.最終ATDMC 方法的更新公式為:

另外,M0、N0、P0都為 0向量.β為步長(zhǎng)參數(shù).式(20)、(21)和(22)在TD 算法更新完權(quán)重向量后執(zhí)行,式(23)在情節(jié)結(jié)束后執(zhí)行.這樣并沒有改變?cè)璗D 算法的結(jié)構(gòu),也就不會(huì)改變?cè)诰€學(xué)習(xí)的方式.

在異策略學(xué)習(xí)中,由于目標(biāo)策略和行為策略不一致,需要采取重要性采樣方法來(lái)放大或縮小值函數(shù).只需要將式(22)改為

其中,ρi為重要性采樣因子.

3 實(shí)驗(yàn)及結(jié)果分析

本節(jié)將分別在同策略評(píng)估、異策略評(píng)估和控制三個(gè)方面進(jìn)行實(shí)驗(yàn),展示ATDMC 方法可以對(duì)多種TD 算法進(jìn)行加速收斂,以及原TD 算法的步長(zhǎng)參數(shù)α和ATDMC 方法的步長(zhǎng)參數(shù)β對(duì)加速效果的影響.其中,策略評(píng)估的實(shí)驗(yàn)側(cè)重覆蓋多種TD算法,而控制的實(shí)驗(yàn)則更多的體現(xiàn)步長(zhǎng)參數(shù)的影響.

3.1 同策略評(píng)估

博揚(yáng)鏈(Boyan chain)是強(qiáng)化學(xué)習(xí)中用于比較不同TD 算法性能的問(wèn)題[12].這個(gè)問(wèn)題中一共有13個(gè)狀態(tài).其中,狀態(tài)12 是開始狀態(tài),狀態(tài)0 是終止?fàn)顟B(tài).每個(gè)狀態(tài)都有兩個(gè)動(dòng)作(狀態(tài)1 兩個(gè)動(dòng)作都到達(dá)終止?fàn)顟B(tài)0),如圖3 所示.除了狀態(tài)1 到狀態(tài)0 的獎(jiǎng)賞是?2,其他收到的獎(jiǎng)賞都是?3.狀態(tài)12、8、4、0 的特征向量分別為[1,0,0,0]、[0,1,0,0]、[0,0,1,0]、[0,0,0,1].處于這些狀態(tài)之間的狀態(tài)的特征向量可以用插值法求得.例如,狀態(tài)11、10、9 的特征向量分別為[3/4,1/4,0,0]、[1/2,1/2,0,0]、[1/4,3/4,0,0].所要評(píng)估的策略設(shè)定為每個(gè)狀態(tài)的兩個(gè)動(dòng)作被執(zhí)行的概率相等.

圖3 博揚(yáng)鏈Fig.3 Boyan chain

為了覆蓋較多的TD 算法,用ATDMC 方法分別加速TD(0)、GTD[13]、GTD2 和TDC[14]算法.這4 種算法相比于其他的TD 算法(如LSTD、KTD和GPTD 等)收斂速率更快[15].另外,實(shí)驗(yàn)通過(guò)比較均方根誤差(Root mean square of er r or,RMSE)的減小速率來(lái)體現(xiàn)ATDMC 方法的加速效果.RMSE是衡量TD 算法求出的值和真實(shí)值之間誤差的常用指標(biāo).如果ATDMC 方法的RMSE 減小速率更快,則可以體現(xiàn)ATDMC 方法的加速效果.為了讓步長(zhǎng)參數(shù)的大小一致,原TD 算法和加速后的算法的步長(zhǎng)參數(shù)α都設(shè)為0.5.如果算法存在次級(jí)權(quán)重向量,那么其對(duì)應(yīng)的步長(zhǎng)參數(shù)也都設(shè)為0.25.ATDMC 方法的步長(zhǎng)參數(shù)β都為0.1.每個(gè)實(shí)驗(yàn)都是重復(fù)100 次取平均值,且折扣因子γ都為1,權(quán)重向量的初值都為 0 向量.

比較結(jié)果如圖4 所示.圖中實(shí)線對(duì)應(yīng)原TD 算法,虛線是加速后的效果.可見,雖然各個(gè)TD 算法收斂速率不盡相同,但是都得到了加速.另外,ATDMC 方法利用MC 算法目標(biāo)的無(wú)偏性質(zhì)進(jìn)行一次值改進(jìn)后,誤差就已經(jīng)顯著減少.

圖4 同策略評(píng)估Fig.4 On-policy estimation

3.2 異策略評(píng)估

本節(jié)是在11 狀態(tài)的隨機(jī)漫步問(wèn)題上做實(shí)驗(yàn),并在一般的隨機(jī)漫步問(wèn)題上進(jìn)行了修改[16],如圖5所示.這個(gè)問(wèn)題共有11 個(gè)狀態(tài),狀態(tài)1 是開始狀態(tài),狀態(tài)11 是終止?fàn)顟B(tài),每個(gè)狀態(tài)都有向左和向右兩個(gè)動(dòng)作,除了狀態(tài)1 的向左的動(dòng)作是到達(dá)自己外,其他的動(dòng)作都是到達(dá)相鄰狀態(tài).可以看出,由于向左和向右動(dòng)作的作用使得實(shí)驗(yàn)一個(gè)情節(jié)的時(shí)間步數(shù)可能會(huì)很長(zhǎng).而較長(zhǎng)的情節(jié)才能體現(xiàn)異策略評(píng)估算法的優(yōu)劣性.前一節(jié)中的博揚(yáng)鏈的情節(jié)最長(zhǎng)為12 步,最短為6 步,不再適用于異策略評(píng)估,所以換為隨機(jī)漫步問(wèn)題.只有到達(dá)終止?fàn)顟B(tài)11 才能獲得1 的獎(jiǎng)賞.其他所有的獎(jiǎng)賞都為0.特征向量是一個(gè)10維向量.狀態(tài)1 的特征向量是前1維√為后面為0.狀態(tài)2的特征向量是前2維為,后面為0,以此類推.狀態(tài)11 的特征向量為 0 向量.評(píng)估的目標(biāo)策略為采取向左的動(dòng)作概率為0.4,采取向右的動(dòng)作概率等于0.6.而行為策略采取向左和向右動(dòng)作的概率相等.

圖5 11 狀態(tài)的隨機(jī)漫步Fig.5 11-State random walk

資格跡是強(qiáng)化學(xué)習(xí)的重要方法[17?19].在異策略評(píng)估方面,TD 算法和資格跡相結(jié)合使得收斂速率和準(zhǔn)確度都得到了提升.為了證明使用資格跡加速后,ATDMC 方法仍然可以加速,實(shí)驗(yàn)采用了TD(0)和GTD 算法的資格跡版本:TD (λ)[20?21]、GTD(λ)[22].另外,為了進(jìn)一步覆蓋更多的TD 算法,又選取了另外兩種算法:HTD (λ)[23]和ETD (λ)[24?25].參數(shù)設(shè)置方面,λ都設(shè)為0.6,ATDMC 方法的步長(zhǎng)參數(shù)β都為0.001.其他參數(shù)與同策略評(píng)估設(shè)置一致.每個(gè)實(shí)驗(yàn)也同樣重復(fù)100 次取平均值.

比較的結(jié)果如圖6 所示.可見,異策略評(píng)估方面采用資格跡的TD 算法的收斂速率也都得到了加速.需要特別指出的是異策略評(píng)估算法中HTD 的收斂速率最快,但是犧牲了準(zhǔn)確度.ATDMC 方法在保證收斂速率不變的條件下,提高了HTD 算法的準(zhǔn)確度.

圖6 異策略評(píng)估Fig.6 Off-policy estimation

3.3 控制

山地車(Mountain car)和平衡桿(Cart pole)問(wèn)題是強(qiáng)化學(xué)習(xí)控制方面的經(jīng)典問(wèn)題,許多算法都是在這兩個(gè)問(wèn)題上進(jìn)行實(shí)驗(yàn).關(guān)于這兩個(gè)問(wèn)題的細(xì)節(jié)在許多文獻(xiàn)中有著詳細(xì)的描述.另外,選用這兩個(gè)問(wèn)題還因?yàn)檫@兩者的目標(biāo)剛好相反,山地車問(wèn)題的目標(biāo)是小車盡可能快地到達(dá)山頂,平衡桿問(wèn)題是盡可能久地保持桿子的平衡,一個(gè)是讓一個(gè)情節(jié)的時(shí)間步數(shù)盡可能的少,而另一個(gè)讓時(shí)間步數(shù)盡可能的多.

山地車問(wèn)題采用的是sarsa (λ) 算法[26]來(lái)解決.為了體現(xiàn)算法收斂速率的快慢,實(shí)驗(yàn)只關(guān)心前50個(gè)情節(jié)的時(shí)間步數(shù).前50 個(gè)情節(jié)的平均時(shí)間步數(shù)越短,說(shuō)明收斂速率越快.實(shí)驗(yàn)采用了瓦片編碼(Tile coding),選擇動(dòng)作的?-greedy 算法的參數(shù)?設(shè)為0.

為了展示相同步長(zhǎng)參數(shù)β和不同的α對(duì)加速效果的影響,第一個(gè)實(shí)驗(yàn)固定β=0.0001,而sarsa(λ)算法采取不同的步長(zhǎng)參數(shù)α,實(shí)驗(yàn)結(jié)果如圖7 所示.縱坐標(biāo)的步數(shù)是前50 個(gè)情節(jié)的時(shí)間步數(shù)的平均值.從圖中看出當(dāng)α較大時(shí),β設(shè)為0.0001 沒有加速,反而減慢了速率.當(dāng)然在α較大時(shí),sarsa (λ) 算法的效果也比較差,所以需要調(diào)整步長(zhǎng)參數(shù).當(dāng)α較小時(shí),雖然α不同但是都得到了加速.

圖7 山地車問(wèn)題 (β 固定)Fig.7 Mountain car(fixedβ)

接著,為了展現(xiàn)不同的β和同一α加速效果,α分別取了0.8/8、1/8、1.4/8 和2/8.結(jié)果如圖8 所式.當(dāng)α較小時(shí),隨著β逐漸變大,加速效果由逐漸變好再逐漸變壞.當(dāng)α較大時(shí),ATDMC 方法的并沒有加速效果.這一點(diǎn)與其他強(qiáng)化學(xué)習(xí)算法一致,過(guò)大的步長(zhǎng)參數(shù)將會(huì)使算法效果變差.

圖8 山地車問(wèn)題 (α 固定)Fig.8 Mountain car(fixedα)

第二個(gè)實(shí)驗(yàn)是平衡桿問(wèn)題.平衡桿的每個(gè)情節(jié)的步長(zhǎng)最大值為200,當(dāng)連續(xù)100 個(gè)情節(jié)的平均步長(zhǎng)大于195 視為該問(wèn)題得到解決.易知,解決問(wèn)題所花費(fèi)的情節(jié)數(shù)越短說(shuō)明算法收斂得越快.實(shí)驗(yàn)設(shè)計(jì)和山地車問(wèn)題是一致的,但是采用的是一步sarsa 算法,選擇動(dòng)作的?-greedy 算法的參數(shù)?設(shè)為0.08.首先也是比較相同的β和不同的α的對(duì)加速效果的影響,固定β為0.0005.實(shí)驗(yàn)結(jié)果如圖9 所示.接著也比較不同β和相同α的影響.α分別等于0.2/16、0.4/16、0.6/16 和0.8/16.實(shí)驗(yàn)結(jié)果如圖10所示.圖中縱座標(biāo)是總共進(jìn)行的情節(jié)數(shù),其中最后100 個(gè)情節(jié)是驗(yàn)證問(wèn)題是否解決,前面的情節(jié)是學(xué)習(xí)花費(fèi)的情節(jié).和山地車問(wèn)題的實(shí)驗(yàn)結(jié)果相比,雖然實(shí)驗(yàn)內(nèi)容不同,但是加速效果類似.

圖9 平衡桿問(wèn)題 (β 固定)Fig.9 Cart pole(fixedβ)

圖10 平衡桿問(wèn)題 (α 固定)Fig.10 Cart pole(fixedα)

從這兩個(gè)實(shí)驗(yàn)可以看出在TD 算法步長(zhǎng)參數(shù)α過(guò)大時(shí),ATDMC 方法并沒有加速效果.而當(dāng)步長(zhǎng)參數(shù)α較小時(shí),可以實(shí)現(xiàn)不同程度的加速,但是還沒有達(dá)到最好效果.只有當(dāng)步長(zhǎng)參數(shù)α適中時(shí),ATDMC 方法的步長(zhǎng)參數(shù)β也適中時(shí),才能達(dá)到算法的最好效果.

4 結(jié)論和后續(xù)工作方向

針對(duì)加速特定TD 算法收斂速率的方法匱乏的問(wèn)題,本文提出利用MC 算法無(wú)偏的性質(zhì)來(lái)加速TD算法收斂的ATDMC 方法.通過(guò)分析TD 算法的收斂速率得出可以通過(guò)減小e1,e2,···來(lái)加速收斂,而MC 算法的目標(biāo)可以在學(xué)習(xí)初期減小這些值,進(jìn)一步推導(dǎo)得出了最終的方法.從推導(dǎo)過(guò)程可知,加速的實(shí)現(xiàn)并不需要改變?cè)璗D 算法,也即TD 算法的在線實(shí)現(xiàn)的方式不會(huì)被改變.同時(shí),只引入了3 個(gè)額外的變量,并沒有增加算法的空間復(fù)雜度.從實(shí)驗(yàn)結(jié)果可以看出,本文提出的方法可以有效地加速各類TD 算法,恰當(dāng)?shù)牟介L(zhǎng)參數(shù)使得算法達(dá)到最優(yōu)的加速效果.

另外,需要指出的是ATDMC 方法只適用于情節(jié)式任務(wù).對(duì)于連續(xù)任務(wù),有兩種解決方案:一種是引入可變的折扣因子γ,在恰當(dāng)?shù)臅r(shí)間步設(shè)置γ等于0(相當(dāng)于主動(dòng)結(jié)束任務(wù)),從而轉(zhuǎn)換為一個(gè)情節(jié)任務(wù),但并不影響對(duì)應(yīng)MDP 的流程;另外一種是采用平均獎(jiǎng)賞設(shè)定(Average-reward setting),MC方法的目標(biāo)需要重新用獎(jiǎng)賞和獎(jiǎng)賞的平均值的差值來(lái)定義.更多的細(xì)節(jié)需要進(jìn)一步研究.