# Semi Bandit Dynamics in Congestion Games: Convergence to Nash Equilibrium and No-Regret Guarantees

arXiv: https://arxiv.org/abs/2306.15543 · HTML: https://mlsanity.com/paper/2306.15543/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jun 2023.

## Built on by (most cited first, 5 of 5)

- [Convergence of Regret Matching in Potential Games and Constrained Optimization](https://mlsanity.com/paper/2510.17067/) (2025)
- [Learning Optimal Tax Design in Nonatomic Congestion Games](https://mlsanity.com/paper/2402.07437/) (2024)
- [Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Games](https://mlsanity.com/paper/2404.06516/) (2024)
- [On the Decomposition of Differential Game](https://mlsanity.com/paper/2411.03802/) (2024)
- [Equilibrium with Internal Transfers](https://mlsanity.com/paper/2606.20960/) (2026)

## Abstract (arXiv)

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).