# Taming the Exponential Action Set: Sublinear Regret and Fast Convergence to
Nash Equilibrium in Online Congestion Games

Jing Dong<EMAIL_ADDRESS>
The Chinese University of Hong Kong, Shenzhen
Jingyu Wu<EMAIL_ADDRESS>
University of Science and Technology of China
Siwei Wang<EMAIL_ADDRESS>
Microsoft Research Asia
Baoxiang Wang<EMAIL_ADDRESS>
The Chinese University of Hong Kong, Shenzhen
Wei Chen<EMAIL_ADDRESS>
Microsoft Research Asia

###### Abstract

The congestion game is a powerful model that encompasses a range of
engineering systems such as traffic networks and resource allocation. It
describes the behavior of a group of agents who share a common set of $F$
facilities and take actions as subsets with $k$ facilities. In this work, we
study the online formulation of congestion games, where agents participate in
the game repeatedly and observe feedback with randomness. We propose
CongestEXP, a decentralized algorithm that applies the classic exponential
weights method. By maintaining weights on the facility level, the regret bound
of CongestEXP avoids the exponential dependence on the size of possible
facility sets, i.e., $\binom{F}{k}\approx F^{k}$, and scales only linearly
with $F$. Specifically, we show that CongestEXP attains a regret upper bound
of $O(kF\sqrt{T})$ for every individual player, where $T$ is the time horizon.
On the other hand, exploiting the exponential growth of weights enables
CongestEXP to achieve a fast convergence rate. If a strict Nash equilibrium
exists, we show that CongestEXP can converge to the strict Nash policy almost
exponentially fast in $O(F\exp(-t^{1-\alpha}))$, where $t$ is the number of
iterations and $\alpha\in(1/2,1)$.

##  1 Introduction

Congestion games are a class of general-sum games that can be used to describe
the behavior of agents who share a common set of facilities (resources)
(Brown, 1949). In these games, each player chooses a combination of
facilities, and popular facilities will become congested, yielding a lower
utility for the players who choose them. Thus, players are incentivized to
avoid congestion by choosing combinations that are less popular among the
other players. A range of real-world scenarios can be captured by the
congestion game model, such as traffic flow, data routing, and wireless
communication networks (Tekin et al., 2012; Cheung et al., 2014; Zhang and
Wang, 2020).

In the model of the congestion game, the Nash equilibrium is a popular concept
to describe the behavior of selfish players and the dynamics induced by
decentralized algorithms. It describes a stable state of the game where no
player can improve their utility by unilaterally changing their choice of
actions. When a unique Nash equilibrium exists in the congestion game, it can
be a reference point for players to coordinate to avoid suboptimal outcomes.
Beyond the Nash equilibrium, social welfare is a significant metric, capturing
the overall utility or well-being of all players involved. It serves as a
crucial benchmark, enabling the evaluation of the efficiency loss incurred
when transitioning from centralized to decentralized algorithms.

In the classic one-shot congestion game setting, the Nash equilibrium and the
loss of efficiency due to decentralized dynamics have been well studied
(Roughgarden and Tardos, 2002; Roughgarden, 2007). However, these results do
not provide insights into how players arrive at the equilibrium. This
motivates the study of congestion games in an online learning framework, where
players participate in the game repeatedly at every time step. This framework
better models many realistic scenarios, such as the traffic congestion problem
in urban areas. In this repeated congestion game setting, players such as
drivers in a congested city must choose between different routes to reach
their destinations every day. As more drivers use a particular route, the
congestion on that route increases, leading to higher travel times and lower
utility. In this scenario, players can update their desired route every day to
optimize their utility, but the observed utility by each player may be subject
to randomness due to uncertainty in the actual congestion situation (e.g., the
influence of the weather). All these make it suitable to model the congestion
game in an online learning framework.

While there have been various decentralized algorithms that can attain the
Nash equilibria efficiently for the general online games, they can suffer from
a linear dependency on the number of actions when directly applied to the
congestion game (Daskalakis et al., 2011; Syrgkanis et al., 2015; Chen and
Peng, 2020; Hsieh et al., 2021; Daskalakis et al., 2021; Giannou et al.,
2021), which is exponential with $k,F$. On the other hand, algorithms designed
specifically for congestion games either only converge to Nash equilibria
asymptotically (Kleinberg et al., 2009; Krichene et al., 2015; Palaiopanos et
al., 2017), on average (Cui et al., 2022), or require additional assumptions
on the structure of the game (Chen and Lu, 2015, 2016). Moreover, to the best
of our knowledge, there is no algorithm that can simultaneously guarantee both
low regret and fast convergence to Nash equilibrium for each player. While
some online learning algorithms, such as exponential weights, have been shown
to converge faster than others due to the specific choice of regularization
(Giannou et al., 2021), previous regret results indicate that their guarantees
still rely on the exponentially large number of actions, due to their specific
form of updates (exponential weighting) (Cohen et al., 2016).

In this paper, we study the online congestion game with semi-bandit and full
information feedback. We propose a decentralized algorithm that modifies the
celebrated exponential weights algorithm, which can be utilized by each player
without additional information about other players’ utility. From the
individual player’s perspective, we show that the algorithm guarantees
sublinear individual regret, with respect to the best action in hindsight when
holding the other player’s strategy fixed. We remark that the regret is also
only linear with respect to the number of facilities. As a result of this, we
show that the optimal social welfare can be efficiently approximated, up to an
error that is only linear with respect to the number of facilities. When a
strict Nash equilibrium exists for the congestion game, we also prove that our
algorithm is capable of converging to the strict Nash equilibrium fast, with
an almost exponentially fast rate that is only linear with respect to the
number of facilities.

##  2 Related works

#### Learning in games

Online learning has a long history that is closely tied to the development of
game theory. The earliest literature can be traced back to Brown’s proposal on
using fictitious play to solve two-player zero-sum games (Brown, 1949). It is
now understood that fictitious play can converge very slowly to Nash
equilibrium (Daskalakis and Pan, 2014). On the other side, it has been shown
that if each player of a general-sum, multi-player game experiences regret
that is at most $f(T)$, the empirical distribution of the joint policy
converges to a coarse correlated equilibrium of the game with a rate of
$O(f(T)/T)$ (Cesa-Bianchi and Lugosi, 2006). This implies that a variety of
online learning algorithms such as Hedge and Follow-The-Regularized-Leader
algorithms can converge to coarse correlated equilibria at a rate of
$O(1/\sqrt{T})$.

While the standard no-regret learning dynamic can guarantee convergence to
equilibria, it has been shown that more specialized no-regret learning
protocols can do better (Daskalakis et al., 2011; Syrgkanis et al., 2015; Chen
and Peng, 2020; Hsieh et al., 2021; Daskalakis et al., 2021). It has also been
shown that when strict pure Nash equilibria are present, algorithms that are
based on entropic regularization (e.g. exponential weights) can converge fast
to the equilibria (Cohen et al., 2016; Giannou et al., 2021). Moreover, such
convergence rate holds for a variety of different feedback models, from full
information to bandit feedback.

Though all of the above-mentioned methods are applicable to congestion games,
the results usually involve a linear dependency on the number of actions. As
each action is a combination of the different facilities (resources) in the
congestion games, the results lead to the undesirable exponential dependency
on the number of facilities.

#### Learning in online congestion games

Congestion games were first introduced in the seminal work Rosenthal (1973) as
a class of games with pure-strategy Nash equilibria. It has then been
extensively studied, where its Nash equilibria have been characterized in
Roughgarden and Tardos (2002) and a comprehensive introduction has been given
in Roughgarden (2007).

In the online setting, many works use no-regret learning to develop learning
dynamics in this class of games for efficient convergence. Kleinberg et al.
(2009) are the first to study no-regret learning for congestion games. They
showed that the well-known multiplicative weights learning algorithm results
in convergence to pure equilibria. Furthermore, they identified a set of mixed
Nash equilibria that are weakly stable and showed that the distribution of
play converges to this set. Followup works Krichene et al. (2015) showed that
multiplicative weights algorithms converge to the set of Nash equilibria in
the sense of Cesàro means, and Palaiopanos et al. (2017) investigated the
effect of learning rate on convergence to Nash equilibria.

With an additional assumption of convex potential functions, Chen and Lu
(2015, 2016) established a non-asymptotic convergence rate. However, their
rate has an exponential dependency on the number of facilities. Cui et al.
(2022) gave the first non-asymptotic convergence rate under semi-bandit
feedback and without an exponential dependency on the number of facilities.
However, the convergence is with respect to the averaged-over-time policy and
suffers from a dependency of $F^{9}$, where $F$ is the number of facilities.
This result is later improved by concurrent work Panageas et al. (2023), who
proposed an online stochastic gradient descent algorithm that convergences to
an $\epsilon$-approximate Nash equilibrium in $O(\epsilon^{-5})$ time while
each individual player enjoys a regret of $O(T^{4/5})$.

#### Combinatorial bandits and shortest path

Combinatorial bandits offer an extension of the classic multi-armed bandit
problem where the player must select an action that involves a combination of
various resources (Cesa-Bianchi and Lugosi, 2012; Chen et al., 2013; Lattimore
and Szepesvári, 2020). In a special case, the shortest path problem can be
viewed as a combinatorial bandit problem where the resources are edges on a
graph and the action is a path (György et al., 2007). Efficient algorithms
have been proposed for these problems, and it has been shown that the
sublinear regret only linearly depends on the number of resources. However, it
is important to note these algorithms are designed for a single player, and as
a result, they may not converge to a Nash equilibrium when applied directly to
congestion games by allowing each player to execute the algorithm.

##  3 Problem Formulation

###  3.1 Congestion game

