Coordination Graphs for Constrained Multi-Agent Reinforcement Learning

📄 arXiv: 2606.02337v1 📥 PDF

作者: Santiago Amaya-Corredor, Miguel Calvo-Fullana, Anders Jonsson

分类: cs.AI

发布日期: 2026-06-01

备注: Accepted at the Reinforcement Learning Conference (RLC) 2026. 40 pages (12 main + 28 appendix), 5 figures, 16 tables, 7 theorems

💡 一句话要点

提出CG-CMARL框架，通过协调图和拉格朗日对偶解决约束多智能体强化学习问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 多智能体强化学习 约束优化 协调图 拉格朗日对偶 Max-Sum消息传递

📋 核心要点

  1. 约束多智能体强化学习面临联合动作空间爆炸和智能体间复杂约束建模的双重挑战。
  2. CG-CMARL框架结合协调图和拉格朗日对偶，将问题分解为成对区域，并使用共享Q函数进行学习。
  3. 实验表明，CG-CMARL在合作导航任务中优于现有基线，并能扩展到更大规模的智能体团队。

📝 摘要（中文）

本文提出了一种用于约束多智能体强化学习(CMARL)的协调图框架(CG-CMARL)，旨在解决联合动作空间随智能体数量呈指数增长以及智能体间耦合约束难以通过奖励塑造捕获的问题。CG-CMARL结合了协调图和拉格朗日对偶，将联合问题分解为成对区域，每个区域由一组共享的Q函数服务，包括一个用于主要目标和每个约束的Q函数，从而使学习模型的数量与智能体数量无关。在执行时，Max-Sum消息传递协调因子图上的动作，而拉格朗日乘子控制目标-约束的权衡，允许单个训练模型跟踪帕累托前沿而无需重新训练。论文提供了在温和条件下收敛保证，以及可分解为单独可解释来源的组合误差界限，每个来源都可追溯到特定的设计选择并可独立控制。在合作导航任务（其中最多10个智能体团队必须协调以达到目标位置同时满足成对约束）上的实验表明，该方法产生的帕累托前沿优于在固定奖励塑造比率下训练的基线，同时扩展到集中式方法变得难以处理的团队规模。

🔬 方法详解

问题定义：约束多智能体强化学习(CMARL)问题，其核心挑战在于随着智能体数量的增加，联合动作空间呈指数级增长，导致学习难度急剧增加。此外，智能体之间的约束关系，例如避免碰撞或保持特定距离，难以通过传统的奖励塑造方法有效建模，需要更精细的协调机制。现有方法通常难以在复杂约束下实现高效的策略学习和良好的可扩展性。

核心思路：CG-CMARL的核心思路是将复杂的联合问题分解为更易于管理的成对子问题，利用协调图来表示智能体之间的交互关系，并通过拉格朗日对偶将约束优化问题转化为无约束问题。这种分解降低了计算复杂度，使得算法能够扩展到更大规模的智能体团队。同时，拉格朗日乘子能够灵活地调整目标和约束之间的权衡，从而生成帕累托最优解。

技术框架：CG-CMARL的整体框架包括以下几个主要模块：1) 协调图构建：根据智能体之间的交互关系构建协调图，确定哪些智能体需要进行协调。2) 局部Q函数学习：为每个成对区域学习一组共享的Q函数，包括一个用于主要目标和每个约束的Q函数。3) Max-Sum消息传递：在执行时，使用Max-Sum消息传递算法在因子图上协调智能体的动作，以实现全局最优。4) 拉格朗日乘子更新：根据约束满足情况动态更新拉格朗日乘子，以调整目标和约束之间的权衡。

关键创新：CG-CMARL的关键创新在于将协调图与拉格朗日对偶相结合，从而能够有效地解决约束多智能体强化学习问题。与传统的集中式方法相比，CG-CMARL具有更好的可扩展性。与基于奖励塑造的方法相比，CG-CMARL能够更精确地建模智能体之间的约束关系。此外，通过拉格朗日乘子，CG-CMARL能够生成帕累托最优解，而无需重新训练模型。

关键设计：CG-CMARL的关键设计包括：1) 共享Q函数：为每个成对区域使用共享的Q函数，减少了需要学习的模型数量。2) Max-Sum消息传递：使用Max-Sum消息传递算法进行动作协调，保证了算法的收敛性。3) 拉格朗日乘子更新规则：设计了合适的拉格朗日乘子更新规则，以保证约束的满足和帕累托最优解的生成。具体的网络结构和损失函数选择取决于具体的任务，但通常会采用深度神经网络来近似Q函数，并使用TD-learning或类似的算法进行训练。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，CG-CMARL在合作导航任务中能够生成优于现有基线的帕累托前沿。与在固定奖励塑造比率下训练的基线相比，CG-CMARL能够更好地平衡目标和约束之间的权衡。此外，CG-CMARL能够扩展到包含10个智能体的团队，而集中式方法在这种规模下变得难以处理。这些结果表明，CG-CMARL是一种有效的约束多智能体强化学习方法。

🎯 应用场景

CG-CMARL可应用于各种需要多智能体协作且存在约束的场景，例如机器人编队、交通流量优化、资源分配、以及智能电网管理等。该方法能够有效地协调多个智能体的行为，同时满足各种约束条件，从而提高系统的整体性能和效率。未来的研究可以探索将CG-CMARL应用于更复杂的现实世界问题，并进一步提高其可扩展性和鲁棒性。

📄 摘要（原文）

Constrained Multi-agent reinforcement learning (CMARL) faces two intertwined challenges: the joint action space grows exponentially with the number of agents, and additional requirements couple agents in ways that reward structure alone does not capture. We introduce Coordination Graphs for Constrained Multi-Agent Reinforcement Learning (CG-CMARL), a framework that addresses both challenges by combining coordination graphs with Lagrangian duality. The system decomposes the joint problem into pairwise regions, each served by a set of shared Q-functions, one for the primary objective and one for each of the constraints, so that the number of learned models is independent of the number of agents. At execution time, Max-Sum message passing coordinates actions across the factor graph, while a Lagrangian multiplier controls the objective--constraint tradeoff, allowing a single trained model to trace a Pareto front without retraining. We provide convergence guarantees under mild conditions, together with a compositional error bound that decomposes into separate interpretable sources, each traceable to a specific design choice and independently controllable. Experiments on cooperative navigation tasks (where teams of up to 10 agents must coordinate to reach target positions while satisfying pairwise constraints) show that our method produces Pareto fronts dominating established baselines trained at fixed reward-shaping ratios, while scaling to team sizes where centralized approaches become intractable.