Learning in games with continuous action sets and unknown payoff functions

By Panayotis Mertikopoulos, Zhengyuan Zhou. 2016

303 citations recorded by the source corpus.

This paper examines the convergence of no-regret learning in games with continuous action sets. For concreteness, we focus on learning via “dual averaging”, a widely used class of no-regret learning schemes where players take small steps along their individual payoff gradients and then “mirror” the output back to their action sets. In terms of feedback, we assume that players can only estimate their payoff gradients up to a zero-mean error with bounded variance. To study the convergence of the induced sequence of play, we introduce the notion of variational stability, and we show that stable equilibria are locally attracting with high probability whereas globally stable equilibria are globally attracting with probability 1. We also discuss some applications to mixed-strategy learning in finite games, and we provide explicit estimates of the method’s convergence speed.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, methodology): “As we mentioned in the main paper, the assumption of quasi-strong monotonicity is equivalent to the concept of strong stability described in Mertikopoulos and Zhou [2019].”
Stochastic Mirror Descent in Variationally Coherent Optimization Problems (2017, methodology): “Our analysis leverages the Lyapunov properties of the Fenchel coupling [14], a primal-dual divergence measure that quantifies the distance between primal (decision) variables and dual (gradient) variables, and which serves as an energy function to establish recurrence of SMD (Theorem 3.”
Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities (2021, background): “Some nontrivial examples satisfying the generalized monotone assumption can be found in [7, 44, 28].”
Stable Opponent Shaping in Differentiable Games (2018, background): “Mertikopoulos & Zhou (2018) recently prove local convergence of no-regreat learning to variationally stable equilibria, though under a number of regularity assumptions.”
Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games (2020, background): “This information can be imperfect for a multitude of reasons; see Mertikopoulos and Zhou [2019, Section 3.1].”
Invariant Risk Minimization Games (2020, background): “There are diﬀerent strategies in the literature to compute the equilibrium, such as best response dynamics (BRD) and ﬁctitious play [4], but none of these strategies are guaranteed to arrive at equilibria in continuous games except for special classes of games [32, 33, 34, 35].”
Differentiable Game Mechanics (2019, background): “Convergence has also been studied in various n -player settings, see Rosen (1965); Scutari et al. (2010); Facchinei and Kanzow (2010); Mertikopoulos and Zhou (2016).”
On the convergence of single-call stochastic extra-gradient methods (2019, background): “As for saddle-point problems and smooth games, variants of this condition can be found in several different sources, see e.g., [16, 24, 29, 40, 41] and references therein.”