A congestion game with $n$ players is defined by
${\mathcal{G}}=\left({\mathcal{F}},\\{{\mathcal{A}}_{i}\\}_{i=1}^{n},\\{r^{f}\\}_{f\in{\mathcal{F}}}\right)$,
where i) ${\mathcal{F}}$ is the facility set that contains $F$ facilities; ii)
${\mathcal{A}}_{i}$ is the action space for player $i$ and contains $A$
actions (we assume that the action space for each player is the same), where
each action $a_{i}\in{\mathcal{A}}_{i}$ is a combination of $k$ facilities in
${\mathcal{F}}$; and iii)
$r^{f}:({\mathcal{A}}_{1}\times\dots\times{\mathcal{A}}_{n})\rightarrow[0,1]$
is the reward function for facility $f\in{\mathcal{F}}$, which only depends on
the number of players choosing this facility, i.e.,
$\sum^{n}_{i=1}\mathbb{I}\\{f\in a_{i}\\}$.We denote $a=(a_{i},a_{-i})$ as a
joint action, where $a_{-i}$ is the actions of all other players except player
$i$. The total reward collected by player $i$ with joint action
$a=(a_{i},a_{-i})$ is $r_{i}(a_{i},a_{-i})=\sum_{f\in
a_{i}}r^{f}(a_{i},a_{-i})$. Without loss of generality, we assume that
$r^{f}(a)\in[0,1]$.

Deterministically playing actions $a=(a_{i},a_{-i})$ is referred to as a pure
strategy. The player can also play a mixture of pure strategy,
$\omega_{i}\in\Delta({\mathcal{A}}_{i})$, where $\Delta({\mathcal{A}}_{i})$
denotes the probability simplex of action space ${\mathcal{A}}_{i}$.
Similarly, we use $\omega=(\omega_{i},\omega_{-i})$ to denote a joint
randomized policy.

###  3.2 Nash equilibrium

One of the commonly used solution concepts in congestion games is Nash
equilibrium (NE), and the policies that lead to a Nash equilibrium are
referred to as Nash policies. The players are said to be in a Nash equilibrium
when no player has an incentive from deviating from its current policy (as
described in the definition below).

######  Definition 3.1 (Nash equilibrium).

A policy $\omega^{\ast}=(\omega^{\ast}_{1},\ldots,\omega^{\ast}_{n})$ is
called a Nash equilibirum if for all $i\in[n]$,
$r_{i}(\omega_{i}^{\ast},\omega_{-i}^{\ast})\geq
r_{i}(\omega_{i},\omega_{-i}^{\ast})\,,\forall\omega_{i}\in\Delta({\mathcal{A}}_{i})$.
When $\omega^{\ast}$ is pure, the equilibrium is called a pure Nash
equilibrium. In addition, when the strategy is pure and the inequality is a
strict inequality, the equilibrium is called a strict Nash equilibrium.

######  Fact 3.1 ((Rosenthal, 1973)).

There exists a pure Nash equilibrium in any congestion game.

###  3.3 Social welfare and price of anarchy

Except for Nash equilibrium, another commonly used metric to measure the
efficiency of the dynamics between the players is through social welfare. For
a given joint action $a=\\{a_{i}\\}_{i=1}^{n}$, the social welfare is defined
to be the sum of players’ rewards, i.e., $W(a)=\sum^{n}_{i=1}r_{i}(a)$, and
the optimal social welfare of the game is defined as

$\displaystyle\mathrm{OPT}=\max_{a\in\mathcal{A}_{1}\times\dots\times\mathcal{A}_{n}}W(a)\,.$

This optimality is under the case where a central coordinator could dictate
each player’s strategy, and each player’s individual incentives are not
considered.

Based on the definition of $\mathrm{OPT}$, We can define smooth games as
follows.

######  Definition 3.2 (Smooth game (Roughgarden, 2009)).

A game is $(\lambda,\mu)$-smooth if there exists a joint action $a^{\ast}$
such that for any joint action $a$, $\sum_{i\in
n}r_{i}\left(a_{i}^{\ast},a_{-i}\right)\geq\lambda\mathrm{OPT}-\mu W(a)$.

Nisan et al. (2007) show that congestion games are smooth when the reward
function are affine, that is, when $r^{f}(a)$ is an affine function on the
scalar variable $\sum^{n}_{i=1}\mathbb{I}\\{f\in a_{i}\\}$. This property
enables certain decentralized no-regret learning dynamics to efficiently
approximate the optimal welfare (Syrgkanis et al., 2015).

###  3.4 Online congestion game

In this paper, we study the congestion game in an online setting with a finite
time horizon $T$, where the underlying reward function is unknown. At each
time step $t\in[T]$, each player chooses (randomized) policy $\omega_{i}^{t}$,
from which it forms a joint policy
$\omega^{t}=(\omega_{1}^{t},\ldots,\omega_{n}^{t})$. Then each player $i$
draws a random action $a_{i}^{t}\sim\omega_{i}^{t}$, plays this action (denote
$a^{t}$ the joint action), and receives overall reward of $\sum_{f\in
a_{i}^{t}}R^{f}(a^{t})$, where $R^{f}(a^{t})$’s are random variables that
satisfy the following assumption.

######  Assumption 3.1.

For any facility $f\in\mathcal{F}$, any joint action $a^{t}$ and any player
$i\in[n]$, let $\mathcal{H}_{t}$ be the history up to time step $t-1$. Then,
$R^{f}(a)\in[0,1]$, and
$\mathbb{E}\left[R^{f}(a^{t})\mid\mathcal{H}_{t}\right]=r^{f}(a^{t})$.

The assumption implies that the mean of $R^{f}(a^{t})$ is always
$r^{f}(a^{t})$. Hence the Nash equilibrium and expected social welfare of the
online congestion game is the same as those of the offline congestion game.

We consider two types of feedback rules in this paper: semi-bandit feedback,
and full information feedback. In the semi-bandit feedback, player $i$
observes all the $R^{f}(a^{t})$’s for any $f\in a_{i}$ (only the facilities he
played); and in full information feedback, player $i$ observes all possible
information $R^{f}(a_{i},a_{-i})$, for every $a\in\mathcal{A}_{i}$, $\forall
f\in a$.

The efficiency of a sequence of policy $\\{\omega_{i}^{t}\\}_{t=1}^{T}$ can be
measured by the individual regret of all the players (which is defined as
follows).

######  Definition 3.3 (Individual regret).

The individual regret of player $i$ playing policy
$\\{\omega_{i}^{t}\\}_{t=1}^{T}$ is defined as the cumulative difference
between the received rewards and the rewards incurred by a best-in-hindsight
policy, that is

$\displaystyle\mathrm{Regret}_{i}(T)=\max_{\omega_{i}\in{\mathcal{A}}_{i},\\{\omega_{-i}^{t}\\}^{T}_{t=1}}\sum^{T}_{t=1}r_{i}(\omega_{i},\omega_{-i}^{t})-r_{i}(\omega_{i}^{t},\omega_{-i}^{t})\,.$

##  4 Algorithm

Algorithm 1 CongestEXP

1:Input: learning rate $\eta$.

2:For all $f\in\mathcal{F}$, initialize $\tilde{y}_{i}^{0}(f)=0$,
$\omega_{i}^{0}(a)$ initialized according to Equation (2).

3:for $t=1,\ldots,T$ do

4: Players play strategy $a^{t}\sim\omega^{t}$,
$\omega^{t}=(\omega_{1}^{t},\ldots,\omega_{n}^{t})$.

5: Each player $i$ observe $R^{f}(a^{t})\sim r^{f}(a^{t})$, for each $f\in
a_{i}^{t}$.

6: Each player $i\in[N]$ computes $\tilde{y}_{i}^{t}(f)$ according to Equation
(1).

7: Each player $i\in[N]$ updates $\omega_{i}^{t+1}(a)$ according to Equation
(2).

8:end for

In this section, we introduce CongestEXP, a decentralized algorithm for online
congestion games (Algorithm 1).

The algorithm uses the combinatorial nature of the action space. Each player
maintains a sampling distribution $\omega_{i}^{t}$ and a facility-level reward
estimator $\tilde{y}_{i}^{t}$. At each time step, they first draw a random
action $a_{i}^{t}\sim\omega_{i}^{t}$ and play this action. Then they use their
received information to update $\tilde{y}_{i}^{t}(f)$’s (for all
$f\in{\mathcal{F}}$) as follows

$\displaystyle\tilde{y}_{i}^{t}(f)=1-\frac{\mathbb{I}\\{f\in
a_{i}^{t}\\}(1-R^{f}(a^{t}))}{q_{i}^{t}(f)}\,,\quad
q_{i}^{t}(f)=\sum_{a_{i}\in{\mathcal{A}}_{i},f\in
a_{i}}\omega_{i}^{t}(a_{i})\,,$ (1)

where $q_{i}^{t}(f)$ is the probability that player $i$ selects facility $f$
at time $t$ based on its current policy $\omega_{i}^{t}$. One can easily check
that if $f\in a_{i}^{t}$, $\tilde{y}_{i}^{t}(f)$ is an unbiased estimator for
$r^{f}(a^{t})$, and with these facility-level reward estimators, the players
then update $\omega_{i}^{t+1}$ as follows (exponential weighting), and then
proceed to the next time step.

$\displaystyle\omega_{i}^{t+1}(a)=\frac{\prod_{f\in
a}\tilde{\omega}_{i}^{t}(f)}{\sum_{a_{i}\in{\mathcal{A}}_{i}}\prod_{f^{\prime}\in
a_{i}}\tilde{\omega}_{i}^{t}(f^{\prime})}\,,\forall
a\in{\mathcal{A}}_{i}\,,\quad\text{where}\ \
\tilde{\omega}_{i}^{t}(f)=\exp\left(\eta\sum^{t}_{j=1}\tilde{y}_{i}^{j}(f)\right)\,.$
(2)

