Convergence of Learning Dynamics in Stackelberg Games

By Tanner Fiez, Benjamin J. Chasnov, Lillian J. Ratliff. 2019

98 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Statistics and Probability

Citations in the corpus

Continual Learning of Control Primitives: Skill Discovery via Reset-Games (2020, background): “Since the reset game corresponds to a Stackelberg game, gradients-based learning algorithms with respect to these objectives exist that have finite time high probability bounds for local convergence in the case of non zero-sum objectives [15].”
What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization? (2019, background): “The definition in Fiez et al. (2019) implicitly assumes that the best response r : X → Y is well-defined by implicit equation ∇yf(x, r(x)) = 0, and g(x) := f(x, r(x)) is differentiable with respect to x, conditions which do not always hold even if f is infinitely differentiable.”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, methodology): “Even though some remedies have been advocated [312, 321, 322, 311] to stabilize the convergence in general continuous games, these assumptions are not easily verified/satisfied in MARL, e.”
Minimax Theorem for Latent Games or: How I Learned to Stop Worrying about Mixed-Nash and Love Neural Nets (2020, unknown): “Recently, Fiez et al. (2019) and Jin et al. (2019) proved results on games where the goal is to ﬁnd a Stackelberg equilibrium.”
A Game Theoretic Framework for Model Based Reinforcement Learning (2020, background): “In such cases, the standard notion of Stackelberg equilibrium is to optimize under the worst case realization (Fiez et al., 2019), which results in:”
On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach (2019, methodology): “Similarly, one can deﬁne local Stackelberg equilibrium as a generalization of local minimax in general-sum games (Fiez et al., 2019).”