增强学习ReinforcementLearning经典算法梳理

1、增强学习ReinforcementLearning经典算法梳理1：policyandvalueiteration前言就目前来看，深度增强学习(DeepReinforcementLearning)中的很多方法都是基于以前的增强学习算法，将其中的valuefunction价值函数或者Policyfunction策略函数用深度神经网络替代而实现。因此，本文尝试总结增强学习中的经典算法。本文主要参考：ReinforcementLearning:AnIntroduction;2ReinforcementLearningCoursebyDavidSilver1预备知识对增强学习有所理解，知道MDP,Bel

2、lman方程详细可见：DeepReinforcementLearning基础知识(DQWT面)很多算法都是基于求解Bellman方程而形成：ValueIterationPolicyIterationQ-LearningSARSA2PolicyIteration策略迭代PolicyIteration的目的是通过迭代计算valuefunction价值函数的方式来使policy收敛到最优。PolicyIteration本质上就是直接使用Bellman方程而得到的："+1=EkR+工+ISi=s口那么PolicyIteration一般分成两步：PolicyEvaluation策略评估。目的是

3、更新ValueFunctionPolicyImprovement策略改进。使用greedypolicy产生新的样本用于第一步的策略评估。PolicyevaluationEstimatevAnypolicyevaluationalgorithmPolicyimprovementGenerate7rz>ttAnvpolicyimprovementalgorithm本质上就是使用当前策略产生新的样本，然后使用新的样本更新当前的策略，然后不断反复。理论可以证明最终策略将收敛到最优。具体算法：1. Initialization6Randtt(5)6A(h)arbitrarilyforallsS2.

