引言

强化学习中，找到最优策略是核心目标。本文详细介绍三种能够找到最优策略的基础算法：价值迭代、策略迭代和截断策略迭代。这些算法属于动态规划范畴，需要系统模型，是后续无模型强化学习算法的重要基础。

在强化学习的发展路线中，这些算法处于"基础工具"到"算法/方法"的过渡阶段，是从"有模型"到"无模型"学习的重要桥梁。

价值迭代（Value iteration）

价值迭代算法基于收缩映射定理求解贝尔曼最优方程。其核心迭代公式为：

\[ \begin{equation}v_{k+1} = \max_{\pi \in \Pi} (r_\pi + \gamma P_\pi v_k), k = 0, 1, 2, ...\end{equation} \]

根据收缩映射定理，当 $k \to \infty$ 时，$v_k$ 和 $\pi_k$ 分别收敛到最优状态值和最优策略。

每次迭代包含两个步骤：

策略更新步骤（policy update step）：找到能解决以下优化问题的策略
价值更新步骤（value update step）：计算新的价值
这两个步骤以矩阵-向量形式表示，但实际实现需要转换为元素形式。

Elementwise form

对于时间步 $k$ 和状态 $s$：

策略更新的元素形式：
价值更新的元素形式：
整个流程可概括为：

\[ v_k(s) \rightarrow q_k(s,a) \rightarrow \text{新贪婪策略} \pi_{k+1}(s) \rightarrow \text{新价值} v_{k+1}(s) = \max_a q_k(s,a) \]

需要注意的是，价值迭代中的 $v_k$ 不是状态价值，它不满足任何策略的贝尔曼方程，只是算法生成的中间值，最终会收敛到最优状态价值。

对应的算法伪代码如下所示：

策略迭代（Policy iteration）

策略迭代不是直接求解贝尔曼最优方程，但与价值迭代有密切关系。策略迭代的思想在强化学习算法中被广泛应用。

具体算法中每次迭代包含两个步骤：

策略评估步骤（policy evaluation step）：计算给定策略的状态价值，即求解贝尔曼方程
策略改进步骤（policy improvement step）：改进策略

策略评估方法

策略评估步骤可以通过两种方法解决：

闭式解：
迭代算法：

策略改进定理

策略改进步骤能够改进给定策略，这由以下引理保证：

引理（策略改进）：如果 $\pi_{k+1} = \arg\max_\pi (r_\pi + \gamma P_\pi v_{\pi_k})$，则 $v_{\pi_{k+1}} \geq v_{\pi_k}$。
这里 $v_{\pi_{k+1}} \geq v_{\pi_k}$ 表示对所有 $s$ 都有 $v_{\pi_{k+1}}(s) \geq v_{\pi_k}(s)$。

🧾 首先，由于 $v_{\pi_{k+1}}$ 和 $v_{\pi_k}$ 是状态值，它们满足贝尔曼方程：

这个定理是策略迭代算法收敛性的关键基础，它保证了算法能够单调地改进策略，最终收敛到最优策略。

算法收敛性

策略迭代算法生成两个序列：策略序列 $\{\pi_0, \pi_1, ..., \pi_k, ...\}$ 和状态值序列 $\{v_{\pi_0}, v_{\pi_1}, ..., v_{\pi_k}, ...\}$。

由策略改进定理可知：

\[ v_{\pi_0} \leq v_{\pi_1} \leq v_{\pi_2} \leq \cdots \leq v_{\pi_k} \leq \cdots \leq v^* \]

根据单调收敛定理，当 $k \to \infty$ 时，$v_{\pi_k}$ 收敛到常数值 $v_\infty$，且 $v_\infty = v^*$。

定理（策略迭代收敛性）：策略迭代算法生成的状态值序列 $\{v_{\pi_k}\}_{k=0}^{\infty}$ 收敛到最优状态值 $v^*$。因此，策略序列 $\{\pi_k\}_{k=0}^{\infty}$ 收敛到最优策略。

🧾 为了证明 $\{v_{\pi_k}\}_{k=0}^{\infty}$ 的收敛性，我们引入另一个序列 $\{v_k\}_{k=0}^{\infty}$，该序列由价值迭代算法 (1)式迭代生成。我们已知，对于任意初始值 $v_0$，$v_k$ 都会收敛到 $v^*$。

通过上面的一系列定理和证明，我们可以得到这么几个结论

策略迭代的优越性：证明表明策略迭代算法在每一步都生成不低于价值迭代的状态值估计（$v_{\pi_k} \geq v_k$），这解释了为什么策略迭代通常比价值迭代收敛更快。
单调改进性质：策略迭代算法的状态值序列是单调递增的（$v_{\pi_{k+1}} \geq v_{\pi_k}$），这是由策略改进定理（引理 4.1）保证的。
上界存在性：最优状态值 $v^*$ 是任何策略的状态值的上界，确保了策略迭代序列是有界的。

Elementwise form

策略评估步骤的元素形式：
策略改进步骤的元素形式：
对应算法伪代码如下：

实例说明

