馬朋委　潘地林

(安徽理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院　淮南　232001)

?

基于啟發(fā)函數(shù)改進(jìn)的SARSA(λ)算法*

馬朋委潘地林

(安徽理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院淮南232001)

摘要強(qiáng)化學(xué)習(xí)是一種重要的機(jī)器學(xué)習(xí)方法,在機(jī)器人路徑規(guī)劃,智能控制等許多決策問(wèn)題中取得了成功的應(yīng)用,已經(jīng)成為機(jī)器學(xué)習(xí)研究的一個(gè)重要分支。針對(duì)強(qiáng)化學(xué)習(xí)存在著的收斂慢,學(xué)習(xí)知識(shí)慢,探索與利用平衡等問(wèn)題,論文對(duì)SARSA(λ)算法提出了一種改進(jìn),改進(jìn)的方法借助經(jīng)驗(yàn)知識(shí)從環(huán)境特征中提出一個(gè)用于策略擇優(yōu)和優(yōu)化回報(bào)函數(shù)的啟發(fā)函數(shù),以此來(lái)加速算法的收斂速度。通過(guò)仿真對(duì)比,論文提出改進(jìn)算法具有比SARSA(λ)更快的獎(jiǎng)賞反饋,表明了該算法在知識(shí)學(xué)習(xí)方面的有效性。

關(guān)鍵詞強(qiáng)化學(xué)習(xí); SARSA(λ); 啟發(fā)函數(shù); 評(píng)估學(xué)習(xí)

Class NumberTP301.6

1引言

20世紀(jì)90年代強(qiáng)化學(xué)習(xí)通過(guò)與運(yùn)籌學(xué)、控制理論的交叉結(jié)合,在控制理論和算法方面取得若干突破性的研究成果,奠定了強(qiáng)化學(xué)習(xí)的理論基礎(chǔ),并在智能控制、機(jī)器人系統(tǒng)規(guī)及分析預(yù)測(cè)等序貫決策中取得了成功的應(yīng)用[1～2]。強(qiáng)化學(xué)習(xí)是一個(gè)試錯(cuò)學(xué)習(xí)的過(guò)程,目的是使Agent從環(huán)境中獲得的累積獎(jiǎng)賞值最大。Agent在環(huán)境中執(zhí)行一個(gè)動(dòng)作,到達(dá)下一個(gè)狀態(tài),同時(shí)給予Agent一個(gè)強(qiáng)化信號(hào)[3](獎(jiǎng)勵(lì)或懲罰),Agent借助環(huán)境給予的強(qiáng)化新號(hào)來(lái)對(duì)原有的策略進(jìn)行改進(jìn),最終目的是最大化累積獎(jiǎng)賞值。

強(qiáng)化學(xué)習(xí)大部分都是以馬爾科夫決策過(guò)程(Markov Decision Process)為基礎(chǔ)。馬爾科夫決策過(guò)程借助四元組(S,A,P,r)來(lái)描述。S為環(huán)境狀態(tài)空間,A為動(dòng)作空間,P(s,a,s′)為狀態(tài)轉(zhuǎn)移概率,r為立即回報(bào)函數(shù)。在馬爾科夫決策過(guò)程中,Agent是通過(guò)一個(gè)決策函數(shù)(即策略)來(lái)選擇動(dòng)作的,常用π表示策略。在定義了策略后對(duì)應(yīng)狀態(tài)-動(dòng)作值函數(shù)為Qπ(s,a),Qπ(s,a)表示在狀態(tài)s下根據(jù)策略π執(zhí)行動(dòng)作a的期望值如式(1):

(1)

最優(yōu)動(dòng)作值函數(shù)Q*(s,a)的定義為式(2):

Q*(s,a)=maxπQπ(s,a)

(2)

最優(yōu)策略π*是使得Agent在每一個(gè)狀態(tài)下均能獲得最大值的策略如式(3):

(3)

