Learning in Congestion Games with Bandit Feedback
Authors: Qiwen Cui, Zhihan Xiong, Maryam Fazel, Simon S. Du
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | Qiwen Cui1 qwcui@cs.washington.edu Zhihan Xiong1 zhihanx@cs.washington.edu Maryam Fazel2 mfazel@uw.edu Simon S. Du1 ssdu@cs.washington.edu 1 Paul G. Allen School of Computer Science & Engineering, University of Washington 2 Department of Electrical & Computer Engineering, University of Washington |
| Pseudocode | Yes | Algorithm 1 Nash-UCB for Congestion Games; Algorithm 2 ϵ-approximate Nash Equilibrium for Potential Games; Algorithm 3 Frank-Wolfe with Exploration for Congestion Game |
| Open Source Code | No | If you ran experiments... (a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A] |
| Open Datasets | No | The paper is theoretical and does not conduct empirical experiments with datasets. The ethics checklist states "If your work uses existing assets, did you cite the creators? [N/A]" and "Did you discuss whether and how consent was obtained from people whose data you re using/curating? [N/A]", indicating no data was used in experiments. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical experiments that would involve training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any hardware specifications for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not describe any specific software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and theoretical guarantees. It does not describe an experimental setup with hyperparameters or training details. |