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

从无穷回报
到一组方程

一条轨迹的回报是无穷和,既算不完也用不上。动态规划说:回报的期望——也就是价值——其实是一组有限方程的解。中间隔着四步——定位、门票、期望方程、最优方程。

① DP 的位置 ② 三张入场券 ③ 贝尔曼期望方程 ④ 贝尔曼最优方程
一句话DP 把算不完的无穷,换成解得动的有限;代价是:必须先有环境说明书。
本片要回答的一件事
Gt = Σk=0∞ γk Rt+k+1
无穷项 · 无法直接计算
①定位:有模型 → 规划;没模型 → 采样
②门票:模型已知 · 马尔可夫 · 有限 MDP
③期望方程:线性 → 可求逆,但大规模时算不动
④最优方程:非线性 → 一般无闭式解,靠迭代
01 · 一张图定位

DP 不是万能钥匙,它是「有说明书」的那条路

① 定位› ② 门票› ③ 期望方程› ④ 最优方程
贝尔曼方程 长期价值的递归结构 手里有什么? 需要完整模型 p(s′,r | s,a) 每次备份都要对全部后继求和 只需要采样 (s, a, r, s′) 用真实走一步代替求和 规划 / DP 模型上做数学 无模型学习 靠真实体验修正 策略迭代 价值迭代 MC TD DP 是理论原型与正确性基准 TD 的目标、Q-learning 收敛的理由、DQN 的 Bellman 损失,都从这组方程掉出来
1
每一次更新都在算期望
要对所有后继状态求和,必须知道每一项的概率与权重。没有模型,连该加哪几项都不知道。
2
它不与环境交互
DP 只在模型上做数学,本质是一台只靠模型、一步步向前展望的计算器。
3
它的地位:正确性基准
它未必能直接上机器人,但所有价值型算法都以它为标准答案。先有基准,才谈近似。
分水岭有无环境模型,决定了你是在推演还是在试错;DP 站在推演这一侧。
02 · 三张入场券

缺一张,就得换工具

① 定位› ② 门票› ③ 期望方程› ④ 最优方程
必备
门票 01
模型已知
能对任意 (s, a) 算出 p(s′, r | s, a)
用在:贝尔曼备份里的 Σ 求和项
缺了→ 算不出期望,只能改用采样(MC / TD)
必备
门票 02
马尔可夫性
下一步只取决于当前的状态和动作,与「怎么来的」无关
用在:价值函数只写 v(s),不必拖着历史
缺了→ 状态不充分,要补信念状态或历史特征
必备
门票 03
有限 MDP
|S| < ∞,|A| < ∞,|R| < ∞,可以逐个枚举
用在:外层 for s in S 能扫完
缺了→ 连续状态要离散化,或用函数逼近
附加条件 折扣 γ < 1,或在策略 π 下从任何状态出发必然终止(二者满足其一即可):前者靠 γk → 0 把远处抹平,后者靠回合本身有限; (γ < 1、|R| ≤ Rmax 时)|Gt| ≤ Rmax / (1 − γ) γ < 1 时贝尔曼算子在最大范数下是 γ-压缩,迭代必收敛;γ = 1 时由「必然终止」保证 vπ 存在唯一、迭代收敛。
缺 模型
→ 采样
MC / TD:用一步真实转移,代替对 p 的求和
缺 马尔可夫
→ 补状态
信念状态、历史特征:把有用的历史塞进 S
缺 有限性
→ 离散化 / 函数逼近
离散化:把连续状态切成格子;逼近:不存表,存参数
直觉马尔可夫性 = 记账只记余额:当前余额已经把过往流水里有用的信息压缩干净,算下一步不必翻旧账。
03 · 地基

先定义「好」是什么,再谈怎么算

