Alternating updates accelerate learning in imperfect-information games
Why Alternation Speeds Up Counterfactual Regret Minimization?
Computer Science and Game Theory
Summary
When two players learn strategies in games where they can't see everything, it turns out updating their play one after the other is faster. The common idea that this works because players get optimistic hints from seeing each other's new plans doesn’t fully explain why. The authors studied how these updates affect the learning path and found that speedups depend on whether certain plays repeat or stop. Their results show any explanation must consider how delays in responding to old information slow learning down.
What this means in practice
- •For game ai developers: Optimize training algorithms for AI players in imperfect-information games by applying alternating update methods to speed convergence.
- •For automated decision systems teams: Improve decision-making models that rely on iterative strategy updates by reducing delays caused by stale opponent information.
A theory result. No direct application yet.
Authors
Boning Li, Longbo Huang
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.