# Multi-Agent Reinforcement Learning in Stochastic Networked Systems

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

## Key facts

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

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

- [Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approach](https://mlsanity.com/paper/2108.02731/) (2021)
- [Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2211.17116/) (2022)
- [Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilities](https://mlsanity.com/paper/2305.17568/) (2023)
- [A Survey on Large-Population Systems and Scalable Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2209.03859/) (2022)
- [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)
- [Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scale](https://mlsanity.com/paper/2403.00222/) (2024)
- [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)
- [Exploiting Structure in Offline Multi-Agent RL: The Benefits of Low Interaction Rank](https://mlsanity.com/paper/2410.01101/) (2024)
- [Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Games](https://mlsanity.com/paper/2112.07859/) (2021)
- [On the Near-Optimality of Local Policies in Large Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2209.03491/) (2022)
- [Bayesian Ego-graph Inference for Networked Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2509.16606/) (2025)
- [Hypergraphon Mean Field Games](https://mlsanity.com/paper/2203.16223/) (2022)
- [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)
- [Model-Free Learning for the Linear Quadratic Regulator over Rate-Limited Channels](https://mlsanity.com/paper/2401.01258/) (2024)
- [Policy Evaluation in Decentralized POMDPs with Belief Sharing](https://mlsanity.com/paper/2302.04151/) (2023)
- [A finite time analysis of distributed Q-learning](https://mlsanity.com/paper/2405.14078/) (2024)
- [Toward Adaptable Multi-Agent Reinforcement Learning: An Assumption-Aware Review](https://mlsanity.com/paper/2507.10142/) (2025)
- [A Unified Framework for Locality in Scalable MARL](https://mlsanity.com/paper/2602.16966/) (2026)
- [Revisiting Policy Gradients for Restricted Policy Classes: Escaping Myopic Local Optima with k-step Policy Gradients](https://mlsanity.com/paper/2605.10909/) (2026)
- [Scalable Policy Optimization for Networked Multi-Agent Reinforcement Learning with Continuous State-Action Spaces](https://mlsanity.com/paper/2607.18554/) (2026)
- [Sparse Mean Field Load Balancing in Large Localized Queueing Systems](https://mlsanity.com/paper/2312.12973/) (2023)
- [Almost Sure Convergence of Networked Policy Gradient over Time-Varying Networks in Markov Potential Games](https://mlsanity.com/paper/2410.20075/) (2024)
- [Multi-agent Uncertainty-Aware Pessimistic Model-Based Reinforcement Learning for Connected Autonomous Vehicles](https://mlsanity.com/paper/2503.20462/) (2025)
- [LOD: Latent Objective Discovery in Heterogeneous Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2505.09756/) (2025)
- [Explicit Credit Assignment through Local Rewards and Dependence Graphs in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2601.21523/) (2026)
- [Distributed Zeroth-Order Policy Gradient for Networked Multi-agent Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2605.15697/) (2026)

## Abstract (arXiv)

We study multi-agent reinforcement learning (MARL) in a stochastic network of agents. The objective is to find localized policies that maximize the (discounted) global reward. In general, scalability is a challenge in this setting because the size of the global state/action space can be exponential in the number of agents. Scalable algorithms are only known in cases where dependencies are static, fixed and local, e.g., between neighbors in a fixed, time-invariant underlying graph. In this work, we propose a Scalable Actor Critic framework that applies in settings where the dependencies can be non-local and stochastic, and provide a finite-time error bound that shows how the convergence rate depends on the speed of information spread in the network. Additionally, as a byproduct of our analysis, we obtain novel finite-time convergence results for a general stochastic approximation scheme and for temporal difference learning with state aggregation, which apply beyond the setting of MARL in networked systems.