时序差分学习 | 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),

终止状态的续值约定为零。令 $\mathcal F_t$ 记录本次转移采样前的历史，包括 $S_t$ 与当前估计 $V$ ； $V$ 可以由过去数据产生，但在这次更新中保持不变。在固定策略和 Markov 转移下，有

\mathbb E[\delta_t\mid\mathcal F_t] =(T^\pi V)(S_t)-V(S_t).

其中 $T^\pi$ 来自Bellman 期望方程。若 $V$ 是预先固定的确定函数，也可只条件于 $S_t=s$ ，写成右端在 $s$ 处的值。对随历史变化的估计，却不能省掉历史条件而让右端仍保留尚未平均的随机 $V$ 。因此单次 $\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$ ，蒙特卡洛方法取直到终止的全部奖励。对在 $T$ 终止的回合，冻结估计后的前向 $\lambda$ 回报是

G_t^\lambda=(1-\lambda)\sum_{n=1}^{T-t-1}\lambda^{n-1}G_{t:t+n}+\lambda^{T-t-1}G_t,

其中 $G_t$ 为完整终止回报，最后一项收拢剩余权重，保证权重和为 $1$ 。 $\lambda=0$ 得一步 TD， $\lambda=1$ 得蒙特卡洛；无限继续任务则需相应的收敛条件。bootstrap 误差来自末端估计，采样波动来自奖励与转移，增大步数并不保证均方误差单调改善。

直觉

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

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

时序差分学习：终局尚未出现，相邻时刻的 TD 误差已回写当前估计 — 在完整回报前更新

例子与边界

确定性轨迹 $a\to b\to$ 终止的两次奖励为 $0,1$ ，初始值全零， $\gamma=1$ ，步长为 $1/2$ 。第一回合访问 $a$ 时目标仍为零，只有终止前的 $b$ 更新为 $1/2$ ；第二回合 $a$ 才用目标 $V(b)=1/2$ 更新为 $1/4$ 。TD 可以立即更新，但终局信息未必一次遍历就传到起点。

设从状态 $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.

形式陈述 ​

反向链接

形式陈述