Bellman 最优性原理的严格表述、向后归纳（Backward Induction）思维与海盗分钻石经典案例
最优策略的任何一段子策略也是最优的——这就是 Bellman 最优性原理。本章用海盗分钻石这个博弈论经典案例，让你直观感受"从终局倒推"的向后归纳思维，这是 DP 算法能够将多步决策分解为单步优化的根本原因。
在开始之前，先快速回顾动态规划的基本问题框架。一个离散时间动态系统由以下方程描述：
其中 $x_{k}$ 为状态，$u_{k}$ 为控制量，$w_{k}$ 为随机扰动
我们的目标是极小化期望总代价：
策略（policy）定义为各时刻控制律的序列：
基本问题可以简化为：在所有可能的策略中找到使总期望代价最小的最优策略 $\pi^{*}$。
Bellman 最优性原理是动态规划的基石。让我们从直观理解进入严格的数学表述。
🏆 Bellman 最优性原理（直观表述，1957）
一个最优策略具有这样的性质：无论初始状态和初始决策如何，剩余的决策必须构成一个以第一个决策产生的状态为初始状态的最优策略。
设 $\pi^{*} = \{ \mu_{0}^{*}, \mu_{1}^{*}, \dots, \mu_{N-1}^{*} \}$ 是基本问题的一个最优策略。假定在 $\pi^{*}$ 下，某个状态 $x_{i}$ 以正概率出现。
考虑一个子问题：我们在时刻 $i$ 处于状态 $x_{i}$，希望最小化从时刻 $i$ 到 $N$ 的代价：
最优性原理指出：截断后的策略 $\{ \mu_{i}^{*}, \mu_{i+1}^{*}, \dots, \mu_{N-1}^{*} \}$ 对这个子问题也是最优的。
因为代价函数是可加的（分离性）。未来代价只依赖于当前状态和未来决策，不依赖于历史——这就是马尔可夫性质。
最优性原理要求截断后的子策略对所有可能的状态 $x_i$ 都是最优的。如果某些状态在最优策略下不会出现，我们可以任意定义那些状态的策略。
最优性原理的最经典直观就是最短路径问题：
🌰 从香港到北京的最短路径
假设从香港（HK）到北京（BJ）有一条最短路径，它途经某座城市 $X$。那么从 $X$ 到北京的那一段路径，一定也是从 $X$ 到北京的所有路径中最短的。
反证法：如果从 $X$ 到北京有一条更短的路径，那么把它替换进来，就能得到一条从 HK 到 BJ 的更短路径——与"最短"矛盾。
这个直觉非常朴素，但它的力量是巨大的——它告诉我们不需要穷举所有可能的路径组合，而可以通过"倒着推"的方式逐段构建最优解。
海盗分钻石问题是博弈论中的经典，也是理解 backward induction（向后归纳）的最佳入口。这个问题完美展现了最优性原理在序贯决策中的应用。
🏴☠️ 海盗分钻石
场景：5 个海盗抢到了 100 颗钻石（形状、大小、颜色完全一样，价值相同）。他们需要决定如何分配。
假设：
我们从最简子问题开始，逐步向复杂情况推导——这正是最优性原理的应用！
此时 4 号提出方案。他只需要自己一票（50%）即可通过。因此他会提出：
4 号：100 颗，5 号：0 颗
4 号自己投票同意（1 票 = 50%），方案通过。5 号得到 0 颗。
3 号知道：如果自己的方案被否，他会死，进入"情况 A"——那时 4 号得 100 颗，5 号得 0。
3 号需要拉至少 1 票（加上自己共 2 票 = 66.7%）。给 5 号 1 颗（比情况 A 的 0 颗好），5 号就会同意。
3 号：99 颗，4 号：0 颗，5 号：1 颗
3 号和 5 号同意（2 票 = 66.7%），方案通过。
2 号知道：如果自己被否，会进入"情况 B"——那时 3 号得 99，4 号得 0，5 号得 1。
2 号需要拉至少 1 票。给 4 号 1 颗（比情况 B 的 0 颗好），4 号就会同意。
2 号：99 颗，3 号：0 颗，4 号：1 颗，5 号：0 颗
2 号和 4 号同意（2 票 = 50%），方案通过。
1 号知道：如果自己被否，会进入"情况 C"——那时 2 号得 99，3 号得 0，4 号得 1，5 号得 0。
1 号需要拉至少 2 票（加上自己共 3 票 = 60%）。对比情况 C 的结果：
1 号：98 颗，2 号：0 颗，3 号：1 颗，4 号：0 颗，5 号：1 颗
1 号、3 号、5 号同意（3 票 = 60%），方案通过！
上述推理可以用一张表格紧凑地展示。每一行代表当前提议者的情况，数字表示该提议者分配给每个海盗的钻石数：
| 提议者 | 海盗 1 | 海盗 2 | 海盗 3 | 海盗 4 | 海盗 5 | 同意票数 |
|---|---|---|---|---|---|---|
| 海盗 5（只剩 1 人） | — | — | — | — | 100 | — |
| 海盗 4（2 人） | — | — | — | 100 | 0 | 1/2 (50%) |
| 海盗 3（3 人） | — | — | 99 | 0 | 1 | 2/3 (66.7%) |
| 海盗 2（4 人） | — | 99 | 0 | 1 | 0 | 2/4 (50%) |
| 海盗 1（5 人）— 最终答案 | 98 | 0 | 1 | 0 | 1 | 3/5 (60%) |
💡 关键洞察
海盗 1 最终拿到 98 颗钻石——几乎全部！看似最危险的提议者反而获得了最大收益。这就是向后归纳的力量：从终局状态逐级倒推，每个节点只考虑"如何用最小代价争取足够票数"。
这个过程本质上就是 DP 算法：从终端条件（只剩 1 个海盗）开始，反向递推每一阶段的最优策略。
海盗分钻石问题展示了向后归纳（backward induction）的核心思维，这与 DP 算法完全一致：
从问题的最简"终局"状态开始。在海盗问题中，就是只剩 1 个海盗的情况。
对应 DP：设 $J_{N}(x_{N}) = g_{N}(x_{N})$
在每一步，向前看一步——知道下一步的结果后，当前步的最优选择就变成了一个"单步优化"。
对应 DP：$J_{k} = \min\{ \text{即时代价} + J_{k+1} \}$
记录在每个状态下最优的决策（给谁多少钻石）。
对应 DP：提取 $\mu_{k}^{*}(x_{k})$
回到初始状态，按提取的策略执行。海盗 1 提出 (98, 0, 1, 0, 1)，获得通过。
对应 DP：查表执行最优控制
🧠 与最优性原理的联系
海盗分钻石的完整推理过程，就是对最优性原理最生动的诠释：
最优性原理并非天然成立，它依赖于两个关键条件：
代价函数必须是各阶段代价之和（或可分解为相加形式）：
$$ J = g_{N}(x_{N}) + \sum_{k=0}^{N-1} g_{k}(x_{k}, u_{k}, w_{k}) $$如果代价函数不是可加的（如存在跨阶段约束或乘积形式的代价），最优性原理可能不成立。
系统的未来演化只依赖于当前状态和当前决策，不依赖于历史：
$$ x_{k+1} = f_{k}(x_{k}, u_{k}, w_{k}) $$如果系统的未来依赖于完整历史（如 $x_{k+1}$ 依赖 $x_{k-1}$），则不能直接应用 DP。
📌 结论
在满足可加性和马尔可夫性的前提下，Bellman 最优性原理保证：多步决策问题可以分解为一系列单步优化，且这种分解不会丢失全局最优性。这正是动态规划能够在无数领域（控制理论、强化学习、博弈论、运筹学、经济学）发挥作用的根本原因。
用你自己的话解释 Bellman 最优性原理。为什么在 DP 中它被称为"最优策略的子策略也是最优的"？
Bellman 最优性原理指出：如果 $\pi^{*} = \{ \mu_{0}^{*}, \mu_{1}^{*}, \dots, \mu_{N-1}^{*} \}$ 是原始问题的最优策略，那么对于任意时刻 $i$ 和以正概率出现的状态 $x_{i}$，截断策略 $\{ \mu_{i}^{*}, \dots, \mu_{N-1}^{*} \}$ 也一定是子问题（从 $x_{i}$ 出发最小化代价）的最优策略。
换句话说：不能存在一个策略，它在前 $i$ 步与 $\pi^{*}$ 相同，但从 $i$ 步以后更优——因为我们总可以用更好的子策略替换，从而得到比 $\pi^{*}$ 更优的全局策略，这与 $\pi^{*}$ 的全局最优性矛盾。
海盗分钻石问题中，如果将规则改为"严格超过 50% 同意"（即需要 >50% 而非 ≥50%），重新求解向后归纳。海盗 1 的最优分配方案是什么？
逐步推理：
现在假设有 6 个海盗和 100 颗钻石，规则为原规则（≥50% 同意）。请从后向前推导第 1 个海盗的最优分配方案，并计算出他能获得多少颗钻石。
逐步向后归纳：
答案：海盗 1 获得 98 颗钻石，分配方案为 (98, 0, 1, 0, 1, 0)。
施老师大课堂 · 研讨会系列 KF L19(1/2) · 最优性原理与海盗分钻石
板书来源：KF L19 · 研讨会系列 24 · 施凌老师