Independent Policy Gradient Methods for Competitive Reinforcement Learning

Introduction

Reinforcement learning (RL)—in which an agent must learn to maximize reward in an unknown dynamic environment—is an important frontier for artificial intelligence research, and has shown great promise in application domains ranging from robotics (Kober et al., 2013; Lillicrap et al., 2015; Levine et al., 2016) to games such as Atari, Go, and Starcraft (Mnih et al., 2015; Silver et al., 2017; Vinyals et al., 2019). Many of the most exciting recent applications of RL are game-theoretic in nature, with multiple agents competing for shared resources or cooperating to solve a common task in stateful environments where agents’ actions influence both the state and other agents’ rewards (Silver et al., 2017; OpenAI, 2018; Vinyals et al., 2019). Algorithms for such multi-agent reinforcement learning (MARL) settings must be capable of accounting for other learning agents in their environment, and must choose their actions in anticipation of the behavior of these agents. Developing efficient, reliable techniques for MARL is a crucial step toward building autonomous and robust learning agents.

While single-player (or, non-competitive RL has seen much recent theoretical activity, including development of efficient algorithms with provable, non-asymptotic guarantees (Dann and Brunskill, 2015; Azar et al., 2017; Jin et al., 2018; Dean et al., 2019; Agarwal et al., 2020), provable guarantees for MARL have been comparatively sparse. Existing algorithms for MARL can be classified into centralized/coordinated algorithms and independent/decoupled algorithms (Zhang et al., 2019a). Centralized algorithms such as self-play assume the existence of a centralized controller that joinly optimizes with respect to all agents’ policies. These algorithms are typically employed in settings where the number of players and the type of interaction (competitive, cooperative, etc.) are both known a-priori. On the other hand, in independent reinforcement learning, agents behave myopically and optimize their own policy while treating the environment as fixed. They observe only local information, such as their own actions, rewards, and the part of the state that is available to them. As such, independent learning algorithms are generally more versatile, as they can be applied even in uncertain environments where the type of interaction and number of other agents are not known to the individual learners.

Both centralized (Silver et al., 2017; OpenAI, 2018; Vinyals et al., 2019) and independent (Matignon et al., 2012; Foerster et al., 2017) algorithms have enjoyed practical success across different domains. However, while centralized algorithms have experienced recent theoretical development, including provable finite-sample guarantees (Wei et al., 2017; Bai and Jin, 2020; Xie et al., 2020), theoretical guarantees for independent reinforcement learning have remained elusive. In fact, it is known that independent algorithms may fail to converge even in simple multi-agent tasks (Condon, 1990; Tan, 1993; Claus and Boutilier, 1998): When agents update their policies independently, they induce distribution shift, which can break assumptions made by classical single-player algorithms. Understanding when these algorithms work, and how to stabilize their performance and tackle distribution shift, is recognized as a major challenge in multi-agent RL (Matignon et al., 2012; Hernandez-Leal et al., 2017).

In this paper, we focus on understanding the convergence properties of independent reinforcement learning with policy gradient methods (Williams, 1992; Sutton et al., 2000). Policy gradient methods form the foundation for modern applications of multi-agent reinforcement learning, with state-of-the-art performance across many domains (Schulman et al., 2015, 2017). Policy gradient methods are especially relevant for continuous reinforcement learning and control tasks, since they readily scale to large action spaces, and are often more stable than value-based methods, particularly with function approximation (Konda and Tsitsiklis, 2000). Independent reinforcement learning with policy gradient methods is poorly understood, and attaining global convergence results is considered an important open problem (Zhang et al., 2019a, Section 6).

We analyze the behavior of independent policy gradient methods in Shapley’s stochastic game framework (Shapley, 1953). We focus on two-player zero-sum stochastic games with discrete state and action spaces, wherein players observe the entire joint state, take simultaneous actions, and observe rewards simultaneously, with one player trying to maximize the reward and the other trying to minimize it. To capture the challenge of independent learning, we assume that each player observes the state, reward, and their own action, but not the action chosen by the other player. We assume that the dynamics and reward distribution are unknown, so that players must optimize their policies using only realized trajectories consisting of the states, rewards, and actions. For this setting, we show that—while independent policy gradient methods may not converge in general—policy gradient methods following a two-timescale rule converge to a Nash equilibrium. We also show that moving beyond two-timescale rules by incorporating optimization techniques from matrix games such as optimism (Daskalakis et al., 2017) or extragradient updates (Korpelevich, 1976) is likely to require new analysis techniques.

At a technical level, our result is a special case of a more general theorem, which shows that (stochastic) two-timescale updates converge to Nash equilibria for a class of nonconvex minimax problems satisfying a certain two-sided gradient dominance property. Our results here expand the class of nonconvex minimax problems with provable algorithms beyond the scope of prior work (Yang et al., 2020), and may be of independent interest.

Preliminaries

We investigate the behavior of independent learning in two-player zero-sum stochastic games (or, Markov games), a simple competitive reinforcement learning setting (Shapley, 1953; Littman, 1994). In these games, two players—a min-player and a max-player—repeatedly select actions simultaneously in a shared Markov decision process in order to minimize and maximize, respectively, a given objective function. Formally, a two-player zero-sum stochastic game is specified by a tuple $\mathcal{G}=(\mathcal{S},\mathcal{A},\mathcal{B},P,R,\zeta,\rho)$:

$\mathcal{S}$ is a finite state space of size $S=|\mathcal{S}|$.

$\mathcal{A}$ and $\mathcal{B}$ are finite action spaces for the min- and max-players, of sizes $A=|\mathcal{A}|$ and $B=|\mathcal{B}|$.

$P$ is the transition probability function, for which $P(s^{\prime}\mid s,a,b)$ denotes the probability of transitioning to state $s^{\prime}$ when the current state is $s$ and the players take actions $a$ and $b$. In general we will have $\zeta_{s,a,b}\vcentcolon={}1-\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}\mid s,a,b)>0$; this quantity represents the probability that $\mathcal{G}$ stops at state $s$ if actions $a,b$ are played.

$R:\mathcal{S}\times\mathcal{A}\times\mathcal{B}\rightarrow$ is the reward function; $R(s,a,b)$ gives the immediate reward when the players take actions $a,b$ in state $s$. The min-player seeks to minimize $R$ and the max-player seeks to maximize it.We consider deterministic rewards for simplicity, but our results immediately extend to stochastic rewards.

$\zeta:=\min_{s,a,b}\{\zeta_{s,a,b}\}$ is a lower bound on the probability that the game stops at any state $s$ and choices of actions $a,b$. We assume that $\zeta>0$ throughout this paper.

$\rho\in\Delta(\mathcal{S})$ is the initial distribution of the state at time $t=0$.

At each time step $t\geq 0$, both players observe a state $s_{t}\in\mathcal{S}$, pick actions $a_{t}\in\mathcal{A}$ and $b_{t}\in\mathcal{B}$, receive reward $r_{t}\vcentcolon={}R(s_{t},a_{t},b_{t})$, and transition to the next state $s_{t+1}\sim P(\cdot\mid s_{t},a_{t},b_{t})$. With probability $\zeta_{s_{t},a_{t},b_{t}}$, the game stops at time $t$; since $\zeta>0$, the game stops eventually with probability $1$.

