Why Alternation Speeds Up Counterfactual Regret Minimization?

1. Introduction

• Alternation is a practical speed choice for CFR with RM+, routinely yielding a one-to-two-order-of-magnitude speedup, while its mechanism remains largely unexplained.Prior theory separates alternating and simultaneous duality gaps by a nonnegative improvement term, but known predictive-regret bounds do not separate them.Source: §1 · p. 1
• The canonical additive prediction form fails the direct test of the intuition that alternation acts like optimism with a perfect one-step predictor (Rakhlin & Sridharan, 2013a,b; Farina et al., 2019a, 2021).The paper isolates this previously untested interpretation of alternation.Source: §1 · pp. 1–2
• Across the 2 × 2 witness family, alternating RM+ and one-sided predictive RM+ have duality gaps separated by factors of 5–154 (median 28.7) and median final ℓ1 trajectory distance 0.58.Both receive player 2’s instantaneous regret against player 1’s newly computed strategy; the difference is whether that signal enters persistent regret or a transient prediction term.Source: §1 · p. 2
• Under an interior-band assumption on the alternating strategy, predictive exact-vertex play either recurs, yielding an explicit constant trajectory separation infinitely often, or terminates.The interior-band condition was verified on the tested grid in every arithmetic precision.Source: §1 · p. 2
• Transient injection can meet a persistent state washed to zero, producing an unbounded-gain switch between exact vertices; persistent injection is averaged into a rotation with a vanishing angular step.The mechanism is illustrated in Fig. 1.Source: §1 · p. 2
• The paper tests four explanation families on 47 matrix games and extensive-form witnesses, and reports that their canonical implementations are not equivalent to alternation.The families cover additive one-sided prediction, play-level proximal damping, staleness interpolation, and standard two-sided optimism.Source: §1 · p. 2

2. Related Work

• For gradient-type methods, prior work proves benefits of alternation, including improved average regret, finite-regret or cycling analyses, and O(1/T) average-iterate convergence in constrained bilinear games.These results concern mirror-descent or gradient-descent-ascent updates; analogous benefits for regret-matching dynamics remained open.Source: §2 · p. 3
• Alternation-aware Hedge bounds address one learner’s worst-case regret, whereas this paper studies RM+ self-play trajectories; fictitious play separates optimism and alternation in the opposite direction.For the witness game class, optimism alone can attain constant regret while alternation alone can incur Ω(T) regret for almost all initializations (Lazarsfeld et al., 2026).Source: §2 · p. 3
• Predictive regret matching and optimistic methods develop prediction-based guarantees, including constant regret in simultaneous N-player general-sum self-play, but their signatures do not match measured alternation behavior.The cited simultaneous result uses an exponential moving average optimism cascade.Source: §2 · p. 3
• Neither RM+ nor predictive RM+ is generally last-iterate stable, although smooth, constrained, perturbed, or forgetting variants recover guarantees in specific settings.The literature distinguishes best-, last-, and random-iterate guarantees and studies variants for sequential games and self-play.Source: §2 · p. 3
• On the witness family, predictive dynamics exhibit finite-horizon bang–bang vertex visits with persistent state washed to zero, while alternation rotates with a shrinking step.This is the paper’s stated contrast with the surrounding work on last-iterate behavior.Source: §2 · p. 3
• CFR+ alternation entered practice and is a default in modern discounted variants, alongside work scaling solvers through parallelism, abstraction, sampling, and evaluation tools.The cited practice traces to Tammelin (2014), Tammelin et al. (2015), and Bowling et al. (2015).Source: §2 · pp. 3–4

3. Preliminaries

