枕石的个人博客
文章 标签 分类 关于
枕石的个人博客

Contents

强化学习的数学原理（四）：值迭代和策略迭代

 included in 强化学习
   2615 words   6 minutes 

在基于模型的强化学习（特别是使用动态规划求解马尔可夫决策过程）中，价值迭代（Value Iteration）和策略迭代（Policy Iteration）是两大基石算法。它们从不同角度出发，最终都旨在找到最优策略 $\pi_*$。本文将深入剖析这两种算法的运作机制，并引出统一两者的泛化算法——截断策略迭代（Truncated Policy Iteration）。

1. 价值迭代算法 (Value Iteration Algorithm)

价值迭代的核心思想是直接通过迭代计算贝尔曼最优方程来逼近最优价值函数 $v^*$。它相信，一旦我们获得了最优价值函数，最优策略自然就水到渠成了。

其更新公式为： $$\vec{v}_{k+1} = f(\vec{v}_k) = \max_{\pi} (\vec{r}_{\pi} + \gamma P_{\pi}\vec{v}_k)$$

算法步骤

  • 给定任意初始值$\vec{v}_0$

  1. 策略更新 (Policy Update) 在第 k 次迭代中，我们基于当前的值 $v_k$ 进行一次“隐式”的策略改进，即为每个状态选择能够最大化期望回报的动作。 $$\pi_{k+1} = \arg\max_{\pi} (\vec{r}_{\pi} + \gamma P_{\pi} \vec{v}_k)$$

  2. 价值更新 (Value Update) 使用上一步中找到的“最优”动作（策略）来更新价值函数，得到 $v_{k+1}$。 $$\vec{v}_{k+1} = \vec{r}_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} \vec{v}_k$$

Note: 这里的$\vec{v}$不是state value，因为并不满足贝尔曼公式

核心: 实际上，这两个步骤被合并在一个贝尔曼最优方程的更新操作中，不断迭代直至价值函数收敛。

Procedure Summary

价值迭代的每一次迭代可以看作是一个“压缩”了的“评估-改进”过程：

$u_0 \rightarrow \pi_1 \rightarrow u_1 \rightarrow \pi_2 \rightarrow \cdots $

即从值 $u_k$ 出发，计算所有动作的Q值，然后通过贪心选择（max 操作）直接得到新的价值 $u_{k+1}$。

Pseudocode

Pseudocode: Value iteration algorithm

Initialization: The probability model $p(r|s, a)$ and $p(s’|s, a)$ for all $(s, a)$ are known. Initial guess $v_0$.

Aim: Search the optimal state value and an optimal policy solving the Bellman optimality equation.

While $v_k$ has not converged in the sense that $||v_k - v_{k-1}||$ is greater than a predefined small threshold, for the $k$th iteration, do

  • For every state $s \in S$, do
    • For every action $a \in A(s)$, do
      • q-value: $q_k(s, a) = \sum_r p(r|s, a)r + \gamma \sum_{s’} p(s’|s, a)v_k(s’)$
    • Maximum action value: $a_k^*(s)=\text{argmax}_a q_k(a,s)$
    • Policy update: $\pi_{k+1}(a|s)=1$ if $a=a^*_k$, and $\pi_{k+1}(a|s)=0$ otherwise
    • Value update: $v_{k+1}(s) = \max_a q_k(s, a)$

2. 策略迭代算法 (Policy Iteration Algorithm)

策略迭代则采用更为“稳健”的迭代思路。它明确地将策略评估和策略改进两个环节分开，通过完整的“评估-改进”大循环来逐步提升策略，直至最优。

算法步骤

  • 随机生成初始策略$\pi_0$

  1. 策略评估 (Policy Evaluation, PE) 给定当前策略 $\pi_k$，精确计算出该策略下的状态价值函数 $v_{\pi_k}$。这需要求解贝尔曼期望方程： $$v_{\pi_k} = r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}$$ 这个求解过程本身就是一个迭代计算，直至 $v_{\pi_k}$ 收敛。

  2. 策略改进 (Policy Improvement, PI) 基于上一步得到的精确价值函数 $v_{\pi_k}$，通过贪心选择来寻找一个更优的新策略 $\pi_{k+1}$。 $$\pi_{k+1} = \arg\max_{\pi} (r_{\pi} + \gamma P_{\pi} v_{\pi_k})$$ 如果新策略 $\pi_{k+1}$ 与旧策略 $\pi_k$ 相同，则说明算法已收敛，找到了最优策略。

