SARSA 与 Q-Learning 算法详解与探索策略对比
引言
在强化学习中，时序差分 (Temporal Difference, TD) 学习是一类无需环境模型、通过经验进行学习的核心方法。TD 控制算法的目标是学习最优策略，即在每个状态下选择哪个动作可以最大化长期累积奖励。SARSA 和 Q-Learning 是两种最基础且重要的 TD 控制算法，它们在学习方式上有着本质的区别：
- SARSA (State-Action-Reward-State-Action): 一种 同策略 (On-Policy) TD 控制算法。它学习的是智能体当前正在执行的策略（包含探索）的价值。
- Q-Learning: 一种 异策略 (Off-Policy) TD 控制算法。它可以学习最优策略的价值，即使智能体实际执行的是另一个不同的（通常更具探索性的）策略。
本文将详细比较这两种算法的核心差异，并通过实例解释其工作原理，最后探讨除了经典的 \(\epsilon\)-greedy 之外的其他探索策略。
SARSA vs. Q-Learning: 核心对比
理解 SARSA 和 Q-Learning 的关键在于它们的更新规则以及这规则背后所蕴含的策略评估方式。
更新规则对比
假设在时间步 \(t\)，智能体处于状态 \(S_t\)，根据其行为策略（通常是 \(\epsilon\)-greedy）选择了动作 \(A_t\)，执行后观察到奖励 \(R_{t+1}\) 和下一个状态 \(S_{t+1}\)。
SARSA 更新规则: 还需要知道在 \(S_{t+1}\) 状态下，根据当前策略选择的下一个实际动作 \(A_{t+1}\)。 使用五元组 \((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}\) 是智能体在 \(S_{t+1}\) 状态实际将要执行的动作。
Q-Learning 更新规则: 只需要知道 \((S_t, A_t, R_{t+1}, S_{t+1})\) 四元组。它在更新时不关心下一个实际执行的动作是什么，而是直接考虑在 \(S_{t+1}\) 状态下采取最优动作能带来的价值： \[ 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] \] 这里的 \(\max_{a'} Q(S_{t+1}, a')\) 表示在状态 \(S_{t+1}\) 下，所有可能的动作 \(a'\) 中能够获得的最大 Q 值。
关键差异表格
| 特征/步骤 | SARSA (同策略) | Q-Learning (异策略) | 关键差异说明 |
|---|---|---|---|
| 目标策略 | 学习当前行为策略 \(\pi\) (例如 \(\epsilon\)-greedy) 的价值函数 \(Q_{\pi}\) | 学习最优策略 \(\pi^*\) 的价值函数 \(Q^*\)，与行为策略 \(\mu\) 无关 | SARSA 评估正在执行的策略，Q-Learning 直接评估最优策略。 |
| 行为策略 | 通常与目标策略相同 (\(\pi = \mu\)) | 可以与目标策略不同 (\(\mu \ne \pi^*\))，通常更具探索性 | SARSA 依赖当前策略产生的完整轨迹；Q-Learning 可以利用任何充分探索数据的策略。 |
| 策略类型 | 同策略 (On-Policy) | 异策略 (Off-Policy) | SARSA 的学习和行为紧密耦合；Q-Learning 将学习目标（最优）与实际行为（探索）分离。 |
| 更新所需信息 | \((S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})\) (五元组) | \((S_t, A_t, R_{t+1}, S_{t+1})\) (四元组) | SARSA 需要知道下一步的实际动作；Q-Learning 不需要。 |
| TD 目标计算 | \(R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})\) | \(R_{t+1} + \gamma \max_{a'} Q(S_{t+1}, a')\) | SARSA 使用实际下一步动作的 Q 值；Q-Learning 使用下一步最优动作的 Q 值。 |
| 对探索动作的处理 | 将探索动作的（可能次优的）后果纳入学习过程。 | 在更新 Q 值时忽略探索动作的实际后果，总是假设采取最优动作。 | SARSA 更”保守”，会因探索带来的风险而调整策略；Q-Learning 更”激进”，直接学习最优路径，无视探索风险。 |
| 典型例子 (CliffWalking) | 倾向于学习远离悬崖的”安全”路径。 | 倾向于学习贴近悬崖的”危险”但理论上最短的路径。 | 反映了同策略与异策略在处理探索风险上的差异。 |
| 收敛性 | 在一定条件下（如 GLIE 策略）收敛到当前策略的最优动作价值函数 \(Q_{\pi}\)。 | 在一定条件下收敛到全局最优动作价值函数 \(Q^*\)。 | Q-Learning 直接收敛到最优解，而 SARSA 收敛到其执行策略下的最优解。 |
实例解释 (简单 A-B-C 例子)
回顾之前的例子：状态 A, B, C (终止)，动作 left, right。从 A 执行 right 到 B (R=+1)。更新 \(Q(A, \text{`right`})\)。 当前 \(Q(B, \text{`left`})=2.0\), \(Q(B, \text{`right`})=5.0\)。\(\gamma=0.9\), \(\epsilon=0.1\)。
- SARSA:
- 在 B 状态，以 0.95 概率选
right(\(A_{t+1}\)=\(\text{`right`}\)), TD 目标 = \(1 + 0.9 * 5.0 = 5.5\)。 - 在 B 状态，以 0.05 概率选
left(\(A_{t+1}\)=\(\text{`left`}\)), TD 目标 = \(1 + 0.9 * 2.0 = 2.8\)。 - SARSA 的更新目标取决于实际选择的 \(A_{t+1}\)。
- 在 B 状态，以 0.95 概率选
- Q-Learning:
- 在 B 状态，找到 \(\max(Q(B, \text{`left`}), Q(B, \text{`right`})) = 5.0\)。
- TD 目标 = \(1 + 0.9 * 5.0 = 5.5\)。
- Q-Learning 的更新目标始终是基于最优选择，与实际选择的 \(A_{t+1}\) 无关。
这个例子清晰地展示了 SARSA 如何受实际行为（包括探索）的影响，而 Q-Learning 如何始终以最优动作为目标进行更新。
探索策略：超越 Epsilon-Greedy
为了让 TD 控制算法能够学习到最优策略，智能体需要在探索 (Exploration)（尝试新的、未知的动作以发现潜在更好的选择）和利用 (Exploitation)（选择当前已知的最佳动作以获取最大奖励）之间取得平衡。 \(\epsilon\)-greedy 是最常用的策略之一，但并非唯一选择。
1. Epsilon-Greedy (\(\epsilon\)-greedy)
- 机制: 以 \(1-\epsilon\) 的概率选择当前 Q 值最高的动作（利用），以 \(\epsilon\) 的概率从所有可用动作中随机选择一个（探索）。
- 优点: 简单、易于实现。理论上保证在一定条件下（如 \(\epsilon\) 随时间衰减）能探索所有状态-动作对。
- 缺点: 探索是完全随机的，不够智能。即使某个探索动作明显很差，它仍有 \(\epsilon/|A|\) 的概率被选中。当有多个较优动作时，它只选择 Q 值最高的那一个（在利用时），忽略了其他可能也较好的动作。
- 衰减 \(\epsilon\): 通常会让 \(\epsilon\) 随着学习的进行而逐渐减小，使得智能体在早期更多地探索，在后期更多地利用已学到的知识。
2. 乐观初始值 (Optimistic Initial Values)
- 机制: 在学习开始时，将所有的 Q 值初始化为一个远高于实际可能最大值的数（例如，对于奖励范围在 [-1, 1] 的环境，可以初始化为 5）。
- 原理: 智能体最初会倾向于尝试所有动作，因为它们都被赋予了很高的初始价值。只有当一个动作被尝试多次，其 Q 值因为实际获得的奖励而下降到低于其他动作的初始值时，智能体才会”放弃”对该动作的探索。这鼓励了对未知状态-动作对的系统性探索。
- 优点: 实现简单，有时能非常有效地引导探索，尤其是在早期阶段。
- 缺点: 需要对奖励的可能范围有一个估计来设定合适的初始值。对于非平稳环境（奖励或转移会变化）可能效果不佳。它更像是一种启发式方法。
- 适用性: 可用于 SARSA 和 Q-Learning。
3. 上置信界 (Upper Confidence Bound, UCB)
- 机制: 选择动作时，不仅考虑其当前的 Q 值估计，还考虑其不确定性。选择能最大化以下表达式的动作 \(a\): [ A_t = ] 其中： * \(Q_t(a)\) 是动作 \(a\) 在时间 \(t\) 的估计价值。 * \(\ln t\) 是时间 \(t\) 的自然对数，随时间增长。 * \(N_t(a)\) 是动作 \(a\) 在时间 \(t\) 之前被选择的次数。 * \(c > 0\) 是一个常数，用于控制探索的程度。
- 原理: 第二项 \(c \sqrt{\frac{\ln t}{N_t(a)}}\) 是不确定性或探索奖励。如果一个动作被选择的次数 \(N_t(a)\) 很少，或者时间 \(t\) 增长得很快，这一项就会变大，增加了该动作被选中的可能性，即使其当前 \(Q_t(a)\) 不高。这鼓励探索那些不经常被尝试的动作。
- 优点: 比 \(\epsilon\)-greedy 更”智能”，倾向于探索更有潜力的动作。有较好的理论保证（尤其是在多臂老虎机问题中）。
- 缺点: 实现比 \(\epsilon\)-greedy 复杂，需要记录每个动作的选择次数。在非平稳环境中可能需要调整。
- 适用性: 主要思想源于多臂老虎机，可以直接应用于 Q-Learning。对于 SARSA，由于其同策略性质，直接应用 UCB 来选择 \(A_{t+1}\) 可能稍微复杂，但其核心思想（平衡价值和不确定性）仍然可以借鉴。
4. Boltzmann 探索 (Softmax Exploration)
- 机制: 根据动作的 Q 值，以概率方式选择动作。Q 值越高的动作被选中的概率越大，但 Q 值较低的动作仍有一定概率被选中。通常使用 Softmax 函数计算选择概率： [ P(a | S_t) = ] 其中 \(\tau > 0\) 是”温度”参数： * \(\tau \to \infty\): 概率趋于均匀分布（纯探索）。 * \(\tau \to 0^+\): 概率趋于选择 Q 值最高的动作（纯利用）。
- 原理: 提供了一种平滑的方式来根据动作价值进行探索。相比 \(\epsilon\)-greedy，它更倾向于选择价值相对较高的动作，而不是完全随机。
- 优点: 能够根据价值差异调整探索程度。
- 缺点: 需要调整温度参数 \(\tau\)。计算概率涉及指数运算，可能比 \(\epsilon\)-greedy 稍慢。
- 衰减 \(\tau\): 通常会让 \(\tau\) 随时间衰减，从高温（更多探索）到低温（更多利用）。
- 适用性: 可以直接用于 SARSA 和 Q-Learning 的行为策略。
5. Thompson Sampling (主要用于 Bandit 问题，可启发 RL)
- 机制: 为每个动作的价值维护一个概率分布（例如，Beta 分布用于二元奖励，高斯分布用于连续奖励）。在选择动作时，从每个动作的当前价值分布中采样一个值，然后选择采样值最大的那个动作。根据观察到的奖励更新相应动作的价值分布。
- 原理: 通过贝叶斯方法来估计不确定性。一个动作被尝试的次数越多，其价值分布就越集中；反之则越分散。采样过程自然地平衡了利用（选择分布均值高的动作）和探索（选择分布方差大，即不确定性高的动作）。
- 优点: 在 Bandit 问题中表现通常非常好，是一种非常有效的探索方法。
- 缺点: 将其直接扩展到完整的强化学习（涉及状态）比较复杂，计算成本较高。
- 适用性: 其核心思想（根据后验分布采样）可以启发更高级的 RL 探索策略，但直接应用不如前几种常见。
结论
SARSA 和 Q-Learning 是 TD 控制的基石。
- SARSA (同策略): 学习正在执行的策略，对探索的风险敏感，可能学习到更保守但安全的策略。
- Q-Learning (异策略): 学习最优策略，不受实际行为策略探索风险的影响，可能学习到理论上最优但更”危险”的策略。
选择哪种算法取决于具体应用场景。如果需要考虑实际执行策略（包含探索）的性能和风险，SARSA 可能是更好的选择。如果目标是直接学习最优策略，并且可以容忍行为策略带来的探索风险（或者使用离线数据），Q-Learning 更为常用。
选择合适的探索策略对于算法的性能至关重要。\(\epsilon\)-greedy 是最简单常用的方法，但乐观初始值、UCB 和 Boltzmann 探索等提供了更智能、有时更高效的探索机制。理解这些策略的原理和优缺点，有助于根据具体问题选择或设计更有效的探索方法。