[RL Notes] 迭代策略评估

Author: nex3z 2019-10-19

  动态规划（Dynamic Programming，DP）是一类优化方法，它可以在给定用 MDP 描述的完备环境模型的情况下，使用贝尔曼方程进行策略评估和控制。

　　贝尔曼方程给出了 $v_\pi(s)$ 的一个递归表达式

$$\begin{align} v_\pi(s) = \sum_a \pi(a|s) \sum_{s’} \sum_{r} p(s’, r | s, a) \Big[ r + \gamma v_\pi(s’) \Big] \tag{1} \end{align}$$

通过将贝尔曼方程转换为更新的形式，就得到了 DP 算法

$$\begin{align} v_{k+1}(s) \leftarrow \sum_a \pi(a|s) \sum_{s’} \sum_{r} p(s’, r | s, a) \Big[ r + \gamma v_k(s’) \Big] \tag{2} \end{align}$$

使用式 $(2)$ 进行迭代更新，可以不断逼近价值函数。如果在某次更新后 $v_{k+1}(s)$ 在所有状态 $s$ 上都等于 $v_k(s’)$，则说明已经找到了价值函数 $v_\pi(s)$，因为 $v_\pi(s)$ 是贝尔曼方程的唯一解。

　　由式 $(2)$ 可见，在实现迭代策略评估算法时，需要同时保存旧的价值函数 $v_k$ 和新的价值函数 $v_{k+1}$。在一次迭代中，对于每一个状态，使用 $v_k$ 来更新 $v_{k+1}$，更新过程中 $v_k$ 需要保持不变；对所有状态更新完 $v_{k+1}$ 后，开始下一轮迭代。

　　除了上述使用两个数组的实现方式，也可以使用一个数组来就地更新，但此时在更新 $v_{k+1}$ 时，有时会使用旧的价值函数，有时会使用旧的价值函数。这种使用单数组就地更新的算法依然能够收敛到 $v_\pi$，而且可以在获得新数据后立即使用，收敛速度比两个数据的版本更快。

　　迭代策略评估的完整版本如下所示。

---

迭代策略评估算法，用于估计 $V \approx v_\pi$
输入待评估的策略 $\pi$
算法参数：小阈值 $\theta > 0$，用于确定估计量的精度
对于任意 $s \in \mathcal S^+$，任意初始化 $V(s)$，其中 $V(终止状态) = 0$
循环：
　　$\Delta \leftarrow 0$
　　对每一个 $s \in \mathcal S$，循环：
　　　　$v \leftarrow V(s)$
　　　　$V(s) \leftarrow \sum\limits_a \pi(a|s) \sum\limits_{s’,r} p(s’, r | s, a) \Big[r + \gamma V(s’) \Big]$
　　　　$\Delta \leftarrow \max(\Delta, |v – V(s)|)$
　　直到 $\Delta < \theta$

---