版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:[https://blog.csdn.net/Solo95/article/details/102577461](https://blog.csdn.net/Solo95/article/details/102577461)
这篇博客是前面一篇博客Model-Free Policy Evaluation 无模型策略评估 的一个小节,因为TD本身也是一种无模型策略评估方法。原博文有对无模型策略评估方法的详细概述。
Temporal Difference(TD) 时序差分
“if one had to identify one idea as central and novel to reinforcement learning, it would undoubtedly be temporal-difference(TD) learning.” - Sutton and Barto 2017
如果要选出对强化学习来说是最核心且最新颖的思想,那好毫无疑问是时序差分学习。-Sutton and Barto 2017 它结合了蒙特·卡罗尔(策略评估)方法和动态规划方法 不依赖模型 Boostraps和samples(采样)都进行
Bootstrapping通常被用于近似未来回报的折扣总和;Sampling通常被用于近似所有状态上的期望。 在可重复进行和非有限horizon非重复情境下都可以使用(这说明它解决了动态规划和蒙特·卡罗尔方法的缺点,博主注) 在每一次(s,a,r,s′)(s,a,r,s')(s,a,r,s′)四元组(即每一次状态变迁/每一次Observation)发生后都立即更新VVV的估计 Temporal Difference Learning for Estimating V 目标:在给定由于遵循策略π\piπ而产生的所有轮次的条件下估计Vπ(s)V^\pi(s)Vπ(s) MDP M在遵循策略π\piπGt=rt+γtt+1+γ2rt+2+γ3rt+3+...G_t=r_t+\gamma t_{t+1}+\gamma^2r_{t+2}+\gamma^3r_{t+3}+...Gt=rt+γtt+1+γ2rt+2+γ3rt+3+... Vπ(s)=EπGt∣st=sV^\pi(s)=\mathbb{E}_\piG_t|s_t=sVπ(s)=EπGt∣st=s 重温Bellman operator (如果MDP模型已知)
BπV(s)=r(s,π(s))+γ∑s′∈Sp(s′∣s,π(s))V(s′)B^\pi V(s)=r(s,\pi(s))+\gamma \sum_{s' \in S}p(s'|s,\pi(s))V(s')BπV(s)=r(s,π(s))+γs′∈S∑p(s′∣s,π(s))V(s′) 递增every-visit MC算法,使用一次对回报的采样更新估计
Vπ(s)=Vπ(s)+α(Gi,t−Vπ(s))V^\pi(s) = V^\pi(s)+\alpha(G_{i, t}-V^\pi(s))Vπ(s)=Vπ(s)+α(Gi,t−Vπ(s)) 灵感:已经有一个VπV^\piVπ的估计器,使用下面的方法估计回报的期望
Vπ(s)=Vπ(s)+α(rt+γVπ(st+1)−Vπ(s))V\pi(s) = V\pi(s) + \alpha(r_t+\gamma V^\pi(s_{t+1})-V^\pi(s))Vπ(s)=Vπ(s)+α(rt+γVπ(st+1)−Vπ(s)) Temporal Difference TD(0) Learning 时序差分学习
目标:在给定由于遵循策略π\piπ而产生的所有轮次的条件下估计Vπ(s)V^\pi(s)Vπ(s) (同上) s1,a1,r1,s2,a2,r2,...s_1,a_1,r_1,s_2,a_2,r_2,...s1,a1,r1,s2,a2,r2,...其中动作a在策略π\piπ下采样而来 最简单的采样TD学习:以趋近估计值的方式更新价值
Vπ(st)=Vπ(st)+α(rt+γVπ(st+1)−Vπ(st))V^\pi(s_t)=V^\pi(s_t)+\alpha(r_t+\gamma V^\pi(s_{t+1})-V^\pi(s_t))Vπ(st)=Vπ(st)+α(rt+γVπ(st+1)−Vπ(st))
TD target = rt+γVπ(st+1)rt+γVπ(st+1)
请注意,这里没有求和,我们是采样,所以上面的式子里只有一个下一个状态,而不是所有的未来状态。而且像动态规划那样,我们会使用先前的VπV^\piVπ估计。所以你可以把式子左边的Vπ(st)V^\pi(s_t)Vπ(st)写成Vk+1π(st)V_{k+1}^\pi(s_t)Vk+1π(st),右边的Vπ(st)V^\pi(s_t)Vπ(st)写成Vkπ(st)V_{k}^\pi(s_t)Vkπ(st)。和动态规划的区别在于,动态规划相当于更新了整个价值函数,这里相当于仅更新了价值函数的一个项。 TD error:
δt=rt+γVπ(st+1)−Vπ(st)\delta_t = r_t + \gamma V^\pi(s_{t+1})-V^\pi(s_t)δt=rt+γVπ(st+1)−Vπ(st)
Vπ(st)≈V^\pi(s_t) \approxVπ(st)≈下一个状态s′s's′上的期望 可以在一次状态变迁(s,a,r,s’)发生后立即更新价值估计 不要求必须是可重复情景 这毫无疑问是偏差估计。一般来说,当你做bootstrap的时候,它就会是有偏差估计,因为你依赖之前的估计器,而之前的估计器通常不准确,所以会带有一个偏向特定方向的bias。 而且它也可能会有很高的方差,所以它有可能既高方差也高偏差。跟蒙特·卡罗尔方法相比,通常会有较小的方差,因为bootstrapping帮助你在多样性(variability)上取了平均。它的优点在于:可以很快的更新,不需要等到当前轮次的结束并且可以使用大量的信息。
Temporal Difference TD(0) Learning Algorithm Input: α\alphaα
Initialize Vπ=0,∀s∈SV^\pi=0, \forall s \in SVπ=0,∀s∈S
Loop
Sample tuple (st,at,rt,st+1)(s_t, a_t, r_t, s_{t+1})(st,at,rt,st+1) Vπ(st)=Vπ(st)+α(rt+γVπ(st+1−Vπ(st))V^\pi(s_t)=V^\pi(s_t) + \alpha(r_t+\gamma V^\pi(s_{t+1}-V^\pi(s_t))Vπ(st)=Vπ(st)+α(rt+γVπ(st+1−Vπ(st))
TD target = rt+γVπ(st+1)rt+γVπ(st+1) α\alphaα可以是一个时间的函数,ata_tat是π(st)\pi(s_t)π(st),因为遵循策略π\piπ。
例题 手写体是解题过程。
与蒙特·卡罗尔算法不同的是,我们不会再将回报反向传播到之前访问过的状态,而是采样一个四元组(s,a,r,s′)(s,a,r,s')(s,a,r,s′)即一次变迁,更新V(s)V(s)V(s)的状态,之后不记录这次采样,也不会再改变sss的价值V(s)V(s)V(s)。
结果是按照手写体以如下顺序生成的(初始化所有状态的价值为零):
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 最后一次采样得到(s1,a1,1,#)(s_1,a_1,1,#)(s1,a1,1,#),按照TD(0)算法更新步骤算,V(s1)=1V(s_1) = 1V(s1)=1,其余由于更新它们价值时回报都是0,所以V(s)=0(except for s1)V(s)=0(except \ for \ s_1)V(s)=0(except for s1)。
TD Learning和Q-Learing高度相似。Q-Learning是在做对模型的控制,即求解最佳策略;TD-Learning基本上就是Q-Learning,但是你的策略是固定的。
实际中如果你取α=1N\alpha=\frac{1}{N}α=N1或者其他类似的形式,或者取一个很小的值,那么它将必定收敛,当你像上面的例题那样取α=1\alpha=1α=1,它绝对会震荡。α=1\alpha=1α=1其实意味着你直接忽视掉了先前的估计。
图形化描述 TD是蒙特·卡罗尔和动态规划的结合。因为,一方面它靠采样st+1s_{t+1}st+1来近似期望,而不是显式地求期望(蒙特·卡罗尔方法的思想);另一方面它使用V(st+1)V(s_{t+1})V(st+1)通过bootstrap的方式更新价值估计(动态规划的思想)。