强化学习 · 动态规划 · 专题讲解 02

从一组方程
到一台迭代机器

上一集把无穷回报压成了一组方程。这一集是最后一公里:方程不会自己算出来——办法是猜一个初值,反复套用,直到它不再变化。

① 策略评估 ② 压缩映射 ③ 策略改进 ④ 两个迭代
一句话模型只负责给方程;算法要回答三件事——从哪开始、每次动多少、什么时候停。
本片要回答的一件事
Vk+1 = TVk → v*
同一个算子,反复套用
①评估:固定 π,把 vπ 迭代出来
②压缩:误差每轮乘 γ,因此必然收敛
③改进:贪心一步,价值绝不下降
④一根杆:m = ∞ 策略迭代 ↔ m = 1 价值迭代
01 · 策略评估 · Policy Evaluation

给定 π,不解方程,只反复执行方程的右边

① 评估› ② 压缩› ③ 改进› ④ 迭代
Bellman 备份Vk+1(s) ← Σa π(a|s) Σs′,r p(s′,r|s,a) [ r + γ Vk(s′) ] 等价于 V ← TπV:用旧的一整张猜测,算出新的一整张猜测;每个状态只问一句「跟着 π 走一步,拿多少奖励,再按折扣加上下一站的旧猜测」。
同步 · Jacobi
整表算完再替换
理论干净、可并行;代价是要额外存一份旧表。
原地 · Gauss-Seidel
边算边用
后面的状态立刻用到刚更新的值,一次扫描能传好几步——实践中更快。
优先级扫描
只修残差最大的
用优先队列排队,信息传播效率最高,适合状态多、影响稀疏的问题。
闭式解的代价
上一集给过 vπ = (I − γPπ)−1Rπ:O(|S|3) 的一次求逆,还要把整张 P 存下来。状态上万就很吃力,百万级连 P 都存不下。
迭代法的代价
一次扫描 O(|S|2|A|),但要多扫若干轮。不需要求逆、能原地更新、能异步——这是 DP 真正的工程形态。
类比给城市估价:每个小区 ≈ 租金 + 折扣 × 邻居价格。瞎猜一轮全是错的,但每轮都更接近真相——一致性条件反复执行,猜测自己变成答案。
停止判据
所有状态的变化量都小于阈值:maxs |Vk+1(s) − Vk(s)| < θ。它只说明「快不动了」,不等于「已经最优」——准确的误差界留到价值迭代那一幕。
02 · 为什么一定收敛

Tπ 是 γ-压缩:三行证明,一条不动点定理

① 评估› ② 压缩› ③ 改进› ④ 迭代
① 作差
|TπV(s) − TπU(s)| = | Σaπ(a|s) Σs′ γp(s′|s,a)[V(s′) − U(s′)] |
奖励 r 相减消失,只剩 γ 倍的差
② 放大
≤ γ Σaπ(a|s) Σs′ p(s′|s,a) · ‖V − U‖∞
每个差换成统一上界(无穷范数)
③ 归一
= γ ‖V − U‖∞
Σaπ = 1,Σs′p = 1
压缩性取 maxs ⟹ ‖TπV − TπU‖∞ ≤ γ ‖V − U‖∞
Banach 不动点定理接上
完备空间上的压缩映射:
① 不动点唯一——就是 vπ;
② 从任意初值迭代都收敛到它;
③ 收敛是几何的:‖Vk − vπ‖∞ ≤ γk‖V0 − vπ‖∞;
④ 压缩率就是速度:每轮误差乘一次 γ,γ 越靠近 1,需要的轮数越多。
γ 决定一切
误差 k 次扫描 γ = 0.9 快 γ = 0.99 慢
γ = 0.9 → 约 22 轮降一个数量级;γ = 0.99 → 约 230 轮。压缩率趋近 1,每轮几乎不动。
03 · 策略改进 · Policy Improvement

贪心一步:为什么「局部改好」不会让整体变差

