RL5-TD

时间差分（Temporal-Difference）概述

蒙特卡洛法的求解需要等待每次实验结束才能进行，这导致蒙特卡洛法在现实环境中的学习效率难以满足实际任务需求。

• 和蒙特卡洛学习一样，它也从Episode学习，不需要了解模型本身，是免模型（Model Free）的。

• 但它可以学习不完整的Episode(回合)，通过合理的引导（bootstrapping）猜测Episode的结果，计算当前的价值函数，同时持续更新这个猜测，而MC是在每次试验结束之后才能计算响应的价值函数。MC的区别在这！！！

  • 先估计某状态在该状态序列完整后可能得到的收获
  • 在此基础上利用前文所述的累进更新平均值的方法得到该状态的价值
  • 通过不断的采样来持续更新这个价值

Bootstrapping（自举）概念

“Bootstrapping”这个概念表示在当前值函数的计算过程中，会利用到后续的状态值函数或动作值函数，即利用到后续的状态或<状态-动作>对.
蒙特卡洛法对多次采样后经验轨迹的奖励进行平均，并将平均后的奖励作为累积奖励的近似期望。需要特别注意的是，累积奖励的平均计算是在一个经验轨迹收集完成之后开展。其更新过程中：

MC利用实际的奖励作为目标来更新状态值，并且状态值的更新过程能够增量式地进行。其中，为学习率，为执行了个时间步后的实际奖励，是基于某一策略状态值的无偏估计。

TD(0)

在时间差分学习中，算法在估计某一状态值时，使用关于该状态的即时奖励和下步的状态值乘以衰减系数进行更新，最简单的时间差分法称为，其更新过程如下：

其中为时间差分目标（TD Target），也称为目标项，其代替了MC中的，其表示预测的实际奖励，通常后面括号里的整体我们称为误差项，因此MC和TD的主要区别就是目标项的不同。

这里定义时间差分误差(TD Error)为，其用于状态值函数的估计。

此外，关于时间差分目标（TD Target），主要分为两种情况：

• 普通时间差分目标：即，基于下一状态的预测值计算当前奖励预测值，是当前状态实际价值的有偏估计。
• 真实时间差分目标：即，基于下一时间步状态的实际价值计算当前奖励预测值，是当前状态实际价值的无偏估计。

时间差分法类似于蒙特卡洛法，需要模拟多次采样的经验轨迹来获得期望的状态值函数估计。当采样足够多时，状态值函数的估计便能够收敛于真实的状态值。

无偏估计（Unbiased Estimate）

无偏估计指在多次重复实验下，计算的平均数接近估计参数的真实值。

实际上，无偏估计是用样未统计量来估计总体参数的一种无偏推断，估计量的数学期望等于被估计参数的真实值。此估计量被称为被估计参数的无偏估计，即具有无偏性性，是一种用于评价估计量优良性的准则。

在MC方法中使用的回报就是对的无偏估计。

真实时间差分目标也是对的无偏估计。

有偏估计（Biased Estimate）

有偏差计与无偏估计相反，是指由样本值求的估计值与待估计参数的真实值之间有系统误差，其期望值不是待估参教的真值。

时间差分目标是对的有偏估计。

MC 和 TD 的优劣

• TD可以在最终结果出来前学习

  • TD可以在每一步在线学习，每一个时间步之后就可以进行学习。

  • MC必须等到片段的最后，必须等到当前幕结束。

• TD也可以在没有最终输出的场景下进行学习。

  • TD可以从不完整的序列中学习

  • MC必须从完整的序列中学习

  • TD在持续的环境中工作（没有终止）

  • MC只在片段式环境中工作（有终止）

• MC 高方差，0偏差

  • 好的收敛性质，因为Gt是True Value，所以一直向着True Value更新.即时在使用函数估计器的时候(详见第六课)

  • 对初始价值不是很敏感,正如上面所说，MC一直向着True Value更新，所以不是很在意初始值。

  • 理解使用简单

