# Learning in Congestion Games with Bandit Feedback

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 69 references that are in the map.
- First posted on arXiv 4 Jun 2022.

## Builds on (most cited first, 25 of 25)

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence](https://mlsanity.com/paper/2202.04129/) (2022)
- [Near-optimal Reinforcement Learning in Factored MDPs](https://mlsanity.com/paper/1403.3741/) (2014)
- [Independent Natural Policy Gradient Always Converges in Markov Potential Games](https://mlsanity.com/paper/2110.10614/) (2021)
- [Bandit learning in concave N-person games](https://mlsanity.com/paper/1810.01925/) (2018)
- [Gradient play in stochastic games: stationary points, convergence, and sample complexity](https://mlsanity.com/paper/2106.00198/) (2021)
- [One Sample Stochastic Frank-Wolfe](https://mlsanity.com/paper/1910.04322/) (2019)
- [Settling the complexity of computing approximate two-player Nash equilibria](https://mlsanity.com/paper/1606.04550/) (2016)
- [Learning Parametric Closed-Loop Policies for Markov Potential Games](https://mlsanity.com/paper/1802.00899/) (2018)
- [Chaos, Extremism and Optimism: Volume Analysis of Learning in Games](https://mlsanity.com/paper/2005.13996/) (2020)
- [Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL](https://mlsanity.com/paper/2008.13319/) (2020)
- [Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes](https://mlsanity.com/paper/2006.13405/) (2020)
- [Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularization](https://mlsanity.com/paper/2204.05466/) (2022)
- [Learning with minimal information in continuous games](https://mlsanity.com/paper/1806.11506/) (2018)
- [Improved Rates for Derivative Free Gradient Play in Strongly Monotone Games](https://mlsanity.com/paper/2111.09456/) (2021)
- [Game Theoretic Optimization via Gradient-based Nikaido-Isoda Function](https://mlsanity.com/paper/1905.05927/) (2019)
- [Oracle-Efficient Regret Minimization in Factored MDPs with Unknown Structure](https://mlsanity.com/paper/2009.05986/) (2020)
- [Generalized Mirror Descents in Congestion Games](https://mlsanity.com/paper/1605.07774/) (2016)

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

- [Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation](https://mlsanity.com/paper/2302.03673/) (2023)
- [Instance-dependent Sample Complexity Bounds for Zero-sum Matrix Games](https://mlsanity.com/paper/2303.10565/) (2023)
- [Markov α-Potential Games](https://mlsanity.com/paper/2305.12553/) (2023)
- [A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2306.07465/) (2023)
- [Taming the Exponential Action Set: Sublinear Regret and Fast Convergence to Nash Equilibrium in Online Congestion Games](https://mlsanity.com/paper/2306.13673/) (2023)
- [Convergence of Regret Matching in Potential Games and Constrained Optimization](https://mlsanity.com/paper/2510.17067/) (2025)
- [Offline congestion games: How feedback type affects data coverage requirement](https://mlsanity.com/paper/2210.13396/) (2022)
- [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)

## Abstract (arXiv)

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.