Bellman 方程的递推求解、最优策略提取、维度灾难的本质与应对思路
DP 算法从终端状态 $N$ 开始反向递推到初始时刻 $0$，在每个状态 $x_{k}$ 上只需求解一个单步优化问题。然而状态空间随维度指数增长——"维度灾难"是 DP 最大的实际障碍，催生了值函数近似、蒙特卡洛方法等现代强化学习技术。
上一讲我们学习了 Bellman 最优性原理——最优策略的子策略也是最优的。这个原理告诉我们：全局优化可以分解为一系列嵌套的单步优化。
为了把这个原理变成可计算的算法，定义最优值函数（optimal cost-to-go）如下：
特别地，在终端时刻 $N$：
终端代价只取决于最终状态
根据最优性原理，$J_{k}(x_{k})$ 可以通过 $J_{k+1}(x_{k+1})$ 计算出来。这就是我们将要推导的 DP 算法。
对于基本问题的每一个初始状态 $x_{0}$，最优代价 $J^{*}(x_{0})$ 等于 $J_{0}(x_{0})$，由以下从 $N-1$ 到 $0$ 反向递推的 DP 算法给出：
⚙️ DP 算法（Bellman 方程）
终端条件：
$$ J_{N}(x_{N}) = g_{N}(x_{N}) $$反向递推（$k = N-1, N-2, \dots, 0$）：
$$ J_{k}(x_{k}) = \min_{u_{k}} \mathbb{E}_{w_{k}} \left\{ g_{k}(x_{k}, u_{k}, w_{k}) + J_{k+1}(f_{k}(x_{k}, u_{k}, w_{k})) \right\} $$其中 $x_{k+1} = f_{k}(x_{k}, u_{k}, w_{k})$
进一步地，如果对每个 $x_{k}$ 和 $k$ 有：
则 $\pi^{*} = \{ \mu_{0}^{*}, \mu_{1}^{*}, \dots, \mu_{N-1}^{*} \}$ 就是最优策略
Bellman 方程将多步优化分解为单步优化。让我们逐项拆解：
即时代价（immediate cost）
在当前状态 $x_{k}$ 下采取控制 $u_{k}$，遇到扰动 $w_{k}$ 所付出的代价。
未来最优代价（optimal future cost）
从下一个状态开始的最优代价——由最优性原理保证其最优性。
最小化期望
对随机扰动取期望后，选择使"即时代价 + 未来代价"最小的控制。
为了更好地理解反向递推过程，我们用一个简单例子来说明。
海盗分钻石问题本质上就是 DP 算法的生动体现。让我们将两者对应起来：
| DP 算法 | 海盗分钻石 |
|---|---|
| $k = N$（终端） $J_{N}(x_{N}) = g_{N}(x_{N})$ |
只剩最后 1 个海盗时，他独吞 100 颗钻石 |
| $k = N-1$ $J_{N-1} = \min\{ \text{即时代价} + J_{N} \}$ |
4 号海盗知道自己如果死了 5 号独吞，所以给 5 号 0 颗即可 |
| $k = N-2$ $J_{N-2} = \min\{ \text{即时代价} + J_{N-1} \}$ |
3 号海盗知道如果自己死了 4 号得 100，所以花 1 颗收买 5 号 |
| $\dots$ | $\dots$ |
| $k = 0$ $J_{0}(x_{0})$ 就是整个问题的最优代价 |
海盗 1 得到 98 颗钻石——整个问题的"最优代价" |
这个对应关系说明：DP 算法本质上就是把上一讲学到的向后归纳思维，变成了一个可以在计算机上执行的数学递推公式。
在实际计算中，我们通常将每个时刻 $k$ 的 $J_{k}$ 存储为一个向量（或表），每个维度对应一个可能的状态值。当状态是离散的且取值有限时，这个表可以直接查：
每个状态 $x_{k}$ 对应一个最优值 $J_{k}(x_{k})$ 和一个最优控制 $u_{k}^{*}$
💡 DP 的"空间换时间"哲学
DP 的核心理念是：用空间换时间。原本我们需要考虑所有可能的路径组合（指数级），但 DP 通过存储每个状态的最优值函数，将复杂度降为 $O(N \times |S| \times |A|)$，其中 $|S|$ 是状态数，$|A|$ 是动作数。这正是 DP 高效的关键。
DP 算法完成后，我们不仅得到了最优代价 $J_{0}(x_{0})$，还得到了在每个状态下应该如何行动——即最优策略。
在反向递推的过程中，对每个 $k$ 和每个 $x_{k}$，记录使 Bellman 方程取到最小值的那一控制：
在实际运行中，我们不需要再解优化问题——只需查表：
设置终端代价函数：
$$ J_{N}(x_{N}) = g_{N}(x_{N}), \quad \forall x_{N} $$对 $k = N-1, N-2, \dots, 0$：
$$ J_{k}(x_{k}) = \min_{u_{k}} \mathbb{E}[g_{k} + J_{k+1}] $$对每个可能的状态 $x_{k}$ 计算。
记录每个状态下的最优决策：
$$ \mu_{k}^{*}(x_{k}) = \arg\min_{u_{k}} \mathbb{E}[g_{k} + J_{k+1}] $$运行时根据当前状态查表：
$$ u_{k} = \mu_{k}^{*}(x_{k}) $$📌 维度灾难
DP 算法理论上可以解决任何离散状态和离散控制的序贯决策问题，但状态空间的维度会导致计算量和存储量指数增长，这是 DP 在实际应用中的主要限制。
假设状态 $x_{k}$ 是一个 10 维向量，每一维离散化为 10 个值：
状态总数 = $\underbrace{10 \times 10 \times \dots \times 10}_{10\text{次}}$ = $10^{10}$ = 100 亿
这意味着我们需要存储 100 亿个 $J_{k}(x_{k})$ 值——显然不可行。而且对每个状态，还需要计算 $\min_{u_{k}}$，计算量更加巨大。
更一般地，如果状态是 $d$ 维向量，每维离散化为 $m$ 个值：
状态总数 = $m^{d}$
计算量和存储量都随维度 $d$ 指数增长：
| 维度 $d$ | 离散化水平 $m = 10$ | 内存需求（假设 8 bytes/状态） |
|---|---|---|
| 1 | $10$ | 80 bytes |
| 2 | $100$ | 800 bytes |
| 3 | $1{,}000$ | 8 KB |
| 4 | $10{,}000$ | 80 KB |
| 5 | $100{,}000$ | 800 KB |
| 6 | $1{,}000{,}000$ | 8 MB |
| 10 | $10^{10}$ | 80 GB |
当 $d = 10$ 时，即使每个状态只存一个浮点数，也需要 80 GB 的内存——这还只是存储一个时刻的值函数！
需要注意的是：维度灾难并不否定最优性原理的正确性。即使状态空间大到无法穷举，最优性原理本身始终成立。维度灾难只是说：如果我们试图用查表的方式精确求解 DP，计算代价可能高到不可接受。这就需要引入近似方法。
面对维度灾难，研究人员提出了多种应对策略。理解这些思路，能帮助你建立起从 DP 到现代强化学习（RL）的桥梁。
用参数化模型（如神经网络、线性基函数）来近似 $J_{k}(x_{k})$，而不是精确存储每个状态的值。这是深度强化学习的核心思路。
代表方法：DQN、DDPG、PPO
通过采样而非穷举来估计期望值。只访问"高概率"的状态路径，忽略极不可能的状态，从而大幅降低计算量。
代表方法：Monte Carlo Tree Search (MCTS)
将高维问题分解为若干低维子问题，利用问题的特殊结构（如稀疏性、可分性、对称性）来降低复杂度。
代表方法：分布式 DP、分层强化学习
对于线性系统 + 二次代价 + 高斯噪声（LQG），Bellman 方程有解析解——Riccati 方程。这正是 Kalman Filter 与 LQR 对偶的来源。
代表方法：离散 Riccati 方程递推
🔗 与 KF 的联系
Kalman Filter 本质上可以看作是 DP/Bellman 方程在线性高斯系统下的特例。KF 的协方差更新方程（Riccati 方程）与 LQR 的 Riccati 方程互为对偶关系。这正是我们把 DP 放在 KF 系列最后的原因——它们是同一个理论框架的不同侧面。
为什么 DP 算法是从 $k = N-1$ 反向递推到 $k = 0$，而不是从 $k = 0$ 正向递推到 $k = N-1$？正向递推会有什么问题？
反向递推是 DP 算法的核心，原因在于：
正向递推通常需要知道所有可能的路径，然后比较这些路径的代价——这本质上就是穷举法，复杂度为 $O(|A|^{N})$，而不是 DP 的 $O(N \cdot |S| \cdot |A|)$。
假设一个简单 DP 问题：终端时刻 $N=3$，状态空间 $\{A, B, C\}$，控制空间 $\{\alpha, \beta\}$。终端代价为：
$$ J_{3}(A) = 10, \quad J_{3}(B) = 20, \quad J_{3}(C) = 30 $$在 $k=2$ 时刻，状态 $A$ 下：
请计算 $J_{2}(A)$ 和 $\mu_{2}^{*}(A)$。
应用 Bellman 方程（本题中无随机扰动，$\mathbb{E}$ 退化为确定性）：
对于 $\alpha$ 选项：
$J_{2}^{\alpha}(A) = g_{2}(A, \alpha) + J_{3}(B) = 5 + 20 = 25$
对于 $\beta$ 选项：
$J_{2}^{\beta}(A) = g_{2}(A, \beta) + J_{3}(C) = 2 + 30 = 32$
取最小值：$J_{2}(A) = \min\{25, 32\} = 25$
最优决策：$\mu_{2}^{*}(A) = \alpha$（因为 $\alpha$ 的代价 25 小于 $\beta$ 的代价 32）
假设一个无人机路径规划问题，状态空间包含位置 $(x, y, z)$ 和速度 $(v_{x}, v_{y}, v_{z})$，每维离散化为 50 个值。
(a) 状态空间的总维度是多少？总状态数是多少？
(b) 如果每个状态的 $J_{k}$ 值用 8 bytes 的浮点数存储，仅存储一个时刻的值函数需要多少内存？
(c) 如果时间步长 $N = 100$，存储所有时刻的值函数需要多少内存？
(a) 状态维度 $d = 6$（3 个位置 + 3 个速度）。每个维度离散化为 50 个值，总状态数 = $50^{6} = 15{,}625{,}000{,}000 \approx \mathbf{1.56 \times 10^{10}}$（约 156 亿个状态）。
(b) 每个状态 8 bytes：$1.56 \times 10^{10} \times 8 \approx 125$ GB。仅存储一个时刻就需要 125 GB 内存。
(c) $N = 100$ 个时刻：$125 \times 100 = 12{,}500$ GB ≈ 12.5 TB。这远远超出了普通计算机的存储能力。
这个例子说明：即使是一个看似简单的问题（6 维状态），精确 DP 查表法也是不可行的。这也是为什么现代强化学习需要使用值函数近似等方法。
施老师大课堂 · 研讨会系列 KF L19(2/2) · DP 算法与维度灾难
板书来源：KF L19 · 研讨会系列 24 · 施凌老师