mlsanityData to 7 Oct 2026

Near-Optimal Reinforcement Learning with Self-Play

arXiv 2006.12007 ↗First posted 22 Jun 2020cs.LG cs.AI stat.MLcited by 108

Not on the map. Why?

Abstract (arXiv)

This paper considers the problem of designing optimal algorithms for reinforcement learning in two-player zero-sum games. We focus on self-play algorithms which learn the optimal policy by playing against itself without any direct supervision. In a tabular episodic Markov game with S states, A max-player actions and B min-player actions, the best existing algorithm for finding an approximate Nash equilibrium requires tildeO(S2AB) steps of game playing, when only highlighting the dependency on (S,A,B). In contrast, the best existing lower bound scales as Omega(S(A+B)) and has a significant gap from the upper bound. This paper closes this gap for the first time: we propose an optimistic variant of the Nash Q-learning algorithm with sample complexity tildeO(SAB), and a new Nash V-learning algorithm with sample complexity tildeO(S(A+B)). The latter result matches the information-theoretic lower bound in all problem-dependent parameters except for a polynomial factor of the length of each episode. In addition, we present a computational hardness result for learning the best responses against a fixed opponent in Markov games---a learning objective different from finding the Nash equilibrium.

Key facts. Cited by 108 papers in the map (data through 7 Oct 2026). First posted on arXiv 22 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 26; 2022: 26; 2023: 20; 2024: 23; 2025: 5; 2026: 8.

108 papers.

Sort:

By area:

  1. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  2. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  3. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  4. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  5. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  6. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  7. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
  8. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  9. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  10. 2024Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learningcited by 45
  11. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  12. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
38 more
  1. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  2. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 42
  3. 2021Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Gamescited by 40
  4. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
  5. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 29
  6. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  7. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 28
  8. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 27
  9. 2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
  10. 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 26
  11. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  12. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  13. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
  14. 2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
  15. 2025Improving LLM General Preference Alignment via Optimistic Online Mirror Descentcited by 24
  16. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 22
  17. 2021Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recallcited by 21
  18. 2021Provably Efficient Algorithms for Multi-Objective Competitive RLcited by 20
  19. 2021Independent Learning in Stochastic Gamescited by 20
  20. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  21. 2022Independent and Decentralized Learning in Markov Potential Gamescited by 19
  22. 2021Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Gamescited by 18
  23. 2022Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limitscited by 17
  24. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  25. 2023Offline Learning in Markov Games with General Function Approximationcited by 16
  26. 2026Reuse your FLOPs: Scaling RL on Hard Problems by Conditioning on Very Off-Policy Prefixescited by 16
  27. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  28. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  29. 2022Efficient Model-based Multi-agent Reinforcement Learning via Optimistic Equilibrium Computationcited by 14
  30. 2022A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Gamescited by 14
  31. 2022Representation Learning for General-sum Low-rank Markov Gamescited by 14
  32. 2024Efficacy of Language Model Self-Play in Non-Zero-Sum Gamescited by 14
  33. 2023On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximationcited by 13
  34. 2023Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learningcited by 13
  35. 2024Performative Reinforcement Learning in Gradually Shifting Environmentscited by 13
  36. 2024Toward Optimal LLM Alignments Using Two-Player Gamescited by 13
  37. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 11
  38. 2022O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Gamescited by 11

50 most cited of 108 All 108 (JSON)