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

从定理
到手感

前三集把 DP 从回报推到定理:两个迭代、一副骨架、一条压缩定理。这一集回到纸笔——手算一遍看压缩真的发生,再把七个误区扫干净、压成一页速查表,最后用六道题自检。

① 手算实验 ② 误差 ×γ ③ 七个误区 ④ 一页速查 ⑤ 六道自测
一句话理论只证明「会收敛」;手算才让你相信——这一集把每个结论都落到一组具体的数上。
本片要回答的五件事
v ← T v ⇒ 误差 × γ
一条主线:定理 ⇒ 手感
①算:两状态、γ = 0.5,闭式解 2/3 与 4/3
②缩:误差每轮恰好乘 0.5,几何收敛
③辨:七个误区,根子是把理想假设当现实
④查:十三行速查表,一张知识地图
⑤测:六道题,考「为什么」不考「是什么」
01 · 手算实验 · 设定

两个状态、一个动作、γ = 0.5,全部可以手算

① 手算› ② 误差› ③ 误区› ④ 速查› ⑤ 自测
模型s₁ → s₂ 奖励 0;s₂ → s₁ 奖励 1;折扣 γ = 0.5,只有一个动作。 一个动作 + 确定转移 ⇒ 期望退化成一项,矩阵退化成 2×2——所有式子都能手算完。
最小 MDP:一条来回的链
s₁ 起点 s₂ 收奖励 奖励 0 确定性转移 奖励 1 两个状态 · 一个动作 · 折扣 0.5 —— 没有任何一项需要数值方法
方程 → 消元 → 闭式解
1
写出两条方程
v(s₁) = 0 + 0.5·v(s₂) ; v(s₂) = 1 + 0.5·v(s₁)
2
代入消元
v(s₁) = 0.5·(1 + 0.5·v(s₁)) = 0.5 + 0.25·v(s₁)
3
移项求解
0.75·v(s₁) = 0.5 ⇒ v(s₁) = 2/3 ≈ 0.6667
4
回代得另一个
v(s₂) = 1 + 0.5 × 2/3 = 4/3 ≈ 1.3333
标准答案
v = (2/3, 4/3),六位小数 (0.666667, 1.333333)。无穷范数取两个状态里较大的那个误差;后面会看到,较大的那个在 s₁、s₂ 之间轮换。
02 · 手算实验 · 迭代

从 V₀ = (0,0) 出发,误差每轮恰好乘 γ

① 手算› ② 误差› ③ 误区› ④ 速查› ⑤ 自测
先手算,再对表:每轮只用上一轮的值
轮先逐轮代入(粗体 = 上一轮的值)误差
k=0V₀(s₁) = 0  V₀(s₂) = 0  (初值全零)1.3333
k=1V₁(s₁) = 0+0.5×0 = 0  V₁(s₂) = 1+0.5×0 = 10.6667
k=2V₂(s₁) = 0+0.5×1 = 0.5  V₂(s₂) = 1+0.5×0 = 10.3333
k=3V₃(s₁) = 0+0.5×1 = 0.5  V₃(s₂) = 1+0.5×0.5 = 1.250.1667
扫描 kV(s₁)V(s₂) ‖Vₖ − v‖∞误差比
00.00000.00001.3333—
10.00001.00000.66670.500
20.50001.00000.33330.500
30.50001.25000.16670.500
40.62501.25000.08330.500
50.62501.31250.04170.500
⋯⋯⋯⋯0.500
∞0.66671.33330—
log 误差 扫描 k 0 5 一条直线:斜率 = log γ
①
几何收敛
误差每轮恰好乘 0.5 = γ,正是 ‖Vₖ − v‖∞ ≤ γᵏ‖V₀ − v‖∞。
②
初值无关
换成 (100, −50):数值正负摆动(这才是真正的不单调),但误差比每轮仍恰好 0.5。
③
阶梯式前进
两个状态轮流更新:奇数轮 V(s₂) 上一级,偶数轮 V(s₁) 上一级,都不回头。
各状态收敛节奏不同——这正是异步 DP 与优先级扫描的动机:谁落后、谁残差大,就先算谁。
03 · 常见误区 · 前三条

先扫三个最容易想歪的地方

