Matroid Semi-Bandits in Sublinear Time
Authors: Ruo-Chun Tzeng, Naoto Ohsaka, Kaito Ariu
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our technique is based on dynamic maintenance of an approximate maximum-weight basis over inner-product weights. Although the introduction of an approximate maximum-weight basis presents a challenge in regret analysis, we can still guarantee an upper bound on regret as tight as CUCB in the sense that it matches the gap-dependent lower bound by Kveton et al. (2014a) asymptotically. ... For T N, the expected regret of Algorithm 5 is upper bounded by... |
| Researcher Affiliation | Collaboration | Ruo-Chun Tzeng 1 Naoto Ohsaka 2 Kaito Ariu 2 Work done during an internship at Cyber Agent. 1EECS, KTH Royal Institue of Technology, Sweden 2AI Lab, Cyber Agent, Japan. |
| Pseudocode | Yes | Algorithm 1 A greedy maximum-weight basis algorithm ... Algorithm 5 Faster CUCB |
| Open Source Code | No | The paper does not provide any statement or link indicating the availability of open-source code. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and regret analysis for matroid semi-bandits. It does not conduct experiments on real-world datasets, nor does it provide access to any dataset for training. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical experiments with data. Therefore, it does not provide any details on validation splits. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and analysis. It does not conduct experiments that would require specifying hardware. |
| Software Dependencies | No | The paper is theoretical and does not conduct experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and analysis. It does not conduct empirical experiments, and therefore, no experimental setup details like hyperparameters or training settings are provided. |