mlsanityData to 14 Oct 2026

ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret

arXiv 2206.04122 ↗First posted 8 Jun 2022cs.GT cs.AI cs.LGcited by 24

Not on the map. Why?

Abstract (arXiv)

Recent techniques for approximating Nash equilibria in very large games leverage neural networks to learn approximately optimal policies (strategies). One promising line of research uses neural networks to approximate counterfactual regret minimization (CFR) or its modern variants. DREAM, the only current CFR-based neural method that is model free and therefore scalable to very large games, trains a neural network on an estimated regret target that can have extremely high variance due to an importance sampling term inherited from Monte Carlo CFR (MCCFR). In this paper we propose an unbiased model-free method that does not require any importance sampling. Our method, ESCHER, is principled and is guaranteed to converge to an approximate Nash equilibrium with high probability. We show that the variance of the estimated regret of ESCHER is orders of magnitude lower than DREAM and other baselines. We then show that ESCHER outperforms the prior state of the art -- DREAM and neural fictitious self play (NFSP) -- on a number of games and the difference becomes dramatic as game size increases. In the very large game of dark chess, ESCHER is able to beat DREAM and NFSP in a head-to-head competition over 90% of the time.

Key facts. Cited by 24 papers in the map (data through 14 Oct 2026). Builds on 42 of its 82 references that are in the map. First posted on arXiv 8 Jun 2022.

Builds on

42 of 82 references.

References · 42

  1. 2017Ray: A Distributed Framework for Emerging AI Applicationscited by 527
  2. 2017Robust Adversarial Reinforcement Learningcited by 451
  3. 2017A Unified Game-Theoretic Approach to Multiagent Reinforcement Learningcited by 268
  4. 2017DeepStack: Expert-Level Artificial Intelligence in No-Limit Pokercited by 233
  5. 2019OpenSpiel: A Framework for Reinforcement Learning in Gamescited by 186
  6. 2019Action Robust Reinforcement Learning and Applications in Continuous Controlcited by 174
  7. 2016Deep Reinforcement Learning from Self-Play in Imperfect-Information Gamescited by 158
  8. 2020Combining Deep Reinforcement Learning and Search for Imperfect-Information Gamescited by 114
  9. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
  10. 2018Deep Counterfactual Regret Minimizationcited by 103
  11. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
  12. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
30 more
  1. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 93
  2. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  3. 2021DouZero: Mastering DouDizhu with Self-Play Deep Reinforcement Learningcited by 66
  4. 2020From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularizationcited by 61
  5. 2020Suphx: Mastering Mahjong with Deep Reinforcement Learningcited by 58
  6. 2020Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descentcited by 57
  7. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 57
  8. 2019A Generalized Training Approach for Multiagent Learningcited by 54
  9. 2020Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Gamescited by 47
  10. 2019Finding Friend and Foe in Multi-Agent Gamescited by 42
  11. 2017Safe and Nested Subgame Solving for Imperfect-Information Gamescited by 41
  12. 2020Human-Level Performance in No-Press Diplomacy via Equilibrium Searchcited by 41
  13. 2021Independent Natural Policy Gradient Always Converges in Markov Potential Gamescited by 37
  14. 2019Rethinking Formal Models of Partially Observable Multiagent Decision Makingcited by 36
  15. 2020DREAM: Deep Regret minimization with Advantage baselines and Model-free learningcited by 36
  16. 2018Actor-Critic Policy Optimization in Partially Observable Multiagent Environmentscited by 35
  17. 2021XDO: A Double Oracle Algorithm for Extensive-Form Gamescited by 34
  18. 2021Gradient play in stochastic games: stationary points, convergence, and sample complexitycited by 34
  19. 2013Solving Imperfect Information Games Using Decompositioncited by 29
  20. 2018Depth-Limited Solving for Imperfect-Information Gamescited by 27
  21. 2021Learning in Nonzero-Sum Stochastic Games with Potentialscited by 26
  22. 2018Variance Reduction in Monte Carlo Counterfactual Regret Minimization (VR-MCCFR) for Extensive Form Games using Baselinescited by 25
  23. 2018Online Convex Optimization for Sequential Decision Processes and Extensive-Form Gamescited by 21
  24. 2019Single Deep Counterfactual Regret Minimizationcited by 20
  25. 2020Stochastic Regret Minimization in Extensive-Form Gamescited by 17
  26. 2020The Advantage Regret-Matching Actor-Criticcited by 17
  27. 2018Double Neural Counterfactual Regret Minimizationcited by 16
  28. 2021Subgame solving without common knowledgecited by 12
  29. 2019Low-Variance and Zero-Variance Baselines for Extensive-Form Gamescited by 9
  30. 2020Model-free Neural Counterfactual Regret Minimization with Bootstrap Learningcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 3; 2023: 6; 2024: 3; 2025: 6; 2026: 6.

24 papers.

Sort:

By area:

  1. 2023ASP: Learn a Universal Neural Solver!cited by 27
  2. 2025Reevaluating Policy Gradient Methods for Imperfect-Information Gamescited by 13
  3. 2022Illusory Attacks: Information-Theoretic Detectability Matters in Adversarial Attackscited by 12
  4. 2022Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Gamescited by 11
  5. 2022Adapting to game trees in zero-sum imperfect information gamescited by 11
  6. 2024Policy Space Response Oracles: A Surveycited by 10
  7. 2023Ensemble Value Functions for Efficient Exploration in Multi-Agent Reinforcement Learningcited by 5
  8. 2024A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergencecited by 5
  9. 2026The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedbackcited by 5
  10. 2023JiangJun: Mastering Xiangqi by Tackling Non-Transitivity in Two-Player Zero-Sum Gamescited by 2
  11. 2023Local and adaptive mirror descents in extensive-form gamescited by 2
  12. 2025NashPG: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibriacited by 2
12 more
  1. 2026Parallelizing Counterfactual Regret Minimizationcited by 2
  2. 2025On the Power of Perturbation under Sampling in Solving Extensive-Form Gamescited by 1
  3. 2025Deep (Predictive) Discounted Counterfactual Regret Minimizationcited by 1
  4. 2026Data-Augmented Game Starts for Accelerating Self-Play Exploration in Imperfect Information Gamescited by 1
  5. 2026EMAgnet: Parameter-Space EMA Regularization for Policy Gradient Self-Play in Large Gamescited by 1
  6. 2026How Much Due Diligence Before You Bid? Learning in Intractable Takeover Auctionscited by 1
  7. 2026AV-AIVAT: 74x Cheaper Agent Evaluation with Certified Anytime-Valid Stopping in Imperfect-Information Gamescited by 1
  8. 2023Game-Theoretic Robust Reinforcement Learning Handles Temporally-Coupled Perturbationscited by 0
  9. 2023AI planning in the imagination: High-level planning on learned abstract search spacescited by 0
  10. 2024Easy as ABCs: Unifying Boltzmann Q-Learning and Counterfactual Regret Minimizationcited by 0
  11. 2025No-Regret Strategy Solving in Imperfect-Information Games via Pre-Trained Embeddingcited by 0
  12. 2025KrwEmd: Revising the Imperfect-Recall Abstraction from Forgetting Everythingcited by 0