• RM+ updates a nonnegative regret state by taking the componentwise positive part after adding instantaneous regret, then plays its normalized readout, using uniform play at zero state.The passage defines the payoff matrix, strategy simplices, and both players’ instantaneous regret vectors.Source: §3 · p. 4
• Algorithms are deterministic maps on joint states, iterated from zero initialization with fixed tie-breaking; fresh information can enter as a persistent update or a transient readout term.Joint states include regret states and any auxiliary variables.Source: §3 · p. 4
• Alternating and one-sided predictive dynamics receive player 1’s newly computed strategy as the same information channel, but only the alternating update folds it into player 2’s persistent regret state.The predictive arm uses a transient prediction term discarded after the readout; it is the canonical additive one-step-prediction form with a perfect predictor (Farina et al., 2021).Source: §3 · p. 4
• On matrix games, the duality gap is the best-response sum for linearly averaged strategies; on extensive-form games, reported exploitability is that sum divided by two.The anatomy analysis uses a shifted average in its first identity.Source: §3 · p. 4
• The preregistered evidence ladder distinguishes dynamical equivalence, strong or weak trajectory separation, and performance separation, with strong separation targeted first.The primary statistic is the per-game log10 ratio of an arm’s gap to alternation’s gap; the suite includes 47 matrix games and three extensive-form witnesses, run deterministically in lockstep.Source: §3 · p. 4

4. Mechanisms

• The four explanation families are canonical additive one-sided prediction, play-level proximal damping, staleness interpolation, and standard two-sided optimism.Table 1 catalogs representative arms, tested predictions, test tiers, and questions left for future explanations.Source: §4 · p. 4, Table 1 · p. 5
• For F1, the information-matched canonical predictive arm uses a transient prediction term with a perfect one-step predictor, while making half the fresh signal persistent meets the median criterion.The cost of removing persistence grows more slowly with perturbation than the cost of staleness.Source: §4 · p. 5
• At proximal damping λ = 10^-3, the measured cost is already 1.66×; the dial reaches alternation exactly only as λ approaches zero.The surrogate mixes the alternating target play with the old play and compares damping at equal perturbation.Source: §4 · p. 5
• The staleness family interpolates from alternation at delay d = 0 to simultaneous updating at d = 1, testing whether performance changes smoothly with delay.Player 2 sees player 1’s strategy from d steps earlier.Source: §4 · p. 5
• Across conditioning and tree depth, the advantage of the tested explanation families over alternation changes sign while alternation’s advantage over simultaneous updating does not.Canonical families do not reproduce alternation at the median criterion at catalog settings; the weakest settings of all three dials do.Source: §4 · p. 5

Injection paths and readout mechanics

• Both paths receive the same signal and produce the same immediate readout, but persistent injection retains the updated state while transient injection retains the old state.Large persistent regret mass limits persistent-path motion; transient injection can jump to the current signal’s sign pattern when persistent mass is small relative to signal mass.Source: §5 · p. 6

Witness dynamics

• The vertex recurrence mechanism is organized by epochs: repeated qualifying epochs imply infinitely many vertex times, while 33–95% of tail rounds were exact vertices on the tested grid.The median exact-vertex frequency was 52%; the persistent state’s maximum infinity norm was ≤8.5 × 10^-3, with its non-signal component exactly zero on a median 90% of tail rounds.Source: §5 · pp. 7, 9
• On the witness, transient injection washes down the disfavored state and produces bang–bang vertex play, while alternating RM+ accumulates regret mass and stays near equilibrium.At T=10^6, alternating’s tail-maximum first-coordinate deviation was ≤0.04, versus 0.52–0.71 for os-prm+; these are half the full profile ℓ1 distances.Source: §5 · p. 8

Theorem 2: Information-matched separation dichotomy

• Under the interior-band assumption, Theorem 2 says os-prm+ either visits exact vertices infinitely often, yielding separation of at least 2η, or has only finitely many vertex visits.The assumption is supported by finite-horizon evidence, but its validity for all rounds and unconditional separation remain conjectures.Source: §5 · pp. 9–10

Exploitability consequence

• Without the interior-band assumption, every os-prm+ vertex time on the witness is Ω(1)-exploitable, so infinitely many vertex visits imply infinitely many such last iterates.This consequence depends only on the vertex-time definition, not the interior-band assumption.Source: §5 · p. 9

Prediction and regret error

