劉 全,于 俊,王 輝，傅啟明,朱 斐

(1.蘇州大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇蘇州 215006;2.吉林大學(xué)符號計算與知識工程教育部重點(diǎn)實驗室,吉林長春 130012：3.軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心，江蘇南京 210023)

?

一種基于隨機(jī)投影的貝葉斯時間差分算法

劉 全1,2，3,于 俊1，3,王 輝1，3，傅啟明1，3,朱 斐1，3

(1.蘇州大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇蘇州 215006;2.吉林大學(xué)符號計算與知識工程教育部重點(diǎn)實驗室,吉林長春 130012：3.軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心，江蘇南京 210023)

在強(qiáng)化學(xué)習(xí)方法中,大部分的算法都是基于值函數(shù)評估的算法.高斯過程時間差分算法利用貝葉斯方法來評估值函數(shù),通過貝爾曼公式和貝葉斯規(guī)則,建立立即獎賞與值函數(shù)之間的概率生成模型.在狀態(tài)空間中,通過在線核稀疏化并利用最小二乘方法來求解新樣本的近似線性逼近,以提高算法的執(zhí)行速度,但時間復(fù)雜度依然較高.針對在狀態(tài)空間中近似狀態(tài)的選擇問題,在高斯過程框架下提出一種基于隨機(jī)投影的貝葉斯時間差分算法,該算法利用哈希函數(shù)把字典狀態(tài)集合中的元素映射成哈希值,根據(jù)哈希值進(jìn)行分組,進(jìn)而減少狀態(tài)之間的比較.實驗結(jié)果表明,該方法不僅能夠提高算法的執(zhí)行速度,而且較好地平衡了評估狀態(tài)值函數(shù)精度和算法執(zhí)行時間.

強(qiáng)化學(xué)習(xí);馬爾科夫決策過程;高斯過程;隨機(jī)投影;時間差分算法

1 引言

強(qiáng)化學(xué)習(xí)(Reinforcement Learning,RL)是在未知、動態(tài)環(huán)境中在線求解最優(yōu)策略,以獲取最大期望回報的一類算法.強(qiáng)化學(xué)習(xí)方法的基本框架為:Agent通過試錯與環(huán)境進(jìn)行交互,將每一步的延遲回報通過時間信用分配機(jī)制傳遞給過去動作序列中的某些動作,用值函數(shù)評價每個狀態(tài)或狀態(tài)動作對的好壞程度,最終通過值函數(shù)確定最優(yōu)策略[1,2].目前強(qiáng)化學(xué)習(xí)方法越來越多地被用于在線控制、作業(yè)調(diào)度、游戲等領(lǐng)域[3,4].

馬爾科夫決策過程(Markov Decision Process,MDP)是一類重要的隨機(jī)過程,經(jīng)常用來對強(qiáng)化學(xué)習(xí)進(jìn)行建模[5].Sutton在1998年提出對馬爾科夫鏈學(xué)習(xí)的理論和TD(λ)算法[6].核方法在監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)問題中都得到了廣泛的研究[7].目前基于核的強(qiáng)化學(xué)習(xí)理論與應(yīng)用成果還較少,這主要是由于核方法需要隨機(jī)或重復(fù)的獲取訓(xùn)練樣本[8].直到2002年,Ormoneit 等人提出了基于核的強(qiáng)化學(xué)習(xí)方法[9].后來,Xu等人提出了基于核的最小二乘TD方法(Kernel-based Least Squares TD,KLSTD),將基于核的逼近與LSTD相結(jié)合[10],取得了一定的效果.在KLSTD基礎(chǔ)之上,Xu等人繼續(xù)提出了KLSPI及KLSPI-Q算法[11],并證明了方法的有效性.Yaakov Engel等人提出了一種新的值函數(shù)評估方法,該方法利用核方法來估計值函數(shù),選擇核方法中的高斯過程 (Gaussian process)模型[12]為值函數(shù)建模,通過高斯過程與時間差分方法相結(jié)合得到高斯過程的時間差分(Gaussian Process Temporal Difference,GPTD)學(xué)習(xí)算法[13，14],建立值函數(shù)的概率生成模型,然后根據(jù)先驗,以及觀測到的樣本,利用貝葉斯推理得到值函數(shù)完整的后驗分布.