4、 PolicyEvaluationRepeat-0ForeachseS:v-VsV(s)一£凡内(另，小尸(3)卜+W(s。A什niax(A,|vV()|)untilA<0(asmallprxdtivenuinber)3. PolicyImprovementpolicy-stableJtrueForeachsS:a一开(s)tt(s)cargmaxfl£台yp(J,r|s,a)r+WIfq，7T(s),thenpolicy-stablefalseIfpolicy-stable,thenstopandreturnVandtt;elsegoto2那么这里要注意的是poli

5、cyevaluation部分。这里的迭代很重要的一点是需要知道state状态转移概率p。也就是说依赖于model模型。而且按照算法要反复迭代直到收敛为止。所以一般需要做限制。比如到某一个比率或者次数就停止迭代。3ValueIteration价值迭代ValueIteration则是使用Bellman最优方程得到=luajjEa+i+制.(5计)|$£二34=口=一£郎仙卜+然后改变成迭代形式跺+L(s)+gMSt+1)I=“Jvalueiteration的算法如下:InitializearrayVarbitrarily(eg,V(5)Qforalls5+)Rcjicat-0F

6、oreach日W5:vyV(-s)V一仃】的£/产p(sra,(r)r+W(s')A4-max(a|廿-产I)untilii<(hstnallpositivenumber)Outputadetenninisticpolicy,suchthattt®=argrriaxapsf>国门)卜+。V(吟那么问题来了：PolicyIteration和ValueIteration有什么本质区另1J?为什么个叫policyiteration,个叫valueiteration呢？原因其实很好理解，policyiteration使用bellman方程来更新value,最后收

7、敛的value即vn是当前policy下的value值（所以叫做对policy进行评估），目的是为了后面的policyimprovement得到新的policy。而valueiteration是使用bellman最优方程来更新value,最后收敛得到的value即v?就是当前state状态下的最优白vvalue值。因此，只要最后收敛，那么最优的policy也就得到的。因此这个方法是基于更新value的，所以叫valueiteration。从上面的分析看，valueiteration较之policyiteration更直接。不过问题也都是一样，需要知道状态转移函数p才能计算。本质上依赖于模型，而

8、且理想条件下需要遍历所有的状态，这在稍微复杂一点的问题上就基本不可能了。4异步更新问题那么上面的算法的核心是更新每个状态的value值。那么可以通过运行多个实例同时采集样本来实现异步更新。而基于异步更新的思想，DeepMind出了篇不错的paper：AsynchronousMethodsforDeepReinforcementLearning。该文又于Atari游戏的效果得到大幅提升。5小结ReinforcementLearning有很多经典算法，很多算法都基于以上衍生。鉴于篇幅问题，下一个blog再分析基于蒙特卡洛的算法。增强学习ReinforcementLearning经典算法梳理2：蒙特

9、卡洛方法1前言在上一篇文章中，我们介绍了基于Bellman方程而得到的PolicyIteration和ValueIteration两种基本的算法，但是这两种算法实际上很难直接应用，原因在于依然是偏于理想化的两个算法，需要知道状态转移概率，也需要遍历所有的状态。对于遍历状态这个事，我们当然可以不用做到完全遍历，而只需要尽可能的通过探索来遍及各种状态即可。而对于状态转移概率，也就是依赖于模型Model,这是比较困难的事情。什么是状态转移？就比如一颗子弹，如果我知道它的运动速度，运动的当前位置，空气阻力等等，我就可以用牛顿运动定律来描述它的运动，进而知道子弹下一个时刻会大概在哪个位置出现。那么这个基

10、于牛顿运动定律来描述其运动就是一个模型Model,我们也就可以知道其状态（空间位置，速度）的变化概率。那么基本上所以的增强学习问题都需要有一定的模型的先验知识，至少根据先验知识我们可以来确定需要多少输入可以导致多少输出。比如说玩Atari这个游戏，如果输入只有屏幕的一半，那么我们知道不管算法多么好，也无法训练出来。因为输入被限制了，而且即使是人类也是做不到的。但是以此同时，人类是无需精确的知道具体的模型应该是怎样的，人类可以完全根据观察来推算出相应的结果。所以，对于增强学习的问题，或者说对于任意的决策与控制问题。输入输出是由基本的模型或者说先验知识决定的，而具体的模型则可以不用考虑。所以，为了

11、更好的求解增强学习问题，我们更关注ModelFree的做法。简单的讲就是如果完全不知道状态转移概率（就像人类一样），我们该如何求得最优的策略呢？本文介绍蒙特卡洛方法。2蒙特卡洛方法蒙特卡洛方法只面向具有阶段episode的问题。比如玩一局游戏，下一盘棋，是有步骤，会结束的。而有些问题则不一定有结束，比如开赛车，可以无限的开下去，或者说需要特别特别久才能结束。能不能结束是一个关键。因为只要能结束，那么每一步的reward都是可以确定的，也就是可以因此来计算value。比如说下棋，最后赢了就是赢了，输了就是输了。而对于结束不了的问题，我们只能对于value进行估计。那么蒙特卡洛方法只关心这种能够较

12、快结束的问题。蒙特卡洛的思想很简单，就是反复测试求平均。如果大家知道在地上投球计算圆周率的事情就比较好理解了。不清楚的童鞋可以网上找找看。那么如何用在增强学习上呢？既然每一次的episode者B可以至ij结束，那么意味着根据：aGoal:learn廿芥fromepisodesofexperienceunderpolicytt5l,5土7T Recallthatthereturnisthetotaldiscountedreward:G-/+L+T&+2+7r-1r Recallthatthevaluefunctionistheexpectedreturn:%(s)=EttGt|5f=s

13、Monte-Carlopolicyevaluatronusesempiricalmeanreturninsteadofexpectedreturn每一步的reward都知道，也就意味着每一步的returnGt都可以计算出来。这就好了。我们反复做测试，这样很多状态会被遍历到，而且不止一次，那么每次就可以把在状态下的return求和取平均。当episode无限大时，得到的数据也就接近于真实的数据。蒙特卡洛方法就是使用统计学的方法来取代Bellman方法的计算方法。Initialize:tv1policytobeevaluatedV4-tuiirbitrarystate-valin?function

14、Returns(s)anemptylist,forall55RepentRin?vet:Generatoanepisodeusing/Fbreachstatesappearingintheepisode：G-returnfollowingthefiratoccurrenceofaAppendGtoReturnss)V(«)<.verage(Returns)上面的算法叫first-visitMC。也就是每一次的episode中state只使用第一次到达的t来计算return。另一种方法就是every-visit,就是每一次的episode中state只要访问到就计算return求

15、平均。所以可以看到蒙特卡洛方法是极其简单的。但是缺点也是很明显的，需要尽可能多的反复测试，而且需要到每一次测试结束后才来计算，需要耗费大量时间。但是，大家知道吗？AlphaGo就是使用蒙特卡洛的思想。不是蒙特卡洛树搜索，而是说在增强学习中使用蒙特卡洛方法的思想。AlphaGo每次也是到下棋结束，而且只使用最后的输赢作为returno所以这也是非常神奇的事，只使用最后的输赢结果，竟然能够优化每一步的走法。3使用蒙特卡洛方法来控制上面说的蒙特卡洛方法只是能够对当前的policy进行评估。那么大家记得上一个blog说白ppolicyiteration方法吗？我们可以在policyiteration中

16、使用蒙特卡洛方法进行评估，然后使用greedypolicy更新。那么依然是有两种做法。一种就是在一个policy下测试多次，评估完全，然后更新policy,然后再做很多测试。另一种就是不完全评估，每次测试一次完就评估，评估完就更新：第一种做法：PolicyevaluationMonte-Carlopolicyevaluation,Q=qrPolicyimprox/mentf-greedypolicyimprovement第二种做法:Everyepisode:PolicyevaluationMonte-Carlopolicyevaluation,QkqPolicyimprovementE-gre

17、edypolicyimprovement两种做法都能够收敛，那么显然第二种做法的速度更快。那么再改进一点，就是改变greedypolicy中？的值，使得不断变小趋于0,这个时候最后得到的policy就是完全的最优policy了。这个算法就叫做GLIEMonte-CarloControl: Samplekthepisodeusingtt:5上4八835丁五 ForeachstateStandactionAtintheepisode,N,4)N(S/J+lQ国4)J。(配4)+A(Q_Q(5，»阳I'mAt) Improvepolicybasedonnewaction-value

18、function1/&7rc-grccdy(O)其他变种：MonteCarlowithExploringStarts,使用Q(s,a),然后使用上面说的第二种做法，一次episod就更新一次policy,而且policy直接使用Q值。Initialize,forallhW&.W人(s)：Q(S,C1)arbitrary7t(s)<arbitraryReturn(fita)emptylistRepeatforever:Choose5。E3andAqEJI(Sq)s.t.allpairshaveprobability>0Generateanepisodestarting

19、fromSo,Ao,followingnForeachpairs*appearingintheepisode:Greturnfollowingthefirstoccurrenceoffi.aAppendGtoRL.turns8ya)a)-average(展加导)Foreachsintheepisode:tt(s)<argmaxQ(n,q)Figure54:MonteCarloES:AMonroCarlocontrolalgorithmassumingexploringstartsandthatepisodesalwaysterminateforallpolicies.policy的更新使

20、用了？-greedy,目的就是能够更好的探索整个状态空间。Initialize,forallsE5.&FX(s):arbitrary1emptylistnas)-anarbitrarye-softpolicyHrptviffbrevi'r；3) Gutivratcanepisodeusingr(b) Foreachjyairs.aajjpearinf；iiitheejiisude:GJreturnfbliowingth户firstoccurrncpof乐"AppendGtoReturnsa)QI*,a)ritv(jragii(fleturnnA,fij)(c) For

