增強學習ReinforcementLearning經(jīng)典算法梳理

增強學習ReinforcementLearning經(jīng)典算法梳理1：policyandvalueiteration前百就目前來看，深度增強學習(DeepReinforcementLearning)中的很多方法都是基于以前的增強學習算法，將其中的valuefunction價值函數(shù)或者Policyfunction策略函數(shù)用深度神經(jīng)網(wǎng)絡替代而實現(xiàn)。因此，本文嘗試總結增強學習中的經(jīng)典算法。本文主要參考：1ReinforcementLearning:AnIntroduction；2ReinforcementLearningCoursebyDavidSilver1預備知識對增強學習有所理解，知道MDP，Bellman方程詳細可見：DeepReinforcementLearning基礎知識(DQN方面)很多算法都是基于求解Bellman方程而形成：ValueIterationPolicyIterationQ-LearningSARSA2PolicyIteration策略迭代PolicyIteration的目的是通過迭代計算valuefunction價值函數(shù)的方式來使policy收斂到最優(yōu)。PolicyIteration本質上就是直接使用Bellman方程而得到的：縱+1⑻=&田±+1+y/(S2+i)|St=s]=工笆㈤呂)1+7喙(#)].a 8f,v那么PolicyIteration一般分成兩步：PolicyEvaluation策略評估。目的是更新ValueFunctionPolicyImprovement策略改進。使用greedypolicy產(chǎn)生新的樣本用于第一步的策略評估。

startingVjtimprovementstartingVjtimprovementPolicyev^luadoriEstimate吃AnypolicyevaluationalgorithmPolicyimprovementGenerate/之丁Anypolic/improvementalgorithm然后使用新的樣本更新當前的策略，然后不斷反復。理論可以證明最終本質上就是使用當前策略產(chǎn)生新的樣本然后使用新的樣本更新當前的策略，然后不斷反復。理論可以證明最終策略將收斂到最優(yōu)。具體算法：InitializationV(5)GRandtt(s)EX(.s)arbitrarilyforall5￡SPolicyEvaluationRijpcjat△一0ForeachsGS:v<—V(5)V(s).DyPtZrWHs))卜+儼(刈△<—niax{A1\v—V(5)|)until△<g(asmallpositivenumber)PolicyImprovementpolicy-stabletrueF()rcacihs€S:a—無⑶7T⑸一也陪1口兇￡口￡5%P(/嚴麗(1)卜十丁/(艮)]Ifa豐thenpolicy-stable<—falseIfpolicy-stable,thenstopandreturnVand?r:elsegoto2那么這里要注意的是policyevaluation部分。這里的迭代很重要的一點是需要知道state狀態(tài)轉移概率p。也就是說依賴于model模型。而且按照算法要反復迭代直到收斂為止。所以一般需要做限制。比如到某一個比率或者次數(shù)就停止迭代。3ValueIteration價值迭代ValueIteration則是使用Bellman最優(yōu)方程得到%(3)=.niHxlE[描+1+丁香.{3+1)I顯=氧4」可二msix *號肛)1r+7^*($')U式T然后改變成迭代形式切t十I,)=口”邛吧凡+1+尸盟(&+1)|&=曷4=口］Q-=11臂x￡p(s\『|s，g『十"也3)卜valueiteration的算法如下：InitializearrayVarbitrarilyV(s)=0foralls€S1)Repeat△-0Fbreachse3：v-*—F⑸V(fl)lmaxa口,〃(3尸|名叫『十衣兇］△4—mHK(△/廿—V(d)|)untilA<t?(asmallpositivenumber)Outputadeterininistiepolicy,tt,suchthat"?=仃時/口勺成乩?、炔?科⑺］那么問題來了：PolicyIteration和ValueIteration有什么本質區(qū)別？為什么一個叫policyiteration,一個叫valueiteration呢？原因其實很好理解，policyiteration使用bellman方程來更新value，最后收斂的value即vn是當前policy下的value值(所以叫做對policy進行評估)，目的是為了后面的policyimprovement得到新的policy。而valueiteration是使用bellman最優(yōu)方程來更新value，最后收斂得到的value即v就是當前state狀態(tài)下的最優(yōu)的value值。因此，只要最后收斂，那么最優(yōu)的policy也就得到的。因此這個方法是基于更新value的，所以叫valueiteration。從上面的分析看，valueiteration較之policyiteration更直接。不過問題也都是一樣，需要知道狀態(tài)轉移函數(shù)p才能計算。本質上依賴于模型，而且理想條件下需要遍歷所有的狀態(tài)，這在稍微復雜一點的問題上就基本不可能了。4異步更新問題那么上面的算法的核心是更新每個狀態(tài)的value值。那么可以通過運行多個實例同時采集樣本來實現(xiàn)異步更新。而基于異步更新的思想，DeepMind出了一篇不錯的paper：AsynchronousMethodsforDeepReinforcementLearning。該文對于Atari游戲的效果得到大幅提升。5小結ReinforcementLearning有很多經(jīng)典算法，很多算法都基于以上衍生。鑒于篇幅問題，下一個blog再分析基于蒙特卡洛的算法。增強學習ReinforcementLearning經(jīng)典算法梳理2：蒙特卡洛方法1前言在上一篇文章中，我們介紹了基于Bellman方程而得到的PolicyIteration和ValueIteration兩種基本的算法，但是這兩種算法實際上很難直接應用，原因在于依然是偏于理想化的兩個算法，需要知道狀態(tài)轉移概率，也需要遍歷所有的狀態(tài)。對于遍歷狀態(tài)這個事，我們當然可以不用做到完全遍歷，而只需要盡可能的通過探索來遍及各種狀態(tài)即可。而對于狀態(tài)轉移概率，也就是依賴于模型Model，這是比較困難的事情。什么是狀態(tài)轉移？就比如一顆子彈，如果我知道它的運動速度，運動的當前位置，空氣阻力等等，我就可以用牛頓運動定律來描述它的運動，進而知道子彈下一個時刻會大概在哪個位置出現(xiàn)。那么這個基于牛頓運動定律來描述其運動就是一個模型Model，我們也就可以知道其狀態(tài)（空間位置，速度）的變化概率。那么基本上所以的增強學習問題都需要有一定的模型的先驗知識，至少根據(jù)先驗知識我們可以來確定需要多少輸入可以導致多少輸出。比如說玩Atari這個游戲，如果輸入只有屏幕的一半，那么我們知道不管算法多么好，也無法訓練出來。因為輸入被限制了，而且即使是人類也是做不到的。但是以此同時，人類是無需精確的知道具體的模型應該是怎樣的，人類可以完全根據(jù)觀察來推算出相應的結果。所以，對于增強學習的問題，或者說對于任意的決策與控制問題。輸入輸出是由基本的模型或者說先驗知識決定的，而具體的模型則可以不用考慮。所以，為了更好的求解增強學習問題，我們更關注ModelFree的做法。簡單的講就是如果完全不知道狀態(tài)轉移概率（就像人類一樣），我們該如何求得最優(yōu)的策略呢？本文介紹蒙特卡洛方法。2蒙特卡洛方法蒙特卡洛方法只面向具有階段episode的問題。比如玩一局游戲，下一盤棋，是有步驟，會結束的。而有些問題則不一定有結束，比如開賽車，可以無限的開下去，或者說需要特別特別久才能結束。能不能結束是一個關鍵。因為只要能結束，那么每一步的reward都是可以確定的，也就是可以因此來計算value。比如說下棋，最后贏了就是贏了，輸了就是輸了。而對于結束不了的問題，我們只能對于value進行估計。那么蒙特卡洛方法只關心這種能夠較快結束的問題。蒙特卡洛的思想很簡單，就是反復測試求平均。如果大家知道在地上投球計算圓周率的事情就比較好理解了。不清楚的童鞋可以網(wǎng)上找找看。那么如何用在增強學習上呢？既然每一次的episode都可以到結束，那么意味著根據(jù):Goal:learn%fromepisodesofexperienceunderpolicyit5]h電,…】Sjf—7TRecallthatthereturnisthetotaldiscountedreward:G-a+i+7^t+2+…十個丁_【R丁Recallthatthevaluefunctionistheexpectedreturn:${$)==E)r[GtISt=5]Morte-Carlopolicyevaluationusesempiricalmeanreturninsteadofexpectedreturn每一步的reward都知道，也就意味著每一步的returnGt都可以計算出來。這就好了。我們反復做測試，這樣很多狀態(tài)會被遍歷到，而且不止一次，那么每次就可以把在狀態(tài)下的return求和取平均。當episode無限大時，得到的數(shù)據(jù)也就接近于真實的數(shù)據(jù)。蒙特卡洛方法就是使用統(tǒng)計學的方法來取代Bellman方法的計算方法。Initialize:77JpolicytobeevaluatedVJailarbitrarystate-valuefunctionReturna(s)—anemptylist,forall5GSRepeatforever:GenerateanepiiodeusingttPoreachstate5appearingintheepisode:GyreturnfollowingthefirstoccurrenceofsAppendGtoReturns⑷average(Returns(5))上面的算法叫first-visitMC。也就是每一次的episode中state只使用第一次到達的t來計算returno另一種方法就是every-visit，就是每一次的episode中state只要訪問到就計算return求平均。所以可以看到蒙特卡洛方法是極其簡單的。但是缺點也是很明顯的，需要盡可能多的反復測試，而且需要到每一次測試結束后才來計算，需要耗費大量時間。但是，大家知道嗎？AlphaGo就是使用蒙特卡洛的思想。不是蒙特卡洛樹搜索，而是說在增強學習中使用蒙特卡洛方法的思想。AlphaGo每次也是到下棋結束，而且只使用最后的輸贏作為return。所以這也是非常神奇的事，只使用最后的輸贏結果，竟然能夠優(yōu)化每一步的走法。3使用蒙特卡洛方法來控制上面說的蒙特卡洛方法只是能夠對當前的policy進行評估。那么大家記得上一個blog說的policyiteration方法嗎？我們可以在policyiteration中使用蒙特卡洛方法進行評估，然后使用greedypolicy更新。那么依然是有兩種做法。一種就是在一個policy下測試多次，評估完全，然后更新policy，然后再做很多測試。另一種就是不完全評估，每次測試一次完就評估，評估完就更新：第一種做法:StatrtitlgStatrtitlgPolicyevaluationMonte-Carlopolicyevaluation,Q=q為Policyimprovement(-greedypolicyimprovement第二種做法:兩種做法都能夠收斂，那么顯然第二種做法的速度更快。那么再改進一點，就是改變greedypolicy中w的值，使得不斷變小趨于0,這個時候最后得到的policy就是完全的最優(yōu)policy了。這個算法就叫做GLIEMonte-CarloControl：Samplekthepisodeusingtt:{Si,?l昭一…,57}?女Foreachstate5tandactionAtintheepisode,㈤-g,4)+iJAt)+ 1(G—Q(5±,&))5海Improvepolicybasedonnewaction-valuefunctionE11/ktt—e-greedy(Q)其他變種：MonteCarlowithExploringStarts使用Q(s,a),然后使用上面說的第二種做法，一次episod就更新一次policy，而且policy直接使用Q值。Initialize,forallsE3)a€JI⑷:Q(8,q)—arbitrarytt(s)—arbitraryReturna)<-emptylistRepeatforever:ChooseSgESandAqEs.t,allpairshaveprobability>0Gcn(?rateanepisodestartingfromSq：4辦followingttForeachpairs,aappearingintheepisode:G■returnfollowingthefirstoccurrenceofstaAppendGtoRetums(s^a)Q(s.a)avcragc(/?etitm5(5j(i))Fureach&intheepisode:7T(s)argmaxuQ(s^a)Figure5.4:MonteCarloES：AMonteCarlescontrolnlgorithmassumingexploringstartsandthatepisodesMwaysterminateforallpolicies.policy的更新使用了w-greedy,目的就是能夠更好的探索整個狀態(tài)空間。Initial1叫forallsES,ftE川呂)；Q(如乜)—arbitraryRcturns{s,a)<emptylist7r(￡t|s)?anarbitraryE-softpolicylUpeatibrRverjGetieiateanepisodeu或ngtfFur《雙:hpair%a in匕heepisode：G?returnfbllawingthefirstoccurrenceufs,aAppendGtoRetumti(fi,a)Q(Mn)-avprage(Returns(s,q))FineatJi月in七he史pixiHle;A*4—UreinaxnQ回㈤FurallaE4⑷:G⑼-j-E+E/四川ifQ="{]}IU四刈ifa?A，F(xiàn)igure5,6:Ancn-j)olicyfirst-visitMCcontrolalgorithmfbr巨-softpolicies,4OffPolicyLearning那么上面的方法一直是基于當前的policy,為了探索狀態(tài)空間，采用一個次優(yōu)的策略e-greedypolicy來探索。那么是不是可以更直接的使用兩個policy。一個policy用來探索空間，也就是behaviorpolicy，另一個policy就是為了達到最優(yōu)policy，叫做targetpolicy。那么這種方法就叫做offpolicylearningoOn-policy的方法比較簡單，off-policy方法需要更多的概念和標記，比較不好理解，而且，由于behaviourpolicy和targetpolicy不相關，這種方法比較不容易收斂。但是off-policy更強大，更通用，實際上的on-policy方法就是off-policy方法的一個子集。比如，就可以使用off-policy從人類專家或者傳統(tǒng)的控制算法來學習一個增強學習模型。Initialize,fioralls€S,a€Q⑶。)Jarbitraryi—0tt(s)￥-adctcrmiTiisticpolicythatisgreedywithrcwpccttnQI^peatforever3Generatemiepimdeiisin區(qū)anysoftpolicy四：S口iSt-iiStG<0印-1FortT—LT—21…downtc0：t?J7<?+R/+i。(國，工十IVQ⑶,At)cQ⑸,At)+ [G—Q⑸,小)]4-argjnajcaQBhg](withticsbrokenconsistently)IfAt*稈(5±)thenExitForLoop川LR鳳山|即Figure5.10;AnofTpolicyevery-visitMCcuntrclLi.lgorithm.usiiigweightedimportancesampling.ThepolicyttconvergestooptimalatallencounteredstateseventhoughactionsaresehjeLedaccordingtoadifferentsoftpolicy（i,whieliumycliHJigebetweenorevenwkliinepisotles.關鍵是要找到兩個policy之間的權重關系，從而更新Q值。關于off-policylearning的部分，之后結合TD方法再做分析。小結本次blog分析了一下蒙特卡洛方法。這種基于統(tǒng)計學的方法算法簡單，但是更多的只能用于虛擬環(huán)境能進行無限測試的情況。并且state狀態(tài)比較有限，離散的最好?；谶@個方法，比如簡單的五子棋（棋盤最好小一點），就可以用這個方法來玩玩了。增強學習ReinforcementLearning經(jīng)典算法梳理3：TD方法前言在上一篇blog中，我們分析了蒙特卡洛方法，這個方法的一個特點就是需要運行完整個episode從而獲得準確的result。但是往往很多場景下要運行完整個episode是很費時間的，因此，能不能還是沿著bellman方程的路子，估計一下result呢？并且，注意這里，依然modelfree。那么什么方法可以做至U呢？就是TD（temporal-difference時間差分）方法。有個名詞注意一下：boostraping。所謂boostraping就是有沒有通過估計的方法來引導計算。那么蒙特卡洛不使用boostraping，而TD使用boostraping。接下來具體分析一下TD方法2TD與MC的不同:learnvTonlinefromexperienceunderpolicytvIncrementalevery-visitMonte-Carlo■UpdatevalueV(St)towardactualreturnGtU(Sr)—ng—M博))■Sirrplesttemporal-difTerencelearningalgorithmTD(0)Updatevalue比(5：Jtowardestimatedreturnffr+i—MSJj 斗白1%+!+、?叫%+J—qSJ)昆+14-中JiscalledtheR?0rget/—國十i卜丁爐(5葉1)?{S/)iscalledtheTDerrorMC使用準確的return來