Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Bandits with Feedback Graphs and Switching Costs
Authors: Raman Arora, Teodor Vanislavov Marinov, Mehryar Mohri
NeurIPS 2019 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We give two new algorithms for this problem in the informed setting. Our best algorithm achieves a pseudo-regret of O(γ(G) 2 3 ), where γ(G) is the domination number of the feedback graph. This significantly improves upon the previous best result for the same problem, which was based on the independence number of G. We also present matching lower bounds for our result that we describe in detail. Finally, we give a new algorithm with improved policy regret bounds when partial counterfactual feedback is available. All proofs of results are deferred to Appendix D. |
| Researcher Affiliation | Collaboration | Raman Arora Dept. of Computer Science Johns Hopkins University Baltimore, MD 21204 EMAIL Teodor V. Marinov Dept. of Computer Science Johns Hopkins University Baltimore, MD 21204 EMAIL Mehryar Mohri Google Research & Courant Institute of Math. Sciences New York, NY 10012 EMAIL |
| Pseudocode | Yes | Algorithm 1 Algorithm for star graphs. Algorithm 2 Algorithm for general feedback graphs. Algorithm 3 Corralling star-graph algorithms. Algorithm 4 Log-Barrier-OMD(qt, t, t). Algorithm 5 Policy regret with side observations. |
| Open Source Code | No | The paper does not provide explicit statements or links indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | This paper is theoretical and does not describe experiments performed on datasets, thus no dataset information is provided. |
| Dataset Splits | No | This paper is theoretical and does not describe experiments performed on datasets, thus no dataset split information is provided. |
| Hardware Specification | No | This paper is theoretical and does not describe any experiments that would require hardware specifications. |
| Software Dependencies | No | This paper is theoretical and does not describe any experiments that would require software dependencies with version numbers. |
| Experiment Setup | No | This paper is theoretical and does not describe any experiments or their setup, thus no hyperparameters or training settings are provided. |