强化学习的数学原理（七）：时序差分方法TD Learning

在强化学习领域，当我们没有环境的完整模型时，如何评估一个策略的好坏并最终找到最优策略呢？蒙特卡洛（Monte Carlo）方法为我们提供了一种思路：通过完整的经验序列来估计价值。然而，它必须等到一个完整的 episode 结束后才能进行学习。动态规划（Dynamic Programming）虽然高效，却依赖于已知的环境模型。

时序差分（Temporal-Difference, TD）学习 巧妙地结合了两者的优点：它像蒙特卡洛方法一样，直接从经验中学习，无需环境模型；同时，它又像动态规划一样，利用当前学到的价值估计来更新之前的估计（即“自举”，bootstrapping），从而可以进行单步更新，不必等待 episode 结束。

本文将深入探讨 TD 学习的核心思想，从基础的 TD 价值评估，到 Sarsa、Q-Learning 等经典的 TD 控制算法，并最终阐明 On-Policy 与 Off-Policy 这一核心概念的区别。

一、时序差分（TD）学习基础

TD 学习的核心任务是在给定策略 $\pi$ 的情况下，估计其状态价值函数 $V_\pi(s)$。它通过智能体与环境的交互产生的经验数据来进行学习。

• 所需经验: 智能体遵循策略 $\pi$ 产生的序列 $(s_0, r_1, s_1, …, s_t, r_{t+1}, s_{t+1}, …)$，或者可以看作是一系列样本的集合 ${(s_t, r_{t+1}, s_{t+1})}_t$。

最基础的 TD 学习算法（也称为 TD(0)）的更新规则如下： $$V_{t+1}(s_t) \leftarrow V_t(s_t) + \alpha_t(s_t)[r_{t+1} + \gamma V_t(s_{t+1}) - V_t(s_t)]$$ 对于任意其他状态 $s \neq s_t$，其价值保持不变，即 $V_{t+1}(s) = V_t(s)$。

这里：

• $V_t(s_t)$ 是在时间步 $t$ 对状态 $s_t$ 价值的当前估计。
• $\alpha_t(s_t)$ 是学习率。
• 在每个时间步 $t$，我们只更新刚刚访问过的状态 $s_t$ 的价值。

TD Target 与 TD Error

我们可以将上述更新公式分解，以更清晰地理解其内在机制： $$\underbrace{V_{t+1}(s_t)}{\text{新估计值}} = \underbrace{V_t(s_t)}{\text{当前估计值}} + \alpha_t(s_t) [ \underbrace{(r_{t+1} + \gamma V_t(s_{t+1}))}_{\text{TD Target}} - V_t(s_t) ]$$

• TD Target ($\hat{V}_t$): $r_{t+1} + \gamma V_t(s_{t+1})$ 是一个更优的估计目标。它使用了一步的真实奖励 $r_{t+1}$ 和下一状态的当前价值估计 $V_t(s_{t+1})$，这正是“自举”的体现。
• TD Error ($\delta_t$): $\delta_t = (r_{t+1} + \gamma V_t(s_{t+1})) - V_t(s_t)$，即 TD Target 与当前估计值之间的差距。TD 算法的核心思想就是利用这个误差来驱动当前估计值向着更准确的 TD Target 移动。

TD 更新的目标是让当前估计值 $V_t(s_t)$ 逐渐逼近 TD Target $\hat{V}t$。我们可以看到，更新后的新估计值与目标之间的差距被缩小了： $$|V{t+1}(s_t) - \hat{V}_t| = |(1-\alpha_t(s_t))(V_t(s_t) - \hat{V}_t)| \le |V_t(s_t) - \hat{V}_t|$$

二、TD 算法背后的数学思想