• A perfect prediction of player 1’s next strategy is not a perfect prediction of player 2’s realized regret: each vertex jump incurs error |y_t−y_{t+1}| |δ2(x_{t+1})|.The witness’s |δ2| tail p99 was ≤0.026; the regret error comes from utility changes caused by player 2’s own move and the positive-part update’s lack of shift invariance.Source: §5 · pp. 9–10

Theorem 2: Information-matched separation dichotomy

• At a=2, the minimum measured profile distance at vertex times was 0.74484 versus the predicted 2η value 0.74464, and never fell below the bound.Across the 60-point scan, the maximum relative deviation from the predicted separation constant was 9.0 × 10^-4.Source: §5 · p. 10, Figure 2 · p. 10

Alternating updates and duality-gap improvement

• The exact duality-gap decomposition makes alternation’s extra term measurable along trajectories; under RM+, its improvement term is nonnegative and has a closed form in regret-state updates.The paper relates that term to the squared untruncated regret increment and truncated remainder divided by new regret mass, and bounds it below by a fixed fraction of potential increase when q1=0 with uniform weights.Source: §5 · pp. 10–11

• On truncation-free windows, Δ subtracts at least 1/√m of the increase in a potential that is O(T) for bounded payoffs.This establishes a window-level improvement bound; the faster local decay exponent of alt remains open.Source: §5 · p. 11
• When all four bracketed sums are positive, the alt–sim gap ratio decomposes into a regret channel and an improvement channel.The comparison uses the same game, horizon, and weights, with the alt gap read under the shifted-average convention.Source: §5 · p. 11
• The improvement channel is nonnegative, while the regret channel has no sign guarantee.Source: §5 · p. 11
• On 42/47 games, os-prm+’s inflated regrets sit in R1, where player 1 faces a bang–bang opponent.Unlike alt, os-prm+ has no improvement term in the second identity of Eq. (8), so its slowness must appear as inflated regrets.Source: §5 · p. 11

Primary comparison

• All 11 non-alt arms had median |ρ_g| ≥ 0.477, and none reproduced alt on at least 90% of games in any tested tolerance band.The closest arm was two-sided prm+ at 1.158, a 14× gap factor.Source: §6 · p. 12, Table 2 · p. 12
• Across 47 games, os-prm+ was 33× slower than alt in final gap, with median final profile L1 distance 0.58.Its drift and oscillation were 66× and 263× larger, respectively.Source: §6 · p. 12

Staleness

• At the smallest tested stale fraction, s = 0.01, the gap penalty was 2.6×; across s ∈ [0.01, 1], the mixing-branch excess ratio fit 36s^0.67.Below s = 0.01 was untested.Source: §6 · p. 12

Conditioning

• Alt’s advantage over sim remained at least 13.5× across κ = 10^1–10^8, while the optimism-family advantage closed around κ = 10^5–10^6.Prm+ was 3.9× and 2.7× slower than alt at κ = 10^7 and 10^8, respectively.Source: §6 · p. 13

Extensive-form witnesses

• On Kuhn, os-prm+ was 75× slower than alt, while on Leduc alt attained the lowest exploitability and two-sided optimism was 19–70× slower.The Leduc comparison is reported across the 12 arms.Source: §6 · p. 13
• On the 8177-node liar’s-dice witness, alt was fastest, but the pre-registered Leduc-level separation gate failed because the game was easy for every dynamics.On two larger trees, os-prm+ and alt-prm+ shifted from edging alt by up to 2% to trailing it by 9–13%.Source: §6 · p. 13

Gap decomposition

• The alt/sim log-speedup had median 1.60, with 0.91 from the regret channel and 0.58 from the improvement channel.The regret-channel share was 0.60 at the median and exceeded one half on 31/47 games.Source: §6 · p. 13, Figure 5 · p. 14

Injection dial

• At μ = 0.5, the injection dial placed 27/47 games within 3× of alt, compared with 8/47 at μ = 0.The tail-mean trajectory distance fell from 0.69 to 0.07 over the dial’s full range.Source: §6 · p. 14, Table 5 · p. 15, Figure 6 · p. 15