① 手算› ② 误差› ③ 误区› ④ 速查› ⑤ 自测
读法七个误区不是七个散点,它们大多来自同一个动作:把 DP 的理想假设,当成了 RL 的全部现实。
Q1 · 价值迭代没有策略?
策略藏进了 max 里
每次取 max 的瞬间就选定了动作,等价于「评估 1 步 + 立即改进」;收敛后再补一步 argmax,把策略显式抽出来。
用 GPI 看:两者是同一个循环,只是评估精度不同。
Q2 · 评估必须跑到收敛?
刚好能分辨最优动作最划算
V 只要足够接近 vπ,argmax 就会指向正确动作。评估做到「再精确也换不出新动作」就够了。
这正是修正策略迭代里那个 m 的来历。
Q3 · DP 为什么没有探索?
因为它不采样
对所有动作、所有后继求和,每个分支都算过了——没有「没试过」的动作,自然不需要 ε 贪心这种探索机制。
一旦换成采样,未被采样的动作没有估计,探索才成为必需。
三条,背后是两条事实
两条事实:模型算尽分支 · argmax 只看排序 前者管探索与策略,后者管评估精度 不需要探索 没有没试过的动作 → 不用 ε 贪心 不必精确 argmax 只看排序 → 够分辨就行 策略不缺席 取 max 就是选动作 → 藏在 max 里 合起来看 DP 花掉的是「算力」,省下的是「试错」 换来的是零方差、全覆盖的备份 代价:必须有模型;越出这个前提,推论全部失效
三条背后是两条事实:模型把分支算尽,所以不必探索、策略可藏进 max;argmax 只看排序,所以评估不必绝对精确。
04 · 常见误区 · 后四条

剩下四问:场景、边界与实现

① 手算› ② 误差› ③ 误区› ④ 速查› ⑤ 自测
Q4 · DP 理论有用、实践没用?
模型明确、状态不多时,它仍是最优选择
库存补货、电梯调度、生产排程、MDP 精确求解;也能当子求解器——Dyna 的规划步、MCTS 树内的价值回传。不适用是高维感知问题,原因是状态太多,不是思想过时。
判据只有两条:有模型吗?表存得下吗?
Q5 · γ 能不能取 1?
只在「必然终止」时才安全
否则回报可能是无穷、压缩性失效、迭代发散或震荡。工程默认 γ = 0.99 / 0.995,是有意的权衡:1/(1−γ) 就是有效视野(0.99 → 约 100 步)。
γ 是「看得多远」与「算得快不快」的同一个旋钮。
Q6 · 轮数少 = 成本低?
要比总计算量,不比外层轮数
一轮策略迭代把评估做到收敛,工作量远大于一轮价值迭代。公平单位是总计算量,两者常在同一量级。
只评估 3~5 步的修正策略迭代,经常最快。
Q7 · 两个动作 q 值相等?
任取其一,不影响最优性
最优价值 v* 唯一,但最优策略可能有多个——这正是「解不唯一、价值唯一」的地方。
实现时保留旧动作,避免在两个等价动作间反复跳。
类比拿着一份完整地图走路,和边走边问路:DP 是前者——它是一种能力,不是一个限制。有能力而不用,和用不了,是两回事。
七问归一
所有误区都来自同一个错位:把 DP 的理想假设(有模型、全分支、零方差)当成了 RL 的全部现实。分清这一层,七个问题会自动消失。
05 · 一页速查表

全章压成十三行:定义 → 方程 → 解法 → 迭代 → 收敛

① 手算› ② 误差› ③ 误区› ④ 速查› ⑤ 自测
名称公式一句话作用
回报Gt = Σk≥0 γk Rt+k+1要最大化的目标
状态价值vπ(s) = 𝔼π[Gt | St = s]「站在 s 有多好」
动作价值qπ(s,a) = 𝔼π[Gt | St=s, At=a]「在 s 做 a 有多好」
贝尔曼期望方程vπ(s) = Σa π Σs′,r p[r + γvπ(s′)]评估给定策略(线性,可解)
贝尔曼最优方程v*(s) = maxa Σs′,r p[r + γv*(s′)]刻画最优价值(非线性,一般靠迭代求解)
矩阵解vπ = (I − γPπ)−1 Rπ理论闭式解,成本 O(|S|³)
策略评估V ← TπV反复备份到收敛
策略改进π′(s) = argmaxa qπ(s,a)贪心,保证不变差
策略迭代评估到收敛 → 改进 → 重复外层轮数少,每轮贵
价值迭代V ← T*V评估只做 1 步,实现最简
压缩性‖TV − TU‖∞ ≤ γ‖V − U‖∞评估与价值迭代收敛的地基
误差界‖Vk+1 − v*‖ ≤ γ/(1−γ)·‖Vk+1 − Vk‖只用相邻两轮就能算,不必知道 v*
停止阈值θ = ε(1−γ)/γ保证 ‖V − v*‖ ≤ ε(策略 ε-最优需再除以 2)
从上往下就是一条主线:定义 → 方程 → 解法 → 四个算法动作 → 收敛 → 停机。第十三行那个 θ,是把「误差界」翻译成「该停了」的那一步。
06 · 一页速查表 · 主线

