强化学习 · 动态规划 · 专题讲解 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 × |S|²|A|,随 m 线性涨;
② 多评估的边际收益递减:m 从 5 加到 20,省下的轮数有限;
③ 真正要的不是价值精确,而是 argmax 正确——价值差一点,动作早就对了。
所以工程上常常 m 取 3~10,而不是 ∞。
成本账
面试常问「两个迭代什么关系」——答:同一根杆上的两个端点,m 是唯一旋钮;总成本 ≈ 每轮成本 × 轮数,所以最优不在两端,而在中间偏左。
03 · 广义策略迭代 · GPI
一套骨架,六种填法
① 对比›
② 成本›
③ GPI›
④ 工程›
⑤ 地基与出路
算法
评估用什么
改进怎么做
策略迭代
完整模型 + 备份到收敛
严格 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。差别只在估计方式与是否精确,不在思想。
① 对比›
② 成本›
③ GPI›
④ 工程›
⑤ 地基与出路
教科书算法是同步的:整张表一起更新。可 |S| 上亿时扫全表太贵,而且大多数状态这一步根本没变——先看一个四层楼的小例子。
示例 · 四层楼:只有走到 4F 才得 1 分(γ = 0.5)
异步 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›
④ 工程›
⑤ 地基与出路
几何直觉:整个空间被挤向一点
①
定义:γ-压缩
存在 γ ∈ [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 的出厂说明书。
① 对比›
② 成本›
③ GPI›
④ 工程›
⑤ 地基与出路
①
两个迭代,三个根子
差在「评估做几次、要不要显式 π、靠哪个定理」。m = ∞ 与 m = 1 是同一根杆的两端。
②
总成本是乘积,最优点在中间偏左
每轮成本随 m 线性涨,多评估的边际收益递减;工程上 m 取 3~10 往往最划算。
③
GPI 是所有算法的骨架
评估与改进互相拉扯,收敛到 v*(唯一)与某个最优策略。换掉估计方式与探索,就得到 MC / TD / Q-learning / DQN。
④
工程提速靠「少算没用的地方」
原地让信息一轮跑到底;异步只要求「无限次覆盖」;优先级扫描按残差排队,思路类似 Dijkstra。
⑤
理论有压缩兜底,现实靠三条出路
压缩 ⇒ 唯一 ⇒ 收敛,γ→1 就慢;nk 撞墙后,采样、逼近、只算子集。
DP 给的是骨架与定理,后面每一章只是在换评估的估计方式
下一站 · 04 · 从定理到手感 一个两状态 MDP 手算到底
片尾 · 出品说明
朝露记出品
笔记梳理
讲解配音
动画编排
专题 03 · 完
下一站 · 04 从定理到手感
解