Scope

• The measured regularities are scoped to the tested self-play regimes: the 47-game suite and Kuhn, Leduc, and liar’s dice.The paper notes that several mechanism classes remain outside the comparisons, including persistent auxiliary prediction states and non-RVU stabilization.Source: §7 · pp. 16–17

Staleness

• At s = 0.01, staleness already imposed a 2.6× median gap penalty; at s = 1, the penalty was 41×.The mixing-branch fit over s ∈ [0.01, 1] was gap/gap_ALT − 1 ≈ 36s^0.67.Source: §7 · p. 16

Conditioning

• Across seven orders of magnitude of conditioning, alt’s advantage over sim never fell below 13.5×, while optimism-family acceleration closed near κ ≈ 10^5–10^6.The alt/sim medians ranged from 13.5 to 149.1 across eight bands.Source: §7 · p. 16

Regime crossings

• The two-sided optimism arms beat alt on well-conditioned matrix games and Kuhn but lost to it on Leduc, where they were 19–70× slower.Prm+ was 3.9× and 2.7× slower than alt at κ = 10^7 and 10^8, respectively; the optimism-family advantage therefore changed across regimes.Source: §7 · p. 16

Perturbation costs

• The smallest tested settings cost 2.6× for 1% staleness, 1.66× for 0.1% damping, and 1.65× for a 50% loss of persistence.From μ = 0.75 onward, the injection dial put 90% of games within 3× of alt.Source: §7 · pp. 16–17

8. Conclusion

• Under the interior-band assumption, either predictive exact-vertex times recur with profile distance at least 0.53–0.91 infinitely often, or vertex play terminates.The antecedents hold on all 60 grid points at 2 × 10^5 iterations across four precisions.Source: §8 · p. 17

A. Proofs

• On the witness family A(a), with a ∈ (1, 4], the equilibrium strategy components are both 2/(a+3).The passage reports that the algebraic identities are additionally checked symbolically (15/15 checks).Source: A. Proofs · p. 23

A.2. Proof of Lemma 5 (exact-vertex characterization)

• The readout is e1 when the disfavored component truncates to zero and the favored component is positive; e2 follows under the symmetric condition.If both components truncate, the readout is zero and the uniform convention applies.Source: §A.2 · p. 23

A.3. Robust variant (Lemma 5′, ρ-near-vertex readout)

• With persistent-state violations bounded by ε̄, the separation constant degrades from 2η to 2(η−ρ), where ρ = ε̄/(θΔ0 + ε̄).The near-vertex bound assumes a signal gap Δ ≥ Δ0 and yt ≤ 1−θ.Source: §A.3 · p. 23
• The robust lemma gives no floating-point margin; its robustness evidence is agreement of every certificate statistic across four precisions.Its bound is useful only when ρ is much smaller than η, whereas on the witness the persistent-state-to-signal ratio has median 0.21 and reaches 1 at jump times.Source: §A.3 · p. 23

A.4. Proof of Lemma 6 (best-response-matched suppression)

• Vertex play aligned with the stale signal washes the disfavored persistent component to zero; the resulting small state makes subsequent domination easier.The measured tail persistent state is at most 8.5 × 10^-3 for os-prm+, versus component sums of 37–60 for alt on the same games.Source: §A.4 · p. 23

A.5. Proof of Lemma 7 (vertex–uniform classification)

• When the persistent state is zero, the readout is an exact vertex if the positive part of the transient signal has one positive coordinate, and uniform if it is zero.The supplied proof passage notes that the signal’s components have opposite signs or one is zero.Source: §A.5 · p. 24

A.6. Proof of Lemmas 8 and 9 (complex update and normalizer growth)

• The complex update multiplies the state by (1−iε), so its squared magnitude grows by the factor 1+ε^2.When the relevant sum converges, the regret increment tends to zero and play tends to the equilibrium component.Source: §A.6 · p. 24

