# Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Reward

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

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2020.

## Built on by (most cited first, 30 of 50)

- [Multi-Agent Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2408.09675/) (2024)
- [A Review of Cooperation in Multi-agent Learning](https://mlsanity.com/paper/2312.05162/) (2023)
- [What is the Solution for State-Adversarial Multi-Agent Reinforcement Learning?](https://mlsanity.com/paper/2212.02705/) (2022)
- [Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2211.17116/) (2022)
- [AdaSociety: An Adaptive Environment with Social Structures for Multi-Agent Decision-Making](https://mlsanity.com/paper/2411.03865/) (2024)
- [Causal Multi-Agent Reinforcement Learning: Review and Open Problems](https://mlsanity.com/paper/2111.06721/) (2021)
- [A Survey on Large-Population Systems and Scalable Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2209.03859/) (2022)
- [Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2412.00661/) (2024)
- [Mean-Field Control based Approximation of Multi-Agent Reinforcement Learning in Presence of a Non-decomposable Shared Global State](https://mlsanity.com/paper/2301.06889/) (2023)
- [Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scale](https://mlsanity.com/paper/2403.00222/) (2024)
- [Scalable Model-based Policy Optimization for Decentralized Networked Systems](https://mlsanity.com/paper/2207.06559/) (2022)
- [Distributed Multi-Agent Reinforcement Learning Based on Graph-Induced Local Value Functions](https://mlsanity.com/paper/2202.13046/) (2022)
- [Locally Interdependent Multi-Agent MDP: Theoretical Framework for Decentralized Agents with Dynamic Dependencies](https://mlsanity.com/paper/2406.06823/) (2024)
- [Learning to Share in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2112.08702/) (2021)
- [Dimension-Free Rates for Natural Policy Gradient in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2109.11692/) (2021)
- [On the Near-Optimality of Local Policies in Large Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2209.03491/) (2022)
- [Major-Minor Mean Field Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2303.10665/) (2023)
- [Sample and Communication Efficient Fully Decentralized MARL Policy Evaluation via a New Approach: Local TD update](https://mlsanity.com/paper/2403.15935/) (2024)
- [Bayesian Ego-graph Inference for Networked Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2509.16606/) (2025)
- [Locality Matters: A Scalable Value Decomposition Approach for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2109.10632/) (2021)
- [Approximate Global Convergence of Independent Learning in Multi-Agent Systems](https://mlsanity.com/paper/2405.19811/) (2024)
- [Scalable spectral representations for multi-agent reinforcement learning in network MDPs](https://mlsanity.com/paper/2410.17221/) (2024)
- [Scalable and Sample Efficient Distributed Policy Gradient Algorithms in Multi-Agent Networked Systems](https://mlsanity.com/paper/2212.06357/) (2022)
- [Scalable Reinforcement Learning for Linear-Quadratic Control of Networks](https://mlsanity.com/paper/2401.16183/) (2024)
- [Ego-centric Learning of Communicative World Models for Autonomous Driving](https://mlsanity.com/paper/2506.08149/) (2025)
- [Unifying Agent Interaction and World Information for Multi-agent Coordination](https://mlsanity.com/paper/2509.25550/) (2025)
- [Convergence Rates of Average-Reward Multi-agent Reinforcement Learning via Randomized Linear Programming](https://mlsanity.com/paper/2110.12929/) (2021)
- [Distributed Policy Gradient for Linear Quadratic Networked Control with Limited Communication Range](https://mlsanity.com/paper/2403.03055/) (2024)
- [Multi-agent Assessment with QoS Enhancement for HD Map Updates in a Vehicular Network](https://mlsanity.com/paper/2407.21460/) (2024)
- [Bayesian Optimization Framework for Efficient Fleet Design in Autonomous Multi-Robot Exploration](https://mlsanity.com/paper/2408.11751/) (2024)

## Abstract (arXiv)

It has long been recognized that multi-agent reinforcement learning (MARL) faces significant scalability issues due to the fact that the size of the state and action spaces are exponentially large in the number of agents. In this paper, we identify a rich class of networked MARL problems where the model exhibits a local dependence structure that allows it to be solved in a scalable manner. Specifically, we propose a Scalable Actor-Critic (SAC) method that can learn a near optimal localized policy for optimizing the average reward with complexity scaling with the state-action space size of local neighborhoods, as opposed to the entire network. Our result centers around identifying and exploiting an exponential decay property that ensures the effect of agents on each other decays exponentially fast in their graph distance.