Regret Matching+: (In)Stability and Fast Convergence in Games
Gabriele Farina Julien Grand-Clément Christian Kroer Chung-Wei Lee Haipeng Luo
Regret Matching+ (RM+) and its variants are important algorithms for solving
large-scale games. However, a theoretical understanding of their success in
practice is still a mystery. Moreover, recent advances 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 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.
Our experiments show the advantages of our algorithms over vanilla RM+-based
algorithms in matrix and extensive-form games.