SARSA算法

SARSA（State-Action-Reward-State-Action）是一个学习马尔可夫决策过程策略的算法，通常应用于机器学习和强化学习学习领域中。它由Rummery 和 Niranjan在技术论文“Modified Connectionist Q-Learning（MCQL）” 中介绍了这个算法，并且由Rich Sutton在注脚处提到了SARSA这个别名。

State-Action-Reward-State-Action这个名称清楚地反应了其学习更新函数依赖的5个值，分别是当前状态S1，当前状态选中的动作A1，获得的奖励Reward，S1状态下执行A1后取得的状态S2及S2状态下将会执行的动作A2。我们取这5个值的首字母串起来可以得出一个词SARSA。

算法的核心思想可以简化为：

Latex代码：

$$Q(^{s\boldsymbol{t}\prime a_{t}})\leftarrow Q(s_{\boldsymbol{t}},a_{t})+\alpha [r_{\boldsymbol{t}}+\gamma Q(s_{t+1},a_{\boldsymbol{t}+1})-Q(^{st\prime a_{t}})$$

它包含了三个参数:

学习率 (Alpha)

学习率决定了新获取的信息覆盖旧信息的程度。Alpha为0时，表示让代理不学习任何东西，Alpha为1时，表示让代理只考虑最新的信息。

折扣系数 (Gamma)

折扣因素决定了未来奖励的重要性。Gamma为0时，会让代理变得 "机会主义"，只会考虑目前的奖励，而当Gamma接近1时，会让代理争取长期高回报。如果折扣系数达到或超过 1, 则Q的值可能会发散。

初始条件 (Q（s0，a0）)

由于 SARSA 是一个迭代算法，所以在第一次更新发生之前，它隐式地假定初始条件。一个低 (无限) 初始值，也被称为 "乐观初始条件"，可以鼓励探索。无论发生什么行动, 更新规则导致它具有比其他替代方案更高的价值，从而增加他们的选择概率。

用伪代码可以表示为：

从伪代码中可以直观地看出，SARSA算法通过一直不断更新 Q 的值，然后再根据新的Q值来判断要在某个状态（state）应该采取怎样的行动（action）。

来源：Sutton & Barto Book: Reinforcement Learning: An Introduction，http://incompleteideas.net/book/the-book-2nd.html

发展历史

1994年，G.A. Rummery 和 M.Niranjan 在 Modified Connectionist Q-learning 论文中的脚注提及了SARSA。

1996年，R.S. Sutton 正式提出了SARSA的概念。

主要事件

发展分析

瓶颈

SARSA 算法经常与Q-learning 算法作比较，以便探索出两种算法分别适用的情况。它们互有利弊。

与SARSA相比，Q-learning具有以下优点和缺点：

• Q-learning直接学习最优策略，而SARSA在探索时学会了近乎最优的策略。
• Q-learning具有比SARSA更高的每样本方差，并且可能因此产生收敛问题。当通过Q-learning训练神经网络时，这会成为一个问题。
• SARSA在接近收敛时，允许对探索性的行动进行可能的惩罚，而Q-learning会直接忽略，这使得SARSA算法更加保守。如果存在接近最佳路径的大量负面报酬的风险，Q-learning将倾向于在探索时触发奖励，而SARSA将倾向于避免危险的最佳路径并且仅在探索参数减少时慢慢学会使用它。

如果是在模拟中或在低成本和快速迭代的环境中训练代理，那么由于第一点（直接学习最优策略），Q-learning是一个不错的选择。 如果代理是在线学习，并且注重学习期间获得的奖励，那么SARSA算法更加适用。

未来发展方向

SARSA目前用于机器学习的强化学习方向。因为Sarsa 的整个循环都将是在一个路径上，也就是 on-policy，下一个 state_，和下一个 action_ 将会变成他真正采取的 action 和 state， 所以可以用于On-policy TD control。

Contributor: Tiange Wang