Decision Making under Imperfect Recall: Algorithms and Benchmarks

Emanuel Tewolde; Brian Hu Zhang; Ioannis Anagnostides; Tuomas Sandholm; Vincent Conitzer

cs.GTFeb 16, 2026

Decision Making under Imperfect Recall: Algorithms and Benchmarks

Authors: Emanuel Tewolde, Brian Hu Zhang, Ioannis Anagnostides, Tuomas Sandholm, Vincent Conitzer

Organizations: Computer Science Dept., Carnegie Mellon University, Pittsburgh, USA · Foundations of Cooperative AI Lab (FOCAL) · Strategy Robot, Inc.; Strategic Machine, Inc.; and Optimized Markets, Inc.

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: Three tree-form decision problems, discussed after Definition 1 . The top and bottom ones are of imperfect recall. The right one further exhibits absentmindedness.

Figure 2

Panel of Figure 3 — Figure 3: Subgroup detection under privacy constraints. On the left, we see an arbitrary graph with two subgroups (a $3$ -clique, and a star of degree $3$ ). The goal is to find as many of the subgroups’ nodes as possible. On the right, we see another such decision problem on a 2D grid, which we visualized as an instance of the Absentminded Battleship game. The agent has already succeeded in hitting one node of each ship, which indicates that there must be more subgroup nodes nearby. The agent does not remember whether it has selected any cell other than these two before.

Category	Metric	Gurobi	GD	OGD	AMS	RM	$\texttt{RM}^{\text{+}}$	PRM	$\texttt{PRM}^{\text{+}}$
Utility value	% of best $(\uparrow)$	36.1	44.3	44.3	60.7	70.5	70.5	73.8	70.5
Utility value	avg. rank $(\downarrow)$	6.25	4.99	5.28	4.16	3.93	3.79	3.79	3.81
Convergence	% reached $(\uparrow)$	27.9	72.1	72.1	98.4	83.6	90.2	78.7	80.3
	% of best $(\uparrow)$	0.0	11.5	6.6	37.7	29.5	21.3	18.0	18.0
	avg. rank $(\downarrow)$	8.00	5.08	5.84	3.35	2.80	2.70	4.24	3.99

Table 1: Top table: Statistics that aggregate the full experiments in the appendix. We report how often an algorithm reached convergence across all

61

benchmark instances, and relative to the other algorithms, how well it ranks on average (lower is better), and how often it achieved the best value / convergence. Bottom table: The performance of various algorithms in a subset of our benchmarks. Value and convergence winners per game highlighted in bold. For Gurobi , time is only reported if it terminated.

Figure 4: Benchmark problem instances with

\sim

800 infosets,

\sim

300 infosets, 3 infosets, and

\sim

100 infosets respectively.

Appendix figures & tables66 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 5 — Figure 5: This is the decision making instance one would obtain from applying the construction of the proof of Theorem 1 to the polynomial maximization $\max 2x^{2}y-3xyz$ s.t. $0\leq x,y,z\leq 1$ .

Panel of Figure 6 — Figure 6: Deployment phase $\Gamma^{\prime}$ of the more complex simulation problem with two scenarios given in Figure 2 (bottom). In deployment, the agent acts at least once and up to two times in total. The “good” and “bad” actions yield different immediate payoffs in different scenarios, and they contribute additively to the total payoffs at terminal nodes.

Figure 7: A family of polynomial optimization problems over the unit interval on which the RM and GD families of algorithms perform arbitrarily poorly.

Figure 8: Examples in which particular first-order optimizers are likely to perform arbitrarily bad in value while others converge to the global optimum (if not initialized at

x^{*}=1/2

exactly). On the left, the gradient descent methods initialized closer to the middle will converge to the local optimum at

x^{*}=1/2

while the regret matching methods converge to the global optima. On the contrary, regret matching methods on the right will converge to the global minimum (which is also first-order maximal) while the gradient descent methods converge to the global optimum.

Problem	Gurobi		GD			OGD			AMS			RM			$\texttt{RM}^{\text{+}}$			PRM			$\texttt{PRM}^{\text{+}}$
	value	time	value	time	gap	value	time	gap	value	time	gap	value	time	gap	value	time	gap	value	time	gap	value	time	gap