對于固定的策略,GPTD能夠較準(zhǔn)確的評估該策略的值函數(shù),但是GPTD算法的明顯缺點(diǎn)是模型的學(xué)習(xí)完全依賴于樣本,計算量較大.Engel等人提出了依賴于特征空間的在線核稀疏化方法,將核函數(shù)看作是在高維希伯爾特空間上的兩個向量的內(nèi)積,直接去除那些能夠用特征空間中特征近似線性逼近的樣本[15],利用最小二乘方法來求解新樣本的近似線性逼近,以提高時間和空間效率.

本文針對在強(qiáng)化學(xué)習(xí)狀態(tài)空間中需要選擇近似狀態(tài)的問題,在高斯過程框架上提出一種基于隨機(jī)投影的貝葉斯時間差分算法(Bayesian Temporal Difference algorithm based on Random Projection,RPGPTD).該算法對于新狀態(tài),首先進(jìn)行預(yù)處理,把狀態(tài)轉(zhuǎn)變?yōu)槎M(jìn)制編碼,使得相似的數(shù)據(jù)對象,其二進(jìn)制編碼也相似,在此基礎(chǔ)上進(jìn)行相似性比較選擇,同時設(shè)置參數(shù)閾值來控制狀態(tài)字典集合逼近真實狀態(tài)空間程度.實驗結(jié)果表明,該方法不僅能夠提高算法的執(zhí)行速度,而且在值函數(shù)評估質(zhì)量和時間上有較好的平衡.

2 相關(guān)理論

2.1 馬爾科夫決策過程

在強(qiáng)化學(xué)習(xí)中,通常用馬爾科夫決策過程來對描述的問題進(jìn)行建模,它把強(qiáng)化學(xué)習(xí)問題描述為一個四元組M=,其中X是環(huán)境的狀態(tài)集合;U是Agent能采取的動作集合;f(·|x,u)為狀態(tài)x下執(zhí)行動作u轉(zhuǎn)移到下一狀態(tài)的概率分布,它對后繼狀態(tài)的不確定性進(jìn)行了模型化;f0(·)表示初始狀態(tài)被選擇的概率分布;ρ(·|x,u)是立即獎賞函數(shù)的概率分布,r(x,u)是滿足ρ(·|x,u)的一個隨機(jī)變量,表示在狀態(tài)x處,Agent執(zhí)行動作u,到達(dá)后繼狀態(tài)x′獲得的獎賞值.

強(qiáng)化學(xué)習(xí)中,值函數(shù)通常分為兩種:狀態(tài)值函數(shù)和動作值函數(shù).本文以狀態(tài)值函數(shù)為基礎(chǔ),但是很容易擴(kuò)展到動作值函數(shù),狀態(tài)值函數(shù)V(x)是指當(dāng)前狀態(tài)x下回報R(x)的期望值.

=Eh{r(x)+γR(x′)}

(1)

2.2 高斯過程時間差分算法

(2)

將公式(2)帶入公式(1)中,可得到關(guān)于立即獎賞的生成模型,如公式(3)所示.

r(x)=V(x)-γEx′|x{V(x′)}+N(x)

(3)

在確定性問題的在線學(xué)習(xí)過程中,公式(3)可以改寫成公式(4).

r(x)=V(x)-γV(x′)+N(x)

(4)

其中,N(x)為噪聲項.

假定給定一條包含t+1個樣本的路徑ξ=(x0,x1,…,xt-1,xt),可以得到如公式(5)所示的t個等式.

r(xi)=V(xi)-γV(xi+1)+N(xi)

(5)

將這t個等式的狀態(tài)值函數(shù)、立即獎賞以及噪聲分別寫成向量的形式,如公式(6)、(7)、(8)所示.

Vt=(V(x0),V(x1),…,V(xt))T

(6)

rt-1=(r(x0),r(x1),…,r(xt-1))T

(7)

Nt-1=(N(x0),N(x1),…,N(xt-1))T

(8)

根據(jù)這組樣本序列及公式(5),可得一個包含t個等式的向量表達(dá)式,如公式(9)所示.

rt-1=HtVt+Nt-1

(9)

其中,Ht是一個t×(t+1)的矩陣,如公式(10)所示.

(10)

類比于高斯過程回歸方法,高斯過程時間差分算法在值函數(shù)上引入高斯先驗,即V～N(0,k(·,·)),意味著V是一個高斯過程,對于所有的x,x′∈X都有先驗E(V(x))=0和E(V(x)V(x′))=k(x,x′),為了使得k(·,·)是一個合理的協(xié)方差函數(shù),需要核函數(shù)是對稱正定的,且核函數(shù)的選擇需要反映出兩個狀態(tài)之間的先驗關(guān)系.因此,Vt～N(0,Kt),其中[Kt]i,j=k(xi,xj).

假設(shè)1 假設(shè)各狀態(tài)的立即獎賞的噪聲項相互獨(dú)立服從于高斯分布且與狀態(tài)值函數(shù)V相互獨(dú)立,均值為0,方差為σ2(x),即:N(x)～N(0,σ2(x)).則噪聲向量Nt-1的分布形式如公式(11)所示.

(11)

(12)

(13)

假設(shè)變量X和變量Y是隨機(jī)向量,且滿足多元正態(tài)分布,即

利用貝葉斯規(guī)則,則變量X的后驗X|Y滿足公式(14)

(14)

由此可以得出,設(shè)在一個情節(jié)中,前t個時刻,有樣本路徑ξ=(x0,x1,…,xt-1),以及獎賞序列rt-1=(r(x0),r(x1),…,r(xt-1))T.

3 基于隨機(jī)投影的貝葉斯差分算法及分析

3.1 稀疏化方法

(15)

(16)

(17)

(18)

(19)

由公式(18)、(19)可得到稀疏化后的狀態(tài)值函數(shù)的后驗,如公式(20)所示:

(20)

3.2 基于隨機(jī)投影的貝葉斯時間差分算法

定義1 對于狀態(tài)集合X,集合內(nèi)的狀態(tài)間相似度的計算公式為sim(·,·),如果存在一個哈希函數(shù)hash(·)滿足以下條件:存在一個相似度s到概率p的單調(diào)遞增映射關(guān)系,使得X中的任意兩個元素a和b滿足sim(a,b)≥s,且hash(a)=hash(b)的概率大于p,那么hash(·)就是該集合的一個隨機(jī)投影哈希函數(shù).

隨機(jī)投影方法主要分為預(yù)處理階段和選擇階段兩個部分.

(21)

(22)

在強(qiáng)化學(xué)習(xí)中,對于情節(jié)式任務(wù),設(shè)最后一個狀態(tài)為bound(vt)∈[-0.07,+0.07],由于bound(pt)∈[-1.2,+0.5],因此對于樣本g,有以下公式:

g=-0.0025

(23)

即,可以暫時先把折扣因子置為0,遇到非終止?fàn)顟B(tài)時再把折扣因子重置為初始值.

下面給出基于隨機(jī)投影的貝葉斯時間差分算法.

4 實驗及結(jié)果分析

為了驗證隨機(jī)投影高斯過程時間差分算法的有效性,以經(jīng)典的離散狀態(tài)空間的格子世界為基礎(chǔ)平臺,來對RPGPTD算法的性能進(jìn)行測評,并通過與已有的GPTD算法進(jìn)行性能對比來說明RPGPTD算法的優(yōu)越性.

在一個9×9的格子世界,每個格子代表一個狀態(tài),每個狀態(tài)可采取的動作包括上、下、左、右4個方向的運(yùn)動.每次狀態(tài)遷移時,Agent得到的立即獎賞均為-1,到達(dá)終止?fàn)顟B(tài)時的獎賞也為-1.折扣因子γ=1.

閾值取為ν=1,所有噪聲方差均取σ2=0.1.

在遵循策略h的情況下,分別對RPGPTD算法與GPTD算法執(zhí)行1000個情節(jié),比較兩個算法的執(zhí)行時間和值函數(shù)估計誤差.在給定算法參數(shù)后,每個算法都獨(dú)立運(yùn)行10次,每次獨(dú)立運(yùn)行都計算出兩種算法所需的時間以及對所有狀態(tài)進(jìn)行值函數(shù)估計的均方誤差,然后再計算各次獨(dú)立運(yùn)行的所需時間和值函數(shù)估計均方誤差的平均值,以此來作為算法的評價指標(biāo).

首先,考察RPGPTD算法與GPTD算法在格子世界中執(zhí)行500以及1000個情節(jié)所需的時間,其中RPGPTD算法的參數(shù)l分別取為2,4,8,10,時間的單位為秒(s),如表1所示.

表1 9×9格子世界問題RPGPTD算法與GPTD算法在一定情節(jié)數(shù)內(nèi)執(zhí)行算法的時間比較

9×9格子世界問題500episodes1000episodesGPTD算法634.616s1362.522sRPGPTD算法l=2518.705s1079.906sRPGPTD算法l=4474.883s959.941sRPGPTD算法l=8480.905s953.443sRPGPTD算法l=10494.030s975.366s

