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

从一台机器
到一张算法地图

上一集把 DP 装成了一台机器:评估、改进、再评估。这一集把它摊开成地图——两个迭代怎么比、为什么所有强化学习算法都是同一副骨架、大状态怎么算得动、定理怎么兜底、真实世界为什么仍然用不起来。

① 一张表 ② 成本账 ③ GPI 骨架 ④ 工程提速 ⑤ 地基与出路
一句话DP 不是一堆算法,而是一副骨架 + 若干填空——本片把这副骨架铺开来看。
本片要回答的五件事
评估 + 改进 = 一副骨架
同一副骨架,六种填法
①比:策略迭代与价值迭代,只差三个根子
②账:总成本 = 每轮成本 × 轮数,最优在 m 很小处
③统:GPI 把 MC、TD、Q-learning 一起收进来
④快:原地、异步、优先级扫描
⑤底:压缩 ⇒ 唯一 ⇒ 收敛;nk 撞墙后有三条生路
01 · 两种迭代 · PI vs VI

六行差别,其实只有三个根子

① 对比› ② 成本› ③ GPI› ④ 工程› ⑤ 地基与出路
维度 策略迭代 Policy Iteration 价值迭代 Value Iteration
迭代结构 双层:评估内循环 + 改进外循环 单层:一次备份就是一步
每轮做的事 评估到收敛,再改进一次 备份一次,改进隐含在 max 里
每轮成本 O(k·|S|²|A|),k 通常远大于 1 O(|S|²|A|),还能原地 / 异步加速
迭代轮数 少:常 5~20 轮就稳定 多:≈ log(1/ε)/log(1/γ),γ→1 爆炸
中间量含义 V 是真实策略价值,可解释、可监控 V 只是向 v* 逼近的过程量
理论地基 策略改进定理(逐状态比较) 最优算子 T* 是 γ-压缩映射
根子 ①
评估做几次
1 次是价值迭代,做到收敛是策略迭代,中间的 m 就是修正策略迭代。
根子 ②
要不要显式 π
维护 π 就能解释、能中途停机;不维护就只剩一张价值表。
根子 ③
靠哪个定理
改进定理走「单调 → 严格 → 有限」;压缩映射走「唯一 → 收敛」。
02 · 同一根杆

总成本 = 每轮成本 × 轮数,最优点在 m 很小处

① 对比› ② 成本› ③ GPI› ④ 工程› ⑤ 地基与出路
Modified PI评估固定做 m 次扫描,再改进一次:m = ∞ 是策略迭代,m = 1 是价值迭代,中间取值叫修正策略迭代。 m 是这根杆上唯一的旋钮——它同时决定了「每轮多贵」和「要转多少轮」。
m = 1价值迭代 m ≈ 5MPI · 甜点区 m ≈ 20MPI · 评估更准 m = ∞策略迭代
每轮最便宜 · 轮数最多每轮最贵 · 轮数最少
总成本:两头高,中间低
总成本 评估次数 m 最优点 m ≈ 5 m = 1 · 轮数太多 m = ∞ · 每轮太贵
为什么小 m 就够
① 每轮成本 ≈ m × |S|²|A|,随 m 线性涨;
② 多评估的边际收益递减:m 从 5 加到 20,省下的轮数有限;
③ 真正要的不是价值精确,而是 argmax 正确——价值差一点,动作早就对了。
所以工程上常常 m 取 3~10,而不是 ∞。
成本账
面试常问「两个迭代什么关系」——答:同一根杆上的两个端点,m 是唯一旋钮;总成本 ≈ 每轮成本 × 轮数,所以最优不在两端,而在中间偏左。
03 · 广义策略迭代 · GPI

一套骨架,六种填法

① 对比› ② 成本› ③ GPI› ④ 工程› ⑤ 地基与出路
评估 · Evaluation 让 V 更接近当前的 π V → vπ 改进 · Improvement 让 π 更贪心于当前的 V π → greedy(V) π 想用尽 V 评估先放一步 V 想说清 π 改进再进一步 不动点 v*, π*
算法 评估用什么 改进怎么做
策略迭代 完整模型 + 备份到收敛 严格 argmax
价值迭代 完整模型 + 只备份 1 次 隐含在 max 里
Monte Carlo 采样整条 episode 求平均 ε-greedy,保留探索
SARSA / TD 采样单步 + 自举 ε-greedy
Q-learning 采样单步 + max 自举 ε-greedy(行为策略)
DQN / AC 网络拟合 Q / V DQN:argmax Q + ε;AC:策略梯度
左列换个「评估」、右列换个「改进」,就是一个新算法——六行没有一行动了骨架。
一句话 迭代路径不会一步落到交点,而是锯齿状逼近;v* 唯一,π* 可能不止一个。
GPI 之后,后面所有算法都成了填空题:把「评估」换成采样估计、把「改进」换成带探索的近似贪心,就得到 MC / TD / Q-learning / Actor-Critic。差别只在估计方式与是否精确,不在思想。
04 · 工程提速 · 一