一些強(qiáng)化學(xué)習(xí)算法已經(jīng)在理論和應(yīng)用方面取得了重大的成功Q_learning[4],TD(λ)[5],SARSA[6]。本文借助將人的經(jīng)驗(yàn)和背景知識(shí)融入到強(qiáng)化學(xué)習(xí)中,基于SARSA(λ)提出一個(gè)改進(jìn)的一個(gè)啟發(fā)函數(shù),提高Agent對(duì)環(huán)境知識(shí)的學(xué)習(xí),加快算法的收斂。

2SARSA(λ)簡(jiǎn)介

SARSA算法是強(qiáng)化學(xué)習(xí)中的一種在策略(on-policy)的時(shí)序差分算法[7]。它由Rummery和Niranjan在1994年提出了一種基于模型的算法,最初稱為改進(jìn)的Q學(xué)習(xí)算法,后稱為SARSA(STATE-ACTION-REWARD-STATE-ACTION)學(xué)習(xí)算法[8]。SARSA在更新時(shí)借助五元組(s,a,r,s′,a′)其中:s表示當(dāng)前狀態(tài);a表示當(dāng)前狀態(tài)下選擇的動(dòng)作;r是選擇動(dòng)作a后獲得的獎(jiǎng)勵(lì);s′和a′則分別代表后續(xù)的狀態(tài)和動(dòng)作。SARSA算法中動(dòng)作值函數(shù)的更新規(guī)則如式(4)所示:

δ=[r+γQ(s′,a′)-Q(s,a)]

Q(s,a)←Q(s,a)+αδ

(4)

γ為折扣因子;α是步長(zhǎng)參數(shù),0≤α≤1和0<γ≤1。

在Q_learning和SARSA算法中,當(dāng)接收到一個(gè)獎(jiǎng)賞值時(shí)只向后回溯一步,相當(dāng)于做了一步備份,導(dǎo)致算法收斂緩慢,一個(gè)改進(jìn)的方法是回溯任意步,稱為SARSA(λ)算法,其動(dòng)作值函數(shù)跟新規(guī)則如式(5):

δ=[r+γQ(s′,a′)-Q(s,a)]

Q(s,a)←Q(s,a)+αδe(s′,a′)

(5)

其中e(s,a)為狀態(tài)的“資格跡”(eligibility trace)[9]。借助資格跡來(lái)體現(xiàn)每一步對(duì)結(jié)果負(fù)的責(zé)任大小。一個(gè)“狀態(tài)-動(dòng)作對(duì)”第一次被訪問(wèn)時(shí),將它的資格跡設(shè)置為1。在隨后的每個(gè)時(shí)間步里,它的資格跡應(yīng)是不斷減少的,當(dāng)該狀態(tài)再次被訪問(wèn)時(shí),其資格跡加1。資格跡的定義如式(6):

(6)

其中表示狀態(tài)s在t時(shí)刻的跡,SARSA(λ)使Agent對(duì)環(huán)境知識(shí)的學(xué)習(xí)有一定程度的進(jìn)步,但對(duì)環(huán)境知識(shí)的學(xué)習(xí)依然是緩慢的,忽略了大量有用的信息和知識(shí)。由于缺乏有效的策略選擇機(jī)制,常需在狀態(tài)空間進(jìn)行多次遍歷才能收斂。針對(duì)SARSA(λ)存在的問(wèn)題,本文引入啟發(fā)(Heuristic)函數(shù)加速(Accelerate)算法對(duì)環(huán)境知識(shí)的學(xué)習(xí),簡(jiǎn)稱HASARSA(λ)算法。借助啟發(fā)函數(shù)改進(jìn)策略的選擇,優(yōu)化回報(bào)函數(shù),相比SARSA(λ)對(duì)環(huán)境知識(shí)的學(xué)習(xí)有明顯的提高。

3HASARSA(λ)設(shè)計(jì)

