TD(0) 算法 | Codeboy's Blog

形式陈述

TD(0) 是时序差分学习的一步预测特例。固定平稳马尔可夫策略 $\pi$ 产生转移 $(S_t,R_{t+1},S_{t+1})$ 后，表格算法更新

V_{t+1}(S_t)=V_t(S_t)+\alpha_t(S_t) \bigl[R_{t+1}+\gamma V_t(S_{t+1})-V_t(S_t)\bigr],

其他状态保持不变，终止状态价值取零。

实际运行可预先给定转移更新次数，处理完后返回当前估值；几乎必然收敛描述的是同一更新规则无限延伸时的极限。样本转移给定后，一次表格更新只读写常数个表项，耗时 $O(1)$ ；价值表及可选的逐状态访问计数占 $O(|S|)$ 空间，不含策略采样与环境交互的代价。

“0”指资格迹参数 $\lambda=0$ ，不是说更新不向未来看；它恰好 bootstrap 一步。

在有限折扣 MDP 中，假设给定过去和当前状态后，动作与转移按固定策略及环境核生成，奖励的条件二阶矩统一有界。若每个非终止状态都被无限访问，终止表项固定为零，且步长在抽取本次动作及转移前确定，取值在 $[0,1]$ ，每个状态自己的访问步长满足 Robbins–Monro 条件

\sum_{n=1}^{\infty}\alpha_n(s)=\infty, \qquad \sum_{n=1}^{\infty}\alpha_n(s)^2<\infty,

则标准异步随机近似结果给出整个价值表 $V_t\to v_\pi$ 几乎必然收敛。只覆盖一部分状态时，不能对其余未更新表项声称同一结论。步长条件应按“该状态第几次被访问”计数；用全局时间写下一个衰减序列后让稀有状态只获得有限总步长，会破坏结论。

有限 episodic 情形还需回合能适当终止或等价的稳定性条件。常数步长适合跟踪缓慢变化的环境，但不满足平方可和与总和发散的组合，因此经典极限结论不适用。

直觉

TD(0) 每走一步就问：旧估计 $V(S_t)$ 是否等于“刚收到的奖励加下一状态的旧估计”。差额立即回写当前状态。相比等待整回合，它更早利用信息；相比模型式策略评估，它只需实际到达的一个下一状态。

奖励信息一次只跨过一条转移边。多次访问把终点附近的信号逐层向前传，步长则决定新证据与旧估计的混合比例。递减步长让早期误差最终被洗掉，同时抑制后期采样噪声。

它评估的是一套固定策略，而不负责挑选更优动作；把预测与策略改进混为一步，会悄悄改变待逼近的 Bellman 不动点。

例子与边界

一条确定性回合为 $A\xrightarrow{0}B\xrightarrow{1}\text{terminal}$ ，取 $\gamma=1/2$ 、恒定演示步长 $\alpha=1/2$ ，初值 $V(A)=V(B)=0$ 。第一回合在 $A$ 的目标是 $0+\frac12V(B)=0$ ，故不变；到 $B$ 后更新为

V(B)\leftarrow0+\tfrac12(1-0)=\tfrac12.

第二回合经过 $A$ 时，

V(A)\leftarrow0+\tfrac12\left(0+\tfrac12\cdot\tfrac12-0\right)=\tfrac18,

随后 $V(B)$ 更新到 $3/4$ 。真实值为 $v(B)=1,v(A)=1/2$ ；这个过程清楚展示终点奖励需经重复回合逐步向前传播。恒定步长仅用于算例，不能作为前述几乎必然收敛条件的实例。

若行为策略不访问 $A$ ，其表项永远不会改；若策略在学习中改变，TD(0) 追踪的是移动目标而非固定 $v_\pi$ 。线性函数逼近的 on-policy TD(0) 有投影方程理论，但答案通常是投影固定点，不等于逐状态真值；一般非线性或离策略组合还可能发散。

推论与应用

把一步目标换成 $n$ 步采样回报得到 $n$ -step TD；用资格迹加权许多步长得到 TD( $\lambda$ )。 $\lambda$ 增大通常减少 bootstrap 偏差并增加回报方差，但准确权衡还依赖任务与函数逼近，不能简化成单调优劣排序。

TD(0) 的预测更新常作为控制算法的 critic。SARSA 和 Q-learning 更新的是动作值且包含动作选择或最大化；它们的状态—动作表与控制目标不同于这里的固定策略状态值预测。

参考资料

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, Sec. 6.1.
John N. Tsitsiklis, “Asynchronous Stochastic Approximation and Q-Learning,” Machine Learning 16, 1994, pp. 185–202.

形式陈述 ​

反向链接

形式陈述