Convergence of Monte Carlo Tree Search in Simultaneous Move Games

By Viliam Lisý, Vojtěch Kovařík, Marc Lanctot, Branislav Bosanský. 2013

22 citations recorded by the source corpus.

We study Monte Carlo tree search (MCTS) in zero-sum extensive-form games with perfect information and simultaneous moves. We present a general template of MCTS algorithms for these games, which can be instantiated by various selection methods. We formally prove that if a selection method is e-Hannan consistent in a matrix game and satisfies additional requirements on exploration, then the MCTS algorithm eventually converges to an approximate Nash equilibrium (NE) of the extensive-form game. We empirically evaluate this claim using regret matching and Exp3 as the selection methods on randomly generated games and empirically selected worst case games. We confirm the formal result and show that additional MCTS variants also converge to approximate NE on the evaluated games.

Subfields: Artificial Intelligence, Economics and Econometrics

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 Economics and Econometrics

Citations in the corpus

Online Monte Carlo Counterfactual Regret Minimization for Search in Imperfect Information Games (2015, background): “Variants of MCTS with these selection functions have been shown both formally and empirically [27, 23] to converge to Nash equilibrium in games with simultaneous moves, which are the simplest subclass of imperfect information games.”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, methodology): “With self-play, [302] shows that the average policy obtained by MCTS with any -Hannan consistent policy update method converges to an O(D2 · )-Nash equilibrium, where D is the maximal depth.”