SARSA算法

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

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

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

算法

for each step in episode
 执行动作 $a_{t}$，观察奖励 $r_{t}$ 和下一步状态 $s_{t+1}$
 基于当前的 $Q$ 和 $s_{t+1}$，根据特定策略（如ε-greedy）选择 $a_{t+1}$
 $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})]$
 $s_{t}\leftarrow s_{t+1}$；$a_{t}\leftarrow a_{t+1}$
until 状态 $s$ 终止

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

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

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

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

相关条目

• 强化学习
• Q学习
• 马可夫决策过程