# On the Near-Optimality of Local Policies in Large Cooperative Multi-Agent Reinforcement Learning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 35 references that are in the map.
- First posted on arXiv 7 Sep 2022.

## Builds on (most cited first, 18 of 18)

- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1803.11485/) (2018)
- [QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1905.05408/) (2019)
- [Weighted QMIX: Expanding Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2006.10800/) (2020)
- [A Machine Learning Framework for Solving High-Dimensional Mean Field Game and Mean Field Control Problems](https://mlsanity.com/paper/1912.01825/) (2019)
- [Single and Multi-Agent Deep Reinforcement Learning for AI-Enabled Wireless Networks: A Tutorial](https://mlsanity.com/paper/2011.03615/) (2020)
- [DeepPool: Distributed Model-free Algorithm for Ride-sharing using Deep Reinforcement Learning](https://mlsanity.com/paper/1903.03882/) (2019)
- [Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Reward](https://mlsanity.com/paper/2006.06626/) (2020)
- [Mean-Field Controls with Q-learning for Cooperative MARL: Convergence and Complexity Analysis](https://mlsanity.com/paper/2002.04131/) (2020)
- [Unified Reinforcement Q-Learning for Mean Field Game and Control Problems](https://mlsanity.com/paper/2006.13912/) (2020)
- [Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning](https://mlsanity.com/paper/2107.04050/) (2021)
- [Large-Scale Traffic Signal Control Using a Novel Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1908.03761/) (2019)
- [Multi-Agent Reinforcement Learning in Stochastic Networked Systems](https://mlsanity.com/paper/2006.06555/) (2020)
- [On the Approximation of Cooperative Heterogeneous Multi-Agent Reinforcement Learning (MARL) using Mean Field Control (MFC)](https://mlsanity.com/paper/2109.04024/) (2021)
- [Optimal resource allocation for competitive spreading processes on bilayer networks](https://mlsanity.com/paper/1512.05299/) (2015)
- [Can Mean Field Control (MFC) Approximate Cooperative Multi Agent Reinforcement Learning (MARL) with Non-Uniform Interaction?](https://mlsanity.com/paper/2203.00035/) (2022)
- [Reinforcement Learning for Mean Field Game](https://mlsanity.com/paper/1905.13357/) (2019)
- [Convergence Rates of Average-Reward Multi-agent Reinforcement Learning via Randomized Linear Programming](https://mlsanity.com/paper/2110.12929/) (2021)

## Built on by (most cited first, 4 of 4)

- [Convergence Rates for Localized Actor-Critic in Networked Markov Potential Games](https://mlsanity.com/paper/2303.04865/) (2023)
- [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)
- [Mean-Field Approximation of Cooperative Constrained Multi-Agent Reinforcement Learning (CMARL)](https://mlsanity.com/paper/2209.07437/) (2022)
- [Scalable Task-Driven Robotic Swarm Control via Collision Avoidance and Learning Mean-Field Control](https://mlsanity.com/paper/2209.07420/) (2022)

## Abstract (arXiv)

We show that in a cooperative N-agent network, one can design locally executable policies for the agents such that the resulting discounted sum of average rewards (value) well approximates the optimal value computed over all (including non-local) policies. Specifically, we prove that, if |X|, |U| denote the size of state, and action spaces of individual agents, then for sufficiently small discount factor, the approximation error is given by O(e) where etriangleq frac1√Nleft[√|X|+√|U|right]. Moreover, in a special case where the reward and state transition functions are independent of the action distribution of the population, the error improves to O(e) where etriangleq frac1√N√|X|. Finally, we also devise an algorithm to explicitly construct a local policy. With the help of our approximation results, we further establish that the constructed local policy is within O(maxe,ε) distance of the optimal policy, and the sample complexity to achieve such a local policy is O(ε-3), for any ε>0.