时序差分（TD）学习

一句话总结 · 要点速览

• 时序差分（TD）学习结合了蒙特卡洛的采样和动态规划的自举：每走一步就用 R_{t+1} + γV(S_{t+1}) 作为目标更新 V(S_t)。
• TD 误差定义为 δ_t = R_{t+1} + γV(S_{t+1}) − V(S_t)，它是 TD 学习、Actor-Critic 和 GAE 的核心量。
• 与 MC 相比，TD 目标有偏但方差小，可以在线、增量地学习，也适用于没有终点的持续性任务。
• n 步 TD 和 TD(λ) 在单步 TD 和蒙特卡洛之间平滑过渡，用来调节偏差与方差。

术语不熟悉？查看 强化学习术语表。

时序差分（Temporal-Difference，TD）学习结合了蒙特卡洛和动态规划的思想：像 蒙特卡洛 一样直接从经验中学习、不需要模型，又像 动态规划 一样用对后继状态价值的估计来更新当前估计（即“自举”，bootstrapping）。因此 TD 方法可以在每一步之后立即更新，无需等待回合结束，也能用于持续性任务。Sutton 认为 TD 学习是强化学习中“最核心、最新颖”的思想，它是 Q-learning、DQN 和 Actor-Critic 等算法的基础。

动机：不想等到回合结束

常数步长 MC 的更新是：

$$V(S_t)\leftarrow V(S_t)+\alpha [G_t-V(S_t)]$$

$G_t$ 要等回合结束才知道。但由贝尔曼方程 $v_{\pi }(s)={\mathbb{E}}_{\pi }[R_{t+1}+\gamma v_{\pi }(S_{t+1})\mid S_t=s]$，我们可以用“一步真实奖励 + 下一状态的当前估计”来代替 $G_t$。

一个生活中的例子：每天开车回家，你会估计到家时间。MC 的做法是到家后才根据实际总用时修正估计；TD 的做法是每到一个路口，就根据“已用时间 + 从这个路口到家的估计”及时修正——一出门发现堵车，你立刻就会调高预期，不必等到家。

TD(0) 预测

TD 目标与 TD 误差

最简单的 TD 方法 TD(0) 的更新规则：

$$V(S_t)\leftarrow V(S_t)+\alpha [R_{t+1}+\gamma V(S_{t+1})-V(S_t)]$$

• $R_{t+1}+\gamma V(S_{t+1})$ 称为 TD 目标；
• ${\delta }_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t)$ 称为 TD 误差。

如果 $S_{t+1}$ 是终止状态，则 $V(S_{t+1})=0$。

伪代码：

