Scale-Invariant Stabilized Regret Matching on Game Trees

Counterfactual regret minimization (CFR) is the standard way to solve large imperfect-information games such as poker. Each player breaks its huge strategy space into many small, independent choices, one at every decision point. At each point it runs a simple learner called regret matching+ (RM+), which plays actions in proportion to how much it regrets not having played them. The method is uncoupled: every player uses only its own payoffs, and no one coordinates the players. Recent theory has found a crack in this workhorse. In plain matrix games, RM+ is unstable when its regrets are near zero. It can cycle forever instead of settling, and it converges slowly. Two fixes, "chopping off" the origin and restarting, repair this and give much faster multi-player guarantees. When the fixes were ported to game trees, though, the step sizes the theory required became "prohibitively small," so practical CFR still runs heuristic RM+ with no stability guarantee.

We think the obstruction comes from global bookkeeping, not from the tree itself. At a deep decision point, the payoffs a local learner sees are scaled by the probability of reaching that point, and they can be tiny or huge relative to the root. A single global stabilization threshold therefore fits almost no decision point well. Our proposal is to stabilize each local RM+ with a threshold measured in that decision point's own payoff units. The resulting method is invariant to how payoffs are scaled inside any subtree. We then show that its stability composes up the tree through the laminar regret decomposition, meaning the exact splitting of a player's total regret into a reach-weighted sum of local regrets. If this works, practitioners get a CFR variant that is as parameter-light as predictive CFR+ and comes with the fast multi-player guarantees and last-iterate convergence currently proven only for matrix games.

Core Claim

The central object is Laminar Smooth Predictive RM+. At each information set $h$ (a decision point the player cannot distinguish from others), the learner keeps a nonnegative regret vector $r_h \in \mathbb{R}_+^{A_h}$ over its $A_h$ actions. After each predictive update, it projects that vector onto a set that excludes a neighborhood of the origin:

$$ r_h \leftarrow \Pi\big(\{ r \ge 0 : \mathbf{1}^\top r \ge \tau_h^t \}\big), \qquad \tau_h^t = c \cdot S_h^t , $$

Here $S_h^t$ is a running estimate of the magnitude of counterfactual values at $h$, meaning payoffs conditioned on reaching $h$, up to iteration $t$. The constant $c$ is shared across the whole tree. If every loss in the subtree below $h$ is multiplied by a constant, then $r_h$ and $\tau_h$ scale together, so the played strategy does not change. This is the scale invariance that Local and Adaptive Mirror Descents in Extensive-Form Games obtained for local mirror descent in two-player zero-sum games.

Smooth RM+ is Lipschitz in its regret vector with constant proportional to $1/\tau_h$. The change in strategy at $h$ is therefore controlled by the change in local losses divided by the local scale, and that ratio is dimensionless.

We conjecture, and will try to prove, three results. First, these local stability bounds compose through the tree into a bound of the RVU type ("regret bounded by variation in utilities") for each player's sequence-form strategy. The constants would depend on tree depth $D$ and $\ln \max_h A_h$, not on the spread of payoff magnitudes across the tree. Second, this yields constant social regret and $O(T^{1/4})$ individual regret in multi-player general-sum extensive-form games, with the step size set independently of game size. Third, an extragradient or smoothed variant converges in the last iterate to Nash equilibrium in two-player zero-sum extensive-form games.

Research Program

The work has three roles, one per research direction.

