基于記憶啟發的強化學習方法研究

劉曉峰,劉智斌,董兆安

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

0 引 言

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

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

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

1 強化學習機制

強化學習與監督學習和無監督學習不同,它強調在環境中交互學習,通過在學習過程中取得的評價性的反饋信號作為回報,在學習過程中,通過最大化其積累回報,選取最優行為[11]。

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

|st=s,at=s,π}

(1)

其中,0<γ<1。

進而求得狀態行為對的Q值為：

(2)

對于狀態s,定義：

若環境模型和轉移概率為已知,上述問題歸結為動態規劃問題。然而,在實際應用中,環境模型和轉移概率往往不可知。針對這個問題,Watins[14]提出了Q學習算法同時證明了它的收斂性。表示為：

Q(s,a))

(4)

其中,0<γ<1。

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

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

(5)

(6)

2 啟發式Shaping回報函數

Agent在學習中從環境中獲得報酬值,以更新當前的Q值或V值。在Agent學習過程中,提供附加的報酬值將會有效地提高學習性能,這種思想被稱為Shaping[15]。若提供一個合適的啟發回報函數：F(s,a,s'),則式(4)改寫為：

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

(7)

一個學習策略的選擇就從一個馬爾可夫決策過程M=(S,A,T,γ,R)轉換為在M'=(S,A,T,γ,R')中學習優化策略。其中：R'=R+F為新定義的報酬值。假如在馬爾可夫決策過程M=(S,A,T,γ,R),Agent從狀態s到s'從環境得到報酬為R(s,a,s'),那么在新的馬爾可夫決策過程M'=(S,A,T,γ,R'),Agent收到的報酬為：R(s,a,s')+F(s,a,s')。

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

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

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

證明：對于M有：

-φ(s)=

(8)

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

證明思路與定理1類似。

3 算法實現

標準的強化學習方法都是通過探索-利用過程以發現搜索目標,然而在找到目標后,又開始了新的探索過程,使得原來獲得的經驗結果大部分被遺忘。

對于Agent,給定一個初始狀態,讓它不斷學習,當它到達目標后,記下目標的位置goal,然后圍繞goal形成一個勢能場,為以后的Agent學習提供了一個啟發勢場函數。勢場函數定義為：

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

(9)

其中,s為當前狀態,λ為啟發強度因子,勢場函數形式視具體問題而定。

算法描述如下：

初始化Q(s,a);

從狀態s開始搜索,經過一個episode(輪),直到發現目標goal,記錄下goal的狀態;

for each episode

{

選擇狀態s?goal;

While(沒有滿足終止條件)

{

計算φ(s);

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

執行行為a,獲得報酬值rt,進入到下一狀態s';

計算φ(s');

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

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

更新Q值：

}

}

4 實驗與結果分析

4.1 實驗環境

算法采用路徑規劃問題作為一個算例(如圖1所示),實驗環境采用一個30×30的網格,圖中S為Agent所處的初始位置,G為目標點。圖中白色的部分為Agent的自由活動區域,灰色的區域為障礙物,四周為墻壁,Agent不能穿過墻壁也不能穿過障礙物。假定Agent能感知自身所處的位置,但它起初對環境的一無所知。該問題是讓Agent以盡可能短的時間,搜索到一條通往G點的最短路徑。

圖1 一個路徑規劃實例

顯然,該問題是無法用Dijkstra或A*等算法解決的,因為對Agent來說環境是未知的。Agent通過不斷地學習,探索一條合適的通向G點的優化路徑。

采用Q學習方法,Agent在任意狀態s可選的行為集合為：{向上,向下,向左,向右}。

實驗參數設置為：初始學習率α=0.1,折扣因子γ=0.95,采用ε-greedy方法選擇優化行為,ε=0.1。

Agent被盲目地置于任何合法位置而開始學習,Agent的測試源坐標定義為[2 2],目標坐標定義為[24 20]。

報酬值設定為：若Agent到達目標G,將從環境獲得100的獎賞;若Agent撞到墻壁上將退回到原處,獎懲值為0;Agent每移動一步將獲得-1的懲罰。

4.2 采用標準Q學習的學習性能

采用標準的Q學習算法進行訓練。在每輪學習中,設置Agent的搜索步數上限為3 000,超過3 000步還找不到目標點,本輪搜索就失敗,開始新一輪的搜索。從圖2發現,隨著不斷地學習,每一輪的學習時間在逐步縮短。當Agent學習了599輪,測試從S點到G點的學習結果如圖3所示,可見Agent從測試點出發能搜索到目標點,但是仍然走了若干冗余步,獲得的路徑還不是最優的,若想得到最優結果還需繼續學習。

圖2 Q學習每輪步數

圖3 用Q學習實現路徑規劃

4.3 基于記憶啟發的學習性能

Agent在學習過程中搜索到目標,記下目標點位置,以此為依據進行啟發搜索,啟發勢場函數為：

φ(s)=

(10)

其中,λ為啟發因子,λ>0。

Shaping函數為：

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

(11)

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

在實驗中,令λ=0.3,實驗結果如圖4、圖5所示,設定學習輪數為300。由結果可見,因為加入了啟發函數,收斂速度較沒有啟發的Q學習算法快了很多,但是還是有冗余步,分析原因為：采用該文定義的勢能場函數,離目標越遠,Agent可選的幾個行為所得的啟發回報值F區別越不明顯,其學習效果與沒有啟發的Q學習越接近;反正,離目標點越近,啟發效果越明顯。

圖4 啟發Q學習(λ=0.3)每輪步數

圖5 用啟發Q學習(λ=0.3)實現路徑規劃

為了提高啟發效果,在實驗中,令λ=0.8,實驗結果如圖6、圖7所示,學習輪數在75左右,算法就能達到收斂,并且Agent在測試點能搜索到最優路徑。由結果可見,適當提高啟發因子,有利于Agent快速找到目標。

圖6 啟發Q學習(λ=0.8)每輪步數

圖7 用啟發Q學習(λ=0.8)實現路徑規劃

令λ=1.6,做了同樣的實驗,實驗結果如圖8、圖9所示。由結果可見,Agent能很快發現最優路徑,但是也發現在學習中出現了一些“死點”,Agent一旦陷入到這些點往往不能自拔,當學習步數達到3 000,當前輪就被強制終止,這種現象是由于“過啟發”造成的。現分析如下：

圖8 啟發Q學習(λ=1.6)每輪步數

圖9 用啟發Q學習(λ=1.6)實現路徑規劃

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

通過以上分析可以看出,應選擇合適的λ值。λ值太小,啟發效果不明顯;啟發太大,易產生死點。

5 結束語

無須先驗知識為指導,Agent在發現目標后,基于目標位置,再進一步搜索優化策略,這樣Agent的搜索將不再盲目。該文構造了一個基于勢能場的啟發函數,利用Shaping回報函數,以路徑規劃問題作為一個算例,證明基于記憶啟發的強化學習算法能大大提高學習效率。

針對不同的問題,勢能場啟發函數可以有多種不同的構造方法,相應啟發因子的選取也是一個需要進一步討論的問題。另外,Agent在搜索中除了以目標位置作為啟發,在其學習過程中所得到的過程知識也可以作為啟發知識加入到以后的學習過程中,這也是本課題需要繼續研究的問題。在多Agent的環境中,Agent可以利用自己學習到的知識,也應該能利用其它Agent所學到的知識。該文提出的方法可以應用到許多領域[16],比如路由問題、資源分配、搜索問題、web服務組合、數據挖掘、機器人以及網絡拓撲優化等,都有望得到較好的結果。