摘要

本系列知识点讲解基于蘑菇书EasyRL中的内容进行详细的疑难点分析！具体内容请阅读蘑菇书EasyRL！

---

对应蘑菇书EasyRL——2.3.10 马尔可夫决策过程控制

---

策略迭代（Policy Iteration）与价值迭代（Value Iteration）详解

策略迭代和价值迭代是解决马尔可夫决策过程（MDP）控制问题的两种经典动态规划方法。它们的目标是找到最优策略 ${\pi }^{\ast }$，使得智能体在环境中获得最大累积奖励。以下从基础概念到具体算法逐步推导，并结合实例说明。

---

1. 马尔可夫决策过程（MDP）回顾

MDP 包含以下要素：

• 状态集合 $\mathcal{S}$：所有可能的状态（如机器人位置）。
• 动作集合 $\mathcal{A}$：所有可能的动作（如移动方向）。
• 转移概率 $P(s^{\prime }\mid s,a)$：在状态 $s$ 执行动作 $a$ 后转移到状态 $s^{\prime }$ 的概率。
• 奖励函数 $R(s,a,s^{\prime })$：执行动作 $a$ 后从状态 $s$ 转移到 $s^{\prime }$ 的即时奖励。
• 折扣因子 $\gamma \in [0,1)$：平衡当前奖励与未来奖励的重要性。

---

2. 策略迭代（Policy Iteration）

策略迭代通过交替执行 策略评估（Policy Evaluation） 和 策略改进（Policy Improvement） 来逐步逼近最优策略。

(1) 策略评估（Policy Evaluation）

目标：计算当前策略 $\pi$ 的状态值函数 $V^{\pi }(s)$。
方法：利用贝尔曼期望方程迭代更新值函数，直到收敛。

贝尔曼期望方程：
$$V_{k+1}(s)=\sum _a\pi (a\mid s)\sum _{s^{\prime }}P(s^{\prime }\mid s,a)\left[R(s,a,s^{\prime })+\gamma V_k(s^{\prime })\right]$$

算法步骤：

1. 初始化所有状态的值函数 $V_0(s)=0$。
2. 对于 $k=0,1,2,\dots$，依次更新每个状态的值：
   $$V_{k+1}(s)=\sum _a\pi (a\mid s)\sum _{s^{\prime }}P(s^{\prime }\mid s,a)\left[R(s,a,s^{\prime })+\gamma V_k(s^{\prime })\right]$$
3. 当 ${\max }_s|V_{k+1}(s)-V_k(s)|<ϵ$（预设阈值）时停止迭代。

---

(2) 策略改进（Policy Improvement）

目标：基于当前值函数 $V^{\pi }$，更新策略 $\pi$ 使其更优。
方法：对每个状态选择能够最大化预期收益的动作（贪婪策略）。

策略更新规则：
$${\pi }^{\prime }(s)=\arg \underset{a}{\max }\sum _{s^{\prime }}P(s^{\prime }\mid s,a)\left[R(s,a,s^{\prime })+\gamma V^{\pi }(s^{\prime })\right]$$

算法步骤：

1. 对每个状态 $s$，计算所有动作的预期收益：
   $$Q^{\pi }(s,a)=\sum _{s^{\prime }}P(s^{\prime }\mid s,a)\left[R(s,a,s^{\prime })+\gamma V^{\pi }(s^{\prime })\right]$$
2. 选择使 $Q^{\pi }(s,a)$ 最大的动作作为新策略：
   $${\pi }^{\prime }(s)=\arg \underset{a}{\max }{Q}^{\pi }(s,a)$$

---

(3) 策略迭代完整流程

1. 初始化：随机选择一个初始策略 ${\pi }_0$。
2. 循环直到策略收敛：
   • 策略评估：计算当前策略 ${\pi }_k$ 的值函数 $V^{{\pi }_k}$。
   • 策略改进：根据 $V^{{\pi }_k}$ 生成新策略 ${\pi }_{k+1}$。
   • 如果 ${\pi }_{k+1}={\pi }_k$，停止迭代。

---

示例：网格世界（Grid World）

环境设定：

• 3x3 网格，中心为起点 $S_4$，右上角为终点 $G$（奖励 +10），其他移动每步奖励 -1。

• 动作：上、下、左、右（撞墙则留在原地）。

• 策略 ${\pi }_0$：随机选择动作（各方向概率 25%）。

• 折扣因子 $\gamma =0.9$。

  s6 | s7 | s8（终点，奖励+10）
  s3 | s4 | s5
  s0 | s1 | s2
  

第一次策略评估：

• 计算 $V^{{\pi }_0}(S_0)$：
  $$V^{{\pi }_0}(S_0)=0.25\left[(-1+0.9\times 0)+(-1+0.9\times 0)+(-1+0.9\times 0)+(-1+0.9\times 0)\right]=-1$$