針對RPGPTD算法,在減少算法執(zhí)行時間的基礎(chǔ)上,進(jìn)一步對值函數(shù)評估的準(zhǔn)確度進(jìn)行考察.利用動態(tài)規(guī)劃方法(DP)迭代可以計算出準(zhǔn)確的狀態(tài)值函數(shù),動態(tài)規(guī)劃更新公式為:

(24)

將RPGPTD算法與GPTD算法執(zhí)行1000個情節(jié)得到的狀態(tài)值函數(shù)與利用動態(tài)規(guī)劃方法得到的值函數(shù)進(jìn)行比較.以均方根誤差函數(shù)作為比較準(zhǔn)則:

(25)

圖1給出了RPGPTD算法與GPTD算法的狀態(tài)值函數(shù)的均方根誤差隨情節(jié)數(shù)增加而變化的曲線圖.圖中RPGPTD算法的參數(shù)l取為2.由圖可以看出,在遵循策略h的情況下,RPGPTD算法與GPTD算法對狀態(tài)值函數(shù)的評估能力一致,兩種算法在200個情節(jié)數(shù)后都能很好的收斂,且逼近精度也一致.

下面探究RPGPTD算法中參數(shù)l對值函數(shù)評估的影響,圖2所示的曲線是參數(shù)l分別取為2,4,8,10時RMSE隨情節(jié)數(shù)的變化圖.當(dāng)參數(shù)l取2,4時,在前200個情節(jié),RMSE的值震蕩下降,震蕩較大,200個情節(jié)之后震蕩較小,逐漸趨于一致且收斂,當(dāng)參數(shù)l取8,10時,在前200個情節(jié),RMSE震蕩較大,但是在200個情節(jié)后,RMSE曲線圖明顯高于參數(shù)取2,4時的曲線圖,即對狀態(tài)值函數(shù)的評估誤差較大,評估結(jié)果不理想,所以在參數(shù)l較大時,狀態(tài)值函數(shù)評估誤差較大.由此可見,理想情況下,參數(shù)l越大,執(zhí)行速度越快,并且呈指數(shù)級的提升,但是,在這種情況下哈希函數(shù)HASH(·)的概率公式p(s)可以表示為與新來狀態(tài)x的相似度為s的狀態(tài)的召回率.當(dāng)參數(shù)l的取值越大時狀態(tài)的召回率必然降低,所以RPGPTD算法在參數(shù)l增大時,對狀態(tài)值函數(shù)的評估效果不理想.

5 結(jié)論

本文針對于在強(qiáng)化學(xué)習(xí)狀態(tài)空間中近似狀態(tài)的選擇問題,基于高斯過程時間差分框架,提出一種基于隨機(jī)投影的貝葉斯時間差分算法.高斯過程時間差分算法通過貝爾曼公式和貝葉斯規(guī)則,建立立即獎賞與值函數(shù)之間的概率生成模型,但在評估值函數(shù)時,算法執(zhí)行速度較慢,為進(jìn)一步提升執(zhí)行時間,利用哈希函數(shù)把字典狀態(tài)集合中的元素映射成哈希值,把狀態(tài)轉(zhuǎn)變?yōu)槎M(jìn)制編碼,使得相似的數(shù)據(jù)對象,其二進(jìn)制編碼也相似,根據(jù)哈希值進(jìn)行分組,進(jìn)而減少狀態(tài)之間的比較,同時設(shè)置參數(shù)閾值來控制狀態(tài)字典集合逼近真實狀態(tài)空間的程度.實驗結(jié)果表明,該方法不僅能夠提高算法的執(zhí)行速度,而且在評估狀態(tài)值函數(shù)精度和算法執(zhí)行時間上有較好的平衡.

[1]Sutton R S,Barto A G.Reinforcement Learning:An Introduction[M].Cambridge:MIT Press,1998.

[2]傅啟明,劉全,尤樹華,黃蔚,章曉芳.一種新的基于值函數(shù)遷移的快速Sarsa算法[J].電子學(xué)報,2014,42(11):2157-2161.

Fu Qiming,Liu Quan,You Shuhua,Huang Wei,Zhang Xiaofang.A novel fast Sarsa algorithm based on value function transfer[J].Acta Electronica Sinica,2014,42(11):2157-2161.(in Chinese)

[3]Martínez Y,Nowé A,Suárez J,et al.A Reinforcement Learning Approach for the Flexible Job Shop Scheduling Problem[M].Learning and Intelligent Optimization:Springer Berlin Heidelberg,2014.253-262.

