Bandit learning in concave $N$-person games

Introduction

The bane of decision-making in an unknown environment is regret: noone wants to realize in hindsight that the decision policy they employed was strictly inferior to a plain policy prescribing the same action throughout. For obvious reasons, this issue becomes considerably more intricate when the decision-maker is subject to situational uncertainty and the “fog of war”: when the only information at the optimizer’s disposal is the reward obtained from a given action (the so-called “bandit” framework), is it even possible to design a no-regret policy? Especially in the context of online convex optimization (repeated decision problems with continuous action sets and convex costs), this problem becomes even more challenging because the decision-maker typically needs to infer gradient information from the observation of a single scalar. Nonetheless, despite this extra degree of difficulty, this question has been shown to admit a positive answer: regret minimization is possible, even with bandit feedback (Kleinberg, 2004; Flaxman et al., 2005).

In this paper, we consider a multi-agent extension of this framework where, at each stage $n=1,2,\dotsc$, of a repeated decision process, the reward of an agent is determined by the actions of all agents via a fixed mechanism: a non-cooperative $N$-person game. In general, the agents – or players – might be completely oblivious to this mechanism, perhaps even ignoring its existence: for instance, when choosing how much to bid for a good in an online auction, an agent is typically unaware of who the other bidders are, what are their specific valuations, etc. Hence, lacking any knowledge about the game, it is only natural to assume that agents will at least seek to achieve a minimal worst-case guarantee and minimize their regret. As a result, a fundamental question that arises is a) whether the agents’ sequence of actions stabilizes to a rationally admissible state under no-regret learning; and b) if it does, whether convergence is affected by the information available to the agents.

In finite games, no-regret learning guarantees that the players’ time-averaged, empirical frequency of play converges to the game’s set of coarse correlated equilibria, and the rate of this convergence is $\operatorname{\mathcal{O}}(1/n)$ for $(\lambda,\mu)$-smooth games (Syrgkanis et al., 2015; Foster et al., 2016). In general however, this set might contain highly subpar, rationally inadmissible strategies: for instance, Viossat and Zapechelnyuk (2013) provide examples of CCE that assign positive selection probability only to strictly dominated strategies. In the class of potential games, Cohen et al. (2017) recently showed that the actual sequence of play (i.e., the sequence of actions that determine the agents’ rewards at each stage) converges under no-regret learning, even with bandit feedback. Outside this class however, the players’ chosen actions may cycle in perpetuity, even in simple, two-player zero-sum games with full information (Mertikopoulos et al., 2018b, a); in fact, depending on the parameters of the players’ learning process, agents could even exhibit a fully unpredictable, aperiodic and chaotic behavior (Palaiopanos et al., 2017). As such, without further assumptions in place, no-regret learning in a multi-agent setting does not necessarily imply convergence to a unilaterally stable, equilibrium state.

In the broader context of games with continuous action sets (the focal point of this paper), the long-run behavior of no-regret learning is significantly more challenging to analyze. In the case of mixed-strategy learning, Perkins and Leslie (2014) and Perkins et al. (2017) showed that mixed-stratgy learning based on stochastic fictitious play converges to an $\varepsilon$-perturbed Nash equilibrium in potential games (but may lead to as much as $\operatorname{\mathcal{O}}(\varepsilon n)$ regret in the process). More relevant for our purposes is the analysis of Nesterov (2009) who showed that the time-averaged sequence of play induced by a no-regret dual averaging (DA) process with noisy gradient feedback converges to Nash equilibrium in monotone games (a class which, in turn, contains all concave potential games).

The closest antecedent to our approach is the recent work of Mertikopoulos and Zhou (2018) who showed that the actual sequence of play generated by dual averaging converges to Nash equilibrium in the class of variationally stable games (which includes all monotone games). To do so, the authors first showed that a naturally associated continuous-time dynamical system converges, and then used the so-called asymptotic pseudotrajectory (APT) framework of Benaïm (1999) to translate this result to discrete time. Similar asymptotic pseudotrajectory (APT) techniques were also used in a very recent preprint by Bervoets et al. (2018) to establish the convergence of a payoff-based learning algorithm in two classes of one-dimensional concave games: games with strategic complements, and ordinal potential games with isolated equilibria. The algorithm of Bervoets et al. (2018) can be seen as a special case of mirror descent coupled with a two-point gradient estimation process, suggesting several interesting links with our paper.

Our contributions.

In this paper, we drop all feedback assumptions and we focus on the bandit framework where the only information at the players’ disposal is the payoffs they receive at each stage. As we discussed above, this lack of information complicates matters considerably because players must now estimate their payoff gradients from their observed rewards. What makes matters even worse is that an agent may introduce a significant bias in the (concurrent) estimation process of another, so traditional, multiple-point estimation techniques for derivative-free optimization cannot be applied (at least, not without significant communication overhead between players).

To do away with player coordination requirements, we focus on learning processes which could be sensibly deployed in a single-agent setting and we show that, in monotone games, the sequence of play induced by a wide class of no-regret learning policies converges to Nash equilibrium with probability $1$. Furthermore, by specializing to the class of strongly monotone games, we show that the rate of convergence is $\operatorname{\mathcal{O}}(n^{-1/3})$, i.e., it is nearly optimal with respect to the attainable $\operatorname{\mathcal{O}}(n^{-1/2})$ rate for bandit, single-agent stochastic optimization with strongly convex and smooth objectives (Agarwal et al., 2010; Shamir, 2013).

We are not aware of a similar Nash equilibrium convergence result for concave games with general convex action spaces and bandit feedback: the analysis of Mertikopoulos and Zhou (2018) requires first-order feedback, while the analysis of Bervoets et al. (2018) only applies to one-dimensional games. We find this outcome particularly appealing for practical applications of game theory (e.g., in network routing) because it shows that in a wide class of (possibly very complicated) nonlinear games, the Nash equilibrium prediction does not require full rationality, common knowledge of rationality, flawless execution, or even the knowledge that a game is being played: a commonly-used, individual no-regret algorithm suffices.