A pair of (randomized) policies $\pi_{1}:\mathcal{S}\to\Delta(\mathcal{A})$, $\pi_{2}:\mathcal{S}\to\Delta(\mathcal{B})$ induces a distribution $\operatorname{Pr}^{\pi_{1},\pi_{2}}$ of trajectories $(s_{t},a_{t},b_{t},r_{t})_{0\leq t\leq T}$, where $s_{0}\sim\rho$, $a_{t}\sim\pi_{1}(\cdot\mid s_{t}),b_{t}\sim\pi_{2}(\cdot\mid s_{t})$, $r_{t}=R(s_{t},a_{t},b_{t})$, and $T$ is the last time step before the game stops (which is a random variable). The value function $V_{s}(\pi_{1},\pi_{2})$ gives the expected reward when $s_{0}=s$ and the plays follow $\pi_{1}$ and $\pi_{2}$:

Shapley (1953) showed that stochastic games satisfy a minimax theorem: For any game $\mathcal{G}$, there exists a Nash equilibrium $(\pi^{\star}_{1},\pi^{\star}_{2})$ such that

and in particular $V^{\star}_{\rho}\vcentcolon={}\min_{\pi_{1}}\max_{\pi_{2}}V_{\rho}(\pi_{1},\pi_{2})=\max_{\pi_{2}}\min_{\pi_{1}}V_{\rho}(\pi_{1},\pi_{2})$. Our goal in this setting is to develop algorithms to find $\varepsilon$-approximate Nash equilibria, i.e. to find $\pi_{1}$ such that

Visitation distributions.

For policies $\pi_{1},\pi_{2}$ and an initial state $s_{0}$, define the discounted state visitation distribution $d_{s_{0}}^{\pi_{1},\pi_{2}}\in\Delta(\mathcal{S})$ by

Additional notation.

Independent Learning

We analyze independent reinforcement learning algorithms for stochastic games in an episodic setting in which both players repeatedly execute arbitrary policies for a fixed number of episodes with the goal of producing an (approximate) Nash equilibrium.

We formalize the notion of independent RL via the following protocol: At each episode $i$, the min-player proposes a policy $\pi_{1}^{{\scriptscriptstyle(i)}}:\mathcal{S}\to\Delta(\mathcal{A})$ and the max-player proposes a policy $\pi_{2}^{{\scriptscriptstyle(i)}}:\mathcal{S}\to\Delta(\mathcal{B})$ independently. These policies are executed in the game $\mathcal{G}$ to sample a trajectory. The min-player observes only its own trajectory $(s_{1}^{{\scriptscriptstyle(i)}},a_{1}^{{\scriptscriptstyle(i)}},r_{1}^{{\scriptscriptstyle(i)}}),\ldots,(s_{T}^{{\scriptscriptstyle(i)}},a_{T}^{{\scriptscriptstyle(i)}},r_{T}^{{\scriptscriptstyle(i)}})$, and the max-player likewise observes $(s_{1}^{{\scriptscriptstyle(i)}},b_{1}^{{\scriptscriptstyle(i)}},r_{1}^{{\scriptscriptstyle(i)}})$, $\ldots,$ $(s_{T}^{{\scriptscriptstyle(i)}},b_{T}^{{\scriptscriptstyle(i)}},r_{T}^{{\scriptscriptstyle(i)}})$. Importantly, each player is oblivious to the actions selected by the other.

We call a pair of algorithms for the min- and max-players an independent distributed protocol if (1) the players only access the game $\mathcal{G}$ through the oracle model above (independent oracle), and (2) the players can only use private storage, and are limited to storing a constant number of past trajectories and parameter vectors (limited private storage). The restriction on limited private storage aims to rule out strategies that orchestrate the players’ sequences of actions in order for them to both reconstruct a good approximation of entire game $\mathcal{G}$ in their memory, then solve for equilibria locally. We note that making this constraint precise is challenging, and that similar difficulties with formalizing it arise even for two-player matrix games, as discussed in Daskalakis et al. (2011). In any event, the policy gradient methods analyzed in this paper satisfy these formal constraints and are independent in the intuitive sense, with the caveat that the players need a very small amount of a-priori coordination to decide which player operates at a faster timescale when executing two-timescale updates. Because of the necessity of two-timescale updates, our algorithm does not satisfy the requirement of strong independence, which we define to be the setting that disallows any coordination to break symmetry so as to agree on differing “roles” of the players (such as differing step-sizes or exploration probabilities). As discussed further in Section 5.1, we leave the question of developing provable guarantees for strongly independent algorithms of this type as an important open question.

Our question: Convergence of independent policy gradient methods.

For example, if both players use the ubiquitous REINFORCE gradient estimator (Williams, 1992), and update their policies with stochastic gradient descent, the updates for episode $i$ take the formFor a convex set $\mathcal{X}$, $\mathcal{P}_{\mathcal{X}}$ denotes euclidean projection onto the set.

where $R_{T}^{{\scriptscriptstyle(i)}}\vcentcolon=\sum_{t=0}^{T}r_{t}^{{\scriptscriptstyle(i)}}$, and where $x^{{\scriptscriptstyle(0)}},y^{{\scriptscriptstyle(0)}}$ are initialized arbitrarily. This protocol is independent, since each player forms their respective policy gradient using only the data from their own trajectory. This leads to our central question:

When do independent agents following policy gradient updates in a zero-sum stochastic game converge to a Nash equilibrium?

We focus on an $\varepsilon$-greedy variant of the so-called direct parameterization where $\mathcal{X}=\Delta(\mathcal{A})^{\left\lvert\mathcal{S}\right\rvert}$, $\mathcal{Y}=\Delta(\mathcal{B})^{\left\lvert\mathcal{S}\right\rvert}$, $\pi_{x}(a\mid{}s)=(1-\varepsilon_{x})x_{s,a}+\varepsilon_{x}/\left\lvert\mathcal{A}\right\rvert$, and $\pi_{y}(a\mid{}s)=(1-\varepsilon_{y})y_{s,b}+\varepsilon_{y}/\left\lvert\mathcal{B}\right\rvert$, where $\varepsilon_{x}$ and $\varepsilon_{y}$ are exploration parameters. This is a simple model, but we believe it captures the essential difficulty of the independent learning problem.

Challenges of independent learning.

Independent learning is challenging even for simple stochastic games, which are a special type of stochastic game in which only a single player can choose an action in each state, and where there are no rewards except in certain “sink” states. Here, a seminal result of Condon (1990), establishes that even with oracle access to the game $\mathcal{G}$ (e.g., exact $Q$-functions given the opponent’s policy), many naive approaches to independent learning can cycle and fail to approach equilibria, including protocols where (1) both players perform policy iteration independently, and (2) both players compute best responses at each episode. On the positive side, Condon (1990) also shows that if one player performs policy iteration independently while the other computes a best response at each episode, the resulting algorithm converges, which parallels our findings.