Laminar decomposition supplies the mechanism. We reuse the local-regret decomposition of Kroer et al. and the original CFR factorization of Zinkevich et al.. We measure strategy variation in the primal-dual treeplex norms of Fan et al., which match the recursive geometry of the sequence-form polytope (the "treeplex," the convex set of a player's reach-probability-weighted strategies).

The technical crux is the parent-child coupling. The loss a parent sees includes its children's expected future values, so a parent's variation term inherits its children's instability. Kroer et al. showed that stability requirements must scale with depth for decomposed updates to accelerate. Our question is whether scale-relative thresholds let that depth coordination happen through $c$ alone, instead of through a global step size that shrinks with $|\Sigma|$.

Uncoupled dynamics supply the target guarantees. We aim to extend the matrix-game results of Regret Matching+: (In)Stability and Fast Convergence in Games, namely $O(T^{1/4})$ individual and $O(1)$ social regret, to trees. We also aim to extend the last-iterate results of Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games, for extragradient RM+ and smoothed predictive RM+, beyond normal form. Both papers state their guarantees for matrix games. The first flags the extensive-form step-size problem that we target.

Game-theoretic optimization supplies the lens and a second use case. Liu et al. show that RM+ is online mirror descent with an adaptive regularizer set by cumulative regret. That view lets us read the origin-chopping as a local change of regularizer, which is what makes the composition analyzable. Convergence of Regret Matching in Potential Games and Constrained Optimization shows that RM+ reaches $\epsilon$-KKT points (approximate constrained stationary points) in $O(1/\epsilon^4)$ iterations, while vanilla RM can need $m^{\Omega(m)}$. We will test whether the laminar stabilized method inherits polynomial KKT convergence as a constrained optimizer over treeplexes, for example in common-payoff team games. There, vanilla CFR's inner RM may inherit the exponential failure.

Deliverables are a proof, or a precise counterexample, of the composed bound, and an open implementation in the OpenSpiel game suite. No Lacuna code record was found for OpenSpiel.

Baselines

The naive reference point is vanilla CFR+ with iterate averaging, meaning heuristic RM+ at every information set, as in deployed poker solvers. It shows whether stabilization changes anything a practitioner cares about. Near-Optimal Φ-Regret Learning in Extensive-Form Games compared against it on Kuhn, Goofspiel, and Sheriff and reported only qualitative curves. No reported numerical result was found on Lacuna for CFR+ regret or exploitability values on these games.

The strongest practical competitor is predictive CFR+ (PCFR+), together with Clairvoyant CFR, which Anagnostides et al. found empirically superior to predictive CFR on their extensive-form benchmarks. No reported numerical result was found on Lacuna for PCFR+ or Clairvoyant CFR on 4-player Kuhn, 3-player Leduc, 4-player Liar's Dice, or Sheriff. The only concrete figures in the file are for matrix games. In the hard $3\times 3$ game, vanilla RM+ converges at $O(1/\sqrt{T})$ while stabilized predictive RM+ achieves an asymptotic $O(1/T^2)$ rate (Anagnostides et al.). Restarted variants reach an error of $10^{-10}$ within a few thousand iterations (Cai et al.).

The strongest theoretically grounded competitor is optimistic online mirror descent with dilated entropy. This regularizer is built by recursively weighting local entropies down the tree and is the near-optimal choice analyzed by Fan et al.. Its stabilized and optimistic variants give last-iterate guarantees in two-player zero-sum games (Kroer et al., Liu et al.).

The ablation that isolates our key ingredient is global Smooth PRM+ on the tree. It uses one global threshold with the conservative step size that Anagnostides et al. derived, and also the best single threshold found by tuning. The comparison between one global scale and per-information-set scale is the core test of the proposal.

Fairness protocol. Every method runs on identical game instances with full-information counterfactual feedback and the same number of tree traversals. Each gets the same hyperparameter budget: a sweep of 12 values of its single scalar ($c$ for ours, the step size for mirror descent and global Smooth PRM+). Methods with no tunable scalar, such as CFR+ and PCFR+, get the same number of random seeds.

What counts as winning. Beating the baselines means lower social regret and lower maximum individual regret than PCFR+ at matched traversals on at least three of the four multi-player games. It also means monotone last-iterate exploitability decrease in two-player zero-sum games where PCFR+ plateaus or oscillates. Beating the ablation means the per-information-set version matches or exceeds the tuned global version without per-game tuning.

Why not just…?

Why not just keep running PCFR+, which already works well in practice? This is the real threat. If PCFR+ already shows flat social regret and non-cycling last iterates on these benchmarks, our contribution reduces to explaining existing behavior. The evidence that the gap is real comes from matrix games. Cai et al. show that predictive RM+ and alternating RM+ can cycle indefinitely even on a $3\times 3$ game, and every CFR variant runs these learners at each node. We will embed such cycling matrix games at the leaves of small trees and measure PCFR+'s last iterate directly. We will also report honestly if PCFR+ matches us on the poker games.

Why not just use optimistic mirror descent with dilated entropy, which already has clean theory? Dilated mirror descent needs a step size that interacts with payoff range and tree weights. Its theory is largely for two-player zero-sum games or for coarse correlated equilibrium at $O(n\log|\mathcal{V}|\log T/T)$ (Fan et al.). Regret-matching methods are preferred in practice because they need no such tuning. Our tuning-budget-matched comparison settles which is better at equal effort, and a scale-perturbation test settles which is more robust.

Why not just apply matrix-game Smooth PRM+ to the reduced normal form? The number of normal-form strategies grows exponentially with depth (Bai et al.). Normal-form regularizers pay diameter-to-strong-convexity ratios that are exponential in depth (Fan et al.). We will run this baseline only on the smallest Kuhn instances, to confirm our method matches its trajectory where it is feasible.

Why not just tune one global threshold per game? If a single tuned global threshold does as well, local scaling is unnecessary. The global-versus-local ablation tests this directly, and the scale-perturbation experiment below is designed to make any global threshold fail.

Proposed Experiments and Decisive Checks

We use the benchmark instances from Anagnostides et al.: 4-player Kuhn poker (23,402 nodes), 3-player Leduc poker (15,659 nodes), 4-player Liar's Dice (8,178 nodes), and 2-player Sheriff of Nottingham (9,648 nodes). Two-player Kuhn, two-player Leduc, and Goofspiel serve as the zero-sum last-iterate tests.

The metrics are social regret (the sum over players, which bounds the gap to coarse correlated equilibrium), maximum individual regret, and, in zero-sum games, exploitability of the last iterate and of the average. All are plotted against tree traversals and wall-clock time.

Decisive check 1: scale perturbation. We multiply payoffs in randomly chosen subtrees by factors from $10^{-3}$ to $10^{3}$, and we add chance nodes that make some information sets extremely unlikely to be reached. Our method's trajectory should be unchanged by construction, apart from the adaptive scale estimate. Global Smooth PRM+ and dilated mirror descent should degrade. If ours degrades too, the composition argument is wrong.

Decisive check 2: depth scaling. On synthetic trees of increasing depth, the proof predicts that the largest workable $c$ stays constant and that constant-social-regret behavior persists. A threshold that must shrink with depth would reproduce the "prohibitively small" failure.

Decisive check 3: constrained optimization. On common-payoff extensive-form team games built by nesting the potential-game hard instances of Anagnostides et al., we measure iterations to an $\epsilon$-KKT point for CFR, CFR+, and our method. The prediction is polynomial growth in $1/\epsilon$ for ours and blow-up for the vanilla-RM inner loop.

The proposal fails cleanly if the composed bound provably requires a depth-dependent or size-dependent threshold, or if PCFR+ matches our method on every check. Either outcome would itself answer the open question that Anagnostides et al. left on trees.