On the one hand, in the semi-bandit setting, our algorithm leverages this kind
of feedback and estimates rewards at the facility level. We note that this
idea has also been previously utilized to tackle online shortest path problems
and combinatorial bandit problems, as documented in literature (György et al.,
2007; Cesa-Bianchi and Lugosi, 2012; Chen et al., 2013; Combes et al., 2015).
This enables us to achieve a low individual regret (Theorem 5.1) and guarantee
a lower bound for the overall social welfare (Corollary 5.1). On the other
hand, our algorithm constructs exponential weights based on the reward
estimation at the action level. This makes sure that the joint policy
$\omega^{t}$ can converge to a Nash equilibrium fast when it is nearby
(Theorem 5.2 and 5.3).

In summary, our results indicate that adopting Algorithm 1 in a congestion
game leads to favorable outcomes. Each player enjoys favorable cumulative
individual rewards, without compromising the overall social welfare. Moreover,
when the joint policy is close to the Nash equilibrium, players can quickly
converge to a stable equilibrium state, avoiding inefficient and chaotic
dynamics.

##  5 Theoretical Results

In this section, we present our main theoretical results.

###  5.1 Sublinear individual regret with linear dependency on $F$

Our first theorem shows that each individual player enjoys a sublinear
individual regret.

######  Theorem 5.1.

Under semi-bandit feedback, Algorithm 1 with $\eta=\frac{1}{\sqrt{T}}$
satisfies that for all $i\in[n]$,

$\text{Regret}_{i}(T)=O\left(kF\sqrt{T}\right).$

Compared with naively applying exponential weights on the congestion game
(with a regret of $\tilde{O}\left(\sqrt{A_{i}T}\right)$ (Auer et al., 2002)),
we can see that Theorem 5.1 reduces the factor $\sqrt{A_{i}}$ to $kF$. This is
a significant improvement since $A\approx F^{k}$ is exponentially larger than
$kF$.

Though there exist some works to achieve a similar regret upper bound
(Daskalakis et al., 2021), we emphasize that these algorithms only work in the
full-information setting, but not the semi-bandit setting. Besides, our
algorithm can converge to a strict Nash equilibrium fast, while existing ones
can only guarantee to converge to a coarse correlated equilibrium (please see
details in Section 5.2).

#### Tight approximation to optimal welfare

One immediate consequence of Theorem 5.1 is that our proposed algorithm can
achieve a tight approximation to the optimal social welfare.

######  Corollary 5.1.

Under semi-bandit feedback, if the congestion game is $(\lambda,\mu)$-smooth,
then Algorithm 1 with $\eta=\frac{1}{\sqrt{T}}$ satisfies

$\displaystyle\frac{1}{T}\sum^{T}_{t=1}W(\omega^{t})\geq\frac{\lambda}{1+\mu}\mathrm{OPT}-O\left(\frac{nkF}{\sqrt{T}(1+\mu)}\right)\,.$

We remark that $\frac{\lambda}{1+\mu}\mathrm{OPT}$ is shown to be a tight
approximation of optimal social welfare possible by offline algorithms that
attain Nash equilibrium in congestion games (Roughgarden, 2009). Therefore,
the above result shows that our algorithm is as efficient as any offline Nash
policy asymptotically.

#### Technical highlight of Theorem 5.1

In classical proofs of exponential weights algorithms, the regret is closely
linked to the quadratic term of the reward estimator, i.e.,
$\mathbb{E}_{t}[\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\left(\tilde{y}_{i}^{t}(a_{i})\right)^{2}]$(Auer
et al., 2002; Lattimore and Szepesvári, 2020), where
$\tilde{y}_{i}^{t}(a_{i})$ is the estimated reward of action $a_{i}$ at time
step $t$, and $\mathbb{E}_{t}[\cdot]$ denotes the conditional expectation over
all history up to time $t$. If we can upper bound this term by a constant
polynomial with $k$ and $F$, then we can remove the exponential factor in the
individual regret upper bound.

With our facility level estimator (Eq. (1)),
$\tilde{y}_{i}^{t}(a_{i})=\sum_{f\in a_{i}}\tilde{y}_{i}^{t}(f)$, the above
term could be upper bounded as:

$\displaystyle\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\bigg{(}\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)\bigg{)}^{2}$ $\displaystyle\leq\ $ $\displaystyle
k\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\sum_{f\in
a_{i}}\bigg{(}1-\frac{\mathbb{I}\\{f\in
a_{i}^{t}\\}(1-R^{f}(a^{t}_{i},a^{t}_{-i}))}{q_{i}^{t}(f)}\bigg{)}^{2}$ (3)
$\displaystyle=\ $ $\displaystyle
k+k\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\sum_{f\in
a_{i}}\left(\bigg{(}\frac{\mathbb{I}\left\\{f\in
a_{i}^{t}\right\\}(1-R^{f}(a^{t}_{i},a^{t}_{-i}))}{q_{i}^{t}(f)}\bigg{)}^{2}-\frac{2\mathbb{I}\left\\{f\in
a_{i}^{t}\right\\}(1-R^{f}(a^{t}_{i},a^{t}_{-i}))}{q_{i}^{t}(f)}\right)$ (4)
$\displaystyle\leq\ $ $\displaystyle
k+k\sum_{f\in\mathcal{F}}\bigg{(}\frac{\mathbb{I}\left\\{f\in
a_{i}^{t}\right\\}(1-R^{f}(a^{t}_{i},a^{t}_{-i}))}{q_{i}^{t}(f)}\bigg{)}^{2}\sum_{a_{i}\in\mathcal{A},f\in
a_{i}}\omega_{i}^{t}(a_{i})$ $\displaystyle\leq\ $ $\displaystyle
k+k\sum_{f\in\mathcal{F}}\bigg{(}\frac{\mathbb{I}\left\\{f\in
a_{i}^{t}\right\\}(1-R^{f}(a^{t}_{i},a^{t}_{-i}))}{q_{i}^{t}(f)}\bigg{)}^{2}q_{i}^{t}(f)\,,$
(5)

where Eq. (3) is by the Cauchy-Shwarz inequality, Eq. (4) is by noting
$\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})=1$, and Eq. (5) is by the
definition of $q_{i}^{t}(f)$. Notice that $(1-R_{i}^{f}(a^{t}))^{2}$ is upper
bounded by $1$ and taking a conditional expectation over all history up to
time $t$ yields (denote $\mathbb{E}_{t}$ as the conditional expectation
operator, and the $q_{i}^{t}(f)$ cancels out the $\mathbb{I}\\{f\in
a_{i}^{t}\\}^{2}$).

$\displaystyle\mathbb{E}_{t}\Bigg{[}\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\bigg{(}\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)\bigg{)}^{2}\Bigg{]}\leq\ k+kF\,,$ (6)

and this is an upper bound polynomial with $k$ and $F$.

From the above explanation, one can see the necessity of estimating the
rewards at the facility level. If the reward estimator is constructed at the
action level, that is, an estimator of the form

$\tilde{y}_{i}^{t}(a_{i})=k-\frac{\mathbb{I}\left\\{a_{i}=a_{i}^{t}\right\\}\left(k-\sum_{f\in
a_{i}^{t}}R_{i}^{f}\left(a_{i}^{t},a_{-i}^{t}\right)\right)}{\omega_{i}^{t}(a_{i})},$

Consider the case that $R_{i}^{f}\left(a_{i}^{t},a_{-i}^{t}\right)$ is always
0 and at the beginning $\omega_{i}^{t}(a_{i})=1/|\mathcal{A}_{i}|$, then this
quadratic term
$\mathbb{E}_{t}[\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\left(\tilde{y}_{i}^{t}(a)\right)^{2}]$
is approximately

$\displaystyle\mathbb{E}_{t}\Bigg{[}\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\left(\tilde{y}_{i}^{t}(a)\right)^{2}\Bigg{]}\approx\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\cdot\left(\omega_{i}^{t}(a_{i})\left({k\over\omega_{i}^{t}(a_{i})}\right)^{2}\right)=k^{2}|\mathcal{A}_{i}|\,,$

which scales with the number of actions and is thus always exponentially
large.

###  5.2 Fast convergence to strict Nash equilibrium

Beyond the low individual regret, we also show that our algorithm can produce
a set of policies $\\{\omega_{i}^{t}\\}^{T}_{t=1}$ that converges fast to a
strict Nash equilibrium $\omega_{i}^{\ast}$ in the full-information setting.

We first consider a simple case, where each player observes the expected
rewards directly (which also take expectation on the randomness of
$a_{-i}^{t}\sim\omega_{-i}^{t}$, i.e.
$\mathbb{E}_{a^{t}_{-i}\sim\omega_{-i}^{t}}[r^{f}(a_{i},a^{t}_{-i})]$ for any
$a_{i}$). In addition, we assume that any $k$ facilities form an action.

######  Theorem 5.2.

Consider the case where each player receives
$\mathbb{E}_{a^{t}_{-i}\sim\omega_{-i}^{t}}[r^{f}(a^{t}_{i},a^{t}_{-i})],\forall
a_{i}\in\mathcal{A}_{i},\forall f\in a_{i}$ in a game that permits a strict
Nash equilibrium $\omega^{\ast}=(\omega_{1}^{\ast},\cdots,\omega_{n}^{\ast})$,
and let
$\tilde{y}_{i}^{t}(f)=\mathbb{E}_{a^{t}_{-i}\sim\omega_{-i}^{t}}[r^{f}(a^{t}_{i},a^{t}_{-i})]$
in Line 6 of Algorithm 1. Suppose $\tilde{y}_{i}^{0}(f),\forall i\in[n]$ is
initialized such that $\omega^{0}\in U_{M}\subseteq U_{\epsilon}$, then for
any $i\in[n]$ and any $t$, we have

