劉曉峰,劉智斌,董兆安

(1.曲阜師范大學(xué) 圖書館,山東 日照 276826;2.曲阜師范大學(xué) 計(jì)算機(jī)學(xué)院,山東 日照 276826)

0 引 言

強(qiáng)化學(xué)習(xí)[1-2]是機(jī)器學(xué)習(xí)的一個(gè)重要分支,它的基本思想來源于心理學(xué)和生物學(xué),在計(jì)算機(jī)科學(xué)、決策理論以及控制工程等領(lǐng)域得到了普遍重視,其應(yīng)用范圍也越來越廣泛。采用強(qiáng)化學(xué)習(xí)方法,不需要進(jìn)行顯式編程,Agent在一定的環(huán)境中,其每一步都收到一個(gè)報(bào)酬值,強(qiáng)化學(xué)習(xí)方法試圖通過學(xué)習(xí)得到報(bào)酬值最大的策略。然而采用傳統(tǒng)的強(qiáng)化學(xué)習(xí)算法,收斂速度是很慢的,例如：從目標(biāo)狀態(tài)將報(bào)酬值傳遞到較遠(yuǎn)的狀態(tài)需要無數(shù)次的迭代。對(duì)于大型狀態(tài)空間,由于存在“維數(shù)災(zāi)難”,使采用強(qiáng)化學(xué)習(xí)的方法進(jìn)行求解幾乎成為不可能。為了提高學(xué)習(xí)效率,人們不斷探索各種方法。Sutton等[3]提出了Option方法,他們將狀態(tài)空間分解為若干個(gè)子集,采用分而治之的策略進(jìn)行求解。Parr R[4]提出了HAM方法,他將每個(gè)子任務(wù)抽象為一個(gè)建立在MDP上的隨機(jī)有限狀態(tài)機(jī)。Bernhard Hengst[5]提出了HEXQ方法,他利用時(shí)域和狀態(tài)抽象的方法生成小規(guī)模的狀態(tài)變量子空間。Thomas G. Dietterich[6]提出了MAXQ方法,這種方法則將動(dòng)作序列或動(dòng)作集進(jìn)行分組,將強(qiáng)化學(xué)習(xí)中的單步?jīng)Q策擴(kuò)展到多步?jīng)Q策,減少了決策次數(shù)。Hashemzadeh等人[7]提出將具有相似策略的狀態(tài)分類到同一個(gè)集群中,并且通過這種定位,Agent可以更多地利用子空間學(xué)習(xí)的泛化,有效地提高了學(xué)習(xí)效率。

以上方法將大問題劃分為較小問題來解決,同時(shí)也使簡(jiǎn)單問題復(fù)雜化。強(qiáng)化學(xué)習(xí)中Agent的學(xué)習(xí)是盲目的,沒有任何先驗(yàn)知識(shí),學(xué)習(xí)過程全靠其不斷摸索,這樣勢(shì)必造成學(xué)習(xí)效率較低,難以應(yīng)用到實(shí)際問題中。人們開始用間接知識(shí)指導(dǎo)Agent的探索行為,減小問題的搜索域,從而提高學(xué)習(xí)效率。Peter Dayan等[8]提出了Feudal方法,簡(jiǎn)單地將一個(gè)迷宮問題由下往上進(jìn)行聚合,上層作為下層的管理者,這樣Agent的學(xué)習(xí)有了指導(dǎo),效率有了提高。Shi等人[9]提出了一種高效的模糊規(guī)則分層強(qiáng)化學(xué)習(xí)算法(HFR),這是一種將人的先驗(yàn)知識(shí)與分層策略網(wǎng)絡(luò)相結(jié)合的新框架,可以有效地加速策略的優(yōu)化。Cai等人[10]增強(qiáng)了啟發(fā)式算法的能力,以貪婪地改進(jìn)RL生成的現(xiàn)有初始解,并展示了新穎的結(jié)果,其中RL能夠利用啟發(fā)式的性能作為學(xué)習(xí)信號(hào)來進(jìn)行更好的初始化。

