PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergence of Learning Dynamics in Stackelberg Games

Tanner Fiez, Benjamin Chasnov, Lillian J. Ratliff

arXiv:1906.01217v3cs.GTcs.LGcs.SYeess.SY

TL;DR

Hierarchical learning in Stackelberg games has lacked the convergence guarantees studied for simultaneous play. The paper develops learning rules that reflect leader-follower structure and connects Stackelberg and Nash equilibria. It establishes equilibrium guarantees for stable dynamics and reports GAN experiments in which the leader update avoids cycling.

  • Problem

    The paper addresses the limited convergence theory for learning dynamics in hierarchical Stackelberg games, a setting motivated by interacting agents with a distinct order of play.

    Source: §1 · pp. 1–2

  • Method

    The paper formulates gradient-based learning rules that mirror Stackelberg structure, including a leader update with a best-response follower and a two-timescale method with a gradient-play follower.

    Source: §1 · pp. 2–3

  • Results

    In zero-sum games, stable critical points of Stackelberg gradient dynamics are Stackelberg equilibria, and the best-response leader rule converges from their regions of attraction.

    Source: §1 · p. 3

  • Takeaways & Limitations

    In GAN experiments, the leader update removes rotational dynamics and prevents cycling, while non-Nash Stackelberg attractors show desirable generator and discriminator performance.

    Source: §1 · p. 3

    An extension of the result to arbitrary dimensions remains prospective; the authors suggest quadratic numerical range may help establish it.

    Source: §2.2.1 · p. 12

Abstract

from arXiv · show

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.

1. Introduction

Learning in games has largely focused on simultaneous play and Nash equilibria, while hierarchical Stackelberg learning lacks comparable convergence guarantees. The paper develops Stackelberg-structured learning rules, connects Stackelberg and Nash equilibria, and studies their convergence and GAN applications.

1. Introduction

  • The paper introduces a computable local differential Stackelberg equilibrium notion that generalizes local minimax equilibrium from zero-sum to general-sum games.Its learning rules are designed for continuous, general-sum games and reflect the leader-follower structure.Source: §1 · p. 2
  • Stable Nash equilibria are differential Stackelberg equilibria in zero-sum games, while simultaneous gradient play can also attract to non-Nash Stackelberg equilibria.The paper gives conditions for avoiding Nash equilibria and specializes some results to GANs under a realizable-generator assumption.Source: §1 · pp. 2–3
  • In zero-sum games, only stable critical points of Stackelberg gradient dynamics are Stackelberg equilibria, and the best-response leader rule converges from their attraction regions.The paper also gives a two-timescale method for a gradient-play follower, with asymptotic guarantees and finite-time local bounds in general-sum games.Source: §1 · p. 3
  • For a gradient-play follower, the proposed two-timescale algorithm converges almost surely to Stackelberg equilibria in zero-sum games and stable attractors in general-sum games.The paper also provides a finite-time high-probability bound for local convergence near a stable Stackelberg equilibrium in general-sum games.Source: §1 · p. 3
  • In GAN experiments, the leader update removes rotational dynamics and prevents cycling, while Stackelberg non-Nash attractors show desirable generator and discriminator performance.The paper also reports location and duopoly games that numerically validate the theory and demonstrate advantages of hierarchical over simultaneous play.Source: §1 · p. 3
  • Earlier machine-learning work on hierarchical decision-making focused on zero-sum games; time-scale-separated simultaneous gradient play is distinct from the proposed Stackelberg-structured dynamics.Related hierarchical approaches also appear in control and bilevel optimization.Source: §1 · pp. 3–4

2. Preliminaries

The preliminaries define hierarchical learning through response-aware leader updates and follower best responses, and relate learning dynamics to Stackelberg equilibria in zero-sum games. They also characterize when non-Nash attractors of simultaneous gradient play can be Stackelberg equilibria, connect hierarchical updates to opponent shaping, and compare leader costs at Nash and Stackelberg equilibria.

2.1 Stackelberg Games

  • A Stackelberg game has a leader who acts first and a follower who responds, with potentially noncooperative objectives; Nash and Stackelberg equilibria characterize simultaneous and hierarchical play, respectively.Both equilibrium notions can be characterized as intersections of players’ reaction curves.Source: §2 · p. 4, §2.1 · p. 5
  • The learning rule pairs the leader’s total derivative, accounting for the follower’s implicit best response, with the follower’s own gradient, using unbiased estimates and a slower leader timescale.The follower’s reaction curve is represented locally by an implicit map under regularity conditions.Source: §2.1 · pp. 5–6

