mlsanityData to 14 Oct 2026

Safe and Nested Subgame Solving for Imperfect-Information Games

arXiv 1705.02955 ↗First posted 8 May 2017cs.AI cs.GTcited by 41

Not on the map. Why?

Abstract (arXiv)

In imperfect-information games, the optimal strategy in a subgame may depend on the strategy in other, unreached subgames. Thus a subgame cannot be solved in isolation and must instead consider the strategy for the entire game as a whole, unlike perfect-information games. Nevertheless, it is possible to first approximate a solution for the whole game and then improve it by solving individual subgames. This is referred to as subgame solving. We introduce subgame-solving techniques that outperform prior methods both in theory and practice. We also show how to adapt them, and past subgame-solving techniques, to respond to opponent actions that are outside the original action abstraction; this significantly outperforms the prior state-of-the-art approach, action translation. Finally, we show that subgame solving can be repeated as the game progresses down the game tree, leading to far lower exploitability. These techniques were a key component of Libratus, the first AI to defeat top humans in heads-up no-limit Texas hold'em poker.

Key facts. Cited by 41 papers in the map (data through 14 Oct 2026). First posted on arXiv 8 May 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 9; 2022: 4; 2023: 7; 2024: 3; 2025: 7; 2026: 11.

41 papers.

Sort:

By area:

  1. 2021Learning to run a Power Network Challenge: a Retrospective Analysiscited by 55
  2. 2022ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regretcited by 24
  3. 2021Student of Games: A unified learning algorithm for both perfect and imperfect information gamescited by 23
  4. 2024PokerGPT: An End-to-End Lightweight Solver for Multi-Player Texas Hold'em via Large Language Modelcited by 20
  5. 2021Solving Common-Payoff Games with Approximate Policy Iterationcited by 15
  6. 2021Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Gamescited by 15
  7. 2024RL-CFR: Improving Action Abstraction for Imperfect Information Extensive-Form Games with Reinforcement Learningcited by 10
  8. 2025Scalable Decision Making for Games of Imperfect Informationcited by 8
  9. 2022A Marriage between Adversarial Team Games and 2-player Games: Enabling Abstractions, No-regret Learning, and Subgame Solvingcited by 7
  10. 2024Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descentcited by 7
  11. 2023Abstracting Imperfect Information Away from Two-Player Zero-Sum Gamescited by 6
  12. 2025General search techniques without common knowledge for imperfect-information games, and application to superhuman Fog of War chesscited by 6
29 more
  1. 2025Confucius3-Math: A Lightweight High-Performance Reasoning LLM for Chinese K-12 Mathematics Learningcited by 5
  2. 2025A Theory of Inference Compute Scaling: Reasoning through Directed Stochastic Skill Searchcited by 5
  3. 2026PokerSkill: LLMs Can Play Expert-Level Poker without Training or Solverscited by 5
  4. 2023Hierarchical Deep Counterfactual Regret Minimizationcited by 4
  5. 2026Agents That Certify Their Own Exploits: Confidence-Scheduled Restricted Responses for Safe Opponent Exploitationcited by 4
  6. 2021Safe Search for Stackelberg Equilibria in Extensive-Form Gamescited by 3
  7. 2022A Survey of Decision Making in Adversarial Gamescited by 3
  8. 2023The Update-Equivalence Framework for Decision-Time Planningcited by 3
  9. 2026GTO Wizard Benchmarkcited by 3
  10. 2023Accelerate Multi-Agent Reinforcement Learning in Zero-Sum Games with Subgame Curriculum Learningcited by 2
  11. 2026Solver-Guided Reasoning for Mixed-Equilibrium Strategiescited by 2
  12. 2021D2CFR: Minimize Counterfactual Regret with Deep Dueling Neural Networkcited by 1
  13. 2021AI in Human-computer Gaming: Techniques, Challenges and Opportunitiescited by 1
  14. 2022Safe adaptation in multiagent competitioncited by 1
  15. 2023CFR-p: Counterfactual Regret Minimization with Hierarchical Policy Abstraction, and its Application to Two-player Mahjongcited by 1
  16. 2025Beyond Outcome-Based Imperfect-Recall: Higher-Resolution Abstractions for Imperfect-Information Gamescited by 1
  17. 2026AV-AIVAT: 74x Cheaper Agent Evaluation with Certified Anytime-Valid Stopping in Imperfect-Information Gamescited by 1
  18. 2021Towards a Sample Efficient Reinforcement Learning Pipeline for Vision Based Roboticscited by 0
  19. 2021A Fast Algorithm for Computing the Deficiency Number of a Mahjong Handcited by 0
  20. 2023Game-Theoretic Robust Reinforcement Learning Handles Temporally-Coupled Perturbationscited by 0
  21. 2023AI planning in the imagination: High-level planning on learned abstract search spacescited by 0
  22. 2025Safety Game: Inference-Time Alignment of Black-Box LLMs via Constrained Optimizationcited by 0
  23. 2025Outbidding and Outbluffing Elite Humans: Mastering Liar's Poker via Self-Play and Reinforcement Learningcited by 0
  24. 2026OpenGuanDan: A Large-Scale Imperfect Information Game Benchmarkcited by 0
  25. 2026PokaiTrainer: Scaling Equilibrium Search to Competitive Pok'emon VGCcited by 0
  26. 2026Test-time Reinforcement Learning in Imperfect Information Gamescited by 0
  27. 2026GPU-CFR: 80x Faster Counterfactual Regret Minimization by Compiling the Game to Static Dataflow and CUDA Graph Replaycited by 0
  28. 2026RSD-Poker: Structure-Adaptive and Shift-Robust Risk-Utility Certification for Residual Policies in Imperfect-Information Gamescited by 0
  29. 2026SafeAdapt-Poker: Counterfactual Risk Calibration for Budgeted Adaptation under Opponent Shiftcited by 0