还是以grid-world为例， The reward settings are$ r_{boundary} = −1, r_{forbidden} = −10$, and$ r_{target} = 1$. The discount rate is$ γ = 0.9$

通过简单示例可以看出，策略迭代算法能够从随机初始策略开始，逐步收敛到最优策略。在复杂环境中，可以观察到两个有趣现象：

靠近目标区域的状态比远离目标区域的状态更早找到最优策略
状态值的空间分布呈现规律：靠近目标的状态具有更高的状态值

截断策略迭代算法

价值迭代与策略迭代的比较

价值迭代和策略迭代的步骤可以对比如下：

策略迭代：

策略评估(PE)：给定 $\pi_k$，求解 $v_{\pi_k} = r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}$
策略改进(PI)：给定 $v_{\pi_k}$，求解 $\pi_{k+1} = \arg\max_\pi (r_\pi + \gamma P_\pi v_{\pi_k})$
价值迭代：
策略更新(PU)：给定 $v_k$，求解 $\pi_{k+1} = \arg\max_\pi (r_\pi + \gamma P_\pi v_k)$
价值更新(VU)：给定 $\pi_{k+1}$，求解 $v_{k+1} = r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_k$
两种算法的流程可以表示为：

策略迭代：$\pi_0 \xrightarrow{PE} v_{\pi_0} \xrightarrow{PI} \pi_1 \xrightarrow{PE} v_{\pi_1} \xrightarrow{PI} \pi_2 \xrightarrow{PE} v_{\pi_2} \xrightarrow{PI} \ldots$
价值迭代： $v_0 \xrightarrow{PU} \pi'_1 \xrightarrow{VU} v_1 \xrightarrow{PU} \pi'_2 \xrightarrow{VU} v_2 \xrightarrow{PU} \ldots$

如上表所示，如果让两种算法的初始状态价值相同，即， $v_0=v_{\pi_0}$, 那么两种算法的区别主要在于价值计算步骤（步骤4）：价值迭代只进行一步计算，而策略迭代需要求解贝尔曼方程（理论上需要无限次迭代）。

如果详细展开策略迭代中求解 $v_{\pi_1} = r_{\pi_1} + \gamma P_{\pi_1} v_{\pi_1}$ 的迭代过程，设 $v^{(0)}_{\pi_1} = v_0$，则：

$$
\begin{aligned}
v^{(0)}{\pi_1} &= v_0 \
v^{(1)}{\pi_1} &= r_{\pi_1} + \gamma P_{\pi_1} v^{(0)}{\pi_1} \quad \leftarrow \text{价值迭代的} v_1 \
v^{(2)}{\pi_1} &= r_{\pi_1} + \gamma P_{\pi_1} v^{(1)}{\pi_1} \
&\vdots \
v^{(j)}{\pi_1} &= r_{\pi_1} + \gamma P_{\pi_1} v^{(j-1)}{\pi_1} \quad \leftarrow \text{截断策略迭代的} \bar{v}1 \
&\vdots \
v^{(\infty)}{\pi_1} &= r{\pi_1} + \gamma P{\pi_1} v^{(\infty)}{\pi_1} \quad \leftarrow \text{策略迭代的} v_{\pi_1}
\end{aligned}

从上述过程可以得出以下观察：

如果只运行一次迭代，$v^{(1)}_{\pi_1}$ 就是价值迭代算法中计算的 $v_1$
如果运行无限次迭代，$v^{(\infty)}{\pi_1}$ 就是策略迭代算法中计算的 $v_{\pi_1}$
如果运行有限次迭代（记为 $j_{truncate}$），这种算法就称为截断策略迭代

截断策略迭代

截断策略迭代算法是策略迭代的一种变体，在策略评估步骤中只执行有限次迭代，而不是求解精确的状态值。

价值迭代和策略迭代可以看作是截断策略迭代的两个极端情况：

价值迭代相当于 $j_{truncate} = 1$ 的截断策略迭代
策略迭代相当于 $j_{truncate} = \infty$ 的截断策略迭代[19]

截断策略的Value improvement 性质：考虑策略评估步骤中的迭代算法：

截断策略的算法伪代码如下所示，相比策略迭代算法，只是修改了价值评估过程中的迭代次数

截断策略迭代的优势明显：

相比策略迭代，它在策略评估步骤中只需执行有限次迭代，计算效率更高
相比价值迭代，它通过在策略评估步骤中多运行几次迭代，可以加快整体收敛速度
三种算法的收敛速度关系可以直观表示为：

策略迭代 > 截断策略迭代 > 价值迭代

三种算法的比较与联系

共同特点

三种算法的共同特点是每次迭代都有两个步骤：一个更新价值，一个更新策略。这种价值与策略更新之间的交互思想被称为广义策略迭代（Generalized Policy Iteration），在强化学习算法中广泛存在。
三种算法都需要系统模型（状态转移概率和奖励函数），因此它们通常被称为动态规划算法，而不是强化学习算法

算法特点比较

中间值的性质

价值迭代：中间值 $v_k$ 不是状态价值，不满足任何策略的贝尔曼方程
策略迭代：中间值 $v_{\pi_k}$ 是状态价值，满足当前策略的贝尔曼方程