2.2 Connections and Implications

  • The framework draws connections to adversarial learning and opponent shaping in multi-agent learning.The paper cites adversarial learning as an application where zero-sum abstractions are used to seek robust neural-network configurations.Source: §2.2 · p. 7

2.2.1 Implications for Zero-Sum Settings

  • In sufficiently smooth zero-sum games, every stable critical point of Stackelberg dynamics is a differential Stackelberg equilibrium.Stability is characterized by the Jacobian spectrum lying in the open right-half complex plane.Source: §2.2.1 · p. 8, §2.2 · p. 8
  • Unlike simultaneous gradient play, Stackelberg dynamics have no stable attractors outside the equilibrium concept; an example shows two non-Nash simultaneous attractors that are Stackelberg equilibria.The paper notes that such non-Nash attractors can occur in zero-sum games when the follower’s Hessian is positive definite.Source: §2.2.1 · pp. 8–9, Figure 1 · p. 10
  • Stable differential Nash equilibria in continuous zero-sum games are also differential Stackelberg equilibria.The paper establishes this using the positive-definite Schur complement at the critical point.Source: §2.2.1 · p. 9
  • Under the stated Hessian and cross-derivative structure, a non-Nash simultaneous-play attractor is a differential Stackelberg equilibrium and an attractor of Stackelberg dynamics.The sufficient conditions require Hermitian Hessians, −D2_2f(x*) > 0, aligned eigenvectors, and the stated spectral inequalities.Source: §2.2.1 · pp. 10–11
  • For sufficiently smooth scalar-action zero-sum games (f, −f) on R × R, with player 1 the leader and player 2 the follower, every non-Nash attracting critical point with −D2_2f(x*) > 0 is a differential Stackelberg equilibrium and an attractor of Stackelberg limiting dynamics.Source: §2.2.1 · p. 11
  • The paper’s analysis suggests some non-Nash attractors may have game-theoretic meaning as Stackelberg equilibria, a possibility relevant to GAN training.The paper notes prior work viewing non-Nash attractors as lacking game-theoretic meaning [37] and empirical GAN methods converging to such attractors [8].Source: §2.2.1 · p. 12
  • For realizable GANs, an attractor with −D2_2f positive semidefinite satisfies necessary local Stackelberg conditions and is marginally stable; stronger conditions make it a differential Stackelberg attractor.The sufficient case assumes negative follower curvature is positive definite and a nonzero diagonal cross-derivative structure.Source: §2.2.1 · pp. 12–13

2.2.2 Connections to Opponent Shaping

  • Unlike LOLA [21], whose attractors need not be Nash or Stackelberg equilibria, the paper analyzes a hierarchical update with convergence to Stackelberg equilibria under appropriate stepsizes and initialization.The implicit map in the update must be well-defined uniformly over the initialization region.Source: §2.2.2 · p. 13

2.2.3 Comparing Nash and Stackelberg Equilibrium Cost

  • With unique follower responses, the leader’s arbitrary Stackelberg equilibrium cost is no greater than the infimum of its Nash equilibrium costs [4], while the follower may prefer either outcome.The comparison applies to sufficiently smooth two-player general-sum games on continuous strategy spaces.Source: §2.2.3 · pp. 13–14

3. Convergence Analysis

This section analyzes convergence of leader–follower learning dynamics, including when leader updates and two-timescale play converge to Stackelberg solutions. Under stated assumptions, it gives high-probability lock-in guarantees near stable differential Stackelberg equilibria, first for the follower and then for both players.

3. Convergence Analysis

  • The analysis models players using noisy gradient estimates, with the leader responding to a conjectured follower reaction.The noise processes are conditionally mean-zero martingale differences.Source: §3 · p. 14

3.1 Learning Stackelberg Solutions for the Leader

  • With a locally optimal follower response, the leader’s update converges almost surely to a local Stackelberg solution; under additional conditions, the follower converges to its response.The result assumes a non-degenerate follower Hessian; convergence of both players also requires Assumptions 1 and 2.Source: §3.1 · p. 15

3.2 Learning Stackelberg Equilibria: Two-Timescale Analysis

  • When the leader’s learning rate is asymptotically smaller than the follower’s, the follower evolves on a faster timescale and the dynamics approximate the leader’s update against an equilibrated response.Stable attractors require the leader to be locally optimal along the follower-response manifold, not merely along the leader’s coordinate axis.Source: §3.2 · p. 16

