SARSA算法

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

SARSA算法最早是由G.A. Rummery, M. Niranjan在1994年提出的，当时称为“改进型联结主义Q学习”（Modified Connectionist Q-Learning）。理查德·S·薩頓提出了使用替代名SARSA。

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

算法

 for each step in episode
  执行动作 ，观察奖励  和下一步状态 
  基于当前的  和 ，根据特定策略（如ε-greedy）选择 

  ；
 until 状态  终止

在选择下一步动作时，采用ε-greedy策略，即：
 以 ε 的概率随机选择下一个动作
 以 1-ε 的概率选择可以最大化的下一个动作

在该算法中，超参数  为学习速率， 为折扣因子。

在更新时，对比Q学习使用  作为预估，SARSA则使用  作为预估。一些针对Q学习的提出优化方法也可以应用于SARSA上。

相关条目
 强化学习
 Q学习
 馬可夫決策過程

参考文献

Category:機器學習演算法