Near-Optimal Reinforcement Learning with Self-Play

By Yunru Bai, Chi Jin, Tiancheng Yu. 2020

149 citations recorded by the source corpus.

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^2AB)$ 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.

Subfields: Artificial Intelligence, 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 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.”
A Sharp Analysis of Model-based Reinforcement Learning with Self-Play (2020, methodology): “…and model-free algorithms have been shown to be provably efficient in multi-agent RL in a recent line of work (Bai & Jin, 2020; Xie et al., 2020; Bai et al., 2020), a more precise understanding of the optimal sample complexities within these two types of algorithms (respectively) is still…”
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”