Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games

Introduction

In its most basic incarnation, online learning (Blum 1998; Shalev-Shwartz et al. 2012; Hazan 2016) can be described as a feedback loop of the following form:

The agent interfaces with the environment by choosing an action $a_{t}\in\mathcal{A}\subseteq\mathbf{R}^{d}$ (e.g., bidding in an auction, selecting a route in a traffic network).

The environment then yields a reward function $r_{t}(\cdot)$, and the agent obtains the reward $r_{t}(a_{t})$ and receives some feedback (e.g., reward function $r_{t}(\cdot)$, gradient $\nabla r_{t}(a_{t})$, or reward $r_{t}(a_{t})$), and the process repeats.

As the reward functions $r_{t}(\cdot)$ are allowed to change from round to round, the standard metric that quantifies the performance of an online learning algorithm is that of regret (Blum and Mansour 2007): at time $T$, the regret is the difference between $\max_{a\in A}\sum_{t=1}^{T}u_{t}(a)$, the total rewards achieved by the best fixed action in hindsight, and $\sum_{t=1}^{T}u_{t}(a_{t})$, the total rewards achieved by the algorithm. In the rich online learning literature (Zinkevich 2003; Kalai and Vempala 2005; Shalev-Shwartz and Singer 2007; Arora et al. 2012; Shalev-Shwartz et al. 2012; Hazan 2016), perhaps the simplest algorithm that achieves the minimax-optimal regret guarantee is Zinkevich’s online gradient descent (OGD), where the agent simply takes a gradient step (at current action) to form the next action, performing a projection if necessary. Due to its simplicity and strong performance, it is arguably one of the most widely-used algorithms in online learning theory and applications (Zinkevich 2003; Hazan et al. 2007; Quanrud and Khashabi 2015).

At the same time, the most common instantiation of the above online learning model (where reward functions change arbitrarily over time) is multi-agent online learning: each agent is making online decisions in an environment that consists of other agents who are simultaneously making online decisions and whose actions impact the rewards of other agents; that is, each agent’s reward is determined by an (unknown) game. Note that in multi-agent online learning, as other agents’ actions change, each agent’s reward function, when viewed solely as a function of its own action, also changes, despite the fact that the underlying game mechanism is fixed. Consequently, in this setting, the universality of the OGD regret bounds raises high expectations in terms of performance guarantees, leading to the following fundamental question in game-theoretical learning (Cesa-Bianchi and Lugosi 2006; Shoham and Leyton-Brown 2008; Viossat and Zapechelnyuk 2013; Bloembergen et al. 2015; Monnot and Piliouras 2017): Would OGD learning, and more broadly no-regret learning, lead to Nash equilibiria?

As an example, if all users of a computer network individually follow some no-regret learning algorithm (e.g. OGD) to learn the best route for their traffic demands, would the system eventually converge to a stable traffic distribution, or would it devolve to perpetual congestion as users ping-pong between different routes (like commuters changing lanes in a traffic jam)? Note that whether the process converges at all pertains to the stability of the joint learning procedure, while whether it converges to Nash equilibria pertains to the rationality thereof: if the learning procedure converges to a non-Nash equilibrium, then each can do better by not following that learning procedure.

Despite the seeming simplicity, the existing literature has only provided scarce and qualitative answers to this question. This is in part due to the strong convergence mode conveyed by the question: while a large literature exists on this topic, much of them focuses on time-average convergence (i.e. convergence of the time average of the joint action), rather than last-iterate convergence (i.e. convergence of the joint action). However, not only is last-iterate convergence theoretically stronger and more appealing, it is also the only type of convergence that actually describes the system’s evolution. This was a well-known point that was only recently rigorously illustrated in Mertikopoulos et al. 2018b, where it is shown that even though follow-the-regularized-leader (another no-regret learning algorithm) converges to a Nash equilibrium in linear zero-sum games in the sense of time-averages, actual joint action orbits Nash equilibria in perpetuity. Motivated by this consideration, a growing literature (Krichene et al. 2015; Lam et al. 2016; Zhou et al. 2017c; Palaiopanos et al. 2017; Zhou et al. 2017b; Mertikopoulos et al. 2017; Zhou et al. 2017a; Zhou et al. 2020a; Zhou et al. 2018; Zhou et al.; Mertikopoulos and Zhou 2019) has devoted the efforts to obtaining last-iterate convergence results. However, due to the challenging nature of the problem, all of those lat-iterate convergence results are qualitative. In particular, except in strongly monotone games (Zhou et al. 2020b very recently established a $O(1/T)$ last-iterate convergence rate for OGD learning with noisy feedback The perfect gradient feedback case has a last-iterate convergence of $O(\rho^{T})$, for some $0<\rho<1$ when the game is further Lipchitz. This follows from a classical result in variational inequality (Facchinei and Pang 2007) in strongly monotone games), there are no quantitative, finite-time last-iterate convergence rates available Except in convex potential games. In that case, the problem of converging to Nash equilbiria reduces to a convex optimization problem, where standard techniques apply.

Additionally, an important element in multi-agent online learning is that the horizon of play is typically unknown. As a result, no-regret learning algorithms need to be employed with a decreasing learning rate (e.g., because of a doubling trick or as a result of an explicit $O(1/t^{\alpha})$ step-size tuning). In particular, in order to achieve last-iterate convergence-to-Nash results, all of the above mentioned work rest crucially on using decreasing step-size (often converging to $0$ no slower than a particular rate) in their algorithm designs. This, however, leads to the following general tenet: New information is utilized with decreasing weights

