Near-Optimal Reinforcement Learning with Self-Play

Abstract

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 $\tilde{\mathcal{O}}(S^{2}AB)$ 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 \emph{Nash Q-learning} algorithm with sample complexity $\tilde{\mathcal{O}}(SAB)$, and a new \emph{Nash V-learning} algorithm with sample complexity $\tilde{\mathcal{O}}(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.

References in corpus (9)

• Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• Generalization and Exploration via Randomized Value Functions
• On Lower Bounds for Regret in Reinforcement Learning
• Provable Self-Play Algorithms for Competitive Reinforcement Learning
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity
• Feature-Based Q-Learning for Two-Player Stochastic Games
• Explore no more: Improved high-probability regret bounds for non-stochastic bandits

Cited by in corpus (10)

• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games
• A Sharp Analysis of Model-based Reinforcement Learning with Self-Play
• Minimax Sample Complexity for Turn-based Stochastic Game
• The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces
• Towards General Function Approximation in Zero-Sum Markov Games
• Provably Efficient Algorithms for Multi-Objective Competitive RL
• Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall
• Online Learning in Unknown Markov Games