# Q-learning 与 SARSA

> 来源：https://dqn.cn/basics/q-learning-sarsa ｜ 作者：DQN.CN 编辑部 ｜ 发布：2026-10-29 ｜ 更新：2026-10-30 ｜ 许可：CC BY-NC-SA 4.0（文字）/ MIT（代码）

> **要点速览**
>
> - 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_*$。经典的“悬崖行走”例子很好地展示了两者行为上的差异：SARSA 学到更安全的路线，Q-learning 学到最短但贴着悬崖的路线。

## 从 TD 预测到 TD 控制

[TD(0)](https://dqn.cn/basics/td-learning) 解决的是预测问题。要做控制，沿用 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\left[R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)\right]
$$

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

### 算法流程

```text
初始化 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\left[R_{t+1} + \gamma \max_{a} Q(S_{t+1}, a) - Q(S_t, A_t)\right]
$$

这正是对 [贝尔曼最优方程](https://dqn.cn/basics/bellman) $q_*(s, a) = \mathbb{E}[R_{t+1} + \gamma \max_{a'} q_*(S_{t+1}, a')]$ 的采样近似。

### 为什么是异策略

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

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

这一性质使 Q-learning 可以使用任意来源的数据（包括旧经验），这也是 [DQN](https://dqn.cn/advanced/dqn) 能够使用经验回放的根本原因。

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

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

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

$$
\|\mathcal{T}Q_1 - \mathcal{T}Q_2\|_\infty \le \gamma \max_{s, a} \sum_{s'} p(s' \mid s, a) \max_{a'} |Q_1(s', a') - Q_2(s', a')| \le \gamma \|Q_1 - Q_2\|_\infty
$$

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

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

$$
\Delta_{t+1}(s, a) = (1 - \alpha_t)\, \Delta_t(s, a) + \alpha_t \left[ (\mathcal{T}Q_t)(s, a) - q_*(s, a) + w_t \right]
$$

其中 $w_t = R_{t+1} + \gamma \max_{a'} Q_t(S_{t+1}, a') - (\mathcal{T}Q_t)(s, a)$ 是零均值噪声，方差被 $C(1 + \|\Delta_t\|_\infty^2)$ 控制；而由第 1 步，$|(\mathcal{T}Q_t)(s, a) - q_*(s, a)| \le \gamma \|\Delta_t\|_\infty$。

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

$$
\sum_t \alpha_t(s, a) = \infty, \qquad \sum_t \alpha_t^2(s, a) < \infty
$$

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

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

## Expected SARSA

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

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

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

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

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

```python
"""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$、$\varepsilon = 0.1$，每种方法训练 500 回合，10 个随机种子取平均。实际运行输出：

```text
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` 函数就是完整的表格型实现，核心只有几行：

```python
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 上手](https://dqn.cn/basics/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\left[G_{t:t+n} - Q(S_t, A_t)\right]
$$

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

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

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

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

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

```python
"""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}")
```
实际运行输出：

```text
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[\left(R_{t+1} + \gamma \max_a Q(S_{t+1}, a; \theta^-) - Q(S_t, A_t; \theta)\right)^2\right]
$$

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

## 常见问题与技巧

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

## 小结

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

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

## 练习题

1. 在例题中加入 Expected SARSA，并比较三者在训练中的回报和贪心策略回报。
2. 把 ε 逐渐衰减到 0（例如 $\varepsilon_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 上手](https://dqn.cn/basics/gymnasium)——熟悉标准环境接口，亲手训练 FrozenLake 智能体。

## 常见问题速查（FAQ）

**问：Q-learning 和 SARSA 的核心区别是什么？**

答：目标中下一个动作的取法不同：Q-learning 取使 Q 最大的动作（学习贪心策略的价值，异策略），SARSA 取实际按 ε-贪心选出的动作（学习当前行为策略的价值，同策略）。

**问：为什么 Q-learning 在悬崖行走中训练回报更低？**

答：Q-learning 学的是贴着悬崖的最优路径，但训练时仍按 ε-贪心探索，偶尔会掉下悬崖受到 −100 的惩罚；SARSA 把探索的风险计入价值，选择离悬崖更远的路径。本站实测训练中回报 SARSA 约 −21.5、Q-learning 约 −49.6。

**问：n 步 SARSA 的 n 越大越好吗？**

答：不是。n 越大，目标中真实奖励越多、自举越少，偏差更小、信息传播更快，但方差更大。本站悬崖行走实验中，α=0.1 时 n=3、5 前期学得更快；α=0.5 时最后 100 回合平均回报随 n 增大从 −26.2 降到 −46.0。实践中 n 取 3 到 5 较常见，并需配合较小的步长。

**问：Q-learning 能处理连续状态吗？**

答：表格型 Q-learning 不能直接处理连续或高维状态，需要用函数近似（如神经网络）表示 Q 函数，这就是 DQN。

## 如何引用本文

DQN.CN 编辑部. Q-learning 与 SARSA[EB/OL]. DQN.CN, 2026-10-29（更新于 2026-10-30）. https://dqn.cn/basics/q-learning-sarsa.