策略评估#

对于任意一个策略$\pi$，计算其状态价值函数$v_\pi$的过程在DP中被称为策略评估。我们已知计算状态价值函数的贝尔曼方程：

如果环境的动态特性完全已知，那么上式是一个拥有$|\mathcal S|$个未知数以及$|\mathcal S|$个等式的线性方程组。该计算方程较为繁琐，可以使用迭代法来解决。记策略$\pi$在第$k$轮迭代得到的状态价值函数为$v_k$，其中初始近似值$v_0$可以任意选取（除了终止状态价值必须为$0$），则使用$v_\pi$的贝尔曼方程的更新公式为：

这种根据新一轮的单步即时收益和上一轮所有的后继状态价值函数二者的期望来更新新一轮$s$的价值函数的方法为期望更新，因为它基于所有可能后继状态的期望值。

用程序实现迭代策略评估有两种方式。一种是使用两个数组，一个存储旧的价值函数$v_k(s)$，另一个存储新的价值函数$v_{k+1}(s)$；另一种只使用一个数组就地更新。直接用新的价值函数替换旧的价值函数。就地更新方法根据状态更新的顺序可以将新的价值函数立刻用于当前轮的更新，该算法依然能收敛到$v_\pi$，且比双数组收敛得更快。

完整的就地更新策略评估算法的伪代码如下：

1. 输入：待评估的策略$\pi$
2. 参数：小阈值$\theta>0$
3. 对于任意$s\in\mathcal S^+$，任意初始化$V(s)$，其中$V(终止状态)=0$
4. 循环：
   1. $\Delta\leftarrow0$
   2. 对每一个$s\in\mathcal S$：
      1. $v\leftarrow V(s)$
      2. $V(s)\leftarrow\displaystyle\sum_a\pi(a|s)\sum_{s',r}p(s',r|s,a)[r+\gamma V(s')]$
      3. $\Delta\leftarrow\max(\Delta,|v-V(s)|)$
5. 直到$\Delta<\theta$

由于迭代策略评估只能在极限意义下收敛，因此该算法使用小阈值$\theta$判断程序何时终止。随着更新接近收敛，每一轮更新带来的改变量也将趋于无穷小，当所有状态的价值函数改变量的最大值小于一个小阈值时，可以考虑结束更新。

策略改进#

计算一个给定策略下的价值函数是为了寻找更好的策略。假设对于任一确定的策略$\pi$，我们已知其策略函数$v_\pi$。如果想知道在某个状态$s$，选择一个不同于给定策略的动作$a\neq\pi(s)$是否会更好，一种解决方法是在状态$s$选择动作$a$之后继续遵循现有的策略$\pi$，则相应的动作价值为$q_\pi(s,a)$。如果$q_\pi(s,a)>v_\pi(s)$，则可以认定该新策略总体来说更好。

以上是针对某个状态的特例，一般来说，如果$\pi'$和$\pi$是任意两个确定的策略，对任意的$s\in\mathcal S$有$q_\pi(s,\pi'(s))\geqslant v_\pi(s)$，则我们称策略$\pi'$相比于$\pi$一样好或更好，此时对任意的$s\in\mathcal S$也必然有$v_{\pi'}(s)\geqslant v_\pi(s)$

在上一章针对贝尔曼最优方程的反证法的讨论中，我们知道对于一个策略$\pi$，基于其动作价值函数$q_\pi(s,a)$的贪心策略$\pi'$必然是一个不劣于$\pi$的策略，其满足：

如果$\pi'$和$\pi$一样好，即$v_\pi=v_{\pi'}$，那么上式将与贝尔曼最优方程等效，即$\pi'$和$\pi$都是最优策略。

另外，如果同一状态下存在多个最优动作，则新的贪心策略只需保证每个最优动作都有概率被选中，而选中非最优动作的概率为$0$即可。

策略迭代#

根据策略评估和策略改进，一旦一个策略$\pi$根据$v_\pi$产生了更好的策略$\pi'$，我们就可以通过计算$v_{\pi'}$得到一个更优的策略$\pi''$。该练市方法可以得到如下不断改进的策略和价值函数的序列：

其中$\overset{\mathrm{E}}\rightarrow$代表策略评估，$\overset{\mathrm{I}}\rightarrow$代表策略改进。由于有限MDP必然只有有限种策略，所以该方法一定能在有限次迭代后收敛到一个最优策略和最优价值函数。这种寻找最优策略的方法称为策略迭代，其算法伪代码如下：

1. 初始化
   1. $\forall s\in\mathcal S$，任意设定$V(s)\in\mathbb R$和$\pi(s)\in\mathcal A(s)$
