Papers › Adapting to game trees in zero-sum imperfect information games
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
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_𝒳+B_𝒴)/ϵ²) on the required number of realizations to learn these strategies with high probability, where H is the length of the game, A_𝒳 and B_𝒴 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_𝒳+B_𝒴)/ϵ²) realizations without this requirement by progressively adapting the regularization to the observations.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections