[RL Notes] 广义策略迭代
1. 广义策略迭代
策略迭代包含策略评估和策略改进两个不断交替进行、相互作用的步骤，一种方法是在一个步骤完成后才开始下一个步骤，但这并不是必须的。各种组织策略评估和策略改进相互作用的一般方法统称为广义策略迭代。
2. 价值迭代
一次策略评估本身就是一个迭代的过程，如使用前文中的迭代策略评估算法，这是一个非常耗时的计算，有多种方式可以提前截断策略迭代中的策略评估步骤，而不影响策略迭代的收敛。一种方法是在遍历完所有状态一次后立即停止策略评估，即对每个状态进行一次更新，这种方法称为价值迭代（value iteration）。
使用价值迭代时，策略改进与策略评估可以整合进一个简单的更新公式
\begin{align}
v_{k+1}(s) &\doteq \max_{a} \mathbb{E}[R_{t+1} + \gamma v_k(S_{t+1}) | S_t = s, A_t = a] \\
&= \max_{a} \sum_{s’, r} p(s’,r|s,a)\big[r + \gamma v_k(s’)\big] \tag{1}
\end{align}
可以证明，对于任意 $v_0$，如果 $v_*$ 存在，则序列 $\{v_k\}$ 可以收敛到 $v_*$。
价值迭代算法的完整版本如下所示。
价值迭代算法，用于估计 $\pi \approx \pi_*$
算法参数：小阈值 $\theta $，用于确定估计量的精度
循环：
$\Delta \leftarrow 0$
对每一个 $s \in \mathcal{S}$ 循环：
$v \leftarrow V(s)$
$V(s) \leftarrow \max_{a} \sum\limits_{s’, r} p(s’,r|s,a)\big[r + \gamma V(s’)\big]$
$\Delta \leftarrow \max (\Delta, |v – V(s)|)$
直到 $\Delta < \theta$
输出一个确定的 $\pi \approx \pi_*$，使得
$\pi(s) = \underset{a}{\arg\max} \sum\limits_{s’, r} p(s’,r|s,a)\big[r + \gamma V(s’)\big]$
注意上面的算法在更新 $V(s)$ 时并没有依赖任何特定的策略 $\pi$，因此该算法称为价值迭代。
这种价值迭代算法在每次迭代中需要遍历所有状态，称这样需要系统地进行遍历的算法为同步（synchronous）的，上面所示的价值迭代算法称为同步动态规划算法。
3. 异步动态规划
如果状态空间很大，每次迭代都遍历所有状态会消耗大量时间。相对地，异步（asynchronous）动态规划算法不会系统地遍历整个状态集，而是使用任意可用的状态值，以任意顺序更新状态值。状态更新是就地进行的，某些状态的值在更新一次之前，另一些状态的值可能已经更新了好几次。为了确保收敛，异步算法必须要不断的更新所有状态的值，不能只局限于更新某几个特定的状态。异步算法可以更迅速和灵活地传播价值信息，例如当一个状态的价值发生改变时，优先更新其附近的状态。