2. 策略评估
   1. 循环：
      1. $\Delta\leftarrow0$
      2. 对每一个$s\in\mathcal S$：
         1. $v\leftarrow V(s)$
         2. $V(s)\leftarrow\displaystyle\sum_a\pi(a|s)\sum_{s',r}p(s',r|s,a)[r+\gamma V(s')]$
         3. $\Delta\leftarrow\max(\Delta,|v-V(s)|)$
      3. 直到$\Delta<\theta$（一个决定估计精度的小正数）
3. 策略改进
   1. $\textit{policy-stable}\leftarrow\textit{true}$
   2. 对每一个$s\in\mathcal S$：
      1. $\textit{old-action}\leftarrow\pi(s)$
      2. $\pi(s)\leftarrow\underset a{\mathrm{argmax}}\displaystyle\sum_{s',r}p(s',r|s,a)[r+\gamma V(s')]$
      3. 如果$\textit{old-action}\neq\pi(s)$，那么$\textit{policy-stable}\leftarrow\textit{false}$
   3. 如果$\textit{policy-stable}$为$\textit{true}$，那么停止并返回$V\approx v_*$以及$\pi\approx\pi_*$，否则跳转到策略评估

其中$\textit{policy-stable}$根据新旧策略在每一个状态选择的动作是否都一样判断算法是否（近似）收敛。

价值迭代#

策略迭代算法的一个缺点是每一次迭代都要进行策略评估，而策略评估本身也是一个迭代过程，且其收敛理论上在极限处才成立，效率较低。

有多种方式可以截断策略迭代中的策略评估步骤，并且不影响策略迭代的收敛。其中一种方式在策略评估中只对每个状态进行一次更新，被称为价值迭代。将此表示为结合了策略改进和截断策略评估的更新公式如下，对任意$s\in\mathcal S$：

该方法直接假定策略是贪心的，每轮对每个状态的所有动作遍历一次后即刻选取最优动作价值作为新的状态价值函数。从另一种角度看，这相当于使用贝尔曼最优方程作为更新规则，舍弃在过程中追求具体的策略，直接迭代求解最优价值函数再导出最优策略，根据其压缩映射性质可以证明它必然收敛到该方程唯一的不动点$v_*$。

价值迭代和策略评估一样，理论上需要迭代无限次才能收敛到$v_*$，可以设置一个小阈值使其终止，以下为其算法伪代码：

1. 参数：小阈值$\theta>0$
2. 对于任意$s\in\mathcal S^+$，任意初始化$V(s)$，其中$V(终止状态)=0$
3. 循环：
   1. $\Delta\leftarrow0$
   2. 对每一个$s\in\mathcal{S}$循环：
      1. $v\leftarrow V(s)$
      2. $V(s)\leftarrow\displaystyle\underset a\max\sum_{s',r}p(s',r|s,a)[r+\gamma V(s')]$
      3. $\Delta\leftarrow\max(\Delta,|v-V(s)|)$
4. 直到$\Delta<\theta$
5. 输出一个确定的$\pi\approx\pi_*$，使得$\pi(s)=\displaystyle\underset a{\mathrm{argmax}}\sum_{s',r}p(s',r|s,a)[r+\gamma V(s)]$

异步动态规划#

上述DP方法的一个主要缺点是它们需要对MDP的整个状态集进行遍历。如果状态集很大，即使是单次遍历也很昂贵。

异步DP算法是一类就地迭代的DP算法，其不以系统遍历状态集的形式组织算法，而是使用任意可用的状态值以任意顺序更新状态值。在某些状态值第一次更新之前，另一些状态值可能已经更新了好几次。但为了正确收敛，异步算法必须不断更新直至某个没有遗漏任何一个状态的计算节点。

异步算法具有很大的灵活性。我们可以尝试通过选择一些特定状态来更新可以加快算法的速度、调整更新顺序以使价值信息能更有效地在状态间传播、将更新的重点放在和最优行为更相关的一些状态上等等。

异步算法还使得计算和实时交互的结合更加容易，它可以随着智能体实际在MDP中交互的经历更新，并立刻将更新值应用于智能体下一时刻的决策，这使得将DP算法的更新聚焦到部分与智能体最相关的状态集成为可能。

广义策略迭代#

策略迭代包括策略评估和策略改进两个同时进行、相互作用的流程，但作用的顺序、粒度都不是一成不变的。只要两个流程持续更新所有状态，那么最后的结果通常能收敛到最优价值函数和一个最优策略。我们用广义策略迭代（GPI）指代让策略评估和策略改进相互作用的一般思路，而与其他细节无关。几乎所有的强化学习方法都可以被描述为GPI，即包含明确定义的策略和价值函数。

可以将GPI的评估和改进流程视为两个约束之间相互作用、竞争合作的流程。让策略对价值函数贪心通常会使价值函数与新的策略不匹配，而使价值函数与策略一致通常会使策略不再对新的价值函数贪心。但从长远来看，这两个流程会相互作用以找到一个联合解决方案：最优价值函数和一个最优策略。