Stochastic games also generalize two-player zero-sum matrix games. Here, even with exact gradient access, it is well-known that if players update their strategies independently using online gradient descent/ascent (GDA) with the same learning rate, the resulting dynamics may cycle, leading to poor guarantees unless the entire iterate sequence is averaged (Daskalakis et al., 2017; Mertikopoulos et al., 2018). To make matters worse, when one moves beyond the convex-concave setting, such iterate averaging techniques may fail altogether, as their analysis critically exploits convexity/concavity of the loss function. To give stronger guarantees—either for the last-iterate or for “most” elements of the iterate sequence—more sophisticated techniques based on two-timescale updates or negative momentum are required. However, existing results here rely on the machinery of convex optimization, and stochastic games—even with direct parameterization—are nonconvex-nonconcave, leading to difficulties if one attempts to apply these techniques out of the box.

In light of these challenges, it suffices to say that we are aware of no global convergence results for independent policy gradient methods (or any other independent distributed protocol, for that matter) in general finite state/action zero-sum stochastic games.

Main Result

We show that independent policy gradient algorithms following the updates in (3) converge to a Nash equilibrium, so long as their learning rates follow a two-timescale rule. The two-timescale rule is a simple modification of the usual gradient-descent-ascent scheme for minimax optimization in which the min-player uses a much smaller stepsize than the max-player (i.e., $\eta_{x}\ll\eta_{y}$), and hence works on a slower timescale (or vice-versa). Two-timescale rules help to avoid limit cycles in simple minimax optimization settings (Heusel et al., 2017; Lin et al., 2020), and our result shows that their benefits extend to MARL as well.

Before stating the result, we first introduce some technical conditions that quantify the rate of convergence. First, it is well-known that policy gradient methods can systematically under-explore hard-to-reach states. Our convergence rates depend on an appropriately-defined distribution mismatch coefficient which bounds the difficulty of reaching such states, generalizing results for the single-agent setting (Agarwal et al., 2020). While methods based on sophisticated exploration (e.g., Dann and Brunskill (2015); Jin et al. (2018)) can avoid dependence on mismatch parameters, our goal here—similar to prior work in this direction (Agarwal et al., 2020; Bhandari and Russo, 2019)—is to understand the behavior of standard methods used in practice, so we take the dependence on such parameters as a given.

Given a stochastic game $\mathcal{G}$, we define the minimax mismatch coefficient for $\mathcal{G}$ by:

where $\Pi^{\star}_{1}(\pi_{2})$ and $\Pi^{\star}_{2}(\pi_{1})$ each denotes the set of best responses for the min- (resp. max-) player when the max- (resp. min-) player plays $\pi_{2}$ (resp. $\pi_{1}$).

Compared to results for the single-agent setting, which typically scale with $\|\nicefrac{{d^{\pi^{\star}}_{\rho}}}{{\rho}}\|_{\infty}$, where $\pi^{\star}$ is an optimal policy (Agarwal et al., 2020), the minimax mismatch coefficient measures the worst-case ratio for each player, given that their adversary best-responds. While the minimax mismatch coefficient in general is larger than its single-agent counterpart, it is still weaker than other notions of mismatch such as concentrability (Munos, 2003; Chen and Jiang, 2019; Fan et al., 2020), which—when specialized to the two-agent setting—require that the ratio is bounded for all pairs of policies. The following proposition makes this observation precise.

There exists a stochastic game with five states and initial distribution $\rho$ such that $C_{\mathcal{G}}$ is bounded, but the concentrability coefficient $\max_{\pi_{1},\pi_{2}}\left\|\frac{d_{\rho}^{\pi_{1},\pi_{2}}}{\rho}\right\|_{\infty}$ is infinite.

Next, to ensure the variance of the REINFORCE estimator stays bounded, we require that both players use $\varepsilon$-greedy exploration in conjunction with the basic policy gradient updates (3).

Both players follow the direct parameterization with $\varepsilon$-greedy exploration: Policies are parameterized as $\pi_{x}(a\mid{}s)=(1-\varepsilon_{x})x_{s,a}+\varepsilon_{x}/\left\lvert\mathcal{A}\right\rvert$ and $\pi_{y}(a\mid{}s)=(1-\varepsilon_{y})y_{s,b}+\varepsilon_{y}/\left\lvert\mathcal{B}\right\rvert$, where $\varepsilon_{x},\varepsilon_{y}\in$ are the exploration parameters.

Let $\epsilon>0$ be given. Suppose both players follow the independent policy gradient scheme (3) with the parameterization in Assumption 1. If the learning rates satisfy $\eta_{x}\asymp\epsilon^{10.5}$ and $\eta_{y}\asymp\epsilon^{6}$ and the exploration parameters satisfy $\varepsilon_{x}\asymp\epsilon,\varepsilon_{y}\asymp\epsilon^{2}$, we are guaranteed that

after $N\leq{}\operatorname{poly}(\epsilon^{-1},C_{\mathcal{G}},S,A,B,\zeta^{-1})$ episodes.

This represents, to our knowledge, the first finite-sample, global convergence guarantee for independent policy gradient updates in stochastic games. Some key features are as follows:

Since the learning agents only use their own trajectories to make decisions, and only store a single parameter vector in memory, the protocol is indeed independent in the sense of Section 3. However, an important caveat is that since the players use different learning rates, the protocol only succeeds if the rates are coordinated in advance.

The two-timescale update rule may be thought of as a softened “gradient descent vs. best response” scheme in which the min-player updates their strategy using policy gradient and the max-player updates their policy with a best response to the min-player (since $\eta_{x}\ll\eta_{y}$). This is why the guarantee is asymmetric, in that it only guarantees that the iterates of the min-player are approximate Nash equilibria.From an optimization perspective, the oracle complexity of finding a solution so that the iterates of both the min and max-player are approximate equilibria is only twice as large as that in Theorem 1, since we may apply Theorem 1 with the roles switched. We remark that the gradient descent vs. exact best response has recently been analyzed for linear-quadratic games (Zhang et al., 2019b), and it is possible to use the machinery of our proofs to show that it succeeds in our finite state/action stochastic game setting as well.

Eq. (13) shows that the iterates of the min-player have low error on average, in the sense that the expected error is smaller than $\epsilon$ if we select an iterate from the sequence uniformly at random. Such a guarantee goes beyond what is achieved by gradient-descent-ascent (GDA) with equal learning rates: Even for zero-sum matrix games, the iterates of GDA can reach limit cycles that remain a constant distance from the equilibrium, so that any individual iterate in the sequence will have high error (Mertikopoulos et al., 2018). While averaging the iterates takes care of this issue for matrix games, this technique relies critically on convexity, which is not present in our policy gradient setting. While our guarantees are stronger than GDA, we believe that giving guarantees that hold for individual (in particular, last) iterates rather than on average over iterates is an important open problem. This is discussed further in Section 5.1.

We have not attempted to optimize the dependence on $\epsilon^{-1}$ or other parameters, and this can almost certainly be improved.

