Solving Multi-Agent Safe Optimal Control with Distributed Epigraph Form MARL

Songyuan Zhang 1 2 , Oswin So 1 2 , Mitchell Black 3 , Zachary Serlin 3 and Chuchu Fan 2 Affiliation:  2 Department of Aeronautics and Astronautics, MIT, Cambridge, Massachusetts, USA Email: {szhang21, oswinso, chuchu}@mit.edu Affiliation:  3 MIT Lincoln Laboratory, Lexington, Massachusetts, USA Email: {mitchell.black, Zachary.Serlin}@ll.mit.edu

Abstract

Tasks for multi-robot systems often require the robots to collaborate and complete a team goal while maintaining safety. This problem is usually formalized as a constrained Markov decision process (CMDP), which targets minimizing a global cost and bringing the mean of constraint violation below a user-defined threshold. Inspired by real-world robotic applications, we define safety as zero constraint violation. While many safe multi-agent reinforcement learning (MARL) algorithms have been proposed to solve CMDPs, these algorithms suffer from unstable training in this setting. To tackle this, we use the epigraph form for constrained optimization to improve training stability and prove that the centralized epigraph form problem can be solved in a distributed fashion by each agent. This results in a novel centralized training distributed execution MARL algorithm named Def-MARL. Simulation experiments on 8 different tasks across 2 different simulators show that Def-MARL achieves the best overall performance, satisfies safety constraints, and maintains stable training. Real-world hardware experiments on Crazyflie quadcopters demonstrate the ability of Def-MARL to safely coordinate agents to complete complex collaborative tasks compared to other methods.[^1][^0]

多机器人系统任务常要求机器人协作完成团队目标并保持安全。该问题通常形式化为约束马尔可夫决策过程（CMDP），目标是最小化全局代价，并使约束违反的均值低于用户设定阈值。受真实机器人应用启发，我们将安全定义为零约束违反。已有许多安全多智能体强化学习（MARL）算法用于求解 CMDP，但在该设定下训练不稳定。为此，我们用约束优化的上图形式（epigraph form）提升训练稳定性，并证明中心化上图形式问题可由各智能体分布式求解。由此得到一种新颖的集中训练、分布执行（CTDE）MARL 算法 Def-MARL。在 2 个仿真器共 8 项任务上的实验表明，Def-MARL 综合表现最佳，满足安全约束且训练稳定。Crazyflie 四旋翼真机实验显示，相对其他方法，Def-MARL 能更安全地协调智能体完成复杂协作任务。[^1][^0]

I Introduction

I 引言

Multi-agent systems (MAS) play an integral role in our aspirations for a more convenient future with examples such as autonomous warehouse operations [37], large-scale autonomous package delivery [45], and traffic routing [76]. These tasks often require designing distributed policies for agents to complete a team goal collaboratively while maintaining safety. To construct distributed policies, multi-agent reinforcement learning (MARL) under the centralized training distributed execution (CTDE) paradigm [84, 25] has emerged as an attractive method. To incorporate the safety constraints, most MARL algorithms either choose to carefully design their objective function to incorporate soft constraints [69, 58, 79, 74, 54, 57], or model the problem using the constrained Markov decision process (CMDP) [3], which asks for the mean constraint violation to stay below a user-defined threshold [32, 38, 18, 41, 26, 90]. However, real-world robotic applications always require zero constraint violation. While this can be addressed by setting the constraint violation threshold to zero in the CMDP, in this setting the popular Lagrangian methods experience training instabilities which result in sharp drops in performance during training, and non-convergence or convergence to poor policies [66, 35, 24, 36].

多智能体系统（MAS）在我们对更便捷未来的设想中扮演关键角色，例如仓储自动化 [37]、大规模自主包裹配送 [45] 与交通路由 [76]。这些任务常需设计分布式策略，使智能体协作完成团队目标并保持安全。在集中训练、分布执行（CTDE）范式 [84, 25] 下，多智能体强化学习（MARL）成为构造分布式策略的有吸引力方法。为纳入安全约束，多数 MARL 算法要么精心设计目标以融入软约束 [69, 58, 79, 74, 54, 57]，要么用约束马尔可夫决策过程（CMDP）[3] 建模，要求平均约束违反低于用户阈值 [32, 38, 18, 41, 26, 90]。但真实机器人应用往往要求零约束违反。虽可通过把 CMDP 阈值设为零来处理，此时流行的拉格朗日方法会出现训练不稳定：训练中性能骤降、不收敛或收敛到差策略 [66, 35, 24, 36]。

These concerns have been identified recently, resulting in a series of works that enforce hard constraints [82, 89, 66, 24, 86] using techniques inspired by Hamilton-Jacobi reachability [71, 44, 49, 46, 5] in deep reinforcement learning (RL) for the single-agent case and have been shown to improve safety compared to other safe RL approaches significantly. However, to the best of our knowledge, theories and algorithms for safe RL are still lacking for the multi-agent scenario, especially when policies are executed in a distributed manner. While single-agent RL methods can be directly applied to the MARL setting by treating the MAS as a centralized single agent, the joint action space grows exponentially with the number of agents, preventing these algorithms from scaling to scenarios with a large number of agents [33, 69, 23].

这些顾虑近来被指出，随之出现一系列在单智能体深度强化学习中用哈密顿–雅可比可达性启发的技术强制硬约束的工作 [82, 89, 66, 24, 86]，显著提升了相对其他安全 RL 方法的安全性 [71, 44, 49, 46, 5]。但据我们所知，面向多智能体、尤其策略以分布式执行时的安全 RL 理论与算法仍不足。虽可把 MAS 当作中心化单智能体直接套用单智能体 RL，但联合动作空间随智能体数指数增长，难以扩展到大规模场景 [33, 69, 23]。

To tackle the problem of zero constraint violation in multi-agent scenarios with distributed policies[^2] while achieving high collaborative performance, we propose Distributed epigraph form MARL (Def-MARL) (). Instead of considering the CMDP setting, Def-MARL directly tackles the multi-agent safe optimal control problem (MASOCP), whose solution satisfies zero constraint violation. To solve the MASOCP, Def-MARL uses the epigraph form technique [10], which has previously been shown to yield better policies compared to Lagrangian methods in the single-agent setting [66]. To adapt to the multi-agent setting we consider in this work, we prove that the centralized epigraph form of MASOCP can be solved in a distributed fashion by each agent. Using this result, Def-MARL falls under the CTDE paradigm.

为在多智能体场景下以分布式策略[^2] 实现零约束违反并保持高协作性能，我们提出 Distributed epigraph form MARL（Def-MARL）。Def-MARL 不采用 CMDP 设定，直接求解多智能体安全最优控制问题（MASOCP），其解满足零约束违反。求解时使用上图形式技术 [10]，该技术此前在单智能体设定中已被证明相对拉格朗日方法能得到更好策略 [66]。针对本文多智能体设定，我们证明 MASOCP 的中心化上图形式可由各智能体分布式求解；据此 Def-MARL 落入 CTDE 范式。

We validate Def-MARL using 8 different tasks from 2 different simulators, multi-particle environments (MPE) [40] and Safe Multi-agent MuJoCo [32], with varying numbers of agents, and compare its performance with existing safe MARL algorithms using the penalty and Lagrangian methods. The results suggest that Def-MARL achieves the best performance while satisfying safety: it is as safe as conservative baselines that achieve high safety but sacrifice performance, while matching the performance of unsafe baselines that sacrifice safety for high performance. In addition, while the baseline methods require different choices of hyperparameters to perform well in different environments and suffer from unstable training because of zero constraint violation threshold, Def-MARL is stable in training using the same hyperparameters across all environments, indicative of the algorithm’s robustness to environmental changes.

我们在多智能体粒子环境（MPE）[40] 与 Safe Multi-agent MuJoCo [32] 两个仿真器共 8 项、智能体数量不等的任务上验证 Def-MARL，并与采用惩罚与拉格朗日方法的现有安全 MARL 算法比较。结果表明 Def-MARL 在满足安全的同时取得最佳性能：安全性可比肩高安全但牺牲性能的保守基线，性能又可匹敌牺牲安全换高性能的激进基线。此外，基线常需为不同环境挑选不同超参，且因零违反阈值而训练不稳；Def-MARL 在全部环境用同一套超参即可稳定训练，体现对环境变化的鲁棒性。

We also perform real-world hardware experiments using the Crazyflie (CF) drones [27] on two complex collaborative tasks and compare Def-MARL with both centralized and decentralized model predictive control (MPC) methods [29]. The results indicate that Def-MARL finishes the tasks with $100\%$ safety rates and success rates, while the MPC methods get stuck in local minima or have unsafe behaviors.