输入：待评估策略 π，步长 α ∈ (0, 1]
初始化 V(s) 任意，V(终止状态) = 0
对每个回合：
    初始化 S
    重复直到 S 为终止状态：
        A ← π(·|S) 采样
        执行 A，观察 R, S'
        V(S) ← V(S) + α [R + γV(S') − V(S)]
        S ← S'

与 MC、DP 的比较

三种方法的目标值：

方法	更新目标	是否采样	是否自举
DP	${\mathbb{E}}_{\pi }[R_{t+1}+\gamma V(S_{t+1})]$	否（对所有后继求期望）	是
MC	$G_t$	是	否
TD(0)	$R_{t+1}+\gamma V(S_{t+1})$	是	是

TD 同时具备采样（不需要模型）和自举（不用等回合结束）两个特点。对于固定策略 $\pi$，在表格情形下，只要步长满足随机逼近条件 $\sum _t{\alpha }_t=\mathrm{\infty }$、$\sum _t{\alpha }_t^2<\mathrm{\infty }$，TD(0) 以概率 1 收敛到 $v_{\pi }$。

偏差与方差的权衡

• MC 目标 $G_t$：是 $v_{\pi }(S_t)$ 的无偏估计，但依赖整条轨迹上的所有随机动作、转移和奖励，方差大。
• TD 目标 $R_{t+1}+\gamma V(S_{t+1})$：只依赖一步的随机性，方差小；但 $V(S_{t+1})$ 是估计值而不是真值，所以有偏。

实践中 TD 往往比常数步长 MC 学得更快。另一个深刻的区别是在批量更新（反复在固定数据上训练直到收敛）下：MC 收敛到使训练集上均方误差最小的估计，而 TD(0) 收敛到确定性等价估计——即根据数据拟合出最大似然的马尔可夫模型后，这个模型下的精确价值。TD 隐式地利用了马尔可夫结构，这是它在马尔可夫环境中数据效率更高的原因。

多步 TD 与 TD(λ)

n 步回报

TD(0) 只看一步，MC 看到回合结束，两者之间可以连续过渡。n 步回报定义为：

$$G_{t:t+n}=R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^{n-1}{R}_{t+n}+{\gamma }^{n}V(S_{t+n})$$

$n=1$ 就是 TD(0)，$n\to \mathrm{\infty }$（到回合结束）就是 MC。n 步 TD 的更新：

$$V(S_t)\leftarrow V(S_t)+\alpha [G_{t:t+n}-V(S_t)]$$

中间的 $n$ 通常比两个极端效果都好。n 步回报也被 Rainbow 和 A2C 等深度强化学习算法采用。

资格迹

λ-回报把所有 n 步回报按几何权重平均：

$$G_t^{\lambda }=(1-\lambda )\sum _{n=1}^{\mathrm{\infty }}{\lambda }^{n-1}{G}_{t:t+n},\lambda \in [0,1]$$

$\lambda =0$ 退化为 TD(0)，$\lambda =1$ 等价于 MC。直接计算 $G_t^{\lambda }$ 需要等回合结束（前向视角）；资格迹（eligibility trace）提供了等价的在线实现（后向视角）：每个状态维护一个迹 $e(s)$，表示它对当前 TD 误差“负有多少责任”：

$$\begin{array}{rl}e(s)& \leftarrow \gamma \lambda e(s)+\mathbb{1}[s=S_t]\\ V(s)& \leftarrow V(s)+\alpha {\delta }_{t}e(s),\mathrm{\forall }s\end{array}$$

最近被访问、访问频繁的状态迹更大，获得更多更新。GAE 正是把 λ-回报的思想用在了优势估计上。

代码：随机游走示例

Sutton & Barto 例 6.2：5 个非终止状态 A–E 排成一行，从中间 C 出发，每步等概率向左或向右，从右端离开得奖励 1，其余奖励为 0，$\gamma =1$。真实价值为 $v(A..E)=1/6,2/6,\dots ,5/6$。下面比较 TD(0) 和常数步长 MC 在 100 个回合后的均方根误差（100 次独立运行取平均），价值初始化为 0.5。

"""TD(0) 与常数步长 MC 在 5 状态随机游走上的对比（Sutton & Barto 例 6.2）。"""
import numpy as np

N_STATES = 5                     # 非终止状态 A..E，编号 1..5；0 和 6 为终止状态
TRUE_V = np.arange(1, 6) / 6.0   # 真实价值：1/6, 2/6, ..., 5/6


def run_episode(rng):
    s, traj = 3, []              # 从中间状态 C 出发
    while True:
        s2 = s + (1 if rng.random() < 0.5 else -1)
        r = 1.0 if s2 == 6 else 0.0          # 只有从右端离开才得到奖励 1
        traj.append((s, r, s2))
        if s2 in (0, 6):
            return traj
        s = s2


def td0(alpha, episodes, rng):
    V = np.full(7, 0.5); V[0] = V[6] = 0.0
    errs = []
    for _ in range(episodes):
        for s, r, s2 in run_episode(rng):
            V[s] += alpha * (r + V[s2] - V[s])      # γ = 1
        errs.append(np.sqrt(np.mean((V[1:6] - TRUE_V) ** 2)))
    return np.array(errs)


def mc(alpha, episodes, rng):
    V = np.full(7, 0.5); V[0] = V[6] = 0.0
    errs = []
    for _ in range(episodes):
        traj = run_episode(rng)
        G = traj[-1][1]                              # γ = 1，回报 = 最终奖励
        for s, _, _ in traj:
            V[s] += alpha * (G - V[s])
        errs.append(np.sqrt(np.mean((V[1:6] - TRUE_V) ** 2)))
    return np.array(errs)


runs, episodes = 100, 100
for name, fn, alphas in [("TD(0)", td0, [0.05, 0.1, 0.15]), ("MC", mc, [0.01, 0.02, 0.04])]:
    for alpha in alphas:
        err = np.mean([fn(alpha, episodes, np.random.default_rng(i)) for i in range(runs)], axis=0)
        print(f"{name:6s} α={alpha:<5} 第100回合 RMS 误差 = {err[-1]:.3f}")

实际运行输出：

TD(0)  α=0.05  第100回合 RMS 误差 = 0.036
TD(0)  α=0.1   第100回合 RMS 误差 = 0.057
TD(0)  α=0.15  第100回合 RMS 误差 = 0.073
MC     α=0.01  第100回合 RMS 误差 = 0.097
MC     α=0.02  第100回合 RMS 误差 = 0.085
MC     α=0.04  第100回合 RMS 误差 = 0.109

在各自尝试过的步长中，TD(0) 的误差都明显低于 MC，与书中图 6.2 的结论一致。也能看到步长的影响：大步长学得快但最终误差（由噪声引起的波动）更大。

常见误区

• 终止状态的价值不为 0：TD 目标中终止状态的 $V$ 必须为 0，否则价值会被系统性地抬高或压低。
• 把被截断（truncated）当作终止：因时间上限结束的回合，下一状态并非真正的终止状态，仍应自举 $V(S_{t+1})$。详见 智能体与环境。
• 以为 TD 总是优于 MC：在非马尔可夫环境（例如观测不完整）中，TD 的自举会引入偏差，MC 可能更稳健。
• 步长过大：表格 TD 中 $\alpha$ 过大会导致估计剧烈震荡；函数近似下甚至可能发散。

小结

• TD(0) 用 $R_{t+1}+\gamma V(S_{t+1})$ 作为目标，每一步都能更新，无需模型。
• TD 是有偏低方差，MC 是无偏高方差。
• n 步 TD 和 TD(λ) 在 TD(0) 与 MC 之间连续插值，资格迹提供了 TD(λ) 的高效在线实现。
• 把 TD 思想用于控制问题，就得到下一节的 SARSA 与 Q-learning。

练习题

1. 在例题中把初始值从 0.5 改为 0，TD 和 MC 的误差曲线有何变化？为什么？
2. 实现 n 步 TD（$n=1,2,4,8$），在随机游走上比较 100 回合后的 RMS 误差。
3. 实现带资格迹的 TD(λ)，比较 $\lambda =0,0.5,0.9,1$。
4. 解释为什么批量 TD(0) 收敛到确定性等价估计，而批量 MC 不是。（参考 Sutton & Barto 例 6.4。）
5. 回家开车的例子中，哪些情况下 TD 的估计会比 MC 更差？

参考文献

• Sutton, R. S. (1988). Learning to predict by the methods of temporal differences. Machine Learning, 3(1), 9–44.
• Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.), 第 6、7、12 章.

下一步

继续阅读：Q-learning 与 SARSA——把 TD 用于控制问题。