Coordination Graphs for Constrained Multi-Agent Reinforcement Learning

• URL: http://arxiv.org/abs/2606.02337v1
• Date: Mon, 01 Jun 2026 14:46:16 GMT
• Title: Coordination Graphs for Constrained Multi-Agent Reinforcement Learning
• Abstract summary: Coordination Graphs for Constrained Multi-Agent Reinforcement Learning (CG-CMARL)<n>System decomposes the joint problem into pairwise regions, each served by a set of shared Q-functions.<n>At execution time, Max-Sum message passing coordinates actions across the factor graph, while a Lagrangian multiplier controls the objective--constraint tradeoff.
• Score: 4.278821961637313
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• GCT-MARL: Graph-Based Contrastive Transfer for Sample-Efficient Cooperative Multi-Agent Reinforcement Learning [0.764671395172401]
  We propose GCT-MARL, a transfer learning framework that builds on the multi-view graph contrastive backbone of MAIL.<n>We empirically demonstrate that the proposed framework markedly accelerates convergence on the target task.<n>We show that the framework naturally supports continual learning by sequentially chaining the two-phase transfer protocol.
  arXiv  Detail & Related papers  (2026-06-23T18:31:27Z)
• Benchmarking Open-Ended Multi-Agent Coordination in Language Agents [48.1363632826625]
  Alem embeds procedurally generated coordination tasks, soft specialisation, communication, and controllable coordination difficulty into a long-horizon survival world.<n>We introduce $alem$, a JAX-based benchmark for open-ended multi-agent coordination built on Craftax-like dynamics.
  arXiv  Detail & Related papers  (2026-06-06T21:13:43Z)
• Scalable Constrained Multi-Agent Reinforcement Learning via State Augmentation and Consensus for Separable Dynamics [4.278821961637313]
  We present a distributed approach for constrained Multi-Agent Reinforcement Learning (MARL)<n>Our method targets systems where agents have separable dynamics but must coordinate to satisfy global resource constraints.<n>We show that lightweight neighbor-to-neighbor consensus over Lagrange multipliers suffices for globally coordinated constraint enforcement.
  arXiv  Detail & Related papers  (2026-05-28T18:37:16Z)
• Improving the Efficiency of Language Agent Teams with Adaptive Task Graphs [52.26652574704317]
  Large language models (LLMs) are increasingly deployed in teams, yet existing coordination approaches often occupy two extremes.<n>We introduce Language Agent Teams for Task Evolution (LATTE), a framework for coordinating LLM teams inspired by distributed systems.
  arXiv  Detail & Related papers  (2026-05-07T14:19:17Z)
• MO-MIX: Multi-Objective Multi-Agent Cooperative Decision-Making With Deep Reinforcement Learning [68.91090643731987]
  Deep reinforcement learning (RL) has been applied extensively to solve complex decision-making problems.<n>Existing approaches are limited to separate fields and can only handle multi-agent decision-making with a single objective.<n>We propose MO-mix to solve the multi-objective multi-agent reinforcement learning (MOMARL) problem.
  arXiv  Detail & Related papers  (2026-02-28T16:25:22Z)
• Discovering Coordinated Joint Options via Inter-Agent Relative Dynamics [13.0114299827121]
  In multi-agent settings, the exponential growth of the joint state space with the number of agents makes coordinated behaviours even more valuable.<n>Existing multi-agent option discovery methods often sacrifice coordination by producing loosely coupled or fully independent behaviours.<n>We propose a joint-state abstraction that compresses the state space while preserving the information necessary to discover strongly coordinated behaviours.
  arXiv  Detail & Related papers  (2025-12-31T12:39:22Z)
• Offline Multi-agent Reinforcement Learning via Score Decomposition [51.23590397383217]
  offline cooperative multi-agent reinforcement learning (MARL) faces unique challenges due to distributional shifts.<n>This work is the first work to explicitly address the distributional gap between offline and online MARL.
  arXiv  Detail & Related papers  (2025-05-09T11:42:31Z)
• Group-Aware Coordination Graph for Multi-Agent Reinforcement Learning [19.386588137176933]
  Group-Aware Coordination Graph (GACG) is designed to capture cooperation between agent pairs based on current observations. GACG is further used in graph convolution for information exchange between agents during decision-making. Our evaluations, conducted on StarCraft II micromanagement tasks, demonstrate GACG's superior performance.
  arXiv  Detail & Related papers  (2024-04-17T01:17:10Z)
• RACA: Relation-Aware Credit Assignment for Ad-Hoc Cooperation in Multi-Agent Deep Reinforcement Learning [55.55009081609396]
  We propose a novel method, called Relation-Aware Credit Assignment (RACA), which achieves zero-shot generalization in ad-hoc cooperation scenarios. RACA takes advantage of a graph-based encoder relation to encode the topological structure between agents. Our method outperforms baseline methods on the StarCraftII micromanagement benchmark and ad-hoc cooperation scenarios.
  arXiv  Detail & Related papers  (2022-06-02T03:39:27Z)
• CoADNet: Collaborative Aggregation-and-Distribution Networks for Co-Salient Object Detection [91.91911418421086]
  Co-Salient Object Detection (CoSOD) aims at discovering salient objects that repeatedly appear in a given query group containing two or more relevant images. One challenging issue is how to effectively capture co-saliency cues by modeling and exploiting inter-image relationships. We present an end-to-end collaborative aggregation-and-distribution network (CoADNet) to capture both salient and repetitive visual patterns from multiple images.
  arXiv  Detail & Related papers  (2020-11-10T04:28:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.