From a rationality point of view, this is not only counter-intuitive – it flies at the face of established economic wisdom. Instead of discounting past information, players end up indirectly reinforcing it by assigning negligible weight to recent observations relative to those in the distant past. This negative recency bias is unjustifiable from economic micro-foundations and principles, and it cannot reasonably account for any plausible model of human/consumer behavior. The above naturally raises another important open question, one that, if answered, can bridge the gap between online learning and rationalizable economic micro-foundations: Is no-regret learning without discounting recent information compatible with Nash equilibria?

Contributions.

Reflecting on those two gaps simultaneously, we are thus led to the following ambitious research question, one that aims to close two open questions at once: Can we obtain finite-time last-iterate convergence rate using only non-decreasing step-size? Our goal here is to make initial but significant progress in answering this question; our contributions are threefold.

First, we introduce a class of games that we call cocoercive and which contain all strongly monotone games as a special case. We show that if each player adopts OGD, then the joint action sequence converges in last-iterate to the set of Nash equilibria at a rate of $o(1/T)$. The convergence speed more specifically refers to how fast the gradient norm squared converges to $0$: note that in cocoercive games, gradient norm converges to $0$ if and only if the iterate converges to the set of Nash equilibria. To the best of our knowledge, this is the first rate that provides finite-time last-iterate convergence that moves beyond the strong monotonicity assumption.

Second, we study in depth the stochastic gradient feedback case, where each player adopts OGD in $\lambda$-cocoercive games, with gradient corrupted by a zero-mean, martingale-difference noise, whose variance is proportional to current gradient norm squared as assumed in the relative random noise model (Polyak 1987). In this more challenging setting, we first establish that the joint action sequence converges in last-iterate to Nash equilibria almost surely under a constant step-size. The previous best such qualitative convergence is due to Mertikopoulos and Zhou 2019, which shows that such almost sure convergence is guaranteed in a variationally stable game. Despite the fact that variationally stable games contain cocoercive games as a subclass, our result is not covered by theirs because Mertikopoulos and Zhou 2019 assumes compact action set, where we consider unconstrained action set–a more challenging scenario since the action iterates can a priori be unbounded. Our result is further unique in that constant step-size is sufficient to achieve last-iterate almost sure convergence, while Mertikopoulos and Zhou 2019 requires decreasing step-size (that is square-summable-but-not-summable). Note that the relative random noise model is necessary for obtaining such constant step-size result: in an absolute random noise model (where the noise’s second moment is bounded by a constant), the gradient descent iterate forms an ergodic and irreducible Markov chains, which induces an invariant measure that is supported on the entire action set, thereby making it impossible to obtain any convergence-to-Nash result. We then proceed a step further and characterize finite-time convergence rate. We establish two rates here: first, the expected time-average convergence rate is $O(1/T)$; second the expected last-iterate convergence rate is $O(a(T))$, where $a(T)$ depends on how fast the relative noise proportional constants decrease to $0$. As a simple example, if those constants decrease to $0$ at an $O(1/\sqrt{t})$ rate, then the last-iterate convergence rate is $O(1/\sqrt{T})$. For completeness (but due to space limitation), we also present in the appendix a parallel set of results–last-iterate almost sure convergence, time-average convergence rate and last-iterate convergence rate–for the absolute random noise model (under diminishing step-sizes of course).

Third, and even more surprisingly, we provide–to the best of our knowledge–the first adaptive gradient descent algorithm that has last-iterate convergence guarantees on games. In particular, the online gradient descent algorithms mentioned above–both in the deterministic and stochastic gradient case–requires the cocoercive constant $\lambda$ to be known beforehand. Thus, this calls for adaptive variants that do not require such knowledge. In the deterministic setting, we design an adaptive gradient descent algorithm that operates without needing to know $\lambda$ and adaptively chooses its step-size based on past gradients. We then show that the same $o(\frac{1}{T})$ last-iterate convergence rate can be achieved with non-decreasing step-size. Previously, the closest existing result is Bach and Levy 2019, which provided an adaptive algorithm on variational inequality with time-average convergence guarantees. However, providing adaptive algorithms for last-iterate convergence is much more challenging and Bach and Levy 2019 further requires the knowledge of the diameter of domain set (which they assume to be compact) in their adaptive algorithm, whereas we operate in unbounded domains. Our analysis relies on a novel double stopping time analysis, where the first stopping time characterizes the first time until gradient norm starts to monotonically decrease, and the second stopping time, after the first stopping has occured, characterizes the first time the underlying pseudo-contraction mapping starts to rapidly converge. We also provide the adaptive algorithm in the stochastic gradient feedback setting and establish the same finite-time last-iterate convergence guarantee. Note that our results only imply convergence in unconstrained strongly monotone games. Constrained coercive games is another interesting setting that would require a different set of techniques and further exploration.

Problem Setup

In this section, we present the definitions of a game with continuous action sets, which serves as a stage game and provides a reward function for each player in an online learning process. The key notion defined here is called $\lambda$-cococercivity, which is weaker than $\lambda$-strong monotonicity and covers a wider range of games.

For each $i\in\mathcal{N}$, the function $u_{i}(\mathbf{x})$ is continuous in $\mathbf{x}$.

For each $i\in\mathcal{N}$, the function $u_{i}$ is continuously differentiable in $\mathbf{x}_{i}$ and the partial gradient $\nabla_{\mathbf{x}_{i}}u_{i}(\mathbf{x})$ is Lipschitz continuous in $\mathbf{x}$.

The notation $\mathbf{x}_{-i}$ denotes the joint action of all players but player $i$. Consequently, the joint action $\mathbf{x}$ will frequently be written as $(x_{i};\mathbf{x}_{-i})$. Two important quantities are specified as follows:

$\mathbf{v}(\mathbf{x})$ is the profile of the players’ individual payoff gradients, i.e., $\mathbf{v}(\mathbf{x})=(v_{1}(\mathbf{x}),\ldots,v_{N}(\mathbf{x}))$, where $v_{i}(\mathbf{x})\triangleq\nabla_{x_{i}}u_{i}(\mathbf{x})$.

We are looking at pure-Nash equilibria, because we are studying continuous games, where the action set is already a finite-dimensional vector space, rather than a finite set as in the simpler finite games in which each player’s mixed strategy is a vector of probabilities in the simplex. In our setting, each action already lives in a continuum and we follow the standard definition of a pure Nash equilibrium.

$\mathbf{x}^{*}\in\mathcal{X}$ is called a (pure-strategy) Nash equilibrium of a game $\mathcal{G}$ if for each player $i\in\mathcal{N}$, it holds true that $u_{i}(x_{i}^{*},\mathbf{x}_{-i}^{*})\geq u_{i}(x_{i},\mathbf{x}_{-i}^{*})$ for each $x_{i}\in\mathcal{X}_{i}$.

In a continuous game $\mathcal{G}$, if $\mathbf{x}^{*}\in\mathcal{X}$ is a Nash equilibrium, then $(\mathbf{x}-\mathbf{x}^{*})^{\top}\mathbf{v}(\mathbf{x}^{*})\leq 0$ for all $\mathbf{x}\in\mathcal{X}$. The converse also holds true if the game is concave: for each $i\in\mathcal{N}$, the function $u_{i}(x_{i};\mathbf{x}_{-i})$ is concave in $x_{i}$ for all $\mathbf{x}_{-i}\in\prod_{j\neq i}\mathcal{X}_{j}$.

Proposition 2.1 is a classical result (see also Mertikopoulos and Zhou 2019 for a proof) and shows that the Nash equilibria of a concave game are precisely the solutions of the variational inequality $(\mathbf{x}-\mathbf{x}^{*})^{\top}\mathbf{v}(\mathbf{x}^{*})\leq 0$ for all $\mathbf{x}\in\mathcal{X}$.

montone if $(\mathbf{x}^{\prime}-\mathbf{x})^{\top}(\mathbf{v}(\mathbf{x}^{\prime})-\mathbf{v}(\mathbf{x}))\leq 0$ for all $\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{X}$.

strictly monotone if $(\mathbf{x}^{\prime}-\mathbf{x})^{\top}(\mathbf{v}(\mathbf{x}^{\prime})-\mathbf{v}(\mathbf{x}))\leq 0$ for all $\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{X}$, with equality if and only if $\mathbf{x}=\mathbf{x}^{\prime}$.

In a strictly monotone game (first introduced in Rosen 1965 and referred to as diagonal strict concave games there), at most one Nash equilibrium exists; hence when all action sets are convex and compact, a strictly monotone game admits a unique Nash equilibrium. Additionally, when $\mathbf{v}=\nabla f$ for some (smooth) function $f$, $f$ is strictly concave. The notion strictly refers to the only if requirement in the condition. Many useful results regarding strictly monotone games (under convex and compact action sets) can be found in Rosen 1965.

Proceeding a step further, we can define strongly monotone games:

A continuous game $\mathcal{G}$ is called $\lambda$-strongly monotone if the payoff strongly monotone condition holds: $(\mathbf{x}^{\prime}-\mathbf{x})^{\top}(\mathbf{v}(\mathbf{x}^{\prime})-\mathbf{v}(\mathbf{x}))\leq-\lambda\|\mathbf{x}^{\prime}-\mathbf{x}\|^{2}$ for all $\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{X}$.

Note that strongly monotone games are a subclass of strictly monotone games. One appealing feature of strongly monotone games is that the finite-time convergence rate can be derived in terms of $\|\mathbf{x}_{t}-\mathbf{x}^{*}\|$, where $\mathbf{x}^{*}$ is the unique Nash equilibrium (Zhou et al. 2020b) (under convex and compact action sets). On the other hand, $\mathbf{x}_{t}$ can possibly converge to a limit cycle or repeatedly hit the boundary in monotone games Mertikopoulos et al. 2018a; Daskalakis et al. 2018 despite that the time-average $(\sum_{j=1}^{t}\mathbf{x}_{j})/t$ converges. More recently, Mertikopoulos and Zhou 2019 analyzed online mirror descent (OMD) learning (which contains OGD as a special case) in variational stable games (under convex and compact action sets) and proved that last-iterate convergence to Nash equilibria holds almost surely in the presence of imperfect feedback (i.e. gradient corrupted by an unbiased noise). This result is surprising since the notion of variational stablitly is much weaker than strict monotonicity (hence qualitative convergence to Nash in strictly monotone games is guaranteed), showing that strong monotonicity is unnecessary for last-iterate convergence of OGD learning.

However, there are no last-iterate convergence rates available for strictly monotone games (unconstrained or constrained), and such a result does not seem possible because the strictness gap can be made arbitrarily small (and yielding arbitrarily slow rates). In fact, without the quadratic growth of strong monotonicity, it seems impossible to attain the rate for $\|\mathbf{x}_{t}-\mathbf{x}^{*}\|$ and, moreover, using the method with a constant step-size is completely out of reach of the techniques of Zhou et al. 2020b. Finally, we remark that fully adaptive and parameter-free learning methods are also missing from game-theoretic analyses to date.

2 λ\lambda-Cococercive Games

A continuous game $\mathcal{G}$ is called $\lambda$-cocoercive if the payoff cocoercive condition holds: $(\mathbf{x}^{\prime}-\mathbf{x})^{\top}(\mathbf{v}(\mathbf{x}^{\prime})-\mathbf{v}(\mathbf{x}))\leq-\lambda\|\mathbf{v}(\mathbf{x}^{\prime})-\mathbf{v}(\mathbf{x})\|^{2}$ for all $\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{X}$.

