mlsanityData to 7 Oct 2026

Independent Policy Gradient Methods for Competitive Reinforcement Learning

arXiv 2101.04233 ↗First posted 11 Jan 2021cs.LGcited by 97

Not on the map. Why?

Abstract (arXiv)

We obtain global, non-asymptotic convergence guarantees for independent learning algorithms in competitive reinforcement learning settings with two agents (i.e., zero-sum stochastic games). We consider an episodic setting where in each episode, each player independently selects a policy and observes only their own actions and rewards, along with the state. We show that if both players run policy gradient methods in tandem, their policies will converge to a min-max equilibrium of the game, as long as their learning rates follow a two-timescale rule (which is necessary). To the best of our knowledge, this constitutes the first finite-sample convergence result for independent policy gradient methods in competitive RL; prior work has largely focused on centralized, coordinated procedures for equilibrium computation.

Key facts. Cited by 97 papers in the map (data through 7 Oct 2026). Builds on 49 of its 83 references that are in the map. First posted on arXiv 11 Jan 2021.

Builds on

49 of 83 references.

References · 49

  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. 2015End-to-End Training of Deep Visuomotor Policiescited by 847
  5. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  6. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  7. 2018Is Q-learning Provably Efficient?cited by 485
  8. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  9. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  10. 2017Training GANs with Optimismcited by 217
  11. 2019A Theoretical Analysis of Deep Q-Learningcited by 212
  12. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
37 more
  1. 2018Stochastic model-based minimization of weakly convex functionscited by 157
  2. 2017On the Sample Complexity of the Linear Quadratic Regulatorcited by 151
  3. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  4. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  5. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  6. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  7. 2017Cycles in adversarial regularized learningcited by 122
  8. 2017Stabilising Experience Replay for Deep Multi-Agent Reinforcement Learningcited by 114
  9. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  10. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  11. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  12. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  13. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 98
  14. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 97
  15. 2017A Survey of Learning in Multiagent Environments: Dealing with Non-Stationaritycited by 93
  16. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
  17. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  18. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 75
  19. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  20. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  21. 2018Negative Momentum for Improved Game Dynamicscited by 59
  22. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 59
  23. 2019Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applicationscited by 55
  24. 2019Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Gamescited by 38
  25. 2020Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problemscited by 37
  26. 2018Actor-Critic Policy Optimization in Partially Observable Multiagent Environmentscited by 35
  27. 2015Decentralized Q-Learning for Stochastic Teams and Gamescited by 34
  28. 2018Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functionscited by 31
  29. 2019Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descentcited by 31
  30. 2019An accelerated inexact proximal point method for solving nonconvex-concave min-max problemscited by 30
  31. 2019Last-iterate convergence rates for min-max optimizationcited by 25
  32. 2019Policy-Gradient Algorithms Have No Guarantees of Convergence in Linear Quadratic Gamescited by 15
  33. 2019Global Convergence of Policy Gradient for Sequential Zero-Sum Linear Quadratic Dynamic Gamescited by 14
  34. 2019Neural Replicator Dynamicscited by 13
  35. 2017Stochastic mirror descent dynamics and their convergence in monotone variational inequalitiescited by 5
  36. 2020Linear Last-iterate Convergence in Constrained Saddle-point Optimizationcited by 5
  37. 2019A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Gamescited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 20; 2022: 23; 2023: 22; 2024: 15; 2025: 10; 2026: 7.

97 papers.

Sort:

By area:

  1. 2024A Minimaximalist Approach to Reinforcement Learning from Human Feedbackcited by 141
  2. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  3. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
  4. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  5. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  6. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  7. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
  8. 2025MARFT: Multi-Agent Reinforcement Fine-Tuningcited by 51
  9. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  10. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  11. 2024Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHFcited by 41
  12. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
38 more
  1. 2022Policy Gradient in Robust MDPs with Global Convergence Guaranteecited by 35
  2. 2021Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimizationcited by 34
  3. 2021Independent Natural Policy Gradient Always Converges in Markov Potential Gamescited by 34
  4. 2021Gradient play in stochastic games: stationary points, convergence, and sample complexitycited by 32
  5. 2024Multi-Agent Reinforcement Learning for Autonomous Driving: A Surveycited by 30
  6. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 28
  7. 2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
  8. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  9. 2021Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysiscited by 25
  10. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
  11. 2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
  12. 2022ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regretcited by 24
  13. 2022Policy Mirror Ascent for Efficient and Independent Learning in Mean Field Gamescited by 24
  14. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 22
  15. 2023Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problemscited by 21
  16. 2021Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationalitycited by 20
  17. 2021Independent Learning in Stochastic Gamescited by 20
  18. 2022Independent and Decentralized Learning in Markov Potential Gamescited by 19
  19. 2021Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Gamescited by 18
  20. 2021On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Gamescited by 18
  21. 2022Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Gamescited by 18
  22. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  23. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  24. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  25. 2023Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Setscited by 15
  26. 2023On the Convergence of No-Regret Learning Dynamics in Time-Varying Gamescited by 14
  27. 2022On the convergence of policy gradient methods to Nash equilibria in general stochastic gamescited by 13
  28. 2024FightLadder: A Benchmark for Competitive Multi-Agent Reinforcement Learningcited by 13
  29. 2023Dealing With Non-stationarity in Decentralized Cooperative Multi-Agent Deep Reinforcement Learning via Multi-Timescale Learningcited by 12
  30. 2023Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Gamescited by 12
  31. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 11
  32. 2022Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Gamescited by 11
  33. 2022Adapting to game trees in zero-sum imperfect information gamescited by 11
  34. 2024Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergencecited by 11
  35. 2021Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problemscited by 10
  36. 2022Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularizationcited by 10
  37. 2024Independent Learning in Constrained Markov Potential Gamescited by 10
  38. 2021Satisficing Paths and Independent Multi-Agent Reinforcement Learning in Stochastic Gamescited by 9

50 most cited of 97 All 97 (JSON)