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算法使用五元组(s_t, a_t, r_t, s_t+1, a_t+1)来进行更新，其中s、a、r分别为马可夫决策过程（MDP）中的状态、动作、奖励，t和t+1分别为当前步和下一步。

算法

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

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

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

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

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

相关条目

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