机器人入行指南
原理层/动态规划:两种迭代的账

原理层 T20 / 27 · 决策与优化

动态规划:两种迭代的账

值迭代每步便宜但要很多步,策略迭代每步贵但轮数少。策略改进定理保证每轮严格不降——它们谁快,在具体问题上是可算的账。

最优子结构最优路径的子路径也最优贝尔曼方程把子结构写成递归值迭代压缩映射保证收敛策略提取argmax 一步贪心DP 的代价是「全知全能」:要转移矩阵和奖励函数都已知——model-based 的出发点
约 50 分钟2 定理7 步证明4 题自测

一句话结论

策略改进定理(每轮新策略不劣于旧策略)+ 策略评估的精确求解(解线性方程组)= 策略迭代。它是「广义策略迭代」框架的精确版,actor-critic 是它的随机逼近版。

深度 RL 的很多设计决策是这两个经典算法的投影:为什么 critic 要先收敛一点再更新 actor(策略评估先于改进)?为什么 PPO 里更新几次 epoch 后要停(防止改进定理的前提失效)?这一篇给出这些直觉的精确出处。

为什么需要它

T7/T5 留下一个未比较的选项:既然 V* 是贝尔曼算子的不动点,可以直接迭代(值迭代);也可以两阶段——固定策略解它的值(这一步是线性方程,不需要迭代到死),再用值改进策略(策略迭代)。两条路都通向 V*,但账本不同。

值迭代:每步 O(|S|²|A|)(一次贝尔man备份),需要 O(log(1/ε)/log(1/γ)) 步(T5 的界)。策略迭代:每轮策略评估要解 |S| 元线性方程组(O(|S|³),贵),但轮数通常少得惊人——常常几轮就精确收敛。

为什么轮数少?策略改进定理保证每轮值严格上升,而策略总数有限(|A|^|S|),永不重复的策略序列必然在有限轮内到达「无法再改进」的状态——那正是最优策略。这是组合论证,不依赖 γ 的松紧。

定义

定义 8.1 策略评估

固定 π,解线性方程组 V^π(s) = Σs' p(s'|s,π(s))[r + γV^π(s')]——|S| 个方程 |S| 个未知数,系数矩阵 I−γP_π 可逆(γ<1 时对角占优)。也可用迭代法(修改的贝尔曼算子,γ-压缩,T5 适用)。

为什么这样定「评估」在有限情形是解方程不是迭代——这是策略迭代每轮贵的原因,也是它轮数少的原因(评估是精确的)。

定义 8.2 广义策略迭代(GPI)

任何「近似评估 + 改进」交替的框架。值迭代、策略迭代、actor-critic、Q-learning 都是 GPI 的成员,差别只在两个阶段各自做得多精确。

为什么这样定GPI 是把经典 DP 和现代 RL 连起来的框架图。判断一个新算法,第一问就是:它的评估做到多准?它的改进步保真吗?

定理与证明

定理 8.1 策略改进定理(完整证明)

若对所有 s:Σs' p(s'|s,π'(s))[r+γV^π(s')] ≥ V^π(s),则 Vπ' ≥ V^π(逐状态),且只要有严格不等的状态就严格优于。

证

记改进后的「一步备份算子」作用在 V^π 上为 Tπ'V^π,前提即 Tπ'V^π ≥ V^π(逐点)。

关键恒等式:Tπ' 是 γ-压缩且 Vπ' 是它的不动点(固定策略的贝尔曼方程,T5 定理 5.2 的特例)。

Vπ' − V^π = (Vπ' − Tπ'V^π) + (Tπ'V^π − V^π) = γ Pπ'(Vπ' − V^π) + (Tπ'V^π − V^π)

其中 Pπ' 是策略的转移矩阵。反复代入展开 k 次:

Vπ' − V^π = γ^k Pπ'^k (Vπ'−V^π) + Σj=0k−1 γ^j Pπ'^j (Tπ'V^π − V^π)

令 k→∞:第一项 → 0(γ^k 压死)。第二项的每一项:P^j 保持非负性(随机矩阵),γ^j ≥ 0,而 (Tπ'V^π − V^π) ≥ 0 是前提。所以和 ≥ 0,即 Vπ' ≥ V^π。若某个状态备份严格大且该状态能到达目标状态(不可约),则严格不等传播。∎

注证明结构:「不动点 − 当前点 = 收缩项 + 改进项」的裂项,然后让收缩项消失。这与 T5 证明是同一套肌肉。注意它对期望值成立——样本版的「改进可能暂时变差」正是 /fund/ 里 off-policy 高方差的来源之一。

定理 8.2 收敛速度的比较

值迭代误差按 γ^k 几何衰减(T5);策略迭代轮数 ≤ |A||S|(策略不重复的组合上界),实践中通常 3~10 轮内精确收敛。

证

轮数上界:由定理 8.1 值逐轮严格上升 ⇒ 策略序列无重复 ⇒ 至多 |A||S| 轮(有限个策略)。∎

注这个上界极其松(组合爆炸),但它说明了质的差别:策略迭代的收敛不靠 γ 逼近 1 的宽容度,是「组合意义下的有限步」。大状态空间下评估解不动(O(|S|³)),就要退回值迭代或函数逼近版——这个权衡没有免费午餐。

手算一遍

仍用 T7 的两状态 MDP(γ=0.9)。从劣策略 π₀ =「状态 0 选 a(留在原地)」出发跑策略迭代,数轮数;再对比值迭代达到同样精度要几步。

  1. 第 1 轮评估 π₀(状态 0 选 a):V(s0) = 0+0.9V(s0) → V(s0)=0;V(s1)=10。得 V^π₀ = (0, 10)。
  2. 第 1 轮改进:s0 处比较 a: 0+0.9×0 = 0 vs b: 0.5+0.9×10 = 9.5 → 改选 b。s1 不变。π₁ = (b, stay)。
  3. 第 2 轮评估 π₁:V(s1)=10,V(s0)=0.5+0.9×10=9.5。得 V^π₁ = (9.5, 10)。第 2 轮改进:s0 处 a: 0+0.9×9.5=8.55 < b: 9.5,无变化 → 收敛。
  4. [object Object]
答

策略迭代 2 轮 vs 值迭代 176 步。单步成本反过来(解方程 O(|S|³) vs 一次备份 O(|S|²|A|)),所以结论只在小状态空间成立。这个「轮数 vs 步数」的账在函数逼近场景会重演:actor-critic 的 critic 更新几步、actor 更新一步,本质是同一权衡。

实跑一遍

数字出处

两状态 MDP 实测(γ=0.9):

  • 值迭代到误差 1e−8:176 步
  • 策略迭代(从劣策略 a 出发):2 轮收敛,V = [9.5000, 10.0000]
  • 改进单调性实测:V^b(s0)=9.5000 > V^a(s0)=0.0000 —— 每轮严格上升

映射回强化学习

这里的对象RL 里的对应物站内用法
策略评估critic 的更新(近似评估)用法 →
策略改进actor 的更新(近似改进)用法 →
改进定理前提PPO 限制每次更新的 KL——防止改进定理在样本版失效用法 →
评估精度权衡「critic 更新几步再动 actor」的直接出处用法 →

边界:这一篇停在哪里

本篇停在哪里:异步 DP、无限状态的收敛条件、近似策略迭代的误差累积理论(|V−V*| 的传播界),都不讲。近似版的一阶结论可以给出:评估误差 ε 时,改进后的策略性能损失 ≤ 2γε/(1−γ)²——这个公式在 /fund/approx/ 里以另一面目出现。

自测 4 题

全是手算和「找证明错在哪」类题目,不出背诵题。答不上来回到对应小节。

01策略改进定理证明里「裂项」的作用是什么?

把 Vπ'−V^π 拆成「收缩项(γ^k P^k 项,自动消失)」+「改进项(非负,来自一步比较)」。这一招把「全局比较」化归为「局部一步比较」——所有不动点类收敛证明的通用套路。

02为什么策略迭代的轮数不依赖 γ?

收敛论证是组合的:值严格上升+策略有限 ⇒ 不重复 ⇒ 有限轮。与几何衰减无关。γ 影响的是每轮「评估」的难度(γ→1 时线性方程组病态化),不是轮数。

03值迭代 176 步 vs 策略迭代 2 轮,能说策略迭代总是更快吗?

不能。每轮评估要解 |S| 元线性方程组(O(|S|³)),状态一多就不可行;且近似评估时轮数优势缩水。正确读法:小状态空间用 PI,大状态空间用 VI/函数逼近——账要算,不是背结论。

04actor-critic 里「critic 多更新几步再动 actor」对应本篇什么概念?

策略评估先于策略改进(GPI 的两阶段)。评估太糙时 actor 在噪声值函数上「改进」,改进定理前提失效,可能变差——这就是为什么训不稳时常把 critic 学习率调大或 actor 调小(T10 的两时间尺度)。

接着看

全系列 27 篇

T1矩阵就是旋转的记账本约 25 分钟T2从斜率到梯度:机器人学习算法的第一行约 25 分钟T3向量与受力:点积的物理读法约 20 分钟T4两把尺子和一把更好的尺子约 25 分钟T5电机转一圈的账:弧度、转速与功率约 20 分钟T6复数乘法就是旋转:四元数的一维版约 20 分钟T7基与坐标:为什么机器人什么都用矩阵约 45 分钟T8矩阵乘法:变换的串联,不是表格运算约 40 分钟T9雅可比:关节转一度,末端动多少约 45 分钟T10特征向量:矩阵不敢动的方向约 45 分钟T11SVD 与伪逆:没有精确解时,找最近的解约 50 分钟T12泰勒展开:用直线替曲线打工约 40 分钟T13概率空间:为什么「随机」需要公理约 50 分钟T14期望:「平均」的严格构造约 55 分钟T15条件期望:竖线的真正含义约 60 分钟T16四个不等式:「多少样本才够」的定量答案约 45 分钟T17范数与不动点:「一定收敛」的出处约 55 分钟T18马尔可夫链:时间平均何时等于集合平均约 55 分钟T19MDP 的数学构造:一条公理值多少钱约 50 分钟T20动态规划:两种迭代的账约 50 分钟T21优化:约束为什么不能只靠罚约 55 分钟T22随机逼近:学习率公式里的每一条约 55 分钟T23接触的数学:Hertz 理论约 45 分钟T24摩擦与摩擦锥:约束的几何形状约 40 分钟T25力封闭与抓取度量:ε 是一个线性规划约 50 分钟T26接触运动学:滚动为什么不是「贴着滑」约 45 分钟T27滑移检测:从「感觉到了」到「算出来了」约 50 分钟