2023/05/24 by Gabriele Farina, Farina, Gabriele, Julien Grand-Clément +7 · 5 citations
Decision Sciences · Physics and Astronomy · Computer Science · #Advanced Bandit Algorithms Research #Quantum many-body systems #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2305.14709
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(T1/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.