RL-03-03-算法-SARSA

← 上级：RL-03.算法分类与选型 · 对照：RL-03-02-算法-Q-Learning

SARSA（State-Action-Reward-State-Action）是与 Q-Learning 并列的表格型 TD 算法，区别在于它是 On-Policy：更新时使用实际采取的下一动作 $a’$，而非 $\max_{a’} Q(s’,a’)$。

段末注释：SARSA 名称来自更新所需五元组 $(S,A,R,S’,A’)$；后文沿用 SARSA。

---

一、更新公式

$$
Q(s,a) \leftarrow Q(s,a) + \alpha \left[ r + \gamma Q(s’, a’) - Q(s,a) \right]
$$

其中 $a’$ 是在 $s’$ 下行为策略（常为 $\varepsilon$-greedy）实际选择的动作。

与 Q-Learning 对比：

算法	TD 目标
Q-Learning	$r + \gamma \max_{a’} Q(s’,a’)$
SARSA	$r + \gamma Q(s’, a’)$

---

二、算法流程

1. 初始化 $Q$。
2. 每个 episode：$s \leftarrow reset$。
3. 用 $\varepsilon$-greedy 选 $a$。
4. 循环：
   • 执行 $a$，得 $r, s’$
   • 用 $\varepsilon$-greedy 在 $s’$ 选 $a’$
   • 更新 $Q(s,a)$（用上式）
   • $s \leftarrow s’$，$a \leftarrow a’$
   • 若终止则跳出

注意：SARSA 在选 $a’$ 之后才完成当前步更新，因此必须「先选下一步动作再更新」。

---

三、伪代码

s = env.reset()
a = epsilon_greedy(Q[s], eps)
while not done:
    s_next, r, done, _ = env.step(a)
    a_next = epsilon_greedy(Q[s_next], eps)
    td_target = r + gamma * Q[s_next, a_next]
    Q[s, a] += alpha * (td_target - Q[s, a])
    s, a = s_next, a_next

---

四、悬崖行走（Cliff Walking）经典对比

网格中智能体从起点到终点，悬崖格踩中得大负奖励：

算法	学到路径	原因
Q-Learning	沿悬崖边缘最短路径	学 $Q^*$，假设未来全贪心
SARSA	绕远避开悬崖	考虑探索时可能「滑落」的风险

这体现 Off-Policy 乐观 vs On-Policy 保守：部署策略若含探索噪声，SARSA 更贴近真实回报。

---

五、Expected SARSA（补充）

用下一状态策略的期望代替单个 $a’$：

$$
Q(s,a) \leftarrow Q(s,a) + \alpha \left[ r + \gamma \sum_{a’} \pi(a’|s’) Q(s’,a’) - Q(s,a) \right]
$$

$\varepsilon$-greedy 下可解析计算期望，方差常小于 SARSA，仍可为 Off-Policy（若 $\pi$ 为行为策略）。

---

六、超参与选型

场景	建议
教学、小离散 MDP	Q-Learning 或 SARSA 均可
在线部署含持续探索	倾向 SARSA
学最优策略、数据可离策略复用	Q-Learning → DQN

---

七、小结

• SARSA = On-Policy TD，TD 目标含真实 $a’$。
• 与 Q-Learning 一对照，理解 Off/On-Policy 差异最直观。
• 上一篇：Q-Learning · 下一篇：蒙特卡洛与时序差分