《增强学习ReinforcementLearning经典算法梳理.docx》由会员分享，可在线阅读，更多相关《增强学习ReinforcementLearning经典算法梳理.docx（14页珍藏版）》请在三一文库上搜索。
1、前言就目前来看，深度增强学Al(DeeP ReinfOrCement Learning)中的很多方法都是基于以前的增强学习算法, 将其中的ValUe function价值函数或者POliCy function策略函数用深度神经网络替代而实现。因此，本文尝试 总结增强学习中的经典算法。本文主要参考：1； 21预备知识对增强学习有所理解，知道MDP, BeIlman方程详细可见：很多算法都是基于求解BeIlman方程而形成：ValUe IteratiOnPOIiCy IteratiOnQ-Lear ningSARSA2 POliCy IteratiOn 策略迭代POliCy IteratiOn的目
2、的是通过迭代计算ValUe (UnCtiOn价值函数的方式来使POIiCy收敛到最优。POliCy IteratiOn本质上就是直接使用BeIlman方程而得到的：r + 7Vfc()j I松+1G)=E7r+1 7t,(+) I St = s=工 r(s)工p(,r) S9那么POliCy IteratiOn 一般分成两步：POliCy EValUatiOn 策略评估。目的是 更新 ValUe FUnCtiOnPOliCy ImPrOVement策略改进。使用greedy POliCy产生新的样本用于第一步的策略评估。Stal VPOliCy evaluation EStimate vAny
3、 PoliCy evaluation algorithmPOIiCy improvement Generate , Any POliCy improvement algorithm本质上就是使用当前策略产生新的样本，然后使用新的样本更新当前的策略，然后不断反复。理论可以证明最终 策略将收敛到最优。具体算法：1 IIlitiaIiZatiOIlV(S) R and Tr(S) 人(S) arbitrarily for all s S2. POliCy EVaIUatiOnRePeat -0FOr each s S:v V(s)U(S) J ,r r s, (s) r yV() - InaX( I
4、V-V(S)I)Until V 0 (a Small POSitiVC number)3 POliCy ImPrOVementPOliCy-Stable - trueFOr each S S:a (s)Tr(S) - argmax. SI r p(, r s, a) r +()If a (s), then POliCy-StabIe - falseIf POliCy-StabIeI then StOP and return V and ; else go to 2那么这里要注意的是POIiCy evaluation部分。这里的迭代很重要的一点是需要知道State状态转移概率p.也就是说依赖于m
5、odel模型。而且按照算法要反复迭代直到收敛为止。所以一般需要做限制。比如到某一个比率或者次数就停止迭代。3 VaIUe IteratiOn 价值迭代ValUe IteratiOn则是使用BeIlman最优方程得到%(s) = mnxE凡十 1 +l%(Sf+) St = s,At = a d= n爰X 工 P(SIrls,)厂+ zyu.(s)a必然后改变成迭代形式%+(s) maxEt+ + yk(St+1) St=s,At = a=mffx P(SZrla)卩 +丁VaIUe iteration的算法如下:InitialiZe array V arbitrarily (e.g. V(S)
6、 = 0 for all S S+)RePeat -0FOr each s S: Vr(s)V(S) max 刀仆 P(Sfy rs, ) r 7V(sf) max(, IV V(S)I)Until (? (a Small POSitiVe number)OUtPUt a deterministic policy, , SUCh thatTr=argmax f8r p(s rs,a) r + 7V()那么问题来了：PoliCy IteratiOn 和 VaIUe Iteration 有什么本质区别？为什么一个叫 PoliCy iteration,个叫 VaIUe iteration 呢？原因其
7、实很好理解，POliCy iteration使用bellman方程来更新value,最后收敛的ValUe即Vn是当前POliCy下的ValUe值(所以叫做对POliCy进行评估)，目的是为了后而的POliCy improvement得到新的POliCyo而VaIUe iteration是使用bellman最优方程来更新value,最后收敛得到的ValUe即v*就是当前State状 态下的最优的ValUe值。因此，只要最后收敛，那么最优的POliCy也就得到的。因此这个方法是基于更新ValUe 的，所以叫 ValUe iterationo从上而的分析看，VaIUe iteration较之POli
8、Cy iteration更直接。不过问题也都是一样，需要知道状态转移函 数P才能计算。本质上依赖于模型，而且理想条件下需要遍历所有的状态，这在稍微复杂一点的问题上就基本不 可能了。4异步更新问题那么上而的算法的核心是更新每个状态的VaIUe值。那么可以通过运行多个实例同时采集样本来实现异步更新。而基于异步更新的思想，DeePMind岀了一篇不错的paper： ASynChrOnOUS MethOdS for DeeP ReinfOrCement Leaminge该文对于Atari游戏的效果得到大幅提升。5小结ReinfOrCement Learning有很多经典算法，很多算法都基于以上衍生。鉴
9、于篇幅问题，下一个blog再分析 基于蒙特卡洛的算法。1前言在上一篇文章中，我们介绍了基于BeIlman方程而得到的POIiCy IteratiOn和ValUe IteratiOn两种基本的算 法，但是这两种算法实际上很难直接应用，原因在于依然是偏于理想化的两个算法，需要知逍状态转移概率，也 需要遍历所有的状态。对于颯历状态这个事，我们当然可以不用做到完全遍历，而只需要尽可能的通过探索来遍 及各种状态即可。而对于状态转移槪率，也就是依赖于模型MOdeL这是比较困难的事情。什么是状态转移？就比如一颗子弹，如果我知道它的运动速度，运动的当前位置，空气阻力等等，我就可以 用牛顿运动泄律来描述它的运动
10、，进而知道子弹下一个时刻会大概在哪个位置出现。那么这个基于牛顿运动泄律 来描述其运动就是一个模型Model,我们也就可以知道其状态（空间位置，速度）的变化概率。那么基本上所以的增强学习问题都需要有一立的模型的先验知识，至少根据先验知识我们可以来确左需要多 少输入可以导致多少输岀。比如说玩Atari这个游戏，如果输入只有屏幕的一半，那么我们知道不管算法多么好， 也无法训练出来。因为输入被限制了，而且即使是人类也是做不到的。但是以此同时，人类是无需糟确的知道具 体的模型应该是怎样的，人类可以完全根据观察来推算出相应的结果。所以，对于增强学习的问题，或者说对于 任意的决策与控制问题。输入输出是由基本
11、的模型或者说先验知识决定的，而具体的模型则可以不用考虑。所 以，为了更好的求解增强学习问题，我们更关注MOdel Free的做法。简单的讲就是如果完全不知道状态转移概 率（就像人类一样），我们该如何求得最优的策略呢？本文介绍蒙特卡洛方法。2蒙特卡洛方法蒙特卡洛方法只而向具有阶段episode的问题。比如玩一局游戏，下一盘棋，是有步骤，会结朿的。而有些 问题则不一泄有结束，比如开赛车，可以无限的开下去，或者说需要特别特别久才能结束。能不能结束是一个关 键。因为只要能结朿，那么每一步的reward都是可以确定的，也就是可以因此来计算value.比如说下棋，最后 赢了就是赢了，输了就是输了。而对于结
12、束不了的问题，我们只能对于ValUe进行估讣。那么蒙特卡洛方法只关心这种能够较快结朿的问题。蒙特卡洛的思想很简单，就是反复测试求平均。如果大 家知道在地上投球计算圆周率的事情就比较好理解了。不淸楚的童鞋可以网上找找看。那么如何用在增强学习上 呢？既然每一次的episode都可以到结束，那么意味着根据： Goal: Iearn v from episodes Of experience Under POliCy Tr5, 4, R2、,Sk Tr ReCall that the return is the total discounted reward:Gt = Rt+ + URt+2 + +
13、7t1Rt ReCaIl that the VaIUe function is the expected return:v(s) = E Gt I St = s MOnte-CarlO POliCy evaluation USeS empirical mean return instead Of expected return每一步的reward都知道，也就意味着每一步的return Gt都可以计算出来。这就好了。我们反复做测试，这 样很多状态会被遍历到，而且不止一次，那么每次就可以把在状态下的return求和取平均。当episode无限大 时，得到的数据也就接近于真实的数拯。蒙特卡洛方法就是
14、使用统汁学的方法来取代BeIIman方法的讣算方法。InitiaIize: POliCy to be evaluatedV an arbitrary State-ValUe functionRetUrnS(Sy) an empty list, for all s SRePeat forever:GenCrate an episode USing FOr each State S appearing in the episode:G return following the first OCCUrrCnCC Of SAPPClI(I G to RetUrnS(S)Vr(S) J average(
15、RetUrnS(S)上而的算法叫first-visit MCO也就是每一次的episode中State只使用第一次到达的t来计算return另一种方法就是every-visit,就是每一次的episode中State只要访问到就计算return求平均。所以可以看到蒙特卡洛方法是极其简单的。但是缺点也是很明显的，需要尽可能多的反复测试，而且需要到 每一次测试结束后才来计算，需要耗费大量时间。但是，大家知道吗？ AIPhaG0就是使用蒙特卡洛的思想。不是 蒙特卡洛树搜索，而是说在增强学习中使用蒙特卡洛方法的思想。AIPhaGo每次也是到下棋结朿，而且只使用最 后的输赢作为returne所以这也是非
16、常神奇的事，只使用最后的输贏结果，竟然能够优化每一步的走法。3使用蒙特卡洛方法来控制上而说的蒙特卡洛方法只是能够对当前的POliCy进行评估。那么大家记得上一个blog说的POliCy iteration 方法吗？我们可以在POliCy iteration中使用蒙特卡洛方法进行评估，然后使用greedy POliCy更新。那么依然是有两种做法。一种就是在一个POliCy下测试多次，评估完全，然后更新policy,然后再做很多测 试。另一种就是不完全评估，每次测试一次完就评估，评估完就更新：第一种做法：POliCy evaluation MOnte-CarIO POliCy evaluation
17、, Q = qrrPOliCy improvement t. greedy POliCy improvement第二种做法：EVery episode:POliCy evaluation MOnte-CarIO POIiCy evaluation, QQqTTPOliCy improvement -greedy POliCy improvement两种做法都能够收敛，那么显然第二种做法的速度更快。那么再改进一点，就是改变greedy POliCy中的值，使得不断变小趋于0,这个时候最后得到的POliCy就是完全的最优POliCy TO这个算法就叫做GLIE MOnte-CarlO Contro
18、l： SamPIe kth episode USing : S, A, R2,., S FOr each State St and action At in the episode,N(St,州)i(St,A) + l Q(SMt) Q(St,m + 皿扛jG Q(SMJ) ImPrOVe POliCy based On new action-value funCtiOne - 1/k - -gredy(Q)英他变种：MOnte CarIO With EXPlOnng Starts,使用Q(S,a),然后使用上而说的第二种做法，一次episod就更新一次policy,而且POliCy直接使用Q
19、值。Initialize, for all s l(s): Q(s,) - arbitrary Tr(S) 1(So) s.t. all PairS have PrObability 0 Generate an episode Starting from SOMO) following TrFOr each Pair s, a appearing in the episode:G return following the first OCCUrrenCe Of s, aAPPCnd G to RetUrnS(Sti a)Q(s，) average(RetUrTis(S, )FOr each S
20、 in the episode:Tr(S) argmax Q(Sa)FigUre 5.4: MOnte CarlO ES: A MOnte CarIO COntrOl algorithm assuming exploring StartS and that episodes always terminate for all policies.POliCy的更新使用了 -greedy,目的就是能够更好的探索整个状态空间。Initialize, for all s S, A(S)IQ(s,) - arbitrarjrRCtUrnS(Sa) - CmPty IiSt7r(s) - an arbitr
21、arysoft POliCyRCPCat forever:(a) GelleratC an CPiSOdC USilIg Tr(b) FOr CaCh Pair s, a appearing in the episode:G return following the first OCClHTenCe Of s, a APPend G to RetUrTIs(s. ) Q(s，a) average(eturns(s, )(C) FOr each S in the episode: * - arg max Q(Si a) FOr all a X(s):FigUre 5.6: n On-POliCy
22、 first-visit MC COntrOl algorithm forsoft policies.4 Off POliCy Learning那么上面的方法一直是基于当前的policy,为了探索状态空间，采用一个次优的策略-greedy POIiCy来探 索。那么是不是可以更直接的使用两个POIiCya 一个POliCy用来探索空间，也就是behavior policy,另一个 POIiCy就是为了达到最优policy,叫做target POliCyO那么这种方法就叫做OffPOliCy Iearning. On-POliCy的 方法比较简单，Off-POIiCy方法需要更多的概念和标记，比
23、较不好理解，而且，由于behaviour POliCy和target POIiCy不相关，这种方法比较不容易收敛。但是Off-POIiCy更强大，更通用，实际上的On-POliCy方法就是off- POiiCy方法的一个子集。比如，就可以使用Off-POliCy从人类专家或者传统的控制算法来学习一个增强学习模 型。Initializc. for all s S1 l(s):Q(s, a) arbitrary C(Sia) 4- 0Tr(S) - a deterministic POliCy that is greedy With respect to QRePeat forever:Gener
24、ate an episode IlSing any SOft POIiCy : So, Ao, Ri,., ST-1,4-9STG-0W J 1FOr I = T- 1, T 2,. downto O:C(ShAt)C(ShAt) +WQ(SX At) - QiS, Al) + C盘AC) Q - Q(Su A)IIf At 丰兀(Sf) then EXitFOrLoOPTr(St) argrnax0 Q(SSa) (With ties broken ConSiStently)(AtSt)FigUre 5.10: An OffLPoIiCy every-vis让 MC COntrOl algo
25、rithm, USing weighted importance SarnPIillg The POliCy COnVergeS to OPtirnal at all encountered StateS even though actions are SeleCted arcording to a different SOft POliCy , WhiCh may Change between Or even Within episodes.关键是要找到两个POliCy之间的权重关系，从而更新Q值。关于Off-POliCy Iearning的部分，之后结合TD方法再做分析。小结本次blog分
26、析了一下蒙特卡洛方法。这种基于统汁学的方法算法简单，但是更多的只能用于虚拟环境能进行无限测试的情况。并且State状态比较有限，离散的最好。基于这个方法，比如简单的五子棋（棋盘最好小一点），就可以用这个方法来玩玩了。1前育在上一篇blog中，我们分析了蒙特卡洛方法，这个方法的一个特点就是需要运行完整个episode从而获得 准确的resulto但是往往很多场景下要运行完整个episode是很费时间的，因此，能不能还是沿着bellman方程 的路子，估计一下result呢？并且，注意这里，依然mOdel freeu那么什么方法可以做到呢？就是TD（temporal-difference 时间差分
27、）方法。有个名词注意一下：boostraping.所谓boostraping就是有没有通过估计的方法来引导计算。那么蒙特卡 洛不使用 boostraping,而 TD 使用 boostrapingu接下来具体分析一下TD方法2 TD与MC的不同 Goal: Iearn v Online from experience Under POliCy Tr InCremental every-visit MOnte-CarIO UPdate VaIUe V(St) toward actual return GtV(St)V(Sr)+ (Gr-V(St) SimPleSt temporal-differ
28、ence Iearning algorithm: TD(O) UPdate VaIUe V(St) toward estimated return Rz - ,V(Srn)V(St) V(St) + (Rf + 7V(Sf4-) - V(Sf) Rr+ +7V(Sr+1) is CaIIed the TD target无=Rt+1 +7V(S4-1) 一 V(5t) is CalIed the TD errorMC使用准确的return来更新value,而TD则使用BeIlman方程中对VaIUe的估计方法来估计value,然后将估计值作为VaIUe的目标值进行更新。也因此，估计的目标值的设泄
29、将衍生出种TD下的算法。那么TD方法的优势有什么呢？每一步都可以更新，这是显然，也就是0nline learning,学习快；可以而对没有结果的场景，应用范围广不足之处也是显而易见的，就是因为TD target是估计值，估计是有误差的，这就会导致更新得到VaIUe是 有偏差的。很难做到无偏估计。但是以此同时，TD target是每一个SteP进行估计的，仅最近的动作对苴有影 响，而MC的result则受到整个时间片中动作的影响，因此TD target的方差VananCe会比较低 也就是波动性 小。还是放一下DaVid SilVer的总结吧： MC has high VarianCet ZerO
30、 bias GOOd COnVergenCe PrOPertieS (even With function approximation) NOt Very SenSitiVe to initial VaIUe Very SimPIe to UnderStand and USe TD has IOW VarianCer SOme bias USUaIIy more efficient than MC TD(O) COnVergeS to v(s) (but not always With function approximation) MOre SenSitiVe to initial VaIU
31、e那么DaVid SilVer的PPt中有三张图，很淸楚的对比了 MC, TD以及DP的不同：MOnte-CarlO BaCkUPV(St) R)TemPOraI-DifferenCe BaCkUP从上而可以很淸楚的看到三者的不同 DP就是理想化的情况，遍历所有。MC现实一点，TD最现实，但是TD也最不准确C但是没关系，反复迭代之下，还是可以收敛的。整个增强学习算法也都在上而的范畴里：Unified VieW Of ReinfOrCement Learning3 TD算法Input: the POliCy to be evaluatedInitialiZe Vr arbitrarily (e.
32、g., V(3) = 0, S+)RePCat (for CaCh episode):InitiaIiZe SRePCat (for CaCh StCP Of episode):A - action given by for S Take action A, ObSerVe R, SrV(S) V(S) + aR + W(SJ - V(S) SSUntil S is terminalFiglIre G.l: TabUlar TD(O) for estimating .这只是TD (0)的估计方式，显然可以拓展到n-StePO就是讲TD-target再根据bellman方程展开。 再下来的思想，
33、就是可以把TD (I)和TD (j)合在一起求个平均吧。再下来就是把能算的TD (i)都算一遍，每一个给个系数，总和为1,这就是TD()GA(I-入)亡心少) H=I4 SARSA算法SARSA算法的思想很简单，就是增加一个A,下一步的A,然后据此来估计Q(s,a)oInitialiZe Q(s.)5s S, (s)5 arbitrarily, and Q(IerminaI-State ) = 0 RePeat (for eacl episode):InitialiZe SChOOSe A from S USing POliCy (IeriVed from Q (c.g., e-grcedy)
34、RePeat (for each SteP Of episode):TakC action 4, ObSCrVC R. SfChOOSC A! from St IlSing POliCy derived from Q (c.g., c-grccdy)Q(S, A) J Q6) + E + yQ(S, Af) - Q(S, A)S- S,; - A,;Until S is terminalFigUrC 6.5: SarSa: An On-POliCy TD COntrOl algorithm.之所以算法称为SARSA就是指一次更新需要用到这5个量。5 Q-Learning 算法著名的 Q-Lea
35、rningoInitiaIiZe Q(.s,),Vs 8, l(s), arbitrarily, and Q(terminal-state, ) = RCPCat (for CaCh episode):InitialiZe SRCPCat (for CaCh StCP Of episode):ChOOSe A from S USing POliCy derived from Q (e.g., e-greedy) Take action A, ObSerVe R) SQ(S, A) - Q(S, A) + aR + y max Q(SSa) 一 Q(S, A) s-oUiItil S is te
36、rminalFigUre 6.7: Q-Iearning: An OffLPOliCy TD COntrOl algorithm.这里直接使用最大的Q来更新。为什么说SARSA是On-POliCy而Q-Learning是Off-POliCy呢?因为SARSA只是对POliCy进行估讣，而Q-Leaming的Q则是通往最优。6 DOUble Q-LearningQ-Learning可能会出现对Q值过度估讣的问题，DOUble Q-Learning可以解决这个问题:ImtiaIiZe Q(s,) and Q2(8,)M S, (s), arbitrarilyInitialiZe Q(termina
37、lstate. ) = Q2terminalstate. ) = 0 IlePeat (for each episode):InitiaIiZe SRePeat (for each SteP Of episode):ChOoSe A from S USing POliCJr derived from Q and Qq (e.g.,greedy in QI + Q) Take action /1, ObSCrVC Rl S,With 0.5 Probabilility:QI(S, A) J Ql(SI ) + (fl + 也2(&, argmax QI(Sfi) 一 Q1(S, A) else:
38、2(S, A) - Q2S., A) + all + 7Q1 (5 argmaxa Q2S ) -Q2(SM) S-S,Until S is terminalFigUrC 6.12: DOUbIe Q-Iearning.使用两个Q交替更新。7多种方法比较FUII BaCkUP (DP)SamPIe BaCkUP (TD)CBeIIman EXPeCtatiOnO O OCEqUatiOn for v(s)IteratiVe POliCy EValUatiOnTD LearningT5QKBeIIman EXPeCtatiOn702I /IKEqUatiOn for q-(s.a)Q-POIiC
39、y IteratiOnSarSae.0.BeIIman OPtirnalityWZf ANEqUatiOn for q. (s, a)Q-ValUe IteratiOnQ-LearningFUII BaCkUP (DP)SamPIe BaCkUP (TD)IteratiVe POliCy EVaIUatiOnV(s)-ER + 7V(S,) sTD LearningI V(S)R+ yV(Sf)Q-POIiCy IteratiOnQ(s,a)R + g(SM) I s,aI SarSaI Q(SIA) R + 7Q(S,)Q-VaIUe IteratiOnQ-LearningQ(s： a) *- E? + 7 ma Q(S,y) s, aQ(S, A) ? + 7 max Q(Ss a,)9,eAWhere xAyx-x + a(y x)由上而两图可以理解TD, Sarsa,和Q-Leaming的算法来源，本质上都是基于BeIlman方程。可以这么理解：BeIlman方程是一种理想条件的解法，而这些方法则是放弃理想准确度而形成的可实现方 法。小结本文梳理了 TD相关的几个算法。TD算法特别是TD（入）方法引出了 eligibility trace （翻译做资格迹不知可 否），这部分内容留待之后分析。