Analysis of Hannan consistent selection for Monte Carlo tree search in simultaneous move games

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F20%3A00333064" target="_blank" >RIV/68407700:21230/20:00333064 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1007/s10994-019-05832-z" target="_blank" >https://doi.org/10.1007/s10994-019-05832-z</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10994-019-05832-z" target="_blank" >10.1007/s10994-019-05832-z</a>

Result language

angličtina

Original language name

Analysis of Hannan consistent selection for Monte Carlo tree search in simultaneous move games

Original language description

Hannan consistency, or no external regret, is a key concept for learning in games. An action selection algorithm is Hannan consistent (HC) if its performance is eventually as good as selecting the best fixed action in hindsight. If both players in a zero-sum normal form game use a Hannan consistent algorithm, their average behavior converges to a Nash equilibrium of the game. A similar result is known about extensive form games, but the played strategies need to be Hannan consistent with respect to the counterfactual values, which are often difficult to obtain. We study zero-sum extensive form games with simultaneous moves, but otherwise perfect information. These games generalize normal form games and they are a special case of extensive form games. We study whether applying HC algorithms in each decision point of these games directly to the observed payoffs leads to convergence to a Nash equilibrium. This learning process corresponds to a class of Monte Carlo Tree Search algorithms, which are popular for playing simultaneous-move games but do not have any known performance guarantees. We show that using HC algorithms directly on the observed payoffs is not sufficient to guarantee the convergence. With an additional averaging over joint actions, the convergence is guaranteed, but empirically slower. We further define an additional property of HC algorithms, which is sufficient to guarantee the convergence without the averaging and we empirically show that commonly used HC algorithms have this property.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2020

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Machine Learning

ISSN

0885-6125

e-ISSN

1573-0565

Volume of the periodical

109

Issue of the periodical within the volume

1

Country of publishing house

US - UNITED STATES

Number of pages

50

Pages from-to

1-50

UT code for WoS article

000512049900001

EID of the result in the Scopus database

2-s2.0-85069750687