OpenAlex ·
Why Alternation Speeds Up Counterfactual Regret Minimization?
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.21970
- Original
- Read it at the publisher
- Topics
Abstract
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 first player just produced. A widely repeated intuition explains why: seeing the opponent's fresh strategy should act like optimism. We treat this intuition as a testable hypothesis about deterministic two-player zero-sum self-play dynamics and find that its canonical additive form fails an information-matched test. On an analytic witness family we compare alternating RM$^{+}$ against a one-sided predictive RM$^{+}$ that receives the same information channel each round and differs only in where the fresh signal enters, a persistent regret state versus a transient prediction term. Our main result is a dichotomy theorem that reduces trajectory separation to the recurrence of exact-vertex play by the predictive dynamics: under an interior-band assumption on the alternating iterate, either vertex times recur and the profile distance is at least, infinitely often, an explicit constant that our measurements nearly attain, or they terminate. Across the tested self-play regimes, any correct explanation of the alternation speedup must reproduce a staleness cost present at the smallest tested stale fraction, an advantage that persists across seven orders of payoff conditioning, regime crossings of the optimism family, and a measured per-perturbation cost of weakening the injection path that is far steeper for staleness than for partial persistence.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Artificial Intelligence
When is a better LLM worth paying for? Stochastic Optimization with Switching Mixed-Fidelity Oracles
ParetoChat: An LLM-Based Interface for Interactive Multi-Objective Optimization
Honesty is the Best Policy ... or is it? Demand Management for Probabilistic Service Options
Distributed Performance Boosting through Neural Control for Plug-and-Play Networks
Quantum-compatible Riemannian conjugate gradient for ground-state preparation
Get the few papers worth your time in Artificial Intelligence every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.