Speaker: Vidya Muthukumar (UC Berkeley)

Title: On the Impossibility of Convergence of Mixed Strategies with No-Regret Learning
Abstract: We study the convergence properties of the mixed strategies that result from a general class of optimal no-regret learning strategies in a repeated game setting where the stage game is any 2 × 2 competitive game, i.e. all the Nash equilibria (NE) of the game are completely mixed. While the convergence of the ergodic averages of the strategies is classically known, the limiting behavior of the mixed strategies, also called the last-iterate, is a more recent topic of interest. We show that any choice of optimal no-regret, approximately mean-based strategy for both players would necessarily yield last-iterate divergence --- including variants that use recency bias. This result demonstrates a crucial difference in outcomes between using the opponent's mixtures and realizations to make strategy updates.

Joint work with Soham Rajesh-Phade and Anant Sahai.