Fast Convergence of Regularized Learning in Games

Introduction

What happens when players in a game interact with one another, all of them acting independently and selfishly to maximize their own utilities? If they are smart, we intuitively expect their utilities — both individually and as a group — to grow, perhaps even to approach the best possible. We also expect the dynamics of their behavior to eventually reach some kind of equilibrium. Understanding these dynamics is central to game theory as well as its various application areas, including economics, network routing, auction design, and evolutionary biology.

It is natural in this setting for the players to each make use of a no-regret learning algorithm for making their decisions, an approach known as decentralized no-regret dynamics. No-regret algorithms are a strong match for playing games because their regret bounds hold even in adversarial environments. As a benefit, these bounds ensure that each player’s utility approaches optimality. When played against one another, it can also be shown that the sum of utilities approaches an approximate optimum , and the player strategies converge to an equilibrium under appropriate conditions , at rates governed by the regret bounds. Well-known families of no-regret algorithms include multiplicative-weights , Mirror Descent , and Follow the Regularized/Perturbed Leader . (See for excellent overviews.) For all of these, the average regret vanishes at the worst-case rate of $O(1/\sqrt{T})$, which is unimprovable in fully adversarial scenarios.

However, the players in our setting are facing other similar, predictable no-regret learning algorithms, a chink that hints at the possibility of improved convergence rates for such dynamics. This was first observed and exploited by Daskalakis et al. . For two-player zero-sum games, they developed a decentralized variant of Nesterov’s accelerated saddle point algorithm and showed that each player’s average regret converges at the remarkable rate of $O(1/T)$. Although the resulting dynamics are somewhat unnatural, in later work, Rakhlin and Sridharan showed surprisingly that the same convergence rate holds for a simple variant of Mirror Descent with the seemingly minor modification that the last utility observation is counted twice.

Although major steps forward, both these works are limited to two-player zero-sum games, the very simplest case. As such, they do not cover many practically important settings, such as auctions or routing games, which are decidedly not zero-sum, and which involve many independent actors.

In this paper, we vastly generalize these techniques to the practically important but far more challenging case of arbitrary multi-player normal-form games, giving natural no-regret dynamics whose convergence rates are much faster than previously possible for this general setting.

We show that the average welfare of the game, that is, the sum of player utilities, converges to approximately optimal welfare at the rate $O(1/T)$, rather than the previously known rate of $O(1/\sqrt{T})$. Concretely, we show a natural class of regularized no-regret algorithms with recency bias that achieve welfare at least $({\lambda}/({1+\mu}))\text{{Opt}}-O({1}/{T})$, where $\lambda$ and $\mu$ are parameters in a smoothness condition on the game introduced by Roughgarden . For the same class of algorithms, we show that each individual player’s average regret converges to zero at the rate $O\left(T^{-3/4}\right)$. Thus, our results entail an algorithm for computing coarse correlated equilibria in a decentralized manner with significantly faster convergence than existing methods.

Finally, we simulate a 4-bidder simultaneous auction game, and compare our optimistic algorithms against Hedge in terms of utilities, regrets and convergence to equilibria.

Repeated Game Model and Dynamics

We assume that the players each decide their strategy ${\bf w}_{i}^{t}$ based on a vanishing regret algorithm. Formally, for each player $i$, the regret after $T$ time steps is equal to the maximum gain he could have achieved by switching to any other fixed strategy:

The algorithm has vanishing regret if $r_{i}(T)=o(T)$.

This is the optimal welfare achievable in the absence of player incentives and if a central coordinator could dictate each player’s strategy. We next define a class of games first identified by Roughgarden on which we can approximate the optimal welfare using decoupled no-regret dynamics.

A game is $(\lambda,\mu)$-smooth if there exists a strategy profile ${\bf s}^{*}$ such that for any strategy profile ${\bf s}$: $\sum_{i\in N}u_{i}(s_{i}^{*},{\bf s}_{-i})\geq\lambda\text{{Opt}}-\mu W({\bf s})$.

In words, any player using his optimal strategy continues to do well irrespective of other players’ strategies. This condition directly implies near-optimality of no-regret dynamics as we show below.

In a $(\lambda,\mu)$-smooth game, if each player $i$ suffers regret at most $r_{i}(T)$, then:

where the factor $\rho=(1+\mu)/\lambda$ is called the price of anarchy (PoA ).

This proposition is essentially a more explicit version of Roughgarden’s result ; we provide a proof in the appendix for completeness. The result shows that the convergence to PoA is driven by the quantity $\frac{1}{1+\mu}\frac{1}{T}\sum_{i\in N}r_{i}(T)$. There are many algorithms which achieve a regret rate of $r_{i}(T)=O(\sqrt{\log(d)T})$, in which case the latter theorem would imply that the average welfare converges to PoA at a rate of $O(n\sqrt{\log(d)/T})$. As we will show, for some natural classes of no-regret algorithms the average welfare converges at the much faster rate of $O(n^{2}\log(d)/T)$.

Fast Convergence to Approximate Efficiency

In this section, we present our main theoretical results characterizing a class of no-regret dynamics which lead to faster convergence in smooth games. We begin by describing this class.

