Convergence of Learning Dynamics in Stackelberg Games

Introduction

Tools from game theory now play a prominent role in machine learning. The emerging coupling between the fields can be credited to the formulation of learning problems as interactions between competing algorithms and the desire to characterize the limiting behaviors of such strategic interactions. Indeed, game theory provides a systematic framework to model the strategic interactions found in modern machine learning problems.

A significant portion of the game theory literature concerns games of simultaneous play and equilibrium analysis. In simultaneous play games, each player reveals the strategy they have selected concurrently. The solution concept often adopted in non-cooperative simultaneous play games is the Nash equilibrium. In a Nash equilibrium, the strategy of each player is a best response to the joint strategy of the competitors so that no player can benefit from unilaterally deviating from this strategy.

The study of equilibrium gives rise to the question of when and why the observed play in a game can be expected to correspond to an equilibrium. A common explanation is that an equilibrium emerges as the long run outcome of a process in which players repeatedly play a game and compete for optimality over time . Consequently, an important topic in the study of learning in games is the convergence behavior of learning algorithms reflecting the underlying game dynamics. Adopting this viewpoint and analyzing so-called ‘natural’ dynamics often provides deep insights into the structure of a game. Moreover, a firm understanding of the structure of a game can inform how to design learning algorithms strictly for computing equilibria. Seeking equilibria via computationally efficient learning algorithms is an equally important perspective on equilibrium analysis .

The classic objectives of learning in games are now being widely embraced in the machine learning community. While not encompassing, the prevailing research areas epitomizing this phenomenon are adversarial training and multi-agent learning. A considerable amount of this work has focused on generative adversarial networks (GANs) . Finding Nash equilibria in GANs is challenging owing to the complex optimization landscape that arises when each player in the game is parameterized by a neural network. Consequently, significant effort has been spent lately on developing principled learning dynamics for this application . In general, this line of work has analyzed learning dynamics designed to mitigate rotational dynamics and converge faster to stable fixed points or to avoid spurious stable points of the dynamics and reach equilibria almost surely. In our work, we draw connections to this literature and believe that the problem we study gives an under-explored perspective that may provide valuable insights moving forward.

Characterizing the outcomes of competitive interactions and seeking equilibria in multi-agent learning gained prominence much earlier than adversarial training. However, following initial works on this topic , scrutiny was given to the solution concepts being considered and the field cooled . Owing to the arising applications with interacting agents, problems of this form are being studied extensively again. There has been a shift toward analyzing gradient-based learning rules, in part due to their scalability and success in single-agent reinforcement learning, and rigorous convergence analysis .

The progress analyzing learning dynamics and seeking equilibria in games is promising, but the work has been narrowly focused on simultaneous play games and the Nash equilibrium solution concept. There are many problems exhibiting a hierarchical order of play between agents in a diverse set of fields such as human-robot collaboration and interacting autonomous systems in artificial intelligence , mechanism design and control , and organizational structures in economics . In game theory, this type of game is known as a Stackelberg game and the solution concept studied is called a Stackelberg equilibrium.

In the simplest formulation of a Stackelberg game, there is a leader and a follower that interact in a hierarchical structure. The sequential order of play is such that the leader is endowed with the power to select an action with the knowledge that the follower will then play a best-response. Specifically, the leader uses this knowledge to its advantage when selecting a strategy.

In this paper, we study the convergence of learning dynamics in Stackelberg games. Our motivation stems from the emergence of problems in which there is a distinct order of play between interacting learning agents and the lack of existing theoretical convergence guarantees in this domain. The dynamics analyzed in this work reflect the underlying game structure and characterize the expected outcomes of hierarchical game play. The rigorous study of the learning dynamics in Stackelberg games we provide also has implications for simultaneous play games relevant to adversarial training.

We formulate and study a novel set of gradient-based learning rules in continuous, general-sum games that emulate the natural structure of a Stackelberg game. Building on work characterizing a local Nash equilibrium in continuous games , we define the differential Stackelberg equilibrium solution concept (Definition 4), which is a local notion of a Stackelberg equilibrium amenable to computation. An analogous local minimax equilibrium concept was developed concurrently with this work, but strictly for zero-sum games . Importantly, the equilibrium notion we present generalizes the local minimax equilibrium concept to general-sum games. In our work, we draw several connections between Nash and Stackelberg equilibria for the class of zero-sum games, which can be summarized as follows:

We show in Proposition 2 that stable Nash equilibria are differential Stackelberg equilibria in zero-sum games. Concurrent with our work, Jin et al. equivalently show that local Nash equilibria are local minimax equilibria. This result indicates learning dynamics seeking Nash equilibria are simultaneously seeking Stackelberg equilibria.

We reveal that there exist stable attractors of simultaneous gradient play that are Stackelberg equilibria and not Nash equilibria. Moreover, in Propositions 3 and 4 we give necessary and sufficient conditions under which the simultaneous gradient play dynamics can avoid Nash equilibria and converge to Stackelberg equilibria. To demonstrate the relevancy to deep learning applications, Propositions 5 and 6 specialize the general necessary and sufficient conditions from Propositions 3 and 4 to GANs satisfying the realizable assumption , which presumes the generator is able to create the underlying data distribution. This set of results has implications for the optimization landscape in GANs as we explore in our numerical experiments.

Our primary contributions concern the convergence behavior of the gradient-based learning rules we formulate that mirror the Stackelberg game structure. These contributions can be summarized as follows:

We demonstrate in Proposition 1 that the only stable critical points of the Stackelberg gradient dynamics are Stackelberg equilibria in zero-sum games. This is in contrast to the simultaneous gradient play dynamics, which can be attracted to non-Nash critical points in zero-sum games. This insight allows us to define a gradient-based learning rule for the leader while the follower plays a best response for which each attracting critical point is a Stackelberg equilibria in zero-sum games. As a result, the learning rule provably converges to an equilibria given an initialization in the region of attraction of a stable critical point. A formal exposition of this set of dynamics and results is provided in Section 3.1.

Leveraging the Stackelberg game structure, for general-sum games, we formulate a gradient-based learning rule in which the leader and follower have an unbiased estimator of their gradient so that updates are stochastic.

In Section 3.2, we consider a formulation in which the follower uses a gradient-play update rule instead of an exact best response strategy and propose a two-timescale algorithm to learn Stackelberg equilibria. We show almost sure asymptotic convergence to Stackelberg equilibria in zero-sum games and to stable attractors in general-sum games; a finite-time high probability bound for local convergence to a neighborhood of a stable Stackelberg equilibrium in general-sum games is also given.

We present this paper with a single leader and a single follower, but this is only for ease of presentation. The extension to $N$ followers that play in a staggered hierarchical structure or simultaneously is in Appendix F; equivalent results hold with some additional assumptions.

Finally, we present several numerical experiments in Section 4, which we now detail:

We present a location game on a torus and a Stackelberg duopoly game. The examples are general-sum games with equilibrium that can be solved for directly, allowing us to numerically validate our theory. The games demonstrate the advantage the leader gains from the hierarchical order of play compared to the simultaneous play versions of the games.

We evaluate the Stackelberg learning dynamics as a GAN training algorithm. In doing so, we find that the leader update removes rotational dynamics and prevents the type of cycling behavior that plagues simultaneous gradient play. Moreover, we discover that the simultaneous gradient dynamics can empirically converge to non-Nash attractors that are Stackelberg equilibria in GANs. The generator and the discriminator exhibit desirable performance at such points, indicating that Stackelberg equilibria can be as desirable as Nash equilibria. Lastly, the Stackelberg learning dynamics often converge to non-Nash attractors and reach a satisfying solution quickly using learning rates that can cause the simultaneous gradient descent dynamics to cycle.

The perspective we explore on analyzing games in which there is an order of play or hierarchical decision making structure has been generally ignored in the modern learning literature. However, this viewpoint has long been researched in the control literature on games . Similarly, work on bilevel optimization adopts this perspective.

The select few recent works in the machine learning literature on learning in games considering a hierarchical decision-making structure exclusively focus on zero-sum games , unlike our work, which extends to general-sum games. A noteworthy paper in the line of work in the zero-sum setting adopting a min-max perspective was the introduction of unrolled GANs . The authors consider a timescale separation between the generator and discriminator, giving the generator the advantage as the slower player. This work used the Schur complement structure presented in Danskin to define a minimax solution of a zero-sum game abstraction of an adversarial training objective. Essentially the discriminator is allowed to perform a finite roll-out in an inner loop of the algorithm with multiple updates; this process is referred to as ‘unrolling’. It is (informally) suggested that, using the results of Danskin , as the roll-out horizon approaches infinity, the discriminator approaches a critical point of the cost function along the discriminators axis given a fixed generator parameter configuration.

The unrolling procedure has the same effect as a deterministic timescale separation between players. Formal convergence guarantees to minimax equilibria in zero-sum games characterizing the limiting behavior of simultaneous individual gradient descent with timescale separation were recently obtained . While related, simultaneous individual gradient play with time-scale separation is a distinct set of dynamics that departs from the dynamics we propose that reflect the Stackelberg game structure.