$\left\|\omega_{i}^{t}-\omega_{i}^{\ast}\right\|_{1}\leq
2(kF\exp(-M-\eta\epsilon t))\,,$

where $M\geq\left|\log\left(\frac{\epsilon}{2kF}\right)\right|$, and
$\epsilon$ is a constant that is game-dependent only.

######  Remark 5.1.

We note that the convergence rate of the algorithm can be improved by
increasing the step size $\eta$. This is because when each player receives
expected rewards, the player can take greedy steps toward the equilibrium
strategy. This agrees with greedy strategies that are previously employed to
reach strict Nash equilibrium (Cohen et al., 2016). However, such greedy
policies would not work in the presence of reward uncertainty, as we will
discuss in Theorem 5.3.

It is worth mentioning that the convergence rate of our algorithm does not
rely on the number of actions $A_{i}$, but rather solely on the number of
facilities $F$. This is an improvement over the previous findings for
exponential weights algorithms with non-combinatorial action spaces in the
context of a congestion game, where the rate is linearly dependent on the
number of actions (Cohen et al., 2016). The reason for this is the utilization
of our facility-level reward estimation technique once again.

Previous studies on the convergence rate of congestion games (Chen and Lu,
2015, 2016) have established a linear rate of convergence when the game
possesses a smooth potential function and the algorithm is given an
appropriate initial starting point. The potential function provides a means to
capture the incentives of all players to modify their actions and can be used
to characterize the dynamics in policy updates. Assuming the smoothness of the
potential function implies optimization on a simpler policy optimization
landscape. In contrast, our algorithm achieves a much faster rate of
convergence, and this convergence rate still holds even in the absence of a
smooth potential function. We adopt a different approach where we directly
argue through the algorithm update rule that the updated policy will always
fall within a neighborhood around the Nash equilibrium. This bypasses the need
for a smoothness potential function and demonstrates the effectiveness of our
approach.

In addition, we remark that though some variants of Mirror Descent (MD) or
Follow-the-Regularized-Leader (FTRL) algorithms are also proven to enjoy
sublinear regret with logarithmic dependency on action space in the full
information setting (Daskalakis et al., 2021), these results only imply
convergence to an approximate coarse correlated equilibrium and do not enjoy
convergence to Nash equilibrium. In comparison, Nash equilibrium is much more
stable, as the dynamic will remain there unless external factors change, while
coarse correlated equilibrium may be more sensitive to small changes in the
correlation method, which can lead to deviation from the equilibrium (Nisan et
al., 2007).

To prove Theorem 5.2, we first identify that there exists a neighborhood
around the strict Nash equilibrium, such that for any player $i$, his action
in the strict Nash equilibrium is the only optimal choice.

######  Lemma 5.1.

If there exists a strict Nash equilibrium
$a^{\ast}=(a_{1}^{\ast},\ldots,a_{n}^{\ast})$, then there exists $\epsilon>0$
and a neighborhood $U_{\epsilon}$ of $a^{\ast}$, such that for all
$\tilde{\omega}=(\tilde{\omega}_{i},\tilde{\omega}_{-i})\in U_{\epsilon}$,

$r_{i}(a_{i}^{\ast},\tilde{\omega}_{-i})-r_{i}(a_{i},\tilde{\omega}_{-i})\geq\epsilon\,,\quad\forall
i\in[n]\,,a_{i}\in{\mathcal{A}}_{i}\,,a_{i}\neq a_{i}^{\ast}\,,$

where $r_{i}(a_{i},\omega_{-i})$ is defined as
$\mathbb{E}_{a_{-i}\sim\omega_{-i}}[r_{i}(a_{i},a_{-i})]$.

###### Proof.

By the existence of the strict Nash equilibrium, there exists $\epsilon>0$
such that $\forall a_{i}\in{\mathcal{A}}_{i}$,
$r_{i}\left(a_{i},a_{-i}^{\ast}\right)\leq
r_{i}(a_{i}^{\ast},a_{-i}^{\ast})-2\epsilon$. Then by continuity, we know that
for $(\tilde{\omega}_{i},\tilde{\omega}_{-i})\in U_{\epsilon}$,
$r_{i}(a_{i},\tilde{\omega}_{-i})\leq
r_{i}(a_{i}^{\ast},\tilde{\omega}_{-i})-\epsilon$. ∎

Moreover, if the difference in reward estimator
$\tilde{z}_{i}^{t}(a_{i})=\sum^{t}_{j=0}\left(\sum_{f\in
a_{i}}\tilde{y}_{i}^{j}(f)-\sum_{f^{\prime}\in
a^{\ast}_{i}}\tilde{y}_{i}^{j}(f^{\prime})\right)$ is upper bounded by some
small enough constant, then the induced policy of Algorithm 1 falls into the
neighborhood set $U_{\epsilon}$.

######  Lemma 5.2.

Let $\tilde{z}_{i}^{t}(a_{i})=\sum^{t}_{j=0}\left(\sum_{f\in
a_{i}}\tilde{y}_{i}^{j}(f)-\sum_{f^{\prime}\in
a^{\ast}_{i}}\tilde{y}_{i}^{j}(f^{\prime})\right)$, and define

$U_{M}=\left\\{\omega^{t}\textup{ computed by Algorithm
\ref{alg}}\mid\tilde{z}_{i}^{t}(a_{i})\leq-M\,,\forall a_{i}\neq
a_{i}^{\ast},\forall i\in[n]\right\\}\,.$

For sufficiently large $M$, $U_{M}\subseteq U_{\epsilon}$. Moreover, following
the updates of Algorithm 1, if $\omega^{t}\in U_{M}$, then $\omega^{t+1}\in
U_{M}$.

Thus, if $\omega^{0}$ is in the neighborhood $U_{M}\subseteq U_{\epsilon}$,
then the reward estimator $\tilde{z}_{i}^{t}(a_{i})$ can only decrease (by
Lemma 5.1), and hence the algorithm will give an updated policy $\omega^{t}$
that is also within the neighborhood set $U_{\epsilon}$.

Also, note that $\omega_{i}^{\ast}$ is a strict Nash equilibrium, which
implies that
$\left|\omega_{i}^{t}-\omega_{i}^{\ast}\right|_{1}=2(1-\omega_{i}^{t}(a_{i}^{\ast}))$.
Hence, to establish the convergence rate, we need to lower bound

$\displaystyle\omega_{i}^{t}(a_{i}^{\ast})=\ $ $\displaystyle\frac{\prod_{f\in
a_{i}^{\ast}}\tilde{\omega}_{i}^{t}(f)}{\sum_{a^{\prime}\in\mathcal{A}}\prod_{f^{\prime}\in
a^{\prime}}\tilde{\omega}_{i}^{t}(f^{\prime})}=\frac{\prod_{f\in
a_{i}^{\ast}}\exp\left(\eta\sum^{t}_{j=0}\tilde{y}_{i}^{j}(f)\right)}{\sum_{a^{\prime}\in\mathcal{A}}\prod_{f^{\prime}\in
a^{\prime}}\exp\left(\eta\sum^{t}_{j=0}\tilde{y}_{i}^{j}(f^{\prime})\right)}\,.$

#### Technical challenge

We remark that if we directly apply Lemma 5.2, we can get

$\displaystyle\omega_{i}^{t}(a_{i}^{\ast})=\ $ $\displaystyle\frac{\prod_{f\in
a_{i}^{\ast}}\tilde{\omega}_{i}^{t}(f)}{\sum_{a^{\prime}\in\mathcal{A}}\prod_{f^{\prime}\in
a^{\prime}}\tilde{\omega}_{i}^{t}(f^{\prime})}\geq\
\frac{1}{1+\sum_{a_{i}\in\mathcal{A}_{i},a_{i}\neq
a_{i}^{\ast}}\left(\prod_{f\in
a_{i}}\tilde{\omega}_{i}^{t}(f)-\prod_{f^{\prime}\in
a_{i}^{\ast}}\tilde{\omega}_{i}^{t}(f^{\prime})\right)}$ $\displaystyle\geq\ $
$\displaystyle 1-\sum_{a_{i}\in\mathcal{A}_{i},a_{i}\neq
a_{i}^{\ast}}\bigg{(}\prod_{f\in
a_{i}}\tilde{\omega}_{i}^{t}(f)-\prod_{f^{\prime}\in
a_{i}^{\ast}}\tilde{\omega}_{i}^{t}(f^{\prime})\bigg{)}\,.$

Suppose one can upper bound $\sum_{a_{i}\in\mathcal{A}_{i},a_{i}\neq
a_{i}^{\ast}}\bigg{(}\prod_{f\in
a_{i}}\tilde{\omega}_{i}^{t}(f)-\prod_{f^{\prime}\in
a_{i}^{\ast}}\tilde{\omega}_{i}^{t}(f^{\prime})\bigg{)}\leq\exp(-t)$, then
this gives $1-\sum_{a_{i}\in\mathcal{A}_{i},a_{i}\neq a_{i}^{\ast}}\exp(-t)$,
which yields a convergence rate of $(|\mathcal{A}_{i}|-1)\exp(-t)$ as
$\left\|\omega_{i}^{t}-\omega_{i}^{\ast}\right\|_{1}=2(1-\omega_{i}^{t}(a_{i}^{\ast}))$.
This approach implies that the convergence rate scales linearly with the
number of actions (thus exponentially with the number of facilities), and is
what we wanted to avoid in the analysis.

To overcome this exponential dependency, we utilize the fact that any
$k$-facility combination is an action, which means that we can order the
facility from $f_{1},\ldots,f_{F}$ in decreasing order of
$\tilde{\omega}_{i}^{t}(f)$ and $f_{1},\ldots,f_{k}$ form the optimal pure
Nash action $a_{i}^{\ast}$.

