SARSA算法的引入
SARSA算法不需要环境的状态转化模型，是不基于模型的强化学习问题求解方法。对于它的控制问题的求解与蒙特卡洛法相似，即通过价值函数的更新来更新当前的策略，再通过新的策略来产生新的状态和即时奖励从而更新价值函数。
SARSA算法属于在线控制的时序差分法，即一直使用一个策略来更新价值函数和选择新的动作，而这个策略是\(\epsilon\)-贪婪法。
SARSA算法概述
在迭代的时候，我们首先基于ϵ−贪婪法在当前状态S选择一个动作A，这样系统会转到一个新的状态S′, 同时给我们一个即时奖励R, 在新的状态S′，我们会基于ϵ−贪婪法在状态S′选择一个动作A′，但是注意这时候我们并不执行这个动作A′，只是用来更新的我们的价值函数，价值函数的更新公式是：
\[ Q(S,A) = Q(S,A) + \alpha(R+\gamma Q(S',A') - Q(S,A)) \]
其中\(\gamma\)是衰减因子，\(\alpha\)是步长。这里和蒙特卡洛算法的主要区别在与收获\(G_t\)的表达式不同，对于时序差分，收获\(G_t\)的表达式是\(R+\gamma Q(S',A')\)。
SARSA算法流程
算法输入：迭代轮数\(T\)，状态集\(S\)，动作集\(A\)，步长\(\alpha\)，衰减因子\(\gamma\)，探索率\(\epsilon\)
输出：所有的状态和动作对应的价值\(Q\)
- 随机初始化所有的状态和动作对应的价值\(Q\)。对于终止状态其\(Q\)值初始化为0
- for i from i to T, 进行迭代
- 初始化\(S\)为当前序列的第一个状态，设置\(A\)为\(\epsilon\)-贪婪法在当前状态选择的动作
- 在状态\(S\)执行当前动作\(A\)，得到新状态\(S'\)以及奖励\(R\)
- 用\(\epsilon\)-贪婪法在状态\(S'\)选择新的动作\(A'\)
- 更新价值函数\(Q(S,A)\)：\(Q(S,A) = Q(S,A) + \alpha(R+\gamma Q(S',A') - Q(S,A))\)
- \(S=S', A=A'\)
- 如果\(S\)是终止状态，则当前轮迭代完毕，否则转到步骤2.2
一般来说，\(\alpha\)一般需要随着迭代的进行而逐渐变小，这样才能保证动作价值函数的收敛。
SARSA算法实践
使用SARSA算法解决Windy Gridworld问题。具体实践参照我的github。