《强化学习与最优控制》【学习笔记09】无穷阶段动态规划：贝尔曼方程与压缩映射

《强化学习与最优控制》第 4 章 · 无穷阶段动态规划

有限阶段问题有明确的终止时刻 $N$。但很多实际问题——持续运行的控制系统、不终止的博弈、在线服务——需要无穷阶段模型。这会带来数学上的新挑战，但也带来优美的结构。

一、为什么需要无穷阶段？

无穷阶段问题的费用是无限求和，需要保证收敛。

二、两大无穷阶段模型

1. 随机最短路径问题（SSP）

$$J_\mu(i) = \mathbb{E}\left\{ \sum_{k=0}^{\infty} g(i_k, \mu_k(i_k), w_k) \right\}$$

• 费用不折扣（$\gamma = 1$）
• 存在终止状态 $t$，到达后费用为 0 且不再离开
• 假设：最优策略下，从任何状态都能（以概率 1）到达终止状态
• 例子：走出迷宫（每步代价 -1，目标是尽快到达终点）

2. 折扣问题

$$J_\mu(i) = \mathbb{E}\left\{ \sum_{k=0}^{\infty} \alpha^k g(i_k, \mu_k(i_k), w_k) \right\}$$

• $\alpha \in (0, 1)$：折扣因子
• 不需要终止状态
• 折扣保证收敛：$|J_\mu| \leq \frac{g_{\max}}{1 - \alpha}$
• 例子：持续控制系统（每步有代价，未来代价折扣）

学习心得：折扣因子 $\alpha$ 的作用与有限阶段问题中的 $\gamma$ 类似——让远期费用权重更小。但在无穷阶段中，折扣因子还有更深的数学意义：它使贝尔曼算子成为压缩映射，从而保证解的存在唯一性和算法收敛性。

三、贝尔曼方程

折扣问题的贝尔曼方程

$$J^*(i) = \min_{u \in U(i)} \sum_j p_{ij}(u) \left[ g(i, u, j) + \alpha J^*(j) \right]$$

这是函数方程——$J^*$ 出现在等式两边。与有限阶段不同，没有"终止条件"来从后向前递推。

贝尔曼算子

定义算子 $T$：

$$(TJ)(i) = \min_{u \in U(i)} \sum_j p_{ij}(u) \left[ g(i, u, j) + \alpha J(j) \right]$$

贝尔曼方程变为：$J^* = TJ^*$，即 $J^*$ 是 $T$ 的不动点。

四、压缩映射定理——数学核心

压缩映射的定义

算子 $T$ 是压缩映射，如果存在 $\rho \in (0, 1)$ 使得：

$$\|TJ_1 - TJ_2\|_\infty \leq \rho \|J_1 - J_2\|_\infty, \quad \forall J_1, J_2$$

折扣问题的压缩性

对于折扣问题，$T$ 是压缩映射，压缩系数为 $\alpha$：

$$\|TJ_1 - TJ_2\|_\infty \leq \alpha \|J_1 - J_2\|_\infty$$

证明直觉：$T$ 中含 $\alpha J(j)$，两个不同 $J$ 的差异被 $\alpha$ 缩小。

压缩映射定理

如果 $T$ 是压缩映射，则：

1. 存在唯一不动点：存在唯一的 $J^*$ 使 $J^* = TJ^*$
2. 值迭代收敛：从任意 $J_0$ 出发，$J_{k+1} = TJ_k$ 收敛到 $J^*$
3. 收敛速度：$\|J_k - J^*\| \leq \frac{\rho^k}{1 - \rho} \|J_1 - J_0\|$

学习心得：压缩映射定理是无穷阶段 DP 的数学基石。它告诉我们：

1. 最优费用函数 $J^*$ 存在且唯一——不是所有优化问题都有解
2. 值迭代一定能收敛——不需要猜测初始值
3. 收敛速度是几何级数——每步误差至少缩小 $\alpha$ 倍

这三个保证在有限阶段问题中是"显然"的（有限步递推），但在无穷阶段中需要严格证明。

五、值迭代算法

$$J_{k+1} = TJ_k$$

即：

$$J_{k+1}(i) = \min_{u \in U(i)} \sum_j p_{ij}(u) \left[ g(i, u, j) + \alpha J_k(j) \right]$$

性质

• 从任意 $J_0$ 出发都收敛到 $J^*$
• 收敛速度：线性收敛率 $\alpha$
• 每步对所有状态做一次最小化

异步值迭代

不需要同步更新所有状态——可以异步更新：

• 按任意顺序更新各状态
• 某些状态更新频率高，某些低
• 只要每个状态被更新无穷次，就收敛

实际意义：异步值迭代是分布式计算和在线学习的基础。在多处理器环境中，各处理器可以独立更新不同状态的值；在在线学习中，只更新遇到的状态。

六、策略迭代算法

两步循环

1. 策略评价：给定策略 μ，求解 J_μ 满足 J_μ = T_μ J_μ
2. 策略改进：μ_new(i) = argmin_u Σ_j p_ij(u) [g(i,u,j) + α J_μ(j)]
3. 重复

数学描述

策略评价：解线性方程组

$$J_\mu(i) = \sum_j p_{ij}(\mu(i)) \left[ g(i, \mu(i), j) + \alpha J_\mu(j) \right]$$

这是 $n$ 个未知数、$n$ 个方程的线性方程组（$n$ 为状态数）。

策略改进：

$$\mu_{\text{new}}(i) = \arg\min_{u \in U(i)} \sum_j p_{ij}(u) \left[ g(i, u, j) + \alpha J_\mu(j) \right]$$

收敛性

• 策略序列的费用单调递减：$J_{\mu_{k+1}} \leq J_{\mu_k}$
• 有限状态/控制空间下，有限步收敛到最优策略
• 无限空间下，收敛到 $J^*$

七、值迭代 vs 策略迭代

学习心得：值迭代和策略迭代是 DP 的两大算法，各有优劣。值迭代每步简单但收敛慢，策略迭代每步复杂但收敛快。实践中常常混合使用——先用值迭代几步粗调，再用策略迭代精调。

八、Q 因子版本

Q 因子的贝尔曼方程

$$Q^*(i, u) = \sum_j p_{ij}(u) \left[ g(i, u, j) + \alpha \min_{u'} Q^*(j, u') \right]$$

Q 因子的策略迭代

策略评价：

$$Q_\mu(i, u) = \sum_j p_{ij}(u) \left[ g(i, u, j) + \alpha Q_\mu(j, \mu(j)) \right]$$

策略改进：

$$\mu_{\text{new}}(i) = \arg\min_u Q_\mu(i, u)$$

Q 因子的优势：策略改进只需要 Q 因子，不需要知道 $p_{ij}$。这是 Q 学习的基础——通过采样 $(i, u, j, g)$ 来近似 Q 因子，完全不需要系统模型。

九、半马尔可夫问题

当状态转移的时间是随机的（不固定为 1），需要半马尔可夫模型：

$$J_\mu(i) = G(i, \mu(i)) + \sum_j m_{ij}(\mu(i)) J_\mu(j)$$

• $G(i, u)$：一步转移的期望折扣费用
• $m_{ij}(u)$：折扣转移概率（含随机时间的折扣因子 $\mathbb{E}[e^{-\beta \tau}]$）

数学结构与标准折扣问题完全平行，只是 $p_{ij}$ 被 $m_{ij}$ 代替。

十、本章核心公式速查

下一篇将进入第 5 章——无穷阶段强化学习。在第 4 章的精确算法基础上，引入近似：拟合值迭代、Q 学习、DQN、TD(λ) 等。