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
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
Figure 2: Top: A simple simulation problem. The misaligned agent receives 10 utility for its preferred action (which is the bad action for the simulator), and 1 utility for the other. The simulator decides to simulate with \nicefrac45 probability, and up to at most 2 times, in order to catch misaligned behavior in advance. Bottom: A slightly more complex simulation problem with two testing scenarios. The “deployment” phase / subgame Γ′ is visualized in the appendix.
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
RM+
PRM
PRM+
Utility value
% of best (↑)
36.1
44.3
44.3
60.7
70.5
70.5
73.8
70.5
avg. rank (↓)
6.25
4.99
5.28
4.16
3.93
3.79
3.79
3.81
Convergence
% reached (↑)
27.9
72.1
72.1
98.4
83.6
90.2
78.7
80.3
% of best (↑)
0.0
11.5
6.6
37.7
29.5
21.3
18.0
18.0
avg. rank (↓)
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 ∼ 800 infosets, ∼ 300 infosets, 3 infosets, and ∼ 100 infosets respectively.
Appendix figures & tables66 assets
Supplementary material from the paper’s appendix.
Appendix
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 max2x2y−3xyz s.t. 0≤x,y,z≤1 .
Figure 6: Deployment phase Γ′ 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
RM+
PRM
PRM+
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.
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.
Michael Sullins, Ian A. Kash
University of Illinois Chicago, Chicago, Illinois, USA
We introduce Multiplicatively Optimistic Regret Matching (MORM), an uncoupled learning rule for finite general-sum games. Under simultaneous full-information self-play, every player achieves external regret O(nlogd) uniformly over all horizons, using only one-step optimism. The analysis combines a potential-based regret-matching argument with multiplicative stability and Hellinger control of strategy movement. A learning-rate safeguard additionally gives O(Tlogd) regret in the face of adversarial utilities.
AI algorithms for imperfect-information games are typically compared using performance metrics on individual games, making it difficult to assess robustness across game choices. Card games are a natural domain for imperfect information due to hidden hands and stochastic draws. To facilitate comparative research on imperfect-information game-playing algorithms and game systems, we introduce Valet, a diverse and comprehensive testbed of 21 traditional imperfect-information card games. These games span multiple genres, cultures, player counts, deck structures, mechanics, winning conditions, and methods of hiding and revealing information. To standardize implementations across systems, we encode the rules of each game in RECYCLE, a card game description language. We empirically characterize each game's branching factor and duration using random simulations, reporting baseline score distributions for a Monte Carlo Tree Search player against random opponents to demonstrate the suitability of Valet as a benchmarking suite.
Mark Goadrich, Achille Morenville, Éric Piette
Hendrix College, Conway AR 72032, USA · ICTEAM, UCLouvain, Louvain-la-Neuve, Belgium