Problem setup and preliminaries

With all this in hand, a concave game will be a tuple $\mathcal{G}\equiv\mathcal{G}(\mathcal{N},\mathcal{X},u)$ with players, action spaces and payoffs defined as above. Below, we briefly discuss some examples thereof:

i.e., it comprises the total revenue from producing $x_{i}$ units of the good in question minus the associated production cost (in the above, $c_{i}>0$ represents the marginal production cost of firm $i$).

Consider a service provider with a number of splittable resources $s\in\mathcal{S}=\{1,\dotsc,S\}$ (bandwidth, server time, GPU cores, etc.). These resources can be leased to a set of $N$ bidders (players) who can place monetary bids $x_{is}\geq 0$ for the utilization of each resource $s\in\mathcal{S}$ up to each player’s total budget $b_{i}$, i.e., $\sum_{s\in\mathcal{S}}x_{is}\leq b_{i}$. Once all bids are in, resources are allocated proportionally to each player’s bid, i.e., the $i$-th player gets \rho_{is}=(q_{s}x_{is})\big{/}(c_{s}+\sum_{j\in\mathcal{N}}x_{js}) units of the $s$-th resource (where $q_{s}$ denotes the available units of said resource and $c_{s}\geq 0$ is the “entry barrier” for bidding on it). A simple model for the utility of player $i$ is then given by

with $g_{i}$ denoting the marginal gain of player $i$ from acquiring a unit slice of resources.

2. Nash equilibrium and monotone games.

The most widely used solution concept for non-cooperative games is that of a Nash equilibrium (NE), defined here as any action profile $x^{\ast}\in\mathcal{X}$ that is resilient to unilateral deviations, viz.

By the classical existence theorem of Debreu (1952), every concave game admits a Nash equilibrium. Moreover, thanks to the individual concavity of the game’s payoff functions, Nash equilibria can also be characterized via the first-order optimality condition

where $v_{i}(x)$ denotes the individual payoff gradient of the $i$-th player, i.e.,

with $\operatorname{\nabla\!}_{i}$ denoting differentiation with respect to $x_{i}$.We adopt here the standard convention of treating $v_{i}(x)$ as an element of the dual space $\mathcal{Y}_{i}\equiv\mathcal{V}^{\ast}_{i}$ of $\mathcal{V}_{i}$, with $\langle y_{i},x_{i}\rangle$ denoting the duality pairing between $y_{i}\in\mathcal{Y}_{i}$ and $x_{i}\in\mathcal{X}_{i}\subseteq\mathcal{V}_{i}$. In terms of regularity, it will be convenient to assume that each $v_{i}$ is Lipschitz continuous; to streamline our presentation, this will be our standing assumption in what follows.

Starting with the seminal work of Rosen (1965), much of the literature on continuous games and their applications has focused on games that satisfy a condition known as diagonal strict concavity (DSC). In its simplest form, this condition posits that there exist positive constants $\lambda_{i}>0$ such that

Owing to the formal similarity between (DSC) and the various operator monotonicity conditions in optimization (see e.g., Bauschke and Combettes, 2017), games that satisfy (DSC) are commonly referred to as (strictly) monotone. As was shown by Rosen (1965, Theorem 2), monotone games admit a unique Nash equilibrium $x^{\ast}\in\mathcal{X}$, which, in view of (DSC) and (NE), is also the unique solution of the (weighted) variational inequality

This property of Nash equilibria of monotone games will play a crucial role in our analysis and we will use it freely in the rest of our paper.

Regularized no-regret learning

We now turn to the learning methods that players could employ to increase their individual rewards in an online manner. Building on Zinkevich’s (2003) online gradient descent policy, the most widely used algorithmic schemes for no-regret learning in the context of online convex optimization invariably revolve around the idea of regularization. To name but the most well-known paradigms, “following the regularized leader” (FTRL) explicitly relies on best-responding to a regularized aggregate of the reward functions revealed up to a given stage, while online mirror descent (OMD) and its variants use a linear surrogate thereof. All these no-regret policies fall under the general umbrella of “regularized learning” and their origins can be traced back to the seminal mirror descent (MD) algorithm of Nemirovski and Yudin (1983).In a utility maximization setting, mirror descent should be called mirror ascent because players seek to maximize their rewards (as opposed to minimizing their losses). Nonetheless, we keep the term “descent” throughout because, despite the role reversal, it is the standard name associated with the method.

for all $x_{i},x^{\prime}_{i}\in\mathcal{X}_{i}$ and all $t\in$. In terms of smoothness (and in a slight abuse of notation) we also assume that the subdifferential of $h_{i}$ admits a continuous selection, i.e., a continuous function $\nabla h_{i}\colon\operatorname{dom}\partial h_{i}\to\mathcal{Y}_{i}$ such that $\nabla h_{i}(x_{i})\in\partial h_{i}(x_{i})$ for all $x_{i}\in\operatorname{dom}\partial h_{i}$.Recall here that the subdifferential of $h_{i}$ at $x_{i}\in\mathcal{X}_{i}$ is defined as $\partial h_{i}(x_{i})\equiv\{y_{i}\in\mathcal{Y}_{i}:h_{i}(x^{\prime}_{i})\geq h_{i}(x_{i})+\langle y_{i},x^{\prime}_{i}-x_{i}\rangle\;\text{for all}\;x^{\prime}_{i}\in\mathcal{V}_{i}\},$ with the standard convention that $h_{i}(x_{i})=+\infty$ if $x_{i}\in\mathcal{V}_{i}\setminus\mathcal{X}_{i}$. By standard results, the domain of subdifferentiability $\partial h_{i}\equiv\{x_{i}\in\mathcal{X}_{i}:\partial h_{i}\neq\varnothing\}$ of $h_{i}$ satisfies $\mathcal{X}^{\circ}_{i}\subseteq\operatorname{dom}\partial h_{i}\subseteq\mathcal{X}_{i}$. Then, letting $h(x)=\sum_{i}h_{i}(x_{i})$ for $x\in\mathcal{X}$ (so $h$ is strongly convex with modulus $K=\min_{i}K_{i}$), we get a pseudo-distance on $\mathcal{X}$ via the relation