Procedure Summary

策略迭代的流程是一个清晰的“评估-改进”双循环： $$\pi_0 \xrightarrow{\text{评估(PE)}} v_{\pi_0} \xrightarrow{\text{改进(PI)}} \pi_1 \xrightarrow{\text{评估(PE)}} v_{\pi_1} \xrightarrow{\text{改进(PI)}} \pi_2 \rightarrow \cdots \rightarrow \pi_*$$

Pseudocode

Pseudocode: Policy iteration algorithm

Initialization: The probability model $p(r|s, a)$ and $p(s’|s, a)$ for all $(s, a)$ are known. Initial guess $\pi_0$.

Aim: Search for the optimal state value and an optimal policy.

While the policy has not converged, for the $k$th iteration, do

  • Policy evaluation:
    • Initialization: an arbitrary initial guess $v_{\pi_k}^{(0)}$
    • While $v_{\pi_k}^{(j)}$ has not converged, for the $j$th iteration, do
      • For every state $s \in S$, do $$ v_{\pi_k}^{(j+1)}(s) = \sum_a \pi_k(a|s) \left[ \sum_r p(r|s, a)r + \gamma \sum_{s’} p(s’|s, a)v_{\pi_k}^{(j)}(s’) \right] $$
  • Policy improvement:
    • For every state $s \in S$, do
      • For every action $a \in A(s)$, do $$ q_{\pi_k}(s, a) = \sum_r p(r|s, a)r + \gamma \sum_{s’} p(s’|s, a)v_{\pi_k}(s’) $$
      • $a_k^*(s) = \arg\max_a q_{\pi_k}(s, a)$
      • $\pi_{k+1}(a|s) = 1$ if $a = a_k^*$, and $\pi_{k+1}(a|s) = 0$ otherwise

Questions

Q1: 在策略评估中，如何求解贝尔曼方程？

  • 解析解: $V_{\pi_k} = (I - \gamma P_{\pi_k})^{-1} R_{\pi_k}$。理论上可行，但由于求逆矩阵的计算复杂度高 ($O(n^3)$)，实践中很少使用。
  • 迭代解: $v_{\pi_k}^{(j+1)} = r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}^{(j)}$。通过多次迭代直至收敛，这是最常用的方法。

Q2: 为什么新策略 $\pi_{k+1}$ 比旧策略 $\pi_k$ 更好？

这由策略改进定理保证。该定理证明，通过对当前价值函数采取贪心策略所得到的新策略，其价值函数在所有状态上都将不劣于原策略的价值函数，即 $v_{\pi_{k+1}}(s) \ge v_{\pi_k}(s)$ 对所有 $s \in S$ 成立。

Q3: 算法的收敛性如何？

由于策略改进定理保证了价值函数的单调非递减性 ($v_{\pi_0} \le v_{\pi_1} \le \cdots \le v_*$)，且在一个有限状态的MDP中，策略的数量是有限的，因此策略迭代保证在有限次“评估-改进”循环后收敛到最优策略。

3. 截断策略迭代算法 (Truncated Policy Iteration Algorithm)

价值迭代和策略迭代看似不同，但实际上是同一个思想谱系的两端。为了清晰地看到这一点，我们先对它们进行比较。

对比 Value Iteration 与 Policy Iteration

对比项Policy Iteration AlgorithmValue Iteration AlgorithmComments
步骤 1 (策略)$\pi_0$ (初始策略)N/A
步骤 2 (价值)$v_{\pi_0} = r_{\pi_0} + \gamma P_{\pi_0} v_{\pi_0}$ (完整评估)$v_0 := v_{\pi_0}$ (初始价值)
步骤 3 (策略)$\pi_1 = \text{argmax}_{\pi}(r_{\pi} + \gamma P_{\pi} v_{\pi_0})$$\pi_1 = \text{argmax}_{\pi}(r_{\pi} + \gamma P_{\pi} v_0)$The two policies are the same
步骤 4 (价值)$v_{\pi_1} = r_{\pi_1} + \gamma P_{\pi_1} v_{\pi_1}$ (完整评估)$v_1 = r_{\pi_1} + \gamma P_{\pi_1} v_0$ (单步更新)$v_{\pi_1} \ge v_1$
步骤 5 (策略)$\pi_2 = \text{argmax}_{\pi}(r_{\pi} + \gamma P_{\pi} v_{\pi_1})$$\pi_2^’ = \text{argmax}_{\pi}(r_{\pi} + \gamma P_{\pi} v_1)$
区别策略评估需要迭代至收敛，成本高策略评估仅迭代一次，成本低

