增強(qiáng)學(xué)習(xí)ReinforcementLearning經(jīng)典算法梳理

1、增強(qiáng)學(xué)習(xí)ReinforcementLearning經(jīng)典算法梳理1：policyandvalueiteration前言就目前來看，深度增強(qiáng)學(xué)習(xí)(DeepReinforcementLearning)中的很多方法都是基于以前的增強(qiáng)學(xué)習(xí)算法，將其中的valuefunction價(jià)值函數(shù)或者Policyfunction策略函數(shù)用深度神經(jīng)網(wǎng)絡(luò)替代而實(shí)現(xiàn)。因此，本文嘗試總結(jié)增強(qiáng)學(xué)習(xí)中的經(jīng)典算法。本文主要參考：ReinforcementLearning:AnIntroduction;2ReinforcementLearningCoursebyDavidSilver1預(yù)備知識(shí)對(duì)增強(qiáng)學(xué)習(xí)有所理解，知道MDP,Bel

2、lman方程詳細(xì)可見：DeepReinforcementLearning基礎(chǔ)知識(shí)(DQWT面)很多算法都是基于求解Bellman方程而形成：ValueIterationPolicyIterationQ-LearningSARSA2PolicyIteration策略迭代PolicyIteration的目的是通過迭代計(jì)算valuefunction價(jià)值函數(shù)的方式來使policy收斂到最優(yōu)。PolicyIteration本質(zhì)上就是直接使用Bellman方程而得到的：+1=EkR+工+ISi=s口那么PolicyIteration一般分成兩步：PolicyEvaluation策略評(píng)估。目的是更新Valu

3、eFunctionPolicyImprovement策略改進(jìn)。使用greedypolicy產(chǎn)生新的樣本用于第一步的策略評(píng)估。PolicyevaluationEstimatevAnypolicyevaluationalgorithmPolicyimprovementGenerate7rzttAnvpolicyimprovementalgorithm本質(zhì)上就是使用當(dāng)前策略產(chǎn)生新的樣本，然后使用新的樣本更新當(dāng)前的策略，然后不斷反復(fù)。理論可以證明最終策略將收斂到最優(yōu)。具體算法：1. Initialization6Randtt(5)6A(h)arbitrarilyforallsS2. PolicyEva

