Q-learning 与 SARSA

一句话总结 · 要点速览

• Q-learning 的更新为 Q(S,A) ← Q(S,A) + α[R + γ max_a Q(S',a) − Q(S,A)]，用下一状态的最大 Q 值作为目标，是异策略（off-policy）算法。
• SARSA 的更新用实际执行的下一个动作：Q(S,A) ← Q(S,A) + α[R + γQ(S',A') − Q(S,A)]，是同策略（on-policy）算法。
• 在悬崖行走中，Q-learning 学到贴着悬崖的最短路径，SARSA 学到考虑了探索风险的更安全路径，因此 SARSA 训练时的回报更高。
• Expected SARSA 用下一状态 Q 值按策略的期望作为目标，方差比 SARSA 更小。
• n 步 SARSA 用 n 步真实奖励加第 n 步的 Q 值作为目标；本站悬崖行走实测（α=0.1）中，n=3、5 的前 50 回合平均回报（−139.3、−144.9）明显好于 n=1（−209.2），但步长较大时 n 越大越不稳定。

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

SARSA 和 Q-learning 是两种最经典的 TD 控制算法，都直接学习动作价值函数 $Q(s,a)$。SARSA 是同策略（on-policy）方法，用实际执行的下一个动作来更新；Q-learning 是异策略（off-policy）方法，用下一状态的最大 Q 值来更新，因此能直接逼近最优动作价值 $q_{\ast }$。经典的“悬崖行走”例子很好地展示了两者行为上的差异：SARSA 学到更安全的路线，Q-learning 学到最短但贴着悬崖的路线。

从 TD 预测到 TD 控制

TD(0) 解决的是预测问题。要做控制，沿用 GPI 框架：

1. 估计动作价值 $Q(s,a)$（没有模型时，只有 $Q$ 才能直接用来选动作）；
2. 用相对于 $Q$ 的 ε-贪心策略选动作（兼顾探索）。

区别在于“TD 目标中下一步的价值用什么动作来估计”。

SARSA

更新规则

SARSA 的名字来自更新所用的五元组 $(S_t,A_t,R_{t+1},S_{t+1},A_{t+1})$：

$$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)]$$

其中 $A_{t+1}$ 是按当前（ε-贪心）策略实际将要执行的动作。因此 SARSA 评估的就是正在执行的策略本身，是同策略方法。

算法流程

初始化 Q(s, a) 任意，Q(终止状态, ·) = 0
对每个回合：
    初始化 S
    用 ε-贪心(Q) 选择 A
    重复直到 S 为终止状态：
        执行 A，观察 R, S'
        用 ε-贪心(Q) 选择 A'
        Q(S, A) ← Q(S, A) + α [R + γ Q(S', A') − Q(S, A)]
        S ← S'；A ← A'

在 GLIE 条件下（所有状态—动作对被无限次访问，且 ε 逐渐衰减到 0），配合合适的步长，表格 SARSA 以概率 1 收敛到最优策略。

Q-learning

更新规则

Q-learning（Watkins, 1989）的 TD 目标用下一状态所有动作中的最大值：

$$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma \underset{a}{max}Q(S_{t+1},a)-Q(S_t,A_t)]$$

这正是对 贝尔曼最优方程 $q_{\ast }(s,a)=\mathbb{E}[R_{t+1}+\gamma \underset{a^{\prime }}{max}{q}_{\ast }(S_{t+1},a^{\prime })]$ 的采样近似。

为什么是异策略

Q-learning 的目标值中，下一步动作取的是 $\arg max$，对应贪心的目标策略；而实际产生数据的是 ε-贪心的行为策略。无论行为策略如何（只要它持续访问所有状态—动作对），Q 都会收敛到 $q_{\ast }$（Watkins & Dayan, 1992）。

与 异策略 MC 不同，单步 Q-learning 不需要重要性采样：更新的是 $Q(S_t,A_t)$，而 $A_t$ 已经给定，目标中下一步的动作是按目标策略“想象”出来的，不依赖行为策略的概率。

这一性质使 Q-learning 可以使用任意来源的数据（包括旧经验），这也是 DQN 能够使用经验回放的根本原因。

扩展阅读：Q-learning 收敛性的证明思路

Watkins & Dayan（1992）以及之后基于随机逼近的证明（Jaakkola、Jordan & Singh, 1994；Tsitsiklis, 1994）的核心步骤如下（表格情形，奖励有界，$\gamma <1$）。

1. 贝尔曼最优算子是压缩映射。 定义 $(\mathcal{T}Q)(s,a)=\mathbb{E}[R_{t+1}+\gamma \underset{a^{\prime }}{max}Q(S_{t+1},a^{\prime })\mid S_t=s,A_t=a]$。对任意 $Q_1,Q_2$，利用 $|\underset{a}{max}f(a)-\underset{a}{max}g(a)|\le \underset{a}{max}|f(a)-g(a)|$：

$$\parallel \mathcal{T}{Q}_1-\mathcal{T}{Q}_2{\parallel }_{\mathrm{\infty }}\le \gamma \underset{s,a}{max}\sum _{s^{\prime }}p(s^{\prime }\mid s,a)\underset{a^{\prime }}{max}|Q_1(s^{\prime },a^{\prime })-Q_2(s^{\prime },a^{\prime })|\le \gamma \parallel Q_1-Q_2{\parallel }_{\mathrm{\infty }}$$

所以 $\mathcal{T}$ 有唯一不动点 $q_{\ast }$。

2. 把 Q-learning 写成“带噪声的不动点迭代”。 记 ${\mathrm{\Delta }}_t=Q_t-q_{\ast }$，在被更新的 $(s,a)$ 上：

$${\mathrm{\Delta }}_{t+1}(s,a)=(1-{\alpha }_t){\mathrm{\Delta }}_t(s,a)+{\alpha }_t[(\mathcal{T}{Q}_t)(s,a)-q_{\ast }(s,a)+w_t]$$

其中 $w_t=R_{t+1}+\gamma \underset{a^{\prime }}{max}{Q}_t(S_{t+1},a^{\prime })-(\mathcal{T}{Q}_t)(s,a)$ 是零均值噪声，方差被 $C(1+\parallel {\mathrm{\Delta }}_t{\parallel }_{\mathrm{\infty }}^2)$ 控制；而由第 1 步，$|(\mathcal{T}{Q}_t)(s,a)-q_{\ast }(s,a)|\le \gamma \parallel {\mathrm{\Delta }}_t{\parallel }_{\mathrm{\infty }}$。

3. 套用随机逼近定理。 若每个 $(s,a)$ 被访问无限次，且步长满足 Robbins–Monro 条件

$$\sum _t{\alpha }_t(s,a)=\mathrm{\infty },\sum _t{\alpha }_t^2(s,a)<\mathrm{\infty }$$

则上式这类“期望部分是压缩、噪声零均值且方差受控”的迭代以概率 1 收敛到 0，即 $Q_t\to q_{\ast }$。第一个条件保证步长总和足以抵消任意初始误差；第二个条件保证噪声的累积方差有限。

要点： 证明不要求行为策略是什么，只要求它无限次访问所有状态—动作对，这正是 Q-learning 异策略性质的理论依据。实践中常用的固定步长（如 0.1）不满足第二个条件，此时 Q 值会在 $q_{\ast }$ 附近小幅波动而不是严格收敛。函数近似（如 DQN）下这个证明不再成立。

Expected SARSA

Expected SARSA 把 SARSA 中的采样项换成对下一步动作的期望：

$$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma \sum _a\pi (a\mid S_{t+1})Q(S_{t+1},a)-Q(S_t,A_t)]$$

它消除了 $A_{t+1}$ 采样带来的方差，通常比 SARSA 更稳定，可以使用更大的步长。当目标策略 $\pi$ 是贪心策略时，Expected SARSA 就退化为 Q-learning。

悬崖行走（Cliff Walking）对比实验

Gymnasium 的 CliffWalking-v1 是一个 4×12 的网格（Sutton & Barto 例 6.6）：起点在左下角，终点在右下角，两者之间的底边是悬崖。每走一步奖励 −1，掉下悬崖奖励 −100 并被送回起点。最短路径是贴着悬崖走（13 步，回报 −13）。

"""SARSA 与 Q-learning 在 CliffWalking-v1（悬崖行走）上的对比。"""
import gymnasium as gym
import numpy as np

env = gym.make("CliffWalking-v1")
nS, nA = env.observation_space.n, env.action_space.n


def eps_greedy(Q, s, eps, rng):
    if rng.random() < eps:
        return int(rng.integers(nA))
    q = Q[s]
    return int(rng.choice(np.flatnonzero(q == q.max())))   # 随机打破平局


