原理层 T20 / 27 · 决策与优化
动态规划:两种迭代的账
值迭代每步便宜但要很多步,策略迭代每步贵但轮数少。策略改进定理保证每轮严格不降——它们谁快,在具体问题上是可算的账。
一句话结论
策略改进定理(每轮新策略不劣于旧策略)+ 策略评估的精确求解(解线性方程组)= 策略迭代。它是「广义策略迭代」框架的精确版,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 的特例)。
其中 Pπ' 是策略的转移矩阵。反复代入展开 k 次:
令 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 轮评估 π₀(状态 0 选 a):V(s0) = 0+0.9V(s0) → V(s0)=0;V(s1)=10。得 V^π₀ = (0, 10)。
- 第 1 轮改进:s0 处比较 a: 0+0.9×0 = 0 vs b: 0.5+0.9×10 = 9.5 → 改选 b。s1 不变。π₁ = (b, stay)。
- 第 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,无变化 → 收敛。
- [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 的两时间尺度)。