SARSA 算法 | Codeboy's Blog

形式陈述

SARSA 的名字来自一次更新所用的五元组 $(S_t,A_t,R_{t+1},S_{t+1},A_{t+1})$ 。行为策略 $\pi_t$ 在 $S_t$ 选择 $A_t$ ，观察转移后又在 $S_{t+1}$ 实际抽取 $A_{t+1}$ ，再做

Q_{t+1}(S_t,A_t)=Q_t(S_t,A_t)+\alpha_t \bigl[R_{t+1}+\gamma Q_t(S_{t+1},A_{t+1})-Q_t(S_t,A_t)\bigr].

这是动作值上的时序差分更新。终止转移没有 $A_{t+1}$ ，续值项取零。

在固定策略下，对下一状态和实际下一动作取条件期望，目标成为

r(s,a)+\gamma\sum_{s'}P(s'\mid s,a) \sum_{a'}\pi(a'\mid s')Q(s',a'),

正是 $q_\pi$ 的 Bellman 算子。SARSA 只抽一个 $A_{t+1}$ ，因而对这个动作期望无偏但有抽样方差；Expected SARSA 显式求内层和，消除这部分方差，却仍保留状态转移与奖励噪声。

若策略固定，条件期望目标对应该策略的动作值 Bellman 方程，SARSA 是 on-policy prediction。用于控制时，常令 $\pi_t$ 对当前 $Q_t$ 为 $\varepsilon_t$ -greedy，并要求 GLIE：所有状态—动作对被无限探索，同时策略在极限中变成贪心。有限 MDP、奖励有界、 $\gamma<1$ 、每对状态—动作的步长满足

\sum_n\alpha_n(s,a)=\infty, \qquad \sum_n\alpha_n(s,a)^2<\infty,

再加上适当的 GLIE 与回合条件，可得到表格 SARSA 收敛到 $q_*$ 的经典结果。

“ $\varepsilon_t\to0$ ”本身不等于 GLIE。若衰减太快，某些动作只被尝试有限次；若保持常数 $\varepsilon$ ，则有无限探索却不在极限贪心，算法评估的是持续探索的行为而非纯贪心策略。

常见的有限动作 $\varepsilon_t$ -greedy 只有在状态本身也被反复到达、且探索概率衰减得足够慢时才可能满足无限探索。动作层的随机化无法补救动力学造成的不可达状态，也不能替代对每个状态—动作访问次数的实际检查。

直觉

SARSA 用“我下一步真的会做什么”给当前动作定价。若行为策略为了探索可能在危险状态选到保守性较差的动作，这种风险会进入目标值；所以它学习的是包含探索习惯在内的 on-policy 后果。

控制过程把评估和改进交错进行：动作值变化使行为策略更贪心，新策略又改变以后采到的数据和目标。GLIE 让探索永不完全丢失，同时使这张移动策略最终趋向贪心，恰好平衡辨识与优化。

因此同一环境转移在探索率变化后可能产生不同的下一动作目标；这种随行为策略而变的续值，正是 on-policy 的含义。

例子与边界

设样本从 $(s,a)$ 获得奖励 $0$ 到达 $u$ 。当前 $Q(s,a)=1$ ，在 $u$ 有“安全”值 $2$ 、“冒险”值 $5$ ；行为策略这次实际抽到安全动作。取 $\gamma=0.9,\alpha=1/2$ ，SARSA 目标是

0+0.9\,Q(u,\mathrm{safe})=1.8,

故

Q(s,a)\leftarrow1+\tfrac12(1.8-1)=1.4.

值为 $5$ 的动作没有被这次行为采取，所以不会出现在目标中。这不是浪费已知最大值，而是有意估计当前行为的实际续程；同一转移若交给离策略最大化目标会回答另一个问题。

GLIE 保证也有明确边界：访问条件通常需对控制过程可能相关的全部状态—动作成立；环境动力学根本到不了的状态不能靠探索策略创造。函数逼近、经验回放或并行旧策略数据会破坏严格 on-policy 结构。固定学习率的工程实现可以适应非平稳性，却不满足经典渐近步长假设。

推论与应用

在悬崖行走等问题中，持续 $\varepsilon$ -greedy 探索时，SARSA 会把靠近危险区域后的探索失误计入价值，因而可能学到较安全路线；Q-learning的最大化目标则估计贪心目标策略。比较二者必须固定训练行为和最终评估策略，否则“更安全”只是含混标签。

Expected SARSA 把实际 $A_{t+1}$ 换成对 $\pi_t(\cdot\mid S_{t+1})$ 的精确期望，减少动作抽样方差但需要枚举动作。多步 SARSA 延长信用分配范围；两种变体都要重新陈述行为策略与收敛条件。

参考资料

Gavin A. Rummery and Mahesan Niranjan, On-Line Q-Learning Using Connectionist Systems, Cambridge University Engineering Department Technical Report CUED/F-INFENG/TR 166, 1994.
Satinder P. Singh, Tommi Jaakkola, Michael L. Littman, and Csaba Szepesvári, “Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms,” Machine Learning 38, 2000, pp. 287–308.
Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, 2nd ed., MIT Press, 2018, Secs. 6.4–6.5.

形式陈述 ​

反向链接

形式陈述