First, a cocoercive game is a monotone game (as can be easily seen from the definitions), but cocoercive games neither contain nor belong to strictly monotone games. When a Nash equilibrium exists in a cocoercive game, it may not be unique; further, all Nash equilibria of a cococercive game shares the same individual payoff gradient (either constrained or unconstrained): neither of these two properties hold in a strictly monotone game. For a simple one-player example where the cost function $f(x)=x^{2}$ for $x<0$ and $0$ otherwise: this game is cocoercive but not strictly monotone. Moreover, $(\mathbf{x}^{\prime}-\mathbf{x})^{\top}(\mathbf{v}(\mathbf{x}^{\prime})-\mathbf{v}(\mathbf{x}))=0$ only implies that $\mathbf{v}(\mathbf{x}^{\prime})=\mathbf{v}(\mathbf{x})$ and $\mathbf{x}^{\prime}=\mathbf{x}$ does not necessarily hold true.

Second, the unconstrained cocoercive games may not always have a Nash equilibrium since we lifted the compactness assumption. Accordingly, all of our subsequent convergence results are stated for games that do have Nash equilibria: we did so because we want our results to apply to all cocoercive games that have Nash equilibria. That said, many additional sufficient conditions can be imposed on a cocoercive game to ensure the existence of a Nash equilrium. One such sufficient condition is the coercivity of the costs: the costs go to infinity as joint actions go to infinity (as already alluded to, we didn’t assume both cocoercivity and coercivity because that would eliminate other cocoercive games that admit Nash equilibria, which is more restrictive).

Thirdly, we remark that it is more difficult to analyze the convergence property of online algorithms in unconstrained setting, especially when the feedback information is noisy, since the iterates are not necessarily assumed to be bounded. Further, since in a cocoercive game, $\mathbf{x}^{*}\in\mathcal{X}^{*}$ is a Nash equilibrium if and only if $\mathbf{v}(\mathbf{x}^{*})=0$, the natural candidate for measuring convergence (i.e. optimality gap) is $\epsilon(\mathbf{x})=\|\mathbf{v}(\mathbf{x})\|^{2}$.

3 Learning via Online Gradient Descent

We describe the online gradient descent (OGD) algorithm in our game-theoretical setting. Intuitively, the main idea is: At each stage, every player $i\in\mathcal{N}$ gets an estimate $\hat{v}_{i}$ of the individual gradient of their payoff function at current action profile, possibly subject to noise and uncertainty. Subsequently, they choose an action $x_{i}$ for the next stage using the current action and feedback $\hat{v}_{i}$, and continue playing.

where $t\geq 0$ denotes the stage of process, $\hat{v}_{i,t}$ is an estimate of the individual payoff gradient $v_{i}(\mathbf{x}_{t})$ of player $i$ at stage $t$. The learning rate $\eta_{t}>0$ is a nonincreasing sequence which can be of the form $c/t^{p}$ for some $p\in$.

We assume that each player $i\in\mathcal{N}$ has access to a “black box” feedback mechanism – an oracle – which returns an estimate of their payoff gradients at their current action profile. This information can be imperfect for a multitude of reasons; see Mertikopoulos and Zhou 2019. With all this in mind, we consider the following noisy feedback model:

where the noise process $\xi_{t}=(\xi_{i,t})_{i\in\mathcal{N}}$ is an $L^{2}$-bounded martingale difference adapted to the history $(\mathcal{F}_{t})_{t\geq 1}$ of $\mathbf{x}_{t}$ (i.e., $\xi_{t}$ is $\mathcal{F}_{t}$-measurable but $\xi_{t+1}$ isn’t).

We focus on two types of random noise proposed by Polyak 1987. The first type is called relative random noise:

and the second type is called absolute random noise:

The above condition is mild (the i.i.d. condition is not imposed) and allows for a broad range of error processes. For the relative random noise, the variance decreases as it approaches a Nash equilibrium which admits better convergence rate of learning algorithms.

Convergence under Perfect Feedback

In this section, we analyze the convergence property of OGD learning under perfect feedback. In particular, we show that the finite-time last-iterate convergence rate is $o(1/T)$ regardless of fully adaptive learning rates. To our knowledge, the proof techniques for analyzing adaptive OGD learning is new and can be of independent interests.

We first provide a lemma which shows that $\|\mathbf{v}(\mathbf{x}_{t})\|^{2}$ is nonnegative, nonincreasing and summable.

For the OGD learning with perfect feedback and constant step-size, the update formula in Eq. (1) implies that $\|\mathbf{v}(\mathbf{x}_{t})\|^{2}=\|\mathbf{x}_{t}-\mathbf{x}_{t+1}\|^{2}/\eta^{2}$. This implies that $\|\mathbf{x}_{t}-\mathbf{x}_{t+1}\|^{2}$ also serves as the candidate for an optimality gap function. Such quantity is called the iterative gap and frequently used to construct the stopping criteria in practice.

Now we are ready to present our main results on the last-iterate convergence rate of OGD learning.

Proof. Lemma 3.1 implies that $\{\|\mathbf{v}(\mathbf{x}_{t})\|^{2}\|\}_{t\geq 0}$ is nonnegative, nonincreasing and $\sum_{t=0}^{+\infty}\|\mathbf{v}(\mathbf{x}_{t})\|^{2}<+\infty$. Therefore,

which implies that $\|\mathbf{v}(\mathbf{x}_{T})\|^{2}=o(1/T)$. By the definition of $\epsilon(\mathbf{x})$, we conclude the desired result. $\Box$

2 Adaptive OGD Learning

