# Near-Optimal Reinforcement Learning with Self-Play

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

## Key facts

- Cited by 109 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2020.

## Built on by (most cited first, 30 of 109)

- [Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning](https://mlsanity.com/paper/2106.04895/) (2021)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Dueling RL: Reinforcement Learning with Trajectory Preferences](https://mlsanity.com/paper/2111.04850/) (2021)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games](https://mlsanity.com/paper/2102.04540/) (2021)
- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Decentralized Q-Learning in Zero-sum Markov Games](https://mlsanity.com/paper/2106.02748/) (2021)
- [The Complexity of Markov Equilibrium in Stochastic Games](https://mlsanity.com/paper/2204.03991/) (2022)
- [The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces](https://mlsanity.com/paper/2106.03352/) (2021)
- [Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learning](https://mlsanity.com/paper/2407.00617/) (2024)
- [Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability](https://mlsanity.com/paper/2111.12306/) (2021)
- [Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets](https://mlsanity.com/paper/2202.07511/) (2022)
- [Towards General Function Approximation in Zero-Sum Markov Games](https://mlsanity.com/paper/2107.14702/) (2021)
- [Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games](https://mlsanity.com/paper/2110.05682/) (2021)
- [Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games](https://mlsanity.com/paper/2102.11494/) (2021)
- [On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2110.05707/) (2021)
- [Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus](https://mlsanity.com/paper/2206.00159/) (2022)
- [Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation](https://mlsanity.com/paper/2302.06606/) (2023)
- [Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2303.02738/) (2023)
- [When is Offline Two-Player Zero-Sum Markov Game Solvable?](https://mlsanity.com/paper/2201.03522/) (2022)
- [Sample-Efficient Reinforcement Learning of Partially Observable Markov Games](https://mlsanity.com/paper/2206.01315/) (2022)
- [Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation](https://mlsanity.com/paper/2302.03673/) (2023)
- [Near-Optimal Learning of Extensive-Form Games with Imperfect Information](https://mlsanity.com/paper/2202.01752/) (2022)
- [Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games](https://mlsanity.com/paper/2210.01050/) (2022)
- [Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Games](https://mlsanity.com/paper/2102.07404/) (2021)
- [Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?](https://mlsanity.com/paper/2112.13521/) (2021)
- [Regret Minimization and Convergence to Equilibria in General-sum Markov Games](https://mlsanity.com/paper/2207.14211/) (2022)
- [Improving LLM General Preference Alignment via Optimistic Online Mirror Descent](https://mlsanity.com/paper/2502.16852/) (2025)
- [Provably Efficient Algorithms for Multi-Objective Competitive RL](https://mlsanity.com/paper/2102.03192/) (2021)
- [Independent Learning in Stochastic Games](https://mlsanity.com/paper/2111.11743/) (2021)

## 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.