The full proof of Theorem 1—as well as explicit dependence on problem parameters—is deferred to Appendix A. In the remainder of this section we sketch the key techniques.

Overview of techniques.

Suppose that players follow the $\varepsilon$-greedy direct parameterization of Assumption 1 with parameters $\varepsilon_{x}$ and $\varepsilon_{y}$. Then for all $x\in\Delta(\mathcal{A})^{\left\lvert\mathcal{S}\right\rvert}$, $y\in\Delta(\mathcal{B})^{\left\lvert\mathcal{S}\right\rvert}$ we have

and an analogous upper bound holds for $\max_{\pi_{2}}V_{\rho}(\pi_{y},\pi_{2})-V_{\rho}(\pi_{x},\pi_{y})$.

Informally, the gradient dominance condition posits that for either player to have low regret relative to the best response to the opponent’s policy, it suffices to find a near-stationary point. In particular, while the function $x\mapsto{}V_{\rho}(x,y)$ is nonconvex, the condition (7) implies that if the max-player fixes their strategy, all local minima are global for the min-player.

Unfortunately, compared to the single-agent setting, we are aware of no existing black-box minimax optimization results that can exploit this condition to achieve even asymptotic convergence guarantees. To derive our main results, we develop a new proof that two-timescale updates find Nash equilibria for generic minimax problems that satisfy the two-sided GD condition.

Then, given stochastic gradient oracles with variance at most $\sigma^{2}$, two-timescale stochastic gradient descent-ascent (Eq. (25) in Appendix B) with learning rates $\eta_{x}\asymp\epsilon^{8}$ and $\eta_{y}\asymp\epsilon^{4}$ ensures that

A formal statement and proof of Theorem 2 are given in Appendix B. To deduce Theorem 1 from this result, we simply trade off the bias due to exploration with the variance of the REINFORCE estimator.

Our analysis of the two-timescale update rule builds on Lin et al. (2020), who analyzed it for minimax problems $f(x,y)$ where $f$ is nonconvex with respect to $x$ but concave with respect to $y$. Compared to this setting, our nonconvex-nonconcave setup poses additional difficulties. At a high level, our approach is as follows. First, thanks to the gradient dominance condition for the $x$-player, to find an $\epsilon$-suboptimal solution it suffices to ensure that the gradient of $\Phi(x)\vcentcolon={}\max_{y\in\mathcal{Y}}f(x,y)$ is small. However, since $\Phi$ may not differentiable, we instead aim to minimize $\left\|\nabla\Phi_{\lambda}(x)\right\|_{2}$, where $\Phi_{\lambda}$ denotes the Moreau envelope of $\Phi$ (Appendix B.2). If the $y$-player performed a best response at each iteration, a standard analysis of nonconvex stochastic subgradient descent (Davis and Drusvyatskiy, 2018a), would ensure that $\left\|\nabla\Phi_{\lambda}(x^{{\scriptscriptstyle(i)}})\right\|_{2}$ converges at an $\epsilon^{-4}$ rate. The crux of our analysis is to argue that, since the $x$ player operates at a much slower timescale than the $y$-player, the $y$-player approximates a best response in terms of function value. Compared to Lin et al. (2020), which establishes this property using convexity for the $y$-player, we use the gradient dominance condition to bound the $y$-player’s immediate suboptimality in terms of the norm of the gradient of the function $\psi_{t,\lambda}(y)\vcentcolon={}-(-f(x_{t},\cdot))_{\lambda}(y)$, then show that this quantity is small on average using a potential-based argument.

Discussion

An important problem left open by our work is to develop independent policy gradient-type updates that enjoy last iterate convergence. This property is most cleanly stated in the noiseless setting, with exact access to gradients: For fixed, constant learning rates $\eta_{x}=\eta_{y}=\eta$, we would like that if both learners independently run the algorithm, their iterates satisfy

Algorithms with this property have enjoyed intense recent interest for continuous, zero-sum games (Daskalakis et al., 2017; Daskalakis and Panageas, 2018; Mertikopoulos et al., 2018; Daskalakis and Panageas, 2019; Liang and Stokes, 2019; Gidel et al., 2019b; Mokhtari et al., 2020; Kong and Monteiro, 2019; Gidel et al., 2019a; Abernethy et al., 2019; Azizian et al., 2020; Golowich et al., 2020). These include Korpelevich’s extragradient method (Korpelevich, 1976), Optimistic Mirror Descent (e.g., Daskalakis et al. (2017)), and variants. For a generic minimax problem $f(x,y)$, the updates for the extragradient method take the form

In the remainder of this section we show that while the extragradient method appears to succeed in simple two-player zero-sum stochastic games experimentally, establishing last-iterate convergence formally likely requires new tools. We conclude with an open problem.

As a running example, we consider von Neumann’s ratio game (von Neumann, 1945), a very simple stochastic game given by

For nonconvex-nonconcave minimax problems, the only general tool we are aware of for establishing last-iterate convergence for the extragradient method and its relatives is the Minty Variational Inequality (MVI) property (Facchinei and Pang, 2007; Lin et al., 2018; Mertikopoulos and Staudigl, 2018; Mertikopoulos et al., 2019; Gidel et al., 2019a). For $z=(x,y)$ and $F(z)\vcentcolon=(\nabla_{x}f(x,y),-\nabla_{y}f(x,y))$, the MVI property requires that there exists a point $z^{\star}\in\mathcal{Z}\vcentcolon=\mathcal{X}\times\mathcal{Y}$ such that

For general minimax problems, the MVI property is typically applied with $z^{\star}$ as a Nash equilibrium (Mertikopoulos et al., 2019). We show that this condition fails in stochastic games, even for the simple ratio game in (12)

Fix $\epsilon,s\in(0,1)$ with $\epsilon<\frac{1-s}{2s}$. Suppose we take

Then the ratio game defined by (12) has the following properties: (1) there is a unique Nash equilibrium $z^{*}=(z^{*},y^{*})$ given by $x^{*}=y^{*}=(0,1)$, (2) $\zeta\geq{}s$, (3) there exists $z=(x,y)\in\Delta(\mathcal{A})\times\Delta(\mathcal{B})$ so that $\langle F(z),z-z^{*}\rangle<0$.In fact, for this example the MVI property fails for all choices of $z^{\star}$, not just the Nash equilibrium.

Figure 1(a) plots the sign of $\left\langle F(z),z-z^{\star}\right\rangle$ for the game in (12) as a function of the players’ parameters, which changes based on whether they belong to one of two regions, and Figure 1(b) shows that extragradient readily converges to $z^{\star}$ in spite of the failure of MVI. While this example satisfies the MVI property locally around $z^{\star}$, Figure 1(c) shows a randomly generated game (Appendix C.1) for which the MVI property fails to hold even locally. Nonetheless, Figure 1(d) shows that extragradient converges for this example, albeit more slowly, and with oscillations. This leads to our open problem.

Does the extragradient method with constant learning rate have last-iterate convergence for the ratio game (11) for any fixed $\zeta>0$?

Additional experiments with multi-state games generated at random suggest that the extragradient method has last-iterate convergence for general stochastic games with a positive stopping probability. Proving such a convergence result for extragradient or for relatives such as the optimistic gradient method would be of interest not only because it would guarantee last-iterate convergence, but because it would provide an algorithm that is strongly independent in the sense that two-timescale updates are not required.

2 Related Work

Issues of independence in MARL have enjoyed extensive investigation. We refer the reader to Zhang et al. (2019a) for a comprehensive overview and discuss some particularly relevant related work below.

Beginning with their introduction by Shapley (1953), there is a long line of work developing computationally efficient algorithms for multi-agent RL in stochastic games (Littman, 1994; Hu and Wellman, 2003; Bu et al., 2008). While centralized, coordinated MARL algorithms such as self-play have recently enjoyed some advances in terms of non-asymptotic guarantees Brafman and Tennenholtz (2002); Wei et al. (2017); Bai and Jin (2020); Xie et al. (2020); Zhang et al. (2020), independent RL has seen less development, with a few exceptions we discuss below.

A recent line of work (Srinivasan et al., 2018; Omidshafiei et al., 2019; Lockhart et al., 2019) shows that for zero-sum extensive form games (EFG), independent policy gradient methods can be formulated in the language of counterfactual regret minimization (Zinkevich et al., 2008), and uses this observation to derive convergence guarantees. Unfortunately, for the general zero-sum stochastic games we consider, reducing to an EFG results in exponential blowup in size with respect to horizon.

Arslan and Yüksel (2017) introduce an algorithm for learning stochastic games which can be viewed as a 2-timescale method and show convergence (though without rates) in a somewhat different setting from ours. Perolat et al. (2018) provide asymptotic guarantees for an independent two-timescale actor-critic method in zero-sum stochastic games with a “simultaneous-move multistage” structure in which each state can only be visited once. Our result is somewhat more general since it works for arbitrary infinite-horizon stochastic games, and is non-asymptotic.

Zhang et al. (2019b); Bu et al. (2019) recently gave global convergence results for policy gradient methods in two-player zero-sum linear-quadratic games. These results show that if the min-player follows policy gradient updates and the max-player follows the best response at each timestep, the min-player will converge to a Nash equilibrium. These results do not satisfy the independence property defined in Section 3, since they follow an inner-loop/outer-loop structure and assume exact access to gradients of the value function. Interestingly, Mazumdar et al. (2020) show that for general-sum linear-quadratic games, independent policy gradient methods can fail to converge even locally.

Two concurrent works also develop provable independent learning algorithms for stochastic games. Lee et al. (2020) show that the optimistic gradient algorithm obtains linear rates in the full-information and finite-horizon (undiscounted) setting, where the transition probability function $P$ is known and we have exact access to gradients. Their rate depends on the constant in a certain restricted secant inequality; this constant can be arbitrarily small even in the setting of matrix games (i.e., a single state, $\zeta=1$, and fixed $A,B$), which causes the rate to be arbitrarily slow. In a setting very similar to that of this paper, Bai et al. (2020) propose a model-free upper confidence bound-based algorithm, Nash V-learning, which satisfies the independent learning requirement and has near-optimal sample complexity, achieving superior dependence to Theorem 1 on the parameters $S,A,B,\zeta$, as well as no dependence on $C_{\mathcal{G}}$. However, their work has the limitation of only learning non-Markovian policies, whereas the policies learned by 2-timescale SGDA are Markovian (i.e., only depend on the current state).

Minimax optimization and (non-monotone) variational inequalities.

Since the objective $V_{\rho}(x,y)$ is continuous, a natural approach to minimizing it is to appeal to black-box algorithms for nonconvex-nonconcave minimization, and more broadly non-montone variational inequalities. In particular, the gradient dominance condition implies that all first-order stationary points are Nash equilibria. Unfortunately, compared to the single-player setting, where many algorithms such as gradient descent find first-order stationary points for arbitrary smooth, nonconvex functions, existing algorithms for non-monotone variational inequalities all require additional assumptions that are not satisfied in our setting. Mertikopoulos et al. (2019) give convergence guarantees for non-monotone variational inequalities satisfying the so-called MVI property, which we show fails even for single-state zero-sum stochastic games (Section 5.1). Yang et al. (2020) give an alternating gradient descent algorithm which succeeds for nonconvex-nonconcave games under a two-sided Polyak-Łojasiewicz condition, but this condition (which leads to linear convergence) is also not satisfied in our setting. Another complementary line of work develops algorithms for nonconvex-concave problems (Rafique et al., 2018; Thekumparampil et al., 2019; Lu et al., 2020; Nouiehed et al., 2019; Kong and Monteiro, 2019; Lin et al., 2020).

3 Future Directions

We presented the first independent policy gradient algorithms for competitive reinforcement learning in zero-sum stochastic games. We hope our results will serve as a starting point for developing a more complete theory for independent reinforcement learning in competitive RL and multi-agent reinforcement learning. Beyond Open Problem 1, there are a number of questions raised by our work.

Efroni et al. (2020) have recently shown how to improve the convergence rates for policy gradient algorithms in the single-agent setting by incorporating optimism. Finding a way to use similar techniques in the multi-agent setting under the independent learning requirement could be another promising direction for future work.

Many games of interest are not zero-sum, and may involve more than two players or be cooperative in nature. It would be useful to extend our results to these settings, albeit likely for weaker solution concepts, and to derive a tighter understanding of the optimization geometry for these settings.

On the technical side, there are a number of immediate technical extensions of our results which may be useful to pursue, including (1) extending to linear function approximation, (2) extending to other policy parameterizations such as soft-max, and (3) actor-critic and natural policy gradient-based variants (Agarwal et al., 2020).

References

Appendix A Proofs from Section 4

For policies $\pi_{1},\pi_{2}$, we let $Q^{\pi_{1},\pi_{2}}(s,a,b)$ denote the $Q$-value function:

and we let $A^{\pi_{1},\pi_{2}}(s,a,b)=Q^{\pi_{1},\pi_{2}}(s,a,b)-V_{s}(\pi_{1},\pi_{2})$ denote the advantage function.

Throughout this section we abbreviate $V_{\rho}(x,y)=V_{\rho}(\pi_{x},\pi_{y})$, where $\pi_{x}$ and $\pi_{y}$ use the $\varepsilon$-greedy direct parameterization in Assumption 1.

A.2 Full Version of Theorem 1 and Proof

The full version of Theorem 1 is as follows.

Let $\epsilon>0$ be given. Suppose both players follow the independent policy gradient scheme (3) with the parametrization in Assumption 1. If the learning rates satisfy $\eta_{x}=\Theta\left(\frac{\epsilon_{0}^{10.5}\zeta^{44.5}}{C_{\mathcal{G}}^{15.5}(A\vee B)^{9.75}S^{0.75}}\right)$ and $\eta_{y}=\Theta\left(\frac{\epsilon^{6}\zeta^{27}}{C_{\mathcal{G}}^{9}(A\vee B)^{6}\sqrt{S}}\right)$ and $\varepsilon_{x}=\Theta\left(\frac{\zeta^{3}\cdot\epsilon}{\sqrt{S}\sqrt{A\vee B}C_{\mathcal{G}}}\right)$ and $\varepsilon_{y}=\Theta\left(\frac{\zeta^{8}\epsilon^{2}}{C_{\mathcal{G}}^{3}(A\vee B)\sqrt{S}}\right)$, then we are guaranteed that