在不具有先驗(yàn)知識(shí)或先驗(yàn)知識(shí)不夠明晰的情況下,還要靠Agent自我學(xué)習(xí)。其實(shí),Agent在每一輪學(xué)習(xí)過程中也是在不停地獲得經(jīng)驗(yàn)知識(shí),希望Agent在不具有先驗(yàn)知識(shí)或擁有先驗(yàn)知識(shí)較少時(shí),也能利用自身學(xué)習(xí)的經(jīng)驗(yàn)提高效率。該文提出一種基于記憶啟發(fā)的強(qiáng)化學(xué)習(xí)方法,不需要植入先驗(yàn)知識(shí),自主Agent能將學(xué)習(xí)中獲得的知識(shí)作為啟發(fā)知識(shí)應(yīng)用到以后的學(xué)習(xí)中,利用啟發(fā)式Shaping回報(bào)函數(shù)改造Q學(xué)習(xí)方法,使Agent在一定程度上脫離盲目探索,以提高效率。

1 強(qiáng)化學(xué)習(xí)機(jī)制

強(qiáng)化學(xué)習(xí)與監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)不同,它強(qiáng)調(diào)在環(huán)境中交互學(xué)習(xí),通過在學(xué)習(xí)過程中取得的評(píng)價(jià)性的反饋信號(hào)作為回報(bào),在學(xué)習(xí)過程中,通過最大化其積累回報(bào),選取最優(yōu)行為[11]。

Qπ(s,a)=E{rt+1+γrt+2+γ2rt+3+…

|st=s,at=s,π}

(1)

其中,0<γ<1。

進(jìn)而求得狀態(tài)行為對(duì)的Q值為：

(2)

對(duì)于狀態(tài)s,定義：

若環(huán)境模型和轉(zhuǎn)移概率為已知,上述問題歸結(jié)為動(dòng)態(tài)規(guī)劃問題。然而,在實(shí)際應(yīng)用中,環(huán)境模型和轉(zhuǎn)移概率往往不可知。針對(duì)這個(gè)問題,Watins[14]提出了Q學(xué)習(xí)算法同時(shí)證明了它的收斂性。表示為：

Q(s,a))

(4)

其中,0<γ<1。

Agent在每次迭代中更新Q(s,a)值,在多次迭代后Q(s,a)值收斂。

有了上述關(guān)于Q值的定義,很容易通過策略迭代得到V*值和最優(yōu)策略π*,表示如下：

(5)

(6)

2 啟發(fā)式Shaping回報(bào)函數(shù)

