Abstract
Self-play, where the algorithm learns by playing against itself withoutrequiring any direct supervision, has become the new weapon in modernReinforcement Learning (RL) for achieving superhuman performance in practice.However, the majority of exisiting theory in reinforcement learning onlyapplies to the setting where the agent plays against a fixed environment. Itremains largely open whether self-play algorithms can be provably effective,especially when it is necessary to manage the exploration/exploitationtradeoff. We study self-play in competitive reinforcement learning under the setting ofMarkov games, a generalization of Markov decision processes to the two-playercase. We introduce a self-play algorithm---Value Iteration with Upper/LowerConfidence Bound (VI-ULCB), and show that it achieves regret$\mathcal{\tilde{O}}(\sqrt{T})$ after playing $T$ steps of the game. The regretis measured by the agent's performance against a \emph{fully adversarial}opponent who can exploit the agent's strategy at \emph{any} step. We alsointroduce an explore-then-exploit style algorithm, which achieves a slightlyworse regret of $\mathcal{\tilde{O}}(T^{2/3})$, but is guaranteed to run inpolynomial time even in the worst case. To the best of our knowledge, our workpresents the first line of provably sample-efficient self-play algorithms forcompetitive reinforcement learning.