[RL Notes] 迭代策略评估
动态规划（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$