🤖 machine learning

Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs

本文提出了一种基于非精确增广拉格朗日方法的通用框架，该框架在表格型、对数线性及复杂非线性策略设定下，均能实现约束马尔可夫决策过程的可证明全局最后迭代收敛，从而解决了现有混合策略方法的实际局限性。

原作者： Michael Lu, Max Qiushi Lin, Mo Chen, Sharan Vaswani

发布于 2026-05-13

📖 1 分钟阅读☕ 轻松阅读

原作者： Michael Lu, Max Qiushi Lin, Mo Chen, Sharan Vaswani

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在训练一个机器人玩电子游戏。目标很简单：获得尽可能高的分数。但有一个陷阱：机器人有一条严格的规定：在游戏结束前不能耗尽电量。

这就是本文要解决的核心问题，在科技界被称为约束马尔可夫决策过程（CMDP）。机器人（即“智能体”）需要在遵守预算（电量寿命）的前提下，最大化其奖励（分数）。

现有方法的问题：“混合搭配”的混乱局面

目前大多数针对该问题的人工智能方法，就像一位试图做出完美汤品的厨师。它们逐一尝试许多不同的食谱（策略）。然而，在结束时，它们并没有端出找到的那一份最佳食谱，而是告诉你：“这是一碗汤，由我们尝试过的每一种食谱随机混合少许而成。”

虽然这种“混合汤”在纸面上（数学上）表现良好（满足规则），但在现实世界中却是一场噩梦：

内存负担重：你必须记住曾经尝试过的每一种食谱，才能进行混合。
不可预测：如果你真的从这碗混合汤中舀出一勺，它可能会难喝至极。哪怕整碗汤的平均水平尚可，随机舀出的一勺却可能全是盐（违反电量规则）。
振荡：机器人的行为往往在“太快”和“太慢”之间剧烈摇摆，无法稳定下来。

本文认为，在现实生活中（如自动驾驶汽车或医疗设备），我们不能依赖这种“随机混合”。我们需要一个单一、最终的机器人，它开箱即用，既安全又有效。这被称为**“最后迭代收敛”**。

解决方案：“增广拉格朗日”（严格的教练）

作者提出了一种新方法，利用数学中的经典技术——增广拉格朗日（AL）方法来训练机器人。

将 AL 方法想象成一位严格的教练，他不仅会大喊“加速！”（最大化奖励），如果机器人违反规则，还会在机器人背上挂上一个沉重的惩罚负重。

这位教练的工作方式如下：

惩罚负重：如果机器人快要耗尽电量，教练就会在机器人的目标上增加一个沉重的二次惩罚（就像一个沉重的背包）。违反规则越严重，背包就越重，使其前进越困难。
调整：教练不会只是把负重留在那里。他们会根据机器人的表现不断调整背包的重量。
- 如果机器人表现安全，教练会稍微减轻负重。
- 如果机器人表现危险，教练会立即加重负重。
结果：AL 方法引导机器人不再在“太快”和“太慢”之间剧烈摇摆，而是平滑地走向一条单一、稳定的路径，使其既能获得高分，又能保持安全。

“魔法”成分：投影 Q 上升（PQA）

本文最大的突破在于，他们找到了如何让这位“严格教练”高效工作，即使机器人正在学习复杂技能（如行走或飞行）。

他们使用了一种特定的训练技术，称为投影 Q 上升（PQA）。

类比：想象机器人正试图爬上一座山，寻找最高峰（最佳分数）。但这座山上有一个“禁入区”（安全约束）。
旧方法：机器人可能会尝试攀登，意识到自己进入了“禁入区”，然后来回跳跃，永远无法安定下来。
PQA 方法：机器人向山上迈进一步。如果这一步会将其带入“禁入区”，PQA 就会像一堵磁性墙一样发挥作用。它会温柔但坚定地将机器人推回安全区的边缘，同时保持其沿最佳方向移动。它将机器人的运动“投影”到安全路径上。

他们证明了什么？

作者不仅构建了一个酷炫的机器人，还从数学上证明了这种方法的有效性：

收敛性：机器人最终会停止摇摆，稳定在一个单一的最终策略上。
安全性：该最终策略将以高度确定性满足安全规则（电量限制），而不仅仅是平均意义上满足。
高效性：他们证明该方法适用于简单的网格（表格型）和复杂的现实世界任务（如电子游戏中的连续控制），而无需存储成千上万个机器人的过往版本。

