[RL Notes] 加权重要度采样及增量实现
Contents
1. 加权重要度采样
MC 预测算法中使用的简单重要度采样定义为
\begin{equation}
V(s) \doteq \frac{\sum\limits_{t \in \mathcal{T}(s)} \rho_{t:T(t)-1} G_t}{|\mathcal{T}(s)|} \tag{1}
\end{equation}
其中 $\mathcal{T}(s)$ 为所有访问过状态 $s$ 的集合，$T(t)$ 表示在时刻 $t$ 后首次终止，$G_t$ 表示在 $t$ 之后到达 $T(t)$ 时的回报，$\{G_t\}_{t \in \mathcal{T}(s)}$ 为状态 $s$ 对应的回报，$\{\rho_{t:T(t)-1}\}_{t \in \mathcal{T}(s)}$ 为相应的重要度采样比。简单重要度采样只是简单地计算平均值。
另外还可以使用加权平均的方法，称为加权重要度采样，定义为
\begin{equation}
V(s) \doteq \frac{\sum\limits_{t \in \mathcal{T}(s)} \rho_{t:T(t)-1} G_t}{\sum\limits_{t \in \mathcal{T}(s)} \rho_{t:T(t)-1} } \tag{2}
\end{equation}
如果式 $(2)$ 中的分母为零，则该式的定义也为零。
2. 增量实现
假设有一个回报序列 $G_1, G_2, \cdots, G_{n-1}$，它们都从相同的状态开始，每一个回报对应一个随机权重 $W_t$（如前面的重要度采样比 $W_t = \rho_{t:T(t)-1}$），使用加权重要度采样时，需要估计
\begin{equation}
V_n \doteq \frac{\sum\limits_{k=1}^{n-1} W_k G_k}{\sum\limits_{k=1}^{n-1} W_k}, \quad n \geq 2 \tag{3}
\end{equation}
我们希望能跟踪 $V_n$ 的变化，从而使用增量的方式对其进行更新
\begin{equation}
V_{n+1} \doteq V_n + \frac{W_n}{C_n} [G_n – V_n], \quad n \geq 1 \tag{4}
\end{equation}
其中
\begin{equation}
C_{n+1} \doteq C_n + W_{n+1} \tag{4}
\end{equation}
定义 $C_0 \doteq 0$。
由此可以得到增量实现离轨策略 MC 预测算法如下所示。
离轨策略 MC 预测算法（策略评估），用于估计 $Q \approx q_\pi$
输入：一个任意的目标策略 $\pi$
初始化：对所有 $s \in \mathcal{S}$，$a \in \mathcal{A(s)}$：
任意初始化 $Q(s, a) \in \mathbb{R}$
$C(s, a) \leftarrow 0$
无限循环（对每幕）：
$b \leftarrow$ 任何能包括 $\pi$ 的策略
根据 $b$ 生成一幕序列：$S_0, A_0, R_1, \cdots, S_{T-1}, A_{T-1}, R_T$
$G \leftarrow 0$
$W \leftarrow 1$
对幕中的每一步循环，$t = T-1, T-2, \cdots, 0$，当 $W \neq 0$ 时：
$G \leftarrow \gamma G + R_{t+1}$
$C(S_t, A_t) \leftarrow C(S_t, A_t) + W$
$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \frac{W}{C(S_t, A_t)} [G – Q(S_t, A_t)]$
$W \leftarrow W \frac{\pi(A_t|S_t)}{b(A_t|S_t)}$
如果 $W = 0$，则退出内循环