PaperlayerView exact revision on arXiv

Source-linked AI summary

When Are We Near Nash? Certifying Solutions in General-Sum Games

Boning Li, Longbo Huang

arXiv:2610.29300v1cs.GTcs.AIcs.MA

TL;DR

Heuristic solvers for general-sum extensive-form games produce iterates whose NashGap is commonly evaluated after training, but exact evaluation is costly. The paper derives online certificates from solver-maintained accumulators and uses them to select an iterate from a portfolio. On biased Leduc, the protocol matches the trajectory-minimum union in-sample and reports results on held-out and fresh sets.

  • Problem

    Exact NashGap evaluation requires one best-response pass per player, while general-sum no-regret dynamics guarantee only coarse correlated equilibria in general.

    Source: §1 · p. 1

  • Method

    The paper derives an online certificate from regret and terminal-distribution accumulators, adding signed comparator terms when needed, then selects the lowest-certificate iterate across training-free solvers.

    Source: §1 · p. 2

  • Results

    At threshold 10^-5, sixteen training-free solvers solve 89% of 64 biased-Leduc instances in-sample, matching their trajectory-minimum union, and solve 92% held-out and 89% on a third set.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    Certificate-based selection makes the solver portfolio’s selection rule and budget explicit, and the selected iterate can be verified with one exact gap evaluation.

    Source: §1 · pp. 2–3

    The reported fractions are counts over the same 64 instances, and the head-to-head claims rest on few discordant pairs.

    Source: §7 · p. 17

Abstract

from arXiv · show

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.

1. Introduction

The paper develops online certificates for selecting low-NashGap iterates from quantities regret-minimization solvers already maintain. It applies the certificates to portfolio selection, avoiding exact gap queries during selection while preserving a final verification option.

1. Introduction

  • The natural Pinsker-based candidate sits three orders of magnitude above the true gap, while the benchmark’s 96% result used exact gap evaluation at roughly 19 checkpoints.The benchmark reports the trajectory minimum, making its selection rule and evaluation budget relevant to comparison.Source: §1 · p. 2
  • For two-player weighted averages, NashGap equals weighted external regret plus a signed value correction, yielding an online certificate after bounding regret by its running accumulator.Its per-checkpoint cost is linear in the number of terminal histories.Source: §1 · p. 2
  • Alternating updates create a mismatch between evaluated regrets and recorded averages; one signed comparator term captures it, keeping the certificate sound for any update order and player count.In games with three or more players, that term measures coalition imbalance not bounded by correlation level.Source: §1 · p. 2
  • The certificate selects the lowest-scoring checkpoint across a solver portfolio; C0 uses accumulators alone, while C1 adds signed backward passes for nonzero comparator weights.The selected iterate can then be verified with one exact gap evaluation.Source: §1 · pp. 2–3, Figure 1 · p. 3
  • 89% in-sample, 92% held-out, and 89% on a third biased-Leduc set: sixteen training-free solvers match the trajectory-minimum union at threshold 10^-5 in-sample.The third set contains 64 instances; the held-out set was pre-registered.Source: §1 · pp. 2–3

2. Related Work

Related work spans meta-learned regret minimizers, training-free regret variants, and certificates for evaluating game-theoretic solutions. The paper distinguishes its sound certificate-based selection among solver iterates from these approaches and from existing zero-sum guarantees.

2. Related Work

  • NPCFR+ meta-learns a predictive bias for general-sum Nash approximation, while Learning-not-to-regret meta-learns regret-minimizer internals for faster convergence (Sychrovský et al., 2024; Sychrovský et al., 2026).External payments provide another way to steer no-regret learners toward equilibria (Zhang et al., 2024).Source: §2 · pp. 3–4
  • The prior Pinsker-type certificate bounds NashGap using regret and extensive-form marginalizability, whereas the paper’s two-player theorem removes the distribution inequality (Sychrovský et al., 2026).Exact gap evaluation otherwise requires one best-response pass per player.Source: §2 · p. 4
  • In zero-sum games, total regret bounds the average’s gap because the signed value corrections cancel; in general-sum play, the residual remains (MacQueen, 2023).The cited alternatives do not provide an online, best-response-free certificate for selecting iterates during general-sum extensive-form training.Source: §2 · p. 4
  • CFR and its predictive, discounted, scheduled, and stabilized variants accelerate regret minimization, but their guarantees generally yield only coarse correlated equilibria in general-sum games (Farina et al., 2021; Brown & Sandholm, 2019; Anagnostides et al., 2022).Monte Carlo variants trade exact terminal distributions for sampling, while abstraction and pruning are complementary scaling approaches.Source: §2 · p. 4
  • Portfolio selection here scores no-regret solver iterates with a sound certificate, unlike strategy-portfolio optimization or solver-dependent selection among equal-value equilibria (Drabent et al., 2025; Leal, 2026).The portfolio-level selection among training-free solver iterates is described as new.Source: §2 · p. 4