Agent在學(xué)習(xí)中從環(huán)境中獲得報(bào)酬值,以更新當(dāng)前的Q值或V值。在Agent學(xué)習(xí)過程中,提供附加的報(bào)酬值將會(huì)有效地提高學(xué)習(xí)性能,這種思想被稱為Shaping[15]。若提供一個(gè)合適的啟發(fā)回報(bào)函數(shù)：F(s,a,s'),則式(4)改寫為：

Q(st+1,at+1)=Q(st,at)+α(r+F(s,a,s')+

(7)

一個(gè)學(xué)習(xí)策略的選擇就從一個(gè)馬爾可夫決策過程M=(S,A,T,γ,R)轉(zhuǎn)換為在M'=(S,A,T,γ,R')中學(xué)習(xí)優(yōu)化策略。其中：R'=R+F為新定義的報(bào)酬值。假如在馬爾可夫決策過程M=(S,A,T,γ,R),Agent從狀態(tài)s到s'從環(huán)境得到報(bào)酬為R(s,a,s'),那么在新的馬爾可夫決策過程M'=(S,A,T,γ,R'),Agent收到的報(bào)酬為：R(s,a,s')+F(s,a,s')。

定義1：在馬爾可夫決策過程中,已知S,A,γ,給定一個(gè)Shaping回報(bào)函數(shù)F：S×A×S|→R。令F(s,a,s')=γφ(s')-φ(s),其中：φ(s)和φ(s')分別為狀態(tài)s和狀態(tài)s'下的勢(shì)場(chǎng)函數(shù)。

推論1：在一個(gè)Shaping回報(bào)函數(shù)啟發(fā)的馬爾可夫決策過程中,M=(S,A,T,γ,R)轉(zhuǎn)化為M'(S,A,T,γ,R'),其中：γ'(s,a,s')=r(s,a,s')+F(s,a,s')。Shaping回報(bào)函數(shù)為：F：S×A×S|→R。

定理1：如果F是一個(gè)基于勢(shì)場(chǎng)函數(shù)的Shaping函數(shù),F(s,a,s')=γφ(s')-φ(s),則在M'(S,A,T,γ,R')中的優(yōu)化策略在M=(S,A,T,γ,R)中也必為優(yōu)化策略。

證明：對(duì)于M有：

-φ(s)=

(8)

定理2：如果F是一個(gè)基于勢(shì)場(chǎng)函數(shù)的Shaping函數(shù),F(s,a,s')=γφ(s')-φ(s),則在M=(S,A,T,γ,R)中的優(yōu)化策略在M'(S,A,T,γ,R')中也必為優(yōu)化策略。

證明思路與定理1類似。

3 算法實(shí)現(xiàn)

標(biāo)準(zhǔn)的強(qiáng)化學(xué)習(xí)方法都是通過探索-利用過程以發(fā)現(xiàn)搜索目標(biāo),然而在找到目標(biāo)后,又開始了新的探索過程,使得原來獲得的經(jīng)驗(yàn)結(jié)果大部分被遺忘。

對(duì)于Agent,給定一個(gè)初始狀態(tài),讓它不斷學(xué)習(xí),當(dāng)它到達(dá)目標(biāo)后,記下目標(biāo)的位置goal,然后圍繞goal形成一個(gè)勢(shì)能場(chǎng),為以后的Agent學(xué)習(xí)提供了一個(gè)啟發(fā)勢(shì)場(chǎng)函數(shù)。勢(shì)場(chǎng)函數(shù)定義為：

φ(s)=λh(s,goal)

(9)

其中,s為當(dāng)前狀態(tài),λ為啟發(fā)強(qiáng)度因子,勢(shì)場(chǎng)函數(shù)形式視具體問題而定。

算法描述如下：

初始化Q(s,a);

從狀態(tài)s開始搜索,經(jīng)過一個(gè)episode(輪),直到發(fā)現(xiàn)目標(biāo)goal,記錄下goal的狀態(tài);

for each episode

{

選擇狀態(tài)s?goal;

While(沒有滿足終止條件)

{

計(jì)算φ(s);

從當(dāng)前狀態(tài)s下按某種策略(如：ε-greedy)選擇行為a;

執(zhí)行行為a,獲得報(bào)酬值rt,進(jìn)入到下一狀態(tài)s';

計(jì)算φ(s');

根據(jù)收斂情況,采取某種方法(如：模擬退火法)選擇學(xué)習(xí)率α;

計(jì)算F(s,a,s');

更新Q值：

}

}

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境

算法采用路徑規(guī)劃問題作為一個(gè)算例(如圖1所示),實(shí)驗(yàn)環(huán)境采用一個(gè)30×30的網(wǎng)格,圖中S為Agent所處的初始位置,G為目標(biāo)點(diǎn)。圖中白色的部分為Agent的自由活動(dòng)區(qū)域,灰色的區(qū)域?yàn)檎系K物,四周為墻壁,Agent不能穿過墻壁也不能穿過障礙物。假定Agent能感知自身所處的位置,但它起初對(duì)環(huán)境的一無所知。該問題是讓Agent以盡可能短的時(shí)間,搜索到一條通往G點(diǎn)的最短路徑。

圖1 一個(gè)路徑規(guī)劃實(shí)例

顯然,該問題是無法用Dijkstra或A*等算法解決的,因?yàn)閷?duì)Agent來說環(huán)境是未知的。Agent通過不斷地學(xué)習(xí),探索一條合適的通向G點(diǎn)的優(yōu)化路徑。

采用Q學(xué)習(xí)方法,Agent在任意狀態(tài)s可選的行為集合為：{向上,向下,向左,向右}。

實(shí)驗(yàn)參數(shù)設(shè)置為：初始學(xué)習(xí)率α=0.1,折扣因子γ=0.95,采用ε-greedy方法選擇優(yōu)化行為,ε=0.1。

