mlsanityData to 7 Oct 2026

Adapting to game trees in zero-sum imperfect information games

arXiv 2212.12567 ↗First posted 23 Dec 2022stat.ML cs.LGcited by 11

Not on the map. Why?

Abstract (arXiv)

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 widetildeO(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 widetildeO(H2(AX+BY)/ε2) realizations without this requirement by progressively adapting the regularization to the observations.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 27 of its 67 references that are in the map. First posted on arXiv 23 Dec 2022.

Builds on

27 of 67 references.

References · 27

  1. 2017DeepStack: Expert-Level Artificial Intelligence in No-Limit Pokercited by 228
  2. 2019OpenSpiel: A Framework for Reinforcement Learning in Gamescited by 180
  3. 2022Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learningcited by 129
  4. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
  5. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  6. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  7. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  8. 2018Deep Counterfactual Regret Minimizationcited by 102
  9. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  10. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  11. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
  12. 2014Solving Large Imperfect Information Games Using CFR+cited by 78
15 more
  1. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  2. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  3. 2020Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descentcited by 56
  4. 2015Fighting Bandits with a New Kind of Smoothnesscited by 45
  5. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 41
  6. 2021Last-iterate Convergence in Extensive-Form Gamescited by 27
  7. 2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
  8. 2018Variance Reduction in Monte Carlo Counterfactual Regret Minimization (VR-MCCFR) for Extensive Form Games using Baselinescited by 24
  9. 2022ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regretcited by 24
  10. 2018Revisiting CFR+ and Alternating Updatescited by 19
  11. 2020Stochastic Regret Minimization in Extensive-Form Gamescited by 17
  12. 2018Solving Large Sequential Games with the Excessive Gap Techniquecited by 16
  13. 2021Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Gamescited by 15
  14. 2014A Unified View of Large-scale Zero-sum Equilibrium Computationcited by 7
  15. 2020Finding and Certifying (Near-)Optimal Strategies in Black-Box Extensive-Form Gamescited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 3; 2025: 4; 2026: 2.

11 papers.

  1. 2024Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learningcited by 45
  2. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  3. 2024A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergencecited by 5
  4. 2025Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversariescited by 5
  5. 2023Local and adaptive mirror descents in extensive-form gamescited by 2
  6. 2024On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Gamescited by 2
  7. 2025On the Power of Perturbation under Sampling in Solving Extensive-Form Gamescited by 1
  8. 2025Best of Both Worlds: Regret Minimization versus Minimax Playcited by 1
  9. 2026Differential Privacy in the Extensive-Form Bandit Problemcited by 1
  10. 2025The Fair Game: Auditing & Debiasing AI Algorithms Over Timecited by 0
  11. 2026Tracking the Best Strategy in an Extensive-Form Gamecited by 0