On Reinforcement Learning for Turn-based Zero-sum Markov Games
This addresses game theory and AI challenges for researchers, though it is incremental as it builds on AlphaGo Zero.
The paper tackles the problem of finding Nash equilibrium in two-player turn-based zero-sum games by proposing a Reinforcement Learning approach called Explore-Improve-Supervise (EIS), which achieves an ε-approximate value function in nearly optimal steps for continuous state-spaces.
We consider the problem of finding Nash equilibrium for two-player turn-based zero-sum games. Inspired by the AlphaGo Zero (AGZ) algorithm, we develop a Reinforcement Learning based approach. Specifically, we propose Explore-Improve-Supervise (EIS) method that combines "exploration", "policy improvement"' and "supervised learning" to find the value function and policy associated with Nash equilibrium. We identify sufficient conditions for convergence and correctness for such an approach. For a concrete instance of EIS where random policy is used for "exploration", Monte-Carlo Tree Search is used for "policy improvement" and Nearest Neighbors is used for "supervised learning", we establish that this method finds an $\varepsilon$-approximate value function of Nash equilibrium in $\widetilde{O}(\varepsilon^{-(d+4)})$ steps when the underlying state-space of the game is continuous and $d$-dimensional. This is nearly optimal as we establish a lower bound of $\widetildeΩ(\varepsilon^{-(d+2)})$ for any policy.