RL 学习笔记（6）：时序差分学习 • Axi's Blog

本博客基于西安交通大学强化学习课程 PPT 改编，历经 Gemini 以及本人总结以及整理形成。

时序差分（TD）学习概述#

动机：结合动态规划（DP）与蒙特卡洛（MC）的优点

DP：利用自举 (Bootstrapping)，即基于其他状态的估计值来更新当前状态的估计值（例如， $V(S_t) \leftarrow \mathbb{E}_\pi[R_{t+1} + \gamma V(S_{t+1})]$ ）。但它需要知道环境的完整模型。
MC：无模型，直接从完整经验片段的最终实际回报 $G_t$ 中学习（例如， $V(S_t) \leftarrow V(S_t) + \alpha [G_t - V(S_t)]$ ）。它不使用自举，必须等待片段结束。
TD 学习：旨在融合两者的长处：
- 无模型 (Model-Free)：像 MC 一样，直接从经验中学习，无需环境模型 $\mathcal{P}, \mathcal{R}$ 。
- 自举 (Bootstrapping)：像 DP 一样，更新当前状态 $S_t$ 的价值时，会使用后续状态 $S_{t+1}$ 的当前价值估计 $V(S_{t+1})$ ，而不需要等到片段结束。

核心思想：TD 学习在智能体与环境交互的每一步之后，利用观测到的即时奖励 $R_{t+1}$ 和下一状态 $S_{t+1}$ 的当前价值估计 $V(S_{t+1})$ 来构建一个目标值 (TD Target)。然后，用这个目标值来更新当前状态 $S_t$ 的价值估计 $V(S_t)$ 。

TD(0) 更新规则（最简单的 TD 算法）：

V(S_t) \leftarrow V(S_t) + \alpha \underbrace{[ \overbrace{R_{t+1} + \gamma V(S_{t+1})}^{\text{TD 目标 (TD Target)}} - V(S_t) ]}_{\text{TD 误差 (TD Error) } \delta_t}

TD 目标 (TD Target): $R_{t+1} + \gamma V(S_{t+1})$ 。这是对未来总回报 $G_t$ 的一个估计，它仅使用了一步的真实奖励 $R_{t+1}$ 和一步之后状态的价值估计 $V(S_{t+1})$ 。
TD 误差 (TD Error) $\delta_t$ : $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ 。它衡量了当前价值估计 $V(S_t)$ 与基于下一步信息的“更好”的估计（TD 目标）之间的差异，可以看作是对当前价值的一个调整信号。

TD 学习的特点：自举与采样 (Bootstrapping and Sampling)

采样 (Sampling)：更新是基于智能体实际经历的转移 $(S_t, A_t, R_{t+1}, S_{t+1})$ ，而不是像 DP 那样考虑所有可能的后续状态和奖励。
自举 (Bootstrapping)：更新的目标值中包含了当前的价值估计 $V(S_{t+1})$ ，而不是像 MC 那样依赖最终观测到的完整回报 $G_t$ 。

学习内容：接下来我们将介绍 TD 如何用于策略评估（TD 预测）和策略改进（TD 控制）。

TD 预测 (TD Prediction)#

目标：在给定策略 $\pi$ 的情况下，估计其状态价值函数 $v_\pi$ 。

TD(0) 算法 (用于估计 $v_\pi$ )：

输入: 需要评估的策略 π
算法参数: 步长 α ∈ (0, 1]
初始化:
  对于所有状态 s ∈ S⁺ (S⁺ 是包含终止状态的状态集):
    V(s) ← 任意值 (例如 V(s)=0)
  V(终止状态) ← 0