for all $p\in\mathcal{X}$, $x\in\operatorname{dom}\partial h$.

This pseudo-distance is known as the Bregman divergence and we have $D(p,x)\geq 0$ with equality if and only if $x=p$; on the other hand, $D$ may fail to be symmetric and/or satisfy the triangle inequality so, in general, it is not a bona fide distance function on $\mathcal{X}$. Nevertheless, we also have $D(p,x)\geq\frac{1}{2}K\lVert x-p\rVert^{2}$ (see the paper’s supplement), so the convergence of a sequence $X_{n}$ to $p$ can be checked by showing that $D(p,X_{n})\to 0$. For technical reasons, it will be convenient to also assume the converse, i.e., that $D(p,X_{n})\to 0$ when $X_{n}\to p$. This condition is known in the literature as “Bregman reciprocity” (Chen and Teboulle, 1993), and it will be our blanket assumption in what follows (note that it is trivially satisfied by Examples 3.1 and 3.2 below).

Now, as with true Euclidean distances, $D(p,x)$ induces a prox-mapping given by

for all $x\in\operatorname{dom}\partial h$ and all $y\in\mathcal{Y}$. Just like its Euclidean counterpart below, the prox-mapping (3.3) starts with a point $x\in\operatorname{dom}\partial h$ and steps along the dual (gradient-like) vector $y\in\mathcal{Y}$ to produce a new feasible point $x^{+}=P_{x}(y)$. Standard examples of this process are:

Let $h(x)=\frac{1}{2}\lVert x\rVert_{2}^{2}$ denote the Euclidean squared norm. Then, the induced prox-mapping is

with $\operatorname{\Pi}(x)=\operatorname*{arg\,min}_{x^{\prime}\in\mathcal{X}}\lVert x^{\prime}-x\rVert^{2}$ denoting the standard Euclidean projection onto $\mathcal{X}$. Hence, the update rule $x^{+}=P_{x}(y)$ boils down to a “vanilla”, Euclidean projection step along $y$.

for all $x\in\mathcal{X}^{\circ}$, $y\in\mathcal{Y}$. The update rule $x^{+}=P_{x}(y)$ is widely known as the multiplicative weights (MW) algorithm and plays a central role for learning in multi-armed bandit problems and finite games (Auer et al., 1995; Freund and Schapire, 1999; Arora et al., 2012).

With all this in hand, the multi-agent mirror descent (MD) algorithm is given by the recursion

where $\gamma_{n}$ is a variable step-size sequence and $\hat{v}_{n}=(\hat{v}_{i,n})_{i\in\mathcal{N}}$ is a generic feedback sequence of estimated gradients. In the next section, we detail how this sequence is generated with first- or zeroth-order (bandit) feedback.

First-order vs. bandit feedback

A common assumption in the literature is that players are able to obtain gradient information by querying a first-order oracle (Nesterov, 2004). i.e., a “black-box” feedback mechanism that outputs an estimate $\hat{v}_{i}$ of the individual payoff gradient $v_{i}(x)$ of the $i$-th player at the current action profile $x=(x_{i};x_{-i})\in\mathcal{X}$. This estimate could be either perfect, giving $\hat{v}_{i}=v_{i}(x)$ for all $i\in\mathcal{N}$, or imperfect, returning noisy information of the form $\hat{v}_{i}=v_{i}(x)+U_{i}$ where $U_{i}$ denotes the oracle’s error (random, systematic, or otherwise).

Having access to a perfect oracle is usually a tall order, either because payoff gradients are difficult to compute directly (especially without global knowledge), because they involve an expectation over a possibly unknown probability law, or for any other number of reasons. It is therefore more common to assume that each player has access to a stochastic oracle which, when called against a sequence of actions $X_{n}\in\mathcal{X}$, produces a sequence of gradient estimates $\hat{v}_{n}=(v_{i,n})_{i\in\mathcal{N}}$ that satisfies the following statistical assumptions:

2. Bandit feedback.

Now, if players don’t have access to a first-order oracle – the so-called bandit or payoff-based framework – they will need to derive an individual gradient estimate from the only information at their disposal: the actual payoffs they receive at each stage. When a function can be queried at multiple points (as few as two in practice), there are efficient ways to estimate its gradient via directional sampling techniques as in Agarwal et al. (2010). In a game-theoretic setting however, multiple-point estimation techniques do not apply because, in general, a player’s payoff function depends on the actions of all players. Thus, when a player attempts to get a second query of their payoff function, this function may have already changed due to the query of another player – i.e., instead of sampling $u_{i}(\cdot;x_{-i})$, the $i$-th player would be sampling $u_{i}(\cdot;x^{\prime}_{-i})$ for some $x^{\prime}_{-i}\neq x_{-i}$.

Following Spall (1997) and Flaxman et al. (2005), we posit instead that players rely on a simultaneous perturbation stochastic approximation (SPSA) approach that allows them to estimate their individual payoff gradients $v_{i}$ based off a single function evaluation. In detail, the key steps of this one-shot estimation process for each player $i\in\mathcal{N}$ are:

Fix a query radius $\delta>0$.For simplicity, we take $\delta$ equal for all players; the extension to player-specific $\delta$ is straightforward, so we omit it.

Pick a pivot point $x_{i}\in\mathcal{X}_{i}$ where player $i$ seeks to estimate their payoff gradient.

Receive $\hat{u}_{i}=u_{i}(\hat{x}_{i};\hat{x}_{-i})$ and set

By adapting a standard argument based on Stokes’ theorem (detailed in the supplement), it can be shown that $\hat{v}_{i}$ is an unbiased estimator of the individual gradient of the $\delta$-smoothed payoff function