We say that a vanishing regret algorithm satisfies the Regret bounded by Variation in Utilities (RVU) property with parameters $\alpha>0$ and $0<\beta\leq\gamma$ and a pair of dual norms $(\|\cdot\|,\|\cdot\|_{*})$The dual to a norm $\|\cdot\|$ is defined as $\|v\|_{*}=\sup_{\|u\|\leq 1}\left\langle u,v\right\rangle$. if its regret on any sequence of utilities ${\bf u}^{1},{\bf u}^{2},\ldots,{\bf u}^{T}$ is bounded as

Typical online learning algorithms such as Mirror Descent and FTRL do not satisfy the RVU property in their vanilla form, as the middle term grows as $\sum_{t=1}^{T}\|{\bf u}^{t}\|_{*}^{2}$ for these methods. However, Rakhlin and Sridharan give a modification of Mirror Descent with this property, and we will present a similar variant of FTRL in the sequel.

We now present two sets of results when each player uses an algorithm with this property. The first discusses the convergence of social welfare, while the second governs the convergence of the individual players’ utilities at a fast rate.

Given Proposition 2, we only need to understand the evolution of the sum of players’ regrets $\sum_{t=1}^{T}r_{i}(T)$ in order to obtain convergence rates of the social welfare. Our main result in this section bounds this sum when each player uses dynamics with the RVU property.

Suppose that the algorithm of each player $i$ satisfies the property RVU with parameters $\alpha,\beta$ and $\gamma$ such that $\beta\leq\gamma/(n-1)^{2}$ and $\|\cdot\|=\|\cdot\|_{1}$. Then $\sum_{i\in N}r_{i}(T)\leq\alpha n$.

Since $u_{i}({\bf s})\leq 1$, definitions imply: $\|{\bf u}_{i}^{t}-{\bf u}_{i}^{t-1}\|_{*}\leq\sum_{{\bf s}_{-i}}\left|\prod_{j\neq i}w_{j,s_{j}}^{t}-\prod_{j\neq i}w_{j,s_{j}}^{t-1}\right|.$ The latter is the total variation distance of two product distributions. By known properties of total variation (see e.g. ), this is bounded by the sum of the total variations of each marginal distribution:

By Jensen’s inequality, $\left(\sum_{j\neq i}\|{\bf w}_{j}^{t}-{\bf w}_{j}^{t-1}\|\right)^{2}\leq(n-1)\sum_{j\neq i}\|{\bf w}_{j}^{t}-{\bf w}_{j}^{t-1}\|^{2}$, so that

The theorem follows by summing up the RVU property (1) for each player $i$ and observing that the summation of the second terms is smaller than that of the third terms and thereby can be dropped.

We now instantiate the result with examples that satisfy the RVU property with different constants.

The optimistic mirror descent (OMD) algorithm of Rakhlin and Sridharan is parameterized by an adaptive predictor sequence ${\bf M}_{i}^{t}$ and a regularizerHere and in the sequel, we can use a different regularizer $\mathcal{R}_{i}$ for each player $i$, without qualitatively affecting any of the results. $\mathcal{R}$ which is $1$-strongly convex$\mathcal{R}$ is 1-strongly convex if $\mathcal{R}\left(\frac{u+v}{2}\right)\leq\frac{\mathcal{R}(u)+\mathcal{R}(v)}{2}-\frac{\|u-v\|^{2}}{8}$, $\forall u,v$. with respect to a norm $\|\cdot\|$. Let $D_{\mathcal{R}}$ denote the Bregman divergence associated with $\mathcal{R}$. Then the update rule is defined as follows: let ${\bf g}_{i}^{0}=\operatorname*{argmin}_{{\bf g}\in\Delta(S_{i})}\mathcal{R}({\bf g})$ and

Then the following proposition can be obtained for this method.

The OMD algorithm using stepsize $\eta$ and ${\bf M}_{i}^{t}={\bf u}_{i}^{t-1}$satisfies the RVU property with constants $\alpha=R/\eta$, $\beta=\eta$, $\gamma=1/(8\eta)$, where $R=\max_{i}\sup_{f}D_{\mathcal{R}}(f,{\bf g}_{i}^{0})$.

The proposition follows by further crystallizing the arguments of Rakhlin and Sridaran , and we provide a proof in the appendix for completeness. The above proposition, along with Theorem 4, immediately yields the following corollary, which had been proved by Rakhlin and Sridharan for two-person zero-sum games, and which we here extend to general games.

If each player runs OMD with ${\bf M}_{i}^{t}={\bf u}_{i}^{t-1}$ and stepsize $\eta=1/(\sqrt{8}(n-1))$, then we have $\sum_{i\in N}r_{i}(T)\leq nR/\eta\leq n(n-1)\sqrt{8}R=O(1)$.

The corollary follows by noting that the condition $\beta\leq\gamma/(n-1)^{2}$ is met with our choice of $\eta$.

1.2 Optimistic Follow the Regularized Leader

We next consider a different class of algorithms denoted as optimistic follow the regularized leader (OFTRL). This algorithm is similar but not equivalent to OMD, and is an analogous extension of standard FTRL . This algorithm takes the same parameters as for OMD and is defined as follows: Let ${\bf w}_{i}^{0}=\operatorname*{argmin}_{{\bf w}\in\Delta(S_{i})}\mathcal{R}({\bf w})$ and:

We consider three variants of OFTRL with different choices of the sequence ${\bf M}_{i}^{t}$, incorporating the recency bias in different forms.

The simplest form of OFTRL uses ${\bf M}_{i}^{t}={\bf u}_{i}^{t-1}$ and obtains the following result, where $R=\max_{i}\left(\sup_{{\bf f}\in\Delta(S_{i})}\mathcal{R}({\bf f})-\inf_{{\bf f}\in\Delta(S_{i})}\mathcal{R}({\bf f})\right)$.

The OFTRL algorithm using stepsize $\eta$ and ${\bf M}_{i}^{t}={\bf u}_{i}^{t-1}$ satisfies the RVU property with constants $\alpha=R/\eta$, $\beta=\eta$ and $\gamma=1/(4\eta).$

Combined with Theorem 4, this yields the following constant bound on the total regret of all players:

If each player runs OFTRL with ${\bf M}_{i}^{t}={\bf u}_{i}^{t-1}$ and $\eta=1/(2(n-1))$, then we have $\sum_{i\in N}r_{i}(T)\leq nR/\eta\leq 2n(n-1)R=O(1).$

Rakhlin and Sridharan also analyze an FTRL variant, but require a self-concordant barrier for the constraint set as opposed to an arbitrary strongly convex regularizer, and their bound is missing the crucial negative terms of the RVU property which are essential for obtaining Theorem 4.

More generally, given a window size $H$, one can define ${\bf M}_{i}^{t}=\sum_{\tau=t-H}^{t-1}{\bf u}_{i}^{\tau}/H$. We have the following proposition.

The OFTRL algorithm using stepsize $\eta$ and ${\bf M}_{i}^{t}=\sum_{\tau=t-H}^{t-1}{\bf u}_{i}^{\tau}/H$ satisfies the RVU property with constants $\alpha=R/\eta$, $\beta=\eta H^{2}$ and $\gamma=1/(4\eta).$

Setting $\eta=1/(2H(n-1))$, we obtain the analogue of Corollary 8, with an extra factor of $H$.

The next proposition considers an alternative form of recency bias which includes all the previous utilities, but with a geometric discounting.

The OFTRL algorithm using stepsize $\eta$ and ${\bf M}_{i}^{t}=\frac{1}{\sum_{\tau=0}^{t-1}\delta^{-\tau}}\sum_{\tau=0}^{t-1}\delta^{-\tau}{\bf u}_{i}^{\tau}$ satisfies the RVU property with constants $\alpha=R/\eta$, $\beta=\eta/(1-\delta)^{3}$ and $\gamma=1/(8\eta).$

Note that these choices for ${\bf M}_{i}^{t}$ can also be used in OMD with qualitatively similar results.

2 Fast Convergence of Individual Utilities

The previous section shows implications of the RVU property on the social welfare. This section complements these with a similar result for each player’s individual utility.

Suppose that the players use algorithms satisfying the RVU property with parameters $\alpha>0,\beta>0,\gamma\geq 0$. If we further have the stability property $\|{\bf w}_{i}^{t}-{\bf w}_{i}^{t+1}\|\leq\kappa$, then for any player $\sum_{t=1}^{T}\left\langle{\bf w}_{i}^{*}-{\bf w}_{i}^{t},{\bf u}_{i}^{t}\right\rangle\leq\alpha+\beta\kappa^{2}(n-1)^{2}T.$

Similar reasoning as in Theorem 4 yields: $\|{\bf u}_{i}^{t}-{\bf u}_{i}^{t-1}\|_{*}^{2}\leq(n-1)\sum_{j\neq i}\|{\bf w}_{j}^{t}-{\bf w}_{j}^{t-1}\|^{2}\leq(n-1)^{2}\kappa^{2}$, and summing the terms gives the theorem.

Noting that OFTRL satisfies the RVU property with constants given in Proposition 7 and stability property with $\kappa=2\eta$ (see Lemma 20 in the appendix), we have the following corollary.

If all players use the OFTRL algorithm with ${\bf M}_{i}^{t}={\bf u}_{i}^{t-1}$ and $\eta=(n-1)^{-1/2}T^{-1/4}$, then we have $\sum_{t=1}^{T}\left\langle{\bf w}_{i}^{*}-{\bf w}_{i}^{t},{\bf u}_{i}^{t}\right\rangle\leq(R+4)\sqrt{n-1}\cdot T^{1/4}.$

Similar results hold for the other forms of recency bias, as well as for OMD. Corollary 12 gives a fast convergence rate of the players’ strategies to the set of coarse correlated equilibria (CCE) of the game. This improves the previously known convergence rate $\sqrt{T}$ (e.g. ) to CCE using natural, decoupled no-regret dynamics defined in .

Robustness to Adversarial Opponent

In order to present our modification, we need a parametric form of the RVU property which will also involve a tunable parameter of the algorithm. For most online learning algorithms, this will correspond to the step-size parameter used by the algorithm.

