Q 学习与 SARSA

Q 学习与 SARSA

本节摘要:蒙特卡洛要等回合结束才更新。时间差分(Temporal Difference, TD)每走一步就用「下一步的价值估计」自举更新——无需模型、无需完整回合。本节讲透两个一行之差的算法:Q 学习(Off-Policy,目标里带 max,乐观、学 Q*)与 SARSA(On-Policy,目标里用真实下一步动作,谨慎、学 Q^π)。它们都是一行代码的差别,却是整个深度 RL 的根基——DQN 就是 Q 学习的神经网络版,PPO 的优势也源自 TD 残差。你会在 4×4 GridWorld 上看到两者 ~2000 回合逼近最优,在悬崖行走(Cliff Walking)上看到 Q 学习贴着崖边走、SARSA 远离崖边——这就是 off-policy 与 on-policy 在部署时的现实差别。

对应原课程:Phase 9 · Lesson 04 · q-learning-sarsa(原英文 phases/09-reinforcement-learning/04-q-learning-sarsa/docs/en.md)。

学习目标

阅读完本节,你应当能够:

1. 写出 TD(0) 更新 V(s) ← V(s) + α[r + γV(s') - V(s)],并解释 TD 误差 δ 的含义。
2. 区分 Q 学习(off-policy, max) 与 SARSA(on-policy, a'),说明它们各自学到 Q* 还是 Q^π。
3. 用悬崖行走这一经典实验说明两算法在探索期的不同行为,并据此为安全关键任务选型。
4. 解释最大化偏差(Maximization Bias)为何让 Q 学习高估,以及 Double Q 学习如何修复。
5. 掌握 GLIE(无限探索下趋贪心)与 α 调度,作为表格 TD 收敛的条件。

一、问题与直觉

蒙特卡洛能用,但有两个昂贵的代价。它要求回合终止,而且只在最终回报到手后才更新。如果你的回合有 1000 步,MC 要等 1000 步才更新任何东西。它高方差、低偏差、实践慢。

动态规划是相反的画像——零方差、自举回溯——但要求已知模型。

时间差分学习走中间路线。从单次转移 (s, a, r, s'),构造一个单步目标 r + γ V(s'),把 V(s) 往它那边推一点。无模型。无需完整回合。因为右侧用了近似的 V,会引入偏差,但方差比 MC 低得多,且从第一步就能在线更新。

这就是整个现代 RL——DQN、A2C、PPO、SAC——所围绕旋转的支点。 本章后半,全是建在这个单步 TD 更新之上的函数逼近与各种技巧。

TD(0) 更新与 TD 误差

V(s) ← V(s) + α [r + γ V(s') - V(s)]
​

方括号里的量就是 TD 误差 δ = r + γ V(s') - V(s)。它是 MC 里 G_t - V(s_t) 的在线对应物。收敛要求 α 满足 Robbins-Monro(Σ α = ∞、Σ α² < ∞),且所有状态被无限次访问。

两个算法,一行之差

Q学习:off-policy 的 TD 控制方法:

Q(s, a) ← Q(s, a) + α [r + γ max_{a'} Q(s', a') - Q(s, a)]

那个 max 假设从 s' 起将遵循贪心策略,无论智能体实际采取什么动作。这种解耦让 Q 学习在用 ε-贪心探索的同时,学的是 Q*。Mnih et al. (2015) 把它变成了 Atari 上的深度 Q 学习(第 05 节)。

SARSA:on-policy 的 TD 方法:

Q(s, a) ← Q(s, a) + α [r + γ Q(s', a') - Q(s, a)]

名字就是元组 (s, a, r, s', a')。SARSA 用智能体实际采取的下一个动作 a',而非贪心 argmax。它对当前跑着的 ε-贪心 π 收敛到 Q^π,在 ε → 0 极限下变成 Q*。

悬崖行走的差别

经典悬崖行走任务(掉崖 = -100):Q 学习学到贴着崖边的最优路径,但探索时偶尔吃惩罚;SARSA 学到离崖边一步的更安全路径,因为它把探索噪声算进了 Q 值。训练到 ε → 0,两者都达最优。实践中这很重要:当部署时探索真的在发生,SARSA 的行为更保守。

Expected SARSA 与 n 步

Expected SARSA:把 Q(s', a') 换成它在 π 下的期望:

Q(s, a) ← Q(s, a) + α [r + γ Σ_{a'} π(a'|s') Q(s', a') - Q(s, a)]

比 SARSA 方差低(不采样 a'),同样的 on-policy 目标。现代教材常作默认。

n 步 TD 与 TD(λ):在 TD(0) 与 MC 之间插值,等 n 步再自举。n=1 是 TD,n=∞ 是 MC。TD(λ) 用几何权重 (1-λ)λ^{n-1} 对所有 n 求平均。多数深度 RL 用 n 在 3 到 20 之间。

💡 「on-policy vs off-policy」是 RL 里最重要的二分。一句话:on-policy 学自己正在用的策略(SARSA、REINFORCE、PPO),off-policy 学一个不同的目标策略(Q 学习、DQN)。off-policy 能用旧数据(经验回放),on-policy 不能——这决定了样本效率与稳定性。

二、从零实现

Step 1:ε-贪心策略上的 SARSA

def sarsa(env, episodes, alpha=0.1, gamma=0.99, epsilon=0.1):
    Q = defaultdict(lambda: {a: 0.0 for a in ACTIONS})

    def choose(s):
        if random() < epsilon:
            return choice(ACTIONS)
        return max(Q[s], key=Q[s].get)

    for _ in range(episodes):
        s = env.reset()
        a = choose(s)
        while True:
            s_next, r, done = env.step(s, a)
            a_next = choose(s_next) if not done else None
            target = r + (gamma * Q[s_next][a_next] if not done else 0.0)
            Q[s][a] += alpha * (target - Q[s][a])
            if done:
                break
            s, a = s_next, a_next
    return Q
​

八行。与 Q 学习唯一的差别就是目标那一行。

Step 2:Q 学习

def q_learning(env, episodes, alpha=0.1, gamma=0.99, epsilon=0.1):
    Q = defaultdict(lambda: {a: 0.0 for a in ACTIONS})
    for _ in range(episodes):
        s = env.reset()
        while True:
            a = choose(s, Q, epsilon)
            s_next, r, done = env.step(s, a)
            target = r + (gamma * max(Q[s_next].values()) if not done else 0.0)
            Q[s][a] += alpha * (target - Q[s][a])
            if done:
                break
            s = s_next
    return Q
​

那个 max 把目标和行为策略解耦。一个符号,就是 on-policy 与 off-policy 的全部差别。

Step 3:学习曲线

跟踪每 100 回合的平均回报。简单确定性 GridWorld 上 Q 学习收敛更快;悬崖行走上 SARSA 更保守。在 code/main.py 的 4×4 GridWorld 上,α=0.1, ε=0.1 时两者约 2000 回合逼近最优。

Step 4:与 DP 真值对比

跑价值迭代(第 02 节)得到 Q*,检查 max_{s,a} |Q_learned(s,a) - Q*(s,a)|。健康的表格 TD 智能体在 4×4 GridWorld 上 10000 回合后,误差落在 ~0.5 内。

💡 这一步「与 DP 真值对比」是 TD 实现的命脉检查。差太多要么是 α/ε 没调好,要么是终点处理、状态哈希出了 bug。先在小环境上把这条对齐,再上规模。

三、框架对比

2026 年的 TD 全景:

2026 年论文里你读到的「RL」,九成是 Q 学习或 SARSA 的某种 elaboration。先把表格更新烂熟于心,再读深的。

与 gymnasium 经典环境的对照

gymnasium 自带的 CliffWalking-v0 是讲清 Q vs SARSA 的最佳实验台:4×12 网格,底行是 -100 的悬崖。跑两个算法各 500 回合,把最终策略可视化——Q 学习贴崖边,SARSA 偏内侧行——这是任何文字都替代不了的直觉。

四、可复用产物

本节产出一个可复用 skill(位于原课程 outputs/skill-td-agent.md)。骨架:

---
name: td-agent
description: 为表格或小特征 RL 任务,在 Q 学习 / SARSA / Expected SARSA 之间选型。
version: 1.0.0
phase: 9
lesson: 4
tags: [rl, td-learning, q-learning, sarsa]
---

给定一个表格或小特征环境,输出:

1. 算法。Q 学习 / SARSA / Expected SARSA / n 步变体。一句话理由,挂到 on vs off-policy 与方差。
2. 超参。α、γ、ε 及衰减调度。
3. 初始化。Q_0 取值(乐观 vs 零)及理由。
4. 收敛诊断。目标学习曲线;若可做 DP,检查 |Q - Q*|。
5. 部署提醒。推理时探索会怎样?是否需要 SARSA 的保守?

拒绝把表格 TD 用在状态空间 > 10⁶。
拒绝交付没有最大化偏差警示的 Q 学习。
标记任何全程 ε=1 训练(没有利用阶段)。
​

五、练习

1. 基础。 在 4×4 GridWorld 上实现 Q 学习与 SARSA,画 2000 回合的学习曲线(每 100 回合平均回报)。谁收敛更快?
2. 进阶。 搭一个悬崖行走环境(4×12,底行是 -100 的悬崖并重置到起点)。对比 Q 学习与 SARSA 的最终策略。截图各自走的路径。谁更贴崖边?
3. 挑战。 实现 Double Q 学习。在带噪声奖励的 GridWorld(每步奖励加高斯噪声 σ=5)上,展示 Q 学习会显著高估 V*(0,0),而 Double Q 学习不会。

六、常见陷阱

• 初始 Q 值很重要。 乐观初始化(负奖励任务里 Q = 0)鼓励探索;悲观初始化可能把贪心策略永远困住。
• α 调度。 非平稳问题用常数 α 就行。理论上衰减 α_n = 1/n 给出收敛,但实践太慢——把 α 钉在 [0.05, 0.3] 并盯学习曲线。
• ε 调度。 起步高(ε=1.0),衰减到 ε=0.05。GLIE(greedy in the limit with infinite exploration)是收敛条件。
• Q 学习的 max 偏差。 max 算子在 Q 有噪时向上偏。导致高估——Hasselt 的 Double Q 学习(第 05 节 DDQN 用它)用两张 Q 表修复。
• 非终止回合。 TD 没有终点也能学,但你要么封顶步数,要么在封顶处正确处理自举。标准做法:把封顶当非终点,继续自举。
• 状态哈希。 状态是元组/张量时,用可哈希的键(元组而非列表;四舍五入的浮点元组,而非原始值)。

七、关键术语速查

本节要点回顾

1. TD = MC 与 DP 的折中:每步用 r + γV(s') 自举更新,无模型、无需完整回合、在线、低方差(但有偏)。
2. TD 误差 δ = r + γV(s') - V(s) 是 MC 里 G_t - V(s_t) 的在线对应物。
3. Q 学习(off-policy)目标带 max,学 Q*,与行为策略解耦;SARSA(on-policy)目标用真实 a',学 Q^π,把探索算进价值。
4. 悬崖行走是经典判例:Q 学习贴崖边(最优但探索期吃亏),SARSA 远离崖边(更保守)。
5. Expected SARSA 用期望替代采样,方差更低,常作默认。
6. n 步 / TD(λ) 在 TD(0) 与 MC 间插值,GAE 是它在 PPO 里的现代形态。
7. 收敛条件:GLIE 探索调度 + 满足 Robbins-Monro 的 α + 所有状态无限次访问。
8. 最大化偏差让 Q 学习高估,Double Q 学习用两张表修复——这是第 05 节 DDQN 的伏笔。

下一节,我们把 Q 表换成神经网络——DQN 用经验回放 + 目标网络驯服「致命三要素」,在 Atari 上从原始像素打到人类水平。