強(qiáng)化學(xué)習(xí)算法是通過(guò)不斷地與環(huán)境交互,從當(dāng)前一個(gè)狀態(tài)s,選取一個(gè)動(dòng)作a,到達(dá)下一個(gè)狀態(tài)s′,獲得該動(dòng)作a的一個(gè)獎(jiǎng)賞值,強(qiáng)化學(xué)習(xí)算法的關(guān)鍵問(wèn)題在于動(dòng)作選擇函數(shù)和回報(bào)函數(shù)的設(shè)計(jì),本文通過(guò)設(shè)計(jì)一個(gè)啟發(fā)函數(shù)來(lái)改進(jìn)動(dòng)作的選擇,優(yōu)化回報(bào)函數(shù),來(lái)加快算法的收斂。啟發(fā)函數(shù)的定義主要來(lái)自兩方面,一方面是借助先驗(yàn)領(lǐng)域知識(shí),一方面是在學(xué)習(xí)的過(guò)程利用學(xué)習(xí)獲得的信息。文獻(xiàn)[10]提出了大多數(shù)啟發(fā)函數(shù)的定義分為兩個(gè)階段,第一階段是根據(jù)值函數(shù)V進(jìn)行領(lǐng)域結(jié)構(gòu)的提取,稱作結(jié)構(gòu)提取[10]。第二階段是在結(jié)構(gòu)提取后構(gòu)造啟發(fā)式函數(shù),稱為啟發(fā)式構(gòu)造。SARSA(λ)在引入啟發(fā)式函數(shù)的強(qiáng)化學(xué)習(xí)模型如圖1所示。

圖1　啟發(fā)式強(qiáng)化學(xué)習(xí)框架圖

圖1表明在原有的強(qiáng)化學(xué)習(xí)框架基礎(chǔ)上引入了特征節(jié)點(diǎn),并從特征中提取了附加回報(bào)和調(diào)和函數(shù)對(duì)原有的動(dòng)作選擇策略和回報(bào)函數(shù)進(jìn)行優(yōu)化。

3.1策略選擇函數(shù)

Q_learning,SARSA算法在選擇策略上通常選用ε-greedy算法。

ε-greedy選擇策略定義如式(7):

(7)

其中π(st)表示策略選擇函數(shù),p為探索-利用平衡的參數(shù),p越大,算法越傾向于利用已有的知識(shí),arandom是當(dāng)前動(dòng)作集合中的一個(gè)隨機(jī)動(dòng)作。加入啟發(fā)函數(shù)后改進(jìn)的動(dòng)作選擇函數(shù)如式(8):

(8)

相比式(7)多了一個(gè)調(diào)和函數(shù)Ht(st,at),值可正可負(fù)。目的使Agent在執(zhí)行選擇策略過(guò)程中,通過(guò)調(diào)和函數(shù)來(lái)折中分析動(dòng)作的好壞,不斷強(qiáng)化好的動(dòng)作,弱化差的動(dòng)作,借此來(lái)指導(dǎo)動(dòng)作的選擇,減少都無(wú)用狀態(tài)的探索,加速算法的收斂過(guò)程。

3.2回報(bào)函數(shù)

啟發(fā)函數(shù)的回報(bào)函數(shù)分為兩部分,原立即回報(bào)函數(shù)和附加回報(bào)函數(shù)如式(9):

R(st)=r+r′(st,at)

(9)

式中r為立即回報(bào),是借助人的經(jīng)驗(yàn)和背景知識(shí),對(duì)環(huán)境的特征提取,設(shè)置的附加回報(bào)函數(shù)。

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

4.1啟發(fā)函數(shù)的設(shè)計(jì)

啟發(fā)函數(shù)的設(shè)計(jì)依賴一定的環(huán)境問(wèn)題背景,在這里選取一個(gè)20×20 Maze,state表示Agent的狀態(tài),坐標(biāo)(x,y)。Agent開始狀態(tài)隨機(jī)生成,終點(diǎn)狀態(tài)為state(20,20)。Agent可以執(zhí)行的動(dòng)作為上下左右,r表示執(zhí)行一個(gè)動(dòng)作后到達(dá)下一個(gè)狀態(tài)獲得的獎(jiǎng)賞。如果是終點(diǎn)給予10的正獎(jiǎng)勵(lì)值,陷阱則給予負(fù)獎(jiǎng)賞值-5,撞墻或遇到障礙物給予-1的獎(jiǎng)賞值,其它情況給予0。

立即回報(bào)r可以表示如式(10):

(10)

為了定義啟發(fā)函數(shù),本文從環(huán)境中提取如下三個(gè)特征:

