Timezone: »

 
Poster
Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games
Tianyi Lin · Zhengyuan Zhou · Panayotis Mertikopoulos · Michael Jordan

Wed Jul 15 05:00 AM -- 05:45 AM & Wed Jul 15 04:00 PM -- 04:45 PM (PDT) @
in Poster Session 21 »
In this paper, we consider multi-agent learning via online gradient descent in a class of games called $\lambda$-cocoercive games, a fairly broad class of games that admits many Nash equilibria and that properly includes unconstrained strongly monotone games. We characterize the finite-time last-iterate convergence rate for joint OGD learning on $\lambda$-cocoercive games; further, building on this result, we develop a fully adaptive OGD learning algorithm that does not require any knowledge of problem parameter (e.g. cocoercive constant $\lambda$) and show, via a novel double-stopping time technique, that this adaptive algorithm achieves same finite-time last-iterate convergence rate as non-adaptive counterpart. Subsequently, we extend OGD learning to the noisy gradient feedback case and establish last-iterate convergence results--first qualitative almost sure convergence, then quantitative finite-time convergence rates-- all under non-decreasing step-sizes. To our knowledge, we provide the first set of results that fill in several gaps of the existing multi-agent online learning literature, where three aspects--finite-time convergence rates, non-decreasing step-sizes, and fully adaptive algorithms have been unexplored before.
Keywords: Game Theory and Mechanism Design · Learning Theory · Online Learning / Bandits

Author Information

Tianyi Lin (UC Berkeley)
Zhengyuan Zhou (Stanford University)
Panayotis Mertikopoulos (CNRS and Criteo AI Lab)
Michael Jordan (UC Berkeley)

More from the Same Authors