Online Learning with Knapsacks: the Best of Both Worlds
Authors: Matteo Castiglioni, Andrea Celli, Christian Kroer
ICML 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Then, we provide the first best-of-both-worlds type framework for this setting, with no-regret guarantees both under stochastic and adversarial inputs. Our framework yields the same regret guarantees of prior work in the stochastic case. On the other hand, when budgets grow at least linearly in the time horizon, it allows us to provide a constant competitive ratio in the adversarial case, which improves over the O(m log T) competitive ratio of (Immorlica et al., 2019). Moreover, our framework allows the decision maker to handle non-convex reward and cost functions. We provide two game-theoretic applications of our framework to give further evidence of its flexibility. |
| Researcher Affiliation | Academia | 1DEIB, Politecnico di Milano, Milan, Italy 2Department of Computing Sciences, Bocconi University, Milan, Italy 3IEOR Department, Columbia University, New York, NY. |
| Pseudocode | Yes | Algorithm 1 Meta-algorithm for strategy mixture Ξ. |
| Open Source Code | No | No explicit statement or link regarding the public release of the source code for the described methodology was found in the paper. |
| Open Datasets | No | The paper is theoretical and does not describe experiments using specific datasets, thus no information on publicly available or open datasets for training is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments or dataset usage, therefore no specific dataset split information (training, validation, test) is provided. |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., GPU/CPU models, memory) used for running experiments, as it is a theoretical paper. |
| Software Dependencies | No | The paper does not provide specific ancillary software details with version numbers (e.g., libraries, solvers), as it is a theoretical paper. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments, therefore no specific experimental setup details (e.g., hyperparameter values, training configurations) are provided. |