Convergence of Monte Carlo Tree Search in Simultaneous Move Games
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F13%3A00212259" target="_blank" >RIV/68407700:21230/13:00212259 - isvavai.cz</a>
Result on the web
<a href="http://papers.nips.cc/paper/5145-convergence-of-monte-carlo-tree-search-in-simultaneous-move-games" target="_blank" >http://papers.nips.cc/paper/5145-convergence-of-monte-carlo-tree-search-in-simultaneous-move-games</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Convergence of Monte Carlo Tree Search in Simultaneous Move Games
Original language description
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 epsilon-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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GAP202%2F12%2F2054" target="_blank" >GAP202/12/2054: Security Games in Extensive Form</a><br>
Continuities
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Advances in Neural Information Processing Systems 26
ISBN
9781632660244
ISSN
1049-5258
e-ISSN
—
Number of pages
9
Pages from-to
2112-2120
Publisher name
Curran Associates, Inc.
Place of publication
Red Hook
Event location
Reno
Event date
Dec 5, 2013
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—