3. Preliminaries

The preliminaries formulate finite perfect-recall extensive-form games using realization plans and terminal distributions. They define the weighted iterates, regrets, and online accumulators used to state the certificate.

3. Preliminaries

  • In sequence form, each player’s strategy is a realization plan in a convex polytope, and utilities are multilinear across players’ plans.A profile induces a terminal distribution.Source: §3 · pp. 4–5
  • NashGap is the largest unilateral improvement; exact evaluation requires one best-response computation per player, while regret-minimization dynamics generally guarantee only coarse correlated equilibria.Computing an inverse-polynomial-precision general-sum equilibrium is PPAD-complete.Source: §3 · p. 5
  • The solver’s weighted average uses nonnegative iteration weights, with uniform, linear, and quadratic choices corresponding to exponents 0, 1, and 2.The weighted empirical terminal distribution mixes the distributions induced by each jointly played iteration.Source: §3 · p. 5
  • Counterfactual values exclude a player’s own reach before an infoset and include that player’s continuation after the chosen action.Counterfactual regrets are defined action-by-action at infosets.Source: §3 · p. 5
  • The loop maintains realization-plan and terminal-distribution sums plus cumulative counterfactual regrets in O(|Z|) per iteration; the regret accumulator is bounded online without a best response.Averaging can make the empirical joint terminal distribution differ from the independent-play distribution.Source: §3 · p. 5
  • The solver pool includes RM+, PRM+, and DPRM+, with simultaneous or alternating updates and several weight exponents, alongside nine later training-free variants.The + step floors accumulated regret at zero before matching.Source: §3 · pp. 5–6

4. The Oracle Gap in Trajectory-Minimum Evaluation

The benchmark evaluates a run by its minimum exact NashGap across checkpoints, so the reported score depends on a costly selection rule. The section motivates an online certificate as an algorithmic, sound, and comparable alternative.

4. The Oracle Gap in Trajectory-Minimum Evaluation

  • The benchmark’s trajectory minimum requires exact gap evaluation at every checkpoint, and a game is solved when that minimum is at most 10^-5.The original study used roughly 19 evaluations through 218 iterations; the paper’s experiments use a 128-point grid.Source: §4 · p. 6
  • Plus-family NashGap trajectories need not be monotone, so the trajectory minimum can be far below the final average and requires post-hoc exact selection.This compares trajectory optima that incur multiple exact gap queries with the final average actually returned by a run.Source: §4 · p. 6
  • A selection certificate should be sound, computed without best responses against the reported profile, tight enough to preserve solved-instance decisions, and comparable across runs.The exact reformulation tracks the gap within a median 1.27× over 127,849 checkpoints with gap above 10^-12; the theorem establishes soundness.Source: §4 · p. 6

5. Online Certificates from an Exact Decomposition

The section derives online NashGap certificates from an exact two-player decomposition, then extends them to coalition imbalance and arbitrary update orders. The certificates use solver-maintained accumulators, with a signed backward pass for exact comparator corrections.

The Pinsker certificate and its bottleneck

  • The distribution-exchange certificate is sound but overestimates benchmark NashGap by a median 1.3×10^3, with the exchange relaxation dominating its slack.Its regret term is approximately 1× tight, while the distribution-exchange relaxation dominates when the terminal-distribution divergence is small.Source: §5 · p. 7

