Provable Self-Play Algorithms for Competitive Reinforcement Learning

By Yu Bai, Chi Jin. 2020

173 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Industrial and Manufacturing Engineering, Management Science and Operations Research, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Industrial and Manufacturing Engineering

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, background): “Bai and Jin (2020); Bai et al. (2020); Liu et al. (2021) address the problems from finite action two player markov games, while Xie et al. (2020) extended this setting to zero sum games with linear function approximation.”
Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization (2021, background): “…signiﬁcant interests from AI researchers (Heinrich & Silver, 2016; Lanctot et al., 2017; Foerster et al., 2018; Kamra et al., 2019; Han & Hu, 2019; Bai & Jin, 2020; Perolat et al., 2020): many existing works studied how to design practical multi-agent reinforcement learning (MARL) algorithms that…”
Near-Optimal Reinforcement Learning with Self-Play (2020, methodology): “In contrast, value iteration type algorithms do not enjoy such an independence property, which is why the best existing sample complexity scales as S(2) [2].”
Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability (2021, methodology): “While the specific formulations vary considerably, one formulation can be seen as a multi-step generalization of (contextual) dueling bandits, where regret is measured using our best response notion (which, as discussed, subsumes many other notion in the literature) (Bai and Jin, 2020; Xie et al., 2”
A Sharp Analysis of Model-based Reinforcement Learning with Self-Play (2020, methodology): “…current best sample complexity for model-based algorithms is achieved by the VI-ULCB (Value Iteration with Upper/Lower Confidence Bounds) algorithm (Bai & Jin, 2020; Xie et al., 2020): In a tabular Markov game with S states, {A,B} actions for the two players, and horizon length H , VI-ULCB is able…”