Optimal Algorithms for Range Searching over Multi-Armed Bandits
Authors: Siddharth Barman, Ramakrishnan Krishnamurthy, Saladi Rahul
IJCAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper studies a multi-armed bandit (MAB) version of the range-searching problem. In this MAB setup, we develop sample-efficient algorithms that find, with high probability, near-optimal arms within the given intervals, i.e., we obtain PAC (probably approximately correct) guarantees. We also provide an algorithm for a generalization wherein the weight of each point is a multi-dimensional vector. The sample complexities of our algorithms depend, in particular, on the size of the optimal hitting set of the given intervals. Finally, we establish lower bounds proving that the obtained sample complexities are essentially tight. |
| Researcher Affiliation | Academia | Siddharth Barman1 , Ramakrishnan Krishnamurthy1 and Saladi Rahul1 1Indian Institute of Science, Bengaluru {barman, kramakrishna, saladi}@iisc.ac.in |
| Pseudocode | Yes | Algorithm 1 D-LSKY: finds ε-left-skyline with probability at least 1 δ ... Algorithm 2 ALG-D-RS: (ε, δ)-PAC algorithm for range searching d-dimensional weights |
| Open Source Code | No | The paper does not contain an unambiguous statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and complexity analysis. It does not describe experiments that use a specific dataset, nor does it provide concrete access information for any publicly available or open dataset for training. |
| Dataset Splits | No | The paper does not describe empirical experiments with datasets, and therefore, no training, validation, or test splits are mentioned for reproducibility. |
| Hardware Specification | No | The paper is theoretical and describes algorithms and their complexity. It does not mention any specific hardware used for running experiments. |
| Software Dependencies | No | The paper does not provide specific software dependencies with version numbers. It focuses on the theoretical aspects of algorithms. |
| Experiment Setup | No | The paper is theoretical, presenting algorithms and their complexity analysis. It does not include details about an experimental setup, such as hyperparameters or system-level training settings. |