Fast Routing under Uncertainty: Adaptive Learning in Congestion Games with Exponential Weights

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, etc.). In this setting, the popular multiplicative / exponential weights algorithm enjoys an O(1/ T) equilibrium convergence rate; however, this rate is suboptimal in static environments - i.e., when the network is not subject to randomness.