上一章的末尾我们提到了value iteration。这一章我们介绍value iteration和policy iteration——这二者都是截断策略迭代（Truncated policy iteration）的两个极端情况。

值迭代

值迭代分两步：

·1.policy update（PU）。

这一步求解当给出时的，即 $。$ 这里的叫做greedy policy，因为它仅仅是在选择最大的q值。

·2.value update（VU）。

这一步求解,即。总的求解流程如下：

以上都是向量形式，为了给出具体算法，我们要将向量形式改写成元素形式（前者更适合理论分析）。伪代码如下。

策略迭代

不同于值迭代，策略迭代是先给出个初始策略.策略迭代也分两步：

·1.policy evaluation（PE）。

这一步是计算贝尔曼方程的v。计算的方法是迭代方法，我们之前已经谈过了。

·2.policy improvement（PI）

根据step1算出的v，我们就可以得出每个状态的各个q值，进而更新greedy policy。

策略迭代的流程为：其伪代码为：

截断策略迭代

我们刚才讲的两个iteration是很相似的：这实际是truncate policy iteration的两个极端情况。我们以下图为例：

考虑求解。对于值迭代呢，我们就直接求出了v；但是对于策略迭代，我们需要无穷次的内部迭代才能求出v。而截断策略迭代就是指，我们能否在这无穷次的内部迭代中找到一个位置，来截断这一迭代过程。（不过实际上就算使用策略迭代也不可能无穷次迭代，一般会迭代到两次迭代误差小于一个阈值。）下面是伪代码，可以看到区别只是在于引入了截断阈值：