mlsanityData to 7 Oct 2026

Local Optimization Achieves Global Optimality in Multi-Agent Reinforcement Learning

arXiv 2305.04819 ↗First posted 8 May 2023cs.LG cs.GT cs.MAcited by 4

Not on the map. Why?

Abstract (arXiv)

Policy optimization methods with function approximation are widely used in multi-agent reinforcement learning. However, it remains elusive how to design such algorithms with statistical guarantees. Leveraging a multi-agent performance difference lemma that characterizes the landscape of multi-agent policy optimization, we find that the localized action value function serves as an ideal descent direction for each local policy. Motivated by the observation, we present a multi-agent PPO algorithm in which the local policy of each agent is updated similarly to vanilla PPO. We prove that with standard regularity conditions on the Markov game and problem-dependent quantities, our algorithm converges to the globally optimal policy at a sublinear rate. We extend our algorithm to the off-policy setting and introduce pessimism to policy evaluation, which aligns with experiments. To our knowledge, this is the first provably convergent multi-agent PPO algorithm in cooperative Markov games.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 39 of its 68 references that are in the map. First posted on arXiv 8 May 2023.

Builds on

39 of 68 references.

References · 39

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2015Continuous control with deep reinforcement learningcited by 3,279
  3. 2015Trust Region Policy Optimizationcited by 2,503
  4. 2018Addressing Function Approximation Error in Actor-Critic Methodscited by 2,302
  5. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,519
  6. 2021The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Gamescited by 903
  7. 2017Counterfactual Multi-Agent Policy Gradientscited by 733
  8. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  9. 2020Reinforcement Learning with Augmented Datacited by 452
  10. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  11. 2016Benchmarking Deep Reinforcement Learning for Continuous Controlcited by 361
  12. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
27 more
  1. 2017How to Escape Saddle Points Efficientlycited by 284
  2. 2020Is Independent Learning All You Need in the StarCraft Multi-Agent Challenge?cited by 281
  3. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  4. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  5. 2019A Theoretical Analysis of Deep Q-Learningcited by 212
  6. 2020Benchmarking Multi-Agent Deep Reinforcement Learning Algorithms in Cooperative Taskscited by 207
  7. 2018Mean Field Multi-Agent Reinforcement Learningcited by 202
  8. 2021Trust Region Policy Optimisation in Multi-Agent Reinforcement Learningcited by 180
  9. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  10. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  11. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 122
  12. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 113
  13. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  14. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  15. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
  16. 2019Probabilistic Recursive Reasoning for Multi-Agent Reinforcement Learningcited by 68
  17. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  18. 2020Predictive Information Accelerates Learning in RLcited by 56
  19. 2021Tactical Optimism and Pessimism for Deep Reinforcement Learningcited by 55
  20. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  21. 2019Bi-level Actor-Critic for Multi-agent Coordinationcited by 38
  22. 2019ELF OpenGo: An Analysis and Open Reimplementation of AlphaZerocited by 37
  23. 2021Independent Natural Policy Gradient Always Converges in Markov Potential Gamescited by 34
  24. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
  25. 2018Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Modelcited by 22
  26. 2021Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Gamescited by 18
  27. 2016Deep Learning for Reward Design to Improve Monte Carlo Tree Search in ATARI Gamescited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 1; 2026: 1.

4 papers.

  1. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyondcited by 6
  2. 2024Toward Finding Strong Pareto Optimal Policies in Multi-Agent Reinforcement Learningcited by 3
  3. 2025K-Level Policy Gradients for Multi-Agent Reinforcement Learningcited by 1
  4. 2026Low Variance Trust Region Optimization with Independent Actors and Sequential Updates in Cooperative Multi-agent Reinforcement Learningcited by 0