# Action Dependency Graphs for Globally Optimal Coordinated Reinforcement Learning

arXiv: https://arxiv.org/abs/2506.00797 · HTML: https://mlsanity.com/paper/2506.00797/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Multi-agent reinforcement learning, 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.

## Placed in

- Deep reinforcement learning methods / [Multi-agent reinforcement learning](https://mlsanity.com/deeprl/multi-agent-reinforcement-learning/)

## Builds on (most cited first, 30 of 32)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1803.11485/) (2018)
- [The StarCraft Multi-Agent Challenge](https://mlsanity.com/paper/1902.04043/) (2019)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1905.05408/) (2019)
- [Actor-Attention-Critic for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1810.02912/) (2018)
- [Benchmarking Multi-Agent Deep Reinforcement Learning Algorithms in Cooperative Tasks](https://mlsanity.com/paper/2006.07869/) (2020)
- [Trust Region Policy Optimisation in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2109.11251/) (2021)
- [Multi-Agent Reinforcement Learning is a Sequence Modeling Problem](https://mlsanity.com/paper/2205.14953/) (2022)
- [A Review of Cooperative Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/1908.03963/) (2019)
- [Deep Coordination Graphs](https://mlsanity.com/paper/1910.00091/) (2019)
- [Deep Implicit Coordination Graphs for Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2006.11438/) (2020)
- [Multi-agent Reinforcement Learning for Networked System Control](https://mlsanity.com/paper/2004.01339/) (2020)
- [Revisiting Some Common Practices in Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2206.07505/) (2022)
- [Context-Aware Sparse Deep Coordination Graphs](https://mlsanity.com/paper/2106.02886/) (2021)
- [On the Global Convergence Rates of Decentralized Softmax Gradient Play in Markov Potential Games](https://mlsanity.com/paper/2202.00872/) (2022)
- [GCS: Graph-based Coordination Strategy for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2201.06257/) (2022)
- [More Centralized Training, Still Decentralized Execution: Multi-Agent Conditional Policy Factorization](https://mlsanity.com/paper/2209.12681/) (2022)
- [Is Centralized Training with Decentralized Execution Framework Centralized Enough for MARL?](https://mlsanity.com/paper/2305.17352/) (2023)
- [Group-Aware Coordination Graph for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2404.10976/) (2024)
- [ACE: Cooperative Multi-agent Q-learning with Bidirectional Action-Dependency](https://mlsanity.com/paper/2211.16068/) (2022)
- [Heterogeneous-Agent Mirror Learning: A Continuum of Solutions to Cooperative MARL](https://mlsanity.com/paper/2208.01682/) (2022)
- [Coordinated Reinforcement Learning for Optimizing Mobile Networks](https://mlsanity.com/paper/2109.15175/) (2021)
- [Understanding Value Decomposition Algorithms in Deep Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2202.04868/) (2022)
- [Distributed Multi-Agent Reinforcement Learning Based on Graph-Induced Local Value Functions](https://mlsanity.com/paper/2202.13046/) (2022)

## 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.