时序差分学习

时序差分（TD）学习指的是一类无模型强化学习方法，这些方法从环境中采样，如蒙特卡洛方法，并根据当前估计值执行更新，如动态编程方法。

下面我们更正式的介绍TD学习。一般的监督学习范式可以用一个熟悉的公式来总结:

\Delta w_t=\alpha (z-V(s_t)) \Delta_w V(s_t)

其中w_t是我们在时间t时的预测函数参数的向量，α是学习速率常数，z是我们的目标值，V（s_t）是我们对输入状态s_t的预测，并且\Delta_w V（s_t）是 相对于参数w的预测的偏导数向量。 我们将价值函数（value function）称之为函数V（⋅），这是我们试图学习的函数。 这与反向传播的基础是相同的，我们需要在更新权重之前观察整个序列，因此整个序列的权重更新只是每个时间步长权重变化的总和：

w \leftarrow w+\sum_{t=1}^m \Delta w_t

TD学习的核心是任何时候的误差z - V_t都可以表示为相邻时间步长预测变化的总和，即：

z-V_t=\sum_{k=t}^m (V_{k+1} -V_k)

其中V_t是V（s_t）的简写，V（s_t）是我们对输入状态s_t的预测，V_{m + 1}定义为z，s_{m + 1}是序列中的终端状态。 在上式中的序列更新公式中替换Δwt，我们得到：

w \leftarrow w+\sum_{t=1}^m \alpha (z-V_t)\Delta_w V_t

并用差值的和代替误差（z-V_t），我们有，

w \leftarrow w+\sum_{t=1}^m \alpha \sum_{k=t}^m (V_{k+1} - V_k) \Delta_w V_t

经过一些代数变换，我们可以将上式整理得：

w \leftarrow w+\sum_{t=1}^m \qlpha(V_{k+1} - V_k)\sum_{k=1}^t\Delta_w V_t

从中我们可以提取单个时间步长的权重更新规则:

\Delta w_t=\alpha(V_{t+1}-V_t)\sum_{k=1}^t\Delta_w V_k

我们需要两次连续的预测来形成误差项，所以我们必须已经处于s_{t + 1}状态以获得我们的预测V_{t + 1}，但是学习进度正处于预测V_{t}（即w_t正被更新）。 对于已经被访问的状态来说，学习是追溯性的。当在时间t + 1出现错误时，我们通过将该误差乘以相加梯度来更新先前的权重。 实际上，TD学习的更新规则是通过使用连续预测值中的差异来更新所有先前的预测以使其更接近于当前状态的预测V_{t + 1}，因此名为时序差分学习。

Sutton（1988）称这是TD（1）程序，并引入了一个称为TD（λ）的泛化，它产生了监督学习方法无法产生的权重变化。 TD（λ）的广义公式为

\Delta w_t=\alpha(V_{t+1}-V_t)\sum_{k=1}^t\lambda^{t-k}\Delta_w V_k

我们增加了一个常数λ，它以指数方式折扣过去的梯度。 也就是说，过去n步发生的预测的梯度用λ^n加权。 当然，λ位于区间[0,1]。 我们已经看到λ= 1会产生与监督学习方法相同的权重变化。 设置λ= 0会导致公式变为：

\Delta w_t=\alpha(V_{t+1}-V_t)\Delta_w V_t

这个方程相当于用V_{t + 1}代替z的监督学习规则。因此，TD（0）产生与监督学习方法相同的权重变化，其监督方法的训练对仅以s_t作为输入并且V_{t + 1}作为目标。 从概念上讲，λ的中间值导致更新规则落在这两个极端之间。 具体来说，λ决定了在当前步骤发生的错误更新先前观测值的预测值的程度。因此，我们称总和:

e_t=\sum_{k=1}^t\lambda^{t-k}\Delta_w V_k

为时间t的eligibility trace，这是TD学习中时间信用分配的主要机制。 也就是说，给定步骤上发生的TD错误的信用（或“责备”）被分配给由资格追踪确定的先前步骤。 这是TD学习中的一个重要概念。

[描述来源：McClelland. J. L.(2015). Explorations in Parallel Distributed Processing: A Handbook of Models,Programs, and Exercises. 2nd Edition.]

发展历史

Richard Sutton于1988年介绍了一类专门用于预测的增量学习过程 - 也就是说，使用过去不完全知道的系统的经验来预测其未来行为。这即是时序差分法，对于大多数现实世界的预测问题，时间差分方法比当时的传统方法需要更少的内存和更少的峰值计算，并且它们可以产生更准确的预测。

随后，Gerald Tesauro基于Richard Sutton的TD-Lambda算法开发了TD-Gammon，这是一个神经网络，通过与自己对抗并从结果中学习，他将TD-Gammon用于步步高游戏，该程序学会了在专业人类玩家的水平上玩步步高游戏，大大超越了以前的所有计算机程序。

时序差分法随后被提议作为巴甫洛夫条件的模型，用于模拟人脑的信号变化，2003年John P. O'Doherty和Raymond J. Dolan等学者用时序差分法对此进行了实验。

2017年Richard Sutton和 Barto等学者提出了Q(σ)算法，该算法结合和推广了现有的多步 TD 控制方法，可带来更好性能。

主要事件

发展分析

瓶颈

时序差分法相较于蒙特卡洛法更快，但不够稳定，Richard S. Sutton和 Andrew G. Barto 在他们的书《Reinforcement Learning: An Introduction》中提出TD error并不精确，它有可能收敛到错误的解决方案。

未来发展方向

Q(σ) 是目前关于时序差分法较新的研究，在这个研究中没有讨论 eligibility trace 的 atomic 多步情况，但是使用复合备份（compound backup）是其自然扩展，也是未来研究的方向。时序差分法可以用在策略和离策略学习，以及生物信息研究中，如前文所述的对人类大脑信号进行模拟。

Contributor：Yuanyuan Li