动态规划方法

策略迭代包含两个交替进行的步骤：

策略评估的迭代公式

对每个状态 $s$，反复应用贝尔曼期望备份：

从任意初始值 $V_0$ 开始，每次迭代都将估值向真实价值推进一步。

策略改进

评估出 $V_\pi$ 后，对每个状态选使期望价值最大的动作：

为什么迭代能收敛？

收敛性的数学基础是巴拿赫压缩映射定理：

• 贝尔曼算子 $T_\pi$ 是一个 $\gamma$-压缩映射：$\|T_\pi V - T_\pi V'\|_\infty \leq \gamma \|V - V'\|_\infty$
• 每次迭代，估计值与真实值之间的最大误差乘以 $\gamma$（严格变小）
• 在完备度量空间中，压缩映射必然有唯一不动点
• 因此 $V_0, V_1, V_2, \ldots$ 以指数级速度收敛到 $V_\pi$

环境设定：4×4 网格，16 个状态（标号 0-15），状态 0 和 15 为终止状态。

初始策略：均匀随机策略，$\pi(a|s) = 0.25$（每个方向等概率）。

第一轮策略评估（$k=0 \to k=1$）

初始 $V_0(s) = 0$ 对所有 $s$。现在计算 $V_1$。

以状态 1（第 1 行第 2 列）为例：

• 上 → 状态 0（终止），$V(0) = 0$，奖励 $= -1$
• 右 → 状态 2，$V(2) = 0$，奖励 $= -1$
• 下 → 状态 5，$V(5) = 0$，奖励 $= -1$
• 左 → 状态 0（终止，因为撞到边界后绕到终止态）……不对，左是状态 0 吗？让我重新核实。

实际上，网格布局如下（标号）：0 在左上角，15 在右下角。

对状态 1：

• 上 → 状态 0（终止），$V_0(0) = 0$，得到 $-1 + 1 \times 0 = -1$
• 右 → 状态 2，$V_0(2) = 0$，得到 $-1 + 0 = -1$
• 下 → 状态 5，$V_0(5) = 0$，得到 $-1 + 0 = -1$
• 左 → 状态 0（左出界了吗？不，状态 1 向左到状态 0），得到 $-1 + 0 = -1$

类似地，所有非终止状态的 $V_1 = -1.0$。

第二轮策略评估（$k=1 \to k=2$）

以状态 1 为例：

• 上 → 状态 0（终止），$V(0) = 0$，得 $-1 + 0 = -1$
• 右 → 状态 2，$V_1(2) = -1$，得 $-1 + (-1) = -2$
• 下 → 状态 5，$V_1(5) = -1$，得 $-1 + (-1) = -2$
• 左 → 状态 0（终止），$V(0) = 0$，得 $-1 + 0 = -1$

边界状态（靠近终止态的）会更快收敛到更高的值，因为它们有更多机会走到终止态。

继续迭代直到收敛（约 50-100 步后 $\Delta$ 很小），然后进行策略改进：对每个状态，选使价值最大的动作。

策略改进结果

经过几轮"评估→改进"循环后，策略会稳定在最优策略上。例如，状态 1 的最优动作是"上"（直接走向终止态 0），状态 14 的最优动作是"右"（走向终止态 15）。

策略迭代需要"评估到完全收敛再改进"，效率不高。价值迭代的核心洞察：不需要等策略评估完全收敛，每一步同时完成评估和改进。

核心公式：贝尔曼最优方程

注意与策略评估的区别：这里直接用 $\max$ 选最优动作，而不是按 $\pi$ 的概率加权。因此每一步迭代都在同时做评估和改进。

算法步骤

1. 初始化 $V_0(s) = 0$（对所有 $s$）
2. 对每个状态 $s$，用贝尔曼最优方程计算 $V_{k+1}(s)$
3. 当 $\max_s |V_{k+1}(s) - V_k(s)| \lt \theta$ 时停止
4. 提取最优策略：$\pi^*(s) = \arg\max_a \sum_{s'} P(s'|s,a)[r + \gamma V^*(s')]$

环境：3 个状态的小型 MDP。

参数：$\gamma = 0.9$。

价值迭代过程

初始化：$V_0(s_A) = 0$，$V_0(s_B) = 0$，$V_0(s_C) = 0$

迭代 $k=1$：

迭代 $k=2$：

注意：$s_B$ 的最优动作从 $a_1$ 变成了 $a_2$！因为在 $k=2$ 时，回到 $s_A$（$V=6.5$）比直接去 $s_C$（$V=0$）更划算。

迭代 $k=3$：

完整收敛表格：