[RL Notes] 重要度采样和离轨蒙特卡洛预测
Contents
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}(\text{策略 } \pi \text{ 的轨迹})}{\mathrm{Pr}(\text{策略 } b \text{ 的轨迹})} \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\limits_{k=t}^{T-1} \pi(A_k|S_k) p(S_{k+1}|S_k, A_k)}{\prod\limits_{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}
上面的算法通过计算平均实现重要度采样，称为简单重要度采样。