###### Proof of Theorem 5.2.

Using the above-mentioned observation, we have,

$\displaystyle\frac{\prod_{f\in
a_{i}^{\ast}}\exp\left(\eta\sum^{t}_{j=0}\tilde{y}_{i}^{j}(f)\right)}{\sum_{a^{\prime}\in\mathcal{A}}\prod_{f^{\prime}\in
a^{\prime}}\exp\left(\eta\sum^{t}_{j=0}\tilde{y}_{i}^{t}(f^{\prime})\right)}\geq\
$
$\displaystyle\prod_{m\in[k]}\frac{\exp\left(\eta\sum^{t}_{j=0}\tilde{y}_{i}^{j}(f_{m})\right)}{\exp\left(\eta\sum^{t}_{j=0}\tilde{y}_{i}^{j}(f_{m})\right)+\sum_{\ell>k}\exp\left(\eta\sum^{t}_{j=0}\tilde{y}_{i}^{j}(f_{\ell})\right)}$
$\displaystyle=\ $
$\displaystyle\prod_{m\in[k]}\frac{1}{1+\sum_{\ell>k}\exp\left(\eta\sum^{t}_{j=0}\left(\tilde{y}_{i}^{j}(f_{\ell})-\tilde{y}_{i}^{j}(f_{m})\right)\right)}$
$\displaystyle\geq\ $
$\displaystyle\prod_{m\in[k]}\Bigg{(}1-\sum_{\ell>k}\exp\Bigg{(}\eta\sum^{t}_{j=0}\left(\tilde{y}_{i}^{j}(f_{\ell})-\tilde{y}_{i}^{j}(f_{m})\right)\Bigg{)}\Bigg{)}\,,$
(7)

where the first inequality is by noting that any $\prod_{f^{\prime}\in
a^{\prime}}\exp\left(\eta\sum^{t}_{j=0}\tilde{y}_{i}^{t}(f^{\prime})\right)$
on the denominator of the left-hand side can be found on the product of the
denominators of the right-hand side.

Consider an action $a_{i}$ formed from $a_{i}^{\ast}$ by replacing $f_{m}$
($m\leq k$) with $f_{\ell}$ ($\ell\geq k+1$), then

$\displaystyle\tilde{z}_{i}^{t}(a_{i})=\sum^{t}_{j=0}\left(\sum_{f\in
a_{i}}\tilde{y}_{i}^{j}(f)-\sum_{f^{\prime}\in
a^{\ast}_{i}}\tilde{y}_{i}^{j}\left(f^{\prime}\right)\right)=\sum^{t}_{j=0}\left(\tilde{y}_{i}^{j}(f_{\ell})-\tilde{y}_{i}^{j}(f_{m})\right)\,,$
(8)

and

$\tilde{z}_{i}^{t}(a_{i})=\tilde{z}_{i}^{t-1}(a_{i})+\eta\bigg{(}\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)-\sum_{f^{\prime}\in
a^{\ast}_{i}}\tilde{y}_{i}^{t}\left(f^{\prime}\right)\bigg{)}\leq-M-\eta\epsilon
t\,,$ (9)

where the inequality is by the condition of starting with $\omega^{0}\in
U_{M}$ such that $M$ is large enough for $U_{M}\subseteq U_{\epsilon}$ and
Lemma 5.2.

Combining Equations (7), (8) and (9), we have
$\omega_{i}^{t}(a_{i}^{\ast})\geq 1-kF\exp(-M-\eta\epsilon t)$. Therefore, we
obtain the result in Theorem 5.2, i.e.,
$\left\|\omega_{i}^{t}-\omega_{i}^{\ast}\right\|_{1}=2(1-\omega_{i}^{t}(a_{i}^{\ast}))\leq
2(kF\exp(-M-\eta\epsilon t))$. ∎

Then we consider the case that each player observes only
$R^{f}(a^{t}_{i},a^{t}_{-i})$, instead of the expected rewards.

######  Theorem 5.3.

Consider the case where each player receives a stochastic reward under the
full information setting. Assume the game permits a strict Nash equilibrium
$\omega^{\ast}=(\omega_{1}^{\ast},\cdots,\omega_{n}^{\ast})$. Let
$\tilde{y}_{i}^{t}(f)=R^{f}(a^{t}_{i},a^{t}_{-i})$ in Line 6 of Algorithm 1,
and set the learning rate to be time-dependent such that
$\sum^{\infty}_{t=0}\eta_{t}^{2}\leq\frac{\delta\cdot
M^{2}}{8kn(F-1)}\leq\sum^{\infty}_{t=0}\eta_{t}=\infty$. Suppose
$\tilde{y}_{i}^{0}(f),\forall i\in[n]$ is initalized such that $\omega^{0}\in
U_{2M}\subseteq U_{\epsilon}$, then for any $i\in[n]$ and any $t$, we have

$\|\omega_{i}^{t}-\omega_{i}^{\ast}\|_{1}\leq
2kF\exp\left(-M-\epsilon\sum^{t}_{j=0}\eta_{j}\right)\,,$

with probability at least $1-\delta$, where
$M\geq\left|\log\left(\frac{\epsilon}{2kF}\right)\right|$, and $\epsilon$ is a
constant that is game-dependent only.

We remark that in the case of stochastic rewards, the convergence rate of our
algorithm cannot be arbitrarily large, as the learning rate $\eta$ cannot be
taken to be arbitrarily large. If we take $\eta_{t}=\beta t^{-\alpha}$, with
$\beta$ being a small positive constant and $\alpha\in(1/2,1)$. Then our
convergence rate is $\|\omega_{i}^{t}-\omega_{i}^{\ast}\|_{1}\leq
O\left(\exp\left(-\frac{\beta}{1-\alpha}t^{1-\alpha}\right)\right)$, which is
close to exponentially fast convergence. When the reward function is smooth,
we remark that this can imply each player only experience constant regret.

##  6 Conclusion

This paper studied the congestion game under semi-bandit feedback and
presented a modified version of the well-known exponential weights algorithm.
The algorithm ensures sublinear regret for every player, with the regret being
linearly dependent on the number of facilities. Additionally, the proposed
algorithm can learn a policy that rapidly converges to the pure Nash policy,
with the convergence rate also being linearly dependent on the number of
facilities. To our best knowledge, these are the first results on congestion
games for sublinear individual regret and geometric Nash convergence rate,
without an exponential dependency on the number of facilities.

There are several possible directions to further study the online congestion
game. First, as our work only considers the semi-bandit feedback model for
individual regret, the regret and convergence rate under the full-bandit
feedback model remains unclear. For the Nash convergence result, our algorithm
only enjoys theoretical guarantee in the full-information setting. It remains
as future work to extend this result to semi-bandits and full-bandits feedback
model. Moreover, it also remains in question whether the results of this work
can be extended to the online Markov congestion game proposed by Cui et al.
(2022).

## References

  * Auer et al. (2002) P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire.  The nonstochastic multiarmed bandit problem.  _SIAM journal on computing_ , 32(1):48–77, 2002\.
  * Brown (1949) G. W. Brown.  Some notes on computation of games solutions.  Technical report, RAND CORP SANTA MONICA CA, 1949.
  * Cesa-Bianchi and Lugosi (2006) N. Cesa-Bianchi and G. Lugosi.  _Prediction, learning, and games_.  Cambridge university press, 2006.
  * Cesa-Bianchi and Lugosi (2012) N. Cesa-Bianchi and G. Lugosi.  Combinatorial bandits.  _Journal of Computer and System Sciences_ , 78(5):1404–1422, 2012.
  * Chen and Lu (2015) P.-A. Chen and C.-J. Lu.  Playing congestion games with bandit feedbacks.  In _Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems_ , 2015.
  * Chen and Lu (2016) P.-A. Chen and C.-J. Lu.  Generalized mirror descents in congestion games.  _Artificial Intelligence_ , 241:217–243, 2016.
  * Chen et al. (2013) W. Chen, Y. Wang, and Y. Yuan.  Combinatorial multi-armed bandit: General framework and applications.  In _International conference on machine learning_ , 2013.
  * Chen and Peng (2020) X. Chen and B. Peng.  Hedging in games: Faster convergence of external and swap regrets.  _Advances in Neural Information Processing Systems_ , 2020.
  * Cheung et al. (2014) M. H. Cheung, R. Southwell, and J. Huang.  Congestion-aware network selection and data offloading.  In _2014 48th Annual Conference on Information Sciences and Systems (CISS)_ , pages 1–6. IEEE, 2014.
  * Cohen et al. (2016) J. Cohen, A. Héliou, and P. Mertikopoulos.  Exponentially fast convergence to (strict) equilibrium via hedging.  _arXiv preprint arXiv:1607.08863_ , 2016.
  * Combes et al. (2015) R. Combes, M. S. Talebi Mazraeh Shahi, A. Proutiere, et al.  Combinatorial bandits revisited.  _Advances in neural information processing systems_ , 2015.
  * Cui et al. (2022) Q. Cui, Z. Xiong, M. Fazel, and S. S. Du.  Learning in congestion games with bandit feedback.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Daskalakis and Pan (2014) C. Daskalakis and Q. Pan.  A counter-example to karlin’s strong conjecture for fictitious play.  In _IEEE 55th Annual Symposium on Foundations of Computer Science_ , 2014.
  * Daskalakis et al. (2011) C. Daskalakis, A. Deckelbaum, and A. Kim.  Near-optimal no-regret algorithms for zero-sum games.  In _Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms_ , 2011.
  * Daskalakis et al. (2021) C. Daskalakis, M. Fishelson, and N. Golowich.  Near-optimal no-regret learning in general games.  _Advances in Neural Information Processing Systems_ , 2021.
  * Giannou et al. (2021) A. Giannou, E.-V. Vlatakis-Gkaragkounis, and P. Mertikopoulos.  On the rate of convergence of regularized learning in games: From bandits and uncertainty to optimism and beyond.  _Advances in Neural Information Processing Systems_ , 2021.
  * György et al. (2007) A. György, T. Linder, G. Lugosi, and G. Ottucsák.  The on-line shortest path problem under partial monitoring.  _Journal of Machine Learning Research_ , 8(10), 2007.
  * Hsieh et al. (2021) Y.-G. Hsieh, K. Antonakopoulos, and P. Mertikopoulos.  Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium.  In _Conference on Learning Theory_ , 2021.
  * Kleinberg et al. (2009) R. Kleinberg, G. Piliouras, and É. Tardos.  Multiplicative updates outperform generic no-regret learning in congestion games.  In _Proceedings of the forty-first annual ACM symposium on Theory of computing_ , 2009.
  * Krichene et al. (2015) W. Krichene, B. Drighès, and A. M. Bayen.  Online learning of nash equilibria in congestion games.  _SIAM Journal on Control and Optimization_ , 53(2):1056–1081, 2015.
  * Lattimore and Szepesvári (2020) T. Lattimore and C. Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Nisan et al. (2007) N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani.  _Algorithmic game theory_.  Cambridge university press, 2007.
  * Palaiopanos et al. (2017) G. Palaiopanos, I. Panageas, and G. Piliouras.  Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Panageas et al. (2023) I. Panageas, S. Skoulakis, L. Viano, X. Wang, and V. Cevher.  Semi bandit dynamicsin congestion games: Convergence to nash equilibrium and no-regret guarantees.  _International Conference on Machine Learning_ , 2023.
  * Rosenthal (1973) R. W. Rosenthal.  A class of games possessing pure-strategy nash equilibria.  _International Journal of Game Theory_ , 2:65–67, 1973\.
  * Roughgarden (2007) T. Roughgarden.  Routing games.  _Algorithmic game theory_ , 18:459–484, 2007.
  * Roughgarden (2009) T. Roughgarden.  Intrinsic robustness of the price of anarchy.  In _Proceedings of the forty-first annual ACM symposium on Theory of computing_ , pages 513–522, 2009.
  * Roughgarden and Tardos (2002) T. Roughgarden and É. Tardos.  How bad is selfish routing?  _Journal of the ACM (JACM)_ , 49(2):236–259, 2002\.
  * Syrgkanis et al. (2015) V. Syrgkanis, A. Agarwal, H. Luo, and R. E. Schapire.  Fast convergence of regularized learning in games.  _Advances in Neural Information Processing Systems_ , 28, 2015.
  * Tekin et al. (2012) C. Tekin, M. Liu, R. Southwell, J. Huang, and S. H. A. Ahmad.  Atomic congestion games on graphs and their applications in networking.  _IEEE/ACM Transactions on Networking_ , 20(5):1541–1552, 2012.
  * Zhang and Wang (2020) F. Zhang and M. M. Wang.  Stochastic congestion game for load balancing in mobile-edge computing.  _IEEE Internet of Things Journal_ , 8(2):778–790, 2020.

## Appendix

##  A Proof of Theorem 5.1

See 5.1

###### Proof.

Let $Q_{i}^{t}=\sum_{a_{i}\in\mathcal{A}_{i}}\prod_{f\in
a_{i}}\tilde{\omega}_{i}^{t}(f)$. Let $a_{i}^{\ast}$ denote the pure Nash
equilibrium.

Notice that

$\displaystyle\prod_{f\in
a_{i}^{\ast}}\exp\left(\eta\sum^{T}_{j=1}\tilde{y}_{i}^{j}(f)\right)=\prod_{f\in
a_{i}^{\ast}}\tilde{\omega}_{i}^{T}(f)\leq\
Q_{i}^{T}=Q_{i}^{0}\frac{Q_{i}^{1}}{Q_{i}^{0}}\ldots\frac{Q_{i}^{T}}{Q_{i}^{T-1}}=Q_{i}^{0}\prod\frac{Q_{i}^{t}}{Q_{i}^{t-1}}\,.$

By the definition of $Q_{i}^{t}$ and the update rules of Algorithm 1, we have

$\displaystyle\frac{Q_{i}^{t}}{Q_{i}^{t-1}}=\ $
$\displaystyle\frac{\sum_{a_{i}\in\mathcal{A}_{i}}\prod_{f\in
a_{i}}\tilde{\omega}_{i}^{t}(f)}{Q_{i}^{t-1}}$ $\displaystyle=\ $
$\displaystyle\sum_{a_{i}\in\mathcal{A}_{i}}\left(\frac{\exp\left(\eta\sum^{t-1}_{j=1}\sum_{f\in
a_{i}}\tilde{y}_{i}^{j}(f)\right)}{Q_{i}^{t-1}}\right)\exp\left(\eta\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)\right)$ $\displaystyle=\ $
$\displaystyle\sum_{a_{i}\in\mathcal{A}_{i}}\left(\frac{\prod_{f\in
a_{i}}\tilde{\omega}_{i}^{t-1}(f)}{Q_{i}^{t-1}}\right)\exp\left(\eta\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)\right)$ $\displaystyle=\ $
$\displaystyle\sum_{a_{i}\in\mathcal{A}_{i}}\left(\frac{\prod_{f\in
a_{i}}\tilde{\omega}_{i}^{t-1}(f)}{Q_{i}^{t-1}}\right)\exp\left(\eta\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)\right)$ $\displaystyle=\ $
$\displaystyle\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\exp\left(\eta\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)\right)$ $\displaystyle\leq\ $
$\displaystyle\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\left(1+\eta\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)+\left(\eta\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)\right)^{2}\right)$ $\displaystyle=\ $
$\displaystyle
1+\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\left(\eta\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)+\left(\eta\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)\right)^{2}\right)$ $\displaystyle\leq\ $
$\displaystyle\exp\left(\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\left(\eta\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)+\left(\eta\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)\right)^{2}\right)\right)\,,$

where the first inequality is by $\eta\leq\frac{1}{k}$, $\exp(x)\leq
1+x+x^{2}$ for $x\leq 1$ and the second inequality is by $1+x\leq\exp(x)$ for
$x\in\mathbb{R}$.

By initialization, we also have

$\displaystyle
Q_{i}^{0}=\sum_{a_{i}\in\mathcal{A}_{i}}\exp\left(\eta\sum_{f\in
a_{i}}\tilde{y}_{i}^{0}(f)\right)\leq A_{i}\,.$

Thus we have

$\displaystyle\prod_{f\in
a_{i}^{\ast}}\exp\left(\eta\sum^{T}_{j=1}\tilde{y}_{i}^{j}(f)\right)=\ $
$\displaystyle\exp\left(\eta\sum^{T}_{j=1}\sum_{f\in
a_{i}^{\ast}}\tilde{y}_{i}^{j}(f)\right)$ $\displaystyle\leq\ $ $\displaystyle
A_{i}\prod^{T}_{t=1}\exp\left(\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\left(\eta\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)+\left(\eta\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)\right)^{2}\right)\right)$ $\displaystyle=\ $
$\displaystyle
A_{i}\exp\left(\sum^{T}_{t=1}\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\left(\eta\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)+\eta^{2}\left(\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)\right)^{2}\right)\right)\,.$

Taking logarithms on both sides, and noticing that $\log\left(A_{i}\right)\leq
kF$ we have

$\displaystyle\eta\sum^{T}_{j=1}\sum_{f\in
a_{i}^{\ast}}\tilde{y}_{i}^{j}(f)\leq\ $ $\displaystyle
kF+\sum^{T}_{t=1}\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\left(\eta\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)+\eta^{2}\left(\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)\right)^{2}\right)\,.$

Rearranging the terms, we have

$\displaystyle\sum^{T}_{t=1}\sum_{f\in
a_{i}^{\ast}}\tilde{y}_{i}^{t}(f)-\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a)\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)\leq\frac{kF}{\eta}+\eta\sum^{T}_{t=1}\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\left(\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)\right)^{2}\,.$

It thus amounts to bound the second term. By the definition of
$\tilde{y}_{i}^{t}$, we have

$\displaystyle\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\left(\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)\right)^{2}$ $\displaystyle=\ $
$\displaystyle\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\left(\sum_{f\in
a_{i}}1-\frac{\mathbb{I}\\{f\in
a_{i}^{t}\\}(1-R^{f}(a^{t}_{i},a^{t}_{-i}))}{q_{i}^{t}(f)}\right)^{2}$
$\displaystyle\leq\ $ $\displaystyle
k\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\sum_{f\in
a_{i}}\left(1-\frac{\mathbb{I}\\{f\in
a_{i}^{t}\\}(1-R^{f}(a^{t}_{i},a^{t}_{-i}))}{q_{i}^{t}(f)}\right)^{2}$
$\displaystyle=\ $ $\displaystyle
k\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\sum_{f\in
a_{i}}\left(1-\frac{2\mathbb{I}\left\\{f\in
a_{i}^{t}\right\\}\left(1-R_{i}^{f}\left(a_{i}^{t},a_{i}^{t}\right)\right)}{q_{i}^{t}(f)}+\left(\frac{\mathbb{I}\left\\{f\in
a_{i}^{t}\right\\}\left(1-R_{i}^{f}\left(a_{i}^{t},a_{-i}^{t}\right)\right)}{q_{i}^{t}(f)}\right)^{2}\right)$
$\displaystyle=\ $ $\displaystyle
k+k\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\sum_{f\in
a_{i}}\left(\left(\frac{\mathbb{I}\left\\{f\in
a_{i}^{t}\right\\}\left(1-R_{i}^{f}\left(a_{i}^{t},a_{-i}^{t}\right)\right)}{q_{i}^{t}(f)}\right)^{2}-\frac{2\mathbb{I}\left\\{f\in
a_{i}^{t}\right\\}\left(1-R_{i}^{f}\left(a_{i}^{t},a_{-i}^{t}\right)\right)}{q_{i}^{t}(f)}\right)$
$\displaystyle=\ $ $\displaystyle
k+k\sum_{f\in\mathcal{F}}\left(\left(\frac{\mathbb{I}\left\\{f\in
a_{i}^{t}\right\\}\left(1-R_{i}^{f}\left(a_{i}^{t},a_{-i}^{t}\right)\right)}{q_{i}^{t}(f)}\right)^{2}-\frac{2\mathbb{I}\left\\{f\in
a_{i}^{t}\right\\}\left(1-R_{i}^{f}\left(a_{i}^{t},a_{-i}^{t}\right)\right)}{q_{i}^{t}(f)}\right)\sum_{a_{i}\in\mathcal{A},f\in
a_{i}}\omega_{i}^{t}(a_{i})$ $\displaystyle=\ $ $\displaystyle
k+k\sum_{f\in\mathcal{F}}\left(\left(\frac{\mathbb{I}\left\\{f\in
a_{i}^{t}\right\\}\left(1-R_{i}^{f}\left(a_{i}^{t},a_{-i}^{t}\right)\right)}{q_{i}^{t}(f)}\right)^{2}-\frac{2\mathbb{I}\left\\{f\in
a_{i}^{t}\right\\}\left(1-R_{i}^{f}\left(a_{i}^{t},a_{-i}^{t}\right)\right)}{q_{i}^{t}(f)}\right)q_{i}^{t}(f)$
$\displaystyle=\ $ $\displaystyle
k+k\sum_{f\in\mathcal{F}}\left(\left(\frac{\mathbb{I}\left\\{f\in
a_{i}^{t}\right\\}\left(1-R_{i}^{f}\left(a_{i}^{t},a_{-i}^{t}\right)\right)}{q_{i}^{t}(f)}\right)^{2}q_{i}^{t}(f)-2\mathbb{I}\left\\{f\in
a_{i}^{t}\right\\}\left(1-R_{i}^{f}\left(a_{i}^{t},a_{-i}^{t}\right)\right)\right)$
$\displaystyle\leq\ $ $\displaystyle
k+k\sum_{f\in\mathcal{F}}\left(\frac{\mathbb{I}\left\\{f\in
a_{i}^{t}\right\\}\left(1-R_{i}^{f}\left(a_{i}^{t},a_{-i}^{t}\right)\right)}{q_{i}^{t}(f)}\right)^{2}q_{i}^{t}(f)\,.$

Let $\mathbb{E}_{t}[\cdot]$ denote conditional expectation over all history up
to time $t$. Notice that our estimator $\tilde{y}_{i}^{t}(f)$ is unbiased.
Taking expectations on both sides yield

$\displaystyle\mathbb{E}\left[\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a_{i})\left(\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)\right)^{2}\right]\leq\ $ $\displaystyle
k+k\mathbb{E}\left[\sum_{f\in\mathcal{F}}\left(\frac{\mathbb{I}\left\\{f\in
a_{i}^{t}\right\\}\left(1-R_{i}^{f}\left(a_{i}^{t},a_{-i}^{t}\right)\right)}{q_{i}^{t}(f)}\right)^{2}q_{i}^{t}(f)\right]$
$\displaystyle\leq\ $ $\displaystyle
k+k\mathbb{E}\left[\mathbb{E}_{t-1}\left[\sum_{f\in\mathcal{F}}\frac{\mathbb{I}\left\\{f\in
a_{i}^{t}\right\\}}{q_{i}^{t}(f)}\right]\right]$ $\displaystyle\leq\ $
$\displaystyle k+kF\,.$

Combining the terms, and by the unbiasedness of our estimator
$\tilde{y}_{i}^{t}$, we have

$\displaystyle\text{Regret}_{i}(T)=\ $
$\displaystyle\mathbb{E}\left[\sum^{T}_{t=1}\sum_{f\in
a_{i}^{\ast}}\tilde{y}_{i}^{t}(f)-\sum_{a_{i}\in\mathcal{A}_{i}}\omega_{i}^{t}(a)\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)\right]$ $\displaystyle\leq\ $
$\displaystyle\frac{kF}{\eta}+\eta T\left(k+kF\right)$ $\displaystyle=\ $
$\displaystyle O\left(\frac{kF}{\eta}+\eta T\left(kF\right)\right)\,.$

Taking $\eta=\frac{1}{\sqrt{T}}$ gives

$\displaystyle\text{Regret}_{i}(T)=O\left(kF\sqrt{T}\right)\,.$

∎

##  B Proof of Corollary 5.1

See 5.1

###### Proof.

The proof largely follows from Proposition 2 of (Syrgkanis et al., 2015).

Denote $a_{i}^{\ast}=\mathop{\rm
argmax}_{\omega_{i}\in{\mathcal{A}}_{i}}\sum^{T}_{t=1}r_{i}(\omega_{i},\omega_{-i}^{t})-r_{i}(\omega_{i}^{t},\omega_{-i}^{t})$.

For any $i\in[n]$ and policy $\omega=(\omega_{i},\omega_{-i})$, by Definition
3.3, we have

$\displaystyle\sum^{T}_{t=1}r_{i}(\omega_{i},\omega_{-i})\geq\sum^{T}_{t=1}r_{i}(a_{i}^{\ast},\omega_{-i}^{t})-\mathrm{Regret}_{i}(T)\,.$

Summing over $i\in[n]$, we have

$\displaystyle\sum^{n}_{i=1}\sum^{T}_{t=1}r_{i}(\omega_{i},\omega_{-i})\geq\ $
$\displaystyle\sum^{n}_{i=1}\sum^{T}_{t=1}r_{i}(a_{i}^{\ast},\omega_{-i}^{t})-\sum^{n}_{i=1}\mathrm{Regret}_{i}(T)$
$\displaystyle=\ $
$\displaystyle\sum^{n}_{i=1}\sum^{T}_{t=1}\mathbb{E}_{a_{-i}^{t}\sim\omega^{t}}\left[r_{i}(a_{i}^{\ast},a_{-i}^{t})\right]-\sum^{n}_{i=1}\mathrm{Regret}_{i}(T)$
$\displaystyle\geq\ $
$\displaystyle\lambda\cdot\mathrm{OPT}-\mu\mathbb{E}_{a\sim\omega^{t}}\left[W(a)\right]-\sum^{n}_{i=1}\mathrm{Regret}_{i}(T)\,,$

where the second inequality is by Definition 3.2.

Rearranging the terms and substituting results from Theorem 5.1, we have

$\displaystyle\frac{1}{T}\sum^{T}_{t=1}W(\omega^{t})\geq\frac{\lambda}{1+\mu}\mathrm{OPT}-\frac{1}{T(1+\mu)}\sum^{n}_{i=1}O\left(k\log\left(A_{i}\right)\sqrt{T}+F\sqrt{T}\right)\,.$

∎

##  C Proof of Lemma 5.2

See 5.2

###### Proof.

$\displaystyle\omega_{i}^{t}(a_{i}^{\ast})=\ $ $\displaystyle\frac{\prod_{f\in
a_{i}^{\ast}}\tilde{\omega}_{i}^{t}(f)}{\sum_{a^{\prime}\in\mathcal{A}}\prod_{f^{\prime}\in
a^{\prime}}\tilde{\omega}_{i}^{t}\left(f^{\prime}\right)}=\frac{\prod_{f\in
a_{i}^{\ast}}\exp\left(\eta\sum^{t}_{j=0}\tilde{y}_{i}^{j}(f)\right)}{\sum_{a^{\prime}\in\mathcal{A}}\prod_{f^{\prime}\in
a^{\prime}}\exp\left(\eta\sum^{t}_{j=0}\tilde{y}_{i}^{j}\left(f^{\prime}\right)\right)}\,.$

Without loss of generality, we order the facility from $1,\ldots,|F|$, such
that $f_{1},\ldots,f_{k}$ form the optimal pure Nash action $a_{i}^{\ast}$. We
have

$\displaystyle\frac{\prod_{f\in
a_{i}^{\ast}}\exp\left(\eta\sum^{t}_{j=0}\tilde{y}_{i}^{j}(f)\right)}{\sum_{a^{\prime}\in\mathcal{A}}\prod_{f^{\prime}\in
a^{\prime}}\exp\left(\eta\sum^{t}_{j=0}\tilde{y}_{i}^{j}\left(f^{\prime}\right)\right)}\geq\
$
$\displaystyle\prod_{m\in[k]}\frac{\exp\left(\eta\sum^{t}_{j=0}\tilde{y}_{i}^{j}\left(f_{m}\right)\right)}{\exp\left(\eta\sum^{t}_{j=0}\tilde{y}_{i}^{j}\left(f_{m}\right)\right)+\sum_{\ell>k}\exp\left(\eta\sum^{t}_{j=0}\tilde{y}_{i}^{j}\left(f_{\ell}\right)\right)}\,,$

where the inequality is by noting that any $\prod_{f^{\prime}\in
a^{\prime}}\exp\left(\eta\sum^{t}_{j=0}\tilde{y}_{i}^{t}(f^{\prime})\right)$
on the denominator of the left-hand side can be found on the product of the
denominators of the right-hand side. We then have