① 评估› ② 压缩› ③ 改进› ④ 迭代
贪心改进π′(s) = argmaxa qπ(s, a) = argmaxa Σs′,r p(s′,r|s,a) [ r + γ vπ(s′) ] 在每个状态,改成「只看一步 + 之后跟着老策略走」里最划算的那个动作——只改第一步,后面仍归老策略管。
策略改进定理
设 π、π′ 是确定性策略。若对所有状态 s 都有
qπ(s, π′(s)) ≥ vπ(s),
则对所有 s 都有 vπ′(s) ≥ vπ(s);
只要有一处严格大于,就存在某状态严格变好。
直觉:只换起点那一步
一条从家到公司的固定路线,你在第三个路口发现左转更快;之后仍走原来的路,但整条路线都变快了。
滚动证明的含义:把这个「某一步改一下」重复无限次,结果就是从第一步开始全程按新策略走。
注意
这是逐状态的不等式,不是平均值:它保证每个起点都不亏,而不是「平均下来不亏」。贪心之所以安全,正因为比较是逐个状态做的。
① 假设:qπ(s, π′(s)) ≥ vπ(s),逐状态成立 ② 滚动:对下一状态再用一次,重复无限步 ③ 结论:整条轨迹都按 π′ 走 ⟹ vπ′ ≥ vπ
停下来的条件:若贪心之后 π′ = π(每个状态的最佳动作就是当前动作),则 vπ 满足贝尔曼最优方程;而最优方程的解唯一,于是 vπ = v*、π 就是最优策略。
04 · 定理证明

把不等式「滚动」到无限步:每滚一轮,钉住一步

① 评估› ② 压缩› ③ 改进› ④ 迭代
① 假设
vπ(s) ≤ qπ(s, π′(s))
定理的前提,对所有状态成立
② 定义
= E[ Rt+1 + γ vπ(St+1) | St=s, At=π′(s) ]
q 的定义:走一步,再按折扣接老价值
③ 再用
≤ Eπ′[ Rt+1 + γ qπ(St+1, π′(St+1)) | St=s ]
对下一状态,把同一个假设再用一次
④ 展开
= Eπ′[ Rt+1 + γRt+2 + γ2 vπ(St+2) | St=s ]
多滚动一次,就多钉住一步真实奖励
⑤ 无限
≤ ⋯ ≤ Eπ′[ Rt+1 + γRt+2 + γ2Rt+3 + ⋯ | St=s ]
尾巴是 γk·vπ(St+k) → 0
结论= vπ′(s) ⟹ vπ′(s) ≥ vπ(s),处处成立
最后一环取等号,靠 γ<1(或回合必然终止)且价值有界:尾巴归零 只改一步不够狠,滚动无限次才把整条轨迹换成新策略 某处严格大于 ⟹ 至少一个状态真的变好,迭代才有推进
同时得到这个证明的命门是尾巴必须消失:要么 γ < 1 让 γk → 0,要么回合必然终止(γ = 1 时终止后尾巴恒为 0)。两者都不满足,无限滚动就没有落点。
05 · 策略迭代 · Policy Iteration

评估与改进接起来,就成了一圈永动机

① 评估› ② 压缩› ③ 改进› ④ 迭代
① 策略评估 V ← TπV ,直到 Δ < θ ② 策略改进 π′(s) = argmax qπ(s,a) π′ = π ? 是 输出 π*, v* 否 · π ← π′,回到评估(V 可复用)
①
单调性
由策略改进定理,每轮改进后 vπ′ ≥ vπ,逐状态成立。
②
严格性
若策略真的变了,则至少有一个状态的价值严格变大——不会原地打转。
③
有限性
确定性策略总共只有 |A||S| 个。单调、严格、有限 ⟹ 必在有限步到达稳定点。
闭环:策略稳定 ⟹ 满足贝尔曼最优方程 ⟹ 策略最优。反过来未必:若有并列最优动作,argmax 可能在它们之间来回切换,需固定平局规则(如「当前动作已是最优之一就不换」)才能保证停下。
工程经验 评估不必跑到收敛:跑几轮、甚至只跑一轮就改进,方向往往已经对了——这个「评估精度」就是下一个算法的旋钮。
06 · 策略迭代 · 手算一遍

三站公交:两轮外层,策略就自己停住

① 评估› ② 压缩› ③ 改进› ④ 迭代
场景 一条只有三站的公交线:车从 S1 出发,每到一站只能二选一——慢=停在原站等,拿 1 分;快=直接开去下一站,拿 0 分。问题:每站怎么选,才能让整趟车的折扣总分最大?
S1 · 起点 S2 · 中转 S3 · 终点 到了就结束 · V(S3) ≡ 0 慢 · 1 + 0.5·V(S1) 快 · 0 + 0.5·V(S2) 慢 · 1 + 0.5·V(S2) 快 · 0 + 0.5×0 = 0
Δk = 逐状态「新值 − 旧值」取绝对值后最大:Δ1 = |1.0000 − 0.0000| = 1.0000,Δ2 = |1.5000 − 1.0000| = 0.5000。
评估Vk+1(S1) = 1 + 0.5·Vk(S1)
改进V(S1) = max{ 1 + 0.5·Vk(S1) , 0 + 0.5·Vk(S2) }
k=0→1 V(S1) = 1 + 0.5×0 = 1.0000 | V(S2) = 0 + 0.5×0 = 0.0000
k=1→2 V(S1) = 1 + 0.5×1 = 1.5000 | V(S2) = 0 + 0.5×0 = 0.0000
评估不取 max:π₀ 把两条候选各钉死一条(S1 慢、S2 快)。S3 是终点,V(S3) ≡ 0 永不更新,所以 S2 走快的候选恒为 0、扫多少轮都是 0。
慢=留在原站拿 1 分,快=前进一站拿 0 分,到 S3 就结束(V(S3) ≡ 0);γ = 0.5、θ = 0.01。一直坐慢车 1 + 0.5 + 0.25 + … = 2 ⟹ v* =(2, 2, 0)、π* =(慢, 慢),起点用 V = 0、π₀ =(慢, 快)。
第 1 轮 · 评估 π₀ =(慢, 快)
扫描 kV(S1)V(S2)Δk
00.00000.0000—
11.00000.00001.0000
21.50000.00000.5000
31.75000.00000.2500
41.87500.00000.1250
51.93750.00000.0625
61.96880.00000.0313
71.98440.00000.0156
81.99220.00000.0078 ✓
改进 q(S2, 慢) = 1 + 0.5×0 = 1.000 > q(S2, 快) = 0 ⟹ π₁ =(慢, 慢)
第 2 轮 · 热启动1.9922 → 取 2.0000
扫描 kV(S1)V(S2)Δk
02.00000.0000—
12.00001.00001.0000
22.00001.50000.5000
32.00001.75000.2500
42.00001.87500.1250
52.00001.93750.0625
62.00001.96880.0313
72.00001.98440.0156
82.00001.99220.0078 ✓
停 q(S2, 慢) = 1 + 0.5×1.9922 = 1.9961 > q(S2, 快) = 0 ⟹ π₂ = π₁
两轮外层:8 + 8 = 16 次扫描、2 次改进 ⟹ v* =(2, 2, 0)、π* =(慢, 慢)。热启动接住上一轮的 1.9922,第 2 轮 S1 一次都不动,每次扫描的账只花在 S2 上;改进再没改动动作,所以停。
07 · 价值迭代 · Value Iteration

把「评估到收敛」删掉,两个循环压成一个

① 评估› ② 压缩› ③ 改进› ④ 迭代
价值迭代Vk+1(s) ← maxa Σs′,r p(s′,r|s,a) [ r + γ Vk(s′) ] 就是贝尔曼最优方程的右边:把按 π 求期望换成对动作取最大,一次备份既是评估一步,也隐含改进一次。
策略迭代 · 双层循环
每轮 = 完整评估 + 1 次改进
显式维护 π;V 是真实策略价值,可解释、可监控;每轮贵、轮数少。
价值迭代 · 单层循环
每轮 = 1 次评估 + 隐含改进
不维护 π,最后一步 argmax 抽取;中间 V 只是朝 v* 逼近的过程量,不是任何策略的价值。
停止条件的误差界‖ Vk+1 − v* ‖∞ ≤ γ / (1 − γ) · ‖ Vk+1 − Vk ‖∞ Δ 小只说明「快不动了」,不等于已经最优;这个系数把 Δ 翻译成「离最优还有多远」。
γ 越接近 1,Δ 越不可信
γ = 0.9 时系数是 9;γ = 0.99 时是 99。若要求 ‖V − v*‖ ≤ ε,阈值应设 θ = ε(1−γ)/γ,而不是直接拿 ε 当阈值。
停法 ① · 看 Δ
保守:先换算阈值
要误差 ≤ ε,就把阈值设成 ε(1−γ)/γ;直接用 ε 会高估精度。
停法 ② · 看策略
最实用:argmax 不再变
策略常比价值先收敛:V 还差一点,动作已经对了,可直接停。
停法 ③ · 看预算
固定轮数
算力有限就限定扫描次数,接受残余误差——工程最常用。
08 · 价值迭代 · 手算一遍

同一个世界:每步取最大,八轮到 1.9922

① 评估› ② 压缩› ③ 改进› ④ 迭代
一步备份Vk+1(S1) = max{ 1 + 0.5·Vk(S1) , 0 + 0.5·Vk(S2) } 慢:留在原站拿 1,再加 0.5 × 自己的旧值;快:前进一站拿 0,再加 0.5 × 下一站的旧值。两项都拿同一张旧表算,所以整轮同步更新也不会互相污染。
k = 0 → 1旧表 V₀ =(0, 0)
k = 1 → 2旧表 V₁ =(1, 1)
V(S1) = max{ 1 + 0.5×0 , 0 + 0.5×0 } = max{1.00, 0.00} = 1.00 ⟹ 慢
V(S1) = max{ 1 + 0.5×1 , 0 + 0.5×1 } = max{1.50, 0.50} = 1.50 ⟹ 慢
V(S2) = max{ 1 + 0.5×0 , 0 + 0.5×0 } = max{1.00, 0.00} = 1.00 ⟹ 慢
V(S2) = max{ 1 + 0.5×1 , 0 + 0.5×0 } = max{1.50, 0.00} = 1.50 ⟹ 慢
S3 是终点、V(S3) ≡ 0,S2 走「快」的第二项恒为 0。Δk = 各状态变化量取绝对值后最大:Δ1 = |1.0000 − 0.0000| = 1.0000、Δ2 = |1.5000 − 1.0000| = 0.5000,之后逐轮减半。整套只有一层循环,扫一遍就挪一步。
轮次 kV(S1)V(S2)V(S3)Δkargmax
00.00000.00000——
11.00001.000001.0000慢 / 慢
21.50001.500000.5000慢 / 慢
31.75001.750000.2500慢 / 慢
41.87501.875000.1250慢 / 慢
51.93751.937500.0625慢 / 慢
61.96881.968800.0313慢 / 慢
71.98441.984400.0156慢 / 慢
81.99221.992200.0078 ✓慢 / 慢
∞2.00002.000000停
先收敛的是动作:第一轮的 argmax 就已经是(慢, 慢),策略比价值早七轮停下——这就是上一幕「看动作变不变」比「看 Δ」更早停的来历。
误差界核对:‖V8 − v*‖∞ = 0.0078 ≤ γ/(1−γ)·Δ8 = 1 × 0.0078 —— 这里恰好取等号,因为 S1、S2 的误差同步,且都等于每轮的变化量。
09 · 本质关系

同一根杆:轮数省四倍,每轮贵九倍

① 评估› ② 压缩› ③ 改进› ④ 迭代

令评估阶段固定做 m 次扫描再改进:m = ∞ 是策略迭代,m = 1 是价值迭代,中间叫修正策略迭代(MPI)。下面用同一个三状态世界把三种 m 的账算到底。

m = 1价值迭代 m ≈ 5MPI · 甜点区 m ≈ 20MPI · 评估更准 m = ∞策略迭代
每轮最便宜 · 轮数最多每轮最贵 · 轮数最少
同一个世界 · 目标 ‖V − v*‖∞ < 0.01m = 1 · VIm = 3 · MPIm = ∞ · PI
每轮评估扫描138
每轮全表操作149
误差达标的轮数842
总全表操作 = 轮数 × 每轮81618
走 3 轮用掉的扫描3916
3 轮后的误差0.25000.03130.0078
口径:一次全表操作 = |S|²|A|。VI 的取最大与备份同一遍完成,记 1;PI / MPI 的改进是单独一遍,另记 1。
轮数 8 → 4 → 2,每轮 1 → 4 → 9,乘出来 8 → 16 → 18:轮数省了四倍,总账反而贵了两倍多。多扫的每一次评估,都是为「少转几圈」付的账。
谷底在哪 本例 γ = 0.5、只有三个状态,收缩极快,多扫立刻变浪费,所以最优点贴着左端;一般问题里谷底常落在 m = 3~10。γ → 1 时两边一起变慢,PI 值钱的是外层只转两圈、每轮都握着一个合法策略。
10 · 收束

一条链:不动点 → 迭代 → 最优

① 评估› ② 压缩› ③ 改进› ④ 迭代
①
压缩映射给了收敛
Tπ 每作用一次,任意两点的距离乘 γ;于是不动点唯一,从任意初值出发都收敛,误差按 γk 掉。
②
策略改进给了方向
一步的 q 不低于老价值,滚动到无限步就得到 vπ′ ≥ vπ——贪心永远不吃亏。
③
两者相拼就是策略迭代
单调 + 严格 + 有限 ⟹ 有限步停在稳定点;而稳定点满足最优方程,所以它就是 π*, v*。
④
价值迭代只是把评估压成一步
同一个最优算子 T*,不维护策略;m = 1 与 m = ∞ 是一根杆的两端。
评估与改进,绕着一个不动点转圈 —— 转到转不动,就是最优
下一站 · 广义策略迭代 GPI 与异步 DP
片尾 · 出品说明
朝露记
强化学习 · 第二章 · 动态规划专题
朝露记出品
笔记梳理 讲解配音 动画编排
第二章 · 完结篇 下一站 · 广义策略迭代与异步 DP
解
00:00 / 13:08
空格 播放/暂停 ← → 切幕 R 重播 1–9 / 0 跳转