《强化学习与最优控制》【学习笔记04】动态规划的丰富实例：从最短路径到部分可观察

《强化学习与最优控制》第 1.3 节 · 例子、变形和简化

Bertsekas 用一整节的实例来展示 DP 框架的普适性。这些例子不是可有可无的装饰——它们帮助建立直觉，并且许多后续的近似方法正是从这些具体问题中自然生长出来的。

一、最短路径问题

最短路径是 DP 的"Hello World"。

给定一个有向图，边 $(i,j)$ 的长度为 $a_{ij}$，求从节点 $s$ 到目的地 $t$ 的最短路径。

DP 建模

• 状态 $x_k$：第 $k$ 步所在的节点
• 控制 $u_k$：选择下一个要去的节点
• 系统方程：$x_{k+1} = u_k$（下一节点就是选择的节点）
• 费用：$g_k(x_k, u_k) = a_{x_k, u_k}$，终止费用 $g_N(t) = 0$

DP 算法

$$J_k^*(i) = \min_{j} \left[ a_{ij} + J_{k+1}^*(j) \right]$$

从目的地反向计算：$J_N^*(t) = 0$，逐步向前推。

学习心得：最短路径问题展示了 DP 的一个重要特性——终止条件。当 $J_k^*(i)$ 不再随 $k$ 变化时（即 $J_{k-1}^*(i) = J_k^*(i)$），算法可以提前终止。这是因为已经找到了所有节点的最优展望费用。

二、旅行商问题（TSP）

TSP 是经典的 NP-hard 问题，Bertsekas 展示了如何将其转化为 DP。

DP 建模

• 状态：已访问城市的序列（如 “ACDB” 表示已按序访问 A→C→D→B）
• 控制：选择下一个要访问的城市
• 阶段费用：两城市间的旅行时间
• 终止费用：从最后一个城市返回出发城市的旅行时间

维数灾难

$N$ 座城市的 TSP，第 $k$ 阶段的状态数为 $\binom{N}{k} \times k!$，总状态数为 $O(N!)$。

关键洞察：TSP 完美展示了为什么需要近似 DP / 强化学习。DP 的数学框架完全正确，但计算量随 $N$ 指数增长。实际中，大规模 TSP 只能用近似方法求解——策略前展、蒙特卡洛树搜索等正是为此而设计。

三、预报与状态扩充

实际中，控制器可能获得关于未来扰动的预报（forecast）。例如天气预报预测明天的需求分布。

处理方法：状态扩充

引入预报过程 $y_k$ 作为额外状态：

$$\begin{pmatrix} x_{k+1} \\ y_{k+1} \end{pmatrix} = \begin{pmatrix} f_k(x_k, u_k, w_k) \\ \epsilon_k \end{pmatrix}$$

新的状态为 $(x_k, y_k)$，新的扰动为 $(w_k, \epsilon_k)$。

学习心得：状态扩充是 DP 中一个非常通用的技术。它的核心思想是：如果某些信息会影响未来的决策，就把这些信息纳入状态。这不改变 DP 的数学结构，只是让状态空间变大。后面讲部分可观察问题时，这个思想会再次出现。

四、部分可观察问题与置信状态

问题设定

在很多实际问题中，控制器无法直接观测完整状态。例如：

• 雷达只能测得三维位置，速度不可测
• 传感器有噪声
• 某些状态组分测量代价太高

解决方案：置信状态（Belief State）

置信状态 $b_k$ 是给定所有历史观测后，当前状态 $x_k$ 的概率分布：

$$b_k = P(x_k \mid \text{所有历史观测})$$

用 $b_k$ 代替 $x_k$ 作为新的状态，部分可观察问题就转化为了完全可观察问题（但状态空间变成了概率分布的空间）。

例子：寻宝问题

• 状态：某地点有/没有宝藏（2 个状态）
• 但寻宝者不知道真实状态
• 置信状态：$b = P(\text{有宝藏})$，一个 $[0,1]$ 之间的数
• 每次搜索后，根据是否找到宝藏，用贝叶斯规则更新 $b$

学习心得：置信状态的概念非常重要。它告诉我们："不确定性"本身也是一种状态。在部分可观察问题中，我们不是在"不知道状态的情况下做决策"，而是在"知道状态的概率分布的情况下做决策"。这个视角的转换使得 DP 框架依然适用。

五、自适应控制——未知参数的系统

问题

系统方程 $x_{k+1} = f_k(x_k, \theta, u_k, w_k)$ 中，参数 $\theta$ 未知。

例如汽车的巡航控制：$x_{k+1} = x_k + b \cdot u_k$，其中 $b$（与路面状况、车重相关）未知且可能随时间变化。

解决方案：将参数视为不可测状态

引入额外状态 $y_k = \theta$：

$$\begin{pmatrix} x_{k+1} \\ y_{k+1} \end{pmatrix} = \begin{pmatrix} f_k(x_k, y_k, u_k, w_k) \\ y_k \end{pmatrix}$$

$y_k$ 不随时间变化（参数恒定），但不可直接观测——这就变成了部分可观察问题，可以用置信状态来处理。

与 RL 的联系：自适应控制是强化学习的重要来源之一。RL 本质上就是在"未知环境"中学习最优策略。Bertsekas 通过这个例子展示了：未知参数可以自然地纳入 DP 框架，只是状态空间变大了，需要近似方法来处理。

六、确定性等价

定义

如果将系统方程中的随机扰动用其期望代替后，最优策略保持不变，则称确定性等价（certainty equivalence）成立。

$$x_{k+1} = f_k(x_k, u_k, w_k) \quad \longrightarrow \quad x_{k+1} = f_k(x_k, u_k, \mathbb{E}[w_k])$$

何时成立？

• 线性二次型问题（LQP）：线性系统 + 二次型费用 → 确定性等价成立
• 一般问题：通常不成立，但可以作为问题近似的基础

实际意义：确定性等价是一种最简单的问题近似方法——把随机问题当作确定性问题来解。虽然一般不精确，但在很多实际问题中效果不错。后面第 2 章会详细讨论这种方法。

七、Tetris（俄罗斯方块）——一个"大"问题

Bertsekas 用 Tetris 作为"状态空间极大"的例子：

• 状态：当前游戏区域的布局 + 下落板块的形状
• 控制：板块的放置位置和旋转角度
• 扰动：下落板块的形状（随机生成）

DP 算法：

$$J^*(z) = \sum_y p(y) \max_u \left[ g(z, y, u) + J^*(f(z, y, u)) \right]$$

虽然形式简洁，但游戏区域的布局数量是天文数字。精确 DP 完全不可行——只能用近似方法。

学习心得：Tetris 是一个很好的"试金石"问题。很多近似 DP/RL 方法都会在 Tetris 上测试性能。它足够复杂（大状态空间、随机性、长期规划），又足够简单（规则明确、容易实现）。

八、本节启示

这组例子传达了一个统一信息：

1. DP 框架极其通用——从最短路径到 TSP，从库存管理到自适应控制，都可以纳入 DP 框架
2. 维数灾难是核心挑战——精确 DP 在大状态空间上不可行
3. 状态扩充是万能工具——预报、部分可观察、未知参数都可以通过状态扩充来处理
4. 近似是必须的——本书后续所有内容都是对精确 DP 的某种近似

下一篇将进入第 2 章——强化学习中的近似方法，从值空间近似开始。