Timezone: »
A seminal result in game theory is von Neumann's minmax theorem, which states that zero-sum games admit an essentially unique equilibrium solution. Classical learning results build on this theorem to show that online no-regret dynamics converge to an equilibrium in a time-average sense in zero-sum games. In the past several years, a key research direction has focused on characterizing the transient behavior of such dynamics. General results in this direction show that broad classes of online learning dynamics are cyclic, and formally Poincar\'{e} recurrent, in zero-sum games. We analyze the robustness of these online learning behaviors in the case of periodic zero-sum games with a time-invariant equilibrium. This model generalizes the usual repeated game formulation while also being a realistic and natural model of a repeated competition between players that depends on exogenous environmental variations such as time-of-day effects, week-to-week trends, and seasonality. Interestingly, time-average convergence may fail even in the simplest such settings, in spite of the equilibrium being fixed. In contrast, using novel analysis methods, we show that Poincar\'{e} recurrence provably generalizes despite the complex, non-autonomous nature of these dynamical systems.
Author Information
Tanner Fiez (University of Washington)
Ryann Sim (Singapore University of Technology and Design)
Stratis Skoulakis (Singapore University of Technology and Design)
Georgios Piliouras (Singapore University of Technology and Design)
Lillian Ratliff (University of Washington)
More from the Same Authors
-
2021 Spotlight: Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationality »
Stefanos Leonardos · Georgios Piliouras · Kelly Spendlove -
2021 : Learning in Matrix Games can be Arbitrarily Complex »
Gabriel Andrade · Rafael Frongillo · Georgios Piliouras -
2021 : Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games »
Stefanos Leonardos · Will Overman · Ioannis Panageas · Georgios Piliouras -
2021 : Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationality »
Stefanos Leonardos · Kelly Spendlove · Georgios Piliouras -
2021 : Learning in Matrix Games can be Arbitrarily Complex »
Gabriel Andrade · Rafael Frongillo · Georgios Piliouras -
2021 : Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games »
Stefanos Leonardos · Will Overman · Ioannis Panageas · Georgios Piliouras -
2021 : Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationality »
Stefanos Leonardos · Kelly Spendlove · Georgios Piliouras -
2022 Poster: Alternating Mirror Descent for Constrained Min-Max Games »
Andre Wibisono · Molei Tao · Georgios Piliouras -
2022 Poster: Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update »
Georgios Piliouras · Ryann Sim · Stratis Skoulakis -
2022 Poster: Matrix Multiplicative Weights Updates in Quantum Zero-Sum Games: Conservation Laws & Recurrence »
Rahul Jain · Georgios Piliouras · Ryann Sim -
2022 Poster: Instance-optimal PAC Algorithms for Contextual Bandits »
Zhaoqi Li · Lillian Ratliff · houssam nassif · Kevin Jamieson · Lalit Jain -
2021 : Closing the loop in Machine Learning: Learning to optimize with decision dependent data »
Lillian Ratliff -
2021 Poster: Global Convergence to Local Minmax Equilibrium in Classes of Nonconvex Zero-Sum Games »
Tanner Fiez · Lillian Ratliff · Eric Mazumdar · Evan Faulkner · Adhyyan Narang -
2021 Poster: Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent »
Emmanouil-Vasileios Vlatakis-Gkaragkounis · Lampros Flokas · Georgios Piliouras -
2021 Poster: Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationality »
Stefanos Leonardos · Georgios Piliouras · Kelly Spendlove -
2020 Poster: Efficient Online Learning of Optimal Rankings: Dimensionality Reduction via Gradient Descent »
Dimitris Fotakis · Thanasis Lianeas · Georgios Piliouras · Stratis Skoulakis -
2019 : Contributed talk: Characterizing Equilibria in Stackelberg Games »
Tanner Fiez -
2019 Poster: First-order methods almost always avoid saddle points: The case of vanishing step-sizes »
Ioannis Panageas · Georgios Piliouras · Xiao Wang -
2019 Poster: Sequential Experimental Design for Transductive Linear Bandits »
Lalit Jain · Kevin Jamieson · Tanner Fiez · Lillian Ratliff -
2019 Poster: Multiagent Evaluation under Incomplete Information »
Mark Rowland · Shayegan Omidshafiei · Karl Tuyls · Julien Perolat · Michal Valko · Georgios Piliouras · Remi Munos -
2019 Spotlight: Multiagent Evaluation under Incomplete Information »
Mark Rowland · Shayegan Omidshafiei · Karl Tuyls · Julien Perolat · Michal Valko · Georgios Piliouras · Remi Munos -
2017 Poster: Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos »
Gerasimos Palaiopanos · Ioannis Panageas · Georgios Piliouras -
2017 Spotlight: Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos »
Gerasimos Palaiopanos · Ioannis Panageas · Georgios Piliouras