从对比中可以看出，最大的区别在于策略评估的深度。策略迭代要求评估到“底”（完全收敛），而价值迭代则可以看作是评估“一步”就马上进行改进。

从迭代过程看三者关系

截断策略迭代 (Truncated Policy Iteration) 正是为了弥合这两者之间的鸿沟而被提出的。它允许我们控制策略评估的迭代次数。

让我们来看求解贝尔曼期望方程 $v_{\pi_1} = r_{\pi_1} + \gamma P_{\pi_1} v_{\pi_1}$ 的过程，设初始值为 $v_{\pi_1}^{(0)} = v_0$：

  • Value Iteration (评估一步): $$v_{\pi_1}^{(1)} \leftarrow r_{\pi_1} + \gamma P_{\pi_1} v_{\pi_1}^{(0)}$$ 它计算一次就停止，并进入下一轮大循环。

  • Truncated Policy Iteration (评估 j 步): $$\bar{v}_{\pi_1} \leftarrow v_{\pi_1}^{(j)}, \text{其中 } v_{\pi_1}^{(j)} = r_{\pi_1} + \gamma P_{\pi_1} v_{\pi_1}^{(j-1)}$$ 它计算一个固定的 $j$ 次后停止，并进行策略改进。

  • Policy Iteration (评估到底): $$v_{\pi_1} \leftarrow v_{\pi_1}^{(\infty)}, \text{其中 } v_{\pi_1}^{(\infty)} = r_{\pi_1} + \gamma P_{\pi_1} v_{\pi_1}^{(\infty)}$$ 它一直计算到内部的价值函数完全收敛。

因此，截断策略迭代是前两者的一般化形式。

Pseudocode

Pseudocode: Truncated policy iteration algorithm

Initialization: The probability model $p(r|s, a)$ and $p(s’|s, a)$ for all $(s, a)$ are known. Initial guess $\pi_0$.

Aim: Search for the optimal state value and an optimal policy.

While the policy has not converged, for the $k$th iteration, do

  • Policy evaluation:
    • Initialization: select the initial guess as $v_k^{(0)} = v_{k-1}$. The maximum iteration is set to be $j_{\text{truncate}}$.
    • While $j < j_{\text{truncate}}$, do
      • For every state $s \in S$, do $$ v_k^{(j+1)}(s) = \sum_a \pi_k(a|s) \left[ \sum_r p(r|s, a)r + \gamma \sum_{s’} p(s’|s, a)v_k^{(j)}(s’) \right] $$
    • Set $v_k = v_k^{(j_{\text{truncate}})}$
  • Policy improvement:
    • For every state $s \in S$, do
      • For every action $a \in A(s)$, do $$ q_k(s, a) = \sum_r p(r|s, a)r + \gamma \sum_{s’} p(s’|s, a)v_k(s’) $$
      • $a_k^*(s) = \arg\max_a q_k(s, a)$
      • $\pi_{k+1}(a|s) = 1$ if $a = a_k^*$, and $\pi_{k+1}(a|s) = 0$ otherwise

4. 总结

本文系统性地梳理了强化学习中三种核心的动态规划算法。

  • 价值迭代 (Value Iteration): 算法简单，每次迭代计算成本低。它通过不断对贝尔曼最优方程进行迭代来逼近最优价值函数，可以看作是“最不耐心”的算法，评估一步就改进。

  • 策略迭代 (Policy Iteration): 算法收敛所需的“大循环”次数少，但每次迭代成本高，因为它需要完整地进行策略评估直至收敛。它是“最耐心”的算法，必须评估到完全准确再改进。

  • 截断策略迭代 (Truncated Policy Iteration): 它是前两者的一般化框架。通过调整策略评估的迭代次数，可以在计算成本和收敛速度之间做出灵活的权衡。当评估次数为1时，它就是价值迭代；当评估次数为无穷大时，它就是策略迭代。

理解这三种算法的内在逻辑和相互关系，是掌握现代强化学习理论与实践的坚实基础。

/images/强化学习的数学原理/policy_and_value_iteration.png

图片来源：bilibili-【强化学习的数学原理】课程：从零开始到透彻理解

Updated on 2025-09-18
 强化学习
Back | Home