The second feasibility issue concerns the size of the perturbation step: even if $z_{i}$ is a feasible direction of motion, the query point $\hat{x}_{i}=x_{i}+\delta z_{i}$ may be unfeasible if $x_{i}$ is too close to the boundary of $\mathcal{X}_{i}$. For this reason, we will introduce a “safety net” in the spirit of Agarwal et al. (2010), and we will constrain the set of possible pivot points $x_{i}$ to lie within a suitably shrunk zone of $\mathcal{X}$.

and each player plays $\hat{x}_{i}=x_{i}+\delta w_{i}$ instead of $x_{i}+\delta z_{i}$. In other words, this adjustment moves each pivot to $x_{i}^{\delta}=x_{i}-r_{i}^{-1}\delta(x_{i}-p_{i})$, i.e., $\operatorname{\mathcal{O}}(\delta)$-closer to the interior base point $p_{i}$, and then perturbs $x_{i}^{\delta}$ by $\delta z_{i}$. Feasibility of the query point is then ensured by noting that

The difference between this estimator and the oracle framework we discussed above is twofold. First, each player’s realized action is $\hat{x}_{i}=x_{i}+\delta w_{i}$, not $x_{i}$, so there is a disparity between the point at which payoffs are queried and the action profile where the oracle is called. Second, the resulting estimator $\hat{v}$ is not unbiased, so the statistical assumptions (4.1) for a stochastic oracle do not hold. In particular, given the feasibility adjustment (4.4), the estimate (4.2) with $\hat{x}$ given by (4.5) satisfies

so there are two sources of systematic error: an $\operatorname{\mathcal{O}}(\delta)$ perturbation in the function, and an $\operatorname{\mathcal{O}}(\delta)$ perturbation of each player’s pivot point from $x_{i}$ to $x_{i}^{\delta}$. Hence, to capture both sources of bias and separate them from the random noise, we will write

Convergence analysis and results

Combining the learning framework of Section 3 with the single-shot gradient estimation machinery of Section 4, we obtain the following variant of (MD) with payoff-based, bandit feedback:

In the above, the perturbations $W_{n}$ and the estimates $\hat{v}_{n}$ are given respectively by (4.4) and (4.2), i.e.,

and $Z_{i,n}$ is drawn independently and uniformly across players at each stage $n$ (see also Algorithm 1 for a pseudocode implementation and Fig. 1 for a schematic representation).

In the rest of this paper, our goal will be to determine the equilibrium convergence properties of this scheme in concave $N$-person games. Our first asymptotic result below shows that, under (MD-b), the players’ learning process converges to Nash equilibrium in monotone games:

Suppose that the players of a monotone game $\mathcal{G}\equiv\mathcal{G}(\mathcal{N},\mathcal{X},u)$ follow (MD-b) with step-size $\gamma_{n}$ and query radius $\delta_{n}$ such that

Then, the sequence of realized actions $\hat{X}_{n}$ converges to Nash equilibrium with probability $1$.

Even though the setting is different, the conditions (5.2) for the tuning of the algorithm’s parameters are akin to those encountered in Kiefer–Wolfowitz stochastic approximation schemes and serve a similar purpose. First, the conditions $\lim_{n\to\infty}\gamma_{n}=0$ and $\sum_{n=1}^{\infty}\gamma_{n}=\infty$ respectively mitigate the method’s inherent randomness and ensure a horizon of sufficient length. The requirement $\lim_{n\to\infty}\delta_{n}=0$ is also straightforward to explain: as players accrue more information, they need to decrease the sampling bias in order to have any hope of converging. However, as we discussed in Section 4, decreasing $\delta$ also increases the variance of the players’ gradient estimates, which might grow to infinity as $\delta\to 0$. The crucial observation here is that new gradients enter the algorithm with a weight of $\gamma_{n}$ so the aggregate bias after $n$ stages is of the order of $\operatorname{\mathcal{O}}(\sum_{k=1}^{n}\gamma_{k}\delta_{k})$ and its variance is $\operatorname{\mathcal{O}}(\sum_{k=1}^{n}\gamma_{k}^{2}/\delta_{k}^{2})$. If these error terms can be controlled, there is an underlying drift that emerges over time and which steers the process to equilibrium. We make this precise in the supplement by using a suitably adjusted variant of the Bregman divergence as a quasi-Féjér energy function for (MD-b) and relying on a series of (sub)martingale convergence arguments to establish the convergence of $\hat{X}_{n}$ (first as a subsequence, then with probability $1$).

Of course, since Theorem 5.1 is asymptotic in nature, it is not clear how to choose $\gamma_{n}$ and $\delta_{n}$ so as to optimize the method’s convergence rate. Heuristically, if we take schedules of the form $\gamma_{n}=\gamma/n^{p}$ and $\delta_{n}=\delta/n^{q}$ with $\gamma,\delta>0$ and $0<p,q\leq 1$, the only conditions imposed by (5.2) are $p+q>1$ and $p-q>1/2$. However, as we discussed above, the aggregate bias in the algorithm after $n$ stages is $\operatorname{\mathcal{O}}(\sum_{k=1}^{n}\gamma_{n}\delta_{n})=\operatorname{\mathcal{O}}(1/n^{p+q-1})$ and its variance is $\operatorname{\mathcal{O}}(\sum_{k=1}^{n}\gamma_{k}^{2}/\delta_{k}^{2})=\operatorname{\mathcal{O}}(1/n^{2p-2q-1})$: if the conditions (5.2) are satisfied, both error terms vanish, but they might do so at very different rates. By equating these exponents in order to bridge this gap, we obtain $q=p/3$; moreover, since the single-shot SPSA estimator (4.2) introduces a $\Theta(\delta_{n})$ random perturbation, $q$ should be taken as large as possible to ensure that this perturbation vanishes at the fastest possible rate. As a result, the most suitable choice for $p$ and $q$ seems to be $p=1$, $q=1/3$, leading to an error bound of $\operatorname{\mathcal{O}}(1/n^{1/3})$.

We show below that this bound is indeed attainable for games that are strongly monotone, i.e., they satisfy the following stronger variant of diagonal strict concavity:

for some $\lambda_{i},\beta>0$ and for all $x,x^{\prime}\in\mathcal{X}$. Focusing for expository reasons on the most widely used, Euclidean incarnation of the method (Example 3.1), we have:

Let $x^{\ast}$ be the (necessarily unique) Nash equilibrium of a $\beta$-strongly monotone game. If the players follow (MD-b) with Euclidean projections and parameters $\gamma_{n}=\gamma/n$ and $\delta_{n}=\delta/n^{1/3}$ with $\gamma>1/(3\beta)$ and $\delta>0$, we have

Theorem 5.2 is our main finite-time analysis result, so some remarks are in order. First, the step-size schedule $\gamma_{n}\propto 1/n$ is not required to obtain an $\operatorname{\mathcal{O}}(n^{-1/3})$ convergence rate: as we show in the paper’s supplement, more general schedules of the form $\gamma_{n}\propto 1/n^{p}$ and $\delta_{n}\propto 1/n^{q}$ with $p>3/4$ and $q=p/3>1/4$, still guarantee an $\operatorname{\mathcal{O}}(n^{-1/3})$ rate of convergence for (MD-b). To put things in perspective, we also show in the supplement that if (MD) is run with first-order oracle feedback satisfying the statistical assumptions (4.1), the rate of convergence becomes $\operatorname{\mathcal{O}}(1/n)$. Viewed in this light, the price for not having access to gradient information is no higher than $\operatorname{\mathcal{O}}(n^{-2/3})$ in terms of the players’ equilibration rate.

Finally, it is also worth comparing the bound (D.2) to the attainable rates for stochastic convex optimization (the single-player case). For problems with objectives that are both strongly convex and smooth, Agarwal et al. (2010) attained an $\operatorname{\mathcal{O}}(n^{-1/2})$ convergence rate with bandit feedback, which Shamir (2013) showed is unimprovable. Thus, in the single-player case, the bound (D.2) is off by $n^{1/6}$ and coincides with the bound of Agarwal et al. (2010) for strongly convex functions that are not necessarily smooth. One reason for this gap is that the $\Theta(n^{-1/2})$ bound of Shamir (2013) concerns the smoothed-out time average $\bar{X}_{n}=n^{-1}\sum_{k=1}^{n}X_{k}$, while our analysis concerns the sequence of realized actions $\hat{X}_{n}$. This difference is semantically significant: In optimization, the query sequence is just a means to an end, and only the algorithm’s output matters (i.e., $\bar{X}_{n}$). In a game-theoretic setting however, it is the players’ realized actions that determine their rewards at each stage, so the figure of merit is the actual sequence of play $\hat{X}_{n}$. This sequence is more difficult to control, so this disparity is, perhaps, not too surprising; nevertheless, we believe that this gap can be closed by using a more sophisticated single-shot estimate, e.g., as in Ghadimi and Lan (2013). We defer this analysis to the future.

Concluding remarks

The most sensible choice for agents who are oblivious to the presence of each other (or who are simply conservative), is to deploy a no-regret learning algorithm. With this in mind, we studied the long-run behavior of individual regularized no-regret learning policies and we showed that, in monotone games, play converges to equilibrium with probability $1$, and the rate of convergence almost matches the optimal rates of single-agent, stochastic convex optimization. Nevertheless, several questions remain open: whether there is an intrinsic information-theoretic obstacle to bridging this gap; whether our convergence rate estimates hold with high probability (and not just in expectation); and whether our analysis extends to a fully decentralized setting where the players’ updates need not be synchronous. We intend to address these questions in future work.

Appendix A Monotone games

Our aim in this appendix is to show that the game-theoretic examples of Section 2 are both monotone. Before studying them in detail, it will be convenient to introduce a straightforward second-order test for monotonicity based on the game’s Hessian matrix.

Specifically, extending the notion of the Hessian of an ordinary (scalar) function, the ($\lambda$-weighted) Hessian of a game $\mathcal{G}$ is defined as the block matrix $H_{\mathcal{G}}(x;\lambda)=(H_{ij}(x;\lambda))_{i,j\in\mathcal{N}}$ with blocks

As was shown by Rosen (1965, Theorem 6), $\mathcal{G}$ satisifes (DSC) with weight vector $\lambda$ whenever $z^{\top}H_{\mathcal{G}}(x;\lambda)z<0$ for all $x\in\mathcal{X}$ and all nonzero $z\in\mathcal{V}\equiv\prod_{i}\mathcal{V}_{i}$ that are tangent to $\mathcal{X}$ at $x$.By “tangent” we mean here that $z$ belongs to the tangent cone $\operatorname{TC}(x)$ to $\mathcal{X}$ at $x$, i.e., the intersection of all supporting (closed) half-spaces of $\mathcal{X}$ at $x$. It is thus common to check for monotonicity by taking $\lambda_{i}=1$ for all $i\in\mathcal{N}$ and verifying whether the unweighted Hessian of $\mathcal{G}$ is negative-definite on the affine hull of $\mathcal{X}$.

In the standard Cournot oligopoly model described in the main body of the paper, the players’ payoff functions are given by

Consequently, a simple differentiation yields

where $\delta_{ij}=\operatorname{\mathds{1}}\{i=j\}$ is the Kronecker delta. This matrix is clearly negative-definite, so the game is monotone.

A.2. Resource allocation auctions (Example 2.2).

In our auction-theoretic example, the players’ payoff functions are given by

To prove monotonicity in this example, we will consider the following criterion due to Goodman (1980): a game $\mathcal{G}$ satisfies (DSC) with weights $\lambda_{i}$, $i\in\mathcal{N}$, if:

Each payoff function $u_{i}$ is strictly concave in $x_{i}$ and convex in $x_{-i}$.

The function $\sum_{i\in\mathcal{N}}\lambda_{i}u_{i}(x)$ is concave in $x$.

