Regret Matching+: (In)Stability and Fast Convergence in Games

Regret Matching + (RM + ) and its variants are important algorithms for solving large-scale games [35] . However, a theoretical understanding of their success in practice is still a mystery. Moreover, recent advances [34] on fast convergence in games are limited to no-regret algorithms such as online mirror descent, which satisfy stability. In this paper, we first give counterexamples showing that RM + and its predictive version [12] can be unstable, which might cause other players to suffer large regret. We then provide two fixes: restarting and chopping off the positive orthant that RM + works in. We show that these fixes are sufficient to get O(T 1/4 ) individual regret and O(1) social regret in normal-form games via RM + with predictions. We also apply our stabilizing techniques to clairvoyant updates in the uncoupled learning setting for RM + and prove desirable results akin to recent works for Clairvoyant online mirror descent [31, 14] . Our experiments show the advantages of our algorithms over vanilla RM + -based algorithms in matrix and extensive-form games.