Scalable Constrained Multi-Agent Reinforcement Learning via State Augmentation and Consensus for Separable Dynamics

• URL: http://arxiv.org/abs/2605.30461v1
• Date: Thu, 28 May 2026 18:37:16 GMT
• Title: Scalable Constrained Multi-Agent Reinforcement Learning via State Augmentation and Consensus for Separable Dynamics
• Abstract summary: 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.
• Score: 4.278821961637313
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a distributed approach for constrained Multi-Agent Reinforcement Learning (MARL) that combines state-augmented policy learning with distributed consensus over dual variables. Our method targets systems where agents have separable dynamics but must coordinate to satisfy global resource constraints, a setting in which, as we demonstrate empirically, independent learning fails to produce feasible solutions because agents cannot determine appropriate individual contributions toward collective constraint satisfaction. The key technical contribution is showing that lightweight neighbor-to-neighbor consensus over Lagrange multipliers suffices for globally coordinated constraint enforcement while preserving the scalability of independent training. Each agent learns a single augmented policy offline, conditioned on both its local state and a dual variable encoding constraint feedback. During execution, agents reach agreement on this dual variable through local communication alone. We prove that under mild connectivity assumptions, the consensus error among agents' multipliers is bounded, and show that this translates to a bounded constraint violation that decreases with graph connectivity and the number of consensus rounds. Unlike centralized training with decentralized execution (CTDE) approaches, whose complexity grows at least quadratically with agent count, our method scales linearly in both training and execution. Experiments on smart grid demand response demonstrate that consensus coordination is \emph{essential for feasibility}: without it, agents satisfy grid capacity constraints only by indefinitely postponing demand, a degenerate non-solution. With consensus, agents converge to a shared dual variable and satisfy both grid constraints and demand fulfillment, scaling to thousands of agents while CTDE baselines are limited to dozens.

Related papers

• Communication-Efficient Digital-Twin Coordination for Heterogeneous LLM Embodied Agents over Computing Power Networks [48.90302419915548]
  Embodied agent teams powered by heterogeneous large language models (LLMs) are being widely deployed in smart factories, warehouses, and service robotics.<n>We propose LDT-Coord, a networked coordination framework built upon a lightweight digital twin (DT)<n>Specifically, each agent independently selects its intended action and reports both the action decision and a structured temporal constraint over shared resources to the DT server.
  arXiv  Detail & Related papers  (2026-07-10T12:10:31Z)
• Coordination Graphs for Constrained Multi-Agent Reinforcement Learning [4.278821961637313]
  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.
  arXiv  Detail & Related papers  (2026-06-01T14:46:16Z)
• Beyond Arrow's Impossibility: Fairness as an Emergent Property of Multi-Agent Collaboration [3.4539478661465766]
  As large language models become agentic, we propose that fairness emerges through interaction and exchange.<n>We study this via a controlled hospital triage framework in which two agents negotiate over three structured debate rounds.
  arXiv  Detail & Related papers  (2026-04-15T10:34:35Z)
• On Performance Guarantees for Federated Learning with Personalized Constraints [1.0195618602298684]
  Federated learning (FL) has emerged as a communication-efficient algorithmic framework for distributed learning across multiple agents.<n>We propose PC-FedAvg, a method in which each agent maintains cross-estimates of the other agents' variables through a multi-block local decision vector.<n>We establish communication-complexity rates of $mathcalO(-2)$ for suboptimality and $mathcalO(-1)$ for agent-wise infeasibility.
  arXiv  Detail & Related papers  (2026-03-20T03:49:28Z)
• Deep Reinforcement Learning for Multi-Agent Coordination [8.250169938213558]
  We propose a Stigmergic Multi-Agent Deep Reinforcement Learning (S-MADRL) framework that leverages virtual pheromones to model local and social interactions.<n>We show that our framework achieves the most effective coordination of up to eight agents, where robots self-organize into asymmetric workload distributions.<n>This emergent behavior, analogous to strategies observed in nature, demonstrates a scalable solution for decentralized multi-agent coordination in crowded environments.
  arXiv  Detail & Related papers  (2025-10-04T00:47:20Z)
• 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)
• AgentMixer: Multi-Agent Correlated Policy Factorization [35.73799473896975]
  AgentMixer combines individual partially observable policies into a joint fully observable policy non-linearly.<n>AgentMixer outperforms or matches state-of-the-art methods in the Multi-Agent MuJoCo, SMAC-v2, Matrix Game, and Predator-Prey benchmarks.
  arXiv  Detail & Related papers  (2024-01-16T15:32:41Z)
• On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring [105.13668993076801]
  A central problem in the theory of multi-agent reinforcement learning (MARL) is to understand what structural conditions and algorithmic principles lead to sample-efficient learning guarantees. We study this question in a general framework for interactive decision making with multiple agents. We show that characterizing the statistical complexity for multi-agent decision making is equivalent to characterizing the statistical complexity of single-agent decision making.
  arXiv  Detail & Related papers  (2023-05-01T06:46:22Z)
• Distributed Adaptive Learning Under Communication Constraints [54.22472738551687]
  This work examines adaptive distributed learning strategies designed to operate under communication constraints. We consider a network of agents that must solve an online optimization problem from continual observation of streaming data.
  arXiv  Detail & Related papers  (2021-12-03T19:23:48Z)
• Dealing with Non-Stationarity in Multi-Agent Reinforcement Learning via Trust Region Decomposition [52.06086375833474]
  Non-stationarity is one thorny issue in multi-agent reinforcement learning. We introduce a $delta$-stationarity measurement to explicitly model the stationarity of a policy sequence. We propose a trust region decomposition network based on message passing to estimate the joint policy divergence.
  arXiv  Detail & Related papers  (2021-02-21T14:46:50Z)
• F2A2: Flexible Fully-decentralized Approximate Actor-critic for Cooperative Multi-agent Reinforcement Learning [110.35516334788687]
  Decentralized multi-agent reinforcement learning algorithms are sometimes unpractical in complicated applications. We propose a flexible fully decentralized actor-critic MARL framework, which can handle large-scale general cooperative multi-agent setting. Our framework can achieve scalability and stability for large-scale environment and reduce information transmission.
  arXiv  Detail & Related papers  (2020-04-17T14:56:29Z)

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.