mlsanityData to 14 Oct 2026

Learning in Congestion Games with Bandit Feedback

arXiv 2206.01880 ↗First posted 4 Jun 2022cs.GT cs.LG cs.MAcited by 10

Not on the map. Why?

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.

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

25 of 69 references.

References · 25

  1. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
  2. 2018Is Q-learning Provably Efficient?cited by 487
  3. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  4. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
  5. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 113
  6. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
  7. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 93
  8. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
  9. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 57
  10. 2014Near-optimal Reinforcement Learning in Factored MDPscited by 41
  11. 2021Independent Natural Policy Gradient Always Converges in Markov Potential Gamescited by 37
  12. 2018Bandit learning in concave N-person gamescited by 35
13 more
  1. 2021Gradient play in stochastic games: stationary points, convergence, and sample complexitycited by 34
  2. 2019One Sample Stochastic Frank-Wolfecited by 32
  3. 2016Settling the complexity of computing approximate two-player Nash equilibriacited by 31
  4. 2018Learning Parametric Closed-Loop Policies for Markov Potential Gamescited by 21
  5. 2020Chaos, Extremism and Optimism: Volume Analysis of Learning in Gamescited by 16
  6. 2020Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RLcited by 16
  7. 2020Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processescited by 13
  8. 2022Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularizationcited by 10
  9. 2018Learning with minimal information in continuous gamescited by 8
  10. 2021Improved Rates for Derivative Free Gradient Play in Strongly Monotone Gamescited by 7
  11. 2019Game Theoretic Optimization via Gradient-based Nikaido-Isoda Functioncited by 6
  12. 2020Oracle-Efficient Regret Minimization in Factored MDPs with Unknown Structurecited by 6
  13. 2016Generalized Mirror Descents in Congestion Gamescited by 5

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 5; 2024: 3; 2025: 1.

10 papers.

  1. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 27
  2. 2023Instance-dependent Sample Complexity Bounds for Zero-sum Matrix Gamescited by 7
  3. 2023Markov α-Potential Gamescited by 6
  4. 2023A Black-box Approach for Non-stationary Multi-agent Reinforcement Learningcited by 3
  5. 2023Taming the Exponential Action Set: Sublinear Regret and Fast Convergence to Nash Equilibrium in Online Congestion Gamescited by 2
  6. 2025Convergence of Regret Matching in Potential Games and Constrained Optimizationcited by 2
  7. 2022Offline congestion games: How feedback type affects data coverage requirementcited by 1
  8. 2024Learning Optimal Tax Design in Nonatomic Congestion Gamescited by 1
  9. 2024Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Gamescited by 1
  10. 2024On the Decomposition of Differential Gamecited by 0