TD Error 不仅仅是一个计算上的构造，它也反映了当前价值函数 $V_t$ 与真实价值函数 $V_\pi$ 之间的“缺陷”。在理想情况下，真实的价值函数 $V_\pi$ 应该满足贝尔曼方程，其期望 TD Error 为零： $$E_\pi[r_{t+1} + \gamma V_\pi(s_{t+1}) - V_\pi(s_t) | S_t=s_t] = 0$$ 因此，当 TD Error 的期望不为零时，就意味着我们当前的估计 $V_t$ 还不等于 $V_\pi$。TD 算法的本质，就是一种随机近似（Stochastic Approximation） 的方法，它通过采样得到的 TD Error 来迭代求解满足贝尔曼方程的价值函数。

算法的收敛性

TD 学习收敛性定理: 只要学习率 $\alpha_t(s)$ 满足标准随机近似的收敛条件（即 $\sum_{t=1}^{\infty} \alpha_t(s) = \infty$ 且 $\sum_{t=1}^{\infty} \alpha_t^2(s) < \infty$），TD(0) 算法的价值估计 $V_t(s)$ 将以概率 1 收敛到真实的策略价值 $V_\pi(s)$。

三、Sarsa：On-Policy TD 控制

仅仅能评估策略是不够的，我们更希望找到最优策略。这就需要将 TD 方法从价值评估扩展到控制问题。Sarsa 算法就是一种用于估计动作价值函数 $q_\pi(s,a)$ 的 TD 算法。

• 所需经验: Sarsa 算法的学习需要一个五元组 $(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})$。这个名字本身就来源于其更新所依赖的序列：State, Action, Reward, State, Action。

Sarsa 的更新规则如下： $$q_{t+1}(s_t, a_t) \leftarrow q_t(s_t, a_t) + \alpha_t(s_t, a_t)[r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1}) - q_t(s_t, a_t)]$$ Sarsa 算法通常与 $\epsilon$-greedy 等探索策略结合使用，一边评估当前策略的动作价值，一边基于更新后的价值函数来改进策略，这体现了广义策略迭代（Generalized Policy Iteration, GPI） 的思想。

Sarsa 学习收敛性定理: 在满足与 TD(0) 类似的条件下，Sarsa 的动作价值估计 $q_t(s,a)$ 将以概率 1 收敛到真实的动作价值 $q_\pi(s,a)$。

四、TD 算法的变体

1. Expected Sarsa

Expected Sarsa 是 Sarsa 的一个变体，它在计算 TD Target 时，用所有可能动作的期望价值替代了 Sarsa 中下一个采样到的动作 $a_{t+1}$ 的价值。

其更新规则为： $$q_{t+1}(s_t, a_t) \leftarrow q_t(s_t, a_t) + \alpha_t[r_{t+1} + \gamma \sum_a \pi(a|s_{t+1})q_t(s_{t+1}, a) - q_t(s_t, a_t)]$$ 其中，$\sum_a \pi(a|s_{t+1})q_t(s_{t+1}, a)$ 正是状态 $s_{t+1}$ 的期望价值 $V_t(s_{t+1})$。

与 Sarsa 相比，Expected Sarsa 的计算量稍大，但它的 TD Target 消除了对下一个动作 $a_{t+1}$ 的随机依赖，从而降低了更新目标的方差，使得学习过程可能更加平稳。

2. n-step Sarsa

Sarsa 属于单步 TD 方法，而蒙特卡洛方法则使用完整的未来回报。n-step Sarsa 则是在这两者之间进行权衡，它向前看 $n$ 步来计算回报。

我们可以将折扣回报 $G_t$ 写成不同的形式：

• Sarsa (1-step): $G_t^{(1)} = r_{t+1} + \gamma q(s_{t+1}, a_{t+1})$
• n-step Sarsa: $G_t^{(n)} = r_{t+1} + \gamma r_{t+2} + \cdots + \gamma^{n-1} r_{t+n} + \gamma^n q(s_{t+n}, a_{t+n})$
• Monte Carlo: $G_t^{(\infty)} = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots$

