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

arXiv: https://arxiv.org/abs/2206.04122 · HTML: https://mlsanity.com/paper/2206.04122/

## 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 (most cited first, 30 of 42)

- [Ray: A Distributed Framework for Emerging AI Applications](https://mlsanity.com/paper/1712.05889/) (2017)
- [Robust Adversarial Reinforcement Learning](https://mlsanity.com/paper/1703.02702/) (2017)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Action Robust Reinforcement Learning and Applications in Continuous Control](https://mlsanity.com/paper/1901.09184/) (2019)
- [Deep Reinforcement Learning from Self-Play in Imperfect-Information Games](https://mlsanity.com/paper/1603.01121/) (2016)
- [Combining Deep Reinforcement Learning and Search for Imperfect-Information Games](https://mlsanity.com/paper/2007.13544/) (2020)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Deep Counterfactual Regret Minimization](https://mlsanity.com/paper/1811.00164/) (2018)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium](https://mlsanity.com/paper/2002.07066/) (2020)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [Online Reinforcement Learning in Stochastic Games](https://mlsanity.com/paper/1712.00579/) (2017)
- [DouZero: Mastering DouDizhu with Self-Play Deep Reinforcement Learning](https://mlsanity.com/paper/2106.06135/) (2021)
- [From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization](https://mlsanity.com/paper/2002.08456/) (2020)
- [Suphx: Mastering Mahjong with Deep Reinforcement Learning](https://mlsanity.com/paper/2003.13590/) (2020)
- [Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent](https://mlsanity.com/paper/2007.14358/) (2020)
- [Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence](https://mlsanity.com/paper/2202.04129/) (2022)
- [A Generalized Training Approach for Multiagent Learning](https://mlsanity.com/paper/1909.12823/) (2019)
- [Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games](https://mlsanity.com/paper/2006.08555/) (2020)
- [Finding Friend and Foe in Multi-Agent Games](https://mlsanity.com/paper/1906.02330/) (2019)
- [Safe and Nested Subgame Solving for Imperfect-Information Games](https://mlsanity.com/paper/1705.02955/) (2017)
- [Human-Level Performance in No-Press Diplomacy via Equilibrium Search](https://mlsanity.com/paper/2010.02923/) (2020)
- [Independent Natural Policy Gradient Always Converges in Markov Potential Games](https://mlsanity.com/paper/2110.10614/) (2021)
- [Rethinking Formal Models of Partially Observable Multiagent Decision Making](https://mlsanity.com/paper/1906.11110/) (2019)
- [DREAM: Deep Regret minimization with Advantage baselines and Model-free learning](https://mlsanity.com/paper/2006.10410/) (2020)
- [Actor-Critic Policy Optimization in Partially Observable Multiagent Environments](https://mlsanity.com/paper/1810.09026/) (2018)
- [XDO: A Double Oracle Algorithm for Extensive-Form Games](https://mlsanity.com/paper/2103.06426/) (2021)
- [Gradient play in stochastic games: stationary points, convergence, and sample complexity](https://mlsanity.com/paper/2106.00198/) (2021)

## Built on by (most cited first, 24 of 24)

- [ASP: Learn a Universal Neural Solver!](https://mlsanity.com/paper/2303.00466/) (2023)
- [Reevaluating Policy Gradient Methods for Imperfect-Information Games](https://mlsanity.com/paper/2502.08938/) (2025)
- [Illusory Attacks: Information-Theoretic Detectability Matters in Adversarial Attacks](https://mlsanity.com/paper/2207.10170/) (2022)
- [Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2207.06541/) (2022)
- [Adapting to game trees in zero-sum imperfect information games](https://mlsanity.com/paper/2212.12567/) (2022)
- [Policy Space Response Oracles: A Survey](https://mlsanity.com/paper/2403.02227/) (2024)
- [Ensemble Value Functions for Efficient Exploration in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2302.03439/) (2023)
- [A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergence](https://mlsanity.com/paper/2408.00751/) (2024)
- [The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2604.16087/) (2026)
- [JiangJun: Mastering Xiangqi by Tackling Non-Transitivity in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2308.04719/) (2023)
- [Local and adaptive mirror descents in extensive-form games](https://mlsanity.com/paper/2309.00656/) (2023)
- [NashPG: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibria](https://mlsanity.com/paper/2510.18183/) (2025)
- [Parallelizing Counterfactual Regret Minimization](https://mlsanity.com/paper/2605.14277/) (2026)
- [On the Power of Perturbation under Sampling in Solving Extensive-Form Games](https://mlsanity.com/paper/2501.16600/) (2025)
- [Deep (Predictive) Discounted Counterfactual Regret Minimization](https://mlsanity.com/paper/2511.08174/) (2025)
- [Data-Augmented Game Starts for Accelerating Self-Play Exploration in Imperfect Information Games](https://mlsanity.com/paper/2605.14379/) (2026)
- [EMAgnet: Parameter-Space EMA Regularization for Policy Gradient Self-Play in Large Games](https://mlsanity.com/paper/2606.23995/) (2026)
- [How Much Due Diligence Before You Bid? Learning in Intractable Takeover Auctions](https://mlsanity.com/paper/2606.29457/) (2026)
- [AV-AIVAT: 74x Cheaper Agent Evaluation with Certified Anytime-Valid Stopping in Imperfect-Information Games](https://mlsanity.com/paper/2608.06362/) (2026)
- [Game-Theoretic Robust Reinforcement Learning Handles Temporally-Coupled Perturbations](https://mlsanity.com/paper/2307.12062/) (2023)
- [AI planning in the imagination: High-level planning on learned abstract search spaces](https://mlsanity.com/paper/2308.08693/) (2023)
- [Easy as ABCs: Unifying Boltzmann Q-Learning and Counterfactual Regret Minimization](https://mlsanity.com/paper/2402.11835/) (2024)
- [No-Regret Strategy Solving in Imperfect-Information Games via Pre-Trained Embedding](https://mlsanity.com/paper/2511.12083/) (2025)
- [KrwEmd: Revising the Imperfect-Recall Abstraction from Forgetting Everything](https://mlsanity.com/paper/2511.12089/) (2025)

## 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.