[RL Notes] Sarsa：同轨策略下的时序差分控制
1. 预测算法
通过 TD(0) 算法可以得到状态价值函数，而为了在广义策略迭代中使用时序差分方法，我们需要的是动作价值函数。
不同于 TD(0) 算法中只考虑状态之间的转换，现在要考虑“状态-动作”二元组之间的转换，并学习每个“状态-动作”二元组的价值。类似 TD(0) 对状态价值的更新，对“状态-动作”二元组价值的更新如下所示。
\begin{equation}
Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \big[ R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) – Q(S_t, A_t) \big] \tag{1}
\end{equation}
式 $(1)$ 所示的更新规则使用了五元组 $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$，智能体在状态 $S_t$ 选择动作 $A_t$，收到了收益 $R_t$ 并进入状态 $S_{t+1}$。由于预测的是“状态-动作”二元组的价值，因此还需要知道 $t+1$ 时刻选择的动作 $A_{t+1}$，才能更新 $(S_t, A_t)$ 的价值。$A_{t+1}$ 可以通过所要评价的策略 $\pi$ 来生成。上述算法称为 Sarsa 算法，取自五元组 $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$ 的字母。
通过 Sarsa 算法，就可以学习某个特定策略的动作状态价值函数，以此进行策略评估。
2. 控制算法
基于 Sarsa 预测算法，可以很容易地得到一个同轨策略的控制算法——持续地估计行动策略 $\pi$ 的动作价值函数 $q_\pi$，并以 $q_\pi$ 为基础朝着贪心优化的方向改变 $\pi$。此外也可以采用 $\varepsilon$-贪心或 $\varepsilon$-软性策略。完整算法如下所示。
Sarsa（同轨策略下的 TD 控制）算法，用于估计 $Q \approx q_\pi$
对所有 $s \in mathcal{S}$，$a \in \mathcal{A}(s)$，任意初始化 $Q(s, a)$，其中 $Q(终止状态, \cdot) = 0$
对每幕循环：
初始化 $S$
使用从 $Q$ 得到的策略（例如 $\varepsilon$-贪心），在 $S$ 处选择 $A$
对幕中的每一步循环：
执行动作 $A$，观察到 $R, S’$
使用从 $Q$ 得到的策略（例如 $\varepsilon$-贪心），在 $S’$ 处选择 $A’$
$Q(S, A) \leftarrow Q(S, A) + \alpha \big[ R + \gamma Q(S’, A’) – Q(S_t, A_t) \big]$
$S \leftarrow S’; \; A \leftarrow A’;$
直到 $S$ 是终止状态