n-step Sarsa 的更新规则相应地变为： $$q_{t+1}(s_t, a_t) \leftarrow q_t(s_t, a_t) + \alpha_t[G_t^{(n)} - q_t(s_t, a_t)]$$ 通过调整参数 $n$，n-step Sarsa 可以在 Sarsa 和蒙特卡洛方法之间灵活地取得平衡。

五、Q-Learning: Off-Policy TD 控制

Q-Learning 是强化学习中一个里程碑式的算法。与 Sarsa 不同，它是一种 Off-Policy（离策略）算法。Q-Learning 的目标是直接学习最优动作价值函数 $q_*(s,a)$，无论智能体当前遵循的是什么策略。

它的更新规则如下： $$q_{t+1}(s_t, a_t) \leftarrow q_t(s_t, a_t) + \alpha_t[r_{t+1} + \gamma \max_{a’} q_t(s_{t+1}, a’) - q_t(s_t, a_t)]$$ Q-Learning 与 Sarsa 的关键区别就在于 TD Target 的计算：

• Sarsa Target: $r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1})$ (依赖于下一个实际执行的动作 $a_{t+1}$)
• Q-Learning Target: $r_{t+1} + \gamma \max_{a’} q_t(s_{t+1}, a’)$ (总是选择下一状态价值最大的动作，非常“贪婪”)

从数学上看，Q-Learning 旨在求解贝尔曼最优方程: $$q_(s,a) = E[r_{t+1} + \gamma \max_{a’} q_(s_{t+1}, a’) | S_t=s, A_t=a]$$ 这个方程的解就是最优动作价值函数，它不依赖于任何特定的策略。

六、On-Policy vs. Off-Policy：一个核心区别

这是理解现代强化学习算法的关键。在 TD 学习中，我们通常涉及两个策略：

• 行为策略 (Behavior Policy): 智能体实际用来与环境交互、生成经验样本的策略。通常需要有足够的探索性。
• 目标策略 (Target Policy): 我们想要评估和改进的策略。我们希望这个策略最终能收敛到最优策略。

据此，我们可以将算法分为两类：

• On-Policy (同策略): 行为策略和目标策略是同一个策略。例如，Sarsa 算法用 $\epsilon$-greedy 策略生成数据，同时也在评估和改进这个 $\epsilon$-greedy 策略。
• Off-Policy (离策略): 行为策略和目标策略是不同的策略。例如，Q-Learning 的目标策略是纯粹的贪心策略（因为 max 操作），但它的行为策略可以是 $\epsilon$-greedy 或其他任何能充分探索状态空间的策略。

为什么 Off-Policy 很重要？ 它允许我们“看着碗里的，吃着锅里的”。我们可以用一个足够探索性的策略来收集数据，同时用这些数据来学习一个确定性的最优策略。这使得学习可以从历史数据、人类专家的数据、甚至是其他智能体的经验中进行，极大地增强了学习的灵活性和数据利用率。

• Sarsa 是 On-Policy: 因为其更新需要用到下一个动作 $a_{t+1}$，而 $a_{t+1}$ 是由当前策略 $\pi$ 生成的。行为和目标必须一致。
• Monte Carlo 是 On-Policy:因为它使用整个 episode 的回报，而这个 episode 的轨迹完全由一个策略 $\pi$ 生成。
• Q-Learning 是 Off-Policy: 因为它的更新完全不依赖于下一个动作是什么，max 操作使得目标策略隐式地成为了一个贪心策略，而行为策略可以任意选择。

七、总结与展望

我们可以将前面讨论的所有 TD 算法都统一到一个表达式中： $$q_{t+1}(s_t, a_t) \leftarrow q_t(s_t, a_t) + \alpha_t[\tilde{q}_t - q_t(s_t, a_t)]$$ 其中，$\tilde{q}_t$ 是不同算法的 TD Target。下表清晰地总结了它们的区别：

时序差分学习是现代强化学习的基石，它为更高级的算法如深度 Q 网络 (DQN) 等铺平了道路。理解这些基础算法的数学原理、它们之间的联系与区别，对于深入掌握强化学习至关重要。