1) 本文借助Agent離終點(diǎn)的距離來(lái)表示該狀態(tài)的重要性。用Wij表示state(i,j)的權(quán)重,Wij=(i+j)/40(i,j為該狀態(tài)的坐標(biāo)位置),離終點(diǎn)越近的位置權(quán)重越大,給予的附加獎(jiǎng)賞就越大。啟發(fā)后的回報(bào)函數(shù)可寫成R=r+Wij*β,β取一個(gè)較小的正數(shù),以免對(duì)已有的獎(jiǎng)賞值產(chǎn)生較大的干擾。

2) 可以通過(guò)兩個(gè)坐標(biāo)的差值Δd=(x1-x2)+(y1-y2)來(lái)反映與終點(diǎn)的距離變化關(guān)系。Δd小于0反應(yīng)越接近最終目標(biāo)。

3) 越靠近正獎(jiǎng)賞(也就是最終目標(biāo))的狀態(tài)的Q值近似呈增大趨勢(shì),越靠近負(fù)獎(jiǎng)賞(陷阱、障礙、墻壁)Q值呈近似減小趨勢(shì)。Q值的正負(fù)也隱藏體現(xiàn)著與終點(diǎn)的距離。

從分析中可以看出,特征2),3)都從某種程度上反映了與終點(diǎn)距離的關(guān)系。因此動(dòng)作選擇函數(shù)中的協(xié)調(diào)函數(shù)可以表示如式(11):

(11)

其中θ取一個(gè)較小的數(shù),e[s,a]表示資格跡,借助資格跡來(lái)減小調(diào)和函數(shù)H(st,at)累積效應(yīng)所產(chǎn)生的誤差。

4.2HASARSA(λ)算法

begin

初始化Q(s,a),e(s,a),從環(huán)境中提取特征,結(jié)合經(jīng)驗(yàn)知識(shí)構(gòu)造啟發(fā)函數(shù),觀察目前的狀態(tài),利用基于改進(jìn)的ε-greedy算法選取動(dòng)作a

repeat forever

執(zhí)行行為a

觀察獎(jiǎng)賞R和狀態(tài)s′

R=r+r′

利用基于改進(jìn)的ε-greedy算法選取動(dòng)作a′

s←s′

a←a′

end repeat

end

4.3程序仿真圖

建筑工程設(shè)計(jì)管理過(guò)程中，通過(guò)對(duì)BIM 模型的高效利用，有利于為建筑給排水、電氣和暖通等專業(yè)的協(xié)調(diào)配合提供技術(shù)支持，滿足建筑工程設(shè)計(jì)中管線整體剖析、碰撞查驗(yàn)、主要區(qū)域凈空剖析、結(jié)構(gòu)預(yù)留洞校驗(yàn)以及弱電專項(xiàng)剖析等方面的要求，并得到碰撞檢查匯報(bào)、凈空剖析匯報(bào)、結(jié)構(gòu)預(yù)留洞優(yōu)化圖紙（預(yù)埋套管圖）、綜合管線審核匯報(bào)與優(yōu)化圖紙等，從而實(shí)現(xiàn)對(duì)工程設(shè)計(jì)管理要素的深入分析，建立與建筑工程密切相關(guān)的BIM模型并加以利用，促使實(shí)踐中的建筑工程設(shè)計(jì)管理更加高效，進(jìn)而有效避免工程設(shè)計(jì)管理問(wèn)題的發(fā)生。

借助Matlab進(jìn)行仿真,取ε為0.2,折扣率γ為0.9,步長(zhǎng)α為0.1,得到仿真圖如圖2所示。

圖2　兩種算法的對(duì)比圖