3.2.1 Asymptotic Almost Sure Convergence

  • Under Assumptions 1–3 and timescale separation, the dynamics converge almost surely to a compact internally chain transitive set; with Assumption 3, they converge to a stable attractor.The stable attractors include stable differential Stackelberg equilibria.Source: §3.2.1 · pp. 16–17
  • In zero-sum games, the dynamics converge almost surely to a differential Stackelberg equilibrium, whereas in general-sum games stable non-Stackelberg equilibria can also attract.Thus, convergence alone does not guarantee a Stackelberg equilibrium outside the zero-sum setting.Source: §3.2.1 · pp. 16–17

3.2.2 Finite-Time High-Probability Guarantees

  • The finite-time analysis aims to give high-probability concentration and error bounds; it shows that the follower’s sample path tracks the leader’s conjectured response with high probability.The analysis uses an auxiliary response sequence and establishes asymptotic contraction of the tracking error.Source: §3.2.2 · pp. 17–18
  • The follower’s sample path asymptotically tracks the leader’s conjecture zk = r(x1,k) and, for ε ∈ [0, 1), gets locked into an ε-neighborhood with high probability, conditional on reaching Bq0(x*) by iteration n0.Source: §3.2.2 · p. 19
  • If γ2,n is sufficiently small and initialization satisfies x0 ∈ Bq0(x*), Corollary 6 guarantees that the follower locks into an ε-neighborhood with high probability, using n0 = 0.The corollary’s bound is the one in (11).Source: §3.2.2 · p. 19
  • Under the same assumptions and timescale condition, the joint iterate xk locks into an ε-neighborhood of a stable differential Stackelberg equilibrium with high probability after reaching Bq0(x*) by iteration n0.Theorem 2 gives the joint guarantee for any ε ∈ [0, 1).Source: §3.2.2 · p. 20
  • An analogous corollary gives the joint-iterate lock-in guarantee with n0 = 0.Source: §3.2.2 · p. 20

4. Numerical Examples

The examples illustrate convergence to Stackelberg equilibria in duopoly and location games, then test Stackelberg learning on covariance estimation and GAN training. Across GAN experiments, the dynamics can reach useful solutions, including non-Nash Stackelberg equilibria and realistic handwritten digits.

4.1 Stackelberg Duopoly

  • The two-timescale procedure converges to the Stackelberg equilibrium in the duopoly simulation, where the leader earns higher profit than under Nash.The reported equilibrium quantities are q*_S = (1048.2, 659.9); the passage also states that the leader's profit is higher under hierarchical than simultaneous play.Source: §4.1 · pp. 20–21, Figure 2 · p. 21

4.2 Location Game on Torus

  • With the selected torus-game parameters, both dynamics converge to stable equilibria, and the equilibrium reached depends on initialization.The order of play changes the leader's first-order condition and shifts equilibria away from Nash; the leader has lower cost at any equilibrium.Source: §4.2 · pp. 21–22, Figure 3 · p. 22

4.3 Generative Adversarial Networks

  • Across GAN experiments, Stackelberg learning reaches useful solutions, including non-Nash Stackelberg equilibria and realistic handwritten digits.The examples also report faster covariance estimation than simultaneous gradient descent and rapid convergence near the ground-truth distribution in a Gaussian-mixture experiment.Source: §4.3 · pp. 22, 23, 25
  • In covariance estimation, Stackelberg learning reaches equilibrium in fewer iterations than simultaneous gradient descent across the tested dimensions.The tested dimensions are 3, 9, and 25; simultaneous gradient descent exhibits cycling behavior.Source: §4.3 · p. 23, Figure 4 · p. 23
  • In Gaussian-mixture GAN examples, Stackelberg learning can reach a near-ground-truth distribution while simultaneous gradient descent cycles or performs poorly before learning rates decay.The examples report non-Nash Stackelberg equilibria; in another configuration, simultaneous gradient descent converges to Nash while Stackelberg learning converges to non-Nash Stackelberg.Source: Figure 5 · p. 23, §4.3 · pp. 24–25, Figure 6 · p. 24
  • On MNIST, Stackelberg dynamics generate realistic handwritten digits after 2,900 batches for both the 0-and-1 subset and the full dataset.The experiment is presented as evidence that the method's second-order information and inverse can be used with networks containing millions of parameters.Source: §4.3 · p. 25, Figure 7 · p. 25

5. Conclusion

The conclusion places the paper's convergence analysis in the comparatively less-studied setting of hierarchical play. It also notes connections to work on Nash learning; Appendix A supplies mathematical and dynamical-systems preliminaries.