An exact decomposition for two players

  • In two-player games, the weighted-average NashGap equals weighted external regret plus a signed value correction, yielding a certificate when regret is bounded by its online accumulator.The correction is the difference between weighted average realized value and the value of the average strategy profile; it may be negative.Source: §5 · p. 7

The coalition term for three or more players

  • For three or more players, averaging can destroy independence within the opposing coalition, so correlation level ε alone cannot bound coalition imbalance.The coalition term is measured directly; for two players it vanishes, recovering the exact-decomposition bound.Source: §5 · p. 8

Exact coalition comparator

  • The exact coalition comparator removes the remaining M relaxation by maximizing a signed imbalance weight in one backward pass per player.That pass also attributes certificate slack; on three-player games, the comparator relaxation accounts for 96–99% of slack.Source: §5 · p. 8

Any update order

  • For alternating updates, a signed comparator term captures the mismatch between the partially updated profile used for regret evaluation and the profile recorded by averages.This avoids a second regret pass per iteration; under two-player alternation, the first mover’s comparator weight vanishes and the second mover’s term measures drift between consecutive first-player iterates.Source: §5 · pp. 8–9

Certificate and verification layers

  • The certificate has an accumulator-only form and an exact-comparator refinement; one-shot verification then computes best responses only for the selected snapshot.The exact refinement uses one signed backward pass per player with nonzero comparator weight, while the verification protocol uses n best-response passes on the frozen profile.Source: §5 · p. 9

6. Certificate-Guided Portfolio Selection

The portfolio procedure keeps raw accumulators alongside each solver’s optimizer state. At checkpoints, these accumulators specify both the stored profile and its certificate score.

Accumulator state

  • Each solver maintains weighted realization plans, evaluated-profile joint and opponent-coalition reach, and unclipped signed regret alongside its clipped optimizer state.These are unnormalized counterparts of the profile quantities used in the certificate.Source: §6 · p. 10

Checkpoint scoring

  • The accumulators are scaled by the running weight sum W_T to give the normalized certificate quantities.They correspond to the average realization plans, evaluated-profile terminal distribution, and evaluated-profile opponent-coalition reach.Source: §6 · p. 10
  • At a checkpoint, the accumulated quantities define both the stored profile and its score.The profile and score use the same accumulated state.Source: §6 · p. 10

7. Experiments

The experiments test certificate-based selection on biased two-player Leduc and a deterministic three-player game, comparing its selected and certified solves with exact-gap selection and solver baselines. The sixteen-solver pool matches the trajectory-minimum union on the in-sample set, and the certificates remain sound and close to the true gap across the tested sets and game settings.

Biased Leduc

  • 89% of 64 biased-Leduc instances are solved at 10^-5 by certificate selection, matching the trajectory-minimum union of the sixteen-solver pool.The pool contains seven original solvers and nine added training-free variants; its exact-gap selection counterpart agrees on the solved-or-not decision for all 64 instances.Source: §7 · pp. 10, 12

Selection tightness

  • Across 36 in-sample instances with selected gaps above 10^-12, the selected gap exceeds the exact trajectory minimum by a median factor of 1.01.The ratio is 1.36 at the 90th percentile; on the remaining 28 instances, both gaps are at or below 10^-12.Source: §7 · p. 12

Certificates

  • 57/64 in-sample solves are certified by both C1 and C0, while C1 certifies all 59 held-out and 57 fresh solves, versus 58/64 held-out for C0.C1 certifies every solve across the three sets; C0 reads the regret and terminal accumulators without a backward pass.Source: §7 · pp. 12, 16

Three-player Leduc

  • On the single deterministic three-player game, PDCFR+ reaches NashGap 1.17 × 10^-6 and C1 certifies HS-PCFR+ at 1.31× its true gap at T.C1 stays within 1.31–8.2× of the true gap across all twelve solvers and all certificates exceed the exact gap at each of 64 checkpoints per solver.Source: §7 · p. 12

Held-out and fresh instances

  • The sixteen-solver pool solves 59/64 held-out instances and 57/64 fresh instances at 10^-5, matching exact-gap selection on the same grids.The held-out and fresh sets use 64 instances each; the fresh set was drawn from the same distribution under a third pre-registration.Source: §7 · p. 16

