Learning in games with continuous action sets and unknown payoff functions

Panayotis Mertikopoulos, Zhengyuan ZhouMath. Program 2019 · OpenReview

TL;DR

This paper investigates how players learn to coordinate in games with continuous actions and unknown payoffs, using a "dual averaging" learning strategy. They introduce "variational stability" as a key concept to predict convergence to Nash equilibria, showing that stable equilibria are reliably reached even with noisy feedback.

What Problem Does This Paper Address?

In many real-world scenarios, like economic markets or resource allocation, multiple agents interact in a game. Each agent wants to maximize their own payoff, but the game's rules (payoff functions) are often unknown, and their actions affect each other. A common learning approach for such agents is "no-regret learning," where agents aim to minimize their cumulative losses over time. However, a crucial question is whether this no-regret learning actually leads to stable outcomes, specifically Nash equilibria, where no agent has an incentive to unilaterally change their strategy. This paper tackles the challenge of understanding when and how no-regret learning, specifically the dual averaging method, converges to Nash equilibria in games with continuous action spaces, even when agents only receive noisy estimates of their payoff gradients.

Methods

The core of the paper's methodology lies in analyzing the dual averaging (DA) learning algorithm. DA involves players taking steps based on noisy estimates of their payoff gradients and then "mirroring" these steps back into their action sets. A key contribution is the introduction of variational stability (VS), a new concept that characterizes equilibria based on the local behavior of payoff gradients. This concept is more general than traditional monotonicity conditions and allows for the analysis of a wider range of games. The authors use tools from stochastic approximation, martingale theory, and convex analysis, particularly a "primal-dual divergence" measure called the Fenchel coupling, to prove convergence guarantees. They also introduce a second-order criterion (Hessian-based) to test for variational stability.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Variational Stability is Key: The paper introduces "variational stability" as a crucial concept for understanding convergence in learning games. It's a more general condition than monotonicity and directly relates to the local behavior of payoff gradients around an equilibrium.
  • No-Regret Doesn't Always Mean Equilibrium: The authors highlight that simply using no-regret learning doesn't automatically guarantee convergence to a Nash equilibrium. Their work provides conditions under which it does converge.
  • Noise is Manageable: Even with noisy estimates of payoff gradients (a realistic scenario), the dual averaging algorithm can still converge to stable equilibria, though the convergence rate might be affected.
  • Global vs. Local Stability Matters: The paper distinguishes between globally stable and locally stable equilibria, showing that globally stable ones are reliably reached (with probability 1), while locally stable ones are reached with high probability.
  • The Power of the Fenchel Coupling: This "primal-dual divergence" measure is a powerful tool for analyzing the convergence of the dual averaging algorithm, acting as a Lyapunov function.

Key Results

  • Convergence to Variational Stability: The paper proves that under dual averaging, the sequence of play converges to globally variationally stable equilibria with probability 1, and to locally stable equilibria with high probability.
  • Nash Equilibrium Guarantee: For games that are (pseudo-)concave or admit a concave potential, variational stability implies convergence to Nash equilibria.
  • Convergence Speed Estimates: Explicit estimates for the convergence speed are provided, showing that the gap from a stable state decays as O(1/√n) under appropriate step-size choices.
  • Elimination of Dominated Strategies: In finite games, the learning process is shown to eliminate dominated strategies.
  • Local Convergence to Strict Equilibria: For games with strict Nash equilibria, the algorithm achieves convergence with arbitrarily high probability.

Limitations and Future Work

  • Noise Sensitivity: While convergence is shown even with noise, the paper notes that the "critical" value for the step-size parameter (β=1/2) is tied to the finite mean squared error hypothesis. Relaxing this or considering different noise models could be future work.
  • Choice of Regularizer: The paper discusses how the choice of "regularizer" (which defines the players' choice maps) impacts convergence speed, especially for sharp equilibria. However, the optimal choice of regularizer in the general case remains an open question, with a trade-off between steepness and the Ω/K factor in convergence rates.
  • Information Availability: The current analysis assumes players can estimate gradients. Future work could explore scenarios where players only have access to realized, in-game payoffs, requiring them to reconstruct gradients.
  • Extra-Gradient Methods: The paper suggests extending extra-gradient approaches to online learning processes as a potential avenue for future research.

Summary updated

Abstract

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.
BibTeX
@inproceedings{mertikopoulos2019learning,
  author = {Panayotis Mertikopoulos and Zhengyuan Zhou},
  title = {{Learning in games with continuous action sets and unknown payoff functions}},
  booktitle = {Math. Program},
  year = {2019},
  url = {https://openreview.net/forum?id=asXLI1hE7Fn},
}
Figure