Oracle-Efficient Algorithms for Online Linear Optimization with Bandit Feedback
Authors: Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, Ken-Ichi Kawarabayashi
NeurIPS 2019 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our contribution is to propose algorithms that offer optimal regret bounds of O( T) as well as low oracle complexity for both non-stochastic settings and stochastic settings. Our algorithm for non-stochastic settings has an oracle complexity of O(T) and is the first algorithm that achieves both a regret bound of O( T) and an oracle complexity of O(poly(T)), given only linear optimization oracles. |
| Researcher Affiliation | Collaboration | Shinji Ito NEC Corporation, The University of Tokyo EMAIL Daisuke Hatano RIKEN AIP EMAIL Hanna Sumita Tokyo Metropolitan University EMAIL Kei Takemura NEC Corporation EMAIL Takuro Fukunaga Chuo University, RIKEN AIP, JST PRESTO EMAIL Naonori Kakimura Keio University EMAIL Ken-ichi Kawarabayashi National Institute of Informatics EMAIL |
| Pseudocode | Yes | Algorithm 1 An oracle efficient algorithm for non-stochastic bandit linear optimization |
| Open Source Code | No | The paper does not contain any explicit statements about the release of open-source code for the described methodology, nor does it provide any links to a code repository. |
| Open Datasets | No | The paper presents theoretical algorithms and does not involve empirical training on specific datasets. Therefore, no information about publicly available training datasets is provided. |
| Dataset Splits | No | The paper focuses on theoretical contributions and does not describe empirical experiments that would require validation dataset splits. Therefore, no information regarding training/test/validation dataset splits is provided. |
| Hardware Specification | No | The paper focuses on theoretical algorithms and does not describe any empirical experiments or their computational execution. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper describes theoretical algorithms and does not mention any specific software dependencies or their version numbers required for replication. |
| Experiment Setup | No | The paper describes theoretical algorithms and their properties, not an empirical experiment. While Algorithm 1 lists theoretical parameters like 'Learning rate η > 0' and 'error bound ε > 0', these are not concrete experimental setup details like hyperparameters used in an actual computational run. |