Multiagent Online Learning in Time-Varying Games

• 成果类型: Article
• 署名作者: Duvocelle, Benoit; Mertikopoulos, Panayotis; Staudigl, Mathias; Vermeulen, Dries
• 署名单位: Maastricht University; Inria; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Maastricht University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• 发表日期: 2023
• 页码: 914-941
• 关键词: stochastic-approximation; optimization; DYNAMICS; CONVERGENCE; gradient; descent; play; form

摘要

We examine the long-run behavior of multiagent online learning in games that evolve over time. Specifically, we focus on a wide class of policies based on mirror descent, and we show that the induced sequence of play (a) converges to a Nash equilibrium in time-varying games that stabilize in the long run to a strictly monotone limit, and (b) it stays asymptotically close to the evolving equilibrium of the sequence of stage games (assuming they are strongly monotone). Our results apply to both gradient- and payoff-based feedback-that is, when players only get to observe the payoffs of their chosen actions.