Heuristic solvers for general-sum extensive-form games produce a stream of iterates, and practice reports the NashGap of the returned profile. We ask what a solver can know about its own iterates from the regret accumulators and the terminal-distribution accumulators its updates already maintain. In two-player games the NashGap of a weighted average strategy equals, at the maximizing player, the weighted external regret plus a signed value correction. Bounding the regret by the running counterfactual-regret accumulator gives an online certificate whose cost per checkpoint is linear in the number of terminal histories. The certificate stays sound under alternating updates and in games with three or more players. The mismatch between what alternation evaluates and what the averages record enters as one signed comparator term, maximized in a single backward pass per player whose comparator weight is nonzero. The bound is read off the regret state, with no best response against the average. Run a portfolio of training-free regret-matching solvers, output the iterate with the smallest certificate, and verify that iterate once. On the benchmark's biased Leduc family a pool of sixteen training-free solvers, seven original and nine recent variants, solves 89% of the 64 instances at threshold 10−5 this way, matching the trajectory-minimum union of the solvers. The same protocol solves 92% of the 64 pre-registered held-out instances and 89% again on a third set of 64 instances that no earlier stage used. The zero-best-response certificate certifies all 57 in-sample solves and all 57 fresh ones, and 58 of the 59 held-out ones. Its exact-comparator refinement certifies every solve in the three sets. The certificate states both and attributes its bound. Code is available at https://github.com/lbn187/CertNE.
Figures & tables
Figure 1: Two selection protocols on the same K solvers and m checkpoints per solver. a, Exact evaluation scores every candidate with n best-response (BR) passes, costing Kmn passes overall, and outputs the minimum-gap strategy with its exact gap. b, Online certification combines signed regret, value correction, and comparator terms (Proposition 9 ). C0 uses accumulators alone; C1 adds one signed backward pass per player with nonzero comparator weight at each checkpoint. Either certificate selects its own argmin across solvers and checkpoints and bounds the selected strategy’s NashGap. Optional verification evaluates only that strategy, with n BR passes (Corollary 10 ). Nodes, trees and policy glyphs are schematic; arrows on trees indicate backward traversal.
fraction of games with NashGap ≤
Method
10−2
10−3
10−4
10−5
Reported
CFR +
1
0
0
0
PCFR +
1
0.87
0.48
0.16
NPCFR + (oracle)
1
0.98
0.96
0.96
Controls (outside the pool)
Table 1: Biased Leduc, solved fractions at four thresholds on the 64 paired instances. Reported rows are figures of Sychrovský et al. (2026) ; the rest are our runs. Single-solver rows are trajectory-minimum oracles. Selection rows give exact gaps, and certified rows count certificates below the threshold. Control rows are outside both portfolios; the full names of the added solvers are in Appendix E .
Figure 2: Tightness over the 16×64×128 biased-Leduc checkpoints whose exact gap is above floating-point zero (excludes 3,223 checkpoints, all but 31 on HS-PCFR + ): an ECDF of certificate over true NashGap for C1 and C0 (Proposition 9 ), the aligned start-of-round certificate, and the unaligned shortcut of Corollary 5 under alternation. Sound certificates lie at ratio ≥1 . Iteration traces are in Figures 4 and 5 .
Solver
min NashGap
at t
C1 at T
ratio
C0
ratio
MD form
Added solvers
PDCFR + , p=5
1.17×10−6
59392
3.26×10−6
2.41×
1.73×10−5
12.8×
8.59×10−5
HS-PCFR +
2.16×10−6
T
2.83×10−6
1.31×
2.83×10−6
1.3×
2.85×10−6
Stable PRM + , p=2
1.59×10−5
T
4.29×10−5
2.70×
3.76×10−4
23.7×
1.02×10−3
DCFR + , p=4
7.68×10−5
33792
3.25×10−4
3.75×
4.08×10−3
47.1×
1.57×10−2
DCFR, p=2
1.11×10−4
15360
7.68×10−4
3.34×
9.05×10−3
39.4×
3.60×10−2
Table 2: Three-player Leduc ( T=216 , deterministic single runs). The min NashGap column is the trajectory minimum with the checkpoint t at which it is attained; C1 , C0 and the MD relaxation are the certificates of Proposition 9 at T , with ratios to the true gap at T . All solvers use alternating updates. Reported rows are from Table 6 of Sychrovský et al. (2026) ; n/a marks quantities that study does not publish.
Figure 3: Slack attribution on three-player Leduc (PRM + , p=2 , alternating, log–log). The MD−i form of the certificate sits 11.7 – 241× above the true NashGap over training; the zero-BR C0 replaces MD−i by ∥wi∥1 and tightens it to 2.9 – 59× ; the exact comparator C1 (one backward pass per player per checkpoint) reaches 1.39 – 5.2× .
Protocol
Exact-gap queries
Guarantee
Selection by C0
0
Layer II bound
Selection by C1
one signed backward pass per checkpoint under two-player alternation; 0 for simultaneous updates
Layer II bound
One-shot verification
1
exact NashGap(σ^)
Trajectory minimum
per checkpoint
evaluation protocol
Table 3: Verification budgets (one gap evaluation equals n best-response passes). C1 spends one signed backward pass per player whose comparator weight is nonzero, the second mover alone under two-player alternation. C1 ’s pass maximizes a logged linear functional, not a best response against the average; one-shot verification is exact for the selected snapshot. The oracle protocol uses about 19 evaluations on the reference schedule and 128 on our dense two-player grid. C1 costs nothing extra when the comparator weight vanishes, as it does for simultaneous updates in two-player games.
Ours, C0 / C1
Ours, aligned
Reported
(Prop. 9 )
(extra pass)
NPCFR +
Training trajectories
16 solvers
16 solvers
1
Instances
64 (paired)
64 (paired)
not stated
Iterations per run
218
218
218
Tree passes per iteration
n=2
2n=4
not reported
Candidate snapshots
16×128=2048
16×128=2048
≈19
Table 4: Compute budget behind Table 1 (biased Leduc). One gap evaluation equals n=2 best-response passes, and the timed policy is PRM + , p=2 . The isolated block times each term alone on one core outside the training loop; the end-to-end and checkpoint-work blocks time full runs with three repeats per policy in shuffled order ( mean[min,max] ). n/a marks a cell the measurement does not cover; “not reported” marks a value the reference does not publish. The bare solver, exact-gap selection row is a later re-measurement, with the uninstrumented baseline of its own batch at 81.9 s.
Layer
BR cost
Status
I. Exact identity (2p)
exact Rˉ
equality; not a deployment signal
II. C0 , zero-BR certificate
0
theorem-backed upper bound, any update order and n
II. C1 , exact comparator
1 signed pass per player with wi=0 , per ckpt.
theorem-backed upper bound; tighter
II. Aligned start-of-round bound
1 extra regret pass per player per iteration
theorem-backed upper bound; looser (ablation)
III. One-shot verification
1 gap
exact selected gap only
Trajectory minimum
per ckpt.
post-hoc evaluation protocol
Table 5: The three guarantee layers, with their best-response cost and status. One gap evaluation equals n best-response passes.
7 solvers (Stage 1)
16 solvers (Stage 2)
Selector
seeds 0 – 63
seeds 64 – 127
seeds 0 – 63
seeds 64 – 127
C1 selection
54/64[0.74,0.91]
56/64[0.77,0.94]
57/64[0.81,0.97]
59/64[0.83,0.97]
C0 selection
54/64
56/64
57/64
59/64
Value-corrected maxi[Ri+Δi(i)]
54/64
56/64
57/64
59/64
Exact-gap selection, same grid
54/64
56/64
57/64
59/64
Regret-only selection
53/64
54/64
49/64
56/64
Table 6: Solved counts at 10−5 on the in-sample and held-out instance sets for the seven-solver pool of Stage 1 and the sixteen-solver pool of Stage 2, all from the stored checkpoint histories; brackets on the C1 rows are the frozen migration bands (in-sample) and 95% Wilson intervals (held-out). The C0 and value-corrected rows are diagnostic ablations; the frozen selectors are C1 , regret-only and exact-gap.
Selector
7 solvers
16 solvers
C1 selection
55/64
57/64[0.81,0.97]
C0 selection
54/64
57/64
Value-corrected maxi[Ri+Δi(i)]
55/64
57/64
Exact-gap selection, same grid
55/64
57/64
Regret-only selection
55/64
53/64
Certified C1
54/64
57/64
Table 7: Solved counts at 10−5 on the fresh instance set (seeds 128 – 191 , Stage 3) for the seven-solver pool and the sixteen-solver pool, from the stored checkpoint histories; the bracket on the C1 row is the frozen band and the row definitions are those of Table 6 .
Instance set
Median
90 th pct.
Max
Excluded
In-sample
1.01
1.36
42.45
28
Held-out
1.01
2.67
33.11
26
Fresh
1.00
1.74
17.07
25
Table 8: Selected gap relative to the exact trajectory minimum, per instance (sixteen-solver pool; in-sample seeds 0 – 63 , held-out 64 – 127 , fresh 128 – 191 ). The ratio is reported over the instances whose minimum is above 10−12 ; “excluded” counts the remaining instances, on all of which the selected gap is also at or below 10−12 .
Figure 4: Failure analysis (biased Leduc, sixteen-solver pool, threshold 10−5 ). (a) NashGap at the C1 -selected iterate versus tie-refund fraction β ; the dotted line is the threshold, and the cluster at 10−15 is floating-point zero, where HS-PCFR + is selected. (b) On the seven unsolved instances, C1 against the true gap, with the 1× and 2× lines.
Figure 5: Certificates over training (biased Leduc, PRM + p=2 , median and interquartile band over 64 instances, log–log): the true NashGap, C1 , C0 , the aligned start-of-round certificate and the Pinsker bound of Proposition 3 .
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Pool
solvers
selection C1
certified C1
certified C0
aligned
oracle union
PRM + -core
3
0.80
0.72
0.70
0.77
0.80
no DPRM +
4
0.70
0.64
0.64
0.67
0.70
original
7
0.84
0.75
0.73
0.80
0.84
+ discounting
10
0.84
0.77
0.77
0.81
0.84
+ schedules
9
0.84
0.77
0.73
0.81
0.84
+ stabilised RM +
10
0.88
0.88
0.88
0.88
0.88
Appendix
Table 9: Pool ablation at threshold 10−5 (biased Leduc, n=64 paired). PRM + -core contains PRM + with p∈{1,2} and DPRM + with p=2,λ=0.3 ; no DPRM + contains RM + and PRM + with p∈{1,2} ; original contains the seven solvers of the first stage; the “ + ” rows add one family of the extension to them (discounting: DCFR, DCFR + , PDCFR + ; schedules: HS-PCFR + , HS-DCFR; stabilised: Smooth PRM + , Stable PRM + , ExRM + ); all contains the sixteen solvers. Selection is the exact gap at the cross-solver C1 argmin, certified columns count instances whose selected certificate is below the threshold, aligned is selection by the start-of-round certificate, and oracle union is the pool’s best trajectory minimum, which exact-gap selection on the same grid attains.
Threshold
C1 selection
Oracle union
Aligned selection
Certified C1
Certified C0
10−2
64 ( 64 )
64 ( 64 )
64 ( 64 )
64 ( 64 )
64 ( 64 )
10−3
64 ( 64 )
64 ( 64 )
64 ( 64 )
64 ( 64 )
64 ( 64 )
10−4
62 ( 58 )
62 ( 58 )
62 ( 58 )
62 ( 57 )
62 ( 56 )
10−5
57 ( 54 )
57 ( 54 )
57 ( 51 )
57 ( 48 )
57 ( 47 )
Appendix
Table 10: Solved counts (of 64 paired biased-Leduc instances) at each threshold for C1 selection, the solvers’ trajectory-minimum union, selection by the aligned start-of-round certificate, and the certified counts; the sixteen-solver pool, with the seven-solver counts in parentheses.
Solver
10−2
10−3
10−4
10−5
select
RM + , p=1
1.00
0.50
0.00
0.00
0.00
RM + , p=2
1.00
0.52
0.00
0.00
0.00
PRM + , p=1
1.00
1.00
0.88
0.67
0.67
PRM + , p=2
1.00
1.00
0.89
0.70
0.70
DPRM + , p=1 , λ=0.3
1.00
1.00
0.88
0.73
0.73
DPRM + , p=2 , λ=0.1
1.00
1.00
0.88
0.67
0.67
Appendix
Table 11: Per-solver solved fractions, biased Leduc, n=64 paired instances, T=218 . The first four columns are the oracle trajectory-minimum protocol; the last column reports the C1 -argmin extractable fraction within that solver alone, at threshold 10−5 ( n/a on the two portfolio rows, which are not single solvers). All solvers use alternating updates except ExRM + (simultaneous).
Solver
C1
aligned
regret-only
R+Δ(i)
final
random
oracle
RM + , p=1
0.00
0.00
0.00
0.00
0.00
0.00
0.00
RM + , p=2
0.00
0.00
0.00
0.00
0.00
0.00
0.00
PRM + , p=1
0.67
0.67
0.67
0.67
0.66
0.57
0.67
PRM + , p=2
0.70
0.67
0.70
0.70
0.67
0.60
0.70
DPRM + , p=1 , λ=0.3
0.73
0.72
0.72
0.73
0.70
0.55
0.73
DPRM + , p=2 , λ=0.1
0.67
0.64
0.66
0.67
0.62
0.51
0.67
Appendix
Table 12: Per-solver selection-policy ablation at threshold 10−5 (computed from the stored checkpoint histories; see the text above for the policy definitions). Random values are expectations over one uniform checkpoint draw.
best
portfolio
Game
pool
solver
C1 select.
certified C1
oracle
ratio
Sheriff
7 solvers
1.00
1.00
1.00
1.00
11.4×
16 solvers
1.00
1.00
1.00
1.00
n/a
Goofspiel GS( 5 )
7 solvers
0.50
0.56
0.45
0.58
8.3×
16 solvers
0.53
0.62
0.58
0.64
2.0×
Appendix
Table 13: External validity at threshold 10−5 ( n=64 paired instances per game, T=216 ; the seven-solver pool of the first stage and the sixteen-solver pool). “Best solver” is the strongest solver’s oracle fraction; selection is the exact gap at the cross-solver C1 argmin; certified counts instances whose selected C1 is below the threshold; oracle is the pool union, attained by exact-gap selection on the same grid; ratio is the median of C1 over the exact gap at the selected iterate, over instances whose selected gap is above 10−12 ; n/a marks the Sheriff sixteen-solver cell, where every selection gap is below it. Table 14 gives all solvers.
Solver
oracle
C1 select.
certified
ratio
Sheriff
RM + , p=1
0.42
0.38
0.00
3.0×
RM + , p=2
0.53
0.42
0.00
2.9×
PRM + , p=1
1.00
1.00
1.00
17.2×
PRM + , p=2
1.00
1.00
1.00
12.1×
DPRM + , p=1 , λ=0.3
1.00
1.00
1.00
16.0×
Appendix
Table 14: Per-solver external-validity results at threshold 10−5 ( n=64 paired instances per game, T=216 , alternating updates except ExRM + ). Columns as in Table 13 ; per-solver “select.” picks that solver’s own C1 -argmin checkpoint, “certified” is the fraction whose selected C1 is below the threshold, and “ratio” is the median of C1 over the exact gap there; n/a marks a cell whose selected gaps are all below 10−12 . The portfolio row selects across solvers, and its oracle column is the pool’s oracle union.
Many two-player zero-sum games admit not a unique Nash equilibrium but a convex set of them: a polytope of profiles that all share the minimax value V* yet prescribe different behaviour. Standard solvers each converge to some equilibrium and are treated as interchangeable. We ask whether they instead select different members of the Nash set, systematically as a function of the algorithm rather than the seed. Using a tabular, exactly solvable testbed of six games with analytically known Nash sets -- including a two-dimensional Nash polytope and Kuhn poker -- we find that (i) selection is determined by the algorithm, not the seed, but families differ only on asymmetric Nash sets; (ii) regularized last-iterate methods (R-NaD, magnetic mirror descent) select the maximum-entropy member, the information projection of their uniform reference onto the Nash set -- exactly on the 2-D polytope and at 99.7% of maximum entropy in Kuhn -- while regret-averaging methods (CFR, CFR+, fictitious play) drift to a lower-entropy face; we confirm this on a randomized 180-game ensemble, where R-NaD attains the maximum-entropy member in 100% of converged games while CFR+ sits strictly below it in 94% (paired Wilcoxon p < 10^-27); (iii) the selected member has downstream consequences against sub-optimal opponents that scale with sequential/hidden-information structure but stay bounded -- in Kuhn the max-entropy member is a strictly better hedge, whereas on the matrix games the members differ without either dominating. We also report two negative results correcting common intuitions: removing CFR's positive-orthant (max(R,0)) projection does not eliminate boundary drift; and R-NaD's selection is anchor-following, not initialization-independent. We state the maximum-entropy / I-projection characterization as a strongly data-supported conjecture, checked throughout against analytic ground truth.
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
There has been significant recent progress in algorithms for approximation of Nash equilibrium in large two-player zero-sum imperfect-information games and exact computation of Nash equilibrium in multiplayer strategic-form games. While counterfactual regret minimization and fictitious play are scalable to large games and have convergence guarantees in two-player zero-sum games, they do not guarantee convergence to Nash equilibrium in multiplayer games. We present an approach for exact computation of Nash equilibrium in multiplayer imperfect-information games that solves a quadratically-constrained program based on a nonlinear complementarity problem formulation from the sequence-form game representation. This approach capitalizes on recent advances for solving nonconvex quadratic programs. Our algorithm is able to quickly solve three-player Kuhn poker after removal of dominated actions. Of the available algorithms in the Gambit software suite, only the logit quantal response approach is successfully able to solve the game; however, the approach takes longer than our algorithm and also involves a degree of approximation. Our formulation also leads to a new approach for computing Nash equilibrium in multiplayer strategic-form games which we demonstrate to outperform a previous quadratically-constrained program formulation.