Agent被盲目地置于任何合法位置而開始學(xué)習(xí),Agent的測(cè)試源坐標(biāo)定義為[2 2],目標(biāo)坐標(biāo)定義為[24 20]。

報(bào)酬值設(shè)定為：若Agent到達(dá)目標(biāo)G,將從環(huán)境獲得100的獎(jiǎng)賞;若Agent撞到墻壁上將退回到原處,獎(jiǎng)懲值為0;Agent每移動(dòng)一步將獲得-1的懲罰。

4.2 采用標(biāo)準(zhǔn)Q學(xué)習(xí)的學(xué)習(xí)性能

采用標(biāo)準(zhǔn)的Q學(xué)習(xí)算法進(jìn)行訓(xùn)練。在每輪學(xué)習(xí)中,設(shè)置Agent的搜索步數(shù)上限為3 000,超過3 000步還找不到目標(biāo)點(diǎn),本輪搜索就失敗,開始新一輪的搜索。從圖2發(fā)現(xiàn),隨著不斷地學(xué)習(xí),每一輪的學(xué)習(xí)時(shí)間在逐步縮短。當(dāng)Agent學(xué)習(xí)了599輪,測(cè)試從S點(diǎn)到G點(diǎn)的學(xué)習(xí)結(jié)果如圖3所示,可見Agent從測(cè)試點(diǎn)出發(fā)能搜索到目標(biāo)點(diǎn),但是仍然走了若干冗余步,獲得的路徑還不是最優(yōu)的,若想得到最優(yōu)結(jié)果還需繼續(xù)學(xué)習(xí)。

圖2 Q學(xué)習(xí)每輪步數(shù)

圖3 用Q學(xué)習(xí)實(shí)現(xiàn)路徑規(guī)劃

4.3 基于記憶啟發(fā)的學(xué)習(xí)性能

Agent在學(xué)習(xí)過程中搜索到目標(biāo),記下目標(biāo)點(diǎn)位置,以此為依據(jù)進(jìn)行啟發(fā)搜索,啟發(fā)勢(shì)場(chǎng)函數(shù)為：

φ(s)=

(10)

其中,λ為啟發(fā)因子,λ>0。

Shaping函數(shù)為：

F(s,a,s')=γφ(s')-φ(s)

(11)

其中,γ為折扣因子,取值0.95。

在實(shí)驗(yàn)中,令λ=0.3,實(shí)驗(yàn)結(jié)果如圖4、圖5所示,設(shè)定學(xué)習(xí)輪數(shù)為300。由結(jié)果可見,因?yàn)榧尤肓藛l(fā)函數(shù),收斂速度較沒有啟發(fā)的Q學(xué)習(xí)算法快了很多,但是還是有冗余步,分析原因?yàn)椋翰捎迷撐亩x的勢(shì)能場(chǎng)函數(shù),離目標(biāo)越遠(yuǎn),Agent可選的幾個(gè)行為所得的啟發(fā)回報(bào)值F區(qū)別越不明顯,其學(xué)習(xí)效果與沒有啟發(fā)的Q學(xué)習(xí)越接近;反正,離目標(biāo)點(diǎn)越近,啟發(fā)效果越明顯。

圖4 啟發(fā)Q學(xué)習(xí)(λ=0.3)每輪步數(shù)

圖5 用啟發(fā)Q學(xué)習(xí)(λ=0.3)實(shí)現(xiàn)路徑規(guī)劃

為了提高啟發(fā)效果,在實(shí)驗(yàn)中,令λ=0.8,實(shí)驗(yàn)結(jié)果如圖6、圖7所示,學(xué)習(xí)輪數(shù)在75左右,算法就能達(dá)到收斂,并且Agent在測(cè)試點(diǎn)能搜索到最優(yōu)路徑。由結(jié)果可見,適當(dāng)提高啟發(fā)因子,有利于Agent快速找到目標(biāo)。

圖6 啟發(fā)Q學(xué)習(xí)(λ=0.8)每輪步數(shù)

圖7 用啟發(fā)Q學(xué)習(xí)(λ=0.8)實(shí)現(xiàn)路徑規(guī)劃