It is also worth pointing out that the multi-agent learning papers of Foerster et al. and Letcher et al. do in some sense seek to give a player an advantage, but nevertheless focus on the Nash equilibrium concept in any analysis that is provided.

In Section 2, we formalize the problem we study and provide background material on Stackelberg games. We then draw connections between learning in Stackelberg games and existing work in zero-sum and general sum-games relevant to GANs and multi-agent learning, respectively. In Section 3, we give a rigorous convergence analysis of learning in Stackelberg games. Numerical examples are provided in Section 4 and we conclude in Section 5.

Preliminaries

We leverage the rich theory of continuous games and dynamical systems in order to analyze algorithms implemented by agents interacting in a hierarchical game. In particular, each agent has an objective they want to selfishly optimize that depends on not only their own actions but also on the actions of their competitor. However, there is an order of play in the sense that one player is the leader and the other player is the followerWhile we present the work for a single leader and a single follower, the theory extends to the multi-follower case (we discuss this in Appendix F) and to the case where the single leader abstracts multiple cooperating agents.. The leader optimizes its objective with the knowledge that the follower will respond by selecting a best response. We refer to algorithms for learning in this setting as hierarchical learning algorithms. We specifically consider a class of learning algorithms in which the agents act myopically with respect to their given objective and role in the underlying hierarchical game by following the gradient of their objective with respect to their choice variable.

The leader aims to solve the optimization problem given by

and the follower aims to solve the optimization problem $\min_{x_{2}\in X_{2}}f_{2}(x_{1},x_{2})$. As noted above, the learning algorithms we study are such that the agents follow myopic update rules which take steps in the direction of steepest descent with respect to the above two optimizations problems, the former for the leader and the latter for the follower.

Before formalizing these updates, let us first discuss the equilibrium concept studied for simultaneous play games and contrast it with that which is studied in the hierarchical play counterpart. The typical equilibrium notion in continuous games is the pure strategy Nash equilibrium in simultaneous play games and the Stackelberg equilibrium in hierarchical play games. Each notion of equilibria can be characterized as the intersection points of the reaction curves of the players .

The joint strategy $x^{\ast}\in X$ is a Nash equilibrium if for each $i\in\mathcal{I}$,

The strategy is a local Nash equilibrium on $W\subset X$ if for each $i\in\mathcal{I}$,

In a two-player game with player 1 as the leader, a strategy $x_{1}^{\ast}\in X_{1}$ is called a Stackelberg equilibrium strategy for the leader if

where $\mathcal{R}(x_{1})=\{y\in X_{2}|\ f_{2}(x_{1},y)\leq f_{2}(x_{1},x_{2}),\forall x_{2}\in X_{2}\}$ is the rational reaction set of $x_{2}$.

This definition naturally extends to the $n$-follower setting when $\mathcal{R}(x_{1})$ is replaced with the set of Nash equilibria $\text{\tt NE}(x_{1})$, given that player 1 is playing $x_{1}$ so that the follower’s reaction set is a Nash equilibrium.

We denote $D_{i}f_{i}$ as the derivative of $f_{i}$ with respect to $x_{i}$, $D_{ij}f_{i}$ as the partial derivative of $D_{i}f_{i}$ with respect to $x_{j}$, and $D(\cdot)$ as the total derivativeFor example, given a function $f(x,r(x))$, $Df=D_{1}f+D_{2}f\partial r/\partial x$.. Denote by $\omega(x)=(D_{1}f_{1}(x),D_{2}f_{2}(x))$ the vector of individual gradients for simultaneous play and $\omega_{\mathcal{S}}(x)=(Df_{1}(x),D_{2}f_{2}(x))$ as the equivalent for hierarchical play where $Df_{1}$ is the total derivative of $f_{1}$ with respect to $x_{1}$ and $x_{2}$ is implicitly a function of $x_{2}$, which captures the fact that the leader operates under the assumption that the follower will play a best response to its choice of $x_{1}$.

It is possible to characterize a local Nash equilibrium using sufficient conditions for Definition 1.

The joint strategy $x^{\ast}\in X$ is a differential Nash equilibrium if $\omega(x^{\ast})=0$ and $D_{i}^{2}f_{i}(x^{\ast})>0$ for each $i\in\mathcal{I}$.

Analogous sufficient conditions can be stated to characterize a local Stackelberg equilibrium strategy for the leader using first and second order conditions on the leader’s optimization problem. Indeed, if $Df_{1}(x_{1}^{\ast},r(x_{1}^{\ast}))=0$ and $D^{2}f_{1}(x_{1}^{\ast},r(x_{1}^{\ast}))$ is positive definite, then $x_{1}^{\ast}$ is a local Stackelberg equilibrium strategy for the leader. We use these sufficient conditions to define the following refinement of the Stackelberg equilibrium concept.

The pair $(x_{1}^{\ast},x_{2}^{\ast})\in X$ with $x_{2}^{\ast}=r(x_{1}^{\ast})$, where $r$ is implicitly defined by $D_{2}f_{2}(x_{1}^{\ast},x_{2}^{\ast})=0$, is a differential Stackelberg equilibrium for the game $(f_{1},f_{2})$ with player 1 as the leader if $Df_{1}(x_{1}^{\ast},r(x_{1}^{\ast}))=0$, and $D^{2}f_{1}(x_{1}^{\ast},r(x_{1}^{\ast}))$ is positive definite..

Before moving on, let us make a few remarks about similar, and in some cases analogous, equilibrium definitions. For zero-sum games, the differential Stackelberg equilibrium notion is the same as a local min-max equilibrium for a sufficiently smooth cost function $f$. This is a well-known concept in optimization (see, e.g., , among others), and it has recently been introduced in the learning literature . The benefit of the Stackelberg perspective is that it generalizes from zero-sum games to general-sum games, while the min-max equilibrium notion does not. A number of adversarial learning formulations are in fact general-sum, often as a result of regularization and well-performing heuristics that augment the cost functions of the generator or the discriminator.

We utilize these local characterizations in terms of first and second order conditions to formulate the myopic hierarchical learning algorithms we study. Following the preceding discussion, consider the learning rule for each player to be given by

recalling that $\omega_{\mathcal{S}}=(Df_{1}(x),D_{2}f_{2}(x))$ and the notation $\omega_{\mathcal{S},i}$ indicates the entry of $\omega_{\mathcal{S}}$ corresponding to the $i$–th player. Moreover, $\{\gamma_{i,k}\}$ the sequence of learning rates and $\{w_{i,k}\}$ is the noise process for player $i$, both of which satisfy the usual assumptions from theory of stochastic approximation provided in detail in Section 3. We note that the component of the update $\omega_{\mathcal{S},i}(x_{k})+w_{i,k+1}$ captures the case in which each agent does not have oracle access to $\omega_{\mathcal{S},i}$, but instead has an unbiased estimator for it. The given update formalizes the class of learning algorithms we study in this paper.

We require a timescale separation between the leader and the follower: the leader is assumed to be learning at a slower rate than the follower so that $\gamma_{1,k}=o(\gamma_{2,k})$. The reason for this timescale separation is that the leader’s update is formulated using the reaction curve of the follower. In the gradient-based learning setting considered, the reaction curve can be characterized by the set of critical points of $f_{2}(x_{1,k},\cdot)$ that have a local positive definite structure in the direction of $x_{2}$, which is

This set can be characterized in terms of an implicit map $r$, defined by the leader’s belief that the follower is playing a best response to its choice at each iteration, which would imply $D_{2}f_{2}(x_{1,k},x_{2,k})=0$. Moreover, under sufficient regularity conditions, the implicit mapping theorem gives rise to the implicit map $r:U\rightarrow X_{2}:x_{1}\mapsto x_{2}$ on a neighborhood $U\subset X_{1}$ of $x_{1,k}$. Formalized in Section 3, we note that when $r$ is defined uniformly in $x_{1}$ on the domain for which convergence is being assessed, the update in (1) is well-defined in the sense that the component of the derivative $Df_{1}$ corresponding to the implicit dependence of the follower’s action on $x_{1}$ via $r$ is well-defined and locally consistent. In particular, for a given point $x=(x_{1},x_{2})$ such that $D_{2}f_{2}(x_{1},x_{2})=0$ with $D_{2}^{2}f_{2}(x)$ an isomorphism, the implicit function theorem implies there exists an open set $U\subset X_{1}$ such that there exists a unique continuously differentiable function $r:U\rightarrow X_{2}$ such that $r(x_{1})=x_{2}$ and $D_{2}f_{2}(x_{1},r(x_{1}))=0$ for all $x_{1}\in U$. Moreover,

on $U$. Thus, in the limit of the two-timescale setting, the leader sees the follower as having equilibriated (meaning $D_{2}f_{2}\equiv 0$) so that

The map $r$ is an implicit representation of the follower’s reaction curve.

The following describes the general approach to studying the hierarchical learning dynamics in (1). The purpose of this overview is to provide the reader with the high-level architecture of the analysis approach.

