Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games

Abstract

Algorithms based on regret matching, specifically regret matching$^+$ (RM$^+$), and its variants are the most popular approaches for solving large-scale two-player zero-sum games in practice. Unlike algorithms such as optimistic gradient descent ascent, which have strong last-iterate and ergodic convergence properties for zero-sum games, virtually nothing is known about the last-iterate properties of regret-matching algorithms. Since last-iterate convergence is an attractive property both for numerical optimization reasons and because no-regret learning is viewed as a plausible method of real-world learning in games. In this paper, we study the last-iterate convergence properties of various popular variants of RM$^+$. First, we show numerically that several practical variants such as simultaneous RM$^+$, alternating RM$^+$, and simultaneous predictive RM$^+$, all lack last-iterate convergence guarantees even on a simple $3\times 3$ game. Then, we go on to show that recent variants of these algorithms based on a *smoothing* technique do enjoy last-iterate convergence: we prove that *extragradient RM$^{+}$* and *smooth PRM$^+$* enjoy asymptotic last-iterate convergence (without a rate) and $1/\sqrt{t}$ best-iterate convergence. Finally, we introduce restarted variants of these algorithms, and show that in both cases they enjoy linear-rate last-iterate convergence.