Adapting to game trees in zero-sum imperfect information games

Côme Fiegel; Pierre Ménard; Tadashi Kozuno; Rémi Munos; Vianney Perchet; Michal Valko

Adapting to game trees in zero-sum imperfect information games

Côme Fiegel
, Pierre Ménard
, Tadashi Kozuno
, Rémi Munos
, Vianney Perchet
, Michal Valko

Ecole Normale Supérieure de Lyon
Omron Sinic X
DeepMind Technologies Limited
ENSAE & Criteo AI Lab.

Research output: Contribution to journal › Conference article › peer-review

Abstract

Imperfect information games (IIG) are games in which each player only partially observes the current game state. We study how to learn ε-optimal strategies in a zero-sum IIG through self-play with trajectory feedback. We give a problem-independent lower bound Õ(H(A_X + B_Y)/ε²) on the required number of realizations to learn these strategies with high probability, where H is the length of the game, A_X and B_Y are the total number of actions for the two players. We also propose two Follow the Regularized leader (FTRL) algorithms for this setting: Balanced FTRL which matches this lower bound, but requires the knowledge of the information set structure beforehand to define the regularization; and Adaptive FTRL which needs Õ(H²(A_X + B_Y)/ε²) realizations without this requirement by progressively adapting the regularization to the observations.

Original language	English
Pages (from-to)	10093-10135
Number of pages	43
Journal	Proceedings of Machine Learning Research
Volume	202
Publication status	Published - 1 Jan 2023
Event	40th International Conference on Machine Learning, ICML 2023 - Honolulu, United States Duration: 23 Jul 2023 → 29 Jul 2023

Cite this

@article{8401d2067d29400190235f8e9ca862b7,

title = "Adapting to game trees in zero-sum imperfect information games",

abstract = "Imperfect information games (IIG) are games in which each player only partially observes the current game state. We study how to learn ε-optimal strategies in a zero-sum IIG through self-play with trajectory feedback. We give a problem-independent lower bound {\~O}(H(AX + BY)/ε2) on the required number of realizations to learn these strategies with high probability, where H is the length of the game, AX and BY are the total number of actions for the two players. We also propose two Follow the Regularized leader (FTRL) algorithms for this setting: Balanced FTRL which matches this lower bound, but requires the knowledge of the information set structure beforehand to define the regularization; and Adaptive FTRL which needs {\~O}(H2(AX + BY)/ε2) realizations without this requirement by progressively adapting the regularization to the observations.",

author = "C{\^o}me Fiegel and Pierre M{\'e}nard and Tadashi Kozuno and R{\'e}mi Munos and Vianney Perchet and Michal Valko",

note = "Publisher Copyright: {\textcopyright} 2023 Proceedings of Machine Learning Research. All rights reserved.; 40th International Conference on Machine Learning, ICML 2023 ; Conference date: 23-07-2023 Through 29-07-2023",

year = "2023",

month = jan,

day = "1",

language = "English",

volume = "202",

pages = "10093--10135",

journal = "Proceedings of Machine Learning Research",

issn = "2640-3498",

}

TY - JOUR

T1 - Adapting to game trees in zero-sum imperfect information games

AU - Fiegel, Côme

AU - Ménard, Pierre

AU - Kozuno, Tadashi

AU - Munos, Rémi

AU - Perchet, Vianney

AU - Valko, Michal

PY - 2023/1/1

Y1 - 2023/1/1

N2 - Imperfect information games (IIG) are games in which each player only partially observes the current game state. We study how to learn ε-optimal strategies in a zero-sum IIG through self-play with trajectory feedback. We give a problem-independent lower bound Õ(H(AX + BY)/ε2) on the required number of realizations to learn these strategies with high probability, where H is the length of the game, AX and BY are the total number of actions for the two players. We also propose two Follow the Regularized leader (FTRL) algorithms for this setting: Balanced FTRL which matches this lower bound, but requires the knowledge of the information set structure beforehand to define the regularization; and Adaptive FTRL which needs Õ(H2(AX + BY)/ε2) realizations without this requirement by progressively adapting the regularization to the observations.

AB - Imperfect information games (IIG) are games in which each player only partially observes the current game state. We study how to learn ε-optimal strategies in a zero-sum IIG through self-play with trajectory feedback. We give a problem-independent lower bound Õ(H(AX + BY)/ε2) on the required number of realizations to learn these strategies with high probability, where H is the length of the game, AX and BY are the total number of actions for the two players. We also propose two Follow the Regularized leader (FTRL) algorithms for this setting: Balanced FTRL which matches this lower bound, but requires the knowledge of the information set structure beforehand to define the regularization; and Adaptive FTRL which needs Õ(H2(AX + BY)/ε2) realizations without this requirement by progressively adapting the regularization to the observations.

UR - https://www.scopus.com/pages/publications/85174403232

M3 - Conference article

AN - SCOPUS:85174403232

SN - 2640-3498

VL - 202

SP - 10093

EP - 10135

JO - Proceedings of Machine Learning Research

JF - Proceedings of Machine Learning Research

T2 - 40th International Conference on Machine Learning, ICML 2023

Y2 - 23 July 2023 through 29 July 2023

ER -

Adapting to game trees in zero-sum imperfect information games

Abstract

Other files and links

Fingerprint

Cite this