SARSA

SARSA 是一种经典的 TD 算法。SARSA 是 state-action-reward-state-action 的缩写，原因是它使用 $(s_t,a_t,r_t,s_{t+1},a_{t+1})$ 这样的五元组来进行更新。

SARSA 的 TD 目标

SARSA 可以由下面的贝尔曼方程推导出来：

$$Q_{\pi }\left(s_t,a_t\right)={\mathbb{E}}_{S_{t+1},A_{t+1}}\left[R_t+\gamma \cdot Q_{\pi }\left(S_{t+1},A_{t+1}\right)\mid S_t=s_t,A_t=a_t\right]$$

对方程两边作近似：

• 使用函数估计器 $q$ (表格或神经网络) 来估计 $Q_{\pi }$
• 将期望近似为抽样。具体来说，给定当前状态 $s_t$ 和动作 $a_t$，我们可以通过执行动作 $a_t$ 来获得奖励 $r_t$ 和下一个状态 $s_{t+1}$，然后基于 $s_{t+1}$ 抽样得到新动作 ${\tilde{a}}_{t+1}\sim \pi (\cdot |s_{t+1})$，得到 $r_t+\gamma Q_{\pi }(s_{t+1},{\tilde{a}}_{t+1})\approx r_t+\gamma q(s_{t+1},{\tilde{a}}_{t+1})$

于是我们得到 SARSA 的 TD 目标：

$${\hat{y}}_t=r_t+\gamma q(s_{t+1},{\tilde{a}}_{t+1})$$

更新规则

$q(s_t,a_t)$ 和 ${\hat{y}}_t$ 都是对于 $Q_{\pi }(s_t,a_t)$ 的估计，但是 ${\hat{y}}_t$ 是一个更好的估计，因为它使用了更多的信息。所以我们鼓励函数估计器去逼近 ${\hat{y}}_t$。

对于学习率为 $\alpha$ 的表格型 SARSA：

$$q(s_t,a_t)=(1-\alpha )q(s_t,a_t)+\alpha {\hat{y}}_t$$

对于学习率为 $\alpha$ 的使用神经网络 (参数记为 $w$ ) 的 SARSA：

$$\begin{array}{rl}L(w)& =\frac{1}{2}{\left[q(s_t,a_t;w)-{\hat{y}}_t\right]}^2\\ {\Delta }_{w}L(w)& =\left(q(s_t,a_t;w)-{\hat{y}}_t\right){\nabla }_{w}q(s_t,a_t;w)\\ w& \leftarrow w-\alpha \left(q(s_t,a_t;w)-{\hat{y}}_t\right){\nabla }_{w}q(s_t,a_t;w)\end{array}$$

训练流程

将函数估计器设为 $q_{\text{now}}$，当前策略为 ${\pi }_{\text{now}}$

1. 观察当前状态 $s_t$
2. 根据当前策略 ${\pi }_{\text{now}}$ 采样动作 $a_t\sim {\pi }_{\text{now}}(\cdot |s_t)$
3. 计算 ${\hat{q}}_t=q_{\text{now}}(s_t,a_t)$
4. 执行动作 $a_t$，观察奖励 $r_t$ 和下一个状态 $s_{t+1}$
5. 根据当前策略 ${\pi }_{\text{now}}$ 采样动作 ${\tilde{a}}_{t+1}\sim {\pi }_{\text{now}}(\cdot |s_{t+1})$
6. 计算 ${\hat{q}}_{t+1}=q_{\text{now}}(s_{t+1},{\tilde{a}}_{t+1})$
7. 计算 TD 目标 ${\hat{y}}_t=r_t+\gamma {\hat{q}}_{t+1}$
8. 按照更新规则更新函数估计器 $q_{\text{now}}$
9. 更新策略，注意策略的生成方式与 SARSA 无关