时序差分学习 | Codeboy's Blog

形式陈述

时序差分学习是一族用采样转移逼近 Bellman 误差的方法。给定策略产生的转移 $(S_t,R_{t+1},S_{t+1})$ ，当前状态值估计为 $V$ ，一步 TD 误差是

\delta_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t),

终止状态的续值约定为零。条件于 $S_t=s$ ，在固定策略下有

\mathbb E[\delta_t\mid S_t=s] =(T^\pi V)(s)-V(s),

其中 $T^\pi$ 来自Bellman 期望方程。所以单次 $\delta_t$ 是含噪的一步残差样本，而不是价值误差本身。

表格更新只改变被访问状态；可微函数逼近 $V_w(s)$ 的半梯度版本写成

w_{t+1}=w_t+\alpha_t\delta_t\nabla_wV_w(S_t).

称“半梯度”是因为目标 $R_{t+1}+\gamma V_w(S_{t+1})$ 也依赖 $w$ ，更新却把目标暂时视为常数。若对目标一并求导，得到的是另一种 residual-gradient 方法，两者固定点与数值行为不能仅凭相似公式混同。

TD 方法还包括多步回报和资格迹：它们在纯一步 bootstrap 与等到完整蒙特卡洛回报之间分配信用。TD 是方法族，固定策略预测、动作值预测和控制算法各有不同目标；不能从“都含 $R+\gamma V$ ”推断它们具有同一收敛条件。

具体地， $n$ 步目标为

G_{t:t+n}=\sum_{k=0}^{n-1}\gamma^kR_{t+k+1} +\gamma^nV(S_{t+n}),

若回合在 $t+n$ 前终止则删除续值项。一步 TD 取 $n=1$ ，蒙特卡洛方法取直到终止的全部奖励。TD( $\lambda$ ) 的前向视图以权重 $(1-\lambda)\lambda^{n-1}$ 混合各个 $n$ 步目标；无限继续任务还需处理尾项。这个公式准确指出偏差来自最后的 bootstrap，方差来自前面的随机奖励和转移。

直觉

蒙特卡洛方法等整段轨迹结束后，拿真实累计回报纠正当前估计；TD 则把下一状态的现有估计当作临时收据，只走一步便更新。它因此能用于不断继续的任务，也能让后续信息逐步向前传播。

自举既是效率来源，也是偏差耦合来源。目标的一部分由当前估计产生，更新一个状态会改变另一个状态以后使用的标签。表格、固定策略、折扣情形中 Bellman 压缩能驯服这种耦合；叠加离策略采样和函数逼近后，这份稳定性不再自动存在。

例子与边界

设从状态 $s$ 出发，以概率 $1/4$ 立即获得奖励 $2$ 并终止；以概率 $3/4$ 获得 $0$ 并到状态 $u$ 。取 $\gamma=1/2$ ，当前估计 $V(s)=1,V(u)=2$ 。若样本终止，

\delta=2-1=1;

若样本到 $u$ ，则 $\delta=0+\frac12\cdot2-1=0$ 。因此条件期望 TD 误差为 $1/4$ 。完整 Bellman 计算也给

(T^\pi V)(s)-V(s) =\left(\tfrac14\cdot2+\tfrac34\cdot1\right)-1 =\tfrac14.

若终止样本到来且步长为 $0.4$ ，表格估计从 $1$ 更新为 $1.4$ ；单次上升一整步并不意味着真实价值恰好更大 $1$ 。

经典边界常被称为“致命三元组”：函数逼近、bootstrap 与离策略更新同时出现时，甚至线性方法也可能发散。固定步长通常只得到稳态误差邻域而非几乎必然收敛；非平稳策略让目标不动点本身移动；未访问状态没有数据支撑。深度网络中的目标网络和经验回放能改善工程稳定性，却不是一般收敛定理。

推论与应用

TD(0)是一步表格策略评估的基本算法。动作值上的 on-policy 更新产生SARSA；将下一动作换成最大化目标产生Q-learning。这三者共享 TD 误差的外形，但预测对象、采样策略和不动点不同。

在 actor–critic 中，critic 用 TD 误差近似优势信号，actor 据此更新策略。若 critic 没有在 actor 移动前充分跟踪其价值，TD 偏差会直接进入策略梯度；这正是双时间尺度分析需要控制的量。

参考资料

Richard S. Sutton, “Learning to Predict by the Methods of Temporal Differences,” Machine Learning 3, 1988, pp. 9–44.
Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, 2nd ed., MIT Press, 2018, Chs. 6 and 12.
John N. Tsitsiklis and Benjamin Van Roy, “An Analysis of Temporal-Difference Learning with Function Approximation,” IEEE Transactions on Automatic Control 42(5), 1997, pp. 674–690.

形式陈述 ​

反向链接

形式陈述