skip to main content

H.B. Keller Colloquium

Monday, November 13, 2023
4:00pm to 5:00pm
Add to Cal
Annenberg 105
Regret Matching+: (In)Stability, Low Regret, and Last-Iterate Convergence in Games
Haipeng Luo, Associate Professor, Computer Science, University of Southern California,

Algorithms based on Regret Matching+ (RM+) and its variants are among the most popular approaches for solving large-scale games (such as poker) in practice. However, the theoretical understanding of their success is still a mystery --- unlike other algorithms such as optimistic gradient descent, which have been shown to enjoy stability, low regret, and fast convergence when employed by all players, very little is known about RM+ beyond its classical regret guarantee against a worst-case adversary.

In this talk, I will present our recent attempts towards a better understanding of RM+. Specifically, I will start by showing that, contrary to popular belief, RM+ and many of its variants can in fact produce unstable strategies that suffer large regret and diverge even on a simple 3 × 3 game. Then, I will discuss how a couple of simple fixes can help stabilize the algorithms and eventually lead to constant regret and last-iterate convergence. I will conclude with some experimental results to show the advantages of our proposed algorithms.

This talk is based on joint work with Yang Cai, Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, and Weiqiang Zheng. 

For more information, please contact Narin Seraydarian by phone at (626) 395-6580 or by email at [email protected].