[4]Amato C,Shani G.High-level reinforcement learning in strategy games[A].Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems[C].International Foundation for Autonomous Agents and Multiagent Systems,2010.75-82.

[5]Marco Wiering,Martijn van Otterlo.Reinforcement Learning State of the Art[M].Singapore:Springer Press,2012.

[6]Sutton R S.Learning to predict by the methods of temporal differences[J].Machine Learning,1988,3(1):9-44.

[7]Shawe-Taylor J,Cristianini N.Kernel Methods for Pattern Analysis[M].Cambridge:Cambridge University Press,2004.

[8]Scholkopf B,Smola A J.Learning with Kernels:Support Vector Machines,Regularization,Optimization,and Eyond[M].Cambridge:MIT Press,2002.

[9]Ormoneit D,Sen.Kernel-based reinforcement learning[J].Machine Learning,2012,49(2-3):161-178.

[10]Xu X,Xie T,Hu D,et al.Kernel least-squares temporal difference learning[J].International Journal of Information Technology,2005,11(9):54-63.

[11]Xu X,Hu D,Lu X.Kernel-based least squares policy iteration for reinforcement learning[J].IEEE Transactions on Neural Networks,2007,18:973-992.

[12]C E Rasmussen and C K I Williams.Gaussian Processes for Machine Learning[M].Cambridge:MIT Press,2006.

[13]Engel Y,Mannor S,Meir R.Bayes meets Bellman:the gaussian process approach to temporal difference learning[A].Proceedings of the 20th International Conference on Machine Learning[C].Washington:AAAI,2011.154-161.

[14]Engel Y,Mannor S,Meir R.Reinforcement learning with gaussian processes[A].Proceedings of the 22nd International Conference on Machine Learning[C].Bonn:ACM,2014.201-208.

[15]Engel Y,Mannor S,Meir R.Sparse Online Greedy Support Vector Regression[M].Berlin:Springer,2002.

劉 全 男,1969年生于內(nèi)蒙古,博士,教授,博士生導(dǎo)師.主要研究方向為強(qiáng)化學(xué)習(xí)、無線傳感器網(wǎng)絡(luò)、智能信息處理.

E-mail:quanliu@suda.edu.cn

于 俊 男，1989年生于江蘇泰州，碩士.主要研究方向為強(qiáng)化學(xué)習(xí)、貝葉斯推理.

A Bayesian Temporal Difference Algorithm Based on Random Projection

LIU Quan1, 2, 3,YU Jun1,3,WANG Hui1,3,FU Qi-ming1,3, ZHU Fei1,3

(1.SchoolofComputerScienceandTechnology,SoochowUniversity,Suzhou,Jiangsu215006,China;2.KeyLaboratoryofSymbolicComputationandKnowledgeEngineeringofJilinUniversity,MinistryofEducation,JilinUniversity,Changchun,Jilin130012,China；3.CollaborativeInnovationCenterofNovelSoftwareTechnologyandIndustrialization，Nanjing,Jiangsu210023,China)

Most algorithms are based on policy evaluation in reinforcement learning.The Gaussian process temporal difference is an algorithm that uses Bayesian solution to evaluate value functions.In the method,Gaussian process builds a probabilistic generative model between the immediate reward and the value function through Bellman Equation and Bayesian rule.In order to improve the efficiency of the algorithm,approximate linear approximation for new samples is solved by on-line kernel sparse and least squares in state space.However,the time complexity is still high.To deal with this problem,a Bayesian temporal difference algorithm bases on random projection algorithm is proposed.The elements in dictionary state set are mapped to hash values by hash function.According to the hash values,groups are divided and the comparison between the states is reduced.The experimental results show that this algorithm not only improves the execution speed,but also obtains balance between execution time and precision of the state value function.

reinforcement learning;markov decision process;gaussian process;random projection;temporal difference learning

2015-04-08;

2015-08-17;責(zé)任編輯:藍(lán)紅杰

國家自然科學(xué)基金(No.61272005,No.61303108,No.61373094,No.61472262，No.61502323，No.61502329);江蘇省自然科學(xué)基金(No.BK2012616)；江蘇省高校自然科學(xué)研究項目(No.13KJB520020);吉林大學(xué)符號計算與知識工程教育部重點(diǎn)實驗室項目(No.93K172014K04);蘇州市應(yīng)用基礎(chǔ)研究計劃工業(yè)部分(No.SYG201422，No.SY201308)

TP181

A

0372-2112 (2016)11-2752-06

??學(xué)報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.11.026