2022/01/09 by Dong Quan Vu, Kimon Antonakopoulos, Vu, Dong Quan +3 · 1 citation
Decision Sciences · Economics, Econometrics and Finance · #Advanced Bandit Algorithms Research #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2201.02985
openalex publication_date 2022/01/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the traffic assignment problem in nonatomic routing games where the players' cost functions may be subject to random fluctuations (e.g., weather disturbances, perturbations in the underlying network, etc.). We tackle this problem from the viewpoint of a control interface that makes routing recommendations based solely on observed costs and without any further knowledge of the system's governing dynamics -- such as the network's cost functions, the distribution of any random events affecting the network, etc. In this online setting, learning methods based on the popular exponential weights algorithm converge to equilibrium at an O(1/√(T)) rate: this rate is known to be order-optimal in stochastic networks, but it is otherwise suboptimal in static networks. In the latter case, it is possible to achieve an O(1/T2) equilibrium convergence rate via the use of finely tuned accelerated algorithms; on the other hand, these accelerated algorithms fail to converge altogether in the presence of persistent randomness, so it is not clear how to achieve the "best of both worlds" in terms of convergence speed. Our paper seeks to fill this gap by proposing an adaptive routing algortihm with the following desirable properties: (i) it seamlessly interpolates between the O(1/T2) and O(1/√(T)) rates for static and stochastic environments respectively; (ii) its convergence speed is polylogarithmic in the number of paths in the network; (iii) the method's per-iteration complexity and memory requirements are both linear in the number of nodes and edges in the network; and (iv) it does not require any prior knowledge of the problem's parameters.