1 值迭代（Value iteration）

1.1 矩阵向量形式（Matrix-vector form）

值迭代算法可以拆分成两步，第一步是策略更新（就是更新各个动作的概率分布），第二步是值更新（就是把最优的策略代入值迭代公式），然后又跳转到第一步，重复这个过程：

第二步的值迭代公式，它并不是贝尔曼公式，贝尔曼公式需要等式两边都是 ${\upsilon }_k$ 或者 ${\upsilon }_{k+1}$，即需要下标一致。

1.2 逐元素形式（Elementwise form）

矩阵向量形式一般用于理论分析，真正计算还得是逐元素形式。

根据上一讲，第一步的求解为：

即对每一个 $s\in S$ 都计算一次，最后得到的 ${\pi }_{k+1}$ 被称为贪婪策略。

第二步为：

伪代码形式为：

1.3 例子

根据以下条件求出最优策略及贝尔曼最优公式：

我们设定初始解（可以取任意值，这里假设为0），然后进行第一次迭代：

这里我们用一个表格来表示每个状态下，各个动作的 action value，然后找到最大的 action value 对应的动作，该动作就是所在行（状态）的最优策略。对于有多个最大值的状态，那么可以从这几个中随机取一个，比如上面截图中 $s_1$ 有两个最大值，我们可以取 a3，也可以取 a5，这里假定取 a5。

下面是第一轮迭代得到的 “最优” 策略，这里 “最优” 要打引号：

获得最优策略后，代入值更新（value update）公式中，获得第一轮迭代的解。

随后是第二轮迭代：

第二轮迭代得到的 “最优” 策略为：

迭代的停止条件是相邻两次迭代得到的解的差（这是向量），模长小于某个预设的阈值。

2 策略迭代（Policy iteration）

2.1 矩阵向量形式

上面有两步，第一步是根据给定的策略，求解贝尔曼公式，得到 state value，即 ${\upsilon }_{{\pi }_k}$，第二步是策略优化（即策略更新）。算法的过程如下图所示：

2.2 常见问题与解答

第一个问题是PE的步骤，是如何求出 ${\upsilon }_{{\pi }_k}$ 的，这个可以试用第二讲介绍方式：

第二个问题是，PI阶段，为何 ${\pi }_{k+1}$ 比 ${\pi }_k$ 好，书上有对 ${\upsilon }_{{\pi }_{k+1}}\ge {\upsilon }_{{\pi }_k}$ 的证明，这里略过：

第三个问题，为何通过迭代得到最优策略，前面只是证明了 ${\upsilon }_{{\pi }_{k+1}}\ge {\upsilon }_{{\pi }_k}$，但你没有证明 ${\pi }_k$ 可以收敛，下面是一个定理，定理的相关证明要去书里看。

第四个问题，策略迭代与值迭代的关系，它们的关系会在后续的内容中介绍。

最后一个问题，策略迭代什么时候停止？这个我们会在后面介绍 Truncated policy iteration 提及。

2.3 逐元素形式（Elementwise form）

第一步是PE，即迭代求贝尔曼公式：

第二步是PI，即更新策略：

伪代码表示为：

2.4 例子

示例一：这个示例迭代一次就能得到最优。

示例二：

从上面的演变示意图可以看到，在 ${\pi }_1\to {\pi }_{10}$ 的过程中，越来越多的状态达到最优策略，并且是离 target 近的状态先变好，离 target 远的后变好。

3 截断的策略迭代（Truncated policy iteration）

3.1 比较策略迭代与值迭代

两种算法的示意图：

下标是将两种算法进行了对齐，为了方便比较，在值迭代时，让 ${\upsilon }_{{\pi }_0}$ 作为初始的 state value。

表格的第（4）步，策略迭代时，是在求解贝尔曼公式，而值迭代时，则是进行值更新，这里的区别是，求解要迭代N遍，而更新只计算一遍。

3.2 截断策略迭代

截断策略迭代，计算次数是介于值迭代与策略迭代之间：

当 $j=1$ 时，Truncated policy iteration 就是 Value iteration，当 $j$ 为无穷大时，则为 Policy iteration。因为 $j$ 不可能等于无穷大，我们不可能计算无穷多步，算法总归还是要停下来的，因此 Policy iteration 只在理论上存在。如果我们设置一个 Policy iteration 停下来的阈值，比如当 ${\upsilon }_{{\pi }_1}^{(j)}$ 和 ${\upsilon }_{{\pi }_1}^{(j+1)}$ 的差距小于阈值时停下来，或者设置迭代上限（比如100次），那么就变成了 Truncated policy iteration。

Truncated policy iteration 的伪代码如下：

因为进行了阶段，所以 ${\upsilon }_k={\upsilon }_k^{(j_{truncate})}$ 并不是贝尔曼方程的解，将 ${\upsilon }_k$ 直接代入 PI，是否会产生问题？是否会导致 $\pi$ 不再收敛？

上述疑问可以用下面的结论来解释，相关证明在书上。

简单来讲，你在 PE 的过程中，迭代的次数越多，得到的 state value 越大。只要得到的 state value 越大，那么策略更新（Policy Improve）就是有效的，而 state value 肯定能收敛，因此 $\pi$ 也肯定能收敛。

下图中，横轴表示迭代次数，纵轴表示 state value 的值（假设只有一个状态）：

上图中，蓝线和紫线都是收敛的，因此黑线也肯定收敛。因为策略迭代计算的次数比较多，因此“看起来”收敛比较快。

4 总结