Since the function $\phi(x)=x/(c+x)$ is strictly concave in $x$ for all $c>0$, the first condition above is trivial to verify. For the second, letting $\lambda_{i}=1/g_{i}$ gives

Since the summands above are all concave in their respective arguments, our claim follows.

Appendix B Properties of Bregman proximal mappings

In this appendix, we provide some auxiliary results and estimates that are used throughout the convergence analysis of Appendix C. Some of the results we present here are not new (see e.g., Nemirovski et al., 2009); however, the set of hypotheses used to obtain them varies widely in the literature, so we provide all proofs for completeness.

By standard results in convex analysis (Rockafellar, 1970, Chap. 26), $h^{\ast}$ is differentiable on $\mathcal{Y}$ and its gradient satisfies the identity

For notational convenience, we will also write

and we will refer to $Q\colon\mathcal{Y}\to\mathcal{X}$ as the mirror map generated by $h$.

Together with the prox-mapping induced by $h$, all these notions are related as follows:

Let $h$ be a regularizer on $\mathcal{X}$. Then, for all $x\in\operatorname{dom}\partial h$, $y\in\mathcal{Y}$, we have:

Finally, if $x=Q(y)$ and $p\in\mathcal{X}$, we have

Note that (B.4b) directly implies that $\partial h(x^{+})\neq\varnothing$, i.e., $x^{+}\in\operatorname{dom}\partial h$. An immediate consequence of this is that the update rule $x\leftarrow P_{x}(y)$ is well-posed, i.e., it can be iterated in perpetuity.

To prove (B.4a), note that $x$ solves (B.2) if and only if $y-\partial h(x)\ni 0$, i.e., if and only if $y\in\partial h(x)$. Similarly, for (B.4b), comparing (3.3) and (B.1), we see that $x^{+}$ solves (3.3) if and only if $\nabla h(x)+y\in\partial h(x^{+})$, i.e., if and only if $x^{+}=Q(\nabla h(x)+y)$.

For the inequality (B.5), it suffices to show it holds for interior $p\in\mathcal{X}^{\circ}$ (by continuity). To do so, let

Since $h$ is strongly convex and $y\in\partial h(x)$ by (B.4a), it follows that $\phi(t)\geq 0$ with equality if and only if $t=0$. Moreover, note that $\psi(t)=\langle\nabla h(x+t(p-x))-y,p-x\rangle$ is a continuous selection of subgradients of $\phi$. Given that $\phi$ and $\psi$ are both continuous on $$, it follows that$\phi$is continuously differentiable and$\phi^{\prime}=\psi$on$$. Thus, with$\phi$convex and$\phi(t)\geq 0=\phi(0)$for all$t\in$, we conclude that$\phi^{\prime}(0)=\langle\nabla h(x)-y,p-x\rangle\geq 0$, from which our claim follows. ∎

We continue with some basic relations connecting the Bregman divergence relative to a target point before and after a prox step. The basic ingredient for this is a generalization of the law of cosines which is known in the literature as the “three-point identity” (Chen and Teboulle, 1993):

Let $h$ be a regularizer on $\mathcal{X}$. Then, for all $p\in\mathcal{X}$ and all $x,x^{\prime}\in\operatorname{dom}\partial h$, we have

The lemma then follows by adding the two last lines and subtracting the first. ∎

With all this at hand, we have the following upper and lower bounds:

Let $h$ be a $K$-strongly convex regularizer on $\mathcal{X}$, fix some $p\in\mathcal{X}$, and let $x^{+}=P_{x}(y)$ for $x\in\operatorname{dom}\partial h$, $y\in\mathcal{Y}$. Then, we have:

so (B.9a) follows by gathering all terms involving $h$ and recalling the definition of $D(p,x)$. ∎

By the three-point identity (B.7), we readily obtain

where, in the last step, we used (B.5) and the fact that $x^{+}=Q(\nabla h(x)+y)$, by (B.4b), since $x^{+}=P_{x}(y)$. The above is just (B.9b), so the first part of our proof is complete.

To proceed with the proof of (B.9c), note that (B) gives

By Young’s inequality (Rockafellar, 1970), we also have

with the last step following from Lemma B.1 after plugging in $x$ in place of $p$. ∎

Appendix C Asymptotic convergence analysis

Our goal in this appendix is to prove Theorem 5.1. Our proof strategy will be based on a two-pronged approach. First, we will show that the pivot sequence $X_{n}$ satisfies a “quasi-Fejér” property (Combettes, 2001; Combettes and Pesquet, 2015) with respect to the Bregman divergence. This quasi-Fejér property allows us to show that the Bregman divergence $D(x^{\ast},X_{n})$ with respect to a Nash equilibrium $x^{\ast}$ of $\mathcal{G}$ converges. To show that this limit is actually zero for some Nash equilibrium, we prove that, with probability $1$, the sequence $X_{n}$ admits a (random) subsequence that converges to a Nash equilibrium. The theorem then follows by combining these two results.

To carry all this out, we begin with an auxiliary lemma for the SPSA estimation process of Section 4:

The SPSA estimator $\hat{v}=(\hat{v}_{i})_{i\in\mathcal{N}}$ given by (4.2) satisfies

with $u_{i}^{\delta}$ as in (4.3). Moreover, we have $\lVert\operatorname{\nabla\!}_{i}u_{i}^{\delta}-\operatorname{\nabla\!}_{i}u_{i}\rVert_{\infty}=\operatorname{\mathcal{O}}(\delta)$.

By the independence of the sampling directions $z_{i}$, $i\in\mathcal{N}$, we have

where, in the last line, we used the identity

Our assertion then follows by integrating and differentiating under the integral sign. ∎

With this basic estimate at hand, we proceed to establish the convergence of the Bregman divergence relative to the game’s Nash equilibria:

Let $x^{\ast}$ be a Nash equilibrium of $\mathcal{G}$. Then, with assumptions as in Theorem 5.1, the Bregman divergence $D(x^{\ast},X_{n})$ converges (a.s.) to a finite random variable $D_{\infty}$.