我们还在 Crazyflie（CF）无人机 [27] 上做两项复杂协作真机实验，并与中心化/去中心化模型预测控制（MPC）[29] 比较。结果表明 Def-MARL 以 $100\%$ 安全率与成功率完成任务，而 MPC 方法易陷局部最小或不安全行为。

To summarize, our contributions are presented below:

总结而言，本文贡献如下：

• • Drawing on prior work that addresses the training instability of Lagrangian methods in the zero-constraint violation setting, we extend the epigraph form method from single-agent RL to MARL, improving upon the training instability of existing MARL algorithms.

• • 借鉴先前针对零约束违反设定下拉格朗日方法训练不稳的工作，我们将上图形式方法从单智能体 RL 扩展到 MARL，改善现有 MARL 算法的训练稳定性。

• • We present theoretical results showing that the outer problem of the epigraph form can be decomposed and solved in a distributed manner during online execution. This allows Def-MARL to fall under the CTDE paradigm.

• • 我们给出理论结果：上图形式的外层问题可在在线执行时分解并由各智能体分布式求解，从而使 Def-MARL 落入 CTDE 范式。

• • We illustrate through extensive simulations that, without any hyperparameter tuning, Def-MARL achieves stable training and is as safe as the most conservative baseline while simultaneously being as performant as the most aggressive baseline across all environments.

• • 大量仿真表明，无需调超参，Def-MARL 即可稳定训练，并在全部环境中同时达到最保守基线的安全性与最激进基线的性能。

• • We demonstrate on Crazyflie drones in hardware that Def-MARL can safely coordinate agents to complete complex collaborative tasks. Def-MARL performs the task better than centralized/decentralized MPC methods and does not get stuck in suboptimal local minima or exhibit unsafe behaviors.

• • 我们在 Crazyflie 真机上展示 Def-MARL 可安全协调智能体完成复杂协作；相对中心化/去中心化 MPC，表现更好，且不易陷次优局部最小或不安全行为。

II Related work

II 相关工作

Unconstrained MARL. Early works that approach the problem of safety for MARL focus on navigation problems and collision avoidance [14, 13, 21, 64], where safety is achieved by a sparse collision penalty [39], or a shaped reward penalizing getting close to obstacles and neighboring agents [14, 13, 21, 64]. However, adding a penalty to the reward function changes the original objective function, so the resulting policy may not be optimal for the original constraint optimization problem. In addition, the satisfaction of collision avoidance constraints is not necessarily guaranteed by even the optimal policy [47, 21, 39].

无约束 MARL。 早期面向 MARL 安全的工作聚焦导航与避碰 [14, 13, 21, 64]，通过稀疏碰撞惩罚 [39]，或惩罚靠近障碍与邻智能体的塑形奖励 [14, 13, 21, 64] 实现安全。但把惩罚加进奖励会改变原目标，所得策略未必是原约束优化问题的最优解；即便最优策略也不一定保证满足避碰约束 [47, 21, 39]。

Shielding for Safe MARL. One popular method that provides safety to learning-based methods is using shielding or a safety filter [25]. Here, an unconstrained learning method is paired with a shield or safety filter using techniques such as predictive safety filters [88, 50], control barrier functions [11, 55], or automata [19, 77, 48, 7]. Such shields are often constructed before the learning begins and are used to modify either the feasible actions or the output of the learned policy to maintain safety. One benefit is that safety can be guaranteed during both training and deployment since the shield is constructed before training. However, they require domain expertise to build a valid shield, which can be challenging in the single-agent setting and even more difficult for MAS [25]. Other methods can automatically synthesize shields but face scalability challenges [48, 20]. Another drawback is that the policy after shielding might not consider the same objective as the original policy and may result in noncollaborative behaviors or deadlocks [56, 85, 87].

安全 MARL 的屏蔽。 为学习方法提供安全的流行做法是使用屏蔽或安全滤波器 [25]：无约束学习方法搭配预测安全滤波器 [88, 50]、控制障碍函数 [11, 55] 或自动机 [19, 77, 48, 7] 等构造的屏蔽，在学习开始前建好，用于修改可行动作或所学策略输出以保持安全。优点是训练与部署期都可保证安全；但构建有效屏蔽需要领域专长，单智能体已难，MAS 更甚 [25]。也有自动综合屏蔽的方法，但面临可扩展性挑战 [48, 20]。另一缺点是屏蔽后策略可能不再对应原目标，导致非协作行为或死锁 [56, 85, 87]。

Constrained MARL. In contrast to unconstrained MARL methods, which change the constraint optimization problem to an unconstrained problem, constrained MARL methods explicitly solve the CMDP problem. For the single-agent case, prominent methods for solving CMDPs include primal methods [78], primal-dual methods using Lagrange multipliers [8, 70, 35, 36], and trust-region-based approaches [1, 35]. These methods provide guarantees either in the form of asymptotic convergence guarantees to the optimal (safe) solution [8, 70] using stochastic approximation theory [59, 9], or recursive feasibility of intermediate policies [1, 60] using ideas from trust region optimization [61]. The survey [31] provides an overview of the different methods of solving safety-constrained single-agent RL. In multi-agent cases, however, the problem becomes more difficult because of the non-stationary behavior of other agents, and similar approaches have been presented only recently [32, 38, 18, 41, 26, 90, 15]. However, the CMDP setting they handle makes it difficult for them to handle hard constraints, and results in poor performance with zero constraint violation threshold [24].

约束 MARL。 与把约束问题改成无约束问题的做法不同，约束 MARL 显式求解 CMDP。单智能体侧，主要方法包括原方法 [78]、用拉格朗日乘子的原–对偶方法 [8, 70, 35, 36] 以及基于信任域的方法 [1, 35]。它们或借助随机逼近理论给出渐近收敛到最优（安全）解的保证 [8, 70, 59, 9]，或借助信任域优化思想保证中间策略递归可行 [1, 60, 61]。综述 [31] 概述了安全约束单智能体 RL 的各类方法。多智能体情形因其他智能体非平稳而更难，类似方法近年才出现 [32, 38, 18, 41, 26, 90, 15]。但其所处理的 CMDP 设定难以应对硬约束，在零违反阈值下表现较差 [24]。

Model predictive control. Distributed MPC methods have been proposed to handle MAS, incorporating multi-agent path planning, machine learning, and distributed optimization [75, 72, 92, 22, 42, 16, 52]. However, the solution quality of nonlinear optimizers used to solve MPC when the objective function and constraints are nonlinear highly depends on the initial guess [73, 29]. Moreover, the real-time nonlinear optimizers typically require access to (accurate) first and second-order derivatives [53, 29], which present challenges when trying to solve tasks that have non-differentiable or discontinuous cost functions and constraints such as the ones we consider in this work.

模型预测控制。 已有分布式 MPC 用于 MAS，融合多智能体路径规划、机器学习与分布式优化 [75, 72, 92, 22, 42, 16, 52]。但当目标与约束非线性时，求解 MPC 的非线性优化器解质量高度依赖初值猜测 [73, 29]；实时非线性优化器通常还需（准确的）一、二阶导数 [53, 29]，对本文这类含不可微或间断代价与约束的任务构成挑战。

III Problem setting and preliminaries

III 问题设定与预备知识

III-A Multi-agent safe optimal control problem

III-A 多智能体安全最优控制问题

We consider the multi-agent safe optimal control problem (MASOCP) as defined below. Consider a homogeneous MAS with $N$ agents. At time step $k$, the global state and control input are given by $x^{k}\in\mathcal{X}\subseteq\mathbb{R}^{n}$ and $u^{k}\in\mathcal{U}\subseteq\mathbb{R}^{m}$, respectively. The global control vector is defined by concatenation $u^{k}\coloneqq[u_{1}^{k};\dots;u_{N}^{k}]$, where $u_{i}^{k}\in\mathcal{U}_{i}$ is the control input of agent $i$. We consider the general nonlinear discrete-time dynamics for the MAS:

我们考虑如下定义的多智能体安全最优控制问题（MASOCP）。设同质 MAS 有 $N$ 个智能体。时刻 $k$ 的全局状态与控制输入分别为 $x^{k}\in\mathcal{X}\subseteq\mathbb{R}^{n}$、$u^{k}\in\mathcal{U}\subseteq\mathbb{R}^{m}$。全局控制由拼接定义 $u^{k}\coloneqq[u_{1}^{k};\dots;u_{N}^{k}]$，其中 $u_{i}^{k}\in\mathcal{U}_{i}$ 为智能体 $i$ 的控制。我们考虑 MAS 的一般非线性离散时间动力学：