4、luationRepeat-0ForeachseS:v-VsV(s)一凡內(nèi)(另，小尸(3)卜+W(s。A什niax(A,|vV()|)untilA0(asmallprxdtivenuinber)3. PolicyImprovementpolicy-stableJtrueForeachsS:a一開(s)tt(s)cargmaxfl臺(tái)yp(J,r|s,a)r+WIfq，7T(s),thenpolicy-stablefalseIfpolicy-stable,thenstopandreturnVandtt;elsegoto2那么這里要注意的是policyevaluation部分。這里的迭代很重要的一點(diǎn)

5、是需要知道state狀態(tài)轉(zhuǎn)移概率p。也就是說依賴于model模型。而且按照算法要反復(fù)迭代直到收斂為止。所以一般需要做限制。比如到某一個(gè)比率或者次數(shù)就停止迭代。3ValueIteration價(jià)值迭代ValueIteration則是使用Bellman最優(yōu)方程得到=luajjEa+i+制.(5計(jì))|$二34=口=一郎仙卜+然后改變成迭代形式跺+L(s)+gMSt+1)I=“Jvalueiteration的算法如下:InitializearrayVarbitrarily(eg,V(5)Qforalls5+)Rcjicat-0Foreach日W5:vyV(-s)V一仃】的/產(chǎn)p(sra,(r)r+W(s

6、)A4-max(a|廿-產(chǎn)I)untilii國門)卜+。V(吟那么問題來了：PolicyIteration和ValueIteration有什么本質(zhì)區(qū)另1J?為什么個(gè)叫policyiteration,個(gè)叫valueiteration呢？原因其實(shí)很好理解，policyiteration使用bellman方程來更新value,最后收斂的value即vn是當(dāng)前policy下的value值（所以叫做對(duì)policy進(jìn)行評(píng)估），目的是為了后面的policyimprovement得到新的policy。而valueiteration是使用bellman最優(yōu)方程來更新value,最后收斂得到的value即v?就是

7、當(dāng)前state狀態(tài)下的最優(yōu)白vvalue值。因此，只要最后收斂，那么最優(yōu)的policy也就得到的。因此這個(gè)方法是基于更新value的，所以叫valueiteration。從上面的分析看，valueiteration較之policyiteration更直接。不過問題也都是一樣，需要知道狀態(tài)轉(zhuǎn)移函數(shù)p才能計(jì)算。本質(zhì)上依賴于模型，而且理想條件下需要遍歷所有的狀態(tài)，這在稍微復(fù)雜一點(diǎn)的問題上就基本不可能了。4異步更新問題那么上面的算法的核心是更新每個(gè)狀態(tài)的value值。那么可以通過運(yùn)行多個(gè)實(shí)例同時(shí)采集樣本來實(shí)現(xiàn)異步更新。而基于異步更新的思想，DeepMind出了篇不錯(cuò)的paper：Asynchronou

8、sMethodsforDeepReinforcementLearning。該文又于Atari游戲的效果得到大幅提升。5小結(jié)ReinforcementLearning有很多經(jīng)典算法，很多算法都基于以上衍生。鑒于篇幅問題，下一個(gè)blog再分析基于蒙特卡洛的算法。增強(qiáng)學(xué)習(xí)ReinforcementLearning經(jīng)典算法梳理2：蒙特卡洛方法1前言在上一篇文章中，我們介紹了基于Bellman方程而得到的PolicyIteration和ValueIteration兩種基本的算法，但是這兩種算法實(shí)際上很難直接應(yīng)用，原因在于依然是偏于理想化的兩個(gè)算法，需要知道狀態(tài)轉(zhuǎn)移概率，也需要遍歷所有的狀態(tài)。對(duì)于遍歷狀態(tài)

9、這個(gè)事，我們當(dāng)然可以不用做到完全遍歷，而只需要盡可能的通過探索來遍及各種狀態(tài)即可。而對(duì)于狀態(tài)轉(zhuǎn)移概率，也就是依賴于模型Model,這是比較困難的事情。什么是狀態(tài)轉(zhuǎn)移？就比如一顆子彈，如果我知道它的運(yùn)動(dòng)速度，運(yùn)動(dòng)的當(dāng)前位置，空氣阻力等等，我就可以用牛頓運(yùn)動(dòng)定律來描述它的運(yùn)動(dòng)，進(jìn)而知道子彈下一個(gè)時(shí)刻會(huì)大概在哪個(gè)位置出現(xiàn)。那么這個(gè)基于牛頓運(yùn)動(dòng)定律來描述其運(yùn)動(dòng)就是一個(gè)模型Model,我們也就可以知道其狀態(tài)（空間位置，速度）的變化概率。那么基本上所以的增強(qiáng)學(xué)習(xí)問題都需要有一定的模型的先驗(yàn)知識(shí)，至少根據(jù)先驗(yàn)知識(shí)我們可以來確定需要多少輸入可以導(dǎo)致多少輸出。比如說玩Atari這個(gè)游戲，如果輸入只有屏幕的一半，

10、那么我們知道不管算法多么好，也無法訓(xùn)練出來。因?yàn)檩斎氡幌拗屏耍壹词故侨祟愐彩亲霾坏降?。但是以此同時(shí)，人類是無需精確的知道具體的模型應(yīng)該是怎樣的，人類可以完全根據(jù)觀察來推算出相應(yīng)的結(jié)果。所以，對(duì)于增強(qiáng)學(xué)習(xí)的問題，或者說對(duì)于任意的決策與控制問題。輸入輸出是由基本的模型或者說先驗(yàn)知識(shí)決定的，而具體的模型則可以不用考慮。所以，為了更好的求解增強(qiáng)學(xué)習(xí)問題，我們更關(guān)注ModelFree的做法。簡(jiǎn)單的講就是如果完全不知道狀態(tài)轉(zhuǎn)移概率（就像人類一樣），我們?cè)撊绾吻蟮米顑?yōu)的策略呢？本文介紹蒙特卡洛方法。2蒙特卡洛方法蒙特卡洛方法只面向具有階段episode的問題。比如玩一局游戲，下一盤棋，是有步驟，會(huì)結(jié)束的

11、。而有些問題則不一定有結(jié)束，比如開賽車，可以無限的開下去，或者說需要特別特別久才能結(jié)束。能不能結(jié)束是一個(gè)關(guān)鍵。因?yàn)橹灰芙Y(jié)束，那么每一步的reward都是可以確定的，也就是可以因此來計(jì)算value。比如說下棋，最后贏了就是贏了，輸了就是輸了。而對(duì)于結(jié)束不了的問題，我們只能對(duì)于value進(jìn)行估計(jì)。那么蒙特卡洛方法只關(guān)心這種能夠較快結(jié)束的問題。蒙特卡洛的思想很簡(jiǎn)單，就是反復(fù)測(cè)試求平均。如果大家知道在地上投球計(jì)算圓周率的事情就比較好理解了。不清楚的童鞋可以網(wǎng)上找找看。那么如何用在增強(qiáng)學(xué)習(xí)上呢？既然每一次的episode者B可以至ij結(jié)束，那么意味著根據(jù)：aGoal:learn廿芥fromepisod

