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 no-regret algorithms with an adaptive, non-monotonic learning rate that paces the learning process of the players. Perhaps counterintuitively, the learning rate control aims to temporarily slow down the learning of players with low regret, preventing runaway behavior and provably leading to equilibrium faster. The resulting dynamics are uncoupled (that is, do not require knowledge of anything other than each player’s own utility), and guarantee near-constant regret per player with a polylogarithmic dependence on the number of actions. They apply both in sequential and non-sequential games, no matter the number of players, and no matter the presence of imperfect information