Timezone: »

 
Poster
Fast Routing under Uncertainty: Adaptive Learning in Congestion Games via Exponential Weights
Dong Quan Vu · Kimon Antonakopoulos · Panayotis Mertikopoulos

Thu Dec 09 12:30 AM -- 02:00 AM (PST) @
in Poster Session 5 »
We examine an adaptive learning framework for nonatomic congestion games where the players' cost functions may be subject to exogenous fluctuations (e.g., due to disturbances in the network, variations in the traffic going through a link). In this setting, the popular multiplicative/ exponential weights algorithm enjoys an $\mathcal{O}(1/\sqrt{T})$ equilibrium convergence rate; however, this rate is suboptimal in static environments---i.e., when the network is not subject to randomness. In this static regime, accelerated algorithms achieve an $\mathcal{O}(1/T^{2})$ convergence speed, but they fail to converge altogether in stochastic problems. To fill this gap, we propose a novel, adaptive exponential weights method---dubbed AdaWeight---that seamlessly interpolates between the $\mathcal{O}(1/T^{2})$ and $\mathcal{O}(1/\sqrt{T})$ rates in the static and stochastic regimes respectively. Importantly, this "best-of-both-worlds" guarantee does not require any prior knowledge of the problem's parameters or tuning by the optimizer; in addition, the method's convergence speed depends subquadratically on the size of the network (number of vertices and edges), so it scales gracefully to large, real-life urban networks.
Keywords: Theory

Author Information

Dong Quan Vu (Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG)

I am currently a postdoctoral researcher working at LIG – Laboratoire d’informatique de Grenoble (France); POLARIS Team. My current research interests lie at the intersection of Online Learning, Optimization and Game Theory with the scope of applications aiming towards Operational Research, Resource Management and Multi-agent Systems.

Kimon Antonakopoulos (INRIA)
Panayotis Mertikopoulos (CNRS (French National Center for Scientific Research) and Criteo AI Lab)

More from the Same Authors