Title: Near-Optimal No-Regret Learning Dynamics for General Convex Games

Speaker: Professor Gabriele Farina (Assistant Professor, MIT)

Abstract: Recent research has introduced uncoupled learning dynamics that, when adopted by all players in a game, ensure that each player’s regret after T rounds grows only polylogarithmically with T — representing an exponential improvement over the classic guarantees of the no-regret framework. However, these advances have so far been restricted to specific types of games with well-structured strategy spaces, such as normal-form and extensive-form games. This leaves open the important question of whether O(polylog T) regret bounds can be achieved in more general settings involving convex and compact strategy sets, which are common in key models across economics and multiagent systems — all while maintaining computationally efficient strategy updates. In this paper, we address this open problem by presenting the first uncoupled learning algorithm that achieves O(log T) per-player regret in general convex games, where utility functions are concave and defined over arbitrary convex and compact strategy sets.

Short Bio: Gabriele Farina is an Assistant Professor at MIT in EECS and LIDS, additionally affiliated with the Operations Research Center (ORC). He holds the X-Window Consortium Career Development Chair. Before that, he spent a year as a Research Scientist at FAIR (Meta AI), where he worked on Cicero, a human-level AI agent combining strategic reasoning and natural language. Before that, he was a Ph.D. student in the Computer Science Department at Carnegie Mellon University, where he worked with Tuomas Sandholm. He was supported by a 2019-2020 Facebook Fellowship in the area of Economics and Computation. His dissertation on learning and equilibrium computation in imperfect-information games received the ACM SIGecom dissertation award, one of the two ACM dissertation award honorable mentions, the CMU SCS dissertation award, and the Runner up Victor Lesser distinguished dissertation award. He is the recipient of an NSF CAREER award, and is an AI2050 Early Career Fellow.