Failure analysis

  • The seven in-sample failures cluster at low tie-refund fractions, but C1 remains within 1.22× of the true gap at worst on those failures.Their median tie-refund fraction is 0.17 versus 0.28 over all instances, and no solver's trajectory minimum clears the threshold on them.Source: §7 · pp. 16–17

Certificate comparison

  • C1 is the tightest of four certificates at 98.5% of Figure 2 quantile levels and is never looser than C0.At the selected iterate, its median tightness is 1.4× versus 1.9× for the aligned start-of-round certificate over 36 instances with resolvable gaps.Source: Figure 2 · p. 12, §7 · p. 17
  • On the seven-solver pool, the aligned start-of-round certificate selects 51/64 and certifies 44/64, versus 54/64 and 48/64 for C1.The aligned variant requires a second regret pass per player per iteration; the full portfolio's aligned grid costs 37.2 core-h.Source: §7 · pp. 13, 15, 17

8. Conclusion

The conclusion presents an accumulator-based certificate for NashGap and uses it to make trajectory selection explicit. The certificate is sound across update orders and player counts, while its two-player decomposition is exact.

8. Conclusion

  • On biased Leduc, certificate selection solves 89% of instances in-sample, 92% on pre-registered held-out instances, and 89% on a third set.The in-sample result matches the trajectory-minimum union; the conclusion reports exact-comparator certification for every solve across the three sets.Source: §8 · p. 18
  • The NashGap of a two-player weighted average admits an exact decomposition into weighted external regret and a signed value correction.Bounding regret with the running counterfactual-regret accumulator yields an online certificate.Source: §8 · p. 18
  • For general player counts and update orders, alternation's mismatch enters the sound certificate as one signed comparator term.The conclusion says the term is maximized in one backward pass per player with nonzero comparator weight.Source: §8 · p. 18
  • The certificate makes checkpoint selection a stated rule: score every portfolio iterate and output the one with the smallest certificate.The selected profile is then verified once by exact evaluation.Source: §8 · p. 18

A.1. Proof of Theorem 4

  • In the two-player proof, bilinearity makes the comparator term exact, while the value term is recovered from measurable terminal-distribution quantities.The conclusion identifies the resulting identity as the basis of the exact NashGap decomposition.Source: §8 · p. 18

A.2. Proof of Lemma 1

  • The logged raw regret accumulator preserves the weighted external regret exactly; the deployable bound relaxes its single comparator maximization into local positive maxima.The raw table stores the regrets evaluated by the update, without an extra pass.Source: §A.2 · pp. 23–24

A.5. Proof of Proposition 8

  • For multiple players, the signed comparator functional is maximized by a sequence-form backward pass for each player with nonzero comparator weight.When there are two players, that term is zero.Source: §A.5 · p. 24

A.7. The logged state determines the exact gap

The logged regret and terminal state can recover the exact gap with a linear maximization, while cheaper certificates trade exactness for cost. The appendix also demonstrates that soundness does not guarantee tightness on every trajectory.

A.7. The logged state determines the exact gap

  • The exact gap can be recovered from the logged state by undoing both certificate relaxations with one linear maximization per player.That pass can return the exact gap; the cheaper C0 certificate needs no pass, while C1 retains separate terms to attribute slack.Source: §A.7 · p. 25

A.8. A zero-pass comparator term no larger than ∥w∥1

  • A one-dimensional minimization over terminal-payoff breakpoints bounds the comparator term without a tree pass.The minimization over c uses the breakpoints {u_i(z)}.Source: §A.8 · p. 26

A.9. Tightness is not universal

  • At δ=0, the example has NashGap 0 but C0 and C1 both equal 1, so the certificate has no universal multiplicative tightness guarantee.The example's slack comes from a positive part that discards negative upstream regret needed to cancel an off-path term.Source: §A.9 · p. 26

A.10. Additional details for Proposition 6

  • With three players, zero regrets and zero terminal-distribution divergence still coexist with NashGap 1/2; the coalition term gives an exact bound of 1/2.Thus, for three or more players, the coalition term is not determined by the regrets and divergence alone.Source: §A.10 · p. 27

