Processing math: 0%

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