def train(method, episodes=500, alpha=0.1, gamma=1.0, eps=0.1, seed=0):
    rng = np.random.default_rng(seed)
    Q = np.zeros((nS, nA))
    returns = []
    for ep in range(episodes):
        s, _ = env.reset(seed=seed * 10_000 + ep)
        a = eps_greedy(Q, s, eps, rng)
        G, done = 0.0, False
        while not done:
            s2, r, term, trunc, _ = env.step(a)
            done = term or trunc
            G += r
            a2 = eps_greedy(Q, s2, eps, rng)
            if method == "sarsa":
                target = r + gamma * Q[s2, a2] * (not term)
            else:  # Q-learning
                target = r + gamma * np.max(Q[s2]) * (not term)
            Q[s, a] += alpha * (target - Q[s, a])
            s, a = s2, a2
        returns.append(G)
    return Q, np.array(returns)


def greedy_return(Q):
    s, _ = env.reset()
    G = 0
    for _ in range(100):
        s, r, term, trunc, _ = env.step(int(np.argmax(Q[s])))
        G += r
        if term or trunc:
            break
    return G


for method in ["sarsa", "q_learning"]:
    online, greedy = [], []
    for seed in range(10):
        Q, rets = train(method, seed=seed)
        online.append(rets[-100:].mean())
        greedy.append(greedy_return(Q))
    print(f"{method:10s} 训练中（ε=0.1）最后100回合平均回报: {np.mean(online):7.1f} | "
          f"贪心策略回报: {np.mean(greedy):6.1f}")

参数：$\alpha =0.1$、$\gamma =1$、$\epsilon =0.1$，每种方法训练 500 回合，10 个随机种子取平均。实际运行输出：

sarsa      训练中（ε=0.1）最后100回合平均回报:   -21.5 | 贪心策略回报:  -15.4
q_learning 训练中（ε=0.1）最后100回合平均回报:   -49.6 | 贪心策略回报:  -13.0

结果解读：

• Q-learning 学到了最优路径：贪心策略回报恰好是 −13（10 个种子全部如此），即贴着悬崖走的最短路线。
• 但训练时 Q-learning 的表现更差（−49.6 对 −21.5）：因为执行的是 ε-贪心策略，贴着悬崖走时偶尔的随机动作会让它掉下去。
• SARSA 学到的是更安全的路线：它评估的是“带探索的”策略本身，知道靠近悬崖时随机动作的风险，因此选择离悬崖远一些的路线，训练时回报更高；它的贪心路线平均 −15.4（10 个种子中多数为 −15 或 −17）。

这个例子说明：同策略方法学习的是它实际执行的策略的价值，异策略方法学习的是目标策略的价值。如果训练过程中的表现也很重要（例如真实机器人不能经常“掉下悬崖”），SARSA 这类同策略方法更合适。

我们也观察到：当 $\alpha =0.5$（书中设置）时，个别种子下 SARSA 学到的贪心策略会在某些很少访问的状态之间来回打转，无法到达终点；把 $\alpha$ 降到 0.1 后 10 个种子都能正常到达。

代码：表格型 Q-learning

上面的 train 函数就是完整的表格型实现，核心只有几行：

if method == "sarsa":
    target = r + gamma * Q[s2, a2] * (not term)        # 用实际将执行的 A'
else:  # Q-learning
    target = r + gamma * np.max(Q[s2]) * (not term)    # 用 max_a Q(S', a)
Q[s, a] += alpha * (target - Q[s, a])

在 FrozenLake 上的 Q-learning 示例见 Gymnasium 上手。

n 步 SARSA

单步 SARSA 的目标只用一步真实奖励，其余全靠 $Q(S_{t+1},A_{t+1})$ 的估计（自举）；蒙特卡洛则用完整回报、完全不自举。n 步方法介于两者之间：用 $n$ 步真实奖励，再加上第 $n$ 步之后的估计：

$$G_{t: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})$$

（若回合在 $t+n$ 之前结束，就只累加到终止为止，不再自举。）n 步 SARSA 用它替换单步目标：

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

实现时要等到时刻 $t+n$ 才能更新 $Q(S_t,A_t)$，所以需要缓存最近 $n$ 步的状态、动作和奖励；回合结束后，再把剩下尚未更新的时刻补完。它的取舍与 TD 学习 中讨论的一致：

• $n$ 越大，奖励信息向前传播得越快（一次更新就能把 $n$ 步之外的奖励传回来），目标的偏差越小；
• 但目标中包含更多随机奖励和随机动作，方差越大，通常需要更小的步长。