after $N=O\left(\frac{(A\vee B)^{10.75}S^{1.25}C_{\mathcal{G}}^{17.5}}{\epsilon^{12.5}\zeta^{48.5}}\right)$ episodes.

Similarly, by Proposition 3, the function value $V_{\rho}(x,y)$ is $L\vcentcolon={}\frac{2\sqrt{A\vee{}B}}{\zeta^{2}}$-Lipschitz:

Lemma 1a guarantees that the gradient domination conditions 2 and 3 of Assumption 2 are satisfied with $\mu_{y}=\mu_{x}=\zeta/C_{\mathcal{G}}$, and additive components $\varepsilon_{x},\varepsilon_{y}$ equal to $\frac{2\varepsilon_{x}}{\zeta^{2}}$ and $\frac{2\varepsilon_{y}}{\zeta^{2}}$, respectively:

Recall that $x\mapsto\pi_{x},y\mapsto\pi_{y}$ denote the $\varepsilon_{x}$- and $\varepsilon_{y}$-greedy parametrizations, respectively (where $\varepsilon_{x},\varepsilon_{y}$ are as in the statement of Theorem 1a). Then for any $\pi_{1}:\mathcal{S}\rightarrow\Delta(\mathcal{A})$ (respectively, $\pi_{2}:\mathcal{S}\rightarrow\Delta(\mathcal{B})$), there is some $x\in\Delta(\mathcal{A})^{S}$ (respectively, $y\in\Delta(\mathcal{B})^{s}$) so that $\|\pi_{1}-\pi_{x}\|\leq 2\sqrt{S}\varepsilon_{x}$ (respectively, $\|\pi_{2}-\pi_{y}\|\leq 2\sqrt{S}\varepsilon_{y}$) for each $s\in\mathcal{S},a\in\mathcal{A}$ (respectively, $b\in\mathcal{B}$). Moreover, recall that Proposition 3 shows that the function $(x,y)\mapsto V_{\rho}(x,y)$ is $L$-Lipschitz for any $\varepsilon$-greedy parametrization, in particular for the one given by $\varepsilon_{x}=\varepsilon_{y}=0$. Thus,

To achieve a desired accuracy level $\epsilon_{0}$, it follows from (15), (16), and (17) that if we set

A.3 Proofs for Additional Results

We define the following game $\mathcal{G}$ with state space $\mathcal{S}:=\{1,2,3,4,5\}$, action spaces $\mathcal{A}=\mathcal{B}=\{0,1\}$, and any stopping probability $\zeta>0$.

The transitions and rewards are as follows:

In state 1, with probability $\zeta$, the game stops. Conditioned on not stopping:

If actions $(0,0)$ are taken, the game moves to state 2.

If actions $(0,1)$ are taken, the game moves to state 3.

If actions $(1,0)$ are taken, the game moves to state 4.

If actions $(1,1)$ are taken, the game moves to state 5.

Both players receive 0 reward in state 1.

In state $2\leq i\leq 5$, the game stops with probability $\zeta$, and otherwise always moves back to state 1. Furthermore, player 1 receives reward $i-1$ and player 2 receives reward $1-i$ (regardles of their actions).

Let the initial state distribution $\rho=\delta_{1}$ be defined by

Clearly, the value $V_{\rho}({\pi_{1},\pi_{2}})$ of the game depends only on the policies at state 1, i.e., $\pi_{1}(\cdot|1),\pi_{2}(\cdot|1)$. If $\pi_{1}(0|1)=\pi_{2}(1|1)=1$, then certainly $d^{\pi_{1},\pi_{2}}_{\rho}(3)>0$, and therefore $\max_{\pi_{1},\pi_{2}}\left\|\frac{d_{\rho}^{\pi_{1},\pi_{2}}}{\rho}\right\|_{\infty}$ is infinite.

On the other hand, let us now consider the best-response policies:

For any policy $\pi_{1}$ of the min-player, all policies $\pi_{2}\in\Pi_{2}^{*}(\pi_{1})$ of the max-player satisfy $\pi_{2}(0|1)=1$. This follows since player 2 prefers state 2 to state 3, and state 4 to state 5.

In particular, for any pair $(\pi_{1},\pi_{2})$ with $\pi_{2}\in\Pi_{2}^{*}(\pi_{1})$, we have that $d_{\rho}^{\pi_{1},\pi_{2}}(3)=0$.

For any policy $\pi_{2}$ of the max-player, all policies $\pi_{1}\in\Pi_{1}^{*}(\pi_{1})$ of the min-player satisfy $\pi_{1}(1|0)=1$. This follows since player 1 prefers state 4 to state 2, and state 5 to state 3.

In particular, for any pair $(\pi_{1},\pi_{2})$ with $\pi_{1}\in\Pi_{1}^{*}(\pi_{2})$, we have that $d_{\rho}^{\pi_{1},\pi_{2}}(3)=0$.

which completes the proof of the proposition. ∎

A.4 Supporting Lemmas

Suppose that players follow that $\varepsilon$-greedy direct parameterization in Assumption 1 with parameters $\varepsilon_{x}$ and $\varepsilon_{y}$. Given parameters $x\in\Delta(\mathcal{A})^{\left\lvert\mathcal{S}\right\rvert},y\in\Delta(\mathcal{A})^{\left\lvert\mathcal{S}\right\rvert}$ suppose the players estimate their gradients using the REINFORCE estimator:

under trajectories obtained by following $\pi_{x}$ and $\pi_{y}$. Then we have

We carry the calculation out for the $x$ player, as the $y$ player follows an identical argument. We start by proving that the gradient estimator is unbiased (i.e., (20)). Let $\mathcal{T}$ denote the (infinite) set of all possible trajectories, and for a trajectory $\tau=(s_{t},a_{t},b_{t},r_{t})_{0\leq t\leq T}$, in $\mathcal{T}$, let $R(\tau):=\sum_{t=0}^{T}r_{t}$ denote the total reward associated with $\tau$, and for policies $\pi_{1},\pi_{2}$, let

be the probability of realizing $\tau$. (Here, we let $s_{T+1}$ denote the event that the game stops at time $T$) Let $T(\tau)$ denote the last time step of trajectory $\tau$. Then

We proceed to bound the variance of the gradient estimator (i.e., establish (21)). Since the gradient estimator is unbiased, we have

where the equality is a consequence of the direct parameterization. We further simplify as

Define, for any $s_{0}\in\mathcal{S}$ and policies $\pi_{1},\pi_{2}$,

In the direct parameterization with $\varepsilon$-greedy exploration (Assumption 1), we have, for all $s\in\mathcal{S},a\in\mathcal{A},b\in\mathcal{B}$,