For expository reasons, we tacitly assume above (and in what follows) that $\mathcal{G}$ satisfies (DSC) with weights $\lambda_{i}=1$ for all $i\in\mathcal{N}$. If this is not the case, the Bregman divergence $D(p,x)$ should be replaced by the weight-adjusted variant

Since this adjustment would force us to carry around all player indices, the presentation would become significantly more cumbersome; to avoid this, we stick with the simpler, unweighted case.

Let $D_{n}=D(x^{\ast},X_{n})$ for some Nash equilibrium $x^{\ast}$ of $\mathcal{G}$ and write

where, in the last line, we set $\xi_{n+1}=\langle U_{n+1},X_{n}-x^{\ast}\rangle$, $r_{n}=\langle b_{n},X_{n}-x^{\ast}\rangle$, and we used the variational characterization (VI) of Nash equilibria of monotone games. Thus, conditioning on $\mathcal{F}_{n}$ and taking expectations, we get

where we set $V^{2}=\sum_{i}d_{i}^{2}\max_{x\in\mathcal{X}}\lvert u_{i}(x)\rvert^{2}$ and we used the fact that $X_{n}$ is $\mathcal{F}_{n}$-measurable, so

where we used the fact that $v$ is Lipschitz continuous and $\lVert v^{\delta}-v\rVert_{\infty}=\operatorname{\mathcal{O}}(\delta)$. This shows that there exists some $B>0$ such that $r_{n}\leq B\delta_{n}$; as a consequence, we obtain

Now, letting $R_{n}=D_{n}+\sum_{k=n}^{\infty}[B\gamma_{k}\delta_{k}+(2K)^{-1}V^{2}\gamma_{k}^{2}/\delta_{k}^{2}]$, the estimate (C) gives

i.e., $R_{n}$ is uniformly bounded in $L^{1}$. Thus, by Doob’s convergence theorem for supermartingales (Hall and Heyde, 1980, Theorem 2.5), it follows that $R_{n}$ converges (a.s.) to some finite random variable $R_{\infty}$. In turn, by inverting the definition of $R_{n}$, it follows that $D_{n}$ converges (a.s.) to some random variable $D_{\infty}$, as claimed. ∎

Suppose that the assumptions of Theorem 5.1 hold. Then, with probability $1$, there exists a (random) subsequence $X_{n_{k}}$ of (MD-b) which converges to Nash equilibrium.

We begin with the technical observation that the set $\mathcal{X}^{\ast}$ of Nash equilibria of $\mathcal{G}$ is closed (and hence, compact). Indeed, let $x^{\ast}_{n}$, $n=1,2,\dotsc$, be a sequence of Nash equilibria converging to some limit point $x^{\ast}\in\mathcal{X}$; to show that $\mathcal{X}^{\ast}$ is closed, it suffices to show that $x^{\ast}\in\mathcal{X}$. However, since Nash equilibria of $\mathcal{G}$ satisfy the variational characterization (VI), we also have $\langle v(x),x-x^{\ast}_{n}\rangle\leq 0$ for all $x\in\mathcal{X}$. Hence, with $x^{\ast}_{n}\to x^{\ast}$ as $n\to\infty$, it follows that

i.e., $x^{\ast}$ satisfies (VI). Since $\mathcal{G}$ is monotone, we conclude that $x^{\ast}$ is a Nash equilibrium, as claimed.

Suppose now ad absurdum that, with positive probability, the pivot sequence $X_{n}$ generated by (MD-b) admits no limit points in $\mathcal{X}^{\ast}$.We assume here without loss of generality that $\mathcal{X}^{\ast}\neq\mathcal{X}$; otherwise, there is nothing to show. Conditioning on this event, and given that $\mathcal{X}^{\ast}$ is compact, there exists a (nonempty) compact set $\mathcal{C}\subset\mathcal{X}$ such that $\mathcal{C}\cap\mathcal{X}^{\ast}=\varnothing$ and $X_{n}\in\mathcal{C}$ for all sufficiently large $n$. Moreover, by (VI), we have $\langle v(x),x-x^{\ast}\rangle<0$ whenever $x\in\mathcal{C}$ and $x^{\ast}\in\mathcal{X}^{\ast}$. Therefore, by the continuity of $v$ and the compactness of $\mathcal{X}^{\ast}$ and $\mathcal{C}$, there exists some $c>0$ such that

To proceed, fix some $x^{\ast}\in\mathcal{X}^{\ast}$ and let $D_{n}=D(x^{\ast},X_{n})$ as in the proof of Proposition C.2. Then, telescoping (C) yields the estimate

where, as in the proof of Proposition C.2, we set

Subsequently, letting $\tau_{n}=\sum_{k=1}^{n}\gamma_{k}$ and using (C.15), we obtain

Therefore, by the law of large numbers for martingale difference sequences (Hall and Heyde, 1980, Theorem 2.18), we conclude that $\tau_{n}^{-1}\sum_{k=1}^{n}\gamma_{k}\xi_{k+1}$ converges to with probability $1$.

For the third term in the brackets of (C.19) we have $r_{n}\to 0$ as $n\to\infty$ (a.s.). Since $\sum_{n=1}^{\infty}\gamma_{n}=\infty$, it follows \sum_{k=1}^{n}\gamma_{k}r_{k}\big{/}\sum_{k=1}^{n}\gamma_{k}\to 0.

Finally, for the last term in the brackets of (C.19), let $S_{n+1}=\sum_{k=1}^{n}\gamma_{k}^{2}\lVert\hat{v}_{k}\rVert_{\ast}^{2}$. Since $\hat{v}_{k}$ is $\mathcal{F}_{n}$-measurable for all $k=1,2,\dotsc,n-1$, we have

i.e., $S_{n}$ is a submartingale with respect to $\mathcal{F}_{n}$. Furthermore, by the law of total expectation, we also have

