SARSA算法

SARSA算法是机器学习领域的一种强化学习算法，得名于“状态-动作-奖励-状态-动作”（State–Action–Reward–State–Action）的英文首字母缩写。

SARSA算法最早是由G.A. Rummery, M. Niranjan在1994年提出的，当时称为“改进型联结主义Q学习”（Modified Connectionist Q-Learning）。^[1]Richard S. Sutton（英语：Richard S. Sutton）提出了使用替代名SARSA。^[2]

SARSA算法和Q学习算法的区别主要在期望奖励Q值的更新方法上。SARSA算法使用五元组(s_t, a_t, r_t, s_t+1, a_t+1)来进行更新，其中s、a、r分别为马可夫决策过程（MDP）中的状态、动作、奖励，t和t+1分别为当前步和下一步。^[3]

算法

for each step in episode 执行动作 ${\displaystyle a_{t}}$ ，观察奖励 ${\displaystyle r_{t}}$  和下一步状态 ${\displaystyle s_{t+1}}$  基于当前的 ${\displaystyle Q}$  和 ${\displaystyle s_{t+1}}$ ，根据特定策略（如ε-greedy）选择 ${\displaystyle a_{t+1}}$  ${\displaystyle Q^{new}(s_{t},a_{t})\leftarrow Q(s_{t},a_{t})+\alpha \,[r_{t}+\gamma \,Q(s_{t+1},a_{t+1})-Q(s_{t},a_{t})]}$  ${\displaystyle s_{t}\leftarrow s_{t+1}}$ ；${\displaystyle a_{t}\leftarrow a_{t+1}}$  until 状态 ${\displaystyle s}$  终止 

在选择下一步动作${\displaystyle a_{t+1}}$ 时，采用ε-greedy策略，即：

• 以 ε 的概率随机选择下一个动作
• 以 1-ε 的概率选择可以最大化${\displaystyle Q(s_{t+1},a_{t+1})}$ 的下一个动作

在该算法中，超参数 ${\displaystyle \alpha }$  为学习速率，${\displaystyle \gamma }$  为折扣因子。

在更新${\displaystyle Q}$ 时，对比Q学习使用 ${\displaystyle {\text{max}}_{a}Q(s_{t+1},a)}$  作为预估，SARSA则使用 ${\displaystyle Q(s_{t+1},a_{t+1})}$  作为预估。^[4]一些针对Q学习的提出优化方法也可以应用于SARSA上。^[5]

相关条目

• 强化学习
• Q学习
• 馬可夫決策過程

参考文献

1. Online Q-Learning using Connectionist Systems" by Rummery & Niranjan (1994). [2022-07-14]. （原始内容于2013-06-08）. 
2. Jeevanandam, Nivash. Underrated But Fascinating ML Concepts #5 – CST, PBWM, SARSA, & Sammon Mapping. Analytics India Magazine. 2021-09-13 [2021-12-05]. （原始内容于2021-12-05） （英语）. 
3. Richard S. Sutton and Andrew G. Barto. Sarsa: On-Policy TD Control. Reinforcement Learning: An Introduction. [2022-07-14]. （原始内容于2020-07-05）. 
4. TINGWU WANG. Tutorial of Reinforcement: A Special Focus on Q-Learning (PDF). cs.toronto. [2022-07-14]. （原始内容 (PDF)于2022-07-14）. 
5. Wiering, Marco; Schmidhuber, Jürgen. Fast Online Q(λ) (PDF). Machine Learning. 1998-10-01, 33 (1): 105–115 [2022-07-14]. ISSN 0885-6125. S2CID 8358530. doi:10.1023/A:1007562800292  . （原始内容 (PDF)于2018-10-30） （英语）.