Timezone: »
Poster
Alternating Mirror Descent for Constrained Min-Max Games
Andre Wibisono · Molei Tao · Georgios Piliouras
In this paper we study two-player bilinear zero-sum games with constrained strategy spaces. An instance of natural occurrences of such constraints is when mixed strategies are used, which correspond to a probability simplex constraint. We propose and analyze the alternating mirror descent algorithm, in which each player takes turns to take action following the mirror descent algorithm for constrained optimization. We interpret alternating mirror descent as an alternating discretization of a skew-gradient flow in the dual space, and use tools from convex optimization and modified energy function to establish an $O(K^{-2/3})$ bound on its average regret after $K$ iterations. This quantitatively verifies the algorithm's better behavior than the simultaneous version of mirror descent algorithm, which is known to diverge and yields an $O(K^{-1/2})$ average regret bound. In the special case of an unconstrained setting, our results recover the behavior of alternating gradient descent algorithm for zero-sum games which was studied in (Bailey et al., COLT 2020).
Author Information
Andre Wibisono (Yale University)
Molei Tao (Georgia Institute of Technology)
Georgios Piliouras (Singapore University of Technology and Design)
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 : Data-driven discovery of non-Newtonian astronomy via learning non-Euclidean Hamiltonian »
Oswin So · Gongjie Li · Evangelos Theodorou · Molei Tao -
2022 : Convergence in KL and Rényi Divergence of the Unadjusted Langevin Algorithm Using Estimated Score »
Kaylee Y. Yang · Andre Wibisono -
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 -
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 -
2021 Poster: Online Learning in Periodic Zero-Sum Games »
Tanner Fiez · Ryann Sim · Stratis Skoulakis · Georgios Piliouras · Lillian Ratliff -
2020 Poster: Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? --- A Neural Tangent Kernel Perspective »
Kaixuan Huang · Yuqing Wang · Molei Tao · Tuo Zhao -
2020 Poster: Stochasticity of Deterministic Gradient Descent: Large Learning Rate for Multiscale Objective Function »
Lingkai Kong · Molei Tao -
2019 Poster: First-order methods almost always avoid saddle points: The case of vanishing step-sizes »
Ioannis Panageas · Georgios Piliouras · Xiao Wang -
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