引言

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

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

价值迭代（Value iteration）

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

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

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

每次迭代包含两个步骤：

策略更新步骤（policy update step）：找到能解决以下优化问题的策略

\[\pi_{k+1} = \arg\max_\pi (r_\pi + \gamma P_\pi v_k)\]

价值更新步骤（value update step）：计算新的价值

\[v_{k+1} = r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_k\]

这两个步骤以矩阵-向量形式表示，但实际实现需要转换为元素形式。

Elementwise form

对于时间步 \(k\) 和状态 \(s\)：

策略更新的元素形式：

\[\pi_{k+1}(s) = \arg\max_\pi \sum_a \pi(a|s) \underbrace{\left( \sum_{r \in R} p(r|s, a)r + \gamma \sum_{s' \in S} p(s'|s, a)v_k(s') \right)}_{q_k(s,a)}， s\in S\]

最优策略为：

\[\begin{equation}\pi_{k+1}(a|s) = \begin{cases} 1, & a = a^*_k(s) \\ 0, & a \neq a^*_k(s) \end{cases}\tag{2}\end{equation}\]

其中 \(a^*_k(s) = \arg\max_a q_k(s,a)\)。由于新策略选择具有最大 \(q_k(s,a)\) 的动作，因此称为贪婪策略。

价值更新的元素形式：

\[ {v}_{k + 1}\left( s\right) = \mathop{\sum }\limits_{a}{\pi }_{k + 1}\left( {a |s}\right) \underset{{q}_{k}\left( {s,a}\right) }{\underbrace{\left( \mathop{\sum }\limits_{r}p\left( r \mid s,a\right) r + \gamma \mathop{\sum }\limits_{{s}^{\prime }}p\left( {s}^{\prime } \mid s,a\right) {v}_{k}\left( {s}^{\prime }\right) \right) }},\;s \in \mathcal{S}\]

将 (2) 带入可得，

\[v_{k+1}(s) = \max_a q_k(s,a)\]

整个流程可概括为：

\[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）：计算给定策略的状态价值，即求解贝尔曼方程

\[v_{\pi_k} = r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}\]

策略改进步骤（policy improvement step）：改进策略

\[\pi_{k+1} = \arg\max_\pi (r_\pi + \gamma P_\pi v_{\pi_k})\]

策略评估方法

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

闭式解：

\[v_{\pi_k} = (I - \gamma P_{\pi_k})^{-1} r_{\pi_k}\]

这种方法适合理论分析，但实际实现效率不高，因为需要计算矩阵逆。

迭代算法：

\[\begin{equation}v^{(j+1)}_{\pi_k} = r_{\pi_k} + \gamma P_{\pi_k} v^{(j)}_{\pi_k}, j = 0, 1, 2, ...\tag{3}\end{equation}\]

从任意初始猜测 \(v^{(0)}{\pi_k}\) 开始，当 \(j \to \infty\) 时，\(v^{(j)}{\pi_k} \to v_{\pi_k}\)。

有趣的是，策略迭代是一种迭代算法，其中在策略评估步骤中嵌入另一个迭代算法。

策略改进定理

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

引理（策略改进）：如果 \(\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}\) 是状态值，它们满足贝尔曼方程：

\[v_{\pi_{k+1}} = r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_{k+1}}\]

\[v_{\pi_k} = r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}\]

又 \(\pi_{k+1} = \arg\max_\pi (r_\pi + \gamma P_\pi v_{\pi_k})\)，我们知道：

\[r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_k} \geq r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}\]

这个不等式表明，新策略 \(\pi_{k+1}\) 在一步操作后（考虑当前状态值 \(v_{\pi_k}\)）能获得不低于原策略 \(\pi_k\) 的回报。

接下来，我们考察 \(v_{\pi_k} - v_{\pi_{k+1}}\)：

\[\begin{aligned} v_{\pi_k} - v_{\pi_{k+1}} &= (r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}) - (r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_{k+1}}) \\ &\leq (r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_k}) - (r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_{k+1}}) \\ &= \gamma P_{\pi_{k+1}} (v_{\pi_k} - v_{\pi_{k+1}}) \end{aligned}\]

第一个等式是将贝尔曼方程代入。第二个不等式是利用前面得到的 \(r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_k} \geq r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}\)。第三个等式是通过简单的代数运算得到。

从上面的不等式，我们可以递归地应用 \(P_{\pi_{k+1}}\)：

\[\begin{aligned} v_{\pi_k} - v_{\pi_{k+1}} &\leq \gamma P_{\pi_{k+1}} (v_{\pi_k} - v_{\pi_{k+1}}) \\ &\leq \gamma^2 P^2_{\pi_{k+1}} (v_{\pi_k} - v_{\pi_{k+1}}) \\ &\leq \ldots \\ &\leq \gamma^n P^n_{\pi_{k+1}} (v_{\pi_k} - v_{\pi_{k+1}}) \\ &\leq \lim_{n \to \infty} \gamma^n P^n_{\pi_{k+1}} (v_{\pi_k} - v_{\pi_{k+1}}) = 0 \end{aligned}\]

最后一步的极限等于零是因为：

当 \(n \to \infty\) 时，\(\gamma^n \to 0\)（因为折扣因子 \(\gamma < 1\)）
\(P^n_{\pi_{k+1}}\) 对于任意 \(n\) 都是非负随机矩阵

这里，随机矩阵指的是一个非负矩阵，其每一行的和都等于1。这保证了 \(P^n_{\pi_{k+1}} (v_{\pi_k} - v_{\pi_{k+1}})\) 是有界的。

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

算法收敛性

策略迭代算法生成两个序列：策略序列 \(\{\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^*\)。

对于 \(k = 0\)，我们总能找到一个 \(v_0\) 使得对于任意 \(\pi_0\) 都有 \(v_{\pi_0} \geq v_0\)。

我们通过归纳法证明对于所有 \(k\) 都有 \(v_k \leq v_{\pi_k} \leq v^*\)。

归纳假设：对于 \(k \geq 0\)，假设 \(v_{\pi_k} \geq v_k\)。

归纳步骤：对于 \(k + 1\)，我们有：

\[\begin{aligned} v_{\pi_{k+1}} - v_{k+1} &= (r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_{k+1}}) - \max_\pi (r_\pi + \gamma P_\pi v_k) \\ &\geq (r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_k}) - \max_\pi (r_\pi + \gamma P_\pi v_k) \end{aligned}\]

这里的不等式成立是因为根据策略改进定理，我们有 \(v_{\pi_{k+1}} \geq v_{\pi_k}\)，再加上 \(P_{\pi_{k+1}} \geq 0\)（状态转移概率矩阵是非负的），所以 \(\gamma P_{\pi_{k+1}} v_{\pi_{k+1}} \geq \gamma P_{\pi_{k+1}} v_{\pi_k}\)。

继续推导：

\[\begin{aligned} v_{\pi_{k+1}} - v_{k+1} &\geq (r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_k}) - (r_{\pi'k} + \gamma P{\pi'_k} v_k) \end{aligned}\]

这里，我们假设 \(\pi'k = \arg\max\pi (r_\pi + \gamma P_\pi v_k)\)，即价值迭代中选择的贪婪策略。

由于 \(\pi_{k+1} = \arg\max_\pi (r_\pi + \gamma P_\pi v_{\pi_k})\)，我们知道：

\[r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_k} \geq r_{\pi'k} + \gamma P_{\pi'k} v{\pi_k}\]

因此：

\[\begin{aligned} v_{\pi_{k+1}} - v_{k+1} &\geq (r_{\pi'k} + \gamma P_{\pi'k} v{\pi_k}) - (r_{\pi'_k} + \gamma P{\pi'k} v_k) \\ &= \gamma P{\pi'k} (v{\pi_k} - v_k) \end{aligned}\]

由归纳假设，我们知道 \(v_{\pi_k} - v_k \geq 0\)，再加上 \(P_{\pi'k}\) 是非负矩阵，因此 \(P{\pi'k} (v{\pi_k} - v_k) \geq 0\)，所以 \(v_{\pi_{k+1}} - v_{k+1} \geq 0\)，即 \(v_{\pi_{k+1}} \geq v_{k+1}\)。

通过归纳法，我们证明了对于任意 \(k \geq 0\)，都有 \(v_k \leq v_{\pi_k} \leq v^*\)。

由于价值迭代序列 \(\{v_k\}\) 收敛到 \(v^*\)，即 \(\lim_{k \to \infty} v_k = v^*\)，而我们已经证明 \(v_k \leq v_{\pi_k} \leq v^*\)，根据夹逼定理，\(v_{\pi_k}\) 也必然收敛到 \(v^\)，即：

\[\lim_{k \to \infty} v_{\pi_k} = v^*\]

这就证明了策略迭代算法生成的状态值序列收敛到最优状态值。由于最优状态值对应最优策略，所以策略序列也收敛到最优策略。

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

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

Elementwise form

策略评估步骤的元素形式：

\[v^{(j+1)}{\pi_k}(s) = \sum_a \pi_k(a|s) \left( \sum_r p(r|s,a)r + \gamma \sum{s'} p(s'|s,a) v^{(j)}_{\pi_k}(s') \right), s \in S\]

其中\(j=0,1,2...\)

策略改进步骤的元素形式：

\[\pi_{k+1}(s) = \arg\max_\pi \sum_a \pi(a|s) \underbrace{\left( \sum_r p(r|s,a)r + \gamma \sum_{s'} p(s'|s,a) v_{\pi_k}(s') \right)}_{q_{\pi_k}(s,a)}, s \in S\]

其中，\(q_{\pi_k}(s,a)\) 是在\(\pi_k\)策略下的action value，则最优贪婪策略为：

\[\pi_{k+1}(a|s) = \begin{cases} 1, & a = a^*_k(s) \\ 0, & a \neq a^*_k(s) \end{cases}\]

其中 \(a^*_k(s) = \arg\max_a q_{\pi_k}(s,a)\)。

对应算法伪代码如下：

实例说明

还是以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 性质：考虑策略评估步骤中的迭代算法：
\[v^{(j+1)}{\pi_k} = r{\pi_k} + \gamma P_{\pi_k} v^{(j)}_{\pi_k}, j = 0, 1, 2, ...\]

如果初始猜测选择为 \(v^{(0)}{\pi_k} = v_{\pi_{k-1}}\)，则对于 \(j = 0, 1, 2, ...\)，有：
\[v^{(j+1)}{\pi_k} \geq v^{(j)}{\pi_k}\]

这表明在策略评估过程中，价值估计会单调递增。

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

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

相比策略迭代，它在策略评估步骤中只需执行有限次迭代，计算效率更高
相比价值迭代，它通过在策略评估步骤中多运行几次迭代，可以加快整体收敛速度

三种算法的收敛速度关系可以直观表示为：

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

三种算法的比较与联系

共同特点

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

强化学习算法可以分为两类：

基于模型的强化学习：使用数据估计系统模型，并在学习过程中使用该模型
无模型强化学习：在学习过程中不涉及模型估计

算法特点比较

算法	价值更新方式	中间值性质	收敛速度	计算复杂度
价值迭代	一步更新	不是状态价值	较慢	较低
策略迭代	求解贝尔曼方程	是状态价值	较快	较高
截断策略迭代	有限步更新	不是状态价值	中等	中等

中间值的性质

价值迭代：中间值 \(v_k\) 不是状态价值，不满足任何策略的贝尔曼方程
策略迭代：中间值 \(v_{\pi_k}\) 是状态价值，满足当前策略的贝尔曼方程
截断策略迭代：中间值 \(v_k\) 不是状态价值，是真实状态价值的近似

策略评估步骤的迭代次数选择

在截断策略迭代算法中，策略评估步骤的迭代次数 \(j_{truncate}\) 是一个重要参数：

运行少量迭代可以加快整体收敛速度
运行过多迭代不会显著提高收敛速度，反而增加计算负担
一般建议运行少量迭代，但不要太多

Reference

3 - Chapter 4 Value Iteration and Policy Iteration.pdf

#

!

引言

价值迭代（Value iteration）

Elementwise form

策略迭代（Policy iteration）

策略评估方法

策略改进定理

算法收敛性

Elementwise form

实例说明

截断策略迭代算法

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

截断策略迭代

三种算法的比较与联系

共同特点

算法特点比较

中间值的性质

策略评估步骤的迭代次数选择

Reference