[RL Notes] 期望 Sarsa
Contents
1. 期望 Sarsa
回顾 Sarsa 预测算法 的更新规则
\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}
其中 $S_{t+1}$ 来自环境的动态特征 $p(s’,r|s,a)$，$A_{t+1}$ 来自策略 $\pi(a’|s’)$。但智能体的策略是已知的，因此可以直接计算 $Q(S_{t+1}, A_{t+1})$ 在给定 $S_{t+1}$ 下的期望，而不必采样 $A_{t+1}$。由此得到一个新的更新规则
\begin{align}
Q(S_t, A_t) &\leftarrow Q(S_t, A_t) + \alpha \big[ R_{t+1} + \gamma \mathbb{E}[Q(S_{t+1}, A_{t+1})|S_{t+1}] – Q(S_t, A_t) \big] \\
&\leftarrow Q(S_t, A_t) + \alpha \big[ R_{t+1} + \gamma \sum_{a}\pi(a|S_{t+1})Q(S_{t+1}, a) – Q(S_t, A_t) \big] \tag{2}
\end{align}
给定状态 $S_{t+1}$，上面的更新规则会确定地向期望意义上的 Sarsa 算法所决定的方向上移动，称为期望 Sarsa。
相比 Sarsa 算法，期望 Sarsa 的计算要更复杂，但具有更稳定的更新目标。
2. 一个例子
举例来说，假设对于某个 $S_{t+1}$，有 $4$ 个可选动作，动作的收益都为 $1$，每个动作的价值 $Q(S_{t+1}, a’)$ 和选择该动作的概率 $\pi(a’|S_{t+1})$ 如表 1 所示。
表 1
| $a’$ | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $Q(S_{t+1}, a’)$ | 0.0 | -1.0 | 2.0 | 1.0 |
| $\pi(a’|S_{t+1})$ | 0.1 | 0.1 | 0.7 | 0.1 |
对于 Sarsa 算法，会通过采样计算更新，式 $(1)$ 中的目标 $R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})$ 可能为
\begin{equation}
1 + \gamma \times 0.0 \\
1 + \gamma \times (-1.0) \\
1 + \gamma \times 2.0 \\
1 + \gamma \times 1.0
\end{equation}
虽然这些更新的大小甚至方向都不同，但通过多次采样，这些更新会收敛到期望
\begin{equation}
1 + \gamma [0.1 \times 0.0 + 0.1 \times (-1) + 0.7 \times 2.0 + 0.1 \times 1.0] = 1 + \gamma(1.4)
\end{equation}
而期望 Sarsa 算法会直接使用期望 $1 + \gamma(1.4)$ 进行更新，其更新目标的方差远小于 Sarsa 算法。期望 Sarsa 算法在每个时刻都要对所有可选择的动作计算期望，如果可选择的动作数量太多，期望 Sarsa 算法会带来更大的计算量。
3. 离轨期望 Sarsa
式 $(2)$ 中计算期望 $\mathbb{E}[Q(S_{t+1}, A_{t+1})|S_{t+1}]$ 使用的是 $\sum_{a}\pi(a|S_{t+1})Q(S_{t+1}, a)$，其中的动作 $a$ 来自策略 $\pi$。通过将策略 $\pi$ 替换为其他行动策略 $b$，就得到离轨策略的算法。
如果目标策略 $\pi$ 是一个贪心策略，而行动策略式一种试探性的策略，使用表 1 所示的例子，此时 $\pi(a’|S_{t+1})$ 选择具有最大价值的动作的概率为 $1$，选择其他动作的概率为 $0$，如表 2 所示。
表 2
| $a’$ | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $Q(S_{t+1}, a’)$ | 0.0 | -1.0 | 2.0 | 1.0 |
| $\pi(a’|S_{t+1})$ | 0.0 | 0.0 | 1.0 | 0.0 |
此时计算 $Q(S_{t+1}, a’)$ 的期望就相当于求 $Q(S_{t+1}, a’)$ 的最大值，即
\begin{equation}
\sum_{a’}\pi(a’|S_{t+1})Q(S_{t+1}, a’) = \max_{a’} Q(S_{t+1}, a’)
\end{equation}
可见此时期望 Sarsa 与 Q 学习完全相同。因此可以将期望 Sarsa 看成是 Q 学习的推广，将 Q 学习看成是期望 Sarsa 的特例。