Timezone: »

 
Spotlight Poster
Regret Matching+: (In)Stability and Fast Convergence in Games
Gabriele Farina · Julien Grand-Clément · Christian Kroer · Chung-Wei Lee · Haipeng Luo

Thu Dec 14 08:45 AM -- 10:45 AM (PST) @ Great Hall & Hall B1+B2 #1708
in Poster Session 5 »
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.

Author Information

Gabriele Farina (MIT)
Julien Grand-Clément (HEC Paris / Hi!Paris)
Julien Grand-Clément

I am an Assistant Professor in the Information Systems and Operations Management department at HEC Paris and a Hi! Paris chair holder. My research focuses on data-driven decision making under parameter uncertainty, with applications in healthcare and algorithmic game theory. I received my Ph.D. in Operations Research from Columbia University in 2021 where my advisors were Prof. Vineet Goyal and Prof. Carri Chan. Before Columbia, I completed my master and undergraduate studies at Ecole polytechnique (France) in 2016, with a major in algorithms and optimization.

Christian Kroer (Columbia University)
Chung-Wei Lee (University of Southern California)
Haipeng Luo (University of Southern California)

More from the Same Authors