# Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learning

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 49 references that are in the map.
- First posted on arXiv 30 Nov 2022.

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

- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Learning to Communicate with Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1605.06676/) (2016)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Learning Multiagent Communication with Backpropagation](https://mlsanity.com/paper/1605.07736/) (2016)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Mean Field Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1802.05438/) (2018)
- [Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents](https://mlsanity.com/paper/1802.08757/) (2018)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [Probabilistic Recursive Reasoning for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1901.09207/) (2019)
- [Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence](https://mlsanity.com/paper/2202.04129/) (2022)
- [Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Reward](https://mlsanity.com/paper/2006.06626/) (2020)
- [Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challenges](https://mlsanity.com/paper/2102.01168/) (2021)
- [Multi-Agent Reinforcement Learning in Stochastic Networked Systems](https://mlsanity.com/paper/2006.06555/) (2020)
- [A Multi-Agent Off-Policy Actor-Critic Algorithm for Distributed Reinforcement Learning](https://mlsanity.com/paper/1903.06372/) (2019)
- [Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatch](https://mlsanity.com/paper/2111.02997/) (2021)
- [Learning and Information in Stochastic Networks and Queues](https://mlsanity.com/paper/2105.08769/) (2021)
- [On the Optimal Control of Network LQR with Spatially-Exponential Decaying Structure](https://mlsanity.com/paper/2209.14376/) (2022)

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

- [A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games](https://mlsanity.com/paper/2303.03100/) (2023)
- [Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilities](https://mlsanity.com/paper/2305.17568/) (2023)
- [Multi-Player Zero-Sum Markov Games with Networked Separable Interactions](https://mlsanity.com/paper/2307.09470/) (2023)
- [Convergence Rates for Localized Actor-Critic in Networked Markov Potential Games](https://mlsanity.com/paper/2303.04865/) (2023)
- [Incentivizing Truthful Language Models via Peer Elicitation Games](https://mlsanity.com/paper/2505.13636/) (2025)
- [A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies](https://mlsanity.com/paper/2510.16132/) (2025)
- [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)
- [Perimeter Control with Heterogeneous Metering Rates for Cordon Signals: A Physics-Regularized Multi-Agent Reinforcement Learning Approach](https://mlsanity.com/paper/2308.12985/) (2023)
- [Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptions](https://mlsanity.com/paper/2312.08008/) (2023)
- [Scalable Reinforcement Learning for Linear-Quadratic Control of Networks](https://mlsanity.com/paper/2401.16183/) (2024)
- [Distributed Policy Gradient for Linear Quadratic Networked Control with Limited Communication Range](https://mlsanity.com/paper/2403.03055/) (2024)
- [A finite time analysis of distributed Q-learning](https://mlsanity.com/paper/2405.14078/) (2024)
- [Finite-Agent Stochastic Differential Games on Large Graphs: II. Graph-Based Architectures](https://mlsanity.com/paper/2509.12484/) (2025)
- [Decentralized Federated Learning With Energy Harvesting Devices](https://mlsanity.com/paper/2602.14051/) (2026)
- [The Attacker in the Mirror: Breaking Self-Consistency in Safety via Anchored Bipolicy Self-Play](https://mlsanity.com/paper/2605.08427/) (2026)
- [Scalable Policy Optimization for Networked Multi-Agent Reinforcement Learning with Continuous State-Action Spaces](https://mlsanity.com/paper/2607.18554/) (2026)
- [Simulation-Based Optimistic Policy Iteration For Multi-Agent MDPs with Kullback-Leibler Control Cost](https://mlsanity.com/paper/2410.15156/) (2024)
- [Almost Sure Convergence of Networked Policy Gradient over Time-Varying Networks in Markov Potential Games](https://mlsanity.com/paper/2410.20075/) (2024)
- [Human Machine Co-Adaptation Model and Its Convergence Analysis](https://mlsanity.com/paper/2503.07319/) (2025)

## Abstract (arXiv)

We study a multi-agent reinforcement learning (MARL) problem where the agents interact over a given network. The goal of the agents is to cooperatively maximize the average of their entropy-regularized long-term rewards. To overcome the curse of dimensionality and to reduce communication, we propose a Localized Policy Iteration (LPI) algorithm that provably learns a near-globally-optimal policy using only local information. In particular, we show that, despite restricting each agent's attention to only its kappa-hop neighborhood, the agents are able to learn a policy with an optimality gap that decays polynomially in kappa. In addition, we show the finite-sample convergence of LPI to the global optimal policy, which explicitly captures the trade-off between optimality and computational complexity in choosing kappa. Numerical simulations demonstrate the effectiveness of LPI.