Fast convergence of optimistic gradient ascent in network zero-sum extensive form games

DOI10.1007/978-3-031-15714-1_22MaRDI QIDQ6164523zbMATH OpenOpenAlexFDO

Authors Georgios Piliouras, Lillian J. Ratliff, Ryann Sim, Stratis Skoulakis

Publication date 28 July 2023

Published in Algorithmic Game Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.08426

zbMATH Keywords

extensive form gamesnetwork zero-sum gamesonline learning in gamesoptimistic gradient ascent

Mathematics Subject Classification ID

2-person games (91A05) Noncooperative games (91A10) Games in extensive form (91A18) Games involving graphs (91A43)

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 (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$.

Recommendations

• scientific article; zbMATH DE number 1931819
• On the rate of convergence of fictitious play
• On the rate of convergence of fictitious play
• Best-response dynamics in zero-sum stochastic games
• Near-optimal no-regret algorithms for zero-sum games

Cites work

• Contributions to the theory of games. Vol. II
• Cycles in adversarial regularized learning
• Exploration-exploitation in multi-agent learning: catastrophe theory meets game theory
• Extensive Games
• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 3062455 (Why is no real title available?)
• Introduction to Online Convex Optimization
• Non-cooperative games
• On a Network Generalization of the Minmax Theorem
• On minmax theorems for multiplayer games
• Random extensive form games
• Smoothing techniques for computing Nash equilibria of sequential games
• Superhuman AI for heads-up no-limit poker: Libratus beats top professionals
• Zero-sum polymatrix games: a generalization of minmax

Cited in

(4)

• Analysis of Hannan consistent selection for Monte Carlo tree search in simultaneous move games
• scientific article; zbMATH DE number 1931819 (Why is no real title available?)
• Last-iterate convergence: zero-sum games and constrained min-max optimization
• Multiagent Online Learning in Time-Varying Games

This page was built for publication: Fast convergence of optimistic gradient ascent in network zero-sum extensive form games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6164523)