注意 n 步 SARSA 仍是同策略的：$n$ 步中的动作都来自当前的 ε-贪心策略。若想做 n 步 Q-learning（异策略），中间步骤的动作来自行为策略而非贪心目标策略，就需要重要性采样或 Tree Backup 等修正，这也是练习 5 的答案线索。

实验：悬崖行走上的 n = 1、3、5

设置与上面相同（$\epsilon =0.1$、$\gamma =1$、500 回合、10 个种子），比较两种步长：

"""n 步 SARSA（on-policy，ε-贪心）在 CliffWalking-v1 上的对比：n = 1, 3, 5。
n 步目标：G_{t:t+n} = r_{t+1} + γ r_{t+2} + ... + γ^{n-1} r_{t+n} + γ^n Q(s_{t+n}, a_{t+n})。"""
import gymnasium as gym
import numpy as np

env = gym.make("CliffWalking-v1")
nS, nA = env.observation_space.n, env.action_space.n
EPISODES, SEEDS, GAMMA, EPS = 500, 10, 1.0, 0.1


def eps_greedy(Q, s, eps, rng):
    if rng.random() < eps:
        return int(rng.integers(nA))
    q = Q[s]
    return int(rng.choice(np.flatnonzero(q == q.max())))


def nstep_sarsa(n, alpha, seed):
    rng = np.random.default_rng(seed)
    Q = np.zeros((nS, nA)); returns = []
    for ep in range(EPISODES):
        s, _ = env.reset(seed=seed * 10_000 + ep)
        S, A, R = [s], [eps_greedy(Q, s, EPS, rng)], [0.0]      # R[0] 占位，使 R[t+1] 对应第 t 步的奖励
        T, t = np.inf, 0
        while True:
            if t < T:
                s2, r, term, trunc, _ = env.step(A[t])
                S.append(s2); R.append(r)
                if term or trunc:
                    T = t + 1
                else:
                    A.append(eps_greedy(Q, s2, EPS, rng))
            tau = t - n + 1                                     # 本步要更新的时刻
            if tau >= 0:
                G = sum(GAMMA ** (i - tau - 1) * R[i] for i in range(tau + 1, int(min(tau + n, T)) + 1))
                if tau + n < T:
                    G += GAMMA ** n * Q[S[tau + n], A[tau + n]]
                Q[S[tau], A[tau]] += alpha * (G - Q[S[tau], A[tau]])
            if tau == T - 1:
                break
            t += 1
        returns.append(sum(R))
    return np.array(returns)


if __name__ == "__main__":
    print(f"CliffWalking，ε={EPS}，{EPISODES} 回合 × {SEEDS} 个种子；回报越接近 0 越好（最优路径为 -13）")
    for n in (1, 3, 5):
        for alpha in (0.1, 0.5):
            R = np.stack([nstep_sarsa(n, alpha, sd) for sd in range(SEEDS)])
            print(f"n={n}  α={alpha:.1f}  前50回合平均回报 {R[:, :50].mean():7.1f}  "
                  f"最后100回合平均回报 {R[:, -100:].mean():6.1f}")

实际运行输出：

CliffWalking，ε=0.1，500 回合 × 10 个种子；回报越接近 0 越好（最优路径为 -13）
n=1  α=0.1  前50回合平均回报  -209.2  最后100回合平均回报  -22.3
n=1  α=0.5  前50回合平均回报  -105.0  最后100回合平均回报  -26.2
n=3  α=0.1  前50回合平均回报  -139.3  最后100回合平均回报  -23.9
n=3  α=0.5  前50回合平均回报  -107.1  最后100回合平均回报  -37.7
n=5  α=0.1  前50回合平均回报  -144.9  最后100回合平均回报  -26.7
n=5  α=0.5  前50回合平均回报  -136.6  最后100回合平均回报  -46.0

结果解读：

• 小步长时，多步目标让前期学得更快：$\alpha =0.1$ 时，前 50 回合的平均回报从 $n=1$ 的 −209.2 提高到 $n=3$ 的 −139.3、$n=5$ 的 −144.9。奖励（尤其是掉下悬崖的 −100）能更快地传回较早的状态。
• 后期 $n=1$ 反而略好（−22.3 对 −23.9、−26.7）：多步目标包含了更多 ε-贪心的随机动作，学到的价值更“悲观”、方差也更大。
• 大步长时，$n$ 越大越不稳定：$\alpha =0.5$ 时最后 100 回合回报随 $n$ 从 −26.2 降到 −37.7、−46.0。多步目标的方差与大步长叠加，Q 值来回震荡。
• 结论：$n$ 与步长 $\alpha$ 需要一起调；这也是 DQN 改进中常用 3 步回报（Rainbow）、并配合较小学习率的原因之一。

