深度强化学习（四）SARSA算法

一.SARSA

假设状态空间 $\mathcal{S}$ 和动作空间 $\mathcal{A}$ 都是有限集, 即集合中元素数量有限。比如, $\mathcal{S}$ 中一共有 3 种状态, $\mathcal{A}$ 中一共有 4 种动作。那么动作价值函数 $Q_{\pi }(s,a)$ 可以表示为一个 $3\times 4$ 的表格。该表格与一个策略函数 $\pi (a\mid s)$ 相关联; 如果 $\pi$ 发生变化,表格 $Q_{\pi }$ 也会发生变化。

我们用表格 $q$ 近似 $Q_{\pi }$ 。首先初始化 $q$, 可以让它是全零的表格。然后用表格形式的 SARSA 算法更新 $q$,每次更新表格的一个元素。最终 $q$ 收敛到 $Q_{\pi }$ 。

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_{\pi }\left(s_t,a_t\right)$ 可以近似成 $q\left(s_t,a_t\right)。q\left(s_t,a_t\right)$ 是表格在 $t$ 时刻对 $Q_{\pi }\left(s_t,a_t\right)$做出的估计。
• 方程右边的期望是关于下一时刻状态 $S_{t+1}$ 和动作 $A_{t+1}$ 求的。给定当前状态 $s_t$, 智能体执行动作 $a_t$, 环境会给出奖励 $r_t$ 和新的状态 $s_{t+1}$ 。然后基于 $s_{t+1}$ 做随机抽样,得到新的动作
  $${\tilde{a}}_{t+1}\sim \pi \left(\cdot \mid s_{t+1}\right).$$

用观测到的 $r_t、s_{t+1}$ 和计算出的 ${\tilde{a}}_{t+1}$ 对期望做蒙特卡洛近似, 得到:
$$r_t+\gamma \cdot Q_{\pi }\left(s_{t+1},{\tilde{a}}_{t+1}\right).$$

• 进一步把公式 (5.1) 中的 $Q_{\pi }$ 近似成 $q$, 得到
  $${\hat{y}}_t\triangleq r_t+\gamma \cdot q\left(s_{t+1},{\tilde{a}}_{t+1}\right).$$

把它称作 TD 目标。它是表格在 $t+1$ 时刻对 $Q_{\pi }\left(s_t,a_t\right)$ 做出的估计。
$q\left(s_t,a_t\right)$ 和 ${\hat{y}}_t$ 都是对动作价值 $Q_{\pi }\left(s_t,a_t\right)$ 的估计。由于 ${\hat{y}}_t$ 部分基于真实观测到的奖励 $r_t$,我们认为 ${\hat{y}}_t$ 是更可靠的估计, 所以鼓励 $q\left(s_t,a_t\right)$ 趋近 ${\hat{y}}_t$ 。更新表格 $\left(s_t,a_t\right)$ 位置上的元素:
$$q\left(s_t,a_t\right)\leftarrow (1-\alpha )\cdot q\left(s_t,a_t\right)+\alpha \cdot {\hat{y}}_t.$$

这样可以使得 $q\left(s_t,a_t\right)$ 更接近 ${\hat{y}}_t$ 。 SARSA 算法用到了这个五元组： $\left(s_t,a_t,r_t,s_{t+1},{\tilde{a}}_{t+1}\right)$ 。SARSA 算法学到的 $q$ 依赖于策略 $\pi$, 这是因为五元组中的 ${\tilde{a}}_{t+1}$ 是根据 $\pi \left(\cdot \mid s_{t+1}\right)$ 抽样得到的。

训练流程：设当前表格为 $q_{\text{now }}$, 当前策略为 ${\pi }_{\text{now }}$ 每一轮更新表格中的一个元素,把更新之后的表格记作 $q_{\text{new }}$ 。

1. 观测到当前状态 $s_t$, 根据当前策略做抽样: $a_t\sim {\pi }_{\text{now }}\left(\cdot \mid s_t\right)$ 。
2. 把表格 $q_{\text{now }}$ 中第 $\left(s_t,a_t\right)$ 位置上的元素记作:
   $${\hat{q}}_t=q_{\text{now }}\left(s_t,a_t\right).$$
