Learning in Congestion Games with Bandit Feedback
Learning Nash equilibria is a central problem in multi-agent systems. In this
paper, we investigate 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.