A.7. Proof of Proposition 1 (epoch structure)

• Infinitely many positive epochs force infinitely many predictive vertex times.The epoch argument shows that a positive epoch of length at least two contains a vertex time.Source: §A.7 · p. 24

A.8. Proof of Lemma 11 (sign-flip readout)

• At a sign flip, an e2 readout requires the coordinate favored by the finished epoch to be no greater than the signal’s growth across the flip.An entering zero disfavored coordinate is neither necessary nor sufficient.Source: §A.8 · p. 25

A.9. Proof of Theorem 2

• When predictive vertex times recur, the interior-band assumption places alternating play at least 2η from either vertex, yielding the profile-distance lower bound.The bound applies at vertex times t ≥ T0.Source: §A.9 · p. 25

A.10. Machine-checked identities

• Table 7 lists 15 symbolic identities checked with a, x, y, α, and β treated as free symbols.The proof passage states that all 15 identities are symbolically verified.Source: Table 7 · p. 25

B. Derivations

• Near x*, a macroscopic jump in y can coincide with a small regret-prediction error; the measured p99 is at most 0.026.This is the passage’s stated condition and measured value.Source: B. Derivations · p. 26
• Identities (8)–(10) were numerically verified on all 1,271 eligible matrix-suite trajectories, and Lemma 3’s bound held step by step on alt.The reported residual was below 10^-9 relative to the largest term, and the lower bound was checked against Δ recomputed with uniform weights.Source: B. Derivations · p. 27

C. Registration

• The preregistered strong-separation gate required a nonempty interval where the tail-half minimum of D_t stayed at least 0.2.The registration passage says the ladder and operational gates were frozen before theorem-directed experiments.Source: §C.1 · p. 27

C.1. The ladder and its gates

• Only two isolated grid points met the 0.2 tail-minimum criterion, with no adjacent qualifying points; the gate therefore failed.The scan covered 60 points, and its tail minima had median 0.012 and minimum 3.4 × 10^-4.Source: §C.1 · p. 27
• The failed gate led the authors to downgrade the proof target to weak trajectory separation; mean-level flatness is reported only as empirical context.The scan’s windowed means were flat at 0.60–1.06 across all 60 points, while deep-run tail minima fell to about 4 × 10^-4.Source: §C.1 · p. 27

C.2. Three proof routes, honestly accounted

• The authors place the proof between a rigorous conditional dichotomy and an unconditional theorem, with the remaining gap recorded as Conjecture 1.The time-averaged route cannot yield constant separation; a direct-cascade route stalls at excluding asymptotic sticking, while the ODE route requires an unproved growth rate for S_t and would not resolve the predictive-side difficulty.Source: §C.2 · pp. 27–28

C.3. Exact-arithmetic validation

• Exact rational replay agrees with floating-point trajectories to 10^-12 while feasible, but denominator growth restricts the replay to early iterations.Long floating-point runs show at most eight symbolic itineraries; os-prm+ has persistent-state zeroing in 88–100% of tail windows and vertex visits at 51–66% on the five tested points.Source: §C.3 · p. 28

C.4. Scope of the claims

• Claims are limited to deterministic self-play of tested rules, a 2 × 2 theorem, and witness-level extensive-form evidence; sampled variants and adversarial training are outside scope.The catalog covers dominant, not all conceivable, explanations; the staleness and damping dials are tested only down to s=λ=10^-2 and 10^-3.Source: §C.4 · p. 28

D.1. The twelve arms

• The twelve main dynamics share RM+ state conventions and differ in update schedule and prediction structure.The catalog also includes an alt-prm+ composition and two re-injection dials.Source: §D.1 · p. 28, Table 8 · p. 29

D.2. Game suite

• The suite combines 47 matrix games with Kuhn, Leduc, and liar’s-dice witnesses, plus larger liar’s-dice scale tests.Tree experiments use standard CFR decomposition with RM+ at each information set; the stated sequence-form sign is measured on trees, not proved.Source: §D.2 · p. 28