$$x^{k+1}=f(x^{k},u^{k}), \tag{1}$$

where $f:\mathcal{X}\times\mathcal{U}\to\mathcal{X}$ is the global dynamics function. We consider the partially observable setting, where each agent has a limited communication radius $R>0$ and can only communicate with other agents or observe the environment within its communication region. Denote $o_{i}^{k}=O_{i}(x^{k})\in\mathcal{O}\subseteq\mathbb{R}^{n_{o}}$ as the vector of the information observed by agent $i$ at the time step $k$, where $O_{i}:\mathcal{X}\to\mathcal{O}$ is an encoding function of the information shared from neighbors of agent $i$ and the observed data of the environment. We allow multi-hop communication between agents, so an agent may communicate with another agent outside its communication region if a communication path exists between them.

其中 $f:\mathcal{X}\times\mathcal{U}\to\mathcal{X}$ 为全局动力学。我们考虑部分可观测设定：每个智能体有通信半径 $R>0$，只能与通信区域内的其他智能体通信或观测环境。记 $o_{i}^{k}=O_{i}(x^{k})\in\mathcal{O}\subseteq\mathbb{R}^{n_{o}}$ 为智能体 $i$ 在时刻 $k$ 观测到的信息向量，$O_{i}:\mathcal{X}\to\mathcal{O}$ 编码来自邻居的共享信息与环境观测。我们允许多智能体间多跳通信，因而若存在通信路径，智能体也可与通信半径外的智能体通信。

Let the avoid/unsafe set of agent $i$ be $\mathcal{A}_{i}\coloneqq\{o_{i}\in\mathcal{O}:h_{i}(o_{i})>0\}$, for some function $h_{i}:\mathcal{O}\to\mathbb{R}$. The global avoid set is then defined as $\mathcal{A}\coloneqq\{x\in\mathcal{X}:h(x)>0\}$, where $h(x)=\max_{i}h_{i}(o_{i})=\max_{i}h_{i}(O_{i}(x))$. In other words, $\exists i,\;\mathrm{s.t.}\;o_{i}\in\mathcal{A}_{i}\iff x\in\mathcal{A}$. Given a global cost function $l:\mathcal{X}\times\mathcal{U}\to\mathbb{R}$ describing the task for the agents to accomplish[^3], we aim to find distributed control policies $\pi_{i}:\mathcal{O}\to\mathcal{U}_{i}$ such that starting from any given initial states $x^{0}\notin\mathcal{A}$, the policies keep the agents outside the avoid set $\mathcal{A}$ and minimize the infinite horizon cost. In other words, denoting $\pi:\mathcal{X}\to\mathcal{U}$ as the joint policy such that $\pi(x)=[\pi_{1}(o_{1});\dots;\pi_{N}(o_{N})]=[\pi_{1}(O_{1}(x));\dots;\pi_{N}(O_{N}(x))]$, we aim to solve the following infinite-horizon MASOCP for a given initial state $x^{0}$:

令智能体 $i$ 的避免/不安全集为 $\mathcal{A}_{i}\coloneqq\{o_{i}\in\mathcal{O}:h_{i}(o_{i})>0\}$，其中 $h_{i}:\mathcal{O}\to\mathbb{R}$。全局避免集定义为 $\mathcal{A}\coloneqq\{x\in\mathcal{X}:h(x)>0\}$，其中 $h(x)=\max_{i}h_{i}(o_{i})=\max_{i}h_{i}(O_{i}(x))$。换言之，$\exists i,\;\mathrm{s.t.}\;o_{i}\in\mathcal{A}_{i}\iff x\in\mathcal{A}$。给定描述任务的全局代价 $l:\mathcal{X}\times\mathcal{U}\to\mathbb{R}$[^3]，我们希望找到分布式控制策略 $\pi_{i}:\mathcal{O}\to\mathcal{U}_{i}$，使得从任意给定初态 $x^{0}\notin\mathcal{A}$ 出发，策略使智能体保持在避免集 $\mathcal{A}$ 之外并最小化无限时域代价。记联合策略 $\pi:\mathcal{X}\to\mathcal{U}$ 满足 $\pi(x)=[\pi_{1}(o_{1});\dots;\pi_{N}(o_{N})]=[\pi_{1}(O_{1}(x));\dots;\pi_{N}(O_{N}(x))]$，即对给定初态 $x^{0}$ 求解如下无限时域 MASOCP：

$$\displaystyle\hskip-10.00002pt\min_{\{\pi_{i}\}_{i=1}^{N}}\quad \\ \displaystyle\sum_{k=0}^{\infty}l(x^{k},\pi(x^{k})) \\ \displaystyle\mathrm{s.t.}\quad \\ \displaystyle h_{i}(O_{i}(x^{k}))\leq 0, \\ \displaystyle\hskip-3.99994pt\forall i\in\{1,\dots,N\},k\geq 0, \\ \displaystyle x^{k+1}=f(x^{k},\pi(x^{k})), \\ \displaystyle k\geq 0. \tag{2a}$$

Note that the safety constraint (2b) differs from the average constraints considered in CMDPs [3]. Consequently, instead of allowing safety violations to occur as long as the mean constraint violation is below a threshold, this formulation disallows any constraint violation. From hereon, we omit the dynamics constraint (2c) for conciseness.

注意安全约束 (2b) 不同于 CMDP 中考虑的平均约束 [3]。因此，该表述不允许任何约束违反，而不是只要平均违反低于阈值即可。下文为简洁起见省略动力学约束 (2c)。

III-B Epigraph form

III-B 上图形式

Existing methods are unable to solve (2) well. This has been observed previously in the single-agent setting [82, 89, 66, 24]. We show later that the poor performance of methods that tackle the CMDP setting to the constrained problem (2) also translates to the multi-agent setting, as we observe a similar phenomenon in our experiments (Section V). Namely, although unconstrained MARL can be used to solve (2) using the penalty method [51], this does not perform well in practice, where a small penalty results in policies that violate constraints, and a large penalty results in higher total costs. The Lagrangian method [32] can solve the problem theoretically, but it suffers from unstable training and has poor performance in practice when the constraint violation threshold is zero [66, 24]. In this section, we introduce a new method of solving (2) that can mitigate the above problems by extending prior work [66] to the multi-agent setting.

现有方法难以很好求解 (2)。单智能体设定中已有观察 [82, 89, 66, 24]。我们后文表明，把面向 CMDP 的方法套到约束问题 (2) 上的不良表现也会传递到多智能体设定，实验中可见类似现象（第 V 节）。具体地，虽可用惩罚法 [51] 以无约束 MARL 求解 (2)，实践中表现不佳：惩罚过小则违约束，过大则总代价升高。拉格朗日方法 [32] 理论上可解，但在零违反阈值时训练不稳、实践表现差 [66, 24]。本节介绍一种通过把先前工作 [66] 扩展到多智能体来缓解上述问题的新求解途径。

Given a constrained optimization problem with objective function $J$ (e.g., $J=\sum_{k=0}^{\infty}l(x^{k},\pi(x^{k}))$ as in (2a)), and constraints $h$ (e.g., (2b)):

给定目标函数为 $J$（例如 (2a) 中 $J=\sum_{k=0}^{\infty}l(x^{k},\pi(x^{k}))$）、约束为 $h$（例如 (2b)）的约束优化问题：

$$\displaystyle\min_{{\pi}}\quad J({\pi})\qquad\mathrm{s.t.}\quad h({\pi})\leq 0, \tag{3}$$

its epigraph form [10] is given as

其上图形式 [10] 为

$$\displaystyle\min_{{\pi},z}\quad z\qquad\mathrm{s.t.}\quad h({\pi})\leq 0,\quad J({\pi})\leq z, \tag{4}$$

where $z\in\mathbb{R}$ is an auxiliary variable. In other words, we add a constraint to enforce $z$ as an upper bound of the cost $J(\pi)$, then minimize $z$. The solution to (4) is identical to the original problem (3) [10]. Furthermore, (4) is equivalent [66] to

其中 $z\in\mathbb{R}$ 为辅助变量。换言之，增加约束使 $z$ 成为代价 $J(\pi)$ 的上界，再最小化 $z$。(4) 的解与原问题 (3) 相同 [10]。进一步地，(4) 等价于 [66]

$$\displaystyle\min_{z} \\ \displaystyle\quad z \\ \displaystyle\mathrm{s.t.} \\ \displaystyle\quad\min_{{\pi}}J_{z}({\pi},z)\coloneqq\max\{h({\pi}),J({\pi})-z\}\leq 0 \tag{5a}$$

As a result, the original constrained problem (3) is decomposed into the following two subproblems:

于是原约束问题 (3) 分解为如下两个子问题：

1. An unconstrained inner problem (5b), where, given an arbitrary desired cost upper bound $z$, we find ${\pi}$ such that $J_{z}({\pi},z)$ is minimized, i.e., best satisfies the constraints $h\leq 0$ and $J\leq z$.

1. 无约束内层问题 (5b)：给定任意期望代价上界 $z$，寻找使 $J_{z}({\pi},z)$ 最小的 ${\pi}$，即尽可能满足 $h\leq 0$ 与 $J\leq z$。

2. A $1$-dimensional constrained outer problem (5a) over $z$, which finds the smallest cost upper bound $z$ such that $z$ is indeed a cost upper bound ($J\leq z)$ and the constraints of the original problem $h({\pi})\leq 0$ holds.

2. 关于 $z$ 的一维约束外层问题 (5a)：寻找最小的代价上界 $z$，使 $z$ 确为代价上界（$J\leq z$）且原问题约束 $h({\pi})\leq 0$ 成立。

Comparison with the Lagrangian method. Another popular way to solve MASOCP (2) is the Lagrangian method [32]. However, it suffers from unstable training when considering the zero constraint violation [66, 35] setting. More specifically, this refers to the case with constraints $\sum_{k=0}^{\infty}c(x^{k})\leq 0$ for $c:\mathcal{X}\to\mathbb{R}_{\geq 0}$ non-negative. Since $h$ can be negative, we can convert our problem setting (3) to the zero constraint violation setting by taking $c(x)\coloneqq\max\{0,h(x)\}$. Then, (3) reads as

与拉格朗日方法的比较。 求解 MASOCP (2) 的另一流行途径是拉格朗日方法 [32]，但在零约束违反设定下训练不稳 [66, 35]。具体指约束形如 $\sum_{k=0}^{\infty}c(x^{k})\leq 0$ 且 $c:\mathcal{X}\to\mathbb{R}_{\geq 0}$ 非负的情形。由于 $h$ 可为负，可取 $c(x)\coloneqq\max\{0,h(x)\}$ 把问题设定 (3) 转到零违反设定。于是 (3) 写为

$$\min_{\pi}\quad J(\pi)\qquad\mathrm{s.t.}\quad\sum_{k=0}^{\infty}\max\{0,h(x^{k})\}\leq 0. \tag{6}$$

The Lagrangian form of (6) is then

于是 (6) 的拉格朗日形式为

$$\max_{\lambda\geq 0}\min_{\pi}\quad J_{\lambda}(\pi,\lambda)\coloneqq J(\pi)+\lambda\sum_{k=0}^{\infty}\max\{h(x^{k}),0\}, \tag{7}$$

where $\lambda$ is the Lagrangian multiplier and is updated with gradient ascent. However, $\frac{\partial}{\partial\lambda}J_{\lambda}({\pi},\lambda)=\sum_{k=0}^{\infty}\max\{h(x^{k}),0\}\geq 0$, so $\lambda$ continuously increases and never decreases. As $\frac{\partial}{\partial{\pi}}J_{\lambda}({\pi},\lambda)$ scales linearly in $\lambda$ when $h(x^{k})>0$ for some $k$, a large value of $\lambda$ causes a large gradient w.r.t $x$, and makes the training unstable. Note that for the epigraph form, since $z$ does not multiply with the cost function $J$ but is added to $J$ in (5b), the gradient $\frac{\partial}{\partial{\pi}}J_{z}({\pi},z)$ does not scale with the value of $z$ resulting in more stable training. We validate this in our experiments (Section V).

其中 $\lambda$ 为拉格朗日乘子，用梯度上升更新。然而 $\frac{\partial}{\partial\lambda}J_{\lambda}({\pi},\lambda)=\sum_{k=0}^{\infty}\max\{h(x^{k}),0\}\geq 0$，故 $\lambda$ 只增不减。当某些 $k$ 上 $h(x^{k})>0$ 时，$\frac{\partial}{\partial{\pi}}J_{\lambda}({\pi},\lambda)$ 随 $\lambda$ 线性放大，过大的 $\lambda$ 使相对策略的梯度过大，训练不稳。对上图形式，$z$ 在 (5b) 中是加到 $J$ 上而非与代价相乘，因而 $\frac{\partial}{\partial{\pi}}J_{z}({\pi},z)$ 不随 $z$ 放大，训练更稳。我们在实验（第 V 节）中验证了这一点。

IV Distributed epigraph form multi-agent reinforcement learning

IV 分布式上图形式多智能体强化学习

In this section, we propose the Distributed epigraph form MARL (Def-MARL) algorithm to solve MASOCP (2) using MARL. First, we transfer MASOCP (2) to its epigraph form with an auxiliary variable $z$ to model the desired cost upper bound. The epigraph form includes an inner problem and an outer problem. For distributed execution, we provide a theoretical result that the outer problem can be solved distributively by each agent. This allows Def-MARL to fit the CTDE paradigm, where in centralized training, the agents’ policies are trained together given the desired cost upper bound $z$, and in distributed execution, the agents distributively find the smallest cost upper bound $z$ that ensures safety.

本节提出用 MARL 求解 MASOCP (2) 的 Distributed epigraph form MARL（Def-MARL）算法。首先把 MASOCP (2) 写成带辅助变量 $z$（期望代价上界）的上图形式，包含内层与外层问题。为支持分布式执行，我们给出理论结果：外层问题可由各智能体分布式求解。于是 Def-MARL 符合 CTDE：集中训练时在给定代价上界 $z$ 下联合训练各智能体策略；分布执行时各智能体分布式寻找保证安全的最小代价上界 $z$。

IV-A Epigraph form for MASOCP

IV-A MASOCP 的上图形式

To rewrite MASOCP (2) into its epigraph form (5), we first define the cost-value function $V^{l}$ for a joint policy $\pi$ using the standard optimal control notation [6]:

为把 MASOCP (2) 写成上图形式 (5)，先用标准最优控制记号 [6] 定义联合策略 $\pi$ 的代价价值函数 $V^{l}$：

$$V^{l}(x^{\tau};\pi)\coloneqq\sum_{k\geq\tau}l(x^{k},\pi(x^{k})). \tag{8}$$

We also define the constraint-value function $V^{h}$ as the maximum constraint violation:

同时把约束价值函数 $V^{h}$ 定义为最大约束违反：

$$\displaystyle V^{h}(x^{\tau};\pi) \\ \displaystyle\coloneqq\max_{k\geq\tau}h(x^{k})=\max_{k\geq\tau}\max_{i}h_{i}(o_{i}^{k}) \\ \displaystyle=\max_{i}\max_{k\geq\tau}h_{i}(o_{i}^{k})=\max_{i}V_{i}^{h}(o_{i}^{\tau};\pi).$$

Here, we interchange the $\max$ to define the local per-agent functions $V_{i}^{h}(o_{i}^{\tau};\pi)=\max_{k\geq\tau}h_{i}(o_{i}^{k})$. Each $V_{i}^{h}$ uses only the agent’s local observation and thus is distributed. We now introduce the auxiliary variable $z$ for the desired upper bound of $V^{l}$, allowing us to restate (2) concisely as

这里交换 $\max$ 以定义局部按智能体的函数 $V_{i}^{h}(o_{i}^{\tau};\pi)=\max_{k\geq\tau}h_{i}(o_{i}^{k})$。每个 $V_{i}^{h}$ 仅用智能体局部观测，因而是分布式的。引入期望上界 $V^{l}$ 的辅助变量 $z$ 后，可将 (2) 简洁重述为

$$\displaystyle\min_{\{\pi_{i}\}_{i=1}^{N}}\quad V^{l}(x^{0};\pi)\qquad\mathrm{s.t.}\quad V^{h}(x^{0};\pi)\leq 0. \tag{10}$$

The epigraph form (5) of (10) then takes the form

于是 (10) 的上图形式 (5) 写为

$$\displaystyle\min_{z} \\ \displaystyle\quad z\vphantom{\underbrace{\max\big\{\big\}}_{\coloneqq V}} \\ \displaystyle\mathrm{s.t.} \\ \displaystyle\quad\min_{\{\pi_{i}\}_{i=1}^{N}}\,\underbrace{\max\big\{\max_{i}V_{i}^{h}(o_{i}^{\tau};\pi),V^{l}(x^{\tau};\pi)-z\big\}}_{\coloneqq V(x^{0},z;\pi)}\leq 0. \tag{11a}$$

