Skip to Main content Skip to Navigation
Conference papers

Fast routing under uncertainty: Adaptive learning in congestion games with exponential weights

Dong Quan Vu 1 Kimon Antonakopoulos 1 Panayotis Mertikopoulos 1, 2 
1 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : 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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-03357716
Contributor : Panayotis Mertikopoulos Connect in order to contact the contributor
Submitted on : Wednesday, September 29, 2021 - 2:59:32 AM
Last modification on : Wednesday, July 6, 2022 - 4:16:28 AM
Long-term archiving on: : Thursday, December 30, 2021 - 6:11:39 PM

File

AdaWeight.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03357716, version 1

Citation

Dong Quan Vu, Kimon Antonakopoulos, Panayotis Mertikopoulos. Fast routing under uncertainty: Adaptive learning in congestion games with exponential weights. NeurIPS 2021 - 35th International Conference on Neural Information Processing Systems, Dec 2021, Virtual, Unknown Region. pp.1-36. ⟨hal-03357716⟩

Share

Metrics

Record views

183

Files downloads

85