圖2中橫坐標(biāo)episode為迭代次數(shù),縱坐標(biāo)totoalreward為總獎(jiǎng)賞值。箭頭所指位置對(duì)應(yīng)兩種算法總獎(jiǎng)賞值為0的坐標(biāo)。對(duì)比兩個(gè)算法的結(jié)果:雖然SARSA(λ)和HASARSA(λ)算法剛開始獲得了負(fù)獎(jiǎng)賞,但HASARSA(λ)獲得負(fù)獎(jiǎng)賞明顯比前者少,這表明HASARSA(λ)在執(zhí)行中更多地避開了那些會(huì)獲得負(fù)獎(jiǎng)賞的狀態(tài)。當(dāng)算法進(jìn)行2000次迭代,HASARSA(λ)總獎(jiǎng)賞值已經(jīng)開始為正值,并且接下來(lái)總獎(jiǎng)賞值增長(zhǎng)迅速,相比SARSA(λ)在3000次迭代后才為正值,而且增長(zhǎng)速率比較平緩。這體現(xiàn)了HASARSA(λ)可以充分利用環(huán)境特征,使智能體的學(xué)習(xí)速度達(dá)到很大提升,體現(xiàn)了算法的可行性。

5結(jié)語(yǔ)

雖然HASARSA(λ)可以借助從環(huán)境特征提取啟發(fā)函數(shù),來(lái)使智能體學(xué)習(xí)知識(shí)的能力得到提升,但該算法也有一定的缺陷,定義啟發(fā)函數(shù)需要依賴環(huán)境特征和知識(shí)背景,沒有一個(gè)通用的標(biāo)準(zhǔn)。

參 考 文 獻(xiàn)

[1] 史忠植.智能科學(xué)[M].北京:清華大學(xué)出版社,2006:31-35.

SHI Zhongzhi. Intelligent science[M]. Beijing: Tsinghua University Press,2006:31-35.

[2] MItchell T M.機(jī)器學(xué)習(xí)[M].曾華軍,譯.北京:機(jī)械工業(yè)出版社,2008:23-27.

[3] 金釗.加速?gòu)?qiáng)化學(xué)習(xí)方法研究[D].昆明:云南大學(xué),2010:32-36.

JIN Zhao. Accelerate the reinforcement learning method research[D]. Kunming: Yunnan University,2010:32-36.

[4] L. P. Kael bling, M. L. Litt man, A. W. Moore. Reinforcement Learning: A Survey[R]. Arxiv preprint cs/9605103,1996:237-285.

[5] L. Tang, B. An, D. Cheng. An agent reinforcement learning model based on neural networks[C]//Bio-Inspired Computational Intelligence and Applications,2007:117-127.

[6] Jinsong, Leng, Lakhmi Jain, Colin Fyfe. Convergence Analysis on Approximate Reinforcement Learning[C]//Z.Zhang and Siekmann (Eds): KSEM 2007, LNAI 4798, pp.85-91.

[7] Rummery, G A, Niranjan, M. On-line Q_learning using connectionist system[D]. London: Cambridge University,1994.

[8] SUTTONRS, BARTO AG. Reinforcement learning: an introduction[M]. Cambridge: MIT,1998:150-185.

[9] Singh S P, Sutton R S. Reinforcement learning with replacing eligibility traces[J]. Machine Learning,1996,(22):123-158.

[10] Bianchi R A C, Ribeiro C H C, Costa A H R. Accelerating autonomous learning by using heuristic selection of actions[J]. Journal of Heuristics,2008,14(2):135-168.

SARSA (λ) Algorithm Based on Heuristic Function

MA PengweiPAN Dilin

(School of Computer Science and Engineering, Anhui University of Science and Technology, Huainan232001)

AbstractReinforcement learning is an important method of machine learning research. The success in robot path planning, intelligent control and many other successful application in decision making problems make it become an important component of machine learning. But it is also has the problem of slow convergence, slow learning, exploration and utilization of balance. In this paper, an improved algorithm is proposed based on SARSA (λ), which can extract features form the environment and get the heuristic function for strategy and reward function to accelerate the convergence speed. Through simulation comparison, this improved algorithm has faster reward feedback than SARSA(λ), it is showed that the effectiveness of the algorithm in the learning of knowledge.

Key Wordsreinforcement learning, SARSA(λ), heuristic function, assessment learning

* 收稿日期:2015年11月6日,修回日期:2015年12月26日

作者簡(jiǎn)介:馬朋委,男,碩士,研究方向:機(jī)器學(xué)習(xí)。潘地林,男,教授,研究方向:機(jī)器學(xué)習(xí)。

中圖分類號(hào)TP301.6

DOI:10.3969/j.issn.1672-9722.2016.05.011