[RL Notes] 加权重要度采样及增量实现

Author: nex3z 2019-10-26

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$，则退出内循环

---