21、Fach丹intheepisode:A"<arxniaxqQ(5,fi)7T（09）l-e+/X(fl)|ifa=.4-ifa/A"Figure5.6:Anou-policyfirst-visitMCcuntmlalguritlimfur£-&oftpolicies.4OffPolicyLearning那么上面的方法一直是基于当前的policy,为了探索状态空间，采用一个次优的策略？-greedypolicy来探索。那么是不是可以更直接的使用两个policyo一个policy用来探索空间，也就是behaviorpolicy,另一个policy就是为了

22、达到最优policy,叫做targetpolicy。那么这种方法就叫做offpolicylearning。On-policy的方法比较简单，off-policy方法需要更多的概念和标记，比较不好理解，而且，由于behaviourpolicy和targetpolicy不相关，这种方法比较不容易收敛。但是off-policy更强大，更通用，实际上的on-policy方法就是off-policy方法的一个子集。比如，就可以使用off-policy从人类专家或者传统的控制算法来学习一个增强学习模型。Initialize,forallES,uea)：Q(fljfl)arbitraryC(*iq)J。ir

23、(丹)<adetRFininist.ic?olicythatisgreedywithrRS>ecttoQRepeatforever；Generateanepisodeusinganysoftpolicy挥R11：6丁'-11再.7)./Jj'lSrFort=T1,T2,»,downto0:G<+凡+i呐&)阴+WQ,A)CQ,4)+意而G-Q,A)1tt(S()+argmaxQfSt.fl)(withtictsbrokouconsistently)IfAt7r(SjthenExitForLoopFigure5.1(J：An。也policyev

24、ery-visitMCcontrolalgorithrn+usingweightediiiiportance1NatnpUng.ThepolicyttconvergesL<joptimalatallrncountcrcdslateseventhoughactictiHHireselectedaccordingrondifferentsoftpolicyfi.whichmaychangebetweenorevenwithin白pEjtles.关键是要找到两个policy之间的权重关系，从而更新Q值。关于off-policylearning的部分，之后结合TD方法再做分析。小结本次blog分

25、析了一下蒙特卡洛方法。这种基于统计学的方法算法简单，但是更多的只能用于虚拟环境能进行无限测试的情况。并且state状态比较有限，离散的最好。基于这个方法，比如简单的五子棋（棋盘最好小一点），就可以用这个方法来玩玩了。增强学习ReinforcementLearning经典算法梳理3:TD方法1前言在上一篇blog中，我们分析了蒙特卡洛方法，这个方法的一个特点就是需要运行完整个episode从而获得准确的resulto但是往往很多场景下要运行完整个episode是很费时间的，因此，能不能还是沿着bellman方程的路子，估计一下result呢？并且，注意这里，依然modelfree。那么什么方法可

26、以做到呢？就是TD（temporal-difference时间差分）方法。有个名词注意一下：boostrapingo所谓boostraping就是有没有通过估计的方法来引导计算。那么蒙特卡洛不使用boostraping,而TD使用boostraping。接下来具体分析一下TD方法2TD与MC的不同 Gomi:Iearnvronline£romexperienceunderpoicy订 Incrementalcvery-visitMonte-Carla Updatev3lue叭5JtowardJrtt/a/return©火5j-仪&)+仃(a-鹏5») Si

27、mplesttemporaI-differencelearningalgorithm:TD(0) UpdatevalueV(Sf)towardestimatedreturn雁门+7叭&+【)V(St)-iV(St+.x)- &t+-yV(Sf+i)kulledtheTDtarget 尾二周十二十彳V(5-ijV(Sj)itcalledtheTDerrorMC使用准确的return来更新value,而TD则使用Bellman方程中对value的估计方法来估计value,然后将估计值彳为value的目标值进行更新。也因此，估计的目标值的设定将衍生出各种TD下的算法。那么TD方法的优

28、势有什么呢？每一步都可以更新，这是显然，也就是onlinelearning,学习快；可以面对没有结果的场景，应用范围广不足之处也是显而易见的，就是因为TDtarget是估计值，估计是有误差的，这就会导致更新得到value是有偏差的。很难做到无偏估计。但是以此同时，TDtarget是每一个step进行估计的，仅最近的动作对其有影响，而MC的result则受到整个时间片中动作的影响，因此TDtarget的方差variance会比较低，也就是波动性小。还是放一下DavidSilver的总结吧： WChashighvariance,zerobias Goodconvergenceproperties

29、(evenwithfunctionappraximition) Natverysensitivetoinitialvdlufi Verysimpletounderstandanduse TOhaslowvariance,somebi” UsuallymoreefficientthanMC TD(0)convergesto(s) (butnotalwayswithfunctionppnCKimation) MoresensitivetoinitialvlueMonte-CarloBackup那么DavidSilver的ppt中有三张图，很清楚的对比了MC,TD以及DP的不同:TemporaI-D

30、ifferenceBackup+n的+=也£+)-¥)DynamicProgrammingBackup从上面可以很清楚的看到三者的不同。DP就是理想化的情况,遍历所有。MC现实一点，TD最现实,但是TD也最不准确。但是没关系，反复迭代之下，还是可以收敛的。整个增强学习算法也都在上面的范畴里:UnifiedViewofReinforcementLearnir>g3TD算法Input:thepolicytobeevuluwtedInitializeV(s)arbitrarily(e,g,V(a)=0lVj5+)Repeat(foreachepisode1)：Initial

