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

• DOI: 10.48550/arxiv.2306.13673
• Publication Date: 2023-01-01
• Authors: Jing Dong; Jingyu Wu; Siwei Wang; Baoxiang Wang; Wei Chen
• Keywords: Sublinear function

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