Det-86	18.00	0.22s	18.00	0.01s	—	18.00	0.01s	—	18.00	0.02s	—	18.00	0.00s	—	18.00	0.00s	—	18.00	0.00s	—	18.00	0.00s	—
Det-105	12.00	1.86s	12.00	0.01s	—	12.00	0.01s	—	12.00	0.02s	—	12.00	0.00s	—	12.00	0.00s	—	12.00	0.00s	—	12.00	0.00s	—
Det-1k	13.00	1m 24s	13.00	0.13s	—	13.00	0.07s	—	13.00	0.13s	—	13.00	0.32s	—	13.00	0.36s	—	13.00	0.38s	—	13.00	0.41s	—
Det-1.8k	22.00	2m 40s	22.00	0.06s	—	22.00	0.07s	—	22.00	0.13s	—	22.00	0.03s	—	22.00	0.03s	—	22.00	0.03s	—	22.00	0.03s	—
Det-2.0k	17.50	1m 42s	17.50	0.03s	—	17.50	0.05s	—	17.50	0.06s	—	17.50	0.03s	—	17.50	0.03s	—	17.50	0.03s	—	17.50	0.03s	—

Appendix

Table 2: Experimental results for the full set of benchmarks and the full set of algorithms. The winners per game in terms of value and convergence are highlighted in bold.

Figure 12

Figure 13

Figure 14

Figure 15

Figure 16

Figure 17

Figure 18

Figure 19

Figure 20

Figure 21

Figure 22

Figure 23

Figure 24

Figure 25

Figure 26

Figure 27

Figure 28

Figure 29

Figure 30

Figure 31

Figure 32

Figure 33

Figure 34

Figure 35

Figure 36

Figure 37

Figure 38

Figure 39

Figure 40

Figure 41

Figure 42

Figure 43

Figure 44

Figure 45

Figure 46

Figure 47

Figure 48

Figure 49

Figure 50

Figure 51

Figure 52

Figure 53

Figure 54

Figure 55

Figure 56

Figure 57

Figure 58

Figure 59

Figure 60

Figure 61

Figure 62

Figure 63

Figure 64

Figure 65

Figure 66

Figure 67

Figure 68

Figure 69

Figure 70

Figure 71

Figure 72

Sequential Decision Making

Sequential Decision Making studies how to choose actions over time when outcomes, information, resources, or goals can change.

See all 139 papers

IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence
Oct 13, 2026Michael Sullins, Ian A. KashCounterfactual Regret Minimization Regret Minimization
University of Illinois Chicago, Chicago, Illinois, USA
Multiplicative Optimism for Constant Regret in Games
Sep 18, 2026Ashkan Soleymani, Georgios PiliourasRegret Minimization Game-Based Learning
MIT · Google Deepmind
Valet: A Standardized Testbed of Traditional Imperfect-Information Card Games
Mar 3, 2026Mark Goadrich, Achille Morenville, Éric PietteImperfect-Information Games AI Agent Benchmarks
Hendrix College, Conway AR 72032, USA · ICTEAM, UCLouvain, Louvain-la-Neuve, Belgium

Oct 13, 2026J/K move · Enter open · S save

IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence

Michael Sullins, Ian A. Kash

University of Illinois Chicago, Chicago, Illinois, USA

Counterfactual Regret Minimization Regret Minimization Nash Equilibrium Computation Zero-Sum Games Imperfect-Information Games

Open paper AskPDF arXiv

Regret matching (and its variants) and counterfactual regret minimization are central algorithms in practice for normal-form and extensive-form game solving. Yet these have historically lacked the stronger theoretical convergence guarantees available to optimistic and extra-gradient methods. Recent work introduced IREG-PRM+, a regret matching variant which does have strong theoretical convergence guarantees. However, it relies on a simultaneous, extra-gradient update. IREG-PRM+ is an instance of the more general IR-PRM framework, where empirically optimistic and alternating updates often have better performance. However, the prior extra-gradient analysis does not extend to these cases. We introduce a new approach that covers both settings. For simultaneous and alternating IR-PRM+ in finite two-player zero-sum matrix games, previous-utility prediction recovers the constant-regret and convergence-rate guarantees previously obtained with extra-gradient prediction: external regret bounded independently of T, an O(T^{-1}) average duality gap, and an O(T^{-1/2}) best-current-iterate gap. Moreover, the current duality gap vanishes and the current profile converges to the Nash equilibrium set. The key step bounds the component of consecutive strategy movement not controlled by the existing IR-PRM+ regret inequality using the relative growth of the nondecreasing regret-vector norm rho_t. Coupling this bound across the two players yields recurrences whose effective coefficient scales as 1/(rho_t^X rho_t^Y), preventing unbounded norm growth. We extend the analysis to finitely many simplex learners under a weighted Minty condition and, through the corresponding CFR variant IR-PCFR+, recover analogous guarantees for finite two-player zero-sum perfect-recall extensive-form games under the same full-reach condition as prior work.

Abstract

Sequential Decision Making

Explore similar work

IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence

Multiplicative Optimism for Constant Regret in Games

Valet: A Standardized Testbed of Traditional Imperfect-Information Card Games