Applying all of the above to the estimate (C.19), we get $D_{n+1}\leq D_{1}-c\tau_{n}/2$ for sufficiently large $n$, and hence, $D(x^{\ast},X_{n})\to-\infty$, a contradiction. Going back to our original assumption, this shows that at least one of the limit points of $X_{n}$ must lie in $\mathcal{X}^{\ast}$, so our proof is complete. ∎

We are finally in a position to prove Theorem 5.1 regarding the convergence of (MD-b):

By Proposition C.3, there exists a (possibly random) Nash equilibrium $x^{\ast}$ of $\mathcal{G}$ such that $\lVert X_{n_{k}}-x^{\ast}\rVert\to 0$ for some (random) subsequence $X_{n_{k}}$. By the assumed reciprocity of the Bregman divergence, this implies that $\liminf_{n\to\infty}D(x^{\ast},X_{n})=0$ (a.s.). Since $\lim_{n\to\infty}D(x^{\ast},X_{n})$ exists with probability $1$ (by Proposition C.2), it follows that

i.e., $X_{n}$ converges to $x^{\ast}$ by the first part of Proposition B.3. Since $\delta_{n}\to 0$ and $\lVert\hat{X}_{n}-X_{n}\rVert=\delta_{n}\lVert W_{n}\rVert=\operatorname{\mathcal{O}}(\delta_{n})$, our claim follows. ∎

Appendix D Finite-time analysis and rates of convergence

We now turn to the finite-time analysis of (MD-b). To begin, we briefly recall that a game $\mathcal{G}$ is $\beta$-strongly monotone if it satisfies the condition

for some $\lambda_{i},\beta>0$ and for all $x,x^{\prime}\in\mathcal{X}$. Our aim in what follows will be to prove the following convergence rate estimate for multi-agent mirror descent in strongly monotone games:

Let $x^{\ast}$ be the (unique) Nash equilibrium of a $\beta$-strongly monotone game. Then:

If the players have access to a gradient oracle satisfying (4.1) and they follow (MD) with Euclidean projections and step-size sequence $\gamma_{n}=\gamma/n$ for some $\gamma>1/\beta$, we have

If the players only have bandit feedback and they follow (MD-b) with Euclidean projections and parameters $\gamma_{n}=\gamma/n$ and $\delta_{n}=\delta/n^{1/3}$ with $\gamma>1/(3\beta)$ and $\delta>0$, we have

Theorem 5.2 is recovered by the second part of Theorem D.1 above; the first part (which was alluded to in the main paper) serves as a benchmark to quantify the gap between bandit and oracle feedback.

For the proof of Theorem D.1 we will need the following lemma on numerical sequences, a version of which is often attributed to Chung (1954):

Let $a_{n}$, $n=1,2,\dotsc$, be a non-negative sequence such that

where $0<p\leq 1$, $q>0$, and $P,Q>0$. Then, assuming $P>q$ if $p=1$, we have

with $R=P$ if $p<1$ and $R=P-q$ if $p=1$.

where we set $Q_{n}=Q(1+q_{n}/n)$, so $Q_{n}\to Q$ as $n\to\infty$. Then, under the assumption that $P>q$ when $p=1$, (D) can be rewritten as

for some sequence $R_{n}$ with $R_{n}\to R$ as $n\to\infty$.

Now, fix some small enough $\varepsilon>0$. From (D.6), we readily get

We begin with the second part of the theorem; the first part will follow by setting some estimates equal to zero, so the analysis is more streamlined that way. Also, as in the previous section, we tacitly assume that ($\beta$-DSC) holds with weights $\lambda_{i}=1$ for all $i\in\mathcal{N}$. If this is not the case, the Bregman divergence $D(p,x)$ should be replaced by the weight-adjusted variant (C.5), but this would only make the presentation more difficult to follow, so we omit the details.

The main component of our proof is the estimate (C), which, for convenience (and with notation as in the previous section), we also reproduce below:

In the above, since the algorithm is run with Euclidean projections, $D_{n}=\frac{1}{2}\lVert X_{n}-x^{\ast}\rVert^{2}$; other than that, $\xi_{n}$ and $r_{n}$ are defined as in (C.17) and (C.18) respectively. Since the game is $\beta$-strongly monotone and $x^{\ast}$ is a Nash equilibrium, we further have

with $B$ and $V$ defined as in the proof of Theorem 5.1 in the previous section.

Now, substituting $\gamma_{n}=\gamma/n^{p}$ and $\delta_{n}=\delta/n^{q}$ in (D.12) readily yields

Hence, taking $p=1$ and $q=1/3$, the last two exponents are equated, leading to the estimate

with $C=\gamma\delta B+(2K)^{-1}\gamma^{2}\delta^{2}V^{2}$. Thus, with $\beta\gamma>1/3$, applying Lemma D.2 with $p=1$ and $q=1/3$, we finally obtain $\bar{D}_{n}=\operatorname{\mathcal{O}}(1/n^{1/3})$.

The proof for the oracle case is similar: the key observation is that the bound (D.12) becomes

with $V$ defined as in (4.1). Hence, taking $\gamma_{n}=\gamma/n$ with $\beta\gamma>1$ and applying again Lemma D.2 with $p=q=1$, we obtain $\bar{D}_{n}=\operatorname{\mathcal{O}}(1/n)$ and our proof is complete. ∎

To conclude, we note that the $\operatorname{\mathcal{O}}(1/n^{1/3})$ bound of Theorem D.1 cannot be readily improved by choosing a different step-size schedule of the form $\gamma_{n}\propto 1/n^{p}$ for some $p<1$. Indeed, applying Lemma D.2 to the estimate (D.13) yields a bound which is either $\operatorname{\mathcal{O}}(1/n^{q})$ or $\operatorname{\mathcal{O}}(1/n^{p-2q})$, depending on which exponent is larger. Equating the two exponents (otherwise, one term would be slower than the other), we get $q=p/3$, leading again to a $\operatorname{\mathcal{O}}(1/n^{1/3})$ bound. Unless one has finer control on the bias/variance of the SPSA gradient estimator used in (MD-b), we do not see a way of improving this bound in the current context.

References