12、esofexperienceunderpolicytt5l,5土7T Recallthatthereturnisthetotaldiscountedreward:G-/+L+T&+2+7r-1r Recallthatthevaluefunctionistheexpectedreturn:%(s)=EttGt|5f=s Monte-Carlopolicyevaluatronusesempiricalmeanreturninsteadofexpectedreturn每一步的reward都知道，也就意味著每一步的returnGt都可以計(jì)算出來。這就好了。我們反復(fù)做測(cè)試，這樣很多狀態(tài)會(huì)被遍歷到，而且不

13、止一次，那么每次就可以把在狀態(tài)下的return求和取平均。當(dāng)episode無限大時(shí)，得到的數(shù)據(jù)也就接近于真實(shí)的數(shù)據(jù)。蒙特卡洛方法就是使用統(tǒng)計(jì)學(xué)的方法來取代Bellman方法的計(jì)算方法。Initialize:tv1policytobeevaluatedV4-tuiirbitrarystate-valin?functionReturns(s)anemptylist,forall55RepentRin?vet:Generatoanepisodeusing/Fbreachstatesappearingintheepisode：G-returnfollowingthefiratoccurrenceofa

14、AppendGtoReturnss)V().verage(Returns)上面的算法叫first-visitMC。也就是每一次的episode中state只使用第一次到達(dá)的t來計(jì)算return。另一種方法就是every-visit,就是每一次的episode中state只要訪問到就計(jì)算return求平均。所以可以看到蒙特卡洛方法是極其簡(jiǎn)單的。但是缺點(diǎn)也是很明顯的，需要盡可能多的反復(fù)測(cè)試，而且需要到每一次測(cè)試結(jié)束后才來計(jì)算，需要耗費(fèi)大量時(shí)間。但是，大家知道嗎？AlphaGo就是使用蒙特卡洛的思想。不是蒙特卡洛樹搜索，而是說在增強(qiáng)學(xué)習(xí)中使用蒙特卡洛方法的思想。AlphaGo每次也是到下棋結(jié)束，而且

15、只使用最后的輸贏作為returno所以這也是非常神奇的事，只使用最后的輸贏結(jié)果，竟然能夠優(yōu)化每一步的走法。3使用蒙特卡洛方法來控制上面說的蒙特卡洛方法只是能夠?qū)Ξ?dāng)前的policy進(jìn)行評(píng)估。那么大家記得上一個(gè)blog說白ppolicyiteration方法嗎？我們可以在policyiteration中使用蒙特卡洛方法進(jìn)行評(píng)估，然后使用greedypolicy更新。那么依然是有兩種做法。一種就是在一個(gè)policy下測(cè)試多次，評(píng)估完全，然后更新policy,然后再做很多測(cè)試。另一種就是不完全評(píng)估，每次測(cè)試一次完就評(píng)估，評(píng)估完就更新：第一種做法：PolicyevaluationMonte-Carlop

16、olicyevaluation,Q=qrPolicyimprox/mentf-greedypolicyimprovement第二種做法:Everyepisode:PolicyevaluationMonte-Carlopolicyevaluation,QkqPolicyimprovementE-greedypolicyimprovement兩種做法都能夠收斂，那么顯然第二種做法的速度更快。那么再改進(jìn)一點(diǎn)，就是改變greedypolicy中？的值，使得不斷變小趨于0,這個(gè)時(shí)候最后得到的policy就是完全的最優(yōu)policy了。這個(gè)算法就叫做GLIEMonte-CarloControl: Sampl

17、ekthepisodeusingtt:5上4八835丁五 ForeachstateStandactionAtintheepisode,N,4)N(S/J+lQ國4)J。(配4)+A(Q_Q(5，陽ImAt) Improvepolicybasedonnewaction-valuefunction1/&7rc-grccdy(O)其他變種：MonteCarlowithExploringStarts,使用Q(s,a),然后使用上面說的第二種做法，一次episod就更新一次policy,而且policy直接使用Q值。Initialize,forallhW&.W人(s)：Q(S,C1)arbitrary7

18、t(s)0GenerateanepisodestartingfromSo,Ao,followingnForeachpairs*appearingintheepisode:Greturnfollowingthefirstoccurrenceoffi.aAppendGtoRL.turns8ya)a)-average(展加導(dǎo))Foreachsintheepisode:tt(s)argmaxQ(n,q)Figure54:MonteCarloES:AMonroCarlocontrolalgorithmassumingexploringstartsandthatepisodesalwaysterminat