Our main results in this subsection is the last-iterate convergence rate of Algorithm 1. Here the algorithm requires no prior knowledge of $\lambda$ but still achieves the rate of $o(1/T)$. To facilitate the readers, we summarize the results in the following theorem and provide the detailed proof.

Proof. Since the step-size sequence $\{\eta_{t}\}_{t\geq 1}$ is nonincreasing, we define the first iconic time in our analysis as follows,

In what follows, we prove the last-iterate convergence rate for two cases: $t^{*}=+\infty$ (Case I) and $t^{*}<+\infty$ (Case II).

First, we have $1/\lambda^{2}-\beta_{0}\geq 0$ since $\eta_{0}>\lambda$. Note that $\beta_{t+2}\leftarrow r\beta_{t+1}$ with $r>1$ is updated when $\|\mathbf{v}(\mathbf{x}_{t+1})\|>\|\mathbf{v}(\mathbf{x}_{t})\|$, there exists $T_{0}>0$ such that $\|\mathbf{v}(\mathbf{x}_{t+1})\|\leq\|\mathbf{v}(\mathbf{x}_{t})\|$ for all $t\geq T_{0}$. If not, then $\beta_{t}\rightarrow+\infty$ as $t\rightarrow+\infty$ and $\eta_{t}\rightarrow 0$. However, $t^{*}=+\infty$ implies that $\eta_{t+1}\geq\lambda$ for all $t\geq 1$. This leads to a contradiction. Furthermore, it holds true for all $t\geq 0$ that

By starting the sequence at a later index $T_{0}$, we have $\sum_{t\geq T_{0}}\|\mathbf{v}(\mathbf{x}_{t})\|^{2}<+\infty$ and $\|\mathbf{v}(\mathbf{x}_{t+1})\|\leq\|\mathbf{v}(\mathbf{x}_{t})\|$ for all $t\geq T_{0}$. Using the same argument as in Theorem 3.3, the adaptive OGD iterate $\mathbf{x}_{t}$ satisfies that $\epsilon(\mathbf{x}_{T})=o(1/T)$.

Case II.

First, we claim that $\|\mathbf{x}_{t}-\Pi_{\mathcal{X}^{*}}(\mathbf{x}_{t^{*}})\|\leq D$ where $D=\max_{1\leq t\leq t^{*}}\|\mathbf{x}_{t}-\Pi_{\mathcal{X}^{*}}(\mathbf{x}_{t^{*}})\|$. Indeed, it suffices to show that $\|\mathbf{x}_{t}-\Pi_{\mathcal{X}^{*}}(\mathbf{x}_{t^{*}})\|\leq\|\mathbf{x}_{t^{*}}-\Pi_{\mathcal{X}^{*}}(\mathbf{x}_{t^{*}})\|$ holds for $t>t^{*}$. By the definition of $t^{*}$, we have $\eta_{t+1}\leq\lambda$ for all $t>t^{*}$. The desired inequality follows from Lemma 3.1.

Using the update formula (cf. Eq. (1)), we have

Using the update formula of OGD learning, we have

Summing up Eq. (5) over $t=0,1,2,\ldots,T$ yields that

Since the step-size sequence $\{\eta_{t}\}_{t\geq 1}$ is nonincreasing, we have $1/\eta_{t+1}\geq 1/\eta_{t}$. Letting $\mathbf{x}^{*}=\Pi_{\mathcal{X}^{*}}(\mathbf{x}_{t^{*}})$, we notice that $\|\mathbf{x}^{*}-\mathbf{x}_{t}\|\leq D$ for all $0\leq t\leq T$. Putting these pieces together yields that

To proceed, we define the second iconic time as

Suppose that $t_{1}^{*}=+\infty$, it is straightforward to show that the adaptive OGD iterate $\mathbf{x}_{t}$ satisfies that $\epsilon(\mathbf{x}_{T})=o(1/T)$ using the same argument in Case I.

Next, we consider $t_{1}^{*}<+\infty$. Indeed, we recall that $\eta_{t+1}\leq\lambda$ for all $t>t_{1}^{*}$ which implies that $1/\lambda-1/\eta_{t+1}\leq 0$. Since $\|\mathbf{x}_{t}-\mathbf{x}_{t+1}\|^{2}=\eta_{t+1}^{2}\|\mathbf{v}(\mathbf{x}_{t})\|^{2}$ (cf. Eq. (1)) and assume $T$ sufficiently large without loss of generality, we have

Before bounding term I and II, we present two technical lemmas which is crucial to our subsequent analysis; see (Bach and Levy 2019, Lemma A.1 and A.2) for the detailed proof.

For a sequence of numbers $a_{0},a_{1},\ldots,a_{n}\in[0,a]$ and $b\geq 0$, the following inequality holds:

For a sequence of numbers $a_{0},a_{1},\ldots,a_{n}\in[0,a]$ and $b\geq 0$, the following inequality holds:

Bounding term I:

By the definition of $t_{1}^{*}$ and Lemma 3.1, we have $\beta_{t}=\beta_{t_{1}^{*}+1}$ for all $t>t_{1}^{*}$. Thus, we derive from the definition of $\eta_{t}$ that

Since $\|\mathbf{x}_{t}-\Pi_{\mathcal{X}^{*}}(\mathbf{x}_{t^{*}})\|\leq D$ for all $t\geq 0$. Since the notion of $\lambda$-cocercivity implies the notion of $(1/\lambda)$-Lipschiz continuity, we have

Using the first inequality in Lemma 3.5, we have

Since $\eta_{t+1}\leq\lambda/2D^{2}$ for all $t>t_{1}^{*}$, we have

Using the second inequality in Lemma 3.5,

Putting Eq. (7)-(10) together yields that

Bounding term II: By the definition of $\eta_{t}$ and noting that $\beta_{t}\geq\beta_{1}$ for all $t\geq 1$, we have

Recalling Eq. (6), we can apply Lemma 3.6 with Eq. (10) to obtain that

which implies that $\sum_{t=0}^{T}\|\mathbf{v}(\mathbf{x}_{t})\|^{2}$ is bounded by a constant for all $T\geq 0$. By starting the sequence at a later index $t_{1}^{*}$, we have $\|\mathbf{v}(\mathbf{x}_{t+1})\|\leq\|\mathbf{v}(\mathbf{x}_{t})\|$ for all $t\geq t_{1}^{*}$ and $\sum_{t\geq t_{1}^{*}}\|\mathbf{v}(\mathbf{x}_{t})\|^{2}<+\infty$. Using the same argument as in Theorem 3.3, we conclude that the adaptive OGD iterate $\mathbf{x}_{t}$ satisfies that $\epsilon(\mathbf{x}_{T})=o(1/T)$. $\Box$

In our proof, $D>0$ is the constant that depends on the set of Nash equilibrium, and in stating the bound this way, we followed the standard tradition in optimization where the bound (on either $f(\mathbf{x}_{t})-f(\mathbf{x}^{*})$ or $\|\nabla f(\mathbf{x}^{t})\|^{2}$) would depend on $\|\mathbf{x}_{0}-\mathbf{x}^{*}\|$ (a constant that cannot be avoided). Here, our bound similarly depends on this constant, except the game setting is more complicated (since there is no common objective) so this constant depends on the first few iterates as well (not just the initial iterate $\mathbf{x}^{0}$): more precisely, $D=\max_{1\leq t\leq t^{*}}\|\mathbf{x}_{t}-\Pi_{\mathcal{X}^{*}}(\mathbf{x}_{t^{*}})\|$.

Convergence under Imperfect Feedback with Relative Random Noise

In this section, we analyze the convergence property of OGD learning under imperfect feedback with relative random noise (3). In particular, we show that the almost sure last-iterate convergence is guaranteed and the finite-time average-iterate convergence rate is $O(1/T)$ when $0<\tau_{t}\leq\tau<+\infty$. More importantly, we get the finite-time last-iterate convergence rate when $\tau_{t}$ satisfies certain summable condition (16).

Proof. Using the update formula of $x_{i,t+1}$ in Eq. (1), we have the following for any $x_{i}^{*}\in\mathcal{X}_{i}^{*}$:

Summing up the above inequality over $i\in\mathcal{N}$ and rearranging yields that

Since $\mathbf{x}^{*}\in\mathcal{X}^{*}$ and $\mathcal{G}$ is a $\lambda$-cocoercive game, we have $\mathbf{v}(\mathbf{x}^{*})=0$ and

Putting these pieces yields the desired inequality. $\Box$

Proof. Using the same argument as in Lemma 4.1, we have

Taking an expectation of both sides yields the desired inequality. $\Box$

Now we are ready to characterize the almost sure last-iterate convergence. Note that the condition imposed on $\tau_{t}$ is minimal and $\eta_{t}=\eta\in[\underline{\eta},\overline{\eta}]$ is allowed for all $t\geq 1$.

Proof. We obtain the following inenquality by taking the expectation of both sides of Eq. (11) (cf. Lemma 4.1) conditioned on $\mathcal{F}_{t}$:

Since $\eta_{t}>0$ and $\overline{\eta}<\lambda/(1+\tau)$, we let $M_{t}=\|\mathbf{x}_{t}-\mathbf{x}^{*}\|^{2}$ and obtain that $M_{t}$ is an nonnegative supermartingale. Then Doob’s martingale convergence theorem shows that $M_{n}$ converges to an nonnegative and integrable random variable almost surely. Let $M_{\infty}=\lim_{t\rightarrow+\infty}M_{t}$, it suffices to show that $M_{\infty}=0$ almost surely now. We assume to contrary that, there exists $m>0$ such that $M_{\infty}>m$ with positive probability. Then $M_{t}>m/2$ for sufficiently large $t$ with positive probability. Formally, there exists $\delta>0$ such that

On the other hand, by taking the expectation of Eq. (14) and using the condition $\eta_{t}\geq\underline{\eta}>0$ for all $t\geq 1$, we have

2 Finite-Time Convergence Rate: Time-Average and Last-Iterate

In this subsection, we focus on deriving two types of rates: the time-average and last-iterate convergence rates, as formalized by the following theorems.

Proof. Using the same argument as in Theorem 4.3, we obtain that

Taking an expectation of both sides of Eq. (14) and rearranging yields that

Summing up the above inequality over $t=0,1,\ldots,T$ yields that

The condition (16) is fairly mild. Indeed, the decaying rate $a(t)$ can be very slow which still guarantees the finite-time last-iterate convergence rate. For some typical examples, we have $a(t)=\log\log(t)/t$ if $\tau_{t}=1/t\log(t)$ and $a(t)=\log(t)/t$ if $\tau_{t}=1/t$. When $\tau_{t}=\Omega(1/t)$, we have $a(t)=\tau_{t}$, such as $a(t)=1/\sqrt{t}$ if $\tau_{t}=1/\sqrt{t}$ and $a(t)=1/\log\log(t)$ if $\tau_{t}=1/\log\log(t)$. Under this condition, we can derive the last-iterate convergence rate given the decaying rate of $\tau_{t}$ as $t\rightarrow+\infty$.

Under the condition (16), the finite-time last-iterate convergence rate can be derived under certain step-size sequences.

Proof. Using Lemma 4.2 and $\eta_{t}\geq\underline{\eta}>0$, we have

Summing up the above inequality over $t=0,\ldots,T$ yields

