# Decision Making under Imperfect Recall: Algorithms and Benchmarks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 33 of its 81 references that are in the map.
- First posted on arXiv 16 Feb 2026.

## Builds on (most cited first, 30 of 33)

- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Do the Rewards Justify the Means? Measuring Trade-Offs Between Rewards and Ethical Behavior in the MACHIAVELLI Benchmark](https://mlsanity.com/paper/2304.03279/) (2023)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [Evaluating Language-Model Agents on Realistic Autonomous Tasks](https://mlsanity.com/paper/2312.11671/) (2023)
- [Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent](https://mlsanity.com/paper/2007.14358/) (2020)
- [Smooth Calibration, Leaky Forecasts, Finite Recall, and Nash Dynamics](https://mlsanity.com/paper/2210.07152/) (2022)
- [The Complexity of Gradient Descent: CLS = PPAD cap PLS](https://mlsanity.com/paper/2011.01929/) (2020)
- [Regret Matching+: (In)Stability and Fast Convergence in Games](https://mlsanity.com/paper/2305.14709/) (2023)
- [Game Theory with Simulation of Other Players](https://mlsanity.com/paper/2305.11261/) (2023)
- [Team-maxmin equilibrium: efficiency bounds and algorithms](https://mlsanity.com/paper/1611.06134/) (2016)
- [Polynomial-Time Optimal Equilibria with a Mediator in Extensive-Form Games](https://mlsanity.com/paper/2206.15395/) (2022)
- [For Learning in Symmetric Teams, Local Optima are Global Nash Equilibria](https://mlsanity.com/paper/2207.03470/) (2022)
- [Extensive-Form Game Solving via Blackwell Approachability on Treeplexes](https://mlsanity.com/paper/2403.04680/) (2024)
- [AI Testing Should Account for Sophisticated Strategic Behaviour](https://mlsanity.com/paper/2508.14927/) (2025)
- [Imperfect-Recall Abstractions with Bounds in Games](https://mlsanity.com/paper/1409.3302/) (2014)
- [Team Belief DAG: Generalizing the Sequence Form to Team Games for Fast Computation of Correlated Team Max-Min Equilibria via Regret Minimization](https://mlsanity.com/paper/2202.00789/) (2022)
- [The Computational Complexity of Single-Player Imperfect-Recall Games](https://mlsanity.com/paper/2305.17805/) (2023)
- [Pure Nash Equilibria and Best-Response Dynamics in Random Games](https://mlsanity.com/paper/1905.10758/) (2019)
- [A Bridge between Polynomial Optimization and Games with Imperfect Recall](https://mlsanity.com/paper/2002.09941/) (2020)
- [Recursive Joint Simulation in Games](https://mlsanity.com/paper/2402.08128/) (2024)
- [Imperfect-Recall Games: Equilibrium Concepts and Their Complexity](https://mlsanity.com/paper/2406.15970/) (2024)
- [Computing Game Symmetries and Equilibria That Respect Them](https://mlsanity.com/paper/2501.08905/) (2025)
- [LiteEFG: An Efficient Python Library for Solving Extensive-form Games](https://mlsanity.com/paper/2407.20351/) (2024)
- [Game Theory with Simulation in the Presence of Unpredictable Randomisation](https://mlsanity.com/paper/2410.14311/) (2024)
- [Characterising Simulation-Based Program Equilibria](https://mlsanity.com/paper/2412.14570/) (2024)
- [The Value of Recall in Extensive-Form Games](https://mlsanity.com/paper/2412.19659/) (2024)
- [Automated Construction of Bounded-Loss Imperfect-Recall Abstractions in Extensive-Form Games](https://mlsanity.com/paper/1803.05392/) (2018)
- [Convergence of Regret Matching in Potential Games and Constrained Optimization](https://mlsanity.com/paper/2510.17067/) (2025)

## Abstract (arXiv)

In game theory, imperfect-recall decision problems model situations in which an agent forgets information it held before. They encompass games such as the ``absentminded driver'' and team games with limited communication. In this paper, we introduce the first benchmark suite for imperfect-recall decision problems. Our benchmarks capture a variety of problem types, including ones concerning privacy in AI systems that elicit sensitive information, and AI safety via testing of agents in simulation. Across 61 problem instances generated using this suite, we evaluate the performance of different algorithms for finding first-order optimal strategies in such problems. In particular, we introduce the family of regret matching (RM) algorithms for nonlinear constrained optimization. This class of parameter-free algorithms has enjoyed tremendous success in solving large two-player zero-sum games, but, surprisingly, they were hitherto relatively unexplored beyond that setting. Our key finding is that RM algorithms consistently outperform commonly employed first-order optimizers such as projected gradient descent, often by orders of magnitude. This establishes, for the first time, the RM family as a formidable approach to large-scale constrained optimization problems.