Action-Graph Policies: Learning Action Co-dependencies in Multi-Agent Reinforcement Learning
Authors: Nikunj Gupta, James Zachary Hare, Jesse Milzman, Rajgopal Kannan, Viktor Prasanna
Organizations: University of Southern California, Los Angeles, CA, USA · DEVCOM Army Research Laboratory, Adelphi, MD, USA · DEVCOM ARL Army Research Office, Los Angeles, CA, USA.
Coordinating actions is the most fundamental form of cooperation in multi-agent reinforcement learning (MARL). Successful decentralized decision-making often depends not only on good individual actions, but on selecting compatible actions across agents to synchronize behavior, avoid conflicts, and satisfy global constraints. In this paper, we propose Action Graph Policies (AGP), that model dependencies among agents' available action choices. It constructs, what we call, coordination contexts, that enable agents to condition their decisions on global action dependencies. Theoretically, we show that AGPs induce a strictly more expressive joint policy compared to fully independent policies and can realize coordinated joint actions that are provably more optimal than greedy execution even from centralized value-decomposition methods. Empirically, we show that AGP achieves 80-95% success on canonical coordination tasks with partial observability and anti-coordination penalties, where other MARL methods reach only 10-25%. We further demonstrate that AGP consistently outperforms these baselines in diverse multi-agent environments.
Figures & tables
Figure 1: Illustration of Action-Graph Policies (AGP). The global action graph GA contains one node uai for each available action a∈Ai of every agent i , with edges representing learned coordination dependencies across action choices. Coordination contexts κi are constructed by aggregating information from this action graph prior to decentralized action selection.
Figure 2: Coordination matrix games. (a) Top- K Selection ( N=6 , K=2 ): baselines cluster near the independent-execution bound, while AGP achieves near-optimal coordination. (b) Top- K with anti-coordination penalty: baselines suffer from relative overgeneralization, whereas AGP remains robust.
Figure 3: Ablations. Removing cross-agent action dependencies or the action graph drastically collapses the performance, while a policy-gradient AGP variant recovers similar performance.
Figure 4: Performance on multi-agent particle environments. AGP achieves the highest final test return across all six tasks, outperforming all MARL baselines. Shaded regions indicate ± one standard deviation over five seeds.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Top- K Selection: attention over the action graph. We visualize all attention heads and their mean at the final checkpoint. Attention exhibits structured cross-agent coupling (off-diagonal mass) rather than purely local/self-attention, supporting the interpretation that AGP constructs coordination contexts through action-level dependencies.
Figure 6: Top- K with anti-coordination penalty: attention over the action graph. Compared to Top- K , attention exhibits stronger structured coupling between act1 and act0 nodes across agents, consistent with resolving near-ties and avoiding joint act1 selections that incur the penalty.
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.
Santiago Amaya-Corredor, Miguel Calvo-Fullana, Anders Jonsson
Department of Engineering, Universitat Pompeu Fabra, Barcelona, Spain
Cooperative tasks in Multi-Agent Reinforcement Learning (MARL) require agents to collectively maximize a shared return. Under the Centralized Training with Decentralized Execution (CTDE) paradigm, policy gradients have remained difficult to compute directly. Prior methods largely follow two approaches: independent factorized updates with centralized critics, which lack general joint-improvement guarantees without value decomposition assumptions, or alternating best-response updates, which can converge to suboptimal Nash Equilibria. In this paper, we show the joint policy gradient admits an exact decentralized decomposition of per-agent terms, each formed from per-agent score functions and decentralized critics. Based on this decomposition, we develop Agent-Chained Policy Optimization (ACPO), where actors are trained independently, with their updates together constituting a single step on the joint policy gradient. Central to this result is a serialized view of the simultaneous joint decision in which agents commit actions one at a time, each conditioning on a belief over preceding actions. The belief acts as the coordination mechanism which ties the independent per-agent updates into a joint gradient step. We evaluate ACPO on Multi-Robot Warehouse, SMACv2, and MA-MuJoCo, where it outperforms strong baselines, with the gap widening as the number of agents grows.
Daiki E. Matsunaga, Junho Na, Tri Wahyu Guntara +4
Multi-agent reinforcement learning (MARL) is crucial for AI systems that operate collaboratively in distributed and adversarial settings, particularly in multi-domain operations (MDO). A central challenge in cooperative MARL is determining how agents should coordinate: existing approaches must either hand-specify graph topology, rely on proximity-based heuristics, or learn structure entirely from environment interaction; all of which are brittle, semantically uninformed, or data-intensive. We investigate whether large language models (LLMs) can generate useful coordination graph priors for MARL by using minimal natural language descriptions of agent observations to infer latent coordination patterns. These priors are integrated into MARL algorithms via graph convolutional layers within a graph neural network (GNN)-based pipeline, and evaluated on four cooperative scenarios from the Multi-Agent Particle Environment (MPE) benchmark against baselines spanning the full spectrum of coordination modeling, from independent learners to state-of-the-art graph-based methods. We further ablate across five compact open-source LLMs to assess the sensitivity of prior quality to model choice. Our results provide the first quantitative evidence that LLM-derived graph priors can enhance coordination and adaptability in dynamic multi-agent environments, and demonstrate that models as small as 1.5B parameters are sufficient for effective prior generation.
Nikunj Gupta, Rajgopal Kannan, Viktor Prasanna
University of Southern California, Los Angeles, California, United States · DEVCOM ARL Army Research Office, Los Angeles, California, United States