Near-Optimal Reinforcement Learning with Self-Play

Understand

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.