Using Eq. (14) and $\eta_{t}\geq\underline{\eta}>0$ for all $t\geq 1$, we have

Putting these pieces with the fact that $\{\tau_{t}\}_{t\geq 0}$ is an nonincreasing sequence yields that

3 Adaptive OGD Learning

We study the convergence property of Algorithm 2 under the noisy model (2) with relative random noise (3) satisfying that there exists $a(t)=o(1)$ such that

Note that Eq. (17) is slightly stronger than Eq. (16).

We present our main result in Theorem 4.7 and remark that the proof technique is new and can be interpreted as a novel combination of that in Theorem 3.4 and 4.6.

Proof. Since the step-size sequence $\{\eta_{t}\}_{t\geq 1}$ is decreasing and converges to zero, we define the first iconic time in our analysis as follows,

Furthermore, we derive an upper bound for the term $\sum_{t=0}^{T}\|\mathbf{v}(\mathbf{x}_{t})\|^{2}$. Using the update formula (cf. Eq. (1)) to obtain that

Recall that $\mathcal{G}$ is $\lambda$-cocoercive and the noisy model is defined with relative random noise, we have

Putting these pieces together and taking an expectation yields that

Recall that the step-size sequence $\{\eta_{t}\}_{t\geq 1}$ is nonincreasing and $\|\mathbf{x}_{t}-\Pi_{\mathcal{X}^{*}}(\mathbf{x}_{t^{*}})\|\leq D$, we let $\mathbf{x}^{*}=\Pi_{\mathcal{X}^{*}}(\mathbf{x}_{t^{*}})$ in Eq. (18) and obtain that

To proceed, we define the second iconic time as

It is clear that $t_{1}^{*}<+\infty$ and $\eta_{t+1}\leq\lambda/(2+2\tau)$ for all $t>t_{1}^{*}$ which implies that $(2+2\tau)/\lambda-1/\eta_{t+1}\leq 0$. Assume $T$ sufficiently large without loss of generality, we have

We also use Lemmas A.1 and A.2 from Bach and Levy 2019 to bound terms I and II. For convenience, we present these two lemmas here:

For a sequence of numbers $a_{0},a_{1},\ldots,a_{n}\in[0,a]$ and $b\geq 0$, the following inequality holds:

We derive from the definition of $\eta_{t}$ and Jensen’s inequality that

Using the first inequality in Lemma 4.8, we have

Since $\eta_{t+1}\leq\lambda/[4(1+\tau)D^{2}]$ for all $t>t_{1}^{*}$, we have

Using the second inequality in Lemma 3.5, we have

Putting Eq. (20)-(22) together yields that

Bounding II:

and $\eta_{t}\leq 1/\beta$ for all $t\geq 1$, we have

Putting these pieces together yields that

Finally, we proceed to bound the term $\epsilon(\mathbf{x}_{T})$. Without loss of generality, we can start the sequence at a later index $t_{1}^{*}$ since $t_{1}^{*}<+\infty$. This implies that $\eta_{t+1}\leq\lambda/2(1+\tau)$. Using the last equation in the proof of Lemma 4.2, we have

Summing up the above inequality over $t=t_{1}^{*},\ldots,T+$ yields

Since $\{\tau_{t}\}_{t\geq 0}$ is an nonincreasing sequence, we have

Using Eq. (14) and $\eta_{t+1}\leq\lambda/2(1+\tau)$ for all $t>t_{1}^{*}$, we have

Acknowledgments

We would like to thank three anonymous referees for constructive suggestions that improve the quality of this paper. Zhengyuan Zhou was supported by the IBM Goldstine Fellowship. This work was supported in part by the Mathematical Data Science program of the Office of Naval Research under grant number N00014-18-1-2764.

References

Appendix A Convergence under Imperfect Feedback with Absolute Random Noise

We are now ready to establish last-iterate convergence in a strong, almost sure sense. Note that the conditions imposed on $\sigma_{t}^{2}$ and $\eta_{t}$ are minimal.

Then the noisy OGD iterate $\mathbf{x}_{t}$ converges to $\mathcal{X}^{*}$ almost surely.

A.2 Finite-Time Convergence Rate: Time-Average and Last-Iterate

For completeness, we characterize two types of rates: the time-average and last-iterate convergence rate, as formalized by the following theorems.

Under this condition, the noisy iterate generated by the OGD-based learning achieves the finite-time last-iterate convergence rate regardless of a sequence of possibly constant step-sizes $\eta_{t}$ satisfying $0<\underline{\eta}\leq\eta_{t}\leq\overline{\eta}<\lambda$ for all $t\geq 1$.

Appendix B Proof of Lemma 3.1

Expanding the right-hand side of the above inequality and summing up the resulting inequality over $i\in\mathcal{N}$ yields that

Since $\mathcal{G}$ is a $\lambda$-cocoercive game, we have

Plugging the above equation into Eq. (24) together with the condition $\eta\in(0,\lambda]$ yields that

Using the update formula in Eq. (1), we have $\|\mathbf{v}(\mathbf{x}_{t+1})\|\leq\|\mathbf{v}(\mathbf{x}_{t})\|$ for all $t\geq 0$.

Then we proceed to bound $\sum_{t=0}^{+\infty}\|\mathbf{v}(\mathbf{x}_{t})\|^{2}$. Indeed, for any $x_{i}\in\mathcal{X}_{i}$, we have

Applying the equality $a^{\top}b=(\|a+b\|^{2}-\|a\|^{2}-\|b\|^{2})/2$ yields that

Summing up the resulting inequality over $i\in\mathcal{N}$ yields that

Letting $\mathbf{x}=\mathbf{x}^{*}\in\mathcal{X}^{*}$, we have

