4.值迭代和策略迭代

简介

值迭代和策略迭代都是求解 BOE 的具体迭代算法。二者理论上都能收敛到 $v^*$ 和 $\pi^*$ ，但是侧重点不同，计算开销、收敛速度不同。

前情提要#

在 3.贝尔曼最优公式中已经涉及了迭代求解 $v^*$ 的算法，这个算法准确来讲有两个步骤：

Policy Update：求解 Greedy Optimal Policy

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

Value Update：迭代 pseudo state value

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

初始时 $v_0$ 随机取值，交替循环上述两步，可以迭代出 $v^*$ 和 $\pi^*$ .

在任何中间步骤， $v_k$ 都不能严格称为 state value，因为其不一定满足 Bellman Equation $v_k = r_{\pi_k} + \gamma P_{\pi_k} v_k$ . 在本笔记中，称 $v_k$ 为 pseudo state value.

这个算法就叫做「值迭代」（value iteration）。

此外，我们还会介绍策略迭代（policy iteration）和截断策略迭代（truncated policy iteration）。

值迭代#

分别推导值迭代的两步：Policy Update 和 Value Update.

说明

使用 Matrix-Vector Form 便于理论分析，使用 Element-wise Form 便于代码实现。

下面主要使用后者进行分析。

Policy Update#

正如 Solution 中所说，策略是 state-wise separable 的，因此可以 element-wise 地考虑。

\pi_{k+1}(s) = \arg \max_\pi \sum_a \pi(a \mid s) \left(\sum_r p(r \mid s,a)r + \gamma \sum_{s'}p(s' \mid s,a)v_k(s')\right),\ s \in \mathcal{S}

设出“action value”： $q_k(a,s) = \sum_r p(r \mid s,a)r + \gamma \sum_{s'}p(s' \mid s,a)v_k(s')$ ，这部分是确定的，因此 $\pi_{k+1}(s)$ 直接 greedy 地以 $1$ 的概率取使 $q(a,s)$ 最大的 $a$ ，即：

\pi_{k+1}(a \mid s) = \begin{cases} 1, & a = \arg \max_{\mathscr{a}} q_k(s,\mathscr{a}),\\ 0, & \text{otherwise}. \end{cases}

Value Update#

化为 Element-wise form.

v_{k+1}(s)=\sum_{a} \pi_{k+1}(a \mid s) \underbrace{\left(\sum_{r} p(r \mid s, a) r+\gamma \sum_{s^{\prime}} p\left(s^{\prime} \mid s, a\right) v_{k}\left(s^{\prime}\right)\right)}_{q_{k}(s, a)}, \quad s \in \mathcal{S}

算法#

收敛条件设置为 $\lVert v_{k+1} - v_k\rVert \le \varepsilon$ ，其中 $\varepsilon$ 是一个预定义的容差。

每一次迭代中，对所有的 $(s,a)$ 对，计算出“action value” $q(s,a)$ .

对于 deterministic 的奖励以及状态转移， $q(s,a)$ 的计算是 $O(1)$ 的。

策略迭代#

策略迭代和值迭代最大的不同，就是它的 $v_k$ 是准的、是真正对应于当前 policy 的 state value.

策略迭代就是循环进行 Policy Evaluation 和 Policy Improvement，直到收敛。

Policy Evaluation#

求解 Bellman Equation：

v_k = r_{\pi_k} + \gamma \boldsymbol{P}_{\pi_k}v_k

虽然该方程有闭式解，但正如求解贝尔曼公式中所说的，我们一般使用迭代法：

v_{k}^{(i+1)} = r_{\pi_k} + \gamma \boldsymbol{P}_{\pi_k} v_k^{(i)}

这样得到的 $v_k^{(n)}$ 几乎就是策略 $\pi_k$ 真正的 state value $v_k$ .

Policy Improvement#

对于 $\pi_k$ 的 state value $v_k$ ，尝试用 BOE 的迭代思路来改进策略：

\pi_{k+1} = \arg \max_\pi r_{\pi_k} + \gamma \boldsymbol{P}_{\pi_k} v_k

证明

\pi_{k+1}

优于

\pi_k

这就是要证明， $v_{k+1} \ge v_k$ .

而 $v_{k+1}$ 和 $v_k$ 分别满足这两个 Bellman Equation：

\begin{align*} v_{k+1} &= r_{\pi_{k+1}} + \gamma \boldsymbol{P}_{\pi_{k+1}} v_{k+1}\\ v_{k} &= r_{\pi_{k}} + \gamma \boldsymbol{P}_{\pi_{k}} v_{k}

\end{align*}

$又由 $\pi_{k+1} = \arg \max_\pi r_{\pi_k} + \gamma \boldsymbol{P}_{\pi_k} v_k$，可得$
r_{\pi_{k+1}} + \gamma \boldsymbol{P}{\pi{k+1}} v_k \ge r_{\pi_k} + \gamma \boldsymbol{P}_{\pi_k} v_k
$于是$

\begin{aligned} v_{\pi_{k}}-v_{\pi_{k+1}} & =\left(r_{\pi_{k}}+\gamma P_{\pi_{k}} v_{\pi_{k}}\right)-\left(r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}} v_{\pi_{k+1}}\right) \ & \leq\left(r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}} v_{\pi_{k}}\right)-\left(r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}} v_{\pi_{k+1}}\right) \ & \leq \gamma P_{\pi_{k+1}}\left(v_{\pi_{k}}-v_{\pi_{k+1}}\right) . \end{aligned}

