Skip to content
Preprint

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

Oct 2026 · 0 citations · 57 references
Computer Science

TL;DR

This work asks what a solver can know about its own iterates from the regret accumulators and the terminal-distribution accumulators its updates already maintain, and produces a portfolio of training-free regret-matching solvers.

Abstract

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.

View source

Similar papers

#machine learning Preprint Nov 2026

Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal Approximation

The upper bound is based on a temporal approximation framework for the analysis of Optimistic Hedge, and approximate the losses over time-localized windows by well-behaved functions, whose total variation is a small fraction of their cumulative variance.

Y. Dagan, Nadav Eisen, Liad Erez et al. · 0 citations
Preprint Nov 2026

On the Convergence of Alternating Regret Matching Algorithms

Alternating updates, that is, where each player is updated in turn, tend to typically perform better in regret matching algorithms than simultaneous updates. Alternation within the regret matching family has long been a central ingredient of practical solvers for zero-sum games. Yet our theoretical understanding is lag...

Anh Duc Nguyen, I. Anagnostides, B. Zhang et al. · 0 citations
Preprint Oct 2026

Why Alternation Speeds Up Counterfactual Regret Minimization?

Solving imperfect-information games at scale rests on counterfactual regret minimization with the regret matching$^{+}$ (RM$^{+}$) update, and a seemingly minor implementation choice accounts for much of its practical speed: alternating the two players'updates, so that the second player responds to the strategy the fir...

Bo-Ning Li, Long-Bo Huang · 2 citations

Minimax Last-Iterate Convergence in Matrix Games with Observed Actions

We study last-iterate convergence in unknown two-player zero-sum matrix games with bandit payoff feedback and observed opponent actions. For games with $d$ actions per player, we develop an algorithm achieving a duality gap of $\widetilde{\mathcal{O}}(\sqrt{d/t})$ with high probability, simultaneously at every round $t...

Yu-Heng Zhang · 1 citation

Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback

Optimistic Payoff Balancing (OPB), which achieves instance-dependent instance-dependent $\mathcal{O}(\log^2 T)$ Nash regret against arbitrary adaptive opponents, including games with nonunique equilibria, is developed.

Yu-Heng Zhang · 0 citations
Preprint Oct 2026

The Complexity of Strategizing Against No-Regret Learners: Pure When It Is Easy, Hard Even When Mixed

We study the computational complexity of clairvoyant strategy optimization against a known online learner in finite-horizon repeated games. In general-sum games with bounded payoffs, unless $\mathsf{P}=\mathsf{NP}$, no polynomial-time optimizer can achieve a reward within $cT$ of the reward of the optimal pure-action s...

Yi-Heng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.