[RL Notes] 期望 Sarsa

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