Convergence of Learning Dynamics in Stackelberg Games

Abstract

This paper investigates the convergence of learning dynamics in Stackelberg games. In the class of games we consider, there is a hierarchical game being played between a leader and a follower with continuous action spaces. We establish a number of connections between the Nash and Stackelberg equilibrium concepts and characterize conditions under which attracting critical points of simultaneous gradient descent are Stackelberg equilibria in zero-sum games. Moreover, we show that the only stable critical points of the Stackelberg gradient dynamics are Stackelberg equilibria in zero-sum games. Using this insight, we develop a gradient-based update for the leader while the follower employs a best response strategy for which each stable critical point is guaranteed to be a Stackelberg equilibrium in zero-sum games. As a result, the learning rule provably converges to a Stackelberg equilibria given an initialization in the region of attraction of a stable critical point. We then consider a follower employing a gradient-play update rule instead of a best response strategy and propose a two-timescale algorithm with similar asymptotic convergence guarantees. For this algorithm, we also provide finite-time high probability bounds for local convergence to a neighborhood of a stable Stackelberg equilibrium in general-sum games. Finally, we present extensive numerical results that validate our theory, provide insights into the optimization landscape of generative adversarial networks, and demonstrate that the learning dynamics we propose can effectively train generative adversarial networks.

arXiv commentThis version includes numerical results training generative adversarial networks

References in corpus (15)

• Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks
• GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium
• Which Training Methods for GANs do actually Converge?
• Unrolled Generative Adversarial Networks
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• The Numerics of GANs
• Honeycombs and sums of Hermitian matrices
• The Mechanics of n-Player Differentiable Games
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• A Closer Look at the Optimization Landscapes of Generative Adversarial Networks
• Towards a Better Understanding and Regularization of GAN Training Dynamics
• On a class of non-Hermitian matrices with positive definite Schur complements

Cited by in corpus (23)

• Game-Theoretic Multiagent Reinforcement Learning
• A review of Generative Adversarial Networks for Electronic Health Records: applications, evaluation measures and data sources
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• A Game Theoretic Framework for Model Based Reinforcement Learning
• GANs May Have No Nash Equilibria
• On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach
• Implicit competitive regularization in GANs
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets
• Training Generative Adversarial Networks by Solving Ordinary Differential Equations
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
• Newton-type Methods for Minimax Optimization
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games
• On the Suboptimality of Negative Momentum for Minimax Optimization
• Delta-STN: Efficient Bilevel Optimization for Neural Networks using Structured Response Jacobians
• A mean-field analysis of two-player zero-sum games
• Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale Separation
• Train simultaneously, generalize better: Stability of gradient-based minimax learners
• Optimality and Stability in Non-Convex Smooth Games
• On Characterizing GAN Convergence Through Proximal Duality Gap
• RotoGrad: Gradient Homogenization in Multitask Learning
• A Limited-Capacity Minimax Theorem for Non-Convex Games or: How I Learned to Stop Worrying about Mixed-Nash and Love Neural Nets
• Adversarial Monte Carlo Meta-Learning of Optimal Prediction Procedures
• ADDS: Adaptive Differentiable Sampling for Robust Multi-Party Learning