Look-ahead Search on Top of Policy Networks in Imperfect Information Games

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F24%3A00377053" target="_blank" >RIV/68407700:21230/24:00377053 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.24963/ijcai.2024/480" target="_blank" >https://doi.org/10.24963/ijcai.2024/480</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.24963/ijcai.2024/480" target="_blank" >10.24963/ijcai.2024/480</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Look-ahead Search on Top of Policy Networks in Imperfect Information Games

Popis výsledku v původním jazyce

Search in test time is often used to improve the performance of reinforcement learning algorithms. Performing theoretically sound search in fully adversarial two-player games with imperfect information is notoriously difficult and requires a complicated training process. We present a method for adding test-time search to an arbitrary policy-gradient algorithm that learns from sampled trajectories. Besides the policy network, the algorithm trains an additional critic network, which estimates the expected values of players following various transformations of the policies given by the policy network. These values are then used for depth-limited search. We show how the values from this critic can create a value function for imperfect information games. Moreover, they can be used to compute the summary statistics necessary to start the search from an arbitrary decision point in the game. The presented algorithm is scalable to very large games since it does not require any search during train time. We evaluate the algorithm's performance when trained along Regularized Nash Dynamics, and we evaluate the benefit of using the search in the standard benchmark game of Leduc hold'em, multiple variants of imperfect information Goofspiel, and Battleships.

Název v anglickém jazyce

Look-ahead Search on Top of Policy Networks in Imperfect Information Games

Popis výsledku anglicky

Search in test time is often used to improve the performance of reinforcement learning algorithms. Performing theoretically sound search in fully adversarial two-player games with imperfect information is notoriously difficult and requires a complicated training process. We present a method for adding test-time search to an arbitrary policy-gradient algorithm that learns from sampled trajectories. Besides the policy network, the algorithm trains an additional critic network, which estimates the expected values of players following various transformations of the policies given by the policy network. These values are then used for depth-limited search. We show how the values from this critic can create a value function for imperfect information games. Moreover, they can be used to compute the summary statistics necessary to start the search from an arbitrary decision point in the game. The presented algorithm is scalable to very large games since it does not require any search during train time. We evaluate the algorithm's performance when trained along Regularized Nash Dynamics, and we evaluate the benefit of using the search in the standard benchmark game of Leduc hold'em, multiple variants of imperfect information Goofspiel, and Battleships.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

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

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

Rok uplatnění

2024

Kód důvěrnosti údajů

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

Název statě ve sborníku

Proceedings of the 33rd International Joint Conference on Artificial Intelligence

ISBN

978-1-956792-04-1

ISSN

1045-0823

e-ISSN

—

Počet stran výsledku

9

Strana od-do

4344-4352

Název nakladatele

International Joint Conferences on Artificial Intelligence Organization

Místo vydání

—

Místo konání akce

Jeju

Datum konání akce

3. 8. 2024

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001347142804052