We say that a parametric algorithm $\mathcal{A}(\rho)$ satisfies the Regret bounded by Variation in Utilities$(\rho)$ ($\texttt{RVU}(\rho)$) property with parameters $\alpha,\beta,\gamma>0$ and a pair of dual norms $(\|\cdot\|,\|\cdot\|_{*})$ if its regret on any sequence of utilities ${\bf u}^{1},{\bf u}^{2},\ldots,{\bf u}^{T}$ is bounded as

In both OMD and OFTRL algorithms from Section 3, the parameter $\rho$ is precisely the stepsize $\eta$. We now show an adaptive choice of $\rho$ according to an epoch-based doubling schedule.

Given a parametric algorithm $\mathcal{A}(\rho)$ as a black-box we construct a wrapper $\mathcal{A}^{\prime}$ based on the doubling trick: The algorithm of each player proceeds in epochs. At each epoch $r$ the player $i$ has an upper bound of $B_{r}$ on the quantity $\sum_{t=1}^{T}\|{\bf u}_{i}^{t}-{\bf u}_{i}^{t-1}\|_{*}^{2}$. We start with a parameter $\eta_{*}$ and $B_{1}=1$, and for $\tau=1,2,\ldots,T$ repeat:

Play according to $\mathcal{A}(\eta_{r})$ and receive ${\bf u}_{i}^{\tau}$.

If $\sum_{t=1}^{\tau}|{\bf u}_{i}^{t}-{\bf u}_{i}^{t-1}\|_{*}^{2}\geq B_{r}$:

Update $r\leftarrow r+1$, $B_{r}\leftarrow 2B_{r}$, $\eta_{r}=\min\left\{\frac{\alpha}{\sqrt{B_{r}}},\eta_{*}\right\}$, with $\alpha$ as in Equation (3).

Start a new run of $\mathcal{A}$ with parameter $\eta_{r}$.

Algorithm $\mathcal{A}^{\prime}$ achieves regret at most the minimum of the following two terms:

Observe that for such $\eta^{*}$, we have that: $(2+\eta_{*}\cdot\beta)\log(T)\leq(2+\beta)\log(T)\leq\frac{\gamma}{\eta_{*}(n-1)^{2}}$. Therefore, algorithm $\mathcal{A}^{\prime}$, satisfies the sufficient conditions of Theorem 4.

An analogue of Theorem 11 can also be established for this algorithm:

Once again, OFTRL satisfies the above conditions with $\kappa=2$, implying robust convergence.

Experimental Evaluation

We analyzed the performance of optimistic follow the regularized leader with the entropy regularizer, which corresponds to the Hedge algorithm modified so that the last iteration’s utility for each strategy is double counted; we refer to it as Optimistic Hedge. More formally, the probability of player $i$ playing strategy $j$ at iteration $T$ is proportional to $\exp\left(-\eta\cdot\left(\sum_{t=1}^{T-2}u_{ij}^{t}+2u_{ij}^{T-1}\right)\right)$, rather than $\exp\left(-\eta\cdot\sum_{t=1}^{T-1}u_{ij}^{t}\right)$ as is standard for Hedge.

We studied a simple auction where $n$ players are bidding for $m$ items. Each player has a value $v$ for getting at least one item and no extra value for more items. The utility of a player is the value for the allocation he derived minus the payment he has to make. The game is defined as follows: simultaneously each player picks one of the $m$ items and submits a bid on that item (we assume bids to be discretized). For each item, the highest bidder wins and pays his bid. We let players play this game repeatedly with each player invoking either Hedge or optimistic Hedge. This game, and generalizations of it, are known to be $(1-1/e,0)$-smooth , if we also view the auctioneer as a player whose utility is the revenue. The welfare of the game is the value of the resulting allocation, hence not a constant-sum game. The welfare maximization problem corresponds to the unweighted bipartite matching problem. The PoA captures how far from the optimal matching is the average allocation of the dynamics. By smoothness we know it converges to at least $1-1/e$ of the optimal.

We run the game for $n=4$ bidders and $m=4$ items and valuation $v=20$. The bids are discretized to be any integer in $$. We find that the sum of the regrets and the maximum individual regret of each player are remarkably lower under Optimistic Hedge as opposed to Hedge. In Figure 1 we plot the maximum individual regret as well as the sum of the regrets under the two algorithms, using$\eta=0.1$ for both methods. Thus convergence to the set of coarse correlated equilibria is substantially faster under Optimistic Hedge, confirming our results in Section 3.2. We also observe similar behavior when each player only has value on a randomly picked player-specific subset of items, or uses other step sizes.

We observe that the behavior under Optimistic Hedge is more stable than under Hedge. In Figure 2, we plot the expected bid of a player on one of the items and his expected utility under the two dynamics. Hedge exhibits the sawtooth behavior that was observed in generalized first price auction run by Overture (see [5, p. 21]). In stunning contrast, Optimistic Hedge leads to more stable expected bids over time. This stability property of optimistic Hedge is one of the main intuitive reasons for the fast convergence of its regret.

In this class of games, we did not observe any significant difference between the average welfare of the methods. The key reason is the following: the proof that no-regret dynamics are approximately efficient (Proposition 2) only relies on the fact that each player does not have regret against the strategy $s_{i}^{*}$ used in the definition of a smooth game. In this game, regret against these strategies is experimentally comparable under both algorithms, even though regret against the best fixed strategy is remarkably different. This indicates a possibility for faster rates for Hedge in terms of welfare. In Appendix H, we show fast convergence of the efficiency of Hedge for cost-minimization games, though with a worse PoA .

Discussion

This work extends and generalizes a growing body of work on decentralized no-regret dynamics in many ways. We demonstrate a class of no-regret algorithms which enjoy rapid convergence when played against each other, while being robust to adversarial opponents. This has implications in computation of correlated equilibria, as well as understanding the behavior of agents in complex multi-player games. There are a number of interesting questions and directions for future research which are suggested by our results, including the following:

Convergence rates for vanilla Hedge: The fast rates of our paper do not apply to algorithms such as Hedge without modification. Is this modification to satisfy RVU only sufficient or also necessary? If not, are there counterexamples? In the supplement, we include a sketch hinting at such a counterexample, but also showing fast rates to a worse equilibrium than our optimistic algorithms.

Convergence of players’ strategies: The OFTRL algorithm often produces much more stable trajectories empirically, as the players converge to an equilibrium, as opposed to say Hedge. A precise quantification of this desirable behavior would be of great interest.

Better rates with partial information: If the players do not observe the expected utility function, but only the moves of the other players at each round, can we still obtain faster rates?

References

Appendix A Proof of Proposition 2

Proposition 2. In a $(\lambda,\mu)$-smooth game, if each player $i$ suffers regret at most $r_{i}(T)$, then:

where the factor $\rho=(1+\mu)/\lambda$ is called the price of total anarchy (PoA ).

Since each player $i$ has regret $r_{i}(T)$, we have that:

Summing over all players and using the smoothness property:

Appendix B Proof of Proposition 5

Proposition 5. The OMD algorithm using stepsize $\eta$ and ${\bf M}_{i}^{t}={\bf u}_{i}^{t-1}$satisfies the RVU property with constants $\alpha=R/\eta$, $\beta=\eta$, $\gamma=1/(8\eta)$, where $R=\max_{i}\sup_{f}D_{\mathcal{R}}(f,{\bf g}_{i}^{0})$.

The regret of a player under optimistic mirror descent and with respect to any ${\bf w}_{i}^{*}\in\Delta(S_{i})$ is upper bounded by:

where $R=\sup_{f}D_{\mathcal{R}}(f,g_{0})$.

We show that if the players use optimistic mirror descent with ${\bf M}_{i}^{t}={\bf u}_{i}^{t-1}$, then the regret of each player satisfies the sufficient condition presented in the previous section. Some of the key facts (Equations (9) and (10)) that we use in the following proof appear in . However, the formulation of the regret that we present in the following theorem is not immediately clear in their proof, so we present it here for clarity and completeness.

The regret of a player under optimistic mirror descent with ${\bf M}_{i}^{t}={\bf u}_{i}^{t-1}$ and with respect to any ${\bf w}_{i}^{*}\in\Delta(S_{i})$ is upper bounded by:

By Theorem 17, instantiated for ${\bf M}_{i}^{t}={\bf u}_{i}^{t-1}$, we get:

For $\rho=2\eta$, the latter simplifies to:

Dividing over by $\frac{1}{8\eta}$ and applying it in the previous upper bound on the regret, we get:

Appendix C Proof of Proposition 7

Proposition 7. The OFTRL algorithm using stepsize $\eta$ and ${\bf M}_{i}^{t}={\bf u}_{i}^{t-1}$ satisfies the RVU property with constants $\alpha=R/\eta$, $\beta=\eta$ and $\gamma=1/(4\eta).$

We first show that these algorithms achieve the same regret bounds as optimistic mirror descent. This result does not appear in previous work in any form.

Even though the algorithms do not make use of a secondary sequence, we will still use in the analysis the notation:

These secondary variables are often called be the leader sequence as they can see one step in the future.

The regret of a player under optimistic FTRL and with respect to any ${\bf w}_{i}^{*}\in\Delta(S_{i})$ is upper bounded by:

where $R=\sup_{{\bf f}}\mathcal{R}({\bf f})-\inf_{{\bf f}}\mathcal{R}({\bf f})$.

Without loss of generality we will assume that $\inf_{{\bf f}}\mathcal{R}({\bf f})=0$. Since $\left\langle{\bf g}_{i}^{t}-{\bf w}_{i}^{t},{\bf u}_{i}^{t}-{\bf M}_{i}^{t}\right\rangle\leq\|{\bf g}_{i}^{t}-{\bf w}_{i}^{t}\|\|{\bf u}_{i}^{t}-{\bf M}_{i}^{t}\|_{*}$, it suffices to show that for any ${\bf w}_{i}^{*}\in\Delta(S_{i})$:

For shorthand notation let: $I_{T}=\frac{1}{2\eta}\sum_{t=1}^{T}\left(\|{\bf w}_{i}^{t}-{\bf g}_{i}^{t}\|^{2}+\|{\bf w}_{i}^{t}-{\bf g}_{i}^{t-1}\|^{2}\right)$. By induction assume that for all ${\bf w}_{i}^{*}$:

Apply the above for ${\bf w}_{i}^{*}={\bf g}_{i}^{T-1}$ and add $\left\langle{\bf g}_{i}^{T}-{\bf w}_{i}^{T},{\bf M}_{i}^{T}\right\rangle-\left\langle{\bf g}_{i}^{T},{\bf u}_{i}^{T}\right\rangle$ on both sides:

The inequalities follow by the optimality of the corresponding variable that was changed and by the strong convexity of $\mathcal{R}(\cdot)$. The final vector ${\bf q}_{i}^{*}$ is an arbitrary vector in $\Delta(S_{i})$. The base case of $T=0$ follows trivially by $\mathcal{R}({\bf f})\geq 0$ for all ${\bf f}$. This concludes the inductive proof.

Thus optimistic FTRL achieves the exact same form of regret presented in Theorem 17 for optimistic mirror descent. Hence, the equivalent versions of Theorem 18 and Corollary 6 hold also for the optimistic FTRL algorithm. In fact we are able to show slightly stronger bounds for optimistic FTRL, based on the following lemmas.

Let $F_{T}({\bf f})=\left\langle{\bf f},\sum_{t=1}^{T-1}{\bf u}_{i}^{t}+{\bf M}_{i}^{T}\right\rangle-\eta^{-1}\mathcal{R}({\bf f})$ and $G_{T}({\bf f})=\left\langle{\bf f},\sum_{t=1}^{T}{\bf u}_{i}^{t}\right\rangle-\eta^{-1}\mathcal{R}({\bf f})$. Observe that: $F_{T}({\bf f})-G_{T}({\bf f})=\left\langle{\bf f},{\bf M}_{i}^{T}-{\bf u}_{i}^{T}\right\rangle$ and $F_{T+1}({\bf f})-G_{T}({\bf f})=\left\langle{\bf f},{\bf M}_{i}^{T+1}\right\rangle$.

By the optimality of ${\bf w}_{i}^{T}$ and ${\bf g}_{i}^{T}$ and the strong convexity of $\mathcal{R}(\cdot)$:

Adding both inequalities and using the previous observations:

Dividing over by $\|{\bf w}_{i}^{T}-{\bf g}_{i}^{T}\|$ gives the first inequality of the lemma.

By the optimality of ${\bf g}_{i}^{T}$ and ${\bf w}_{i}^{T+1}$ and strong convexity:

Dividing over by $\|{\bf w}_{i}^{T+1}-{\bf g}_{i}^{T}\|$, yields second inequality of the lemma.

Given Theorem 19 and Lemma 20, the proposition immediately follows since

Replacing ${\bf M}_{i}^{t}$ with ${\bf u}_{i}^{t-1}$ and using Inequality (10), yields the result.

Appendix D Proof of Proposition 9

Proposition 9. The OFTRL algorithm using stepsize $\eta$ and ${\bf M}_{i}^{t}=\sum_{\tau=t-H}^{t-1}{\bf u}_{i}^{\tau}/H$ satisfies the RVU property with constants $\alpha=R/\eta$, $\beta=\eta H^{2}$ and $\gamma=1/(4\eta).$

The proposition is equivalent to the following lemma, which we will state and prove in this appendix.

For the optimistic FTRL algorithm with ${\bf M}_{i}^{t}=\frac{1}{H}\sum_{\tau=t-H}^{t-1}{\bf u}_{i}^{\tau}$, the regret is upper bounded by:

where $R=\sup_{{\bf f}}\mathcal{R}({\bf f})-\inf_{{\bf f}}\mathcal{R}({\bf f})$. Thus we get $\sum_{i}r_{i}(T)\leq\frac{nR}{\eta}=2n(n-1)HR$ for $\eta=\frac{1}{2H(n-1)}$.

Similar to Proposition 7, by Theorem 19, Lemma 20 and Inequality (10) we get:

Appendix E Proof of Proposition 10

Proposition 10. The OFTRL algorithm using stepsize $\eta$ and ${\bf M}_{i}^{t}=\frac{1}{\sum_{\tau=0}^{t-1}\delta^{-\tau}}\sum_{\tau=0}^{t-1}\delta^{-\tau}{\bf u}_{i}^{\tau}$ satisfies the RVU property with constants $\alpha=R/\eta$, $\beta=\eta/(1-\delta)^{3}$ and $\gamma=1/(8\eta).$

The proposition is equivalent to the following lemma which we will prove in this appendix.

For the optimistic FTRL algorithm with ${\bf M}_{i}^{t}=\frac{1}{\sum_{\tau=0}^{t}\delta^{-\tau}}\sum_{\tau=0}^{t-1}\delta^{-\tau}{\bf u}_{i}^{\tau}$ for some discount rate $\delta\in(0,1)$, the regret is upper bounded by:

where $R=\sup_{{\bf f}}\mathcal{R}({\bf f})-\inf_{{\bf f}}\mathcal{R}({\bf f})$. Thus we get $\sum_{i}r_{i}(T)\leq\frac{nR}{\eta}=2n(n-1)\frac{1}{(1-\delta)^{3/2}}R$ for $\eta=\frac{(1-\delta)^{3/2}}{2(n-1)}$.

We show the theorem for the case of optimistic FTRL. The OMD case follows analogously. Similar to Lemma 21 the regret is upper bounded by:

Summing over all $t$ and re-arranging we get:

Appendix F Proof of Theorem 14

Theorem 14. Algorithm $\mathcal{A}^{\prime}$ achieves regret at most the minimum of the following two terms:

We break the proof in the two corresponding parts.

Consider a round $r$ and let $T_{r}$ be its final iteration. Also let $I_{r}=\sum_{t=1}^{T_{r}}\|{\bf u}_{i}^{t}-{\bf u}_{i}^{t-1}\|_{*}^{2}$. First observe that by the definition of $B_{r}$:

By the definition of $\eta$, we know that

By the regret guarantee of algorithm $\mathcal{A}(\eta_{r})$, we have that:

Since $\sqrt{B_{r}}\leq B_{r}+1\leq 2\cdot I_{r}+2$:

Since at each round we are doubling the bound $B_{r}$ and since $\sum_{t=1}^{T}\|{\bf u}_{i}^{t}-{\bf u}_{i}^{t-1}\|_{*}^{2}\leq T$, there are at most $\log(T)$ rounds. Summing up the above inequality for each of the at most $\log(T)$ rounds, yields the claimed bound in Equation (4).

Again consider any round $r$. By Equations (18), (19), the fact that $\eta\leq\frac{\alpha}{\sqrt{B_{r}}}\leq\frac{\alpha\sqrt{2}}{\sqrt{I_{r}}}$ and by the regret of algorithm $\mathcal{A}(\eta_{r})$:

Again since the number of rounds is at most $\log(T)$, by summing up the above bound for each round $r$, we get the second part of the theorem.

Appendix G Proof of Corollary 16

Observe that at any round of $\mathcal{A}^{\prime}$, algorithm $\mathcal{A}$ is run with $\eta_{r}\leq\eta_{*}$. Thus by the property of algorithm $\mathcal{A}$, we have that at every iteration: $\|{\bf w}_{i}^{t}-{\bf w}_{i}^{t-1}\|\leq\kappa\eta_{*}=\kappa T^{-1/4}$. If all players use algorithm $\mathcal{A}^{\prime}$, then by similar reasoning as in Theorem 4 we know that:

Hence, by Equation 5, the regret of each player is bounded by:

Appendix H Fast convergence via a first order regret bound for cost-minimization

for some absolute constants $A_{1}$ and $A_{2}$. Note that this form of first order bound can be achieved by a variety of algorithms such as Hedge with appropriate learning rate tuning. Under this setup, we prove the following:

If a game is $(\lambda,\mu)$-smooth and each player uses a no-regret algorithm with a regret satisfying Eq. (21), then we have

where $A=\frac{A_{1}^{2}\mu}{(1-\mu)^{2}}+\frac{2A_{2}}{1-\mu}$.

Using the regret bound and Cauchy-Schwarz inequality, we have

and therefore $\sum_{t=1}^{T}\sum_{i\in N}c^{t}_{i,s_{i}^{*}}\leq x^{2}$ where we define $x=\sqrt{\lambda T\text{{Opt}}^{\prime}+\mu\sum_{t=1}^{T}C({\bf w}^{t})}$. Now applying this bound in Eq. (22), we continue with

Rearranging gives a quadratic inequality $ax^{2}+bx+c\leq 0$ with

Finally solving for $\sum_{t=1}^{T}C({\bf w}^{t})$ (hidden in the definition of $x$) gives the bound stated in the theorem.

Note that the price of total anarchy is larger than the one achieved by previous analysis by a multiplicative factor of $1+\frac{1}{\mu}$, but the convergence rate is much faster ($n$ times faster compared to optimistic mirror descent or optimistic FTRL).

Appendix I Extension to continuous strategy space games

In this section we extend our results to continuous strategy space games such as for instance ”splittable selfish routing games” (see e.g. ). These are games where the price of anarchy has been well studied and quite well motivated from internet routing. In these games we consider the dynamics where the players simply observe the past play of their opponents and not the expected past play. We consider dynamics where players don’t use mixed strategies, but are simply doing online convex optimization algorithms on their continuous strategy spaces. Such learning on continuous games has also been studied in more restrictive settings in .

We make the following two assumptions on the costs:

(Convex in player strategy) For each player $i$ and for each profile of opponent strategies ${\bf w}_{-i}$, the function $c_{i}(\cdot,{\bf w}_{-i})$ is convex in ${\bf w}_{i}$.

Observe that a sufficient condition for Property (2) is that the function $\delta_{i}({\bf w})$ is coordinate-wise $L$-lipschitz with respect to the $\|\cdot\|$ norm.

then $\delta_{i}(\cdot)$ satisfies Property (2).

For any two vectors ${\bf w}$ and ${\bf y}$, think of switching from the one to the other by switching sequentially each player from his strategy ${\bf w}_{i}$ to ${\bf y}_{i}$, keeping the remaining players fixed and in some pre-fixed player order. The difference $\|\delta_{i}({\bf w})-\delta_{i}({\bf y})\|_{*}$ is upper bounded by the sum of the differences of these sequential switches. The difference of each such unilateral switch for each player $j$ is turn upper bounded by $\|{\bf w}_{j}-{\bf y}_{j}\|$, by the property assumed in the Lemma. The lemma then follows.