Since $\mathcal{G}$ is a $\lambda$-cocoercive game and $\mathbf{v}(\mathbf{x}^{*})=0$, we have

Putting these pieces together yields that

Plugging Eq. (26) into Eq. (25) together with the condition $\eta\in(0,\lambda]$ yields that

Summing up the above inequality over $t=0,1,2,\ldots$ and using the boundedness of $\mathcal{X}$ yields that

Note that $\mathbf{x}^{*}\in\mathcal{X}^{*}$ is chosen arbitrarily, we let $\mathbf{x}^{*}=\Pi_{\mathcal{X}^{*}}(\mathbf{x}_{0})$ and conclude the desired inequality.

Appendix C Postponed Proofs in Section A

In this section, we present the missing proofs in Section A.

By the definition of $\epsilon(\mathbf{x})$, we have

Using the update formula in Eq. (1), it holds that $\mathbf{v}(\mathbf{x}_{t})=\eta_{t+1}^{-1}(\mathbf{x}_{t+1}-\mathbf{x}_{t})-\xi_{t+1}$. Therefore, we have

Since $\mathcal{G}$ is a $\lambda$-cocoercive game, we have

Putting these pieces together yields that

Taking an expectation of Eq. (27) conditioned on $\mathcal{F}_{t}$ yields that

Taking the expectation of both sides yields the desired inequality.

C.2 Proof of Theorem A.2

Recalling Eq. (11) (cf. Lemma 4.1), we take the expectation of both sides conditioned on $\mathcal{F}_{t}$ to obtain

Since $\sum_{t=1}^{\infty}\eta_{t}^{2}<\infty$, we have $\eta_{t}\rightarrow 0$ as $t\rightarrow+\infty$. Without loss of generality, we assume $\eta_{t}\leq\lambda$ for all $t$. Then we have

We let $M_{t}=\|\mathbf{x}_{t}-\mathbf{x}^{*}\|^{2}+2\sigma^{2}(\sum_{j>t}\eta_{j}^{2})$ and obtain that $M_{t}$ is an nonnegative supermartingale. Then Doob’s martingale convergence theorem shows that $M_{n}$ converges to an nonnegative and integrable random variable almost surely. Let $M_{\infty}=\lim_{t\rightarrow+\infty}M_{t}$, it suffices to show that $M_{\infty}=0$ almost surely.

We first claim that every neighborhood $U$ of $\mathcal{X}^{*}$ is recurrent: there exists a subsequence $\mathbf{x}_{t_{k}}$ of $\mathbf{x}_{t}$ such that $\mathbf{x}_{t_{k}}\rightarrow\mathcal{X}^{*}$ almost surely. Equivalently, there exists a Nash equilibria $\mathbf{x}^{*}\in\mathcal{X}^{*}$ such that $\|\mathbf{x}_{t_{k}}-\mathbf{x}^{*}\|^{2}\rightarrow 0$ almost surely. To this end, we can define $M_{t}$ with such Nash equilibria. Since $\sum_{t=1}^{\infty}\eta_{t}^{2}<\infty$, we have $\sum_{j>t}\eta_{j}^{2}\rightarrow 0$ as $t\rightarrow+\infty$ and the following statement holds almost surely:

Since the whole sequence converges to $M_{\infty}$ almost surely, we conclude that $M_{\infty}=0$ almost surely.

Let $U$ be a neighborhood of $\mathcal{X}^{*}$ and assume to the contrary that, $\mathbf{x}_{t}\notin U$ for sufficiently large $t$ with positive probability. By starting the sequence at a later index if necessary and noting that $\sum_{t=1}^{\infty}\eta_{t}^{2}<\infty$, we may assume that $\mathbf{x}_{t}\notin U$ and $\eta_{t}\leq\lambda/2$ for all $t$ without loss of generality. Thus, there exists some $c>0$ such that $\|\mathbf{v}(\mathbf{x}_{t})\|^{2}\geq c$ for all $t$. As a result, for all $\mathbf{x}^{*}\in\mathcal{X}^{*}$, we let $\psi_{t+1}=(\mathbf{x}_{t}-\mathbf{x}^{*})^{\top}\xi_{t+1}$ and have

Summing up the above inequality over $t=0,1,\ldots,T$ together with $\theta_{t}=\sum_{j=1}^{t}\eta_{j}$ yields that

and the following inequality holds true for all $t\geq 1$:

From Doob’s martingale convergence theorem, $R_{t}$ converges to some random, finite value almost surely [Hall and Heyde 2014, Theorem 2.5]. Putting these pieces together with Eq. (29) yields that $\|\mathbf{x}_{t}-\mathbf{x}^{*}\|^{2}\sim-\lambda c\tau_{t}\rightarrow-\infty$ almost surely, a contradiction. Therefore, we conclude that every neighborhood of $\mathcal{X}^{*}$ is recurrent.

C.3 Proof of Theorem A.3

Since $\eta_{t}=c/\sqrt{t}$ for all $t\geq 1$, we have $\eta_{t}\rightarrow 0$ and $\eta_{t}\leq c$ for all $t\geq 1$. This implies that

Plugging Eq. (30) into Eq. (11) (cf. Lemma 4.1) yields that

Using the same argument as in Theorem A.2, we have

Taking the expectation of both sides of Eq. (31) and rearranging yields that

Summing up the above inequality over $t=0,1,\ldots,T$ and using $\eta_{t}=c/\sqrt{T+1}$ yields that

This implies that the following inequality holds for all $t\geq 1$:

C.4 Proof of Theorem A.4

Summing up the above inequality over $t=0,1,\ldots,T$ yields that

On the other hand, the derivation in Theorem A.3 implies that

This implies that the following inequality holds for all $t\geq 1$:

Putting these pieces together yields that