• 同理计算其他状态的值函数（初始均为 -1）。

第一次策略改进：

• 对 $S_4$，计算各动作的 $Q$ 值：
  • 向右：移动到 $S_5$，$Q(S_4,\text{右})=-1+0.9\times (-1)=-1.9$
  • 其他动作同理。
• 由于所有动作 $Q$ 值相同，策略保持不变。

后续迭代：

• 经过多次策略评估和改进后，策略逐渐收敛到最优策略：始终向右或向上移动以最快到达终点。

---

3. 价值迭代（Value Iteration）

价值迭代直接通过迭代更新值函数逼近最优值函数 $V^{\ast }$，最后从中提取最优策略。

(1) 贝尔曼最优方程

价值迭代的核心是贝尔曼最优方程：
$$V_{k+1}(s)=\underset{a}{\max }\sum _{s^{\prime }}P(s^{\prime }\mid s,a)\left[R(s,a,s^{\prime })+\gamma V_k(s^{\prime })\right]$$

(2) 算法步骤

1. 初始化：所有状态的值函数 $V_0(s)=0$。
2. 循环直到值函数收敛：
   $$V_{k+1}(s)=\underset{a}{\max }\sum _{s^{\prime }}P(s^{\prime }\mid s,a)\left[R(s,a,s^{\prime })+\gamma V_k(s^{\prime })\right]$$
3. 提取最优策略：
   $${\pi }^{\ast }(s)=\arg \underset{a}{\max }\sum _{s^{\prime }}P(s^{\prime }\mid s,a)\left[R(s,a,s^{\prime })+\gamma V^{\ast }(s^{\prime })\right]$$

---

示例：网格世界（同策略迭代）

第一次迭代：

• 计算 $V_1(S_0)$：
  V 1 ( S 0 ) = max ⁡ { 向上 : − 1 + 0.9 × 0 , 向下 : − 1 + 0.9 × 0 , 左 : − 1 + 0.9 × 0 , 右 : − 1 + 0.9 × 0 } = − 1 V_1(S_0) = \max \left\{ \text{向上}: -1 + 0.9 \times 0, \text{向下}: -1 + 0.9 \times 0, \text{左}: -1 + 0.9 \times 0, \text{右}: -1 + 0.9 \times 0 \right\} = -1 V1​(S0​)=max{向上:−1+0.9×0,向下:−1+0.9×0,左:−1+0.9×0,右:−1+0.9×0}=−1

第二次迭代：

• 计算 $V_2(S_0)$：
  V 2 ( S 0 ) = max ⁡ { 右 : − 1 + 0.9 × ( − 1 ) = − 1.9 , 其他动作同理 } = − 1.9 V_2(S_0) = \max \left\{ \text{右}: -1 + 0.9 \times (-1) = -1.9, \text{其他动作同理} \right\} = -1.9 V2​(S0​)=max{右:−1+0.9×(−1)=−1.9,其他动作同理}=−1.9
  V 2 ( S 0 ) = max ⁡ { 上 : − 1 + 0.9 × ( − 1 ) = − 1.9 , 其他动作同理 } = − 1.9 V_2(S_0) = \max \left\{ \text{上}: -1 + 0.9 \times (-1) = -1.9, \text{其他动作同理} \right\} = -1.9 V2​(S0​)=max{上:−1+0.9×(−1)=−1.9,其他动作同理}=−1.9

后续迭代：

• $\dots$

提取最优策略：

• 对每个状态选择最大化 $Q^{\ast }(s,a)$ 的动作，例如在 $S_0$ 选择向右或向上移动。

---

4. 策略迭代 vs 价值迭代

特征	策略迭代	价值迭代
核心步骤	策略评估 + 策略改进交替进行	直接迭代更新最优值函数
收敛速度	策略通常快速收敛，但每次评估计算量大	值函数收敛较慢，但单次迭代更快
中间策略	显式维护策略并逐步改进	无显式策略，仅在最后提取
适用场景	策略空间较小或需要显式策略分析	状态空间较大或无需中间策略
数学基础	贝尔曼期望方程	贝尔曼最优方程

---

5. 总结

• 策略迭代：通过交替的策略评估和改进，逐步优化策略。适合需要显式分析策略的场景。
• 价值迭代：直接逼近最优值函数，最后提取策略。适合状态空间较大或无需中间策略的场景。
• 共同点：均基于动态规划，依赖完整的环境模型（已知 ( P ) 和 ( R )）。

通过网格世界示例可直观理解两者的计算流程：策略迭代通过显式策略更新寻找最优路径，而价值迭代通过值函数迭代隐式达成目标。