# Convergence Rates of Average-Reward Multi-agent Reinforcement Learning via Randomized Linear Programming

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 50 references that are in the map.
- First posted on arXiv 22 Oct 2021.

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

- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1803.11485/) (2018)
- [Learning to Communicate with Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1605.06676/) (2016)
- [Multi-agent Reinforcement Learning in Sequential Social Dilemmas](https://mlsanity.com/paper/1702.03037/) (2017)
- [Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents](https://mlsanity.com/paper/1802.08757/) (2018)
- [Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies](https://mlsanity.com/paper/1906.08383/) (2019)
- [Stabilising Experience Replay for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1702.08887/) (2017)
- [Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Reward](https://mlsanity.com/paper/2006.06626/) (2020)
- [Biases for Emergent Communication in Multi-agent Reinforcement Learning](https://mlsanity.com/paper/1912.05676/) (2019)
- [A Reinforcement Learning Based Approach for Automated Lane Change Maneuvers](https://mlsanity.com/paper/1804.07871/) (2018)
- [Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization](https://mlsanity.com/paper/1806.00877/) (2018)
- [Optimization for Reinforcement Learning: From Single Agent to Cooperative Agents](https://mlsanity.com/paper/1912.00498/) (2019)
- [Value Propagation for Decentralized Networked Deep Multi-agent Reinforcement Learning](https://mlsanity.com/paper/1901.09326/) (2019)
- [Proximity Without Consensus in Online Multi-Agent Optimization](https://mlsanity.com/paper/1606.05578/) (2016)
- [Negotiating Team Formation Using Deep Reinforcement Learning](https://mlsanity.com/paper/2010.10380/) (2020)
- [Correcting Experience Replay for Multi-Agent Communication](https://mlsanity.com/paper/2010.01192/) (2020)
- [Decentralized stochastic control](https://mlsanity.com/paper/1310.4545/) (2013)
- [Voting-Based Multi-Agent Reinforcement Learning for Intelligent IoT](https://mlsanity.com/paper/1907.01385/) (2019)
- [Fully Asynchronous Policy Evaluation in Distributed Reinforcement Learning over Networks](https://mlsanity.com/paper/2003.00433/) (2020)

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

- [On the Near-Optimality of Local Policies in Large Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2209.03491/) (2022)

## Abstract (arXiv)

In tabular multi-agent reinforcement learning with average-cost criterion, a team of agents sequentially interacts with the environment and observes local incentives. We focus on the case that the global reward is a sum of local rewards, the joint policy factorizes into agents' marginals, and full state observability. To date, few global optimality guarantees exist even for this simple setting, as most results yield convergence to stationarity for parameterized policies in large/possibly continuous spaces. To solidify the foundations of MARL, we build upon linear programming (LP) reformulations, for which stochastic primal-dual methods yields a model-free approach to achieve optimal sample complexity in the centralized case. We develop multi-agent extensions, whereby agents solve their local saddle point problems and then perform local weighted averaging. We establish that the sample complexity to obtain near-globally optimal solutions matches tight dependencies on the cardinality of the state and action spaces, and exhibits classical scalings with respect to the network in accordance with multi-agent optimization. Experiments corroborate these results in practice.