什么是SARSA
SARSA算法的全称是State Action Reward State Action，属于时序差分学习算法的一种，其综合了动态规划算法和蒙特卡洛算法，比仅仅使用蒙特卡洛方法速度要快很多。当时序差分学习算法每次更新的动作数为最大步数时，就等价于蒙特卡洛方法。
值函数更新公式的引入：多次试验的平均
SARSA的核心思想在于增量计算。在蒙特卡洛算法中，我们需要对函数
进行有效的估计，假设第
次试验后值函数为
的平均为：
其中表示轨迹
的起始状态和动作为
,
。
省却以上公式的中间过程，我们可以将该公式简化为如下：
在该公式中，值函数在第
次试验后的值
，即
次试验的平均等于前
次试验再加上一个增量。在该公式中，
可以表示成第
次试验相对于前
次试验的重要性。
值函数更新公式的改进：权重参数的调整
更一般性的，我们可以将权重系数改成一个比较小的正数
，由此，以上公式可以被改写成为以下：
其中，增量称为蒙特卡洛误差，表示真实的回报与期望回报之间的差距。
值函数更新公式的改进：累积奖励的计算
在上面的公式中，为一次试验的完整轨迹所得到的总回报，为了提高效率，放宽模型的约束，可以借助动态规划算法来计算
，而不需要得到完整的轨迹。
从开始，采样下一步的状态和动作
，并得到奖励
，然后利用贝尔曼方程来近似估计函数
。
贝尔曼方程的思想精髓在于动态规划，即当前值的计算依赖于上一时刻的值。对于无最终状态的情况，我们定义了折扣率来重点强调现世的回报。
将以上公式结合，可以得到以下计算公式：
这种策略学习算法称为算法。
通用
算法框架：一个示例
一个通用的算法如下所示：
SARSA算法框架
该算法的大致逻辑如下：
- 运行完一个回合即一个内循环。
- 运行直到
函数收敛即为一个外循环。
- 运行期间动态更新
。
时序差分学习和蒙特卡罗方法的主要不同为:蒙特卡罗需要完整一个路径完成才能知道其总回报，也不依赖马尔可夫性质；而时序差分学习只需要一步，其总回报需要依赖马尔可夫性质来进行近似估计。