D.3. Lockstep protocol and determinism

• A lockstep protocol advances each arm with its alt reference on the same game, avoiding cross-run nondeterminism and validating references against independent runs.The section defines drift, oscillation, hug criteria, and the last-iterate curve quantities used in comparisons.Source: §D.3 · p. 29

D.4. Sanity checks

• Implementation checks reproduced pilot results, correcting the two-sided prm+ count to 9/12 at T=10^4 and 11/12 at T=2 × 10^4; alt versus os-prm+ separated on 12/12 pilot games.The latter comparison had a median 25.3× ratio; on the liar’s-dice witness, alt exploitability decreased monotonically to 5.45 × 10^-8 over T=10^4.Source: §D.4 · p. 30

E.1. F1 boundary statistics (47-game matrix suite)

• 0/47 arms meet the 90% reproduction criterion in any band; gs-prox(1.0) rises to 6/47 only in the widest band.These counts are interpretable hug summaries, not the primary criterion.Source: §E.1 · p. 30, Table 9 · p. 30

E.2. Staleness curve and robustness

• 39.4 was the median ratio across 50 independent random games (95% CI 29.7–51.0); at d=2 the median ratio was 79.0 (95% CI 64.3–98.6).Strict per-game monotonicity violations occurred in 4 of 47 games.Source: §E.2 · p. 30, Table 10 · p. 30

E.3. Conditioning sweep (full medians)

• κ*(prm+)=10^5 and κ*(pp)=κ*(ts-opt)=10^6 under the first-band gap/alt ≥1/2 closure rule; under vs-sim, no arm triggers through κ≤10^8.Under the vs-sim reading, the advantage shrinks from 10^3–10^5× to 5.8–107×.Source: §E.3 · p. 31

E.4. Extensive-form witnesses (full ranking)

• On liar’s dice, final L1 distances to alt range from 10.1 to 23.3 across the reported arms, with no trajectory-level hugging; Leduc’s decay summary is weakly discriminative.The extensive-form conclusions therefore rely on gap ratios.Source: §E.4 · p. 31, Table 12 · p. 31

E.5. Witness-family certificates (theorem support)

• At a=2, the measured minimum profile distance at vertex times is 0.74484, close to 2η=0.74464; vertex frequency is 0.657.Across all 60 grid points, the un-injected side’s tail p99 |δ2(x_t)| is at most 0.026.Source: §E.5 · p. 31, Table 13 · p. 31

E.6. Four-precision recomputation of the certificates

• The certificate statistics agree across double, extended, and 30- and 60-digit arithmetic, although individual os-prm+ trajectories do not.The recomputation uses the same 60-point grid in lockstep.Source: §E.6 · p. 31, Table 14 · p. 32

E.7. Exact decomposition

• The exact decomposition is reported on four witness games at T=2 × 10^4 per unit weight, separating stale and fresh opponent-strategy readings.The table caption identifies the scope but does not state the decomposition’s numerical results.Source: §E.7 · p. 32, Table 15 · p. 32

E.8. Epoch audit

• The epoch audit covers the tail half at T=2 × 10^5; Lemma 11 is evaluated on length-one epochs and matches measured readout in all of them.The listed length-one counts are 82237, 50105, 39564, and 27582; vertex times inside no epoch are 0/0/1/0.Source: Table 16 · p. 32, §E.8 · p. 32

E.9. Perturbation sensitivity and the three dials

• The perturbation analysis tests relative size 10^-13 under payoff scaling and initial-regret jitter, alongside verdicts for mixing, damping, and injection dials.The supplied passages describe the table scopes but do not give the verdict values.Source: Table 17 · p. 33, §E.9 · p. 33, Table 18 · p. 33

E.10. Per-game log-ratios

• Per-game log-ratios ρ_g=log10(gap_arm/gap_ALT) are reported for the 47-game suite, with positive values indicating slower performance than alt.The table has one row per game and includes GS.25/GS1 and delay-d settings.Source: §E.10 · p. 33, Table 19 · p. 34