and so it follows that for all $\varepsilon_{x},\varepsilon_{y}\geq 0$,

As a consequence, $\left\|\nabla{}_{x}V_{\rho}(x,y)\right\|\leq{}\frac{\sqrt{A}}{\zeta^{2}}$ and $\left\|\nabla{}_{y}V_{\rho}(x,y)\right\|\leq{}\frac{\sqrt{B}}{\zeta^{2}}$.

Fix any initial state $s_{0}\in\mathcal{S}$. Note that

Note that the above calculation holds also when $s_{0}$ is replaced with any distribution $\rho\in\Delta(\mathcal{S})$. It follows by induction and the fact that $\operatorname{Pr}[T\geq t]\leq(1-\zeta)^{t}$ for any $t\geq 0$ that for any $\rho\in\Delta(\mathcal{S})$,

Thus, for any $s\in\mathcal{S},a\in\mathcal{A}$, we have

The inequality for the derivative with respect to $y$ follows in a symmetric manner. ∎

For all policies $\pi_{1},\pi_{1}^{\prime},\pi_{2},\pi_{2}^{\prime}$ and distributions $\rho\in\Delta(\mathcal{S})$,

The proof of the second inequality in the lemma is symmetric. ∎

Suppose that players follow the $\varepsilon$-greedy direct parameterization of Assumption 1 with parameters $\varepsilon_{x}$ and $\varepsilon_{y}$. Then for all $x\in\Delta(\mathcal{A})^{\left\lvert\mathcal{S}\right\rvert}$, $y\in\Delta(\mathcal{B})^{\left\lvert\mathcal{S}\right\rvert}$ we have

We prove the inequality for $x$ player. The inequality for the $y$ player follows by symmetry. For a policy $\pi_{y}$, let $\pi_{1}^{*}(\pi_{y})\in\Pi_{1}^{*}(\pi_{y})$ denote a policy minimizing $\left\|\frac{d_{\rho}^{\pi_{1},\pi_{y}}}{\rho}\right\|_{\infty}$ (whose existence follows from compactness of the space of policies).

Using the performance difference lemma, we have

where (24) follows from Proposition 3. Rearranging, this establishes that

The following lemma, which is a consequence of Lemma E.3 of Agarwal et al. (2020), establishes that the direct parameterization leads to Lipschitz gradients.

For all starting states $s_{0}$, and for all policies $x,x^{\prime},y,y^{\prime}$, it holds that

Appendix B Two-Timescale SGDA

Moreover, let $D_{\mathcal{X}}$ denote the diameter of $\mathcal{X}$ and $D_{\mathcal{Y}}$ denote the diameter of $\mathcal{Y}$. We make the following assumptions about $f(x,y)$. To state the assumption, let $y^{\star}(x)\in\operatorname*{arg\,max}_{y\in\mathcal{Y}}f(x,y)$ and $x^{\star}(y)\in\operatorname*{arg\,min}_{x\in\mathcal{X}}f(x,y)$ denote arbitrary best-response functions for the $y$ and $x$ players, respectively.

For some constants $\varepsilon_{y}\geq 0,\mu_{y}>0$, for each $x\in\mathcal{X}$, the function $y\mapsto f(x,y)$ satisfies the following gradient domination condition:

For some constants $\varepsilon_{x}\geq 0,\mu_{x}>0$, for each $y\in\mathcal{X}$, the function $x\mapsto f(x,y)$ satisfies the following gradient domination condition:

We formalize the stochastic first-order oracle model our algorithm works in as follows. In this section only, we will denote the iterates of stochastic gradient descent-ascent using $x_{t},y_{t}$ (as opposed to previous sections where we wrote $x^{(i)},y^{(i)}$).

For variance parameters $\sigma_{x},\sigma_{y}>0$, the stochastic oracle $G(x,y,\xi)=(G_{x}(x,y,\xi),G_{y}(x,y,\xi))$ satisfies:

Our main theorem for SGDA, Theorem 2a (the full version of Theorem 2), shows that if the learning rate $\eta_{x}$ of two-timescale SGDA is chosen sufficiently small relative to $\eta_{y}$, the iterates $x_{t}$ will approach, on average, the optimal point $x^{*}$.

for $T\geq\Omega\left(\frac{(D_{\mathcal{X}}+D_{\mathcal{Y}})L}{\epsilon^{2}\eta_{x}}\right)$.

B.2 Technical Preliminaries for Proof

Let $\Phi(x)=\max_{y\in\mathcal{Y}}f(x,y)$ and $x^{*}\in\arg\min_{x\in\mathcal{X}}\Phi(x)$.

The following theorem establishes some fundamental properties of $\Phi(x)$.

Descent lemmas for two-timescale SGDA.

Let $(x_{t},y_{t})$ denote the iterates of two-timescale SGDA, as in (25) and (26). Define $\Delta_{t}:=\Phi(x_{t})-f(x_{t},y_{t})$.

Since $\hat{x}_{t-1}\in\mathcal{X}$ and $x_{t}=\mathcal{P}_{\mathcal{X}}(x_{t-1}-\eta_{x}G_{x}(x_{t-1},y_{t-1},\xi_{t-1}))$, we have

Taking the expectation of both sides gives

By equations (30), (31), and (32), we get

For all $t\geq 1$, and $y\in\mathcal{Y}$, we have

Since for all $y^{\prime}\in\mathcal{Y}$ we have

Now let $\Gamma_{t}:=\|\nabla\psi_{t,\lambda}(y_{t})\|$. The following lemma shows that as long as $\Gamma_{t}$ stays large, $\psi_{t,\lambda}$ decreases each iteration (up to an error term controlled by the learning rate of the $x$ player).

Write $g_{t-1}=G_{y}(x_{t-1},y_{t-1},\xi_{t-1})$. Set

We next need the following lower bound on $\psi_{t-1,\lambda}(y_{t})$ in terms of $\psi_{t-1,\lambda}(y_{t-1})$; this calculation was carried out in Davis and Drusvyatskiy (2018b, Eqs. (2.4) – (2.6)), but we prove the following self-contained lemma after the conclusion of this proof for completeness.

The proof is exactly the argument in Davis and Drusvyatskiy (2018b, Eqs. (2.4) – (2.6)) and similar to that used in the proof of Lemma 7, but for completeness we repeat this calculation using our notation. In the setting of Lemma 9, set $\hat{y}_{t-1}:=\operatorname{prox}_{-\lambda\cdot\phi_{t-1}}(y_{t-1})$, and $g_{t-1}=G_{y}(x_{t-1},y_{t-1},\xi_{t-1})$. Then

B.3 Proof of Theorem 2a

Next, for a sufficiently large constant $C>0$ and for any $\epsilon>0$, set

as long as $C$ is sufficiently large, we get that

Here we have used that if $T$ is set as in (41), then

Finally, the guarantee for function value suboptimality follows by applying Lemma 12.

B.4 Supporting Lemmas

and the tangent cone of $\mathcal{X}$ at $x$ is the set

