Provable Self-Play Algorithms for Competitive Reinforcement Learning

Abstract

Self-play, where the algorithm learns by playing against itself without requiring any direct supervision, has become the new weapon in modern Reinforcement Learning (RL) for achieving superhuman performance in practice. However, the majority of exisiting theory in reinforcement learning only applies to the setting where the agent plays against a fixed environment; it remains largely open whether self-play algorithms can be provably effective, especially when it is necessary to manage the exploration/exploitation tradeoff. We study self-play in competitive reinforcement learning under the setting of Markov games, a generalization of Markov decision processes to the two-player case. We introduce a self-play algorithm---Value Iteration with Upper/Lower Confidence Bound (VI-ULCB)---and show that it achieves regret $\tilde{\mathcal{O}}(\sqrt{T})$ after playing $T$ steps of the game, where the regret is measured by the agent's performance against a \emph{fully adversarial} opponent who can exploit the agent's strategy at \emph{any} step. We also introduce an explore-then-exploit style algorithm, which achieves a slightly worse regret of $\tilde{\mathcal{O}}(T^{2/3})$, but is guaranteed to run in polynomial time even in the worst case. To the best of our knowledge, our work presents the first line of provably sample-efficient self-play algorithms for competitive reinforcement learning.

arXiv commentAppearing at ICML 2020. Fixed typos from v1

References in corpus (8)

• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• Generalization and Exploration via Randomized Value Functions
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• On Lower Bounds for Regret in Reinforcement Learning
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity
• Reward-Free Exploration for Reinforcement Learning
• Feature-Based Q-Learning for Two-Player Stochastic Games

Cited by in corpus (24)

• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
• Near-Optimal Reinforcement Learning with Self-Play
• Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games
• Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games
• V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL
• Dynamic Regret of Policy Optimization in Non-stationary Environments
• Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization
• Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret
• Decentralized Q-Learning in Zero-sum Markov Games
• When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?
• A Sharp Analysis of Model-based Reinforcement Learning with Self-Play
• The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces
• Towards General Function Approximation in Zero-Sum Markov Games
• Independent Learning in Stochastic Games
• Dueling RL: Reinforcement Learning with Trajectory Preferences
• Off-Policy Exploitability-Evaluation in Two-Player 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
• Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver
• Efficient Competitive Self-Play Policy Optimization
• Online Learning in Unknown Markov Games
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability