mlsanityData to 14 Oct 2026

Action Dependency Graphs for Globally Optimal Coordinated Reinforcement Learning

arXiv 2506.00797 ↗First posted 1 Jun 2025cs.LG cs.AI cs.SYcited by 0

On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization

Abstract (arXiv)

Action-dependent individual policies, which incorporate both environmental states and the actions of other agents in decision-making, have emerged as a promising paradigm for achieving global optimality in multi-agent reinforcement learning (MARL). However, the existing literature often adopts auto-regressive action-dependent policies, where each agent's policy depends on the actions of all preceding agents. This formulation incurs substantial computational complexity as the number of agents increases, thereby limiting scalability. In this work, we consider a more generalized class of action-dependent policies, which do not necessarily follow the auto-regressive form. We propose to use the `action dependency graph (ADG)' to model the inter-agent action dependencies. Within the context of MARL problems structured by coordination graphs, we prove that an action-dependent policy with a sparse ADG can achieve global optimality, provided the ADG satisfies specific conditions specified by the coordination graph. Building on this theoretical foundation, we develop a tabular policy iteration algorithm with guaranteed global optimality. Furthermore, we integrate our framework into several SOTA algorithms and conduct experiments in complex environments. The empirical results affirm the robustness and applicability of our approach in more general scenarios, underscoring its potential for broader MARL challenges.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods. Builds on 32 of its 51 references that are in the map. First posted on arXiv 1 Jun 2025.

Builds on

32 of 51 references.

References · 32

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  3. 2015High-Dimensional Continuous Control Using Generalized Advantage Estimationcited by 2,026
  4. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,558
  5. 2021The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Gamescited by 942
  6. 2017Counterfactual Multi-Agent Policy Gradientscited by 751
  7. 2018QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learningcited by 708
  8. 2019The StarCraft Multi-Agent Challengecited by 597
  9. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
  10. 2019QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learningcited by 379
  11. 2018Actor-Attention-Critic for Multi-Agent Reinforcement Learningcited by 261
  12. 2020Benchmarking Multi-Agent Deep Reinforcement Learning Algorithms in Cooperative Taskscited by 212
20 more
  1. 2021Trust Region Policy Optimisation in Multi-Agent Reinforcement Learningcited by 186
  2. 2022Multi-Agent Reinforcement Learning is a Sequence Modeling Problemcited by 155
  3. 2019A Review of Cooperative Multi-Agent Deep Reinforcement Learningcited by 147
  4. 2019Deep Coordination Graphscited by 98
  5. 2020Deep Implicit Coordination Graphs for Multi-agent Reinforcement Learningcited by 60
  6. 2020Multi-agent Reinforcement Learning for Networked System Controlcited by 53
  7. 2022Revisiting Some Common Practices in Cooperative Multi-Agent Reinforcement Learningcited by 32
  8. 2021Context-Aware Sparse Deep Coordination Graphscited by 28
  9. 2022On the Global Convergence Rates of Decentralized Softmax Gradient Play in Markov Potential Gamescited by 22
  10. 2022GCS: Graph-based Coordination Strategy for Multi-Agent Reinforcement Learningcited by 20
  11. 2022More Centralized Training, Still Decentralized Execution: Multi-Agent Conditional Policy Factorizationcited by 19
  12. 2023Is Centralized Training with Decentralized Execution Framework Centralized Enough for MARL?cited by 18
  13. 2024Group-Aware Coordination Graph for Multi-Agent Reinforcement Learningcited by 18
  14. 2022ACE: Cooperative Multi-agent Q-learning with Bidirectional Action-Dependencycited by 15
  15. 2022Heterogeneous-Agent Mirror Learning: A Continuum of Solutions to Cooperative MARLcited by 12
  16. 2021Coordinated Reinforcement Learning for Optimizing Mobile Networkscited by 7
  17. 2022Understanding Value Decomposition Algorithms in Deep Cooperative Multi-Agent Reinforcement Learningcited by 6
  18. 2022Distributed Multi-Agent Reinforcement Learning Based on Graph-Induced Local Value Functionscited by 6
  19. 2023Context-Aware Bayesian Network Actor-Critic Methods for Cooperative Multi-Agent Reinforcement Learningcited by 2
  20. 2024Backpropagation Through Agentscited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Action-Graph Policies: Learning Action Co-dependencies in Multi-Agent Reinforcement Learning
  2. 2026Coordination Graphs for Constrained Multi-Agent Reinforcement Learning
  3. 2024Scaling Team Coordination on Graphs with Reinforcement Learning
  4. 2025Reinforcement Networks: novel framework for collaborative Multi-Agent Reinforcement Learning tasks
  5. 2025Structured Cooperative Multi-Agent Reinforcement Learning: a Bayesian Network Perspective
  6. 2024Offline Multi-Agent Reinforcement Learning via In-Sample Sequential Policy Optimization
  7. 2025Graph-Enhanced Policy Optimization in LLM Agent Training
  8. 2024Inferring Latent Temporal Sparse Coordination Graph for Multi-Agent Reinforcement Learning