Learning in Congestion Games with Bandit Feedback
This addresses efficient learning in congestion games for applications like traffic routing, with incremental extensions to non-stationary environments.
The paper tackles Nash-regret minimization in congestion games with bandit feedback, proposing centralized and decentralized algorithms that achieve sample complexity polynomial in players and facilities but independent of the exponentially large action set size, and extends this to Markov congestion games for non-stationary settings.
In this paper, we investigate Nash-regret minimization in congestion games, a class of games with benign theoretical structure and broad real-world applications. We first propose a centralized algorithm based on the optimism in the face of uncertainty principle for congestion games with (semi-)bandit feedback, and obtain finite-sample guarantees. Then we propose a decentralized algorithm via a novel combination of the Frank-Wolfe method and G-optimal design. By exploiting the structure of the congestion game, we show the sample complexity of both algorithms depends only polynomially on the number of players and the number of facilities, but not the size of the action set, which can be exponentially large in terms of the number of facilities. We further define a new problem class, Markov congestion games, which allows us to model the non-stationarity in congestion games. We propose a centralized algorithm for Markov congestion games, whose sample complexity again has only polynomial dependence on all relevant problem parameters, but not the size of the action set.