mlsanityData to 7 Oct 2026

Near-Optimal Learning of Extensive-Form Games with Imperfect Information

arXiv 2202.01752 ↗First posted 3 Feb 2022cs.LG cs.AI cs.GTcited by 26

Not on the map. Why?

Abstract (arXiv)

This paper resolves the open question of designing near-optimal algorithms for learning imperfect-information extensive-form games from bandit feedback. We present the first line of algorithms that require only widetildeO((XA+YB)/varepsilon2) episodes of play to find an varepsilon-approximate Nash equilibrium in two-player zero-sum games, where X,Y are the number of information sets and A,B are the number of actions for the two players. This improves upon the best known sample complexity of widetildeO((X2A+Y2B)/varepsilon2) by a factor of widetildeO(maxX, Y), and matches the information-theoretic lower bound up to logarithmic factors. We achieve this sample complexity by two new algorithms: Balanced Online Mirror Descent, and Balanced Counterfactual Regret Minimization. Both algorithms rely on novel approaches of integrating balanced exploration policies into their classical counterparts. We also extend our results to learning Coarse Correlated Equilibria in multi-player general-sum games.

Key facts. Cited by 26 papers in the map (data through 7 Oct 2026). Builds on 41 of its 77 references that are in the map. First posted on arXiv 3 Feb 2022.

Builds on

41 of 77 references.

References · 41

  1. 2017DeepStack: Expert-Level Artificial Intelligence in No-Limit Pokercited by 228
  2. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  3. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  4. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  5. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  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
29 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. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  4. 2020Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descentcited by 56
  5. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  6. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  7. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  8. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 41
  9. 2019Rethinking Formal Models of Partially Observable Multiagent Decision Makingcited by 35
  10. 2021Last-iterate Convergence in Extensive-Form Gamescited by 27
  11. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  12. 2018Variance Reduction in Monte Carlo Counterfactual Regret Minimization (VR-MCCFR) for Extensive Form Games using Baselinescited by 24
  13. 2021Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibriumcited by 22
  14. 2020Hindsight and Sequential Rationality of Correlated Playcited by 21
  15. 2021Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recallcited by 21
  16. 2018Revisiting CFR+ and Alternating Updatescited by 19
  17. 2020No-Regret Learning Dynamics for Extensive-Form Correlated Equilibriumcited by 19
  18. 2019Coarse Correlation in Extensive-Form Gamescited by 17
  19. 2020Stochastic Regret Minimization in Extensive-Form Gamescited by 17
  20. 2018Solving Large Sequential Games with the Excessive Gap Techniquecited by 16
  21. 2021Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Gamescited by 15
  22. 2013Measuring the Size of Large No-Limit Poker Gamescited by 14
  23. 2021Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Gamescited by 14
  24. 2020Joint Policy Search for Multi-agent Collaboration with Imperfect Informationcited by 13
  25. 2014Solving Games with Functional Regret Estimationcited by 12
  26. 2021Model-Free Online Learning in Unknown Sequential Decision Making Problems and Gamescited by 12
  27. 2018Lazy-CFR: fast and near optimal regret minimization for extensive games with imperfect informationcited by 8
  28. 2015Timeability of Extensive-Form Gamescited by 7
  29. 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: 2022: 10; 2023: 4; 2024: 4; 2025: 4; 2026: 4.

26 papers.

Sort:

By area:

  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. 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 26
  4. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  5. 2025Improving LLM General Preference Alignment via Optimistic Online Mirror Descentcited by 24
  6. 2022Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descentcited by 15
  7. 2023Policy Space Diversity for Non-Transitive Gamescited by 15
  8. 2022Adapting to game trees in zero-sum imperfect information gamescited by 11
  9. 2022Sample-Efficient Learning of Correlated Equilibria in Extensive-Form Gamescited by 7
  10. 2024A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergencecited by 5
  11. 2022A Survey of Decision Making in Adversarial Gamescited by 3
  12. 2022A Deep Reinforcement Learning Approach for Finding Non-Exploitable Strategies in Two-Player Atari Gamescited by 3
14 more
  1. 2022Near-Optimal Phi-Regret Learning in Extensive-Form Gamescited by 3
  2. 2023A Black-box Approach for Non-stationary Multi-agent Reinforcement Learningcited by 3
  3. 2023Local and adaptive mirror descents in extensive-form gamescited by 2
  4. 2024On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Gamescited by 2
  5. 2022Generalized Bandit Regret Minimizer Framework in Imperfect Information Extensive-Form Gamecited by 1
  6. 2025On the Power of Perturbation under Sampling in Solving Extensive-Form Gamescited by 1
  7. 2025Best of Both Worlds: Regret Minimization versus Minimax Playcited by 1
  8. 2026Differential Privacy in the Extensive-Form Bandit Problemcited by 1
  9. 2022Learning Rationalizable Equilibria in Multiplayer Gamescited by 0
  10. 2024Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Gamescited by 0
  11. 2025The Fair Game: Auditing & Debiasing AI Algorithms Over Timecited by 0
  12. 2026On-line Learning in Tree MDPs by Treating Policies as Bandit Armscited by 0
  13. 2026Reinforcement Learning: From Algorithms To Foundation Modelscited by 0
  14. 2026Tracking the Best Strategy in an Extensive-Form Gamecited by 0