Temporal Difference - 时序差分学习

Steve Wang

发布于 2019-10-22 15:00:14

4780

发布于 2019-10-22 15:00:14

                 本文链接：[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其实意味着你直接忽视掉了先前的估计。