Temporal Difference - 时序差分学习

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接: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=s]V^\pi(s)=\mathbb{E}_\pi[G_t|s_t=s]Vπ(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)][r_t+\gamma V^\pi(s_{t+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)][r_t+\gamma V^\pi(s_{t+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)。

结果是按照手写体以如下顺序生成的(初始化所有状态的价值为零):

  1. [0 0 0 0 0 0 0]
  2. [0 0 0 0 0 0 0]
  3. [0 0 0 0 0 0 0]
  4. [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的方式更新价值估计(动态规划的思想)。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券