B.1. Portfolio Composition and Ablation

  • The sixteen-solver portfolio solves 0.89 of biased-Leduc instances, versus 0.84 for the seven original solvers and 0.80 for the best single solver.C1 selection matches the oracle union for every tested pool.Source: §B.1 · p. 27
  • Weighted RM+, uniform PRM+, DCFR, DCFR+, and HS-DCFR each solve 0.00 at the target in the reported comparison.Among those tested configurations, only predictive updates combined with weighting reach it.Source: §B.1 · p. 27

B.2. Per-Solver Biased-Leduc Results

The per-solver biased-Leduc results compare certificate selection with oracle trajectory minima and test how selection policies affect the portfolio's solved fraction. The regret-only surrogate and the full certificate select different checkpoints frequently, but that difference rarely changes solved outcomes.

B.2. Per-Solver Biased-Leduc Results

  • At threshold 10−5, C1 selection reaches each solver’s own oracle fraction for fourteen evaluated solvers; HS-PCFR+ and ExRM+ each miss one instance.The oracle columns report trajectory-minimum results on 64 paired biased-Leduc instances.Source: §B.2 · p. 28
  • On the sixteen-solver portfolio, dropping value and comparator terms reduces the solved fraction from 0.89 to 0.77; keeping the value correction recovers all lost solves.The comparator term does not change solved-or-not outcomes on this benchmark.Source: §B.2 · p. 28
  • C1 and the regret-only surrogate choose the same checkpoint in 39% of runs, yet the extra terms rarely change whether the selected iterate is solved.The regret term carries most of the trajectory minimum, but does not by itself determine checkpoint selection.Source: §B.2 · p. 28

C. External-Validity Games

The external-validity tests evaluate selection on Sheriff and Goofspiel as mechanism-transfer tests, not scalability experiments. Results differ by game: selection certifies all Sheriff instances, while Goofspiel shows a gap between selection and the oracle union.

C. External-Validity Games

  • On Sheriff, C1 selection solves every instance at every threshold and is exact to floating-point precision on all 64 instances.The sixteen-solver pool's selected iterates come from HS-PCFR+ on 33 instances and PDCFR+ on 31.Source: C. External-Validity Games · p. 29
  • Both external-validity games use 64 paired instances, all sixteen solvers, T=216, and 64 checkpoints; the authors characterize them as mechanism-transfer tests.They are not scalability experiments.Source: C. External-Validity Games · p. 29
  • On Goofspiel, the sixteen-solver pool selects 0.62 of instances, compared with 0.64 for exact-gap selection and 0.53 for the best single solver.The selection is one instance below the oracle union on the same grid.Source: C. External-Validity Games · pp. 29–30
  • On Goofspiel, DPRM+ certificates are 6–20× loose and certify nothing, although DPRM+ and PRM+ solve different instances.The seven-solver certified fraction of 0.45 is carried by PRM+ solvers.Source: C. External-Validity Games · p. 30

D. OpenSpiel Cross-Validation

Independent OpenSpiel checks agree with the implementation’s biased-Leduc rules and NashGap evaluator on the tested cases, while leaving the reference solver and its averaging conventions untested.

D. OpenSpiel Cross-Validation

  • At β=1, the reimplementation and OpenSpiel’s Leduc game produce identical CFR+ NashGap values at all ten logged checkpoints.Both games have 936 infosets; the checks validate selected implementation aspects, not a reproduction of NPCFR or its reported PCFR+ baseline.Source: D. OpenSpiel Cross-Validation · p. 30
  • OpenSpiel’s maximum per-player improvement matches the implementation’s NashGap on all 12 tested pairs, with relative error ≤3.9 × 10−7.The exported average strategies were injected into OpenSpiel tabular policies with matching information-state key sets.Source: D. OpenSpiel Cross-Validation · pp. 30, 32
  • At aligned checkpoints, OpenSpiel CFR+ trajectory ratios range from 0.65 to 1.24, while the trajectories agree to relative difference ∼10−11 at t=64.By t=4096, the difference grows monotonically to 24–35%; the diagnostic does not identify the cause or test solver equivalence, update bookkeeping, or long-horizon behavior.Source: D. OpenSpiel Cross-Validation · p. 32
  • The checks validate the tested rules and evaluator, but leave the reference solver, its averaging conventions, and the source of the cross-paper discrepancy untested.The scripts, exported policies, and logs behind the cross-validation are not included in the released code.Source: D. OpenSpiel Cross-Validation · p. 32