令λ=1.6,做了同樣的實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如圖8、圖9所示。由結(jié)果可見,Agent能很快發(fā)現(xiàn)最優(yōu)路徑,但是也發(fā)現(xiàn)在學(xué)習(xí)中出現(xiàn)了一些“死點(diǎn)”,Agent一旦陷入到這些點(diǎn)往往不能自拔,當(dāng)學(xué)習(xí)步數(shù)達(dá)到3 000,當(dāng)前輪就被強(qiáng)制終止,這種現(xiàn)象是由于“過啟發(fā)”造成的。現(xiàn)分析如下：

圖8 啟發(fā)Q學(xué)習(xí)(λ=1.6)每輪步數(shù)

圖9 用啟發(fā)Q學(xué)習(xí)(λ=1.6)實(shí)現(xiàn)路徑規(guī)劃

在F(s,a,s')=γφ(s')-φ(s)中,若Agent從某s點(diǎn)執(zhí)行行為a碰壁后又回到s點(diǎn),也就是s=s',于是有：F(s,a,s')=F(s,a,s)=γφ(s)-φ(s)=φ(s)(γ-1),又因?yàn)棣?s)<0,γ-1<0,所以F(s,a,s)>0。而λ越大,則啟發(fā)值F也就越大,造成Q(s,a)越大,并不斷積累。以后Agent在狀態(tài)s下,選擇行為a的概率將不斷加大。在以后的學(xué)習(xí)中,這個(gè)Q(s,a)會(huì)把值向周圍狀態(tài)擴(kuò)散,于是s狀態(tài)就變成一個(gè)“死點(diǎn)”或偽目標(biāo),致使Agent走到這個(gè)區(qū)域便陷入并無法逃脫。針對(duì)這個(gè)問題,該文提出一種修改回饋報(bào)酬的方法,檢測(cè)Agent的行為和新的狀態(tài),一旦發(fā)現(xiàn)Agent陷入死點(diǎn),就對(duì)這個(gè)狀態(tài)-行為對(duì)的Q值增加一個(gè)懲罰值,懲罰值的大小視Agent陷入的深度而定,這樣隨著Agent不斷學(xué)習(xí),會(huì)跳出這個(gè)死點(diǎn)到別處進(jìn)行探索。經(jīng)這種方法處理后,實(shí)驗(yàn)表明：死點(diǎn)被較理想地消除了。

通過以上分析可以看出,應(yīng)選擇合適的λ值。λ值太小,啟發(fā)效果不明顯;啟發(fā)太大,易產(chǎn)生死點(diǎn)。

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

無須先驗(yàn)知識(shí)為指導(dǎo),Agent在發(fā)現(xiàn)目標(biāo)后,基于目標(biāo)位置,再進(jìn)一步搜索優(yōu)化策略,這樣Agent的搜索將不再盲目。該文構(gòu)造了一個(gè)基于勢(shì)能場(chǎng)的啟發(fā)函數(shù),利用Shaping回報(bào)函數(shù),以路徑規(guī)劃問題作為一個(gè)算例,證明基于記憶啟發(fā)的強(qiáng)化學(xué)習(xí)算法能大大提高學(xué)習(xí)效率。

針對(duì)不同的問題,勢(shì)能場(chǎng)啟發(fā)函數(shù)可以有多種不同的構(gòu)造方法,相應(yīng)啟發(fā)因子的選取也是一個(gè)需要進(jìn)一步討論的問題。另外,Agent在搜索中除了以目標(biāo)位置作為啟發(fā),在其學(xué)習(xí)過程中所得到的過程知識(shí)也可以作為啟發(fā)知識(shí)加入到以后的學(xué)習(xí)過程中,這也是本課題需要繼續(xù)研究的問題。在多Agent的環(huán)境中,Agent可以利用自己學(xué)習(xí)到的知識(shí),也應(yīng)該能利用其它Agent所學(xué)到的知識(shí)。該文提出的方法可以應(yīng)用到許多領(lǐng)域[16],比如路由問題、資源分配、搜索問題、web服務(wù)組合、數(shù)據(jù)挖掘、機(jī)器人以及網(wǎng)絡(luò)拓?fù)鋬?yōu)化等,都有望得到較好的結(jié)果。