• TD低方差，一些偏差

  • TD通常比MC更高效

  • TD（0）更新至，但是在使用函数估计器的时候却不一定保证收敛(详见第六课)

  • TD对初始化的价值更敏感，与MC相对，也是因为TD target是有偏估计

• TD算法有奖励值和状态转移作为更新的驱动力；MC算法只有奖励值作为更新的驱动力

• MC 收敛于最小化观察回报的最小二乘误差，它不开发马尔科夫性质，因此在非马尔科夫环境下更有效

• TD 收敛于最大似然马尔科夫模型，它开发马尔科夫性质，所以通常在马尔科夫环境下更有效

由上面得知，MC无偏差但是高方差，TD低方差，但是有一些偏差，因此自然的就想到这是一个Trade-off，权衡问题，因此一般有个折中的办法，后面会说到。

TD(λ)，λ∈[0,1]

先前所介绍的TD算法实际上都是TD(0)算法。
TD(0)表示采样1步，在当前状态下往前多看1步，利用 和来估。MC算法则是相当于把当前时刻 t 到无穷的所有的奖励都加起来了。
如果介于两者之间的target，比如在当前状态下往前多看几步更新状态价值会怎样？这就引入了n-step的概念。

n-step预测指从状态序列的当前状态 开始往序列终止状态方向观察至状态 ，使用这 n 个状态产生的即时奖励 ()以及状态 的预估价值来计算当前状态 的价值。

这里，TD target 也由2部分组成，已走的步数使用确定的即时reward，剩下的使用估计的状态价值替代。

λ-return就是权重为次方的return，这个权重第一次为1-λ，然后以λ一直衰减，λ为0-1之间。 总的权重之和为1。

前向认识TD(λ) Forward-view TD(λ)

引入了λ之后，会发现要更新一个状态的状态价值，必须要走完整个Episode获得每一个状态的即时奖励以及最终状态获得的即时奖励。这和MC算法的要求一样，因此TD(λ)算法有着和MC方法一样的劣势。但是Backward View TD(λ)不用，它可以在每个时间步更新。

后向认识TD(λ) Backward View TD(λ)

资格轨迹的提出是基于一个信用分配（Credit Assignment）问题的，一局游戏，输了或者赢了，哪一步起到了关键作用？这就是一个信用分配问题。对于小鼠问题， 小鼠先听到三次铃声，然后看见灯亮，接着就被电击了，小鼠很生气，它仔细想，究竟是铃声导致的它被电击， 还是灯亮导致的呢？如果按照事件的发生频率来看，是铃声导致的，如果按照最近发生来看，那就是灯亮导致的，但是，更合理的想法是， 这二者共同导致小鼠被电击了，于是小鼠为这两个事件分别分配了权重，如果某个事件s发生， 那么s对应的资格迹的值就加1，如果在某一段时间s未发生，则按照某个衰减因子进行衰减。

我们可以将资格迹理解为一个权重，状态s被访问的时间离现在越久远，其对于值函数的影响就越小， 状态s被访问的次数越少，其对于值函数的影响也越小。

• 频率启发 Frequency heuristic：将原因归因于出现频率最高的状态
• 就近启发 Recency heuristic：将原因归因于较近的几次状态

通过一系列的说明前向视角和后向视角的 TD(λ) 等价

MC 、TD、 DP三者的区别:

（1）DP是在当前状态下直接算期望，把下一步的所有可能状态进行加和；
（2）MC是在当前状态下选取一条支路，对该支路一走到底来得到该支路的奖励；
（3）TD是在当前状态下往前走一步，只走一步，既需要计算期望又需要采样得到的奖励结果。

• 如果 TD 需要更广度的 update，就变成了 DP（因为 DP 是把所有状态都考虑进去来进行更新）。
• 如果 TD 需要更深度的 update，就变成了 MC。