Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Games

Ryann Sim, Efstratios Panteleimon Skoulakis, Lillian J Ratliff, Georgios Piliouras

TL;DR

This paper introduces "Network Zero-Sum Extensive Form Games" (Network ZS-EFGs), a new class of games that models complex multi-agent interactions in scenarios like poker or resource allocation. They prove that a popular online learning algorithm, Optimistic Gradient Ascent (OGA), can efficiently find stable strategies (Nash Equilibria) in these games, both on average and for individual steps.

What Problem Does This Paper Address?

Game theory often studies simplified "normal form" games. However, real-world scenarios, like those in AI for games like Chess or Poker, or in economics, are better represented by "extensive form" games (EFGs). These games involve sequential decisions and evolving states. While learning algorithms for simple two-player EFGs are well-understood, extending this to multi-agent settings, especially those with complex network structures, has been a major challenge. This paper tackles this gap by introducing Network ZS-EFGs, which combine the structure of graphical games with the complexity of EFGs, and then analyzes the convergence properties of a learning algorithm within this new framework.

Methods

The core of the paper's contribution lies in its theoretical analysis of Optimistic Gradient Ascent (OGA) within Network ZS-EFGs. Key techniques include:

  • Formalizing Network ZS-EFGs: The authors define this new game class by building upon existing concepts of extensive form games and network games. This involves representing agents as nodes in a graph, with edges representing pairwise extensive form games.
  • Sequence Form Representation: They leverage the "sequence form" representation of extensive form games. This is a powerful technique that transforms complex game trees into a more manageable bilinear matrix form, allowing for the application of standard optimization tools.
  • Transformation to Symmetric Games: A crucial step is transforming the Network ZS-EFG into an equivalent two-player symmetric game. This transformation allows them to adapt existing theoretical results from simpler settings.
  • Optimistic Gradient Ascent (OGA): The paper analyzes OGA, a specific type of online learning algorithm known for its convergence guarantees. They show that OGA, when applied to the transformed symmetric game, leads to convergence to Nash Equilibria.
  • Convergence Analysis: Rigorous mathematical proofs are provided to establish both:
  • Time-average convergence: The average strategy of agents converges to a Nash Equilibrium at a rate of $O(1/T)$.
  • Last-iterate convergence (day-to-day): The strategy at each individual step converges to a Nash Equilibrium at an exponential rate of $O(c^{-t})$.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses simulated examples for experimental validation rather than pre-existing datasets.

Key Insights and Ideas

  • Bridging the Gap: The paper successfully bridges the gap between the well-studied two-player EFGs and the more complex, yet more realistic, multi-agent network EFGs.
  • Power of Sequence Form: The sequence form representation proves to be a critical tool for analyzing learning dynamics in complex EFGs, enabling the translation of game-theoretic problems into solvable optimization problems.
  • Symmetric Game Equivalence: The transformation to a symmetric game is a clever way to leverage existing theoretical machinery for convergence analysis, making the problem tractable.
  • OGA's Robustness: The paper demonstrates that OGA, a relatively simple yet effective online learning algorithm, exhibits strong convergence properties even in these complex, multi-agent network settings. This suggests its potential applicability in real-world AI systems.

Key Results

  • Theoretical Guarantees: The authors prove that for Network ZS-EFGs, Optimistic Gradient Ascent (OGA) guarantees:
  • Time-average convergence: The strategies of all agents converge to a Nash Equilibrium with a rate of $O(1/T)$.
  • Last-iterate convergence: The strategies of agents converge to a Nash Equilibrium at each step with a rate of $O(c^{-t})$, where $c$ is a game-dependent constant.
  • Experimental Validation: Simulations on various network games (Matching Pennies, random EFGs, Kuhn Poker) visually confirm the theoretical convergence rates, showing that OGA effectively finds stable strategies.

Limitations and Future Work

  • Computational Complexity: While the theoretical results are strong, the paper acknowledges that simulating larger games becomes computationally challenging, especially as the number of players and games increases. This is a practical limitation for applying these methods to very large-scale problems.
  • Game-Specific Constants: The convergence rates involve game-dependent constants, which can be difficult to determine in practice.
  • Future Directions: The authors express hope that this work will inspire further research into the practical and theoretical applications of online learning in network extensive form games. They highlight the need to bridge the gap between theoretical results and the challenges of modeling and simulating large-scale, real-world games.

Summary updated

Abstract

The study of learning in games has thus far focused primarily on normal form games. In contrast, our understanding of learning in extensive form games (EFG) and particularly in EFGs with many agents lags far behind, despite them being closer in nature to many real world applications. We consider the natural class of Network Zero-Sum Extensive Form Games, which combines the global zero-sum property of agent payoffs, the efficient representation of graphical games as well the expressive power of EFGs. We examine the convergence properties of Optimistic Gradient Ascent (OGA) in these games. We prove that the time-average behavior of such online learning dynamics exhibits $O(1/T)$ rate of convergence to the set of Nash equilibria. Moreover, we show that the day-to-day behavior also converges to Nash with rate $O(c^{-t})$ for some game-dependent constant $c > 0$.
BibTeX
@inproceedings{sim2022fast,
  author = {Ryann Sim and EFSTRATIOS PANTELEIMON SKOULAKIS and Lillian J Ratliff and Georgios Piliouras},
  title = {{Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Games}},
  booktitle = {SAGT},
  year = {2022},
  url = {https://openreview.net/forum?id=agKdNqT1d8},
}
Figure