Taming the Exponential Action Set: Sublinear Regret and Fast Convergence
  to Nash Equilibrium in Online Congestion Games
Jing Dong Jingyu Wu Siwei Wang Baoxiang Wang Wei Chen
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)$.