3. 智能体执行动作 $a_t$ 之后, 观测到奖励 $r_t$ 和新的状态 $s_{t+1}$ 。
4. 根据当前策略做抽样: ${\tilde{a}}_{t+1}\sim {\pi }_{\text{now }}\left(\cdot \mid s_{t+1}\right)$ 。注意, ${\tilde{a}}_{t+1}$ 只是假想的动作, 智能体不予执行。
5. 把表格 $q_{\text{now }}$ 中第 $\left(s_{t+1},{\tilde{a}}_{t+1}\right)$ 位置上的元素记作:
   $${\hat{q}}_{t+1}=q_{\text{now }}\left(s_{t+1},{\tilde{a}}_{t+1}\right).$$
6. 计算 TD 目标和 TD 误差:
   $${\hat{y}}_t=r_t+\gamma \cdot {\hat{q}}_{t+1},{\delta }_t={\hat{q}}_t-{\hat{y}}_t.$$
7. 更新表格中 $\left(s_t,a_t\right)$ 位置上的元素:
   $$q_{\text{new }}\left(s_t,a_t\right)\leftarrow q_{\text{now }}\left(s_t,a_t\right)-\alpha \cdot {\delta }_t.$$
8. 用某种算法更新策略函数。该算法与 SARSA 算法无关。

二.神经网络形式的SARSA

价值网络：如果状态空间 $\mathcal{S}$ 是无限集, 那么我们无法用一张表格表示 $Q_{\pi }$, 否则表格的行数是无穷。一种可行的方案是用一个神经网络 $q(s,a;\mathbf{w})$ 来近似 $Q_{\pi }(s,a)$; 理想情况下，
$$q(s,a;\mathbf{w})=Q_{\pi }(s,a),\forall s\in \mathcal{S},a\in \mathcal{A}$$
训练流程 : 设当前价值网络的参数为 ${\mathbf{w}}_{\mathrm{now}}$, 当前策略为 ${\pi }_{\mathrm{now}}$ 每一轮训练用五元组 $\left(s_t,a_t,r_t,s_{t+1},{\tilde{a}}_{t+1}\right)$ 对价值网络参数做一次更新。

1. 观测到当前状态 $s_t$, 根据当前策略做抽样: $a_t\sim {\pi }_{\text{now }}\left(\cdot \mid s_t\right)$ 。

2. 用价值网络计算 $\left(s_t,a_t\right)$ 的价值:
   $${\hat{q}}_t=q\left(s_t,a_t;{\mathbf{w}}_{\text{now }}\right).$$

3. 智能体执行动作 $a_t$ 之后, 观测到奖励 $r_t$ 和新的状态 $s_{t+1}$ 。

4. 根据当前策略做抽样: ${\tilde{a}}_{t+1}\sim {\pi }_{\mathrm{now}}\left(\cdot \mid s_{t+1}\right)$ 。注意, ${\tilde{a}}_{t+1}$ 只是假想的动作, 智能体不予执行。

5. 用价值网络计算 $\left(s_{t+1},{\tilde{a}}_{t+1}\right)$ 的价值:
   $${\hat{q}}_{t+1}=q\left(s_{t+1},{\tilde{a}}_{t+1};{\mathbf{w}}_{\text{now }}\right).$$

6. 计算 TD 目标和 TD 误差:
   $${\hat{y}}_t=r_t+\gamma \cdot {\hat{q}}_{t+1},{\delta }_t={\hat{q}}_t-{\hat{y}}_t.$$

7. 对价值网络 $q$ 做反向传播, 计算 $q$ 关于 $\mathbf{w}$ 的梯度: ${\nabla }_{\mathbf{w}}q\left(s_t,a_t;{\mathbf{w}}_{\text{now }}\right)$ 。

8. 更新价值网络参数:
   $${\mathbf{w}}_{\text{new }}\leftarrow {\mathbf{w}}_{\text{now }}-\alpha \cdot {\delta }_t\cdot {\nabla }_{\mathbf{w}}q\left(s_t,a_t;{\mathbf{w}}_{\text{now }}\right).$$

9. 用某种算法更新策略函数。该算法与 SARSA 算法无关。