where ${\rm cl}$ denotes closure. It is well-known (Rockafellar, 1970) that for any $v\in N_{\mathcal{X}}(x)$, for all $u\in T_{\mathcal{X}}(x)$, we have that $\langle v,u\rangle\leq 0$ (in other words, $N_{\mathcal{X}}(x)$ is contained in the polar of $T_{\mathcal{X}}(x)$; in fact, $N_{\mathcal{X}}(x)$ is equal to the polar of $T_{\mathcal{X}}(x)$).

The first-order optimality conditions to (42) imply that

where $N_{\mathcal{X}}(\hat{x})$ denotes the normal cone of $\mathcal{X}$ at $\hat{x}$. Since for any $\bar{x}\in\mathcal{X}$, $\bar{x}-\hat{x}$ is in the tangent cone at $\hat{x}$, it follows that

Note that $\frac{1}{\lambda}(x-\hat{x})=\nabla\phi_{\lambda}(x)$. Thus, using also that $\phi$ is $L$-Lipschitz, we arrive at

The next lemma (Lemma 12) shows how to convert an $\epsilon$-approximate stationary point with respect to the Moreau envelope into an approximate minimizer for functions $f$ satisfying Assumption 2.

Suppose that $f$ satisfies the conditions of Assumption 2. Then for all $x\in\mathcal{X}$,

We first establish the statement of Lemma 12 for points $x\in\mathcal{X}$ for which $\Phi$ is differentiable at $x$. Suppose $x$ is such a point. Since a convex function is differentiable at a point if and only if its subgradient is a singleton at that point (Rockafellar, 1970, Theorem 25.1), it follows from (27) that $\partial\Phi(x)$ is a single vector, which we denote by $\nabla\Phi(x)$.

We first show that $\Phi(x)$ satisfies the following KL-type inequality (see also (Yang et al., 2020, Lemma A.3), which shows a similar statement):

To prove (44), fix any $y\in Y(x)$ (so that $f(x,y)=\Phi(x)$), and note that by item 3 of Assumption 2, we have that

Note note that since $f(x^{\prime},y)\leq\max_{y^{\prime}\in\mathcal{Y}}f(x^{\prime},y^{\prime})$ for each $x^{\prime}$,

By Danskin’s theorem (Theorem 3) we have that $\{\nabla\Phi(x)\}=\partial\Phi(x)=\operatorname{conv}\{\nabla_{x}f(x,y^{\prime}):y^{\prime}\in Y(x)\}$, so $\nabla_{x}f(x,y)=\nabla\Phi(x)$. From (45) and Cauchy-Schwarz it follows that

Item 1 of Lemma 5 gives that $\Phi$ is $L$-Lipschitz, and hence

Next we consider any point $x$ for which $\Phi$ is not differentiable at $x$. In the event that the interior $\mathcal{X}^{\circ}$ is dense in $\mathcal{X}$, we may apply (27) together with (Rockafellar, 1970, Theorem 25.5) to conclude that the set of points at which $\Phi$ is differentiable is dense in $\mathcal{X}^{\circ}$, and thus in $\mathcal{X}$. Let $x_{k}\rightarrow x$ be a convergent sequence of points approaching a point $x\in\mathcal{X}$ at which $\Phi(\cdot)$ is differentiable. Then the above argument establishes that for each $k$,

Finally, we consider the case that $\mathcal{X}^{\circ}$ is not dense in $\mathcal{X}$ (e.g., $\mathcal{X}^{\circ}$ may be empty). In this case we consider the neighborhood $\mathcal{X}_{\delta}\supset\supset\mathcal{X}$ defined in Remark 1, which have dense interior. Using the conclusion of the previous paragraph with $\mathcal{X}$ replaced by $\mathcal{X}_{\delta}$ gives that for all $x\in\mathcal{X}_{\delta}$,

For the iterates of two-timescale SGDA, we have

where we recall that $\Gamma_{t}\vcentcolon={}\|\nabla\psi_{t,\lambda}(y_{t})\|$.

Adding the inequality (33) for $t=1,2,\ldots,T$ and using Jensen’s inequality, we have

The conclusion (46) follows by Cauchy-Schwarz and the inequality $\sqrt{x+y}\leq\sqrt{x}+\sqrt{y}$ for $x,y\geq 0$.

Appendix C Proofs from Section 5.1

Below we prove Proposition 2. Recall that $V(x,y)=\frac{\langle x,Ry\rangle}{\langle x,Sy\rangle}$ with $R,S$ given by (12), and for $z=(x,y)$, $F(z)=(\nabla_{x}V(x,y)-\nabla_{y}V(x,y))$.

We first verify that $z^{\star}$ is the unique Nash equilibrium. Note that

The unique global minimum of $\Phi(\cdot)$ over $\mathcal{X}=\Delta(\mathcal{A})$ is at $(x_{1},x_{2})=(0,1)$, and the unique global maximum of $\Psi(\cdot)$ over $\mathcal{Y}=\Delta(\mathcal{B})$ is at $(y_{1},y_{2})=(0,1)$. This verifies that $z^{\star}$ is the unique global Nash equilibrium. The value of the game is $V(x^{\star},y^{\star})=0$.

Now consider the point $z=(x,y)$, where $x=y=(1,0)$. Then

which is negative for sufficiently small $\epsilon$ (in particular, for $\epsilon<\frac{1-s}{2s}$).

fails for all $\hat{z}=(\hat{x},\hat{y})$ which are not a Nash equilibrium. For any $\hat{z}$ which is not a Nash equilibrium, either the min-player or max-player can deviate from their policy in a way that increases their utility; we assume without loss it is the min-player (the case for the max-player is symmetric). In particular, there is some $x\in\mathcal{X}$ so that

It follows that $\langle x-\hat{x},\nabla_{x}V(\hat{x},\hat{y})\rangle<0$. For $\alpha\in$, define $x_{\alpha}=(1-\alpha)\hat{x}+\alpha x$. By continuity of the function $\alpha\mapsto\nabla_{x}V(x_{\alpha},\hat{y})$, there must be some $\alpha\in(0,1)$ so that

Letting $z:=(x_{\alpha},\hat{y})$, we obtain that $\langle z-\hat{z},F(z)\rangle<0$, violating (47). ∎

We remark that an alternative way to verify that $(x^{\star},y^{\star})$ is a Nash equilibrium in the above proof is as follows: we may calculate that

which shows that $x^{\star}$ satisfies the first-order optimality conditions for minimizing $x\mapsto V(x,y^{\star})$, and $y^{\star}$ satisfies the first-order optimality conditions for maximizing $y\mapsto V(x^{\star},y)$. It is then straightforward to check that in fact $x^{\star}$ is a global minimizer of $x\mapsto V(x,y^{\star})$, and $y^{\star}$ is a global minimizer of $y\mapsto V(x^{\star},y)$.

Figure 1(a) and Figure 1(b) use the following game, which is the game from Proposition 2 with $\epsilon=0.1,s=0.3$:

Figure 1(c) and Figure 1(d) use the following game, which is a rounded version of a game we found via a random search: