  In this work, we introduce a new variant of online gradient descent, which
provably converges to Nash Equilibria and simultaneously attains sublinear
regret for the class of congestion games in the semi-bandit feedback setting.
Our proposed method admits convergence rates depending only polynomially on the
number of players and the number of facilities, but not on the size of the
action set, which can be exponentially large in terms of the number of
facilities. Moreover, the running time of our method has polynomial-time
dependence on the implicit description of the game. As a result, our work
answers an open question from (Du et. al, 2022).
