mlsanityData to 14 Oct 2026

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

arXiv 2207.08426 ↗First posted 18 Jul 2022cs.GT cs.LG cs.MAcited by 4

Not on the map. Why?

Abstract (arXiv)

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 (EFGs) 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 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.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 17 of its 39 references that are in the map. First posted on arXiv 18 Jul 2022.

Builds on

17 of 39 references.

References · 17

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2017DeepStack: Expert-Level Artificial Intelligence in No-Limit Pokercited by 233
  3. 2017Training GANs with Optimismcited by 217
  4. 2017Cycles in adversarial regularized learningcited by 124
  5. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 98
  6. 2020Game-Theoretic Multiagent Reinforcement Learningcited by 94
  7. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 69
  8. 2020From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularizationcited by 61
  9. 2017Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaoscited by 29
  10. 2021Last-iterate Convergence in Extensive-Form Gamescited by 28
  11. 2019Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functionscited by 26
  12. 2013Graphical Models for Game Theorycited by 21
5 more
  1. 2020Exploration-Exploitation in Multi-Agent Learning: Catastrophe Theory Meets Game Theorycited by 17
  2. 2018Solving Large Sequential Games with the Excessive Gap Techniquecited by 16
  3. 2019Poincar'e Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Gamescited by 15
  4. 2019Multiagent Evaluation under Incomplete Informationcited by 13
  5. 2017Smoothing Method for Approximate Extensive-Form Perfect Equilibriumcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 0; 2025: 1; 2026: 1.

4 papers.

  1. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 10
  2. 2026Constant Individual Regret in General Gamescited by 3
  3. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  4. 2025Learnable Mixed Nash Equilibria are Collectively Rationalcited by 0