[RL Note] 重要度采样和离轨蒙特卡洛预测

1. 基于重要度采样的离轨策略

  前文中的蒙特卡洛预测算法通过计算回报的平均值来估计状态价值,即

\begin{equation}
v_\pi(s) \doteq \mathbb{E}_\pi[G_t|S_t = s] = \mathrm{average}(Returns(s)) \tag{1}
\end{equation}

而在离轨策略中,样本是通过行动策略获得的,此时计算回报的平均值估计的是行动策略而非目标策略的状态价值。

  为了在离轨策略中估计目标策略的状态价值,需要使用重要度采样比对行动策略的样本回报进行修正,这里重要度采样比 $\rho$ 的定义为

\begin{equation}
\rho = \frac{\mathrm{Pr}(策略\;\pi\;的轨迹)}{\mathrm{Pr}(策略\;b\;的轨迹)} \tag{2}
\end{equation}

给定起始状态 $S_t$,后续的状态-动作轨迹 $A_t, S_{t+1}, A_{t+1}, \cdots, S_T$ 在策略 $\pi$ 下发生的概率为

\begin{align}
&\mathrm{Pr}(A_t, S_{t+1}, A_{t+1}, \cdots, S_T|S_t, A_{t:T-1} \sim \pi) \\
&= \pi(A_t|S_t)p(S_{t+1}|S_t, A_t) \pi(A_{t+1}|S_{t+1}) \cdots p(S_T|S_{T-1}, A_{T-1}) \\
&= \prod_{k=t}^{T-1} \pi(A_k|S_k) p(S_{k+1}|S_k, A_k) \tag{3}
\end{align}

其中 $p$ 是MDP 的状态转移概率,且通常是未知的。于是可得目标策略和行动策略轨迹下的相对概率即重要度采样比为

\begin{equation}
\rho_{t:T-1} \doteq \frac{\prod_{k=t}^{T-1} \pi(A_k|S_k) p(S_{k+1}|S_k, A_k)}{\prod_{k=t}^{T-1} b(A_k|S_k) p(S_{k+1}|S_k, A_k)} = \prod_{k=t}^{T-1}\frac{\pi(A_k|S_k)}{b(A_k|S_k)} \tag{4}
\end{equation}

虽然式 $(3)$ 所示的轨迹概率值与 MDP 的状态转移概率 $p$ 有关,但式 $(4)$ 所示的重要度采样比却与 MDP 的状态转移概率无关,而只与两个策略和样本序列数据有关。

  通过式 $(4)$ 所示的重要度采样比对行动策略的样本回报进行修正,得到目标策略的期望值

\begin{equation}
\mathbb{E}[\rho_{t:T-1} G_t | S_t = s] = v_\pi(s) \tag{5}
\end{equation}

2. 离轨每次访问型 MC 预测

  只需对蒙特卡洛预测算法进行简单的修改,即可得到对应的离轨策略算法:在对每幕无限循环中,根据行动策略 $b$ 而不是目标策略 $\pi$ 生成序列,并在更新 $G$ 时引入重要度采样比修正项 $W$。完整算法如下所示。


离轨每次访问型 MC 预测算法,用于估计 $V_\pi \approx v_\pi$
输入:待评估的策略 $\pi$
初始化:
  对所有 $s \in \mathcal S$,任意初始化 $V(s) \in \mathbb R$
  对所有 $s \in \mathcal S$,$Returns(s) \leftarrow 空列表$
无限循环(对每幕):
  根据 $b$ 生成一幕序列:$S_0, A_0, R_1, S_1, A_1, R_2, \cdots, S_{T-1}, A_{T-1}, R_T$
  $G \leftarrow 0 \qquad W \leftarrow 1$
  对本幕中的每一步进行循环, $t = T-1, T-2, \cdots, 0$:
    $G \leftarrow \gamma W G + R_{t+1}$
    将 $G$ 加入 $Returns(S_t)$
    $V(S_t) \leftarrow \mathrm{average}(Returns(S_t))$
    $W \leftarrow W\frac{\pi(A_t|S_t)}{b(A_t|S_t)}$


  注意上面的算法中对 $\rho_{t:T-1}$ 计算是增量的,由式 $(4)$ 可知

\begin{equation}
\rho_{t:T-1} = \prod_{k=t}^{T-1}\frac{\pi(A_k|S_k)}{b(A_k|S_k)} = \rho_t \rho_{t+1} \rho_{t+2} \cdots \rho_{T-2} \rho_{T-1}
\end{equation}

算法中对每一幕的序列进行逆序遍历,依次计算

\begin{align}
W_1 &\leftarrow \rho_{T-1} \\
W_2 &\leftarrow W_1 \rho_{T-2} = \rho_{T-1}\rho_{T-2} \\
W_3 &\leftarrow W_2 \rho_{T-3} = \rho_{T-1}\rho_{T-2}\rho_{T-3} \\
\vdots
\end{align}

  上面的算法通过计算平均实现重要度采样,称为简单重要度采样