E. Implementation Details

The implementation keeps raw regret and terminal-distribution accumulators alongside solver state, then uses those quantities for certificates across update rules and portfolio runs.

E. Implementation Details

  • Each run maintains raw signed counterfactual-regret accumulators, weighted average realization plans, terminal distributions, and, for n≥3, per-player coalition products.At checkpoints, the aligned and coalition certificates are computed from these accumulated quantities with a few dot products.Source: E. Implementation Details · p. 32
  • The comparator identity reduces both sides to linear functionals, and the biased-Leduc implementation check shows that applying chance reach twice changes the residual from 1.9 × 10−16 to 1.2 × 10−1.The checked terminals have different chance probabilities for folds and showdowns.Source: E. Implementation Details · p. 32
  • DPRM+ inserts the current weighted iterate and terminal distribution before forming its look-ahead proxy, which doubles the current iterate’s effective weight as a finite-difference direction.The proxy’s totals already include the current iterate.Source: E. Implementation Details · p. 32
  • The nine added solvers use raw instantaneous regret at the played profile for certificate accumulators, even when their optimizer state is discounted or projected.Configurations were selected by a preregistered rule; the two held-out stages reuse the same 64 instances, while Stage 3 uses untouched seeds 128–191.Source: E. Implementation Details · p. 33
  • The 16-solver pool combines RM+, PRM+, DPRM+, and nine added training-free solvers; the reported selection rows give exact gaps, while certified rows count selected certificates below threshold.The reference three-player benchmark is the fixed game of its Table 6.Source: E. Implementation Details · p. 33
  • Two-player runs use 218 iterations and 128 checkpoints; the deterministic three-player run uses 2^16 iterations and 64 checkpoints spaced every 1024 iterations.Every run records C0 and C1; aligned certificates are also logged for the specified two-player grid and preselected three-player solver.Source: E. Implementation Details · p. 33

F. Future Work

The discussion identifies limits in benchmark comparability, certificate tightness, and game coverage, and distinguishes certificate-based selection from using certificates to control updates.

F. Future Work

  • The reference solver remains an open reproduction target because its code is unavailable and its averaging weights are underspecified; cross-validation checks only the authors’ own rules and evaluator.Obtaining the reference configuration would enable a controlled rerun.Source: F. Future Work · p. 34
  • The reported NPCFR+ 0.96 versus portfolio 0.89 comparison uses independently drawn samples, and unpublished NPCFR instance draws prevent a paired comparison.A shared instance set would test whether the aggregate margin concentrates in low-β games.Source: F. Future Work · p. 34
  • An aligned certificate was looser than C1 in the portfolio ablation, while the entropy-descent side experiment audited all 13 anchor updates as sound.The final anchor NashConv was 0.0139 against its stored bound of 0.0205.Source: F. Future Work · p. 34
  • Certificate-gated control froze after four advances in a pilot, while forcing advances violated the stored threshold invariant at every forced step.The paper therefore keeps certificates out of the update loop and uses them for selection.Source: F. Future Work · p. 34
  • On three-player Leduc, C1 is 1.4–8.2× loose across the six original solvers; closing the C0–C1 gap requires a zero-best-response surrogate for the comparator optimum.Evaluating that comparator optimum costs a backward pass per player per checkpoint.Source: F. Future Work · p. 34
  • The evaluation remains centered on small tabular Leduc variants; larger and more varied games and non-chip payoffs are identified as further tests.Agents without a regret accumulator fall outside the certificate’s scope.Source: F. Future Work · p. 35
  • The certificate currently requires exact weighted terminal distributions, making it incompatible with Monte Carlo CFR-style sampling; sampled or amortized accumulators are proposed next steps.DPRM+’s O(|Z|) gradient was also too costly for the three-player portfolio.Source: F. Future Work · p. 35
Loading 2610.29300v1…