By interpreting the left-hand side of (11b) as a new policy optimization problem, we define the total value function $V$ as the objective function to (11b). This can be simplified as

把 (11b) 左侧解释为新的策略优化问题，我们定义总价值函数 $V$ 作为 (11b) 的目标。可简化为

$$\displaystyle V(x^{\tau},z;\pi) \\ \displaystyle=\max\{\max_{i}V_{i}^{h}(o_{i}^{\tau};\pi),V^{l}(x^{\tau};\pi)-z\} \\ \displaystyle=\max_{i}\max\{V_{i}^{h}(o_{i}^{\tau};\pi),V^{l}(x^{\tau};\pi)-z\} \\ \displaystyle=\max_{i}V_{i}(x^{\tau},z;\pi),$$

Again, we interchange the $\max$ to define $V_{i}(x^{\tau},z;\pi)=\max\{V_{i}^{h}(o_{i}^{\tau};\pi),V^{l}(x^{\tau};\pi)-z\}$ as the per-agent total value function. Using this to rewrite (11) then yields

再次交换 $\max$，定义按智能体总价值 $V_{i}(x^{\tau},z;\pi)=\max\{V_{i}^{h}(o_{i}^{\tau};\pi),V^{l}(x^{\tau};\pi)-z\}$。据此重写 (11) 得到

$$\displaystyle\min_{z} \\ \displaystyle\quad z\vphantom{\Big(} \\ \displaystyle\mathrm{s.t.} \\ \displaystyle\quad{\min_{\pi}}\max_{i}V_{i}(x^{0},z;\pi)\leq 0.\vphantom{\Big(} \tag{13a}$$

This decomposes the original problem (2) into an unconstrained inner problem (13b) over policy $\pi$ and a constrained outer problem (13a) over $z$. During offline training, we solve the inner problem (13b): for parameter $z$, find the optimal policy $\pi(\cdot,z)$ to minimize $V(x^{0},z;\pi)$. Note that the optimal policy of the inner problem depends on $z$. During execution, we solve the outer problem (13a) online to get the minimal $z$ that satisfies constraint (13b). Using this $z$ in the $z$-conditioned policy $\pi(\cdot,z)$ found in the inner problem gives us the optimal policy for the overall epigraph form MASOCP (EF-MASOCP).

这将原问题 (2) 分解为关于策略 $\pi$ 的无约束内层问题 (13b) 与关于 $z$ 的约束外层问题 (13a)。离线训练时求解内层 (13b)：对参数 $z$，找最优策略 $\pi(\cdot,z)$ 以最小化 $V(x^{0},z;\pi)$；注意最优策略依赖 $z$。执行时在线求解外层 (13a) 得到满足约束 (13b) 的最小 $z$；把该 $z$ 代入内层得到的 $z$-条件策略 $\pi(\cdot,z)$，即得到整体上图形式 MASOCP（EF-MASOCP）的最优策略。

Fig. 1: Def-MARL algorithm. Randomly sampled initial states and $z^{0}$ are used to collect trajectories in $x$ and $z$ using the current policy $\pi$. In the centralized training (orange blocks), distributed constraint-value functions $V^{h}_{i}$ and policies $\pi_{i}$ and a centralized cost-value function $V^{l}$ are jointly trained. During distributed execution (green blocks), the distributed $V^{h}_{i}$ are used to solve the outer problem (15b) to compute the optimal $z_{i}$, which is used in each agent’s $z$-conditioned policy.

图 1：Def-MARL 算法。 用随机采样的初态与 $z^{0}$，在当前策略 $\pi$ 下采集 $x$ 与 $z$ 轨迹。集中训练（橙色块）中，联合训练分布式约束价值函数 $V^{h}_{i}$、策略 $\pi_{i}$ 与中心化代价价值函数 $V^{l}$。分布执行（绿色块）中，用分布式 $V^{h}_{i}$ 求解外层问题 (15b) 得到最优 $z_{i}$，再送入各智能体的 $z$-条件策略。

To solve the inner problem (13b), the total value function $V$ must be amenable to dynamic programming, which we show in the following proposition.

为求解内层 (13b)，总价值 $V$ 须适合动态规划，如下命题所示。

Proposition 1

Dynamic programming can be applied to EF-MASOCP (13), resulting in

命题 1

动态规划可用于 EF-MASOCP (13)，得到

$$\displaystyle V(x^{k},z^{k};\pi) \\ \displaystyle=\max\{h(x^{k}),V(x^{k+1},z^{k+1};\pi)\}, \\ \displaystyle\quad z^{k+1} \\ \displaystyle=z^{k}-l(x^{k},\pi(x^{k})).$$

The proof of 1 is provided in Appendix A following the proof of the single-agent version [66]. In other words, for a given cost upper bound $z^{k}$, the value function $V$ at the current state $x^{k}$ can be computed using the value function at the next state $x^{k+1}$ but with a different cost upper bound $z^{k+1}=z^{k}-l(x^{k},\pi(x^{k}))$ which itself is a function of $z^{k}$. This can be interpreted as a “dynamics” for the cost upper bound $z$. Intuitively, if we wish to satisfy the upper bound $z^{k}$ but suffer a cost $l(x^{k},\pi(x^{k}))$, then the upper bound at the next time step should be smaller by $l(x^{k},\pi(x^{k}))$ so that the total cost from $x^{k}$ remains upper bounded by $z^{k}$. Additional discussion on 1 is provided in Appendix C.

命题 1 的证明见附录 A，沿用单智能体版本的证明 [66]。换言之，给定代价上界 $z^{k}$，当前状态 $x^{k}$ 的价值可用下一状态 $x^{k+1}$ 的价值计算，但代价上界变为 $z^{k+1}=z^{k}-l(x^{k},\pi(x^{k}))$，其本身是 $z^{k}$ 的函数。这可解释为代价上界 $z$ 的一种“动力学”：若希望满足上界 $z^{k}$ 却已付出代价 $l(x^{k},\pi(x^{k}))$，则下一时刻上界应减小同样数量，以使从 $x^{k}$ 起的总代价仍被 $z^{k}$ 上界约束。关于命题 1 的更多讨论见附录 C。

Remark 1(Effect of $z$ on the learned policy)

From (12), for a fixed $x$ and $\pi$, observe that for $z$ large enough (i.e., ${V^{l}(x;\pi)}-z$ is small enough), we have $V(x,z;\pi)=V^{h}(x;\pi)$. Consequently, taking a gradient step on $V(x,z;\pi)$ equals taking a gradient step on $V^{h}(x;\pi)$, which reduces the constraint violation. Otherwise, $V(x,z;\pi)=V^{l}(x;\pi)-z$. Taking gradient steps on $V(x,z;\pi)$ equals taking gradient steps on $V^{l}(x;\pi)$, which reduces the total cost.

注 1（$z$ 对所学策略的影响）

由 (12)，对固定 $x$ 与 $\pi$，当 $z$ 足够大（即 ${V^{l}(x;\pi)}-z$ 足够小）时，$V(x,z;\pi)=V^{h}(x;\pi)$。因而对 $V(x,z;\pi)$ 做梯度步等价于对 $V^{h}(x;\pi)$ 做梯度步，从而减小约束违反。否则 $V(x,z;\pi)=V^{l}(x;\pi)-z$，对 $V$ 做梯度步等价于对 $V^{l}$ 做梯度步，从而减小总代价。

IV-B Solving the inner problem using MARL

IV-B 用 MARL 求解内层问题

Following So and Fan 2023, we solve the inner problem using centralized training with proximal policy optimization (PPO) [63]. We use a graph neural network (GNN) backbone for the $z$-conditioned policy $\pi_{\theta}(o_{i},z)$, cost-value function $V^{l}_{\phi}(x,z)$, and the constraint-value function $V^{h}_{\psi}(o_{i},z)$ with parameters $\theta$, $\phi$, and $\psi$, respectively. Note that other neural network (NN) structures can be used as well. The implementation details are introduced in Appendix E.

沿用 So 与 Fan 2023，我们用近端策略优化（PPO）[63] 做集中训练以求解内层问题。$z$-条件策略 $\pi_{\theta}(o_{i},z)$、代价价值 $V^{l}_{\phi}(x,z)$ 与约束价值 $V^{h}_{\psi}(o_{i},z)$ 均以图神经网络（GNN）为骨干，参数分别为 $\theta$、$\phi$、$\psi$；也可使用其他神经网络结构。实现细节见附录 E。

Policy and value function updates. During centralized training, the NNs are trained to solve the inner problem (13b), i.e., for a randomly sampled $z$, find policy $\pi(\cdot,z)$ that minimizes the total value function $V(x^{0},z;\pi)$. We follow MAPPO [80] to train the NNs. Specifically, when calculating the advantage with the generated advantage estimation (GAE) [62] for the $i$-th agent, $A_{i}$ [63], instead of using the cost function $V^{l}$ [80], we apply the decomposed total value function $\max\{V^{h}_{\psi}(o_{i},z),V^{l}_{\phi}(x,z)-z\}$. We perform trajectory rollouts following the dynamics for $x$ (1) and $z$ (14) using the learned policy $\pi_{\theta}$, starting from random sampled $x^{0}$ and $z^{0}$. After collecting the trajectories, we train the cost-value function $V^{l}_{\phi}$ and the constraint-value function $V^{h}_{\psi}$ via regression and use the PPO policy loss to update the $z$-conditioned policy $\pi_{\theta}$.

策略与价值函数更新。 集中训练时，神经网络用于求解内层 (13b)：对随机采样的 $z$，找最小化总价值 $V(x^{0},z;\pi)$ 的策略 $\pi(\cdot,z)$。我们按 MAPPO [80] 训练。具体地，用广义优势估计（GAE）[62] 计算第 $i$ 个智能体优势 $A_{i}$ [63] 时，不用代价函数 $V^{l}$ [80]，而用分解后的总价值 $\max\{V^{h}_{\psi}(o_{i},z),V^{l}_{\phi}(x,z)-z\}$。从随机采样的 $x^{0}$、$z^{0}$ 出发，用所学策略 $\pi_{\theta}$ 按 $x$ 动力学 (1) 与 $z$ 动力学 (14) 做轨迹 rollout；收集轨迹后，用回归训练 $V^{l}_{\phi}$ 与 $V^{h}_{\psi}$，并用 PPO 策略损失更新 $z$-条件策略 $\pi_{\theta}$。

(a) Target

IV-C Solving the outer problem during distributed execution

IV-C 分布执行时求解外层问题

During execution, we solve the outer problem of EF-MASOCP (13) online. However, the outer problem is still centralized because the constraint (13b) requires the centralized cost-value function $V^{l}$. To achieve a distributed policy during execution, we introduce the following theoretical result:

执行时我们在线求解 EF-MASOCP (13) 的外层问题。但外层仍是中心化的，因为约束 (13b) 需要中心化代价价值 $V^{l}$。为在执行期得到分布式策略，我们引入如下理论结果：

Theorem 1

Assume no two unique values of $z$ achieves the same unique cost. Then, the outer problem of EF-MASOCP (5a) is equivalent to the following:

定理 1

假设不存在两个不同的 $z$ 取得相同的唯一代价。则 EF-MASOCP 外层问题 (5a) 等价于：

$$\displaystyle z \ \displaystyle=\max_{i}z_{i} \ \displaystyle\begin{split}z_{i}&=\min_{z^{\prime}}\quad z^{\prime}\
&\hskip 16.00008pt\mathrm{s.t.}\quad V_{i}^{h}(o_{i};\pi(\cdot,z^{\prime}))\leq 0,\quad i=1,\cdots,N.\end{split} \tag{15a}$$

The proof is provided in Appendix B. 1 enables computing $z$ without the use of the centralized $V^{l}$ during execution. Specifically, each agent $i$ solves the local problem (15b) for $z_{i}$, which is a 1-dimensional optimization problem and can be efficiently solved using root-finding methods (e.g., [12]) as in [66], then communicates $z_{i}$ among the other agents to obtain the maximum (15a). One challenge is that this maximum may not be computable if the agents are not connected. However, in our problem setting, if one agent is not connected, it does not appear in the observations $o$ of other connected agents. Therefore, it would not contribute to the constraint-value function $V^{h}$ of other agents. As a result, it is sufficient for only the connected agents to communicate their $z_{i}$. Furthermore, we observe experimentally that the agents can achieve low cost while maintaining safety even if $z_{i}$ is not communicated (see Section V-C). Thus, we do not include $z_{i}$ communication for our method. The overall framework of Def-MARL is provided in Figure 1.

证明见附录 B。定理 1 使得执行期可不使用中心化 $V^{l}$ 来计算 $z$。具体地，每个智能体 $i$ 求解局部问题 (15b) 得到 $z_{i}$（一维优化，可用求根方法高效求解，例如 [12]，同 [66]），再与其他智能体通信 $z_{i}$ 以取最大 (15a)。挑战在于：若智能体不连通，该最大值可能算不出。但在我们的问题设定中，若某智能体不连通，它不会出现在其他已连通智能体的观测 $o$ 中，因而不会贡献于其他智能体的约束价值 $V^{h}$；因此只需已连通智能体通信其 $z_{i}$ 即可。此外实验观察到，即使不通信 $z_{i}$，智能体仍可在保持安全的同时取得低代价（见第 V-C 节），故本方法不纳入 $z_{i}$ 通信。Def-MARL 整体框架见图 1。

Fig. 3: Comparison on modified MPE ($N=3$) and Safe Multi-agent MuJoCo. Def-MARL is consistently closest to the top-left corner in all environments, achieving low cost with near $100\%$ safety rate. The dots show the mean values and the error bars show one standard deviation.

图 3：改进 MPE（$N=3$）与 Safe Multi-agent MuJoCo 上的比较。Def-MARL 在全部环境中始终最接近左上角，以接近 $100\%$ 的安全率取得低代价。圆点为均值，误差棒为一倍标准差。

Dealing with estimation errors. Since there may be errors estimating $V^{h}$ using NN, we can reduce the resulting safety violation by modifying $h$ to add a buffer region. Specifically, for a constant $\nu>0$, we modify $h$ such that $h\geq\nu$ when the constraints are violated and $h\leq-\nu$ otherwise. We then modify (15b) to $V^{h}_{\psi}(o_{i},z_{i})\leq-\xi$, where $\xi\in[0,\nu]$ is a hyperparameter (where we want $\xi\approx\nu$ to emphasize more on safety). This makes $z$ more robust to estimation errors of $V^{h}$. We study the importance of $\xi$ in Section V-C.

处理估计误差。 用神经网络估计 $V^{h}$ 可能有误差，可通过修改 $h$ 增加缓冲带来降低安全违反。具体地，对常数 $\nu>0$，使违反约束时 $h\geq\nu$、否则 $h\leq-\nu$；再把 (15b) 改为 $V^{h}_{\psi}(o_{i},z_{i})\leq-\xi$，其中 $\xi\in[0,\nu]$ 为超参（希望 $\xi\approx\nu$ 以更强调安全）。这使 $z$ 对 $V^{h}$ 估计误差更鲁棒。我们在第 V-C 节研究 $\xi$ 的重要性。

V Simulation experiments

V 仿真实验

In this section, we design simulation experiments to answer the following research questions:

本节设计仿真实验以回答以下研究问题：

(Q1): Does Def-MARL satisfy the safety constraints and achieve low cost with constant hyperparameters across all environments?

(Q1)： Def-MARL 能否在固定超参下满足安全约束并取得低代价？

(Q2): Can Def-MARL achieve the global optimum of the original constrained optimization problem?

(Q2)： Def-MARL 能否达到原约束优化问题的全局最优？

(Q3): How stable is the training of Def-MARL?

(Q3)： Def-MARL 的训练稳定性如何？

(Q4): How well does Def-MARL scale to larger MAS?

(Q4)： Def-MARL 对更大规模 MAS 的扩展性如何？

(Q5): Does the learned policy from Def-MARL generalize to larger MAS?

(Q5)： Def-MARL 所学策略能否泛化到更大规模 MAS？

Details for the implementation, environments, and hyperparameters are provided in Appendix E.

实现、环境与超参细节见附录 E。

V-A Setup

V-A 设置

Environments. We evaluate Def-MARL in two sets of simulation environments: modified Multi-agent Particle Environments (MPE) [40], and Safe Multi-agent MuJoCo environments [32] (see Figure 2). In MPE, the agents are assumed to have double integrator dynamics with bounded continuous action spaces $[-1,1]^{2}$. We provide the full details of all tasks in Appendix E. To increase the difficulty of the tasks, we add $3$ static obstacles to these environments. For Safe Multi-agent MuJoCo environments, we consider Safe HalfCheetah 2x3 and Safe Coupled HalfCheetah 4x3. The agents must collaborate to make the cheetah run as fast as possible without colliding with a moving wall in front. To design the constraint function $h$, we let $\nu=0.5$ in all our experiments and $\xi=0.4$ when solving the outer problem.

环境。 我们在两套仿真环境中评估 Def-MARL：改进的多智能体粒子环境（MPE）[40]，以及 Safe Multi-agent MuJoCo [32]（见图 2）。MPE 中智能体为双积分器动力学，动作为有界连续空间 $[-1,1]^{2}$。全部任务细节见附录 E。为增加难度，我们在这些环境中加入 $3$ 个静态障碍。Safe Multi-agent MuJoCo 中考虑 Safe HalfCheetah 2x3 与 Safe Coupled HalfCheetah 4x3；智能体须协作使猎豹尽量快跑且不与前方移动墙碰撞。设计约束函数 $h$ 时，全部实验取 $\nu=0.5$，求解外层时取 $\xi=0.4$。

Baselines. We compare our algorithm with the state-of-the-art (SOTA) MARL algorithm InforMARL [51] with a constraint-penalized cost $l^{\prime}(x,u)=l(x,u)+\beta\max\{h(x),0\}$, where $\beta\in\{0.02,0.1,0.5\}$ is a penalty parameter, and denote this baseline as Penalty($\beta$). We also consider the SOTA safe MARL algorithm MAPPO-Lagrangian [30, 32][^4]. In addition, because the learning rate of the Lagrangian multiplier $\lambda$ is tiny ($10^{-7}$) in the official implementation of MAPPO-Lagrangian [32], the value of $\lambda$ during training will be largely determined by the initial value $\lambda_{0}$ of $\lambda$. We thus consider two $\lambda_{0}\in\{1,5\}$. Moreover, to compare the training stability, we consider increasing the learning rate of $\lambda$ in MAPPO-Lagrangian to $3\times 10^{-3}$.[^5] For a fair comparison, we reimplement MAPPO-Lagrangian using the same GNN backbone as used in Def-MARL and InforMARL, denoted as Lagr($\lambda_{0}$) and Lagr(lr) for the increased learning rate one. We run each method for the same number of update steps, which is large enough for all the methods to converge.

基线。 我们与约束惩罚代价 $l^{\prime}(x,u)=l(x,u)+\beta\max\{h(x),0\}$ 下的 SOTA MARL 算法 InforMARL [51] 比较，$\beta\in\{0.02,0.1,0.5\}$，记为 Penalty($\beta$)。另考虑 SOTA 安全 MARL 算法 MAPPO-Lagrangian [30, 32][^4]。由于官方实现 [32] 中拉格朗日乘子 $\lambda$ 的学习率极小（$10^{-7}$），训练中 $\lambda$ 很大程度上由初值 $\lambda_{0}$ 决定；我们考虑 $\lambda_{0}\in\{1,5\}$。为比较训练稳定性，还将 MAPPO-Lagrangian 中 $\lambda$ 学习率提高到 $3\times 10^{-3}$。[^5]公平起见，我们用与 Def-MARL、InforMARL 相同的 GNN 骨干重实现 MAPPO-Lagrangian，记为 Lagr($\lambda_{0}$) 与提高学习率的 Lagr(lr)。各方法更新步数相同，且足够使全部方法收敛。

(a) Def-MARL (ours)

(a) Def-MARL（本文）

Fig. 5: Training Curves in Target and Spread. Def-MARL has a smoother, more stable training curve compared to Lagr(lr). We plot the mean and shade the $\pm 1$ standard deviation.

图 5：Target 与 Spread 上的训练曲线。 相对 Lagr(lr)，Def-MARL 曲线更平滑、更稳定。绘制均值并以 $\pm 1$ 标准差着色。

Evaluation criteria. Following the objective of MASOCP, we use the cost and safety rate as the evaluation criteria for the performance of all algorithms. The cost is the cumulative cost over the trajectory $\sum_{k=0}^{T}l(x^{k},u^{k})$. The safety rate is defined as the ratio of agents that remain safe over the entire trajectory, i.e., $h_{i}(o^{k}_{i})\leq 0,\forall k$, over all agents. Unlike the CMDP setting, we do not report the mean of constraint violations over time but the violation of the hard safety constraints.

评价指标。 按 MASOCP 目标，用代价与安全率评价各算法。代价为轨迹累积代价 $\sum_{k=0}^{T}l(x^{k},u^{k})$；安全率为整条轨迹保持安全（即 $h_{i}(o^{k}_{i})\leq 0,\forall k$）的智能体比例。不同于 CMDP，我们不报告随时间平均的约束违反，而报告对硬安全约束的违反。

Fig. 6: Comparison on larger-scale modified MPE. Def-MARL remains in the top-left corner even when the number of agents increases. The dots show the mean and the error bars show one standard deviation.

图 6：更大规模改进 MPE 上的比较。 智能体数增加时 Def-MARL 仍处左上角。圆点为均值，误差棒为一倍标准差。

V-B Results

V-B 结果

We train all algorithms with $3$ different random seeds and test the converged policies on $32$ different initial conditions. As discussed in Section IV-C, we disable the communication of $z_{i}$ between agents (investigated in Section V-C). We draw the following conclusions.

各算法用 $3$ 个不同随机种子训练，并在 $32$ 个不同初态上测试收敛策略。如第 IV-C 节所述，我们关闭智能体间 $z_{i}$ 通信（第 V-C 节再研究）。结论如下。

(Q1): Def-MARL achieves the best performance with constant hyperparameters across all environments. First, we plot the safety rate (y-axis) and cumulative cost (x-axis) for each algorithm in Figure 3. Thus, the closer an algorithm is to the top-left corner, the better it performs. In both MPE and Safe Multi-agent MuJoCo environments, Def-MARL is always closest to the top-left corner, maintaining a low cost while having near $100\%$ safety rate. For the baselines Penalty and Lagr, their performance and safety are highly sensitive to their hyperparameters. While Penalty with $\beta=0.02$ and Lagr with $\lambda_{0}=1$ generally have low costs, they also have frequent constraint violations. With $\beta=0.5$ or $\lambda_{0}=5$, they prioritize safety but at the cost of high cumulative costs. Def-MARL, however, maintains a safety rate similar to the most conservative baselines (Penalty(0.5) and Lagr(5)) but has much lower costs. We point out that no single baseline method behaves considerably better on all the environments: the performance of the baseline methods varies wildly between environments, demonstrating the sensitivity of these algorithms to the choice of hyperparameters. On the contrary, Def-MARL, performs best in all environments, using a single set of constant hyperparameters, which demonstrates its insensitivity to the choice of hyperparameters.

(Q1)：Def-MARL 在全部环境用固定超参取得最佳表现。首先在图 3 中绘制各算法安全率（纵轴）与累积代价（横轴）；越靠近左上角越好。在 MPE 与 Safe Multi-agent MuJoCo 中，Def-MARL 始终最接近左上角，在接近 $100\%$ 安全率下保持低代价。基线 Penalty 与 Lagr 的性能与安全高度依赖超参：$\beta=0.02$ 或 $\lambda_{0}=1$ 时代价低但常违约束；$\beta=0.5$ 或 $\lambda_{0}=5$ 时偏重安全但累积代价高。Def-MARL 的安全率接近最保守基线（Penalty(0.5)、Lagr(5)），代价却低得多。没有单一基线在全部环境都明显更好：基线表现随环境剧烈变化，说明对超参敏感；相反 Def-MARL 用同一套固定超参在全部环境表现最佳，体现对超参不敏感。

(Q2): Def-MARL is able to reach the global optimum of the original problem. An important observation is that for Penalty and Lagr with a non-optimal $\lambda$, the cost function optimized in their training process is different from the original cost function. Consequently, they can have different optimal solutions compared to the original problem. Therefore, even if their training converges, they may not reach the optimal solution to the original problem. In Figure 4, the converged states of Def-MARL and four baselines are shown. Def-MARL reaches the original problem’s global optimum and covers all three goals. On the contrary, the optima of Penalty(0.02) and Lagr(1) are changed by the penalty term, so they choose to leave one agent behind to have a lower safety penalty. With an even more significant penalty, the optima of Penalty(0.5) and Lagr(5) are changed dramatically, and they forget the goal entirely and only focus on safety.

(Q2)：Def-MARL 能达到原问题的全局最优。重要观察是：对非最优 $\lambda$ 的 Penalty 与 Lagr，其训练优化的代价函数与原代价不同，因而最优解也可能不同于原问题；即便训练收敛，也未必到达原问题最优。图 4 展示 Def-MARL 与四条基线的收敛状态：Def-MARL 达到原问题全局最优并覆盖全部三个目标；Penalty(0.02) 与 Lagr(1) 的最优被惩罚项改变，选择留下一个智能体以降低安全惩罚；惩罚更大时，Penalty(0.5) 与 Lagr(5) 的最优被大幅改变，完全忘记目标只顾安全。

# Agent	32	128	512
Safety rate	$99.8\pm 0.2$	$99.6\pm 0.4$	$99.5\pm 0.3$
Cost	$-0.387\pm 0.029$	$-0.408\pm 0.015$	$-0.410\pm 0.009$

TABLE I: Policy Generalization. Testing Def-MARL on Target with more agents after training with $N=8$ agents.

# Agent	32	128	512
Safety rate	$99.8\pm 0.2$	$99.6\pm 0.4$	$99.5\pm 0.3$
Cost	$-0.387\pm 0.029$	$-0.408\pm 0.015$	$-0.410\pm 0.009$

表 I：策略泛化。 以 $N=8$ 训练后，在更多智能体的 Target 上测试 Def-MARL。

Environment	No communication $(z\leftarrow z_{i})$	Communication ($z=\max_{i}z_{i}$)
Safety rate	Cost	Safety rate	Cost
Target	$97.9\pm 1.5$	$0.196\pm 0.108$	$96.9\pm 3.0$	$0.214\pm 0.141$
Spread	$99.0\pm 0.9$	$0.162\pm 0.144$	$98.6\pm 1.3$	$0.171\pm 0.128$
Formation	$98.3\pm 1.0$	$0.123\pm 0.940$	$98.3\pm 1.8$	$0.126\pm 0.100$
Line	$98.6\pm 0.5$	$0.117\pm 0.540$	$98.3\pm 0.5$	$0.121\pm 0.630$
Corridor	$97.9\pm 1.8$	$0.247\pm 0.390$	$98.6\pm 1.9$	$0.255\pm 0.470$
ConnectSpread	$97.9\pm 1.7$	$0.324\pm 0.187$	$99.0\pm 0.8$	$0.339\pm 0.201$

$\xi$	Safety rate	Cost
$0.5$	$100.0\pm 0.0$	$0.127\pm 0.061$
$0.4$	$98.6\pm 0.5$	$0.117\pm 0.540$
$0.2$	$96.5\pm 0.5$	$0.108\pm 0.044$
$0.0$	$93.4\pm 0.020$	$0.102\pm 0.035$

TABLE II: Effect of $z_{i}$ communication (Section IV-C) in different environments.

Environment	No communication $(z\leftarrow z_{i})$	Communication ($z=\max_{i}z_{i}$)
Safety rate	Cost	Safety rate	Cost
Target	$97.9\pm 1.5$	$0.196\pm 0.108$	$96.9\pm 3.0$	$0.214\pm 0.141$
Spread	$99.0\pm 0.9$	$0.162\pm 0.144$	$98.6\pm 1.3$	$0.171\pm 0.128$
Formation	$98.3\pm 1.0$	$0.123\pm 0.940$	$98.3\pm 1.8$	$0.126\pm 0.100$
Line	$98.6\pm 0.5$	$0.117\pm 0.540$	$98.3\pm 0.5$	$0.121\pm 0.630$
Corridor	$97.9\pm 1.8$	$0.247\pm 0.390$	$98.6\pm 1.9$	$0.255\pm 0.470$
ConnectSpread	$97.9\pm 1.7$	$0.324\pm 0.187$	$99.0\pm 0.8$	$0.339\pm 0.201$

$\xi$	Safety rate	Cost
$0.5$	$100.0\pm 0.0$	$0.127\pm 0.061$
$0.4$	$98.6\pm 0.5$	$0.117\pm 0.540$
$0.2$	$96.5\pm 0.5$	$0.108\pm 0.044$
$0.0$	$93.4\pm 0.020$	$0.102\pm 0.035$

表 II：不同环境中 $z_{i}$ 通信的影响（第 IV-C 节）。

(Q3): Training of Def-MARL is more stable. To compare the training stability of Def-MARL and the Lagrangian method Lagr(lr), we plot their cost and safety rate during training in Figure 5. Def-MARL has a smoother curve compared to Lagr(lr), supporting our theoretical analysis in Section III-B. Due to space limits, the plots for other environments and other baseline methods are provided in Section E-D.

(Q3)：Def-MARL 训练更稳定。 为比较 Def-MARL 与拉格朗日方法 Lagr(lr) 的训练稳定性，在图 5 绘制训练中的代价与安全率。相对 Lagr(lr)，Def-MARL 曲线更平滑，支持第 III-B 节理论分析。篇幅所限，其他环境与基线曲线见第 E-D 节。

(Q4): Def-MARL can scale to more agents while maintaining high performance and safety, but is limited by GPU memory due to centralized training. We test the limits of Def-MARL on the number of agents during training by comparing all methods on $N=5,7$ with Formation and Line, and $N=8,12,16$ with Target (Figure 6). We were unable to increase $N$ further due to GPU memory limitations due to the use of centralized training. For this experiment, we omit Lagr(lr) as it has the worst performance in MPE with $N=3$. Def-MARL is closest to the upper left corner in all environments, and its performance does not decrease with an increasing number of agents.

(Q4)：Def-MARL 可扩展到更多智能体并保持高性能与安全，但受集中训练的 GPU 显存限制。我们在 Formation、Line 上比较 $N=5,7$，在 Target 上比较 $N=8,12,16$（图 6），以测试训练期智能体数上限；因集中训练的显存限制未能继续增大 $N$。本实验省略在 $N=3$ 的 MPE 上表现最差的 Lagr(lr)。Def-MARL 在全部环境最接近左上角，且性能不随智能体数增加而下降。

(Q5): The trained policy from Def-MARL generalizes to much larger MAS. To test the generalization capabilities of Def-MARL, we test a policy trained with $N=8$ on much larger MASs with up to $N=512$ on Target (Table I) with the same agent density to avoid distribution shift. Def-MARL maintains a high safety rate and low costs despite being applied on a MAS with $64$ times more agents.

(Q5)：Def-MARL 训练出的策略可泛化到大得多的 MAS。为测试泛化，我们将 $N=8$ 训练的策略在保持相同智能体密度（避免分布偏移）的 Target 上测到 $N=512$（表 I）。即便智能体数增大 $64$ 倍，Def-MARL 仍保持高安全率与低代价。

V-C Ablation studies

V-C 消融实验

Here we do ablation studies on the communication of $z_{i}$, and study the hyperparameter sensitivity of Def-MARL.

这里对 $z_{i}$ 通信做消融，并研究 Def-MARL 的超参敏感性。

Is communicating $z_{i}$ necessary? As introduced in Section IV-C, theoretically, all connected agents should communicate and reach a consensus on $z=\max_{i}z_{i}$. However, we observe in Section V-B that the agents can perform well even if agents take $z\leftarrow z_{i}$ without communicating to compute the maximum. We perform experiments on MPE ($N=3$) to understand the impact of this approximation in Table III and see that using the approximation does not result in much performance difference compared to communicating $z_{i}$ and using the maximum.

是否必须通信 $z_{i}$？ 如第 IV-C 节所述，理论上所有已连通智能体应通信并就 $z=\max_{i}z_{i}$ 达成一致。但第 V-B 节观察到，即使各智能体取 $z\leftarrow z_{i}$、不通信求最大，表现仍然良好。我们在 MPE（$N=3$）上实验以理解该近似的影响（表 III），发现相对通信 $z_{i}$ 并取最大，性能差异不大。

Varying $\xi$ in the outer problem. To robustify our approach against estimation errors in $V^{h}$, we solve for a $z_{i}$ that is slightly more conservative by modifying (15b) to $V_{\psi}^{h}(o_{i},z_{i})\leq-\xi$ (Section IV-C). We now perform experiments to study the effect of different choices of $\xi$ (Table III) on Line ($N=3$). The results show that higher values of $\xi$ result in higher safety rates and slightly higher costs, while the reverse is true for smaller $\xi$. This matches our intuition that modifying (15b) can help improve constraint satisfaction when the learned $V^{h}$ has estimation errors. We thus recommend choosing $\xi$ close to $\nu$. We also provide the sensitivity analysis on more hyperparameters in Appendix E.

外层问题中变化 $\xi$。 为增强对 $V^{h}$ 估计误差的鲁棒性，我们通过把 (15b) 改为 $V_{\psi}^{h}(o_{i},z_{i})\leq-\xi$ 来求略更保守的 $z_{i}$（第 IV-C 节）。现于 Line（$N=3$）上研究不同 $\xi$（表 III）：更大 $\xi$ 带来更高安全率与略高代价，更小 $\xi$ 则相反。这符合直觉——在所学 $V^{h}$ 有估计误差时，修改 (15b) 有助于约束满足。建议取 $\xi$ 接近 $\nu$。更多超参敏感性见附录 E。