[RL Notes] 期望 Sarsa

Author: nex3z 2019-10-29

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 的特例。