① 定位› ② 门票› ③ 期望方程› ④ 最优方程
回报 Return Gt = Rt+1 + γ Rt+2 + γ2 Rt+3 + … = Σk=0∞ γk Rt+k+1 γ ∈ [0, 1] 是折扣因子:γ = 0 只看眼前,γ → 1 越看越远;γ < 1 且奖励有界时,|Gt| ≤ Rmax/(1−γ)。
γ = 0
近视眼:只看下一步奖励
γ = 0.9
有效视野约 10 步(1/(1−γ)),常见取值 0.9~0.99
状态价值 STATE VALUE
vπ(s) = Eπ[ Gt | St = s ]
「我现在站在 s,并且以后一直按策略 π 行动,平均能拿到多少总回报?」
动作价值 ACTION VALUE
qπ(s, a) = Eπ[ Gt | St = s, At = a ]
「站在 s,先强制做 a,之后按 π 行动,平均能拿到多少?」—— 多了一个「先试试这个动作」的维度。
互推 vπ(s) = Σa π(a|s) qπ(s, a) ⇄ qπ(s, a) = Σs′,r p(s′, r | s, a) [ r + γ vπ(s′) ] 给定 π 由 q 得 v,给定模型由 v 得 q:一个先平均动作,一个先锁定动作
为什么需要两个?没有模型时,光有 v 选不出动作(不知道每个动作通向哪);有模型时也得再往前展开一步,而 q 已经把这一步提前存好了。
03 · 关键推导

只有一招:把回报拆成「第一步 + 剩下的」

① 定位› ② 门票› ③ 期望方程› ④ 最优方程
定义 vπ(s) = Eπ[ Gt | St = s ] 起点:价值定义本身,里面藏着无穷和
拆分 Gt = Rt+1 + γ Gt+1 关键一步:等号,没有任何近似
代入 = Eπ[ Rt+1 | St = s ] + γ Eπ[ Gt+1 | St = s ] 期望的线性性:和的期望 = 期望的和
按策略 = Σa π(a|s) Eπ[ Rt+1 + γ Gt+1 | St = s, At = a ] 全概率:先按策略抽动作 a ~ π(·|s),两项合并展开
按模型 = Σa π(a|s) Σs′,r p(s′, r | s, a) [ r + γ Eπ[Gt+1 | St+1 = s′] ] 再按模型抽后继 (s′, r) ~ p(·|s, a);马尔可夫性让条件只剩 St+1 = s′
自指 [ … ] = vπ(s′) 括号里那一项,按定义就是下一状态的价值
贝尔曼期望方程 vπ(s) = Σa π(a|s) Σs′,r p(s′, r | s, a) [ r + γ vπ(s′) ]
线性性:期望可以按项拆开 全概率:策略一次 + 模型一次 马尔可夫性:给定 St+1,Gt+1 与更早的历史无关
换来什么无穷求和消失了:每个状态写一遍,就是 |S| 个方程、|S| 个未知数 —— 一个有限线性方程组。
03 · 从方程到矩阵

期望版是线性的,所以它有闭式解

① 定位› ② 门票› ③ 期望方程› ④ 最优方程
矩阵形式 vπ = Rπ + γ Pπ vπ Pπ[s, s′] = Σa π(a|s) p(s′|s,a),Rπ(s) = Σa π(a|s) Σs′,r p(s′,r|s,a) r:每个状态一条方程,合起来就是线性方程组。
闭式解 vπ = ( I − γ Pπ )−1 Rπ 移项、求逆:Pπ 是随机矩阵、谱半径为 1,故 γ < 1 时 I − γPπ 一定可逆,理论上一次矩阵求逆就解完了。
直接求逆 · 一次算完
计算量O(|S|³)
内存|S|²
代价不可行
|S| = 106 时,求逆约需 1018 次运算,外加约 8 TB 的稠密矩阵(双精度)。改用 LU 分解解方程量级不变,单机上不现实。
迭代扫描 · 反复扫表
每轮O(|S|²·|A|)
内存|S|(值表)
性质可异步
只存每个状态一个数字(模型另计),可异步、只扫「脏」状态;约 ln(1/ε)/(1−γ) 轮达到精度 ε。大规模问题上基本不直接求逆。
但是闭式解只在「策略评估」这种线性场景存在。一旦出现 max,线性就没了,一般也就没有闭式解 —— 这正是下一幕。
04 · 最优性

把「按策略平均」换成「挑最好的那个」

