A Fast Algorithm for PAC Combinatorial Pure Exploration
Authors: Noa Ben-David, Sivan Sabato6064-6071
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We provide sample complexity guarantees for our algorithm, and demonstrate in experiments its usefulness on large problems, whereas previous algorithms are impractical to run on problems of even a few dozen arms. The code is provided at https://github.com/noabdavid/csale. The full version of this paper is available at https://arxiv.org/abs/2112.04197. |
| Researcher Affiliation | Academia | Noa Ben-David and Sivan Sabato Department of Computer Science Ben-Gurion University of the Negev Beer Sheva Israel bendanoa@post.bgu.ac.il, sabatos@cs.bgu.ac.il |
| Pseudocode | Yes | Algorithm 1: CSALE: Combinatorial Successive Acceptance with Light Elimination |
| Open Source Code | Yes | The code is provided at https://github.com/noabdavid/csale. |
| Open Datasets | No | The paper mentions using 'real-world graph data sets' and the 'USAir97 data set' but does not provide specific links, DOIs, repositories, or formal citations with authors and years for public access to these datasets within the provided text. |
| Dataset Splits | No | No text found that specifies dataset split information such as exact percentages, sample counts, or a detailed splitting methodology for training, validation, or test sets. |
| Hardware Specification | No | The paper states, 'All the experiments were run on a standard PC.' This is too vague and does not provide specific hardware details such as GPU/CPU models, processor types, or memory amounts. |
| Software Dependencies | No | The paper mentions using 'Dijkstra s algorithm as implemented in the Dijkstar package' and 'the algorithm of Galil (1986) as implemented in the Networkx package (Hagberg, Swart, and Schult 2008)'. However, it does not provide specific version numbers for these software packages or any other dependencies. |
| Experiment Setup | Yes | In all of the experiments, we set δ = 0.05. Each experiment was repeated 10 or 100 times, depending on its computational requirements, as detailed in each result table below. In all experiments, the weight of the edge was used as the parameter of a Bernoulli distribution describing its instantaneous rewards. In synthetic or unweighted graphs, the edge weights were sampled uniformly at random out of {0.1, 0.5, 0.9} in each run. |