19、eforallpolicies.policy的更新使用了？-greedy,目的就是能夠更好的探索整個(gè)狀態(tài)空間。Initialize,forallsE5.&FX(s):arbitrary1emptylistnas)-anarbitrarye-softpolicyHrptviffbrevir；3) Gutivratcanepisodeusingr(b) Foreachjyairs.aajjpearinf；iiitheejiisude:GJreturnfbliowingth戶firstoccurrncpof樂AppendGtoReturnsa)QI*,a)ritv(jragii(fleturnnA,

20、fij)(c) ForFach丹intheepisode:AarxniaxqQ(5,fi)7T（09）l-e+/X(fl)|ifa=.4-ifa/AFigure5.6:Anou-policyfirst-visitMCcuntmlalguritlimfur-&oftpolicies.4OffPolicyLearning那么上面的方法一直是基于當(dāng)前的policy,為了探索狀態(tài)空間，采用一個(gè)次優(yōu)的策略？-greedypolicy來探索。那么是不是可以更直接的使用兩個(gè)policyo一個(gè)policy用來探索空間，也就是behaviorpolicy,另一個(gè)policy就是為了達(dá)到最優(yōu)policy,叫做ta

21、rgetpolicy。那么這種方法就叫做offpolicylearning。On-policy的方法比較簡(jiǎn)單，off-policy方法需要更多的概念和標(biāo)記，比較不好理解，而且，由于behaviourpolicy和targetpolicy不相關(guān)，這種方法比較不容易收斂。但是off-policy更強(qiáng)大，更通用，實(shí)際上的on-policy方法就是off-policy方法的一個(gè)子集。比如，就可以使用off-policy從人類專家或者傳統(tǒng)的控制算法來學(xué)習(xí)一個(gè)增強(qiáng)學(xué)習(xí)模型。Initialize,forallES,uea)：Q(fljfl)arbitraryC(*iq)J。ir(丹)ecttoQRepeat

22、forever；Generateanepisodeusinganysoftpolicy揮R11：6丁-11再.7)./JjlSrFort=T1,T2,downto0:G+凡+i吶&)陰+WQ,A)CQ,4)+意而G-Q,A)1tt(S()+argmaxQfSt.fl)(withtictsbrokouconsistently)IfAt7r(SjthenExitForLoopFigure5.1(J：An。也policyevery-visitMCcontrolalgorithrn+usingweightediiiiportance1NatnpUng.ThepolicyttconvergesLg3TD

23、算法Input:thepolicytobeevuluwtedInitializeV(s)arbitrarily(e,g,V(a)=0lVj5+)Repeat(foreachepisode1)：InitializeSRcpauit(forwxehstepofcpiyodc)：Aactio!)iveubyttfic)rSTakeactionA,observeR*SV(5)1儀5)+aR+7/(力-VSsyuntilSisterminalFigure6.1：labularTD;forestinialiug%這只是TD(0)的估計(jì)方式，顯然可以拓展到n-step。就是講TD-target再根據(jù)bell

24、man方程展開。再下來的思想，就是可以把TD(i)和TD(j)合在一起求個(gè)平均吧。再下來就是把能算的TD(i)都算一遍，每一個(gè)給個(gè)系數(shù),總和為1,這就是TD(入)G=口一文*】Ga=L4 SARSA算法SARSA算法的思想很簡(jiǎn)單，就是增加一個(gè)A,下一步的A,然后據(jù)此來估計(jì)Q(s,a)。InitializeQ(,a)TW以0WX(e),arbitrarily,andstate,)=0Repeat(forcactiepisode:InitializeSChooHCAfromSusingpolicyderivedfromQ(e.g“r-greedy)Repeat(foreachstepofepiso

25、de)：Takeaction兒observeR,SfChooseAffromSfusingpolicyderivedfromQ(ag-c-greedy)Q(S,A)Q(S,)+乖+EF-Q(SM)S-S;月一；untilSisterminalFigure6+5:Sarsa:Anon-policyTl)controlalgorithni.之所以算法稱為SARSA,就是指一次更新需要用到這5個(gè)量。5 Q-Learning算法著名的Q-Learning。InitializeQa).VsW&W人(5)，arbitrarily,atidQ(teTtninal-state,-)=0Repeat(forea

26、chepisode)：InitializeSRepeat(foreachstepofepisode):ChooseAfromSusingpolicyderivedfromQ(e.g*,greedy)TakeactionA,observeR.SfQ(f,A)JQ(S,R)+的冗+7max。Q(S。)-Q(S,4)SS*untilSisterminalFigure6,7:(J-learning：Anoff-policyTDcontrolalgorithm.這里直接使用最大的Q來更新。為什么說SARSA是on-policy而Q-Learning是off-policy呢?因?yàn)镾ARSA只是對(duì)policy進(jìn)行估1t,而Q-Learning的Q則是通往最優(yōu)。6DoubleQ-LearningQ-Learning可能會(huì)出現(xiàn)對(duì)Q值過度估計(jì)的問題，DoubleQ-Learning可以解決這個(gè)問題：TnitinliziQ(flha)andG8,u用砧arburiirilyInitidizrQi&Ei汕血，.業(yè)加)=Q式而仃“住山-“汨飆=0llrpcat(foreachepudci：Sliupeal(furrHtlis