把十三行串成一张图

① 手算› ② 误差› ③ 误区› ④ 速查› ⑤ 自测
回报 Gₜ 要最大化的目标 贝尔曼期望方程 线性 · 可解:v = (I − γP)⁻¹R 贝尔曼最优方程 非线性 · 一般靠迭代:多了一个 max 策略评估(对 π 反复备份)+ 改进定理 改进保证不变差 ⇒ 有限步到达最优 价值迭代(对 max 反复备份) 每轮只评估 1 步,改进藏在 max 里 GPI:评估 ⇄ 改进 PI / VI / MPI 都是特例;m 决定每轮评估几步 采样替代期望 MC · TD · Q-learning 函数逼近替代表 DQN · Actor-Critic
读图往左的分支是「策略已知、要算价值」;往右的分支是「价值未知、要同时找策略」。两者在 GPI 汇合——再往下一层,就是把「期望」换成「采样」、把「表」换成「函数」。
上三层回答「怎么算」:方程 → 评估 → 改进;下两层回答「算不动时怎么办」:换采样、换逼近。十三行速查表,就挂在这张图的节点上。
07 · 自测题 · 六道

六道题:考的是「为什么」,不是「是什么」

① 手算› ② 误差› ③ 误区› ④ 速查› ⑤ 自测
Q1 · 线性 vs 非线性
为什么最优方程不能求逆?
max 是非线性的,写不成矩阵乘法 (I − γP)−1R;一般没有闭式解,通常靠迭代(也可用线性规划或策略迭代)。
线性 → 闭式解;非线性 → 不动点迭代。
Q2 · 边界
γ = 0 会收敛成什么?
规划视野退化成 1 步:v(s) = maxa r(s,a)(期望即时奖励),完全不管未来。
γ 控制的正是「规划视野」。
Q3 · 实现技巧
用上一轮的值做初值会怎样?
更快——初始误差更小,扫描次数按 log 减少。这就是热启动。
工程常规做法:评估从不归零。
Q4 · 收敛次序
为什么说策略比价值先收敛?
策略只依赖 q 的相对排序;价值依赖绝对数值。排序对了,argmax 就对了。
所以「策略是否变化」是更经济的停机条件。
Q5 · 采样替代
MC 能否替代 DP 做评估?
能,代价是方差与样本效率:DP 一次备份用尽全部信息,MC 一次只用一条路径。
DP 是零方差理想版,MC/TD 是可执行现实版。
Q6 · 关键引理
最优算子的压缩证明靠哪一步?
|max f − max g| ≤ max |f − g|:把两个 max 的差,压到同一动作下的最大差。
两队最高分之差 ≤ 同一科目上的最大分差。
对照Q1 → 01·max 的代价;Q2 → 01·回报与价值;Q3 → 02·策略迭代;Q4 → 02·策略改进;Q5 → 03·GPI 骨架;Q6 → 03·定理兜底。答不上,回到那一幕重看。
六题全过,这套东西才真正属于你:每题都在问「为什么」,而不是「是什么」。
08 · 收束

把定理,翻译成手感

手算两状态、γ = 0.5:误差每轮恰好乘 γ,两个状态轮流前进误差 ×0.5 / 轮
误区七个坑一个根子:把 DP 的理想假设,当成 RL 的全部现实7 个坑 · 1 个根子
速查十三行一张表:定义 → 方程 → 解法 → 迭代 → 收敛 → 停机13 行 · 5 层
自测六道题,每道都在问「为什么」;答不上就回到对应那一幕6 道题
去路采样替代期望、函数逼近替代表、只算相关子集3 条路
全章一句话 一副骨架、一组定理、一条边界——动态规划给的是方法,不是答案。
下一站 · 第三章:蒙特卡洛与时序差分 把「期望」换成「采样」
片尾 · 出品说明
朝露记
强化学习 · 第二章 · 动态规划专题
朝露记出品
笔记梳理 讲解配音 动画编排
第二章 · 完结篇 下一站 · 蒙特卡洛与时序差分
解
00:00 / 09:50
空格 播放/暂停 ← → 切幕 R 重播 1–9 / 0 跳转