# Robust No-Regret Learning in Min-Max Stackelberg Games

arXiv: https://arxiv.org/abs/2203.14126 · HTML: https://mlsanity.com/paper/2203.14126/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 78 references that are in the map.
- First posted on arXiv 26 Mar 2022.

## Builds on (most cited first, 30 of 30)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Learning Adversarially Fair and Transferable Representations](https://mlsanity.com/paper/1802.06309/) (2018)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Censoring Representations with an Adversary](https://mlsanity.com/paper/1511.05897/) (2015)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization](https://mlsanity.com/paper/2011.00364/) (2020)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [On the Convergence and Robustness of Training GANs with Regularized Optimal Transport](https://mlsanity.com/paper/1802.08249/) (2018)
- [Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problems](https://mlsanity.com/paper/2002.07919/) (2020)
- [Fairness GAN](https://mlsanity.com/paper/1805.09910/) (2018)
- [Metric-Free Individual Fairness in Online Learning](https://mlsanity.com/paper/2002.05474/) (2020)
- [Last-iterate convergence rates for min-max optimization](https://mlsanity.com/paper/1906.02027/) (2019)
- [On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator](https://mlsanity.com/paper/1901.03674/) (2019)
- [Kernel Exponential Family Estimation via Doubly Dual Embedding](https://mlsanity.com/paper/1811.02228/) (2018)
- [A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization](https://mlsanity.com/paper/2003.04375/) (2020)
- [A Primal-Dual Algorithm with Line Search for General Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/1803.01401/) (2018)
- [Convex-Concave Min-Max Stackelberg Games](https://mlsanity.com/paper/2110.05192/) (2021)
- [Accelerated methods for composite non-bilinear saddle point problem](https://mlsanity.com/paper/1906.03620/) (2019)
- [Accelerated Stochastic Algorithms for Convex-Concave Saddle-Point Problems](https://mlsanity.com/paper/1903.01687/) (2019)
- [Linear Lower Bounds and Conditioning of Differentiable Games](https://mlsanity.com/paper/1906.07300/) (2019)
- [A Consumer-Theoretic Characterization of Fisher Market Equilibria](https://mlsanity.com/paper/2107.08153/) (2021)
- [Tracing Equilibrium in Dynamic Markets via Distributed Adaptation](https://mlsanity.com/paper/1804.08017/) (2018)

## Built on by (most cited first, 5 of 5)

- [Is Learning in Games Good for the Learners?](https://mlsanity.com/paper/2305.19496/) (2023)
- [Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactions](https://mlsanity.com/paper/2408.08272/) (2024)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [Learning to Play Against Unknown Opponents](https://mlsanity.com/paper/2412.18297/) (2024)
- [Decentralized Online Bandit Optimization on Directed Graphs with Regret Bounds](https://mlsanity.com/paper/2301.11802/) (2023)

## Abstract (arXiv)

The behavior of no-regret learning algorithms is well understood in two-player min-max (i.e, zero-sum) games. In this paper, we investigate the behavior of no-regret learning in min-max games with dependent strategy sets, where the strategy of the first player constrains the behavior of the second. Such games are best understood as sequential, i.e., min-max Stackelberg, games. We consider two settings, one in which only the first player chooses their actions using a no-regret algorithm while the second player best responds, and one in which both players use no-regret algorithms. For the former case, we show that no-regret dynamics converge to a Stackelberg equilibrium. For the latter case, we introduce a new type of regret, which we call Lagrangian regret, and show that if both players minimize their Lagrangian regrets, then play converges to a Stackelberg equilibrium. We then observe that online mirror descent (OMD) dynamics in these two settings correspond respectively to a known nested (i.e., sequential) gradient descent-ascent (GDA) algorithm and a new simultaneous GDA-like algorithm, thereby establishing convergence of these algorithms to Stackelberg equilibrium. Finally, we analyze the robustness of OMD dynamics to perturbations by investigating online min-max Stackelberg games. We prove that OMD dynamics are robust for a large class of online min-max games with independent strategy sets. In the dependent case, we demonstrate the robustness of OMD dynamics experimentally by simulating them in online Fisher markets, a canonical example of a min-max Stackelberg game with dependent strategy sets.