Recent Advances on Online Learning in Games.

In this talk we will present recent results on the convergence rate of online learning algorithms in the context of multi-player normal-form games. t's established that when all agents in a normal-form game employ a no-regret algorithm, the time-averaged joint strategy profile converges to an $\epsilon$-approximate Coarse Correlated Equilibrium at a rate of $O(1/\epsilon^2)$. However, recent works have delved into online learning algorithms that enhance the convergence rate to $\tilde{O}(1/\epsilon)$ once adopted by all agents. Our talk will cover the recent results for Optimistic Hedge [1], Clairvoyant MWU [2], and Follow the Perturbed Leader [3]. [1] Near-Optimal No-Regret Learning in General Games, [Daskalakis et al., NeurIPS 2021] [2] Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update [Piliouras et al, NeurIPS 2022] [3] Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Games, [Anagnostides et al. NeurIPS 2022]