Equilibrium tracking and convergence in dynamic games

Panayotis Mertikopoulos (1, 2) , Mathias Staudigl (3)

1 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems
2 Criteo AI Lab
3 Maastricht University [Maastricht]

In this paper, we examine the equilibrium tracking and convergence properties of no-regret learning algorithms in continuous games that evolve over time. Specifically, we focus on learning via "mirror descent", a widely used class of noregret learning schemes where players take small steps along their individual payoff gradients and then "mirror" the output back to their action sets. In this general context, we show that the induced sequence of play stays asymptotically close to the evolving equilibrium of the sequence of stage games (assuming they are strongly monotone), and converges to it if the game stabilizes to a strictly monotone limit. Our results apply to both gradient-and payoff-based feedback, i.e., the "bandit" case where players only observe the payoffs of their chosen actions.

Domaines: Optimisation et contrôle [math.OC]

Panayotis Mertikopoulos, Mathias Staudigl. Equilibrium tracking and convergence in dynamic games. CDC 2021 - 60th IEEE Annual Conference on Decision and Control, Dec 2021, Austin, United States. pp.1-8. ⟨hal-03342397⟩