强化学习 · 动态规划 · 专题讲解 01
从无穷回报
到一组方程
一条轨迹的回报是无穷和,既算不完也用不上。动态规划说:回报的期望——也就是价值——其实是一组有限方程的解。中间隔着四步——定位、门票、期望方程、最优方程。
① DP 的位置
② 三张入场券
③ 贝尔曼期望方程
④ 贝尔曼最优方程
一句话DP 把算不完的无穷,换成解得动的有限;代价是:必须先有环境说明书。
本片要回答的一件事
Gt = Σk=0∞ γk Rt+k+1
无穷项 · 无法直接计算
①定位:有模型 → 规划;没模型 → 采样
②门票:模型已知 · 马尔可夫 · 有限 MDP
③期望方程:线性 → 可求逆,但大规模时算不动
④最优方程:非线性 → 一般无闭式解,靠迭代
01 · 一张图定位
DP 不是万能钥匙,它是「有说明书」的那条路
① 定位›
② 门票›
③ 期望方程›
④ 最优方程
1每一次更新都在算期望
要对所有后继状态求和,必须知道每一项的概率与权重。没有模型,连该加哪几项都不知道。
2它不与环境交互
DP 只在模型上做数学,本质是一台只靠模型、一步步向前展望的计算器。
3它的地位:正确性基准
它未必能直接上机器人,但所有价值型算法都以它为标准答案。先有基准,才谈近似。
分水岭有无环境模型,决定了你是在推演还是在试错;DP 站在推演这一侧。
① 定位›
② 门票›
③ 期望方程›
④ 最优方程
必备
门票 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
缺 有限性
→ 离散化 / 函数逼近
离散化:把连续状态切成格子;逼近:不存表,存参数
直觉马尔可夫性 = 记账只记余额:当前余额已经把过往流水里有用的信息压缩干净,算下一步不必翻旧账。
① 定位›
② 门票›
③ 期望方程›
④ 最优方程
回报 Return
Gt = Rt+1 + γ Rt+2 + γ2 Rt+3 + … = Σk=0∞ γk Rt+k+1
γ ∈ [0, 1] 是折扣因子:γ = 0 只看眼前,γ → 1 越看越远;γ < 1 且奖励有界时,|Gt| ≤ Rmax/(1−γ)。
γ = 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 ](一般取不到等号)
先选再赌
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 完
下一站 · 从一组方程到一台迭代机器
解