  We introduce an online learning algorithm in the bandit feedback model that,
once adopted by all agents of a congestion game, results in game-dynamics that
converge to an $\epsilon$-approximate Nash Equilibrium in a polynomial number
of rounds with respect to $1/\epsilon$, the number of players and the number of
available resources. The proposed algorithm also guarantees sublinear regret to
any agent adopting it. As a result, our work answers an open question from
arXiv:2206.01880 and extends the recent results of arXiv:2306.15543 to the
bandit feedback model. We additionally establish that our online learning
algorithm can be implemented in polynomial time for the important special case
of Network Congestion Games on Directed Acyclic Graphs (DAG) by constructing an
exact $1$-barycentric spanner for DAGs.
