原理层 T19 / 27 · 决策与优化
MDP 的数学构造:一条公理值多少钱
整个强化学习压在一条公理上:未来只依赖当前状态。Bellman 最优性原理可以用反证法严格证明——但前提是「状态」真的装下了全部相关信息。
一句话结论
马尔可夫性不是描述而是假设,它的回报是:最优策略可以分解为「当前步选好 + 剩余子问题也最优」(Bellman 1957 原理,可反证法证明)。状态设计漏信息时,这条原理的适用前提就没了——这是真机项目翻车的第一数学原因。
TD、Q-learning、值迭代全都默认贝尔曼方程成立。贝尔曼方程成立依赖马尔可夫性。这一篇把「为什么五元组这么定义」「最优性原理为什么对」「状态漏信息会发生什么」一次讲清——它是 /fund/mdp/ 的地基篇。
为什么需要它
回到定义本身。MDP 五元组 (S, A, P, R, γ) 里,真正承重的是 P:p(s'|s,a) 只依赖当前状态-动作对,与历史无关。这一条为什么值得单独写进定义?因为它是后面一切「递归」的源头——贝尔曼方程把「未来的总账」写成「当前步 + 下一状态的总账」,只有未来不记得历史时这个递归才闭合。
反例立刻有:机器人只观测到关节角度,但货物的实际位置(未观测)影响动力学。此时「未来」依赖隐藏的货物位置,p(s'|s,a) 按可见状态写不出来——同一个可见状态对应的未来分布随隐藏状态变化。这不是近似误差,是模型本身写错了。
Bellman 在 1957 年的论文里把「最优策略的结构」写成了原理:最优策略有如下性质——无论初始状态和初始决策是什么,剩余的决策必须构成「相对初始决策所成状态」的最优策略。这句话可以反证法证明,下面完整给出。
定义
定义 7.1 MDP 五元组
(S, A, P, R, γ):状态集 S、动作集 A、转移核 P(马尔可夫的)、奖励函数 R(可一般化为依赖 s')、折扣 γ∈[0,1)。策略 π 把状态映射到动作(或动作分布)。
为什么这样定每个部件都有明确的承重位置:S/A 定义问题的词汇表;P 承载马尔可夫假设;R 定义「好」;γ 既定义时间偏好又(T5)保证收敛。少任何一个,问题都表述不成。
定义 7.2 回报与值函数
轨迹的折扣回报 G = Σt≥0 γ^t r_t。值函数 V^π(s) = E_π[G | s_0=s]——期望按策略 π 与转移核 P 诱导的轨迹分布取(T1 的测度、T2 的期望、T3 的条件期望在这里会合)。最优值 V*(s) = max_π V^π(s)。
为什么这样定注意 V^π 定义里「条件于 s」——这正是 T3 的条件期望;「取期望」的合法性由 T2 的可积性(γ<1 时折扣和有界)保证。原理层的价值就是让你看到这些引用链是闭合的。
定理与证明
定理 7.1 Bellman 最优性原理(反证法证明)
若 π* 是最优策略,则它在每个状态上选的动作,其「即时奖励 + 后继状态的最优值」不劣于任何其他动作。等价地:最优策略 = 贪心于 V* 的(任意一个)策略。
证
反证。设 π* 最优,但在状态 s 选了动作 a₁,而存在动作 a₂ 使:r(s,a₂) + γE[V*(s')] > r(s,a₁) + γE[V*(s')],其中 s' 按 a₂ 的转移取。
构造新策略 π̃:第一步在 s 用 a₂,之后完全照抄 π*(从 a₂ 导致的新状态开始)。
由归纳假设「π* 在一切状态最优」(对时域或折扣深度归纳,γ<1 时用极限论证收尾):Vπ̃(s') ≤ V*(s') 对一切 s'。于是:
所以 Vπ̃(s) > Vπ*(s),与 π* 最优矛盾。∎
注证明用到的马尔可夫性藏在哪:「之后照抄 π*」这个构造合法,要求 a₂ 之后的子问题与「怎么到达新状态」无关——这正是马尔可夫性。历史依赖的问题里这个构造不成立(新策略的状态没定义好),最优性原理随之失效。这行注释就是「一条公理值多少钱」的账单。
定理 7.2 贝尔曼最优方程
V* 是贝尔曼最优算子的不动点:V*(s) = max_a Σs' p(s'|s,a)[r + γV*(s')]。由 T5 定理 5.2(γ-压缩)+ 定理 5.1(不动点存在唯一),这个方程有唯一解。
证
存在唯一性由 T5 完成(压缩映射原理),此处只剩一件事:确认 V*(最优值的定义)确实是不动点。这由定理 7.1 的贪心结构 + 归纳得到——「最优 = 一步贪心 + 剩余最优」翻译成方程就是不动点方程。∎
注逻辑链完整版:马尔可夫性 → 最优性原理(本篇)→ 贝尔曼方程 → 压缩性(T5)→ 值迭代收敛。链条上任何一环断了,后面的算法都没有保证。这四篇(T5/T7 + /fund/ 两篇)合起来才是「值迭代为什么收敛」的完整答案。
手算一遍
两状态 MDP:状态 1 每步自环奖励 1(唯一动作);状态 0 两个动作——a 留在 0 且奖励 0,b 去状态 1 且奖励 0.5。γ=0.9。手算 V* 与最优策略。
- 状态 1 自环:V*(1) = 1 + 0.9·V*(1) → V*(1) = 1/0.1 = 10(等比级数求和,T2 例题同款)。
- [object Object]
- 比较:若选 a 则 V*(0)=0.9V*(0) 只能解出 0(且 9.5 > 0.9×任何 ≤10 的数);选 b 得 9.5。验证一致性:0.9×9.5 = 8.55 < 9.5 ✓ 选 b 确实更优(自洽)。
- V* = (9.5, 10)。策略:在 0 选 b(去状态 1),在 1 停留。
V*(0)=9.5, V*(1)=10。这道题的检查习惯值得养成:解出不动点后要验证「max 确实取到了假设的那个动作」(自洽性检查)——漏掉它的话,解出「假不动点」(max 取到另一个分支)的情形发现不了。
实跑一遍
数字出处
上面两状态 MDP 的值迭代实测(γ=0.9,从 V₀=0):
- 值迭代收敛到 V* = [9.5000, 10.0000](理论值逐位一致)
- γ=1 对照实验:状态 1 自环每步奖励 1,迭代 30 步后 V=30 且线性增长——无折扣时不动点不存在(T5 定理 5.2 的 γ<1 前提失效)
映射回强化学习
| 这里的对象 | RL 里的对应物 | 站内用法 |
|---|---|---|
| 马尔可夫性 | state 必须装下影响未来的全部信息——sensor 设计的第一原则 | 用法 → |
| 最优性原理 | 「一步贪心+子问题最优」是 Q-learning max 算子的合法性 | 用法 → |
| γ<1 | 折扣不只是偏好设定,是 V* 存在的前提 | 用法 → |
| 状态漏信息 | state aliasing:可见状态相同、未来分布不同 → V 没定义好 | 用法 → |
边界:这一篇停在哪里
本篇停在哪里:POMDP(部分可观测的严格理论)、连续时间最优控制(HJB 方程)、半马尔可夫过程,都不讲。诚实声明:真实机器人几乎总是 POMDP,实践中用「堆观测让马尔可夫性近似成立」绕过——要意识到这是绕过。
自测 4 题
全是手算和「找证明错在哪」类题目,不出背诵题。答不上来回到对应小节。
01最优性原理的反证法证明里,「构造 π̃ 照抄 π*」这一步用到了什么?
马尔可夫性。只有未来与历史无关,「从新状态开始照抄」才有定义良好的值。历史依赖问题(POMDP/非马尔可夫)里此构造失败——新策略的价值无法仅从可见状态算出。
02γ=1、每步奖励 1 的自环,贝尔曼方程 V = 1 + V 有解吗?
没有有限解(1+V=V 导出 1=0)。这不是数值发散而是方程无解:奖励流不衰减、无终止,总回报无穷。三种修法:折扣 γ<1、给问题加终止、换成平均奖励准则(每步平均奖励 1,这有良定义)。
03状态设计只给关节角度,货物位置影响动力学。写出会发生什么。
可见状态 s 处的条件分布 p(s'|s,a) 不再唯一(取决于隐藏的货物位置)——转移核按五元组写不出来,V(s)=E[G|s] 的「E」缺一个确定的分布。现象上:同状态不同行为、训练曲线震荡。修法:把货物位姿放进观测。
04贝尔曼最优方程为什么「恰好」是值迭代的不动点方程?两件事的逻辑顺序是什么?
顺序:马尔可夫性 → 最优性原理(结构定理)→ 把结构翻译成方程(不动点形式)→ T5 证明不动点可迭代逼近。不是「值迭代碰巧收敛」,而是「方程的可解性来自压缩性,压缩性来自 γ<1,γ 的意义来自构造」。