31、izeSRcpauit(forwxehstepofcpiyodc)：Aactio!)iveubyttfic)rSTakeactionA,observeR*S'V(5)1仪5)+aR+7/(力-VSsyuntilSisterminalFigure6.1：labularTD;forestinialiug%这只是TD(0)的估计方式，显然可以拓展到n-step。就是讲TD-target再根据bellman方程展开。总和为1,这就是TD(入)再下来的思想，就是可以把TD(i)和TD(j)合在一起求个平均吧。再下来就是把能算的TD(i)都算一遍，每一个给个系数,G=口一文*】Ga=L4 SARS

32、A算法SARSA算法的思想很简单，就是增加一个A,下一步的A,然后据此来估计Q(s,a)。InitializeQ(«,a)TW以0WX(e),arbitrarily,andstate,)=0Repeat(forcactiepisode:InitializeSChooHCAfromSusingpolicyderivedfromQ(e.g“r-greedy)Repeat(foreachstepofepisode)：Takeaction儿observeR,SfChooseAffromSfusingpolicyderivedfromQ(ag-c-greedy)Q(S,A)Q(S,)+乖+EF

33、-Q(SM)S-S'月一；untilSisterminalFigure6+5:Sarsa:Anon-policyTl)controlalgorithni.之所以算法称为SARSA,就是指一次更新需要用到这5个量。5 Q-Learning算法著名的Q-Learning。InitializeQ®a).VsW&&W人(5)，arbitrarily,atidQ(teTtninal-state,-)=0Repeat(foreachepisode)：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呢?因为SARSA只是对policy进行估1t,而Q-Learning的Q则是通往最