5. Conclusion

  • The paper studies convergence of learning dynamics in Stackelberg games, a setting with ordered play that has received less analysis than simultaneous-play dynamics.It presents novel convergence results and connections to work on learning Nash equilibria.Source: §5 · p. 25
  • The conclusion connects the Stackelberg convergence results to existing work focused on learning Nash equilibria.Source: §5 · p. 25

Appendix A. Mathematical Preliminaries

  • Appendix A recalls linear-algebra and dynamical-systems results needed to state and prove the paper's main results.Source: Appendix A · p. 30

A.1 Proofs of Propositions 3 and 4

These appendices establish conditions linking stable attractors and differential Stackelberg equilibria, then recall tools used in the proofs and convergence analysis.

A.1 Proofs of Propositions 3 and 4

  • The proofs use block-operator and indefinite linear-algebra results to establish necessary and sufficient conditions connecting stable attractors with differential Stackelberg equilibria.The supplied proof passages include eigenvalue conditions for the Schur complement and a sufficient condition under which a stable non-Nash attractor is a differential Stackelberg equilibrium.Source: §A.1 · pp. 30–31

A.2 Dynamical Systems Theory Primer

  • The primer defines a (T, δ)-perturbation and states that sufficiently small such perturbations converge to an ε-neighborhood of the global attractor.Source: §A.2 · p. 31
  • The primer presents Alekseev's nonlinear variation-of-constants formula as a key tool for the finite-time two-timescale analysis.It notes that this approach has yielded tighter bounds than typical Bellman-Gronwall analyses.Source: §A.2 · pp. 31–32

Appendix B. Extended Analysis

The extended analysis tracks the follower and leader dynamics near a stable differential Stackelberg equilibrium and derives bounds used for high-probability local convergence guarantees.

Appendix B. Extended Analysis

  • Local Lyapunov functions and stability of the follower and leader linearized systems underpin the trajectory bounds near a stable differential Stackelberg equilibrium.The analysis assumes a local region around the equilibrium contained within its region of attraction.Source: Appendix B · p. 32
  • The analysis constructs an auxiliary sequence for the leader's conjecture of the follower response and shows that the follower dynamics track this belief with high probability.The argument uses interpolated trajectories, local stability, and bounds on their differences from continuous flows.Source: Appendix B · p. 34
  • The appendix derives bounds for both players' sample paths and uses them to obtain concentration bounds by combining interval-wise estimates.Source: Appendix B · pp. 35–36
  • The concentration analysis chooses sufficiently small follower step sizes and timescale ratios, then applies stochastic-approximation bounds to obtain the main theorems' results.The appendix says an analogous analysis yields the concentration bound for Theorem 2.Source: Appendix B · pp. 35–36

Appendix C. Regularizing the Follower’s Implicit Map

Appendix C regularizes the follower’s implicit response map in the leader’s update and derives a corresponding approximate Stackelberg update. It also gives necessary and sufficient conditions for regularized differential Stackelberg equilibria.

Appendix C. Regularizing the Follower’s Implicit Map

  • The leader’s update requires the follower Hessian to be an isomorphism, a condition that may fail along the learning path.Source: Appendix C · p. 36
  • The regularized update uses an inverse-Hessian regularization motivated by the leader’s uncertainty that a local linearization holds globally.Source: Appendix C · p. 36
  • The approximate Stackelberg update follows from a regularized model of the follower’s response and ignores higher-order terms in its derivative.Source: Appendix C · pp. 36–37
  • The GAN experiments use the regularized update because the discriminator’s Hessian can be ill-conditioned or degenerate.Source: Appendix C · p. 37
  • Propositions 10 and 11 give sufficient and necessary conditions, respectively, for regularized differential Stackelberg equilibria.The stated conditions involve first-order optimality and second-order curvature requirements.Source: Appendix C · p. 37

Appendix D. Experiment Details

Appendix D records the training-process details and selected hyperparameters for the mixture-of-Gaussians and MNIST experiments.

Appendix D. Experiment Details

  • The appendix provides training-process details and selected hyperparameters for the mixture-of-Gaussians and MNIST experiments.Source: Appendix D · p. 37

D.1 Mixture of Gaussians

The mixture-of-Gaussians experiments use distinct Gaussian data distributions for the diamond and circle settings. The appendix also specifies the GAN architectures, objectives, and optimizer settings used to train them.