$\displaystyle\prod_{m\in[k]}\frac{\exp\left(\eta\sum^{t}_{j=0}\tilde{y}_{i}^{j}\left(f_{m}\right)\right)}{\exp\left(\eta\sum^{t}_{j=0}\tilde{y}_{i}^{j}\left(f_{m}\right)\right)+\sum_{\ell>k}\exp\left(\eta\sum^{t}_{j=0}\tilde{y}_{i}^{j}\left(f_{\ell}\right)\right)}$
$\displaystyle=\ $
$\displaystyle\prod_{m\in[k]}\frac{1}{1+\sum_{\ell>k}\exp\left(\eta\sum^{t}_{j=0}\left(\tilde{y}_{i}^{j}\left(f_{\ell}\right)-\tilde{y}_{i}^{j}\left(f_{m}\right)\right)\right)}$
$\displaystyle\geq\ $
$\displaystyle\prod_{m\in[k]}\left(1-\sum_{\ell>k}\exp\left(\eta\sum^{t}_{j=0}\left(\tilde{y}_{i}^{j}\left(f_{\ell}\right)-\tilde{y}_{i}^{j}\left(f_{m}\right)\right)\right)\right)$
$\displaystyle\geq\ $
$\displaystyle\prod_{m\in[k]}\left(1-\sum_{\ell>k}\exp\left(-\eta
M\right)\right)$ $\displaystyle\geq\ $ $\displaystyle 1-kF\exp\left(-\eta
M\right)\,,$

where the second inequality is by considering an action $a_{i}$ formed from
$a_{i}^{\ast}$ by replacing $f_{m}$ with $f_{\ell}$, then

$\displaystyle\tilde{z}_{i}^{t}(a_{i})=\sum^{t}_{j=0}\left(\sum_{f\in
a_{i}}\tilde{y}_{i}^{j}(f)-\sum_{f^{\prime}\in
a^{\ast}_{i}}\tilde{y}_{i}^{j}\left(f^{\prime}\right)\right)=\ $
$\displaystyle\sum^{t}_{j=0}\left(\sum_{f\in a_{i},f\neq
f_{m}}\tilde{y}_{i}^{j}(f)+\tilde{y}_{i}^{j}(f_{\ell})-\sum_{f\in
a_{i}^{\ast}}\tilde{y}_{i}^{j}(f)\right)$ $\displaystyle=\ $
$\displaystyle\sum^{t}_{j=0}\left(\tilde{y}_{i}^{j}(f_{\ell})-\tilde{y}_{i}^{j}(f_{m})\right)\leq\
-M\,.$

The last inequality is by the condition of $z_{i}^{t}(a_{i})\leq-M$.

Therefore,

$\displaystyle\left\|\omega_{i}^{t}-\omega_{i}^{\ast}\right\|_{1}=\ $
$\displaystyle 2(1-\omega_{i}^{t}(a_{i}^{\ast}))$ $\displaystyle\leq\ $
$\displaystyle 2(kF\exp(-M))\,.$

To have $U_{M}\subseteq U_{\epsilon}$, for any $\epsilon$, we let

$\displaystyle 2(kF\exp(-M))\leq\ $ $\displaystyle\epsilon\,,$ $\displaystyle
M\geq\ $ $\displaystyle\left|\log\left(\frac{\epsilon}{2kF}\right)\right|\,.$

For the second claim, notice that

$\displaystyle\tilde{z}_{i}^{t+1}(a_{i})=\ $
$\displaystyle\tilde{z}_{i}^{t}(a_{i})+\eta\left(\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)-\sum_{f^{\ast}\in
a_{i}^{\ast}}\tilde{y}_{i}^{t}(f^{\ast})\right)$ $\displaystyle\leq\ $
$\displaystyle\tilde{z}_{i}^{t}(a_{i})-\eta\epsilon$ $\displaystyle\leq\ $
$\displaystyle-M-\eta\epsilon\,,$

where the first inequality is due to the definition of $U$. Since
$\omega_{i}^{t+1}$ is induced by $\tilde{z}_{i}^{t+1}(a_{i})$, we have
$\omega_{i}^{t+1}\in U_{M}$. ∎

##  D Proof of Theorem 5.3

See 5.3

###### Proof.

Define
$r_{i}^{f}(a_{i},\omega_{-i})=\mathbb{E}_{a_{-i}\sim\omega_{-i}}[r_{i}^{f}(a_{i},a_{-i})]$.
Let $x_{i}^{t}(f)=\tilde{y}_{i}^{t}(f)-r_{i}^{f}(a_{i}^{t},\omega_{-i}^{t})$,
then we have

$\displaystyle\tilde{z}_{i}^{t+1}(a_{i})=\ $
$\displaystyle\tilde{z}_{i}^{t}(a_{i})+\eta_{t}\left(\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)-\sum_{f\in
a^{\ast}_{i}}\tilde{y}_{i}^{t}(f)\right)$ $\displaystyle=\ $
$\displaystyle\tilde{z}_{i}^{t}(a_{i})+\eta_{t}\left(\sum_{f\in
a_{i}}r_{i}^{f}(a_{i}^{t},\omega_{-i}^{t})-\sum_{f\in
a^{\ast}_{i}}r_{i}^{f}(a_{i}^{t},\omega_{-i}^{t})\right)$
$\displaystyle+\eta_{t}\left(\left(\sum_{f\in
a_{i}}\tilde{y}_{i}^{t}(f)-\sum_{f\in
a^{\ast}_{i}}\tilde{y}_{i}^{t}(f)\right)-\left(\sum_{f\in
a_{i}}r_{i}^{f}(a_{i}^{t},\omega_{-i}^{t})-\sum_{f\in
a^{\ast}_{i}}r_{i}^{f}(a_{i}^{t},\omega_{-i}^{t})\right)\right)\,.$

Define

$U_{2M}=\left\\{\omega^{t}\text{ computed by Algorithm \ref{alg}
}\mid\tilde{z}_{i}^{t}(a_{i})\leq-2M\,,\forall a_{i}\neq a_{i}^{\ast},\forall
i\in[n]\right\\}\,.$

Similar to Lemma 5.2, suppose that we initialize the algorithm such that
$\tilde{z}_{i}^{0}(a_{i})\leq-2M$, $\forall i\in[n]$ and with sufficiently
large $M$, $U_{2M}\subseteq U_{\epsilon}$. Then, we have

$\displaystyle\tilde{z}_{i}^{t+1}(a_{i})=\ $
$\displaystyle\tilde{z}_{i}^{t}(a_{i})+\sum^{t}_{j=0}\eta_{j}\left(\sum_{f\in
a_{i}}r_{i}^{f}(a_{i}^{j},\omega_{-i}^{j})-\sum_{f\in
a^{\ast}_{i}}r_{i}^{f}(a_{i}^{j},\omega_{-i}^{j})\right)+2k\max_{f}\sum^{t}_{j=0}\eta_{j}x_{i}^{t}(f)$
$\displaystyle\leq\ $
$\displaystyle-2M_{i}+\sum^{t}_{j=0}\eta_{j}\left(\sum_{f\in
a_{i}}r_{i}^{f}(a_{i}^{j},\omega_{-i}^{j})-\sum_{f\in
a^{\ast}_{i}}r_{i}^{f}(a_{i}^{j},\omega_{-i}^{j})\right)+2k\max_{f}\sum^{t}_{j=0}\eta_{j}x_{i}^{t}(f)\,.$
(10)

Let $X_{i}^{t}(f)=\sum^{t}_{j=1}\eta_{j}x_{i}^{t}(f)$, then $X_{i}^{t}(f)$ is
a Martingale. By Doob’s maximal inequality, we have

$\displaystyle\mathbb{P}\left[\max_{j\in[1,t]}\left|X_{i}^{j}(f)\right|\geq
M/2k\right]\leq\frac{4k^{2}\mathbb{E}\left[X_{i}^{t}(f)^{2}\right]}{\left(M\right)^{2}}\leq\frac{4k^{2}\cdot
j\sum^{t}_{j=0}\eta_{j}^{2}}{\left(M\right)^{2}}\,.$

Notice that whenever
$\mathbb{I}\left\\{\max_{j\in[1,t]}\left|X_{i}^{j}(f)\right|\geq
M/2k\right\\}=1$,
$\mathbb{I}\left\\{\max_{j\in[1,t+1]}\left|X_{i}^{j}(f)\right|\geq
M/2k\right\\}=1$. Thus, by choosing
$\sum^{\infty}_{j=0}\eta_{j}^{2}\leq\frac{\delta\cdot
M_{i}^{2}}{8nk^{2}(F-1)}$, $\delta>0$, we have

$\displaystyle\mathbb{P}\left[\left|X_{i}^{j}(f)\right|\geq M/2k\,,\forall
t\right]\leq\frac{\delta}{n(F-1)}\,.$

Then we obtain

$\displaystyle\mathbb{P}\left[\max_{i\in[n],f\in\mathcal{F}}\sup_{t}\left|X_{i}^{j}(f)\right|\geq
M/2k\right]\leq\delta\,.$

With this and Eq. (D), we can use of Lemma 5.2 to show by induction that if
$\omega^{t}\in U_{M}$, so is $\omega^{t+1}$, with probability at least
$1-\delta$. Then, for any $i\in[n]$, we have

$\displaystyle\mathbb{P}\left[\tilde{z}_{i}^{t+1}(a_{i})\leq-M+\epsilon\sum^{t}_{j=0}\eta_{j}\right]\leq\delta\,.$

Similar to the argument of Theorem 5.2, we have

$\displaystyle\omega_{i}^{t}(a_{i}^{\ast})\geq\ $ $\displaystyle
1-kF\exp\left(-M+\epsilon\sum^{t}_{j=0}\eta_{j}\right)\,,$

with probability at least $1-\delta$.

Hence, with a probability of at least $1-\delta$, we have

$\displaystyle\|\omega_{i}^{t}-\omega_{i}^{\ast}\|_{1}\leq
2kF\exp\left(-M+\epsilon\sum^{t}_{j=0}\eta_{j}\right)\,.$

∎