价值迭代 vs 策略迭代

价值迭代 (VI, Value Iteration) 直接迭代 Bellman 最优方程做全状态同步更新:$V_{k+1}(s) = \max_a \sum_{s'} P(s'|s,a)\left[ r(s,a) + \gamma V_k(s') \right]$, 其中 $V_k$ 是第 $k$ 轮估计, $\max_a$ 隐式做贪婪改进, $\sum_{s'} P(s'|s,a)[\cdot]$ 是转移加权期望;每次迭代 = 一步策略评估 + 一步改进, 等价于"截断到一步"的策略迭代。因 Bellman 算子是 $\gamma$-压缩映射 ($\|TV - TU\|_\infty \le \gamma \|V - U\|_\infty$), $V_k \to V^*$ 保证收敛;注意中间 $V_k$ 可能不对应任何单一策略的值函数,收敛后才取贪婪策略。策略迭代 (PI, Policy Iteration) 分两步交替: ① 策略评估——迭代求解当前策略的值函数 $V^{\pi_k}(s) = \sum_{s'} P(s'|s, \pi_k(s))\left[ r(s, \pi_k(s)) + \gamma V^{\pi_k}(s') \right]$ 直到收敛 (或按容忍度截断);② 策略改进——对新值函数做贪婪更新 $\pi_{k+1}(s) = \arg\max_a \sum_{s'} P(s'|s,a)\left[ r(s,a) + \gamma V^{\pi_k}(s') \right]$。改进定理保证 $V^{\pi_{k+1}} \ge V^{\pi_k}$ 单调提升, 因此有限 MDP 上 PI 必然终止于最优策略 (理论上至多 $|A|^{|S|}$ 轮, 实践远少于此)。

已知模型 $P, R$ 的表格型小规模 MDP (规划问题)——如经典格点世界、机器人导航;也是面试区分动态规划两大流派的标准考题 (与 DQN 等无模型方法对比)。

朴素策略搜索空间是指数级 $|A|^{|S|}$, 不可行;PI 用"评估-改进"交替把搜索转为多项式级迭代,通常几十轮内收敛、每轮更贵但总轮数少;VI 每轮便宜 ($O(|S|^2|A|)$) 但轮数更多——两者都是 Bellman 不动点迭代的不同切分方式。

手推并写出价值迭代的更新公式,逐项解释符号?为什么 VI 能收敛到 V*?

策略迭代的两步是什么?策略改进定理为什么保证单调提升?

VI 与 PI 的复杂度与收敛速度对比?为什么 PI 轮数少但每轮贵?

VI 迭代中的 Vk 是否一定是某个策略的值函数?最终策略如何取?

给定一个小格点 MDP,手动跑 1-2 轮 VI/PI 演示更新过程?