D.1 Mixture of Gaussians

  • The diamond data distribution uses Gaussian components centered at μ = [1.5 sin(ω), 1.5 cos(ω)] with covariance 0.15I, sampled uniformly across components.Source: §D.1 · p. 37
  • The circle data distribution uses Gaussian components centered at μ = [sin(ω), cos(ω)] with covariance 0.3I, sampled uniformly across components.Source: §D.1 · p. 37
  • Both experiments use batches of 256; the generator has two 32-neuron hidden layers, while the discriminator has one 32-neuron hidden layer.Source: §D.1 · p. 37
  • The diamond experiment uses Tanh activations, the saturating GAN objective, and initial learning rates of 0.0001; the circle experiment uses ReLU, the non-saturating objective, and rates of 0.0004.Source: §D.1 · pp. 37–38
  • Both experiments use ADAM with β1 = 0.9, β2 = 0.999, and ϵ = 10^-8.Source: §D.1 · p. 38

D.2 MNIST

The MNIST experiments train DCGAN models on scaled 28 × 28 images using standard-normal latent vectors. The appendix specifies the optimization settings and the follower-map regularization.

D.2 MNIST

  • The experiments use MNIST digits 0 and 1 or each digit, scale images to [−1, 1], and sample real data sequentially from a shuffled dataset.Source: §D.2 · p. 38
  • The generator uses 100-dimensional standard-normal latent vectors, and the adapted DCGAN models train on batches of 256 with initial learning rates of 0.0002.Source: §D.2 · p. 38
  • The MNIST setup regularizes the follower’s implicit map with η = 5000; the paper says this is nearly equal to the mixture-of-Gaussians regularization when scaled by discriminator parameter count.Source: §D.2 · p. 38

Appendix E. Computing the Stackelberg Update and Schur Complement

The appendix constructs the operators needed for the leader update and Schur complement without forming full matrices. The inverse-Hessian solve is iterative, and its accuracy and convergence depend on the solver and conditioning.

Appendix E. Computing the Stackelberg Update and Schur Complement

  • Jacobian-vector products compute the four block operators of the simultaneous-gradient Jacobian, and linear-operator tools can inspect their eigenvalues.The blocks D_ij f_i are mapped from player j's action space to player i's.Source: Appendix E · p. 38
  • Conjugate gradient with at most five warm-started iterations worked for the tested mixture-of-Gaussians and MNIST GAN leader updates.The estimate was within numerical precision of the true-Hessian result on smaller problems; poorly conditioned Hessians can make some solvers fail to converge.Source: Appendix E · p. 39

Appendix F. N–Follower Setting

The appendix extends the framework to a single leader interacting with multiple noncooperative followers.

Appendix F. N–Follower Setting

  • The setting considered has one leader and N noncooperative followers.The passage states the extension without specifying further conditions or results.Source: Appendix F · p. 39

F.1 N + 1 Staggered Learners, All with Non-Uniform Learning Rates

The staggered-learner extension treats a layered hierarchy with increasingly faster learners. Its asymptotic analysis relies on additional assumptions about follower convergence and learning rates.

F.1 N + 1 Staggered Learners, All with Non-Uniform Learning Rates

  • A layered hierarchy can be analyzed under additional learning-rate assumptions.For three players, γ1,k = o(γ2,k) and γ2,k = o(γ3,k) make player 1 slowest and player 3 fastest.Source: §F.1 · p. 39
  • The analysis assumes follower dynamics converge asymptotically to Lipschitz continuous response functions.Assumptions 4 and 5 impose this property at successive levels of the hierarchy.Source: §F.1 · p. 39
  • The notation defines ξ≥2 from the two response functions and defines F3 and F2 using total derivatives.The notation Dj→i denotes the total derivative with respect to arguments j up to i.Source: §F.1 · p. 39
  • The appendix notes that a similar framework for reinforcement-learning algorithms in normal-form games exists.Source: §F.1 · p. 39

F.2 N Simultaneously Play Followers

The simultaneous-follower extension assumes a unique, uniformly stable differential Nash equilibrium for each leader action. Under that assumption, the main Section 3 results continue to hold.

F.2 N Simultaneously Play Followers

  • For every leader action, the follower game is assumed to have a globally asymptotically stable differential Nash equilibrium given by a Lipschitz response function.Source: §F.2 · p. 40
  • Under this assumption, all Section 3 results hold with Assumption 2 replaced, though the assumption is described as somewhat strong.N-player convex games that are diagonally strictly convex admit unique attracting Nash equilibria.Source: §F.2 · p. 40
Loading 1906.01217v3…