从表格到函数近似：通往 DQN

表格方法要为每个 $(s,a)$ 存一个数，状态空间稍大就不可行（例如 Atari 画面）。解决办法是用参数化函数 $Q(s,a;\theta )$ 近似，并把 Q-learning 更新改写为最小化 TD 误差：

$$L(\theta )=\mathbb{E}\left[{(R_{t+1}+\gamma \underset{a}{max}Q(S_{t+1},a;{\theta }^{-})-Q(S_t,A_t;\theta ))}^2\right]$$

但“函数近似 + 自举 + 异策略”三者同时出现会导致训练不稳定，Sutton & Barto 称之为致命三要素（deadly triad）。DQN 用经验回放和目标网络缓解了这个问题。

常见问题与技巧

• Q 值初始化：乐观初始化（例如全部初始化为较大值）可以鼓励早期探索。
• 平局处理：初期 Q 值全为 0，np.argmax 总是返回第一个动作，可能导致系统性偏差。示例代码用随机打破平局。
• ε 的衰减：训练初期大量探索，后期逐渐减小 ε。
• 最大化偏差：Q-learning 的 $max$ 会系统性地高估 Q 值（因为对噪声取最大值）。Double Q-learning（van Hasselt, 2010）用两套 Q 表分别选择和评估动作来消除这一偏差，它是 Double DQN 的前身。

小结

	SARSA	Q-learning	Expected SARSA
TD 目标	$R+\gamma Q(S^{\prime },A^{\prime })$	$R+\gamma \underset{a}{max}Q(S^{\prime },a)$	$R+\gamma \sum _a\pi (a\mid S^{\prime })Q(S^{\prime },a)$
类型	同策略	异策略	均可
学到的是	当前 ε-贪心策略的价值	最优价值 $q_{\ast }$	目标策略 $\pi$ 的价值
悬崖行走表现	安全路线，训练回报高	最短路线，训练回报低	介于两者之间

n 步 SARSA 把 SARSA 的单步目标换成 $n$ 步回报加自举，在偏差与方差之间折中。

练习题

1. 在例题中加入 Expected SARSA，并比较三者在训练中的回报和贪心策略回报。
2. 把 ε 逐渐衰减到 0（例如 ${\epsilon }_k=1/k$），SARSA 最终学到的路线会变成什么？为什么？
3. 实现 Double Q-learning，在悬崖行走上与 Q-learning 比较。
4. 把 $\alpha$ 改回 0.5，打印 SARSA 学到的贪心路线，复现“来回打转”的现象，并解释原因。
5. 为什么单步 Q-learning 不需要重要性采样，而 n 步 Q-learning 需要？
6. 在 nstep_sarsa_cliff.py 中把 $n$ 扩展到 10 和 20，并把 $\alpha$ 降到 0.05，观察前期学习速度与最终回报的变化。

参考文献

• Watkins, C. J. C. H. (1989). Learning from Delayed Rewards. PhD thesis, University of Cambridge.
• Watkins, C. J. C. H., & Dayan, P. (1992). Q-learning. Machine Learning, 8, 279–292.
• Rummery, G. A., & Niranjan, M. (1994). On-line Q-learning using connectionist systems. Technical Report CUED/F-INFENG/TR 166, Cambridge University.（SARSA 的提出）
• van Seijen, H., van Hasselt, H., Whiteson, S., & Wiering, M. (2009). A theoretical and empirical analysis of Expected Sarsa. IEEE ADPRL.
• van Hasselt, H. (2010). Double Q-learning. NeurIPS.
• Jaakkola, T., Jordan, M. I., & Singh, S. P. (1994). On the convergence of stochastic iterative dynamic programming algorithms. Neural Computation, 6(6), 1185–1201.
• Tsitsiklis, J. N. (1994). Asynchronous stochastic approximation and Q-learning. Machine Learning, 16, 185–202.
• Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.), 第 7 章（n 步自举）.

下一步

继续阅读：Gymnasium 上手——熟悉标准环境接口，亲手训练 FrozenLake 智能体。