mlsanityData to 14 Oct 2026

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

arXiv 2211.17116 ↗First posted 30 Nov 2022cs.LG cs.AI cs.MAcited by 20

Not on the map. Why?

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.

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

22 of 49 references.

References · 22

  1. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,258
  2. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,558
  3. 2016Learning to Communicate with Deep Multi-Agent Reinforcement Learningcited by 575
  4. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
  5. 2018Is Q-learning Provably Efficient?cited by 487
  6. 2016Learning Multiagent Communication with Backpropagationcited by 366
  7. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  8. 2018Mean Field Multi-Agent Reinforcement Learningcited by 207
  9. 2018Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agentscited by 194
  10. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 177
  11. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  12. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 150
10 more
  1. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 93
  2. 2019Probabilistic Recursive Reasoning for Multi-Agent Reinforcement Learningcited by 68
  3. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 57
  4. 2020Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Rewardcited by 50
  5. 2021Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challengescited by 50
  6. 2020Multi-Agent Reinforcement Learning in Stochastic Networked Systemscited by 32
  7. 2019A Multi-Agent Off-Policy Actor-Critic Algorithm for Distributed Reinforcement Learningcited by 21
  8. 2021Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatchcited by 17
  9. 2021Learning and Information in Stochastic Networks and Queuescited by 8
  10. 2022On the Optimal Control of Network LQR with Spatially-Exponential Decaying Structurecited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 6; 2024: 6; 2025: 4; 2026: 3.

20 papers.

Sort:

By area:

  1. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  2. 2023Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilitiescited by 15
  3. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 10
  4. 2023Convergence Rates for Localized Actor-Critic in Networked Markov Potential Gamescited by 9
  5. 2025Incentivizing Truthful Language Models via Peer Elicitation Gamescited by 9
  6. 2025A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policiescited by 4
  7. 2024Scalable spectral representations for multi-agent reinforcement learning in network MDPscited by 3
  8. 2022Scalable and Sample Efficient Distributed Policy Gradient Algorithms in Multi-Agent Networked Systemscited by 2
  9. 2023Perimeter Control with Heterogeneous Metering Rates for Cordon Signals: A Physics-Regularized Multi-Agent Reinforcement Learning Approachcited by 2
  10. 2023Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptionscited by 2
  11. 2024Scalable Reinforcement Learning for Linear-Quadratic Control of Networkscited by 2
  12. 2024Distributed Policy Gradient for Linear Quadratic Networked Control with Limited Communication Rangecited by 1
8 more
  1. 2024A finite time analysis of distributed Q-learningcited by 1
  2. 2025Finite-Agent Stochastic Differential Games on Large Graphs: II. Graph-Based Architecturescited by 1
  3. 2026Decentralized Federated Learning With Energy Harvesting Devicescited by 1
  4. 2026The Attacker in the Mirror: Breaking Self-Consistency in Safety via Anchored Bipolicy Self-Playcited by 1
  5. 2026Scalable Policy Optimization for Networked Multi-Agent Reinforcement Learning with Continuous State-Action Spacescited by 1
  6. 2024Simulation-Based Optimistic Policy Iteration For Multi-Agent MDPs with Kullback-Leibler Control Costcited by 0
  7. 2024Almost Sure Convergence of Networked Policy Gradient over Time-Varying Networks in Markov Potential Gamescited by 0
  8. 2025Human Machine Co-Adaptation Model and Its Convergence Analysiscited by 0