Research map / Bandits and online learning / Online convex optimization and games
Learning in Congestion Games with Bandit Feedback
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Estimate facility rewards directly and use optimistic confidence bonuses | Centralized Nash-UCB · Congestion games, semi-bandit feedback | Nash regret: F\sqrt{mT} | Helped |
| Use linear-bandit ridge regression and confidence bonuses for aggregate feedback | Centralized Nash-UCB · Congestion games, bandit feedback | Nash regret: mF^{3/2}\sqrt{K} | Helped |
| Use Frank-Wolfe updates with G-optimal exploration | Decentralized Frank-Wolfe with Exploration · Congestion games, bandit feedback | Nash regret: m^2F^2T^{5/6}+m^3F^3T^{2/3} | Helped |
| Extend centralized Nash-UCB using independent facility-state transitions and Bellman updates | Centralized IMCG algorithm · Independent Markov congestion games | Nash regret: \sum_{f\in\mc{F}}FS^f\sqrt{mH^3T} + \tmco\Sp{m^2H^2F\sum_{f\neq f'}\Sp{S^fS^{f'}}^2} | Helped |
| Use direct action-level Nash-VI rather than exploit congestion-game facility structure | Congestion-game learning · Congestion games | sample complexity: (\prod_{i=1}^mA_i)F/\epsilon^2 | Hurt |
| Use the independent transition structure to avoid dependence on the full product state space | Centralized IMCG algorithm · Independent Markov congestion games | sample complexity | Helped |
Closest papers by meaning
- Semi Bandit dynamics in Congestion Games: Convergence to Nash Equilibrium and No-Regret Guarantees. (ICML 2023 · similarity 0.94)
- Offline Congestion Games: How Feedback Type Affects Data Coverage Requirement (ICLR 2023 · similarity 0.89)
- Learning with Bandit Feedback in Potential Games (NeurIPS 2017 · similarity 0.88)
- Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback (NeurIPS 2023 · similarity 0.88)
- Learning Optimal Tax Design in Nonatomic Congestion Games (NeurIPS 2024 · similarity 0.87)
- The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.