The second assumption is also satisfied, albeit with a slightly more involved proof, which appears in the proof of Theorem 4. Basically, observe that

Where the last inequality holds by the properties of total variation distance.

For an edge $e$, let $f_{i,e}({\bf w}_{i})=\sum_{p\in\mathcal{P}_{i}:e\in p}w_{i,p}$ to be the flow on edge $e$ caused by player $i$ and with $f_{e}({\bf w})=\sum_{i}f_{i,e}({\bf w}_{i})$ to be the total flow on the edge $e$. Then the cost of a player is:

Thus we get that the second condition is satisfied with $L=2Km$.

For these games we will assume that the players are performing some form of regularized learning using the gradients of their utilities as proxies. For fast convergence we would require that the algorithms they use satisfy the following property, which is a generalization of Theorem 4.

Consider a repeated continuous strategy space game where the cost functions satisfy properties $1,2$. Suppose that the algorithm of each player $i$ satisfies the property that for any ${\bf w}_{i}^{*}\in S_{i}$

for some $\alpha>0$ and $0<\beta\leq\frac{\gamma}{L^{2}\cdot n^{2}}$ and with $\|\cdot\|$ we denote the $\|\cdot\|_{1}$ norm. Then:

By summing up the regret inequality for each player and using the above bound we get:

If $\beta L^{2}n^{2}\leq\gamma$, the theorem follows.

All the algorithms that we described in the previous sections can be adapted to satisfy the bound required by Theorem 25, by simply using the gradient of the cost as a proxy of the cost instead of the actual cost. This follows by standard arguments. Hence if players follow for instance the following adaptation of the regularized leader algorithm:

then by Proposition 7 we get that their regret satisfies the conditions of Theorem 25 for $a=\frac{R}{\eta}$, $\beta=\eta$ and $\gamma=\frac{1}{4\eta}$, where $R=\operatorname*{argmax}_{{\bf w}_{i}\in S_{i}}R({\bf w}_{i})$. We need that $\eta L^{2}n^{2}\leq\frac{1}{4\eta}$ or equivalently $\eta\leq\frac{1}{2Ln}$. Thus for $\eta=\frac{1}{2Ln}$, if all players are using the latter algorithm we get regret of at most $n\cdot\frac{R}{\eta}=2Ln^{2}R$

Example. (Splittable congestion games). Consider the case of congestion games with splittable flow, where all the latencies and their derivatives are $K$-Lipschitz and the flow of each player is at most $B$. In that setting, suppose that we use the entropic regularizer. Then for each player $i$, $R\leq B\cdot\log(|\mathcal{P}_{i}|)$. The number of possible $(s,t)$ paths is at most $2^{m}$, which yields $R\leq B\cdot m$. Hence, by using the linearized follow the regularized leader, we get that the total regret is at most $2Ln^{2}R\leq 2K(B+1)Bm^{2}n^{2}$.

Appendix J Ω​(T)Ω𝑇\Omega(\sqrt{T}) Lower Bounds on Regret for other Dynamics

We consider a two-player zero-sum game which can be described by a utility matrix $A$. Assume the row player uses MWU with a fixed learning rate $\eta$, and the column player plays the best response, that is, a pure strategy that minimizes the row player’s expected utility for the current round. Then the following theorem states that no matter how $\eta$ is set, there is always a game $A$ such that the regret of the row player is at least $\Omega(\sqrt{T})$.

In the setting described above, let $r(T)$ and $r^{\prime}(T)$ be the regret of the row player for the game $A=\begin{pmatrix}1&0\\ 0&1\end{pmatrix}$ and $A^{\prime}=\begin{pmatrix}1\\ 0\end{pmatrix}$ respectively after $T$ rounds. Then $\max\{r(T),r^{\prime}(T)\}\geq\Omega(\sqrt{T})$.

For game $A$, according to the setup, one can verify that the row player will play a uniform distribution and receive utility $\frac{1}{2}$ on round $t$ where $t$ is odd, and for the next round $t+1$, the row player will put slightly more weights on one row and the column player will pick the column that has utility for that row. Specifically, the expected utility of the row player is $\frac{e^{\eta(t-1)/2}}{e^{\eta(t-1)/2}+e^{\eta(t+1)/2}}=\frac{1}{1+e^{\eta}}$. Therefore, the regret is (assuming $T$ is even for simplicity)

For game $A^{\prime}$, the expected utility of the row player on round $t$ is $\frac{e^{\eta(t-1)}}{e^{\eta(t-1)}+1}$, and thus the regret is

Now if $\eta\geq 1$, then $r(T)\geq\frac{T}{2}\cdot\frac{e-1}{e+1}=\Omega(T)$. If $\eta\leq\frac{1}{T}$, then $r^{\prime}(T)\geq\frac{1-e^{-1}}{2(1-e^{-\frac{1}{T}})}\geq\frac{T(1-e^{-1})}{2}=\Omega(T)$. Finally when $\frac{1}{T}\leq\eta\leq 1$, we have

To sum up, we have $\max\{r(T),r^{\prime}(T)\}\geq\Omega(\sqrt{T})$.