时序差分算法(一)

时序差分算法是解决BOE问题的又一大工具，它的英文是Temporal Difference Learning，通常简写为TD Learning。我们开始学习这个算法。这节课需要做一些预备。

1

Robbins-Monro算法

RM算法是随机近似(Stochastic Approximation)领域的开创性算法，由 Herbert Robbins 和 Sutton Monro 于1951年提出。它是一种迭代方法，用于在‌无法直接观测目标函数或其梯度‌的情况下，仅通过带有噪声的观测值，逐步逼近某个目标参数（如方程的根或函数的极值点）。

其算法表达如下：

如果g(w)能知道梯度的话，RM算法退化为梯度下降法：

上一节的MC ε-greedy算法里面，更新动作价值函数其实就是RM算法的一种特例：

为什么？逻辑如下：

2

引出TD算法

对上面随机变量求期望利用RM算法的思想进行拓展，可以得到求v(X)期望的RM算法：

我们加上奖励函数和状态价值函数，可以得到：

现在，我们可以给出TD learning算法的形式：

我们对红色部分进行拆分理解：

为什么绿色部分称为时序差分TD的目标，我们能推导：

蓝色部分是误差：

这里要说明的是求条件概率期望下是怎么转换的（就是上图红色到蓝色的转换）：

在第一步的表达式 δπ,t中，st+1是单次采样得到的一个具体“观测值”或“实现值”。而当我们求它的条件期望 E[⋅∣St=st]时，我们是在对“给定当前状态 st”这一条件下，所有可能出现的 st+1（及其对应的奖励）进行加权平均。因此，在期望符号内，必须将下一个状态视为一个随机变量 St+1，而不是它的某个具体取值。

综上，我们知道了在给定策略下，时序差分TD估计状态价值函数的方法。它的核心思想是利用连续时间步长（Temporal）上预测值之间的差异（Difference）来进行学习

3

理解TD公式

上面我们回答了TD算法是什么，现在我们还要回答为什么。一句话说清楚：TD算法本质在求解贝尔曼公式。

注：这一节我们介绍是某个策略下求解状态价值函数，所以说是求解贝尔曼公式(而不是贝尔曼最优公式)。也就是策略评估这一步，下一节会介绍策略改进！

回顾贝尔曼公式：

我们对贝尔曼公式使用RM算法：

黄色部分就是DT算法公式。它通过“利用序列经验”和“使用自身估计进行自举”这两种方式，摆脱了对预先知识或重置环境的依赖，从而能够在在线、增量的环境中，直接从原始经验流中学习状态价值。

4

TD VS MC

最后比较一下TD算法与MC算法的差异：

简单来说，TD（时序差分）就像“走一步看一步”，MC（蒙特卡洛）就像“走完全程再算总账”。