ICML 2023 – Adapting to game trees in zero-sum imperfect information games

In this episode we discuss Adapting to game trees in zero-sum imperfect information games
by Côme Fiegel, Pierre Ménard, Tadashi Kozuno, Rémi Munos, Vianney Perchet, Michal Valko. The paper presents two Follow the Regularized Leader (FTRL) algorithms for learning ε-optimal strategies in zero-sum imperfect information games (IIGs). Players have uncertainty about the true game state, and the set of states controlled by a player is partitioned into information sets. The Balanced FTRL algorithm matches a lower bound on the required number of realizations to learn optimal strategies, while the Adaptive FTRL algorithm progressively adapts the regularization to observations and reduces the required number of realizations.