循环 对每个 episode:
  初始化 S (该 episode 的第一个状态)
  循环 对 episode 中的每一步:
    A ← 根据策略 π 在状态 S 选择的动作
    执行动作 A, 观察得到奖励 R 和下一状态 S'
    // TD 更新
    V(S) ← V(S) + α * [R + γ * V(S') - V(S)]
    S ← S' // 转移到下一状态
  直到 S 是终止状态

plaintext

主要特点：TD(0) 算法在每一步交互后都进行价值更新，无需等待一个 episode 结束。这使得 TD 学习非常适合在线 (Online) 学习场景。

TD 与 MC 的比较：性质与权衡#

TD 和 MC 作为无模型学习方法，各有优劣：

更新时机与数据需求：
- TD 可在线学习，每步更新；MC 需等待 episode 结束才能更新（离线更新）。
- TD 能从不完整的 episode 中学习；MC 必须基于完整 episode。
- TD 天然适用于连续性任务（无终止状态）；MC 主要用于分幕式任务。
偏差与方差 (Bias vs. Variance)：这是两者最核心的区别之一。
- MC 目标 ( $G_t$ )：是 $v_\pi(S_t)$ 的无偏 (Unbiased) 估计。因为 $G_t$ 是从 $t$ 时刻开始实际获得的总回报，其期望就是 $v_\pi(S_t)$ 。但 $G_t$ 的方差较高，因为它受到从 $t$ 到片段结束所有随机因素（动作选择、状态转移、奖励）的影响。
- TD(0) 目标 ( $R_{t+1} + \gamma V(S_{t+1})$ )：是 $v_\pi(S_t)$ 的有偏 (Biased) 估计。因为目标中使用的 $V(S_{t+1})$ 本身就是当前的估计值，可能并不准确。然而，这个目标的方差较低，因为它只依赖于下一个时间步的随机性 ( $R_{t+1}, S_{t+1}$ )。
- 总结：
  - MC：高方差，零偏差。对初始值不敏感。
  - TD：低方差，有偏差。通常比 MC 学习效率更高（收敛更快），但对初始值比较敏感。
对马尔可夫性质的利用：
- TD 隐式地利用了马尔可夫性质，它假设状态 $S_{t+1}$ 的价值 $V(S_{t+1})$ 足够概括未来信息。在满足马尔可夫性的环境中，这种假设有助于提高效率。
- MC 不做此假设，它直接使用实际发生的完整回报序列。这使得 MC 在非马尔可夫环境下可能比 TD(0) 更稳健。
批量学习 (Batch Learning) 下的行为差异：
- 当使用一个固定的、有限的经验数据集进行学习时：
  - 批量 MC 收敛到的价值函数，能最小化训练数据中观测到的回报 $G_t$ 与估计值 $V(S_t)$ 之间的均方误差。
  - 批量 TD(0) 收敛到的价值函数，等于根据这批数据构建的最大似然马尔可夫模型的真实价值函数（称为确定性等价估计 Certainty Equivalence Estimate）。
- 结论：TD(0) 的解更符合 MDP 的结构假设（当前状态价值等于期望的下一步奖励加折扣后的下一状态价值），而 MC 的解直接反映样本平均回报。

同轨时序差分控制 (On-Policy TD Control)#

目标：使用 TD 方法学习最优策略 $\pi_*$ 。

基本思想：与 MC 控制类似，在 GPI 框架中进行策略评估和改进。但使用 TD 预测来替代 MC 预测进行策略评估步骤，以利用 TD 的在线学习和高效率特性。

需要动作价值 $Q(s, a)$ ：同样，在无模型控制中，我们需要估计动作价值 $Q(s, a)$ 而非状态价值 $V(s)$ ，以便在不知道模型的情况下选择最优动作。

Sarsa：同轨 TD 控制算法

名称来源：算法的更新依赖于一个状态-动作-奖励-下一状态-下一动作的五元组 $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$ 。
核心思想：将 TD(0) 的更新思想直接应用于动作价值 $Q(s, a)$ 。
更新规则：
- Sarsa TD 目标： $R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})$ 。关键在于，这里使用的是智能体根据当前策略在 $S_{t+1}$ 状态下实际选择的下一个动作 $A_{t+1}$ 对应的 Q 值。
- Sarsa TD 误差： $\delta_t = R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)$
- Q 值更新： $Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)]$
算法流程 (Sarsa)：

算法参数: 步长 α ∈ (0, 1], 探索参数 ε > 0 (用于 ε-greedy)
初始化:
  对于所有状态 s ∈ S⁺, 所有动作 a ∈ A(s):
    Q(s, a) ← 任意值 (例如 Q(s, a)=0)
  Q(终止状态, ·) ← 0

循环 对每个 episode:
  初始化 S (该 episode 的第一个状态)
  选择动作 A ← 根据 Q 从状态 S 推导出的策略 (例如 ε-greedy)

  循环 对 episode 中的每一步:
    执行动作 A, 观察得到奖励 R 和下一状态 S'

    // 如果 S' 不是终止状态，则选择下一个动作 A'
    如果 S' 是终止状态:
        A' ← None // 或任意值，因为 Q(终止状态, ·)=0
    否则:
        选择动作 A' ← 根据 Q 从状态 S' 推导出的策略 (例如 ε-greedy)

    // Sarsa 更新
    如果 A' 不是 None:
        Q(S, A) ← Q(S, A) + α * [R + γ * Q(S', A') - Q(S, A)]
    否则: // 处理到达终止状态的情况
        Q(S, A) ← Q(S, A) + α * [R + γ * 0 - Q(S, A)]

    S ← S'
    A ← A'

  直到 A 是 None (即 S 是终止状态)

plaintext

同轨 (On-Policy) 特性：Sarsa 学习的是其当前正在执行的策略（例如 $\epsilon$ -greedy 策略）下的动作价值。因为更新目标 $Q(S', A')$ 使用的是下一步实际会遵循策略选择的动作 $A'$ 。它评估和改进的是同一个行为策略。
例子：有风的网格世界 (Windy Gridworld)：Sarsa 可以有效地学习在这个环境中如何抵抗风力到达目标。
Sarsa 收敛性：
- Sarsa 算法能够收敛到最优动作价值函数 $q_*$ $q_{*}$ ，只要满足以下条件：
  1. 策略序列满足 GLIE (Greedy in the Limit with Infinite Exploration)：所有状态-动作对被无限次探索；策略最终收敛到纯贪心策略（例如， $\epsilon$ -greedy 中 $\epsilon \to 0$ ）。
  2. 步长参数 $\alpha_t$ 满足 Robbins-Monro 随机逼近条件： $\sum \alpha_t = \infty$ 且 $\sum \alpha_t^2 < \infty$ 。

总结#

时序差分 (TD) 学习是强化学习中一种核心的无模型方法，巧妙地结合了 DP 的自举和 MC 的采样思想。
TD 方法可以直接从与环境的交互经验中学习，无需模型知识。
TD 可以在每一步之后更新价值估计，支持在线学习，并能处理不完整的序列和连续性任务。
TD(0) 是最基础的 TD 预测算法，用于评估给定策略的价值。
Sarsa 是最基础的同轨 (On-Policy) TD 控制算法，它学习的是当前行为策略（如 $\epsilon$ -greedy）下的动作价值，并通过 GPI 逐步改进策略。
相比 MC，TD 通常具有更低的方差和更高的学习效率（尤其在马尔可夫环境中），但其估计是有偏的。