The analysis techniques we employ combine tools from dynamical systems theory with the theory of stochastic approximation. In particular, we leverage the limiting continuous time dynamical systems derived from (1) to characterize concentration bounds for iterates or samples generated by (1). We note that the hierarchical learning update in (1) with timescale separation $\gamma_{1,k}=o(\gamma_{2,k})$ has a limiting dynamical system that takes the form of a singularly perturbed dynamical system given by

which, in the limit as $\tau\rightarrow 0$, approximates (1).

The limiting dynamical system has known convergence properties (asymptotic convergence in a region of attraction for a locally asymptotically stable attractor). Such convergence properties can be translated in some sense to the discrete time system by comparing pseudo-trajectories—in this case, linear interpolations between sample points of the update process—generated by sample points of (1) and the limiting system flow for initializations containing the set of sample points of (1). Indeed, the limiting dynamical system is then used to generate flows initialized from the sample points generated by (1). Creating pseudo-trajectories, we then bound the probability that the pseudo-trajectories deviate by some small amount from the limiting dynamical system flow over each continuous time interval between the sample points. A concentration bound can be constructed by taking a union bound over each time interval after a finite time; following this we can guarantee the sample path has entered the region of attraction, on which we can produce a Lyapunov function for the continuous time dynamical system. The analysis in this paper is based on the high-level ideas outlined in this section.

2 Connections and Implications

Before presenting convergence analysis of the update in (1), we draw some connections to application domains—including adversarial learning, where zero-sum game abstractions have been touted for finding robust parameter configurations for neural networks, and opponent shaping in multi-agent learning—and equilibrium concepts commonly used in these domains. Let us first remind the reader of some common definitions from dynamical systems theory.

Further, $x^{\ast}$ is said to be asymptotically stable if $x^{\ast}$ is additionally attractive—that is, for all $t_{0}\geq 0$, there exists $\delta(t_{0})$ such that

A critical point is said to be non-degenerate if the determinant of the Jacobian of the dynamics at the critical point is non-zero. For a non-degenerate critical point, the Hartman-Grobman theorem enables us to check the eigenvalues of the Jacobian to determine asymptotic stability. In particular, at a non-degenerate critical point, if the eigenvalues of the Jacobian are in the open left-half complex plane, then the critical point is asymptotically stable. The dynamical systems we study in this paper are of the form $\dot{x}=-F(x)$ for some vector field $F$ determined by the gradient based update rules employed by the agents. Hence, to determine if a critical point is stable, we simply need to check that the spectrum of the Jacobian of $F$ is in the open right-half complex plane.

Zero-sum games are a very special class since there is a strong connection between Nash equilibria and Stackelberg equilibria. Let us first show that for zero-sum games, attracting critical points of $\dot{x}=-\omega_{\mathcal{S}}(x)$ are differential Stackelberg equilibria.

Proof. Consider an arbitrary sufficiently smooth zero-sum game $(f,-f)$ on continuous strategy spaces. The Jacobian of the Stackelberg limiting dynamics $\dot{x}=-\omega_{\mathcal{S}}(x)$ at a stable critical point is $x^{\ast}$

The structure of the Jacobian $J_{\mathcal{S}}(x^{\ast})$ follows from the fact that

The eigenvalues of a lower triangular block matrix are the union of the eigenvalues in each of the block diagonal components. This implies that if $J_{\mathcal{S}}(x^{\ast})>0$, then necessarily $D_{1}(Df)(x^{\ast})>0$ and $-D_{2}^{2}f(x^{\ast})>0$. Consequently, any stable critical point of the Stackelberg limiting dynamics must be a differential Stackelberg equilibrium by definition. The result of Proposition 1 implies that with appropriately chosen stepsizes the only attracting critical points of the update rule in (1) will be Stackelberg equilibria and thus, unlike simultaneous play individual gradient descent (known as gradient-play in the game theory literature), will not converge to spurious locally asymptotically stable attractors of the dynamics that are not relevant to the underlying game.

In a recent work on GANs , hierarchical learning of a similar nature proposed in this paper is studied in the context of zero-sum games. In the author’s formulation, the generator is deemed the leader and the discriminator as the follower. The idea is to allow the discriminator to take $k$ individual gradient steps to update its parameters, while the parameters of the generator are held fixed. The effect of ‘unrolling’ the discriminator update for $k$ steps is that a surrogate objective of $f(x_{1},r_{2}(x_{1}))$ arises for the generator, meaning that the timescale-separation between the discriminator and the follower induces an update reminiscent of that given for the leader in (2). In particular, when $k\rightarrow\infty$ the follower converges to a local optimum as a function of the generator’s parameters so that $D_{2}f(x_{1},x_{2})\rightarrow 0$. As a result, the critical points coincide with the Stackelberg dynamics we study, indicating that unrolled GANs are converging only to Stackelberg equilibria. Empirically, GANs learned with such timescale separation procedures seem to outperform gradient descent with uniform stepsizes , providing evidence Stackelberg equilibria can be sufficient in GANs.

This begs a further question of if attractors of the dynamics $\dot{x}=-\omega(x)$ are Stackelberg equilibria. We begin to answer this inquiry by showing that stable differential Nash are differential Stackelberg equilibria.

Proof. Consider an arbitrary sufficiently smooth zero-sum game $(f,-f)$ on continuous strategy spaces. Suppose $x^{\ast}$ is a stable differential Nash equilibrium so that by definition $D_{1}^{2}f(x^{\ast})>0$, $-D_{2}^{2}f(x^{\ast})>0$, and

Then, the Schur complement of $J(x^{\ast})$ is also positive definite:

Hence, $x^{\ast}$ is a differential Stackelberg equilibrium since the Schur complement of $J$ is exactly the derivative $D^{2}f$ at critical points and $-D_{2}^{2}f(x^{\ast})>0$ since $x$ is a differential Nash equilibrium.

In the zero-sum setting, the fact that Nash equilibria are a subset of Stackelberg equilibria (or minimax equilibria) for finite games is well-known . We show the result for the notion of differential Stackelberg equilibria for continuous action space games that we introduce. Similar to our work and concurrently, Jin et al. also show that local Nash equilibria are local minmax solutions for continuous zero-sum games. It is interesting to point out that for a subclass of zero-sum continuous games with a convex-concave structure for the leader’s cost the set of (differential) Nash and (differential) Stackelberg equilibria coincide. Indeed, $D_{1}^{2}f(x)>0$ at critical points for convex-concave games, so that if $x$ is a differential Stackelberg equilibrium, it is also a Nash equilibrium.

This result indicates that recent works seeking Nash equilibria in GANs are seeking Stackelberg equilibria concurrently. Given that it is well-known simultaneous gradient play can converge to attracting critical points that do not satisfy the conditions of a Nash equilibria, it remains to determine when such spurious non-Nash attractors of the dynamics $\dot{x}=-\omega(x)$ will be an attractor of the Stackelberg dynamics $\dot{x}=-\omega_{\mathcal{S}}(x)$.

Let player $1$ be the leader who aims to minimize $f$ with respect to $x_{1}$ taking into consideration that player 2 (follower) aims to minimize $-f$ with respect to $x_{2}$. In Fig. 1, we show the trajectories for various initializations for this game with $(a,b)=(0.15,0.25)$; it can be seen that for several initializations, simultaneous gradient play leads to non-Nash attractors which are differential Stackelberg equilibria.

We now proceed to provide necessary and sufficient conditions for the phenenom demonstrated in Example 1. Attracting critical points $x^{\ast}$ of the dynamics $\dot{x}=-\omega(x)$ that are not Nash equilibria are such that either $D_{1}^{2}f(x^{\ast})$ or $-D_{2}^{2}f(x^{\ast})$ are not positive definite. Without loss of generality, considering player 1 to be the leader, an attractor of the Stackelberg dynamics $\dot{x}=-\omega_{\mathcal{S}}(x)$ requires both $-D_{2}^{2}f(x^{\ast})$ and $D_{1}^{2}f(x^{\ast})-D_{21}f(x^{\ast})^{\top}(D_{2}^{2}f(x^{\ast}))^{-1}D_{21}f(x^{\ast})$ to be positive definite. Hence, if $-D_{2}^{2}f(x^{\ast})$ is not positive definite at a non-Nash attractor of $\dot{x}=-\omega(x)$, then $x^{\ast}$ will also not be an attractor of $\dot{x}=-\omega_{\mathcal{S}}(x)$. We focus on non-Nash attractors with $-D_{2}^{2}f(x^{\ast})>0$ and seek to determine when the Schur complement is positive definite, so that $x^{\ast}$ is an attractor of $\dot{x}=\omega_{\mathcal{S}}(x)$.

and define $p=\dim(\ker(D_{1}^{2}f(x^{\ast})))$.

Consider a non-Nash attracting critical point $x^{\ast}$ of the gradient dynamics $\dot{x}=-\omega(x)$ such that $-D_{2}^{2}f(x^{\ast})>0$. Given $\kappa>0$ such that $\|D_{21}f(x^{\ast})\|\leq\kappa$, if $D_{1}^{2}f(x^{\ast})-D_{21}f(x^{\ast})^{\top}(D_{2}^{2}f(x^{\ast}))^{-1}D_{21}f(x^{\ast})>0$, then $r\leq n$ and $\kappa^{2}\lambda_{i}+\mu_{i}>0$ for all $i\in\{1,\ldots,r-p\}$.

This means that $x^{\ast}$ does not satisfy the conditions for a differential Stackelberg, however, the point does satisfy necessary conditions for a local Stackelberg equilibrium and the point is a marginally stable attractor of the dynamics.

While the results depend on conditions that are difficult to check a priori without knowledge of $x^{\ast}$, certain classes of games for which these conditions hold everywhere and not just at the equilibrium can be constructed. For instance, alternative conditions can be given: if the function $f$ which defines the zero-sum game is such that it is concave in $x_{2}$ and there exists a $K$ such that

where $\sup_{x}\|D_{12}f(x)\|\leq\kappa<\infty$Functions such that derivative of $f$ is Lipschitz will satisfy this condition. and $K=W_{1}\Sigma W_{2}^{\ast}$ with $\Sigma$ again a (not necessarily positive) diagonal matrix, then the results of Proposition 4 hold. From a control point of view, one can think about the leader’s update as having a feedback term with the follower’s input. On the other hand, the results are useful for the synthesis of games, such as in reward shaping or incentive design, where the goal is to drive agents to particular desirable behavior.

We remark that the fact that the eigenvalues of $J(x^{\ast})$ are in the open-right-half complex plane is not used in proving this result. We believe that further investigation could lead to a less restrictive sufficient condition. Empirically, by randomly generating the different block matrices, it is quite difficult to find examples such that $J(x^{\ast})$ has positive eigenvalues, $-D_{2}^{2}f(x^{\ast})>0$, and the Schur complement $D_{1}^{2}f(x^{\ast})-D_{21}f(x^{\ast})^{\top}(D_{2}^{2}f(x^{\ast}))^{-1}D_{21}f(x^{\ast})$ is not positive definite. In fact, for games on scalar action spaces, it turns out that non-Nash attracting critical points of the simultaneous gradient play dynamics at which $-D_{2}^{2}f(x^{\ast})>0$ must be differential Stackelberg equilibria and attractors of the Stackelberg limiting dynamics.

The fact that the real components of the eigenvalues of the Jacobian are positive implies that $D_{12}f(x^{\ast})D_{21}f(x^{\ast})>D_{1}^{2}f(x^{\ast})D_{2}^{2}f(x^{\ast})$ and $D_{1}^{2}f(x^{\ast})>D_{2}^{2}f(x^{\ast})$ since the determinant and the trace of the Jacobian must be positive. Using this information, it directly follows that the Schur complement of $J(x^{\ast})$ is positive definite:

As a result, $x^{\ast}$ is a differential Stackelberg equilibrium and an attractor of $\dot{x}=-\omega_{\mathcal{S}}(x)$ since the Schur complement of $J(x^{\ast})$ is the derivative $D^{2}f(x^{\ast})$ and $-D_{2}^{2}f(x)>0$ was given. We suspect that using the notion of quadratic numerical range , which is a super set of the spectrum of a block operator matrix, along with the fact that the Jacobian of the simultaneous gradient play dynamics has its spectrum in the open right-half complex plane, may lead to an extension of the result to arbitrary dimensions.

The results of Propositions 3 and 4, Corollary 1, and Example 1 imply that some of the non-Nash attractors of $\dot{x}=-\omega(x)$ are in fact Stackelberg equilibria. This is a meaningful insight since recent works have proposed schemes to avoid non-Nash attractors of the dynamics as they have been classified or viewed as lacking game-theoretic meaning . Moreover, some recent empirical results show that a number of successful approaches to training GANs are not converging to Nash equilibria, but rather to non-Nash attractors of the dynamics . It would be interesting to characterize whether or not the attractors satisfy the conditions we propose, and if such conditions could provide insights into how to improve GAN training. It also further suggests that the Stackelberg equilibria may be a suitable solution concept for GANs.

One of the common assumptions in some of the recent GANs literature is that the discriminator network is zero in a neighborhood of an equilibrium parameter configuration (see, e.g., ). This assumption limits the theory to the ‘realizable’ case; the work by provides relaxed assumptions for the non-realizable case. In both cases, the Jacobian for the dynamics $\dot{x}=-\omega(x)$ is such that $D_{1}^{2}f(x^{\ast})=0$.

Consider a GAN satisfying the realizable assumption—that is, the discriminator network is zero in a neighborhood of any equilibrium. Then, an attracting critical point for the simultaneous gradient dynamics $\dot{x}=-\omega(x)$ at which $-D_{2}^{2}f$ is positive semi-definite satisfies necessary conditions for a local Stackelberg equilibrium, and it will be a marginally stable point of the Stackelberg dynamics $\dot{x}=-\omega_{\mathcal{S}}(x)$.

Proof. Consider an attracting critical point $x$ of $\dot{x}=-\omega(x)$ such that $-D_{2}^{2}f(x^{\ast})\geq 0$. Note that the realizable assumption implies that the Jacobian of $\omega$ is

(see, e.g., ). Hence, since $-D_{2}^{2}f(x^{\ast})\geq 0$,

Since $x^{\ast}$ is an attractor, $D_{1}f(x^{\ast})=0$ and $D_{2}f(x^{\ast})=0$ so that

Consequently, the necessary conditions for a local Stackelberg equilibrium are satisfied. Moreover, since both $-D_{2}^{2}f(x^{\ast})\geq 0$ and the Schur complement $-D_{21}^{\top}f(x^{\ast})(D_{2}^{2})^{-1}f(x^{\ast})D_{21}f(x^{\ast})\geq 0$, the Jacobian of $\omega_{\mathcal{S}}$ is positive semi-definite so that the point $x^{\ast}$ is marginally stable.

Now, simply satisfying the necessary conditions is not enough to guarantee that attractors of the simultaneous play gradient dynamics will be a local Stackelberg equilibrium. We can state sufficient conditions by examining Proposition 4.

Consider a GAN satisfying the realizable assumption—that is, the discriminator network is zero in a neighborhood of any equilibrium—and an attractor for the simultaneous gradient dynamics $\dot{x}=-\omega(x)$ at which $-D_{2}^{2}f$ is positive definite. Suppose that there exists a diagonal matrix $\Sigma$ with non-zero entries such that $D_{12}f(x^{\ast})=\Sigma W$ where $W$ are the orthonormal eigenvectors of $-D_{2}^{2}f(x^{\ast})$. Then, $x^{\ast}$ is a differential Stackelberg equilibrium and an attractor of $\dot{x}=-\omega_{\mathcal{S}}(x)$.

The proof follows directly from Proposition 4 and Proposition 5. It is not directly clear how restrictive these sufficient conditions are for GANs. We leave this for future inquiry.

2.2 Connections to Opponent Shaping

Beyond the work in zero-sum games and applications to GANs, there has also been recent work, which we will refer to as ‘opponent shaping’, where one or more players takes into account its opponents’ response to their action . The initial work of Foerster et al. bears the most resemblance to the learning algorithms studied in this paper. The update rule (LOLA) considered there (in the deterministic setting with constant stepsizes) takes the following form:

The attractors of these dynamics are not necessarily Nash equilibria nor are they Stackelberg equilibria as can be seen by looking at the critical points of the dynamics. Indeed, the LOLA dynamics lead only to Nash or non-Nash stable attractors of the limiting dynamics. The effect of the additional ‘look-ahead’ term is simply that it changes the vector field and region of attraction for stable critical points. In the zero-sum case, however, the critical points of the above are the same as those of simultaneous play individual gradient updates, yet the Jacobian is not the same and it is still possible to converge to a non-Nash attractor.

With a few modifications, the above update rule can be massaged into a form which more closely resembles the hierarchical learning rules we study in this paper. In particular, if instead of $\gamma_{2}$, player 2 employed a Newton stepsize of $(D_{2}^{2}f_{2})^{-1}$, then the update would look like

which resembles a deterministic version of (1). The critical points of this update coincide with the critical points of a Stackelberg game $(f_{1},f_{2})$. With appropriately chosen stepsizes and with an initialization in a region on which the implicit map, which defines the $-(D_{2}^{2}f_{2}(x))^{-1}D_{21}f_{2}(x)$ component of the update, is well-defined uniformly in $x_{1}$, the above dynamics will converge to Stackelberg equilibria. In this paper, we provide an in-depth convergence analysis and for the stochastic settingIn , the authors do not provide convergence analysis; they do in their extension, yet only for constant and uniform stepsizes and for a learning rule that is different than the one studied in this paper as all players are conjecturing about the behavior of their opponents. This distinguishes the present work from their setting. of the above update.

2.3 Comparing Nash and Stackelberg Equilibrium Cost

We have alluded to the idea that the ability to act first gives the leader a distinct advantage over the follower in a hierarchical game. We now formalize this statement with a known result that compares the cost of the leader at Nash and Stackelberg equilibrium.

([4, Proposition 4.4]). Consider an arbitrary sufficiently smooth two-player general-sum game $(f_{1},f_{2})$ on continuous strategy spaces. Let $f_{1}^{\mathcal{N}}$ denote the infimum of all Nash equilibrium costs for player 1 and $f_{1}^{\mathcal{S}}$ denote an arbitrary Stackelberg equilibrium cost for player 1. Then, if $\mathcal{R}(x_{1})$ is a singleton for every $x_{1}\in X_{1}$, $f_{1}^{\mathcal{S}}\leq f_{1}^{\mathcal{N}}$.

This result says that the leader never favors the simultaneous play game over the hierarchical play game in two-player general-sum games with unique follower responses. On the other hand, the follower may or may not prefer the simultaneous play game over the hierarchical play game.

The fact that under certain conditions the leader can obtain lower cost under a Stackelberg equilibrium compared to any of the Nash equilibrium may provide further explanation for the success of the methods in . Commonly, the discriminator can overpower the generator when training a GAN and giving the generator an advantage may mitigate this problem. In the context of multi-agent learning, the advantage of the leader in hierarchical games leads to the question of how the roles of each player in a game are decided. While we do not focus on this question, it is worth noting that when each player mutually benefits from the leadership of a player the solution is called concurrent and when each player prefers to be the leader the solution is called non-concurrent. We believe that exploring classes of games in which each solution concept arises is an interesting direction of future work.

Convergence Analysis

Following the preceding discussion, consider the learning rule for each player to be given by

where recall that $\omega_{\mathcal{S}}=(Df_{1}(x),D_{2}f_{2}(x))$. Moreover, for each $i\in\mathcal{I}$, $\{\gamma_{i,k}\}$ is the sequence of learning rates and $\{w_{i,k}\}$ is the noise process for player $i$. As before, suppose player 1 is the leader and conjectures that player 2 updates its action $x_{2}$ in each round via $r(x_{1})$. This setting captures the scenario in which players do not have oracle access to their gradients, but do have an unbiased estimator. As an example, players could be performing policy gradient reinforcement learning or alternative gradient-based learning schemes. Let $\dim(X_{i})=d_{i}$ for each $i\in\mathcal{I}$ and $d=d_{1}+d_{2}$.

For each $i\in\mathcal{I}$, the learning rates satisfy $\sum_{k}\gamma_{i,k}=\infty$, $\sum_{k}\gamma_{i,k}^{2}<\infty$.

A nonempty invariant set $A\subset X$ for $\xi$ is said to be internally chain transitive if for any $a,b\in A$ and $\delta>0$, $T>0$, there exists a finite sequence $\{x_{1}=a,x_{2},\ldots,x_{k-1},x_{k}=b;t_{1},\ldots,t_{k-1}\}$ with $x_{i}\in A$ and $t_{i}\geq T$, $1\leq i\leq k-1$, such that $\rho(\xi_{t_{i}}(x_{i}),x_{i+1})<\delta$, $\forall 1\leq i\leq k-1$.

Suppose that the leader (player 1) operates under the assumption that the follower (player 2) is playing a local optimum in each round. That is, given $x_{1,k}$, $x_{2,k+1}\in\arg\min_{x_{2}}f_{2}(x_{1,k},x_{2})$ for which $D_{2}f_{2}(x_{1,k},x_{2})=0$ is a first-order local optimality condition. If, for a given $(x_{1},x_{2})\in X_{1}\times X_{2}$, $D_{2}^{2}f_{2}(x_{1},x_{2})$ is invertible and $D_{2}f_{2}(x_{1},x_{2})=0$, then the implicit function theorem implies that there exists neighborhoods $U\subset X_{1}$ and $V\subset X_{2}$ and a smooth map $r:U\rightarrow V$ such that $r(x_{1})=x_{2}$.

where $x_{2,k}$ is defined via the map $r_{2}$ defined implicitly in a neighborhood of $(x_{1,k},x_{2,k})$.

Suppose that for each $x\in X$, $D_{2}^{2}f_{2}$ is non-degenerate and Assumption 1 holds for $i=1$. Then, $x_{1,k}$ converges almost surely to an (possibly sample path dependent) equilibrium point $x_{1}^{\ast}$ which is a local Stackelberg solution for the leader. Moreover, if Assumption 1 holds for $i=2$ and Assumption 2 holds, then $x_{2,k}\rightarrow x_{2}^{\ast}=r(x_{1}^{\ast})$ so that $(x_{1}^{\ast},x_{2}^{\ast})$ is a differential Stackelberg equilibrium.

Proof. This proof follows primarily from using known stochastic approximation results. The update rule in (7) is a stochastic approximation of $\dot{x}_{1}=-Df_{1}(x_{1},x_{2})$ and consequently is expected to track this ODE asymptotically. The main idea behind the analysis is to construct a continuous interpolated trajectory $\bar{x}(t)$ for $t\geq 0$ and show it asymptotically almost surely approaches the solution set to the ODE. Under Assumptions 1–3, results from [11, §2.1] imply that the sequence generated from (7) converges almost surely to a compact internally chain transitive set of $\dot{x}_{1}=-Df_{1}(x_{1},x_{2})$. Furthermore, it can be observed that the only internally chain transitive invariant sets of the dynamics are differential Stackelberg equilibria since at any stable attractor of the dynamics $D^{2}f_{1}(x_{1},r(x_{1}))>0$ and from assumption $D_{2}^{2}f_{2}(x_{1},r(x_{1}))>0$. Finally, from [11, §2.2], we can conclude that the update from (7) almost surely converges to a possibly sample path dependent equilibrium point since the only internally chain transitive invariant sets for $\dot{x}_{1}=-Df_{1}(x_{1},x_{2})$ are equilibria. The final claim that $x_{2,k}\to r(x_{1}^{\ast})$ is guaranteed since $r$ is Lipschitz and $x_{1,k}\to x_{1}^{\ast}$.

The above result can be stated with a relaxed version of Assumption 2.

Given a differential Stackelberg equilibrium $x^{\ast}=(x_{1}^{\ast},x_{2}^{\ast})$, let $B_{q}(x^{\ast})=B_{q_{1}}(x_{1}^{\ast})\times B_{q_{2}}(x_{2}^{\ast})$ for some $q_{1},q_{2}>0$ on which $D_{2}^{2}f_{2}$ is non-degenerate. Suppose that Assumption 1 holds for $i=1$ and that $x_{1,0}\in B_{q_{1}}(x_{1}^{\ast})$. Then, $x_{1,k}$ converges almost surely to $x_{1}^{\ast}$. Moreover, if Assumption 1 holds for $i=2$, $r(x_{1})$ is a locally asymptotically stable equilibrium uniformly in $x_{1}$ on the ball $B_{q_{2}}(x_{2}^{\ast})$, and $x_{2,0}\in B_{q_{2}}(x_{2}^{\ast})$, then $x_{2,k}\rightarrow x_{2}^{\ast}=r(x_{1}^{\ast})$.

The proof follows the same arguments as the proof of Proposition 8.

2 Learning Stackelberg Equilibria: Two-Timescale Analysis

where $Df_{1}(x)=D_{1}f_{1}(x)+D_{2}f_{1}(x)Dr(x_{1})$. Suppose that $\gamma_{1,k}\rightarrow 0$ faster than $\gamma_{2,k}$ so that in the limit $\tau\rightarrow 0$, the above approximates the singularly perturbed system defined by

The learning rates can be seen as stepsizes in a discretization scheme for solving the above dynamics. The condition that $\gamma_{1,k}=o(\gamma_{2,k})$ induces a timescale separation in which $x_{2}$ evolves on a faster timescale than $x_{1}$. That is, the fast transient player is the follower and the slow component is the leader since $\lim_{k\rightarrow\infty}\gamma_{1,k}/\gamma_{2,k}=0$ implies that from the perspective of the follower, $x_{1}$ appears quasi-static and from the perspective of the leader, $x_{2}$ appears to have equilibriated, meaning $D_{2}f_{2}(x_{1},x_{2})=0$ given $x_{1}$. From this point of view, the learning dynamics (8)–(9) approximate the dynamics in the preceding section. Moreover, stable attractors of the dynamics are such that the leader is at a local optima for $f_{1}$, not just along its coordinate axis but in both coordinates $(x_{1},x_{2})$ constrained to the manifold $r(x_{1})$; this is to make a distinction between differential Nash equilibria in agents are at local optima aligned with their individual coordinate axes.

The following two results are fairly classical results in stochastic approximation. They are leveraged here to making conclusions about convergence to Stackelberg equilibria in hierarchical learning settings.

While we do not need the following assumption for all the results in this section, it is required for asymptotic convergence of the two-timescale process in (8)–(9).

The dynamics $\dot{x}_{1}=-Df_{1}(x_{1},r(x_{1}))$ have a globally asymptotically stable equilibrium.

Under Assumption 1–3, and the assumption that $\gamma_{1,k}=o(\gamma_{2,k})$, classical results imply that the dynamics (8)–(9) converge almost surely to a compact internally chain transitive set $\mathcal{T}$ of (10); see, e.g., [11, §6.1-2], [10, §3.3]. Furthermore, it is straightforward to see that stable differential Nash equilibria are internally chain transitive sets since they are stable attractors of the dynamics $\dot{\xi}_{t}=F(\xi_{t})$ from (10).

There are two important points to remark on at this juncture. First, the flow of the dynamics (10) is not necessarily a gradient flow, meaning that the dynamics may admit non-equilibrium attractors such as periodic orbits. The dynamics correspond to a gradient vector field if and only if $D_{2}(Df_{1})\equiv D_{12}f_{2}$, meaning when the dynamics admit a potential function. Equilibria may also not be isolated unless the Jacobian of $\omega_{\mathcal{S}}$, say $J_{\mathcal{S}}$, is non-degenerate at the points. Second, except in the case of zero-sum settings in which $(f_{1},f_{2})=(f,-f)$, non-Stackelberg locally asymptotically stable equilibria are attractors. That is, convergence does not imply that the players have settled on a Stackelberg equilibrium, and this can occur even if the dynamics admit a potential.

Let $t_{k}=\sum_{l=0}^{k-1}\gamma_{1,l}$ be the (continuous) time accumulated after $k$ samples of the slow component $x_{1}$. Define $\xi_{1,s}(t)$ to be the flow of $\dot{x}_{1}=-Df_{1}(x_{1}(t),r(x_{1}(t)))$ starting at time $s$ from intialization $x_{s}$.

Suppose that Assumptions 1 and 2 hold. Then, conditioning on the event $\{\sup_{k}\sum_{i}\|x_{i,k}\|^{2}<\infty\}$, for any integer $K>0$, $\lim_{k\rightarrow\infty}\sup_{0\leq h\leq K}\|x_{1,k+h}-\xi_{1,t_{k}}(t_{k+h})\|_{2}=0$ almost surely.

Now, by Assumption 1, $Df_{1}$ is Lipschitz and bounded (in fact, independent of A1a., since $Df_{1}\in C^{q}$, $q\geq 2$, it is locally Lipschtiz and, on the event $\{\sup_{k}\sum_{i}\|x_{i,k}\|_{2}<\infty\}$, it is bounded). In turn, it induces a continuous globally integrable vector field, and therefore satisfies the assumptions of Benaïm [6, Prop. 4.1]. Moreover, under Assumptions A1b. and A1c., the assumptions of Benaïm [6, Prop. 4.2] are satisfied, which gives the desired result.

Under Assumption 3 and the assumptions of Proposition 9, $(x_{1,k},x_{2,k})\rightarrow(x_{1}^{\ast},r(x_{1}^{\ast}))$ almost surely conditioned on the event $\textstyle\{\sup_{k}\sum_{i}\|x_{i,k}\|^{2}<\infty\}$. That is, the learning dynamics (8)–(9) converge to stable attractors of (10), the set of which includes the stable differential Stackelberg equilibria.

Proof. Continuing with the conclusion of the proof of Proposition 9, on intervals $[t_{k},t_{k+1}]$ the norm difference between interpolates of the sample path and the trajectories of $\dot{x}_{1}=-Df_{1}(x_{1},r(x_{1}))$ vanish asymptotically; applying Lemma 4 (Appendix A) gives the result. Leveraging the results in Section 2.2.1, the convergence guarantees are stronger since in zero-sum settings all attractors are Stackelberg; this contrasts with the Nash equilibrium concept.

Consider a zero-sum setting $(f,-f)$. Under the assumptions of Proposition 9 and Assumption 3, conditioning on the event $\{\sup_{k}\sum_{i}\|x_{i,k}\|^{2}<\infty\}$, the learning dynamics (8)–(9) converge to a differential Stackelberg equilibria almost surely.

The proof of this corollary follows the above analysis and invokes Proposition 1. As with Corollary 2, we can relax Assumption 2 and 3 to local asymptomatic stability assumptions and obtain similarity convergence guarantees.

Given a differential Stackelberg equilibrium $x^{\ast}=(x_{1}^{\ast},x_{2}^{\ast})$ where $x_{2}^{\ast}=r(x_{1}^{\ast})$, let $B_{q}(x^{\ast})=B_{q_{1}}(x_{1}^{\ast})\times B_{q_{2}}(x_{2}^{\ast})$ for some $q_{1},q_{2}>0$ on which $D_{2}^{2}f_{2}$ is non-degenerate. Suppose that Assumption 1 holds for each player, $r(x_{1})$ is a locally asymptotically stable attractor uniformly in $x_{1}$ on the ball $B_{q_{2}}(x_{2}^{\ast})$ for the dynamics $\dot{x}_{2}=-D_{2}f_{2}(x)$, and there exists a locally asymptotically stable attractor on $B_{q_{1}}(x_{1})$ for the dynamics $\dot{x}_{1}=-Df_{1}(x_{1},r(x_{1}))$. Then, given an initialization $x_{1,0}\in B_{q_{1}}(x_{1}^{\ast})$ and $x_{2,0}\in B_{q_{2}}(x_{2}^{\ast})$, it follows that $(x_{1,k},x_{2,k})\rightarrow(x_{1}^{\ast},x_{2}^{\ast})$ almost surely.

2.2 Finite-Time High-Probability Guarantees

While asymptotic guarantees of the proceeding section are useful, high-probability finite-time guarantees can be leveraged more directly in analysis and synthesis, e.g., of mechanisms to coordinate otherwise autonomous agents. In this section, we aim to provide concentration bounds for the purpose of deriving convergence rate and error bounds in support of this objective. The results in this section follow the very recent work by Borkar and Pattathil . We highlight key differences and, in particular, where the analysis may lead to insights relevant for learning in hierarchical decision problems between non-cooperative agents.

The basic idea of the proof is to leverage Alekseev’s formula (Thm. 3, Appendix A) to bound the difference between the asymptotic pseudo-trajectories and the flow of the corresponding limiting differential equation on each continuous time interval between each of the successive iterates $k$ and $k+1$ by sequences of constants that decay asymptotically. Then, a union bound is used over all time intervals after defined for $n\geq n_{0}$ in order to construct a concentration bound. This is done first for the follower, showing that $x_{2,k}$ tracks the leader’s ’conjecture’ or belief $r(x_{1,k})$ about the follower’s reaction, and then for the leader.

where $x_{1}(t)\equiv x_{1}$ is constant (since $\dot{x}_{1}=0$), $x_{2}(t)=r(x_{1})$, and

In addition, for $t\geq s$, $\Phi_{2}(\cdot)$ satisfies linear system

with $\Phi_{2}(t,s,x_{0})=I$ and $x_{0}=(x_{1,0},x_{2,0})$ and where $J_{2}$ the Jacobian of $-D_{2}f_{2}(x_{1},\cdot)$. We provide more detail on this derivation in Appendix B.

Given that $x^{\ast}=(x_{1}^{\ast},r(x_{1}^{\ast}))$ is a stable differential Stackelberg equilibrium, $J_{2}(x^{\ast})$ is positive definite. Hence, as in [57, Lem. 5.3], we can find $M$, $\kappa_{2}>0$ such that for $t\geq s$, $x_{2,0}\in V^{q}$, $\|\Phi_{2}(t,s,x_{1,0},x_{2,0})\|\leq Me^{-\kappa_{2}(t-s)}$; this result follows from standard results on stability of linear systems (see, e.g., Callier and Desoer [14, §7.2, Thm. 33]) along with a bound on

Now, an interesting point worth making is that this analysis leads to a very nice result for the leader-follower setting. In particular, through the use of the auxiliary variable $z$, we can show that the follower’s sample path ‘tracks’ the leader’s conjectured sample path. Indeed, consider $z_{k}=r(x_{1,k})$, that is, where $D_{2}f_{2}(x_{1,k},x_{2,k})=0$. Then, using a Taylor expansion of the implicitly defined conjecture $r$, we get $z_{k+1}=z_{k}+Dr(x_{1,k})(x_{1,k+1}-x_{1,k})+\delta_{k+1}$ where $\|\delta_{k+1}\|\leq L_{r}\|x_{1,k+1}-x_{1,k}\|^{2}$ is the error from the remainder terms. Plugging in $x_{1,k+1}$,

The terms after $-D_{2}f_{2}$ are $o(1)$, and hence asymptotically negligible, so that this $z$ sequence tracks dynamics as $x_{2,k}$. We show that with high probability, they asymptotically contract, leading to the conclusion that the follower’s dynamics track the leader’s conjecture.

Towards this end, we first bound the normed difference between $x_{2,k}$ and $z_{k}$. Define constants

and let $\tau_{k}=\gamma_{1,k}/\gamma_{2,k}$.

For any $n\geq n_{0}$, there exists $K>0$ such that conditioned on ${\mathcal{E}}_{n}$,

Suppose that Assumptions 1, 2, and 3 hold and let $\gamma_{1,k}=o(\gamma_{2,k})$. Given a stable differential Stackelberg equilibrium $x^{\ast}=(x_{1}^{\ast},r(x_{1}^{\ast}))$, the follower’s sample path generated by (9) with asymptotically track the leader’s conjecture $z_{k}=r(x_{1,k})$ and, given $\varepsilon\in[0,1)$, will get ‘locked in’ to a $\varepsilon$–neighborhood with high probability conditioned on reaching $B_{q_{0}}(x^{\ast})$ by iteration $n_{0}$. That is, letting $\bar{n}=n_{0}+T+1$, for some $C_{1},C_{2},C_{3},C_{4}>0$,

with $\beta_{n}=\textstyle\max_{n_{0}\leq k\leq n-1}e^{-\kappa_{2}(\sum_{i=k+1}^{n-1}\gamma_{2,i})}\gamma_{2,k}$.

The key technique in proving the above theorem (which is done in detail in Borkar and Pattathil using results from Thoppe and Borkar ), is taking a union bound of the errors over all the continuous time intervals defined for $n\geq n_{0}$.

The above theorem can be restated to give a guarantee on getting locked-in to an $\varepsilon$-neighborhood of a stable differenital Stackelberg equilibria $x^{\ast}$ if the learning processes are initialized in $B_{q_{0}}(x^{\ast})$.

Given that the follower’s action $x_{2,k}$ tracks $r(x_{1,k})$, we can also show that $x_{1,k}$ gets locked into an $\varepsilon$–neighborhood of $x_{1}^{\ast}$ after a finite time with high probability. First, a similar bound as in Lemma 1 can be constructed for $x_{1,k}$.

Define the event $\hat{\mathcal{E}}_{n}=\{\bar{x}_{1}(t)\in V^{q}\ \forall t\in[\hat{t}_{n_{0}},\hat{t}_{n}]\}$ where for each $t$, $\bar{x}_{1}(t)=x_{1,k}+\frac{t-\hat{t}_{k}}{\gamma_{1,k}}(x_{1,k+1}-x_{1,k})$ is a linear interpolates between the samples $\{x_{1,k}\}$, $\hat{t}_{k+1}=\hat{t}_{k}+\gamma_{1,k}$, and $\hat{t}_{0}=0$. Then as above, Alekseev’s formula can again be applied to get

and $\Phi_{1}$ is the solution to a linear system with dynamics $J_{1}(x_{1}^{\ast},r(x_{1}^{\ast}))$, the Jacobian of $-Df_{1}(\cdot,r(\cdot))$, and with initial data $\Phi_{1}(s,s,x_{1,0})=I$. This linear system, as above, has bound $\|\Phi_{1}(t,s,x_{1,0})\|\leq M_{1}e^{\kappa_{1}(t-1)}$ for some $M_{1},\kappa_{1}>0$. Define $S_{1,n}=\sum_{k=n_{0}}^{n-1}\int_{\hat{t}_{k}}^{\hat{t}_{k+1}}\Phi_{1}(\hat{t}_{n},s,\bar{x}_{1}(\hat{t}_{k}))ds\cdot w_{1,k+1}$.

with \eta_{n}=\max_{n_{0}\leq k\leq n-1}\big{(}e^{-\kappa_{1}(\sum_{i=k+1}^{n-1}\gamma_{1,i})}\gamma_{1,k}\big{)}.

An analogous corollary to Corollary 6 can be stated for $x_{1,k}$ with $n_{0}=0$.

Numerical Examples

In this section, we present and extensive set of numerical examples to validate our theory and demonstrate that the learning dynamics in this paper can effectively train GANsCode is available at github.com/fiezt/Stackelberg-Code..

In Cournot’s duopoly model a single good is produced by two firms so that the industry is a duopoly. The cost for firm $i=1,2$ for producing $q_{i}$ units of the good is given by $c_{i}q_{i}$ where $c_{i}>0$ is the unit cost. The total output of the firms is $Q=q_{1}+q_{2}$. The market price is $P=A-Q$ when $A\geq Q$ and $P=0$ when $A<Q$. We can assume that $A>c_{i}$ for $i=1,2$. The profit of each firm is $\pi_{i}=Pq_{i}-c_{i}q_{i}=(A-q_{i}-q_{-i}-c_{i})q_{i}$. Moreover, the unique Nash equilibrium in the game is $q_{i}^{\ast}=\frac{1}{3}(A+c_{-i}-2c_{i})$ so that the market price is $P^{\ast}=\frac{1}{3}(A+c_{i}+c_{-i})$ and each firm obtains a profit of $\pi_{i}^{\ast}=\frac{1}{9}(A-2c_{i}+c_{-i})^{2}$.

In the Stackelberg duopoly model with two firms, there is a leader and a follower. The leader moves and then the follower produces a best response to the action of the leader. Knowing this, the leader seeks to maximize profit taking advantage of the power to move before the follower. The unique Stackelberg equilibrium in the game is $q_{1}^{\ast}=\frac{1}{2}(A+c_{2}-2c_{1})$, $q_{2}^{\ast}=\frac{1}{4}(A+2c_{1}-3c_{2})$. In equilibrium the market price is $P^{\ast}=\frac{1}{4}(A+2c_{1}+c_{2})$, the profit of the leader is $\pi_{1}^{\ast}=\frac{1}{8}(A-2c_{1}+c_{2})^{2}$, and the profit of the follower is $\pi_{2}^{\ast}=\frac{1}{16}(A+2c_{1}-3c_{2})^{2}$.

The key point we want to highlight is that in this game, firm 1’s (leader) profit is always higher in the hierarchical play game than the simultaneous play game. We also use it as a simple validation example for our theory. For this problem, we simulate the Nash gradient dynamics and our two-timescale algorithm for learning Stackelberg equilibria to illustrate the distinctions between the Cournot and Stackelberg duopoly models. In this simulation, we select a decaying step-size of $\gamma_{i,k}=1/k$ for each player in the Nash gradient dynamics. The decaying step-size is chosen to be $\gamma_{1,k}=1/k$ for the leader and $\gamma_{2,k}=1/k^{2/3}$ for the follower in the Stackelberg two-timescale algorithm so that the leader moves on a slower timescale than the follower as required. The noise at each update step is drawn as $w_{i,k}\sim\mathcal{N}(0,10)$ for each firm. The parameters of the example are selected to be $A=100,c_{1}=5,c_{2}=2$. In Figure 2 we show the results of the simulation. Figure 2a shows the production path of each firm and Figure 2b shows the profit path of each firm. Under the Nash gradient dynamics, the firms converge to the unique Nash equilibrium of $q_{N}^{\ast}=(30.67,33.67)$ that gives profit of $\pi_{N}^{\ast}=(944.4,1114.7)$. The Stacklberg procedure converges to the unique Stackelberg equilibrium of $q_{S}^{\ast}=(46,26)$ that gives profit of $\pi_{S}^{\ast}=(1048.2,659.9)$. Hence as expected the two-timescale procedure converges to the Stackelberg equilibrium and gives the leader higher profit than under the Nash equilibrium.

2 Location Game on Torus

In this section, we examine a two-player game in which each player is selecting a position on a torus. Precisely, each player has a choice variable $\theta_{i}$ that can be chosen in the interval $[-\pi,\pi]$. The cost for each player is defined as $f_{i}(\theta_{i},\theta_{-i})=-\alpha_{i}\cos(\theta_{i}-\phi_{i})+\cos(\theta_{i}-\theta_{-i})$, where each $\phi_{i}$ and $\alpha_{i}$ are constants. The cost function is such that each player must trade-off being close to $\phi_{i}$ and far from $\theta_{-i}$. For the simulation of this game, we select the parameters $\alpha=(1.0,1.3)$ and $\phi=(\pi/8,\pi/8)$. There are multiple Nash and Stackelberg equilibria under these parameters. Each equilibrium is a stable equilibrium in this example. The Nash equilbria are $\theta_{N}^{\ast}=(-0.78,1.18)$ and $\theta_{N}^{\ast}=(1.57,-0.4)$, and the costs are each $f(\theta_{N}^{\ast})=(-0.77,-1.3)$ and $f(\theta_{N}^{\ast})=(-0.77,-1.3)$. The Stackelberg equilbria are $\theta_{S}^{\ast}=(-0.53,1.25)$ and $\theta_{S}^{\ast}=(1.31,-0.46)$, and the costs are each $f(\theta_{S}^{\ast})=(-0.81,-1.05)$. Hence, the ability to play before the follower gives the leader a smaller cost at any equilibrium. The equilibrium the dynamics will converge to depends on the initialization as we demonstrate. For this simulation, we select a decaying step-size of $\gamma_{i,k}=1/k^{1/2}$ for each player in the Nash gradient dynamics. The decaying step-size is chosen to be $\gamma_{1,k}=1/k$ for the leader and $\gamma_{2,k}=1/k^{1/2}$ for the follower in the Stackelberg two-timescale dynamics. The noise at each update step is drawn as $w_{i,k}\sim\mathcal{N}(0,0.01)$ for each player. In Figure 3 we show the results of our simulation. The Nash and Stackelberg dynamics converge to an equilibrium as expected. In Figures 3a and 3b, we visualize multiple sample learning paths for the Nash and Stackelberg dynamics, respectively. The black lines depict $D_{1}f_{1}$ for Nash and $Df_{1}$ for Stackelberg and demonstrate how the order of play warps the first-order conditions for the leader and consequently produces equilibria which move away from the Nash equilibria. In Figure 3c we give a detailed look at the convergence to an equilibrium for a sample path. Finally, in Figure 3d, we present the evolution of the cost while learning and demonstrate the benefit of being the leader and the disadvantage of being the follower.

3 Generative Adversarial Networks

We now present a set of illustrative experiments showing the role of Stackelberg equilibria in the optimization landscape of GANs and the empirical benefits of training GANs using the Stackelberg learning dynamics compared to the simultaneous gradient descent dynamics. We find that the leader update empirically cancels out rotational dynamics and prevents cycling behavior. Moreover, we discover that the simultaneous gradient dynamics can empirically converge to non-Nash stable attractors that are Stackelberg equilibria in GANs. The generator and the discriminator exhibit desirable performance at such points, indicating that Stackelberg equilibria can be as desirable as Nash equilibria. We also find that the Stackelberg learning dynamics often converge to non-Nash stable attractors and reach a satisfying solution quickly using learning rates that can cause the simultaneous gradient descent dynamics to cycle. We provide details on our implementation of the Stackelberg leader update and the techniques to compute relevant eigenvalues of games in Appendix E. More details for specific hyperparameters can be found in Appendix D.

We compare the deterministic gradient update for Stackelberg learning dynamics and simultaneous gradient descent, and analyze the distance from equilibrium as a function of time. We plot $\|\Sigma-VV^{\top}\|_{2}$ for the generator’s performance and $\|\frac{1}{2}(W+W^{\top})\|_{2}$ for the discriminator’s performance in Fig. 4 for varying dimensions $m$ with learning rate where $\gamma_{1,k}=o(\gamma_{2,k})$ and fixed regularization terms $\eta=m/5$. We observe that Stackelberg learning converges to an equilibrium in fewer iterations than simultaneous gradient descent. For zero-sum games, our theory provides reasoning for this behavior since at any critical point the eigenvalues of the game Jacobian are purely real. This is in contrast to the game Jacobian for the simultaneous gradient descent, which can admit imaginary eigenvalue components that are know to cause rotational forces in the dynamics. This example provides empirical evidence that the Stackelberg dynamics cancel out rotations in general-sum games.

Example 2: Mixture of Gaussian (Diamond). We also train a GAN to learn a mixture of Gaussian distributions, where the generator is the leader and the discriminator is the follower. The generator network has two hidden layers and the discriminator has one hidden layer; each hidden layer has $32$ neurons. We train using a batch size of $256$, a latent dimension of $16$, and the default ADAM optimizer configuration in PyTorch version 1. Since the updates are stochastic, we decay the learning rates to satisfy our timescale separation assumption and regularize the implicit map of the follower using the parameter $\eta=1$. We derive the regularized leader update in Appendix C.

The underlying data distribution for this problem consists of Gaussian distributions with means given by $\mu=[1.5\sin(\omega),1.5\cos(\omega)]$ for $\omega\in\{k\pi/2\}_{k=0}^{3}$ and each with covariance $\sigma^{2}I$ where $\sigma^{2}=0.15$. Each sample of real data given to the discriminator is selected uniformly at random from the set of Gaussian distributions. We train each learning rule using learning rates that begin at $0.0001$. Moreover, in this example, the activation following the hidden layers in each network is the tanh function.

We train this experiment using the saturating GAN objective . In Fig. 5a–5b and Fig. 5g–5h we show a sample of the generator and the discriminator for simultaneous gradient descent and the Stackelberg dynamics after 40,000 training batches. Each learning rule converges so that the generator can create a distribution that is close to the ground truth and the discriminator is nearly at the optimal probability throughout the input space. In Fig. 5c–5f and Fig. 5i–5l, we show eigenvalues from the game that allow us to get a deeper view of the convergence behavior. We observe that the simultaneous gradient dynamics appear be in a neighborhood of a non-Nash equilibrium since the individual Hessian for the leader is indefinite, the individual Hessian for the follower is positive definite, and the Schur complement is positive definite. Moreover, the eigenvalues of the leader individual Hessian are nearly zero, which would reflect the realizable assumption from Section 2. The Stackelberg learning dynamics converge to a point with similar eigenvalues, which would be a non-Nash Stackelberg equilibrium. This example demonstrates that standard GAN training can converge to non-Nash attractors that are Stackelberg equilibria and the Stackelberg equilibria can produce good generator and discriminator performance. This indicates that it may not be necessary to look only for Nash equilibria and instead it may be easier to find Stackelberg equilibria and the performance could be as desirable.

Example 3: Mixure of Gaussian (Circle). The underlying data distribution for this problem consists of Gaussian distributions with means given by $\mu=[\sin(\omega),\cos(\omega)]$ for $\omega\in\{k\pi/4\}_{k=0}^{7}$ and each with covariance $\sigma^{2}I$ where $\sigma^{2}=0.3$, sampled in the similar manner as the previous example. We train each learning rule using learning rates that begin at $0.0004$. Moreover, in this example, the activation following the hidden layers in each network is the ReLU function.

We train the GAN with the non-saturating objective . We show the the performance in Fig. 6 along the learning path for the simultaneous gradient descent dynamics and the Stackelberg learning dynamics. The simultaneous gradient descent dynamics cycle and perform poorly until the learning rates have decayed enough to stabilize the training process. The Stackelberg learning dynamics converge quickly to a solution that nearly matches the ground truth distribution. In a similar fashion as in the covariance example, the leader update is able to cancel out rotations and converge to a desirable solution with a learning rate that destabilizes the training process for standard training techniques. We show the eigenvalues after training and see that for this configuration the simultaneous gradient dynamics converge to a Nash equilibrium and the Stackelberg learning dynamics converge again to a non-Nash Stackelberg equilibrium. This provides further evidence that Stackelberg equilibria may be easier to reach and can provide suitable generator performance.

Example 4: MNIST dataset. To demonstrate that the Stackelberg learning dynamics can scale to high dimensional problems, we train a GAN on the MNIST dataset using the DCGAN architecture adapted to handle $28\times 28$ images. We train on an MNIST dataset consisting of only the digits 0 and 1 from the training images and on an MNIST dataset containing the entire set of training images. We train using a batch size of $256$, a latent dimension of $100$, and the ADAM optimizer with the default parameters for the DCGAN network. We regularize the implicit map of the follower as detailed in Appendix C using the parameter $\eta=5000$. If we view the regularization as a linear function of the number of parameters in the discriminator, then this selection of regularization is nearly equal to that from the mixture of Gaussian experiments.

We show the results in Fig. 7 after 2900 batches. For each dataset we show a sample of 16 digits to get a clear view of the generator performance and a sample of 256 digits to get a broader view of the generator output. The Stackelberg dynamics are able to converge to a solution that generates realistic handwritten digits. The primary purpose of this example is to show that the learning dynamics including second order information and an inverse is not an insurmountable problem for training large scale networks with millions of parameters. We believe the tools we develop for our implementation can be helpful to researchers working on GANs since a number of theoretical works on this topic require second order information to strengthen the convergence guarantees.

Conclusion

We study the convergence of learning dynamics in Stackelberg games. This class of games broadly pertains to any application in which there is an order of play between the players in the game. However, the problem has not been extensively analyzed in the way the learning dynamics of simultaneous play games have been. Consequently, we are able to give novel convergence results and draw connections to existing work focused on learning Nash equilibria.

References

A Mathematical Preliminaries

In this appendix, we show some preliminary results on linear algebra and recall some definitions and results from dynamical systems theory that are needed to state and prove the results in the main paper.

The results in this subsection follow from the theory of block operator matrices and indefinite linear algebra .

The following lemma is a very well-known result in linear algebra and can be found in nearly any advanced linear algebra text such as .

We can now use the above Lemma to prove Proposition 3. The proof follows the main arguments in the proof of Lemma 3.2 in the work by Berger et al. with some minor changes due to the nature of our problem.

By assumption, we have that $\dim\mathcal{S}_{2}=r$ so that, since $r>n$,

Thus, $\mathcal{S}_{1}\cap\mathcal{S}_{2}\neq\{0\}$. Now, $\mathcal{S}_{1}=\ker(B(-C^{-1}+|C^{-1}|)B^{\top})$. Hence, for any non-trivial vector $v\in\mathcal{S}_{1}\cap\mathcal{S}_{2}$, $(BC^{-1}B^{\top}-B|C^{-1}|B^{\top})v=0$ so that we have