Online Learning with Feedback Graphs: The True Shape of Regret
Authors: Tomáš Kocák, Alexandra Carpentier
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we define a new quantity R , called the problem complexity, and prove that the minimax regret is proportional to R for any graph and time horizon T. Introducing an intricate exploration strategy, we define the EXP3-EX algorithm that achieves the minimax optimal regret bound and becomes the first provably optimal algorithm for this setting, even if T is smaller than α3. |
| Researcher Affiliation | Academia | Tom aˇs Koc ak 1 Alexandra Carpentier 1 1Institute of Mathematics, University of Potsdam, Germany. |
| Pseudocode | Yes | Algorithm 1 EXP3-EX |
| Open Source Code | No | No explicit statement about providing open-source code or a link to a code repository for the described methodology was found. |
| Open Datasets | No | This paper is theoretical and does not describe any experiments involving datasets for training. |
| Dataset Splits | No | This paper is theoretical and does not describe any experiments involving dataset validation splits. |
| Hardware Specification | No | This paper is theoretical and does not describe any experiments that would require specific hardware specifications. |
| Software Dependencies | No | This paper is theoretical and does not describe any experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | This paper is theoretical and does not describe any experiments or their specific setup details like hyperparameters. |