# Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 58 references that are in the map.
- First posted on arXiv 13 Feb 2021.

## Builds on (most cited first, 19 of 19)

- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Deep Counterfactual Regret Minimization](https://mlsanity.com/paper/1811.00164/) (2018)
- [Solving Large Imperfect Information Games Using CFR+](https://mlsanity.com/paper/1407.5042/) (2014)
- [Bayesian Action Decoder for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1811.01458/) (2018)
- [Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent](https://mlsanity.com/paper/2007.14358/) (2020)
- [DREAM: Deep Regret minimization with Advantage baselines and Model-free learning](https://mlsanity.com/paper/2006.10410/) (2020)
- [Variance Reduction in Monte Carlo Counterfactual Regret Minimization (VR-MCCFR) for Extensive Form Games using Baselines](https://mlsanity.com/paper/1809.03057/) (2018)
- [Correlation in Extensive-Form Games: Saddle-Point Formulation and Benchmarks](https://mlsanity.com/paper/1905.12564/) (2019)
- [Hindsight and Sequential Rationality of Correlated Play](https://mlsanity.com/paper/2012.05874/) (2020)
- [Stable-Predictive Optimistic Counterfactual Regret Minimization](https://mlsanity.com/paper/1902.04982/) (2019)
- [Coarse Correlation in Extensive-Form Games](https://mlsanity.com/paper/1908.09893/) (2019)
- [Solving Games with Functional Regret Estimation](https://mlsanity.com/paper/1411.7974/) (2014)
- [Low-Variance and Zero-Variance Baselines for Extensive-Form Games](https://mlsanity.com/paper/1907.09633/) (2019)
- [A Unified View of Large-scale Zero-sum Equilibrium Computation](https://mlsanity.com/paper/1411.5007/) (2014)
- [Alternative Function Approximation Parameterizations for Solving Games: An Analysis of f-Regression Counterfactual Regret Minimization](https://mlsanity.com/paper/1912.02967/) (2019)
- [Combining No-regret and Q-learning](https://mlsanity.com/paper/1910.03094/) (2019)
- [Optimistic and Adaptive Lagrangian Hedging](https://mlsanity.com/paper/2101.09603/) (2021)

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

- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Near-Optimal Learning of Extensive-Form Games with Imperfect Information](https://mlsanity.com/paper/2202.01752/) (2022)
- [Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2104.01520/) (2021)
- [Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent](https://mlsanity.com/paper/2205.15294/) (2022)
- [Rethinking the Foundations for Continual Reinforcement Learning](https://mlsanity.com/paper/2504.08161/) (2025)
- [Learning Correlated Equilibria in Mean-Field Games](https://mlsanity.com/paper/2208.10138/) (2022)
- [Expected Variational Inequalities](https://mlsanity.com/paper/2502.18605/) (2025)
- [Learning and Computation of Phi-Equilibria at the Frontier of Tractability](https://mlsanity.com/paper/2502.18582/) (2025)
- [Near-Optimal Phi-Regret Learning in Extensive-Form Games](https://mlsanity.com/paper/2208.09747/) (2022)
- [Guarantees for Self-Play in Multiplayer Games via Polymatrix Decomposability](https://mlsanity.com/paper/2310.11518/) (2023)
- [An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to Phi-Regret Minimization](https://mlsanity.com/paper/2604.19592/) (2026)
- [Evolutionary Dynamics and Phi-Regret Minimization in Games](https://mlsanity.com/paper/2106.14668/) (2021)
- [The Partially Observable History Process](https://mlsanity.com/paper/2111.08102/) (2021)
- [Safe Subgame Resolving for Extensive Form Correlated Equilibrium](https://mlsanity.com/paper/2212.14317/) (2022)
- [Normal-Form Correlation in Markov Games](https://mlsanity.com/paper/2610.03621/) (2026)

## Abstract (arXiv)

Hindsight rationality is an approach to playing general-sum games that prescribes no-regret learning dynamics for individual agents with respect to a set of deviations, and further describes jointly rational behavior among multiple agents with mediated equilibria. To develop hindsight rational learning in sequential decision-making settings, we formalize behavioral deviations as a general class of deviations that respect the structure of extensive-form games. Integrating the idea of time selection into counterfactual regret minimization (CFR), we introduce the extensive-form regret minimization (EFR) algorithm that achieves hindsight rationality for any given set of behavioral deviations with computation that scales closely with the complexity of the set. We identify behavioral deviation subsets, the partial sequence deviation types, that subsume previously studied types and lead to efficient EFR instances in games with moderate lengths. In addition, we present a thorough empirical analysis of EFR instantiated with different deviation types in benchmark games, where we find that stronger types typically induce better performance.