1. 引言
强化学习问题通常可以形式化为一个马尔可夫决策过程（Markov Decision Process, MDP）。一个标准的MDP包含以下几个核心要素：环境（Environment）、状态（State）、奖励（Reward）、策略（Policy）和价值（Value）。
策略（Policy）是指从状态到动作的映射。我们的目标是找到一个最优策略，使得在每个状态下所能获得的未来奖励总和最大化。
✅ 动态规划算法要求我们对环境的MDP模型完全已知。这意味着我们可以使用“一步前瞻”（one-step look-ahead）来计算每个动作的预期回报。
本文将重点介绍两种经典的动态规划算法：
- 策略迭代（Policy Iteration）
- 值迭代（Value Iteration）
我们将分别介绍它们的工作原理，并对比它们的优缺点。
2. 策略迭代（Policy Iteration）
2.1 核心思想
策略迭代从一个任意策略（arbitrary policy）开始，然后通过策略评估（Policy Evaluation）和策略改进（Policy Improvement）两个步骤交替进行，直到策略收敛。
流程如下：
π₀ → V(π₀) → π₁ → V(π₁) → π₂ → ... → π* → V*
其中：
π₀是初始策略V(π)是该策略对应的状态价值函数π*是最终收敛的最优策略
2.2 策略评估
在策略评估阶段，我们根据当前策略 π(s) 计算其对应的状态价值函数 V(s)：
$$ V(s) = \sum_{s',r} p(s', r | s, \pi(s)) [r + \gamma V(s')] $$
其中：
p(s', r | s, a)是状态转移概率γ是折扣因子（discount factor）
2.3 策略改进
在策略改进阶段，我们使用一步前瞻来更新策略：
$$ \pi'(s) = \arg\max_{a} \sum_{s',r} p(s', r | s, a) [r + \gamma V(s')] $$
即：在当前状态下选择一个动作，使得期望的回报最大。
2.4 收敛条件
当连续两次迭代的策略不再变化时，即认为策略已经收敛。
2.5 优点
- 每次迭代都保证策略优于前一次
- 收敛速度快，迭代次数少
2.6 缺点
- 每次迭代需要完整的策略评估，计算量较大
- 算法结构相对复杂
3. 值迭代（Value Iteration）
3.1 核心思想
值迭代不显式维护策略，而是直接迭代更新状态价值函数，最终通过价值函数反推出最优策略。
流程如下：
V₀ → V₁ → V₂ → ... → V*
其中：
V₀是初始价值函数V*是最优价值函数
3.2 更新公式
每一步我们通过一步前瞻更新状态价值函数：
$$ V(s) = \max_{a} \sum_{s',r} p(s', r | s, a) [r + \gamma V(s')] $$
这个公式和策略迭代中的策略改进步骤非常相似，区别在于这里直接取最大值，而不是先评估再改进。
3.3 收敛条件
当状态价值函数的变化小于某个阈值时，算法收敛。
3.4 优点
- 算法结构简单，易于实现
- 每次迭代只需要一次更新操作
3.5 缺点
- 需要更多迭代次数才能收敛
- 每次都要对所有动作进行最大值计算，计算量较大
4. 策略迭代 vs 值迭代
| 特性 | 策略迭代（Policy Iteration） | 值迭代（Value Iteration） |
|---|---|---|
| 起始点 | 随机策略 | 随机价值函数 |
| 算法复杂度 | 较高 | 较低 |
| 收敛性 | ✅ 保证收敛 | ✅ 保证收敛 |
| 迭代次数 | 较少 | 较多 |
| 单次迭代计算量 | 较小 | 较大 |
| 收敛速度 | 快 | 慢 |
4.1 工作方式对比
- 策略迭代：先评估当前策略，然后改进策略。
- 值迭代：直接更新状态价值函数，最终通过价值函数提取最优策略。
4.2 实现细节
两者都基于 Bellman 方程，但实现方式略有不同：
- 策略迭代：两阶段更新（评估 + 改进）
- 值迭代：单阶段更新，同时完成策略改进
4.3 总结对比
- 策略迭代收敛更快，但每次迭代更复杂
- 值迭代结构简单，但可能需要更多轮次
5. 总结
本文介绍了两种用于求解马尔可夫决策过程（MDP）的动态规划算法：
- 策略迭代：通过评估和改进策略逐步逼近最优策略
- 值迭代：直接更新状态价值函数，最终反推最优策略
两种方法都基于 Bellman 方程和一步前瞻机制，且都保证收敛到最优策略。
✅ 在实践中，策略迭代通常收敛更快，而值迭代更容易实现。选择哪种算法取决于具体问题的规模和对性能的要求。
通过理解这两种算法，我们可以更好地掌握强化学习中动态规划的核心思想，为后续学习 Q-learning、深度强化学习等打下基础。