现实世界中的结果

该团队在标准的安全基准测试（例如机器人在不撞墙的情况下穿越迷宫）上测试了他们的方法（他们称之为PPQA-ALM或SPMA-ALM）。

对比：他们将其与其他流行方法（如 PPO-Lag 和 CPO）进行了比较。
结果：他们的方法在获得高分方面同样出色，但稳定性要高得多。它不会发生振荡。它找到了一个单一、可靠的解决方案，尊重了安全约束，而其他方法有时难以稳定下来，或者需要复杂的“混合”技巧才能生效。

总结

简而言之，本文介绍了一种更智能的方法来训练带有安全规则的人工智能智能体。他们不再依赖许多失败尝试的令人困惑的“平均值”，而是利用带有惩罚背包的严格教练和磁性墙，引导人工智能走向单一、完美且安全的最终行为。这使得该技术能够应用于安全不可妥协的现实世界场景。

技术摘要：约束马尔可夫决策过程（CMDP）的增广拉格朗日法及其最后一次迭代收敛性

问题表述

本文解决了无限时域、折扣型约束马尔可夫决策过程（CMDP）的策略优化问题。在此设定下，智能体必须最大化累积奖励 $V^\pi_r(\rho)$ ，同时确保累积约束奖励 $V^\pi_{c_i}(\rho)$ 满足 $m$ 个约束的预设阈值 $b_i$ 。与最优策略通常为确定性的标准马尔可夫决策过程（MDP）不同，CMDP 的最优策略通常是随机性的。

现有的原始 - 对偶（Primal-Dual, PD）方法存在显著的实际局限性，构成了一个重大挑战。尽管 PD 方法具有理论保证，但这些保证通常仅适用于混合策略（即训练过程中生成的所有中间策略的均匀平均）。部署此类混合策略在计算和内存方面开销巨大，因为它需要存储所有中间策略。此外，在安全关键应用中，依赖混合策略具有风险，因为即使混合策略在期望上满足约束，从中随机采样的策略仍可能严重违反约束。因此，从业者通常部署最后一次迭代策略（即最终生成的策略），但标准 PD 方法缺乏针对该特定策略的理论保证，往往表现出振荡行为，且无法收敛到可行解。

近期试图证明最后一次迭代收敛性的工作大多局限于表格（tabular）设定，或依赖于难以实现或对大规模问题不切实际的算法变体（例如重度正则化）。

方法论

作者提出了一种基于**增广拉格朗日（Augmented Lagrangian, AL）**方法的通用框架。AL 是约束优化中的经典方法，该框架旨在为 CMDP 实现可证明的最后一次迭代收敛。

1. 增广拉格朗日框架

该框架优化增广拉格朗日函数 $L_\beta(\pi, \lambda)$ ，而非 PD 方法中使用的标准拉格朗日函数：
$L_\beta(\pi, \lambda) := V^\pi_r(\rho) + \frac{\beta}{2} \sum_{i=1}^m \left( -\min\left\{ V^\pi_{c_i}(\rho) - b_i - \frac{\lambda_i}{\beta}, 0 \right\}^2 + \frac{\lambda_i^2}{\beta^2} \right)$
其中 $\beta > 0$ 是惩罚参数， $\lambda$ 是拉格朗日乘子。二次惩罚项抑制约束违反。该算法迭代更新策略（原始变量）以近似最大化该函数，并根据约束违反情况更新对偶变量（拉格朗日乘子）。

2. 求解 AL 子问题

核心挑战在于 $L_\beta(\pi, \lambda)$ 关于策略 $\pi$ 是非凹的，使得子问题难以求解。作者将解决方案分解为两种设定：

表格设定：作者提出使用投影 Q 上升（Projected Q-Ascent, PQA）求解 AL 子问题。他们推导了 AL 子问题的策略梯度，该梯度涉及一个依赖于当前策略约束满足程度的非平稳伪奖励 $\Gamma(\pi)$ 。通过使用 PQA，他们建立了子问题的全局最后一次迭代收敛保证。
函数近似（对数线性策略）：为了处理大型状态 - 动作空间，该框架被扩展至参数化策略（具体为对数线性策略）。作者推导了一种AL 策略梯度，该梯度线性分解为原始奖励和约束分量，从而允许使用标准估计工具（如 PPO 或 SPMA 中使用的工具）。他们引入了一种**投影 PQA（PPQA）**更新，涉及以下步骤：
1. 计算理想化的策略更新（PQA 步骤）。
2. 使用前向 KL 散度将该更新投影到可行策略类上，表述为一个代理优化问题（带软标签的多类逻辑回归）。

3. 收敛性分析

作者提供了模块化分析：

他们首先证明，如果子问题求解器达到特定精度（外循环需要 $O(1/\epsilon^2)$ 次迭代），则非精确 AL 方法将收敛到 CMDP 的 $\epsilon$ -最优解。
随后，他们分析了特定求解器（PQA 和 PPQA），证明它们能够实现子问题所需的精度。
结合这些结果，他们证明了整体算法在表格和对数线性设定下均实现了全局最后一次迭代收敛，其样本复杂度为 $O(1/\epsilon^6)$ 次梯度评估。

主要贡献

通用非精确 AL 框架：本文引入了一个用于求解 CMDP 的模块化框架，采用非精确 AL 方法。它将 AL 迭代的分析与子问题求解器的选择分离开来，证明了只要子问题以足够精度求解， $O(1/\epsilon^2)$ 次外循环迭代足以找到 $\epsilon$ -最优策略。
表格最后一次迭代收敛：通过在表格设定中实例化投影 Q 上升（PQA）作为框架的求解器，作者建立了复杂度为 $O(1/\epsilon^6)$ 的全局最后一次迭代收敛性。这解决了 AL 子问题中伪奖励的非平稳性问题。
扩展至函数近似：该框架被推广至对数线性策略。作者推导了 AL 策略梯度，并提出了一种投影变体（PPQA），实现了可比的 $O(1/\epsilon^6)$ 收敛保证。与 prior work 不同，该方法不需要非标准的算法修改（如投影到受限单纯形）或限制性的结构假设（如兼容函数近似），并支持多个约束。
实证验证：该框架使用 PPO 和 SPMA（一种近期的策略优化算法）进行实例化，并在 Safety-Gymnasium 的大规模连续控制任务上进行了评估。结果表明，所提出的方法与经过高度工程化的基线（如 PPO-Lag 和 CPO）表现相当，同时为最终策略提供了理论保证。

结果

理论方面：本文证明，所提出的算法在经过 $O(1/\epsilon^6)$ 次梯度评估后，返回一个随机策略，该策略是 CMDP 问题的 $\epsilon$ -近似解。这一结论对表格和对数线性策略类均成立。
实证（表格）：在表格环境（约束悬崖世界、约束深海宝藏）中，所提出的 PQA-ALM 和 PPQA-ALM 方法平滑收敛至最优策略，振荡最小，性能优于或匹配其他最后一次迭代方法（如 RPG-PD 和 ReLOAD）。
实证（连续控制）：在 Safety-Gymnasium 任务（SafetyAntVelocity、SafetyHalfCheetahVelocity、SafetyHopperVelocity）上，SPMA-ALM 和 PPO-ALM 变体在回报和约束违反方面达到了与 PPO-Lag 和 CPO 相当的水平。值得注意的是，与基线相比，基于 AL 的方法表现出更少的振荡行为，以及更一致的约束满足度（更低的均值和尾部违反）。

意义与主张

本文声称弥合了约束强化学习中理论保证与实际部署之间的差距。

实用性：与以往局限于表格设定或依赖不切实际的正则化的最后一次迭代收敛工作不同，该框架旨在利用标准函数近似实现高效性，并可扩展至大规模问题。
安全性：通过保证最后一次迭代策略而非混合策略的收敛性，该方法确保部署的策略本身满足约束，这对于从混合策略中随机采样不可接受的安全关键应用至关重要。
原则性方法：该方法依赖于经典的增广拉格朗日方法，提供了清晰的理论基础，无需实际约束强化学习实现中常见的临时启发式方法（例如通过乘子缩放目标）。

作者承认了局限性，特别是表格设定中对最小状态访问概率（ $\rho_{min}$ ）的强依赖，以及对数线性策略中的偏差项（ $\epsilon_{bias}$ ），并建议将这些作为未来工作的方向。他们还指出，未来的方向包括将 Actor-Critic 或离线策略方法纳入理论框架。