《强化学习与最优控制》【学习笔记02】精确动态规划：确定性问题的数学框架

《强化学习与最优控制》第 1.1 节 · 确定性动态规划

这是全书的起点。Bertsekas 从最简单的确定性有限阶段问题出发，建立动态规划的数学框架。理解这一节是理解后续所有近似方法的前提——因为近似是对精确方法的近似。

一、问题的数学描述

一个确定性动态规划问题由以下要素组成：

动态系统方程

$$x_{k+1} = f_k(x_k, u_k), \quad k = 0, 1, \ldots, N-1$$

• $k$：离散时刻（阶段）
• $x_k$：系统状态，属于状态空间 $S_k$
• $u_k$：控制（决策变量），属于控制约束集 $U_k(x_k)$
• $f_k$：系统方程，描述状态如何演化
• $N$：时域（总阶段数）

费用函数

总费用 = 各阶段费用之和 + 终止费用：

$$J(x_0; u_0, \ldots, u_{N-1}) = g_N(x_N) + \sum_{k=0}^{N-1} g_k(x_k, u_k)$$

• $g_k(x_k, u_k)$：第 $k$ 阶段的费用
• $g_N(x_N)$：终止费用

最优值

$$J^*(x_0) = \min_{u_0, \ldots, u_{N-1}} J(x_0; u_0, \ldots, u_{N-1})$$

注意符号：Bertsekas 用 $J$ 表示费用函数，用 $\min$ 表示最小化。这与 Sutton & Barto 用 $V$ 表示值函数、$\max$ 表示最大化是等价的（取负号即可转换）。

二、动态规划算法（核心）

DP 的核心思想是递归分解：把 $N$ 阶段问题分解为 $N$ 个单阶段问题。

从终端向始端反向计算

第 $N$ 步（终止条件）：

$$J_N^*(x_N) = g_N(x_N)$$

第 $k$ 步（递归方程，即贝尔曼方程）：

$$J_k^*(x_k) = \min_{u_k \in U_k(x_k)} \left[ g_k(x_k, u_k) + J_{k+1}^*(f_k(x_k, u_k)) \right]$$

这个方程的含义非常直观：

当前状态 x_k 的最优费用 = min [ 当前阶段费用 + 未来的最优费用 ]
                         u_k

最优策略：在每个状态 $x_k$ 处，选择取得上述最小值的控制 $u_k^*$。

学习心得：DP 算法是反向计算的——从最后一步 $N$ 开始，逐步向前推到第 0 步。这和很多人直觉中"从前往后推"相反。原因是：要决定当前怎么做，必须先知道"如果到了下一步，最优怎么做"。

三、为什么 DP 有效？——最优性原理

DP 算法背后的原理是贝尔曼的最优性原理：

最优策略具有如下性质：无论初始状态和初始决策是什么，剩余的决策必须构成一个关于由初始决策产生的状态的最优策略。

用数学语言说：如果 $\{u_0^*, \ldots, u_{N-1}^*\}$ 是从 $x_0$ 出发的最优控制序列，那么 $\{u_1^*, \ldots, u_{N-1}^*\}$ 是从 $x_1 = f_0(x_0, u_0^*)$ 出发的最优控制序列。

这个原理看似"显然"，但它的威力在于：把一个 $N$ 维联合优化问题分解为 $N$ 个一维优化问题，计算量从指数级降为多项式级。

四、离散最优控制 = 最短路径问题

Bertsekas 给出了一个优美的几何解释：任何确定性有限状态有限阶段问题都可以表示为有向无环图中的最短路径问题。

阶段0    阶段1    阶段2    ...    阶段N     终止
  ●──────→●──────→●──────→...───→●──────→ ●(虚拟终止节点)
  │        │        │              │
  x_0     x_1      x_2            x_N

• 节点 = 状态
• 边 = 状态-控制对 $(x_k, u_k)$，边的权重 = 阶段费用 $g_k(x_k, u_k)$
• 最优控制 = 从初始节点到终止节点的最短路径

学习心得：这个等价关系非常重要。它意味着：

1. 组合优化问题（如 TSP、调度）都可以用 DP 框架来描述
2. DP 算法本质上就是在图上做反向最短路径计算
3. 当状态空间太大时（指数级），精确 DP 不可行——这就是强化学习要解决的问题

五、连续空间最优控制

当状态空间是连续的（如欧几里得空间 $\Re^n$），DP 算法的形式不变，但计算上面临新挑战：

• $J_k^*(x_k)$ 是连续函数，无法用表格存储
• 需要离散化或参数化近似

经典例子是线性二次型问题（LQP）：

$$x_{k+1} = A x_k + B u_k$$

$$J = \sum_{k=0}^{N-1} (x_k' Q x_k + u_k' R u_k) + x_N' Q_N x_N$$

这类问题有解析解（Riccati 方程），是最优控制理论的核心内容。

六、Q 因子形式

Bertsekas 引入了 Q 因子（Q-factors）作为 DP 的等价表达形式：

$$Q_k^*(x_k, u_k) = g_k(x_k, u_k) + J_{k+1}^*(f_k(x_k, u_k))$$

即：在状态 $x_k$ 执行控制 $u_k$ 后，当前费用加上未来最优费用。

由此，最优费用和最优策略可以表示为：

$$J_k^*(x_k) = \min_{u_k \in U_k(x_k)} Q_k^*(x_k, u_k)$$

$$u_k^*(x_k) = \arg\min_{u_k \in U_k(x_k)} Q_k^*(x_k, u_k)$$

Q 因子版本的 DP 递归：

$$Q_k^*(x_k, u_k) = g_k(x_k, u_k) + \min_{u_{k+1} \in U_{k+1}(f_k(x_k, u_k))} Q_{k+1}^*(f_k(x_k, u_k), u_{k+1})$$

为什么需要 Q 因子？ 后面讲 Q 学习时就知道：Q 因子直接关联"状态-控制对"而非仅"状态"，使得无模型方法成为可能——不需要知道系统方程 $f_k$，只需要采样 $(x_k, u_k, x_{k+1})$ 三元组就能更新 Q 因子。

七、DP 的根本局限

Bertsekas 在本节末尾点明了全书动机：

DP 算法需要对所有状态 $x_k$ 计算 $J_k^*(x_k)$。当状态空间很大时（即所谓的维数灾难），这不可行。

强化学习的本质就是：在 DP 框架下，用近似方法来应对状态空间过大的问题。