Scaling regret matching converges fast to equilibrium in zero sum games
Why Last-Iterate Scale-Invariant Regret Matching Converges Linearly?
Computer Science and Game Theory
Summary
This paper explains why a particular algorithm called IREG-PRM+ quickly finds the best strategy in zero-sum games without knowing how large the payoffs are. The authors show that the algorithm’s step size naturally stabilizes because the cumulative regret it tracks hits a limit, causing the process to lock in a steady pace. They prove this stabilization always happens and that it guarantees the algorithm’s decisions get steadily closer to the game’s perfect balance point. The paper also provides a way to monitor progress by observing certain measurable ratios, making it easier to track performance even in more complex games.
What this means in practice
- •For game theory software developers: Improve algorithms for computing equilibrium strategies in zero-sum games with no prior knowledge of payoff scales using norm saturation insights.
- •For ai system engineers: Use convergence analysis tools to monitor and improve iterative decision-making algorithms in multi-agent learning scenarios.
Tested on simulated data.
Authors
Boning Li, Longbo Huang
Abstract
IREG-PRM+ normalizes the cumulative regret vector by its own norm and attains optimal regret without knowledge of the payoff scale. Run unmodified on zero-sum matrix games, it converges linearly in the last iterate, and no analysis explains why. The obstacle is that the algorithm has no fixed step size to analyze: the step size is a state variable, the inverse of a regret norm that the trajectory itself moves. Every proved linear rate for regret-matching dynamics comes from restarting or modifying the update. We identify the mechanism as norm saturation: the regret norm rises to a finite limit and freezes the step size. We prove that it always does, with an explicit bound, and that saturation forces the last-iterate Nash gap to vanish on every matrix game; pointwise convergence follows whenever the equilibrium is unique. Near a unique strictly complementary equilibrium the active support freezes in one step, and the one-round Jacobian on that support has a closed form. The last-iterate then converges linearly at a closed-form rate, provided one scale-invariant quantity stays below one: the saturated step size times the largest singular value of the value-centered payoff submatrix on the support. On the $216$-instance testbed, the $184$ instances with a resolvable limit all satisfy it. The same analysis gives a ratio certificate: observable norm-increment ratios bound the unobservable Nash-gap ratio up to a constant that enters once and does not accumulate with the iteration count. Its slope-two law holds on $96.1\%$ of the instances where the slope is measurable, and the same increment monitors progress in extensive-form games, where best-response passes can be scheduled sparsely. The code is available at https://github.com/lbn187/NormCert.