$由 [Proof of Optimality](/blog/courses/math-behind-reinforcement-learning/2026-09-30-3-bellman-optimality-equation/#proof-of-optimality) 中的相同方法，可以证明 $v_{\pi_k} \le v_{\pi_{k+1}}$.$

证明

v_{\pi_k}

收敛于

v^*

由于 $\forall k\in \mathbb{N}^+$ ， $v_{\pi_k} \le v_{\pi_{k+1}}$ 且 $v_{\pi_k} \le v^*$ ，因此 $\{v_k\}$ 为单调有界数列，设其收敛于 $v_{\pi_\infty}$ ，则只需证明 $v_{\pi_\infty} = v^*$ .

为此，构造辅助数列 $\mathscr{v}_{k+1} = \max_\pi (r_\pi + \gamma\boldsymbol{P}_\pi\mathscr{v}_k) \triangleq f(\mathscr{v}_k)$ . 这个数列就是 Value Iteration 所产生的数列。

对于 $v_{\pi_0}$ ，可构造 $\mathscr{v}_0$ 满足 $\mathscr{v}_0 \le v_{\pi_0}$ . 下面使用数学归纳法：假设 $\mathscr{v}_{k} \le v_{\pi_k}$ ，有

\begin{align*} v_{\pi_{k+1}} - \mathscr{v}_{k+1} &= (r_{\pi_{k+1}} + \gamma \boldsymbol{P}_{\pi_{k+1}} v_{\pi_{k+1}}) - \max_\pi (r_\pi + \gamma\boldsymbol{P}_\pi\mathscr{v}_k) \\ &\ge (r_{\pi_{k+1}} + \gamma \boldsymbol{P}_{\pi_{k+1}}v_{\pi_k}) - \max_\pi (r_\pi + \gamma\boldsymbol{P}_\pi\mathscr{v}_k) && \left(v_{\pi_{k+1}} \ge v_{\pi_k},\ \boldsymbol{P}_{\pi_{k+1}} \ge 0\right) \\ &= (r_{\pi_{k+1}} + \gamma \boldsymbol{P}_{\pi_{k+1}}v_{\pi_k}) - (r_{\pi^*} + \gamma\boldsymbol{P}_{\pi^*}\mathscr{v}_k) && \left(\Leftarrow \pi^* = \arg\max_\pi(r_\pi + \gamma\boldsymbol{P}_\pi\mathscr{v}_k)\right) \\ &\ge (r_{\pi^*} + \gamma \boldsymbol{P}_{\pi^*} v_{\pi_k}) - (r_{\pi^*} + \gamma\boldsymbol{P}_{\pi^*}\mathscr{v}_k) && \left(\Leftarrow \pi_{k+1} = \arg\max_\pi(r_\pi + \gamma\boldsymbol{P}_\pi v_{\pi_k})\right) \\ & = \gamma \boldsymbol{P}_{\pi^*}(v_{\pi_k} - \mathscr{v}_k)\\ &\ge 0 \end{align*}

这就证明了 $\mathscr{v}_k \le v_{\pi_k} \le v^*,\ \forall k \in \mathbb{N}^+$ . 结合 $\mathscr{v}_k$ 收敛于 $v^*$ （Proof of Optimality），可知 $v_{\pi_k}$ 也收敛于 $v^*$ ，且收敛速度不慢于 $\mathscr{v}_k$ .

上述证明说明了，策略迭代也可以收敛到最佳策略，且收敛速率快于值迭代。

对比值迭代和策略迭代

值迭代先始于一个随机“pseudo state value” $v_0$ ，然后直接用迭代法求解 BOE.

策略迭代始于一个随机策略 $\pi_0$ ，然后每次计算准确的 state value $v_{\pi_k}$ ，并且基于它优化策略。

二者都有一个 $\arg \max_\pi (r_\pi + \gamma \boldsymbol{P}_\pi v_k)$ 的部分。

可以理解为：值迭代进行一轮 pseudo state value 的计算之后，立刻据此更新策略；而策略迭代每轮会进行多次 pseudo state value 计算，直到收敛到真正的 state value，再据此更新策略。

截断策略迭代#

在值迭代和策略迭代中，都涉及从给定 $\pi$ 计算 $v$ 的步骤。区别在于，值迭代只从上一步的 $v_k$ 计算一次 $v_{k+1} = r_\pi + \gamma \boldsymbol{P}_\pi v_k$ ；而策略迭代会一直迭代 $v_{\pi_{k+1}}^{(i+1)} = r_\pi + \gamma \boldsymbol{P}_\pi v_{\pi_{k+1}}^{(i)}$ 直到收敛到 $v_{\pi_{k+1}} = v_{\pi_{k+1}}^{(\infty)}$ .

而截断策略迭代就是二者的折中。它每次计算 $v_{k+1}$ 时，会迭代多次，但是不要求必须收敛。

反过来，也可以说值迭代和策略迭代都是截断策略迭代的特殊情况。

\begin{array}{l} \text { Consider the step of solving } v_{\pi_{1}}=r_{\pi_{1}}+\gamma P_{\pi_{1}} v_{\pi_{1}} \text { : }\\ \begin{aligned} v_{\pi_{1}}^{(0)} & =v_{0} \\ \text { value iteration } \leftarrow v_{1} \longleftarrow v_{\pi_{1}}^{(1)} & =r_{\pi_{1}}+\gamma P_{\pi_{1}} v_{\pi_{1}}^{(0)} \\ v_{\pi_{1}}^{(2)} & =r_{\pi_{1}}+\gamma P_{\pi_{1}} v_{\pi_{1}}^{(1)} \\ \vdots & \\ \text { truncated policy iteration } \leftarrow \bar{v}_{1} \longleftarrow v_{\pi_{1}}^{(j)} & =r_{\pi_{1}}+\gamma P_{\pi_{1}} v_{\pi_{1}}^{(j-1)} \\ \vdots & \\ \text { policy iteration } \leftarrow v_{\pi_{1}} \longleftarrow v_{\pi_{1}}^{(\infty)} & =r_{\pi_{1}}+\gamma P_{\pi_{1}} v_{\pi_{1}}^{(\infty)} \end{aligned} \end{array}

然而，一个问题是，截断策略迭代的最优性怎么由理论保证？虽然值迭代和策略迭代都会收敛，但这并不自动导出截断策略迭代就能收敛。

收敛性证明

考虑迭代求解 $v_{\pi_{k}}=r_{\pi_{k}}+\gamma P_{\pi_{k}} v_{\pi_{k }}$ 的过程：

v_{\pi_{k}}^{(i+1)} = r_\pi + \gamma \boldsymbol{P}_\pi v_{\pi_{k}}^{(i)}

下面可以证明，如果初值设置为 $v_{\pi_k}^{(0)} = v_{\pi_{k-1}}$ ，则 $v_{\pi_k}^{(i+1)} \ge v_{\pi_k}^{(i)},\ \forall i$ ：

由于 $v_{\pi_{k}}^{(j)}=r_{\pi_{k}}+\gamma P_{\pi_{k}} v_{\pi_{k}}^{(j-1)}$ 且 $v_{\pi_{k}}^{(j+1)}=r_{\pi_{k}}+\gamma P_{\pi_{k}} v_{\pi_{k}}^{(j)}$ ，有

v_{\pi_{k}}^{(j+1)}-v_{\pi_{k}}^{(j)}=\gamma P_{\pi_{k}}\left(v_{\pi_{k}}^{(j)}-v_{\pi_{k}}^{(j-1)}\right)=\cdots=\gamma^{j} P_{\pi_{k}}^{j}\left(v_{\pi_{k}}^{(1)}-v_{\pi_{k}}^{(0)}\right) \tag{$*$}

而 $v_{\pi_{k}}^{(0)}=v_{\pi_{k-1}}$ ，这就是说，

v_{\pi_{k}}^{(1)}=r_{\pi_{k}}+\gamma P_{\pi_{k}} v_{\pi_{k}}^{(0)}=r_{\pi_{k}}+\gamma P_{\pi_{k}} v_{\pi_{k-1}} \geq r_{\pi_{k-1}}+\gamma P_{\pi_{k-1}} v_{\pi_{k-1}}=v_{\pi_{k-1}}=v_{\pi_{k}}^{(0)}

代入 $v_{\pi_{k}}^{(1)} \ge v_{\pi_{k}}^{(0)}$ 到 $(*)$ 中，可得 $v_{\pi_{k}}^{(j+1)} \ge v_{\pi_{k}}^{(j)}$ .

前情提要#

值迭代#

Policy Update#

Value Update#

算法#

策略迭代#

Policy Evaluation#

Policy Improvement#

截断策略迭代#

三种方法对比#