Towards Optimal Rates for Multiagent Learning

Abstract: Uncoupled learning dynamics for multiagent interactions (“games”) define iterative update rules that each agent can apply repeatedly to improve their strategy. A celebrated result establishes that for several choices of learning dynamics, global notions of equilibrium in the system will arise. This connection runs deep and is far from trivial: equilibrium emerges even despite formally chaotic behavior. Today, learning dynamics are the most scalable technique for equilibrium computation in large-scale, general games.

In this talk, I will focus on the following question: how fast can equilibrium emerge in general games, and how can we design learning dynamics that enable such fast rates? After retracing the history of the problem and recent progress, I will discuss new results that achieve state-of-the-art guarantees. Our algorithm is obtained by combining the classic optimistic multiplicative weights update (OMWU) with an adaptive, non-monotonic learning rate that paces the learning process of the players. The learning rate control, which is obtained via a self-concordant optimization problem, aims to temporarily slow down the learning of overachieving players, preventing runaway behavior and provably leading to equilibrium faster.

Bio: Gabriele Farina is an Assistant Professor at MIT EECS and LIDS. His research combines techniques and notions of strategic behavior from game theory together with modern tools from machine learning, optimization, and statistics to construct state-of-the-art methods to compute optimal strategies for multiagent interactions. Professor Farina received his Ph.D. in Computer Science from Carnegie Mellon University, and his work has been recognized with several awards, including a Best Paper Award at NeurIPS’20 and an Outstanding Paper Honorable Mention at ICLR’23. His dissertation was recognized with the ACM SIGecom Doctoral Dissertation Award and one of the two ACM Dissertation Award Honorable Mentions, among others.