① 定位› ② 门票› ③ 期望方程› ④ 最优方程
定义 v*(s) = maxπ vπ(s)  ,  q*(s, a) = maxπ qπ(s, a) 在所有策略里取「每个状态都最好」的那个:有限 MDP 一定存在一个策略在每个状态上同时最优,所以逐状态取最大是有意义的;而且它可以取成确定性的。
期望版 vπ(s) = Σa π(a|s) Σs′,r p(s′, r | s, a) [ r + γ vπ(s′) ]
↓ 最优策略对 v*(或 q*)贪心:把「按 π 加权平均」换成「挑最好的动作」
最优版 v*(s) = maxa Σs′,r p(s′, r | s, a) [ r + γ v*(s′) ]
v* 版本:max 选的是本步动作 a(在期望外部)
先挑动作,再让环境决定后果:maxa Σs′,r p(s′,r|s,a) [ r + γ v*(s′) ]。这就是「站在 s 就选最好动作」。
q* 版本:max 选的是下一步动作 a′(在期望内部)
先到下一状态,再挑动作:q*(s,a) = Σs′,r p(s′,r|s,a) [ r + γ maxa′ q*(s′,a′) ]。此时 s′ 已经看到了,先看再选是合法的;两种写法等价。
两式等价 差别只在 max 的对象:v* 版挑本步动作(max 在外),q* 版挑下一步动作(max 在内)——两次 max 不是一回事,别混。
04 · 核心难点

max 为什么「杀死」了闭式解

① 定位› ② 门票› ③ 期望方程› ④ 最优方程
期望:线性
Σa π(a|s) · ( … )
可以提出来,可以写成矩阵乘法 Pπ v → 方程可移项、可求逆。
max:非线性
maxa ( … )
没有固定的矩阵表示:哪个动作胜出取决于 v 本身,系数矩阵随 v 变,无法一次移项求逆。线性运算能与期望交换顺序,max 不能:max E ≤ E max。
顺序不能换 · 两动作算例 maxa E[ Xa ] ≤ E[ maxa Xa ](一般取不到等号)
s a₁ a₂ r = 1 · p = 0.5 r = 0 · p = 0.5 r = 0.6 · p = 1 期望 0.5 期望 0.6 本步动作必须在随机结果揭晓之前选定
先选再赌
max 在期望外
0.6 max(0.5, 0.6):你只能赌一次
先看结果再选
(作弊)
0.8 0.5×max(1, 0.6) + 0.5×max(0, 0.6) = 0.8
差在哪 0.6 ≠ 0.8:信息顺序不同,答案就不同。本步动作只能先选再赌;下一步的动作可以等看到 s′ 再选——这正是 q* 里的 max。
所以一般没有一步到位的闭式解,通常迭代逼近:知道最优策略,方程就又线性了;可策略正是要求的。γ < 1 时最优算子是 γ-压缩,保证唯一不动点 v*、值迭代必收敛(Banach 不动点定理);线性规划、策略迭代(有限步终止)也能精确求解,只是每步都要解大规模线性问题。
04 · 收束

解出 v*,策略只是一步展望(有 q* 就是查表)

① 定位› ② 门票› ③ 期望方程› ④ 最优方程
由最优价值反解策略 π*(s) = argmaxa Σs′,r p(s′, r | s, a) [ r + γ v*(s′) ] = argmaxa q*(s, a) v* 已经把长期后果全部折算进来,所以只看一步就是长期最优;而 DP 模型已知,不必靠试错收集信息,也就没有「探索–利用」的两难。
1
无穷 → 有限
贝尔曼期望方程把长度无穷的回报,压成 |S| 个线性方程;这是 DP 能算的核心原因。
2
平均 → 最大
贝尔曼最优方程把 Σaπ 换成 maxa;线性变非线性,矩阵求逆失效。
3
找策略 → 解方程
DP 的终极形态是数值问题:猜初值、反复备份、逼近不动点。
一条轨迹 → 一组方程 → 一台迭代机器
下一站:把这台机器拆开 —— 策略评估 · 策略改进 · 策略迭代 · 价值迭代
片尾 · 出品说明
朝露记
强化学习 · 第二章 · 动态规划专题
朝露记出品
笔记梳理 讲解配音 动画编排
第二章 · 01 完 下一站 · 从一组方程到一台迭代机器
解
00:00 / 10:14
空格 播放/暂停 ← → 切幕 R 重播 1–9 / 0 跳转