让信息在一轮里跑到底

① 对比› ② 成本› ③ GPI› ④ 工程› ⑤ 地基与出路

教科书算法是同步的:整张表一起更新。可 |S| 上亿时扫全表太贵,而且大多数状态这一步根本没变——先看一个四层楼的小例子。

示例 · 四层楼:只有走到 4F 才得 1 分(γ = 0.5)
V(4F) = 0 V(3F) = 1 + 0.5·V(4F) V(2F) = 0.5·V(3F) V(1F) = 0.5·V(2F) 起手 V₀ 全是 0.00 | 金色 = 这一轮才定下的值 | 圈号 = 第几轮定下来 同步 旧表算新表 4F终点0.00 3F0.00 2F0.00 1F0.00 1.00 ① 0.50 ② 0.25 ③ 3 轮 一轮只推一层 原地 边算边用 4F终点0.00 3F0.00 2F0.00 1F0.00 1.00 ① 0.50 ① 0.25 ① 1 轮 边算边用,一轮到底 异步 顺序随意 4F终点0.00 3F0.00 2F0.00 1F0.00 1.00 ① 0.50 ① 0.25 ② 2 轮 1F 白算一次,多扫一轮 同步:只许读上一轮的表(虚线)—— 一轮只把值往下推一层,3 轮才到底。 原地:删掉副本,读到的是刚写下的新值(实线)—— 一轮到底;反着从 1F 往上扫,就退化成同步。 异步:顺序随意,1F 先白算一次,第 2 轮才补上 —— 只要每层反复更新,照样收敛。
异步 DP:收敛的两个条件
不要求「每轮扫全表」,而是任意顺序、任意粒度地更新。只要:
① 每个状态被无限次更新;
② 折扣 γ < 1(或所有策略都必然终止);
那么异步价值迭代仍然收敛到 v*。
顺序自由,但覆盖必须够。
乱序为什么也行?单次更新不会让 ∞-范数误差变大;所有状态各更新过一遍后,误差至多变为 γ 倍。顺序只决定「先到哪一步」。
变体 ①
原地价值迭代
去掉副本,边算边用。最便宜、最常用的一种异步。
变体 ②
加权扫描
按固定分布随机抽状态更新;分布就是「你更关心哪些状态」。
变体 ③
实时 DP
只更新与智能体当前位置相关的一小片状态——边走边算。
等价 同步与异步收敛到同一个 v*;差别只在信息传得快不快——这才是「少算没用的」的全部含义。
05 · 工程提速 · 二

优先级扫描:只敲有共用墙的邻居

① 对比› ② 成本› ③ GPI› ④ 工程› ⑤ 地基与出路
Bellman 残差δ(s) = | maxa Σs′,r p(s′,r|s,a)[ r + γV(s′) ] − V(s) | 残差大 = 这个状态的估值「还很不对劲」 = 优先更新它——因为它的变化会带动它的前驱状态。
四步流程
1
算残差,进最大堆
把所有状态的 δ(s) 压进优先队列。
2
弹出残差最大的 s
只对它做一次备份——最值钱的那一步。
3
只重算它的前驱
能一步到达 s 的状态才会被影响,其余不动。
4
重复到堆空或残差够小
思路类似 Dijkstra:只处理真正会变化的地方。
优先队列里在排什么
s₇δ = 0.84
s₃δ = 0.51
s₁δ = 0.27
s₉δ = 0.09
s₄δ = 0.02
弹出 s₇ 之后,只把 s₆、s₈(能一步到 s₇ 的前驱)重新算残差、重新入堆。其余状态一次都不碰。
单次更新的代价只取决于前驱数,再加 O(log|S|) 的堆操作;同步每轮则是 O(|S|²|A|)。
类比同步 DP 像小区里有人搬进来,物业挨家挨户敲门通知;优先级扫描只敲「和它共用墙」的那几户,再由他们去敲自己的邻居——消息沿关系链定向扩散。
对稀疏转移、局部变化的问题(大规模路网、棋盘),提速可以非常大;代价是要维护一张「谁依赖谁」的反向表。
06 · 理论地基 · Banach

压缩 ⇒ 唯一 ⇒ 收敛,快慢由 γ 决定

① 对比› ② 成本› ③ GPI› ④ 工程› ⑤ 地基与出路
几何直觉:整个空间被挤向一点
价值函数空间 ℝ|S| · 配上无穷范数 · 完备 V₀ U₀ 每迭代一次,两点距离 × γ 第 1 次 ≤ γ·d 第 2 次 ≤ γ²·d …… v*:唯一不动点 γᵏ·d → 0,两点被挤成一点 初值离得多远都不重要——只要 γ < 1,迭代就是一台「空间收缩机」。
①
定义:γ-压缩
存在 γ ∈ [0,1),使任意 V、U 都满足 ‖TV − TU‖∞ ≤ γ‖V − U‖∞。
②
Tπ 与 T* 都是压缩
前者靠期望的线性与归一;后者多一个关键引理 |max f − max g| ≤ max |f − g|。
③
三个结论,一条定理
评估收敛、价值迭代收敛、v* 存在且唯一——全部由 Banach 一句话给出。
④
记忆锚点
压缩 ⇒ 唯一 ⇒ 收敛 ⇒ 快慢由 γ 决定——评估与价值迭代的收敛都挂在这条链上。
γ = 1 时
算子退化成非扩张(1-Lipschitz),Banach 定理失效:有吸收终止态且策略必然终止时,可按「随机最短路 SSP」处理(终止起到折扣的作用);否则价值可能是无穷大,迭代会发散或震荡。所以实现里常取 γ = 0.99 而不是 1.0——代价是视野被截在 100 步上下,换回来的是收敛有保证。
视野 有效视野 ≈ 1/(1−γ):γ = 0.9 → 约 10 步、γ = 0.99 → 约 100 步、γ = 0.999 → 约 1000 步;轮数按同一比例涨——这就是「快慢由 γ 决定」。
07 · 天花板 · Curse of Dimensionality

n 的 k 次方:价值表存不下的那一天

① 对比› ② 成本› ③ GPI› ④ 工程› ⑤ 地基与出路
状态数:k 个变量、每个 n 档
k = 110
k = 2100
k = 31 000
k = 610⁶
k = 1010¹⁰
围棋≈ 10¹⁷⁰
示意(n = 10,按数量级示意,围棋一栏已截断):每多一个变量,就乘以 n。
①
死穴一:需要完整模型
必须知道 p(s′,r|s,a);机器人、推荐系统、对话里几乎拿不到——只能先学模型再规划,或改用无模型方法。
②
死穴二:状态指数增长
每个状态至少访问一次就要 O(nk),穷举不可行。围棋 19×19 的局面数比宇宙原子还多。
③
AlphaGo 的选择
不存表,用神经网络压缩价值函数 vθ(s) ≈ v(s)——从「查表」变成「泛化」。
出路 ① · 没有模型
采样替代期望
MC 用整条轨迹的平均值估 G;TD 用 R + γV(s′) 单步自举。只要能和环境交互。
出路 ② · 状态太多
函数逼近 / 压缩
线性特征 → 神经网络(DQN)。把「表」换成「参数」,把「查表」换成「泛化」。
出路 ③ · 状态太多
只算相关子集
异步 DP、优先级扫描、实时 DP;MCTS 从当前局面向前采样建树。
TD 的目标 Rt+1 + γV(St+1) 就是 DP 备份里期望内部的采样版本;DQN 的损失 (r + γ maxa′Q(s′,a′) − Q(s,a))² 是采样版贝尔曼残差的平方(目标网络冻结)。
学好 DP 不是学一段历史,而是拿到所有现代 RL 的出厂说明书。
08 · 收束

一张地图:从两个迭代到所有算法

① 对比› ② 成本› ③ GPI› ④ 工程› ⑤ 地基与出路
①
两个迭代,三个根子
差在「评估做几次、要不要显式 π、靠哪个定理」。m = ∞ 与 m = 1 是同一根杆的两端。
②
总成本是乘积,最优点在中间偏左
每轮成本随 m 线性涨,多评估的边际收益递减;工程上 m 取 3~10 往往最划算。
③
GPI 是所有算法的骨架
评估与改进互相拉扯,收敛到 v*(唯一)与某个最优策略。换掉估计方式与探索,就得到 MC / TD / Q-learning / DQN。
④
工程提速靠「少算没用的地方」
原地让信息一轮跑到底;异步只要求「无限次覆盖」;优先级扫描按残差排队,思路类似 Dijkstra。
⑤
理论有压缩兜底,现实靠三条出路
压缩 ⇒ 唯一 ⇒ 收敛,γ→1 就慢;nk 撞墙后,采样、逼近、只算子集。
DP 给的是骨架与定理,后面每一章只是在换评估的估计方式
下一站 · 04 · 从定理到手感 一个两状态 MDP 手算到底
片尾 · 出品说明
朝露记
强化学习 · 第二章 · 动态规划专题
朝露记出品
笔记梳理 讲解配音 动画编排
专题 03 · 完 下一站 · 04 从定理到手感
解
00:00 / 09:40
空格 播放/暂停 ← → 切幕 R 重播 1–9 / 0 跳转