An $\varepsilon$-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond
Authors: Marc Jourdan, Rémy Degenne, Emilie Kaufmann
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, we show through numerical simulations that EB-TCε performs favorably compared to existing algorithms, in different settings. We show through numerical simulations that EB-TCε performs favorably compared to existing algorithms, in different settings. We assess the performance of the EB-TCε0 algorithm on Gaussian instances both in terms of its empirical stopping time and its empirical simple regret, and we show that it perform favorably compared to existing algorithms, in both settings. |
| Researcher Affiliation | Academia | Marc Jourdan marc.jourdan@inria.fr Rémy Degenne remy.degenne@inria.fr Emilie Kaufmann emilie.kaufmann@univ-lille.fr Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189-CRISt AL, F-59000 Lille, France |
| Pseudocode | Yes | Figure 1: EB-TCε0 algorithm with fixed or IDS proportions. Figure 3: EB-TCm ε0 algorithm with fixed or IDS proportions. |
| Open Source Code | Yes | Our code is implemented in Julia 1.9.0, and the plots are generated with the Stats Plots.jl package. Other dependencies are listed in the Readme.md. The Readme.md file also provides detailed julia instructions to reproduce our experiments, as well as a script.sh to run them all at once. The general structure of the code (and some functions) is taken from the tidnabbil library. This library was created by [11], see https://bitbucket.org/wmkoolen/ tidnabbil. No license were available on the repository, but we obtained the authorization from the authors. |
| Open Datasets | Yes | We assess the performance of the EB-TCε0 algorithm on Gaussian instances both in terms of its empirical stopping time and its empirical simple regret, and we show that it perform favorably compared to existing algorithms, in both settings. For the sake of space, we only show the results for large sets of arms and for a specific instance with |i (µ)| = 2. Empirical stopping time We study the impact of large sets of arms (up to K = 1000) in ε-BAI for (ε, δ) = (0.1, 0.01) on the α = 0.3 scenario of [18] which sets µi = 1 ((i 1)/(K 1))α for all i [K]. ...Specific instances We continue the experimental validation of our the phenomenon described above by considering the three specific instances from the experimental section of [16] which are described in Table 3. |
| Dataset Splits | No | The paper does not explicitly mention training/test/validation dataset splits. It evaluates algorithms on synthetic 'Gaussian instances' or 'scenarios' with defined mean structures, which are typically used directly without explicit data partitioning in the conventional sense of supervised learning. |
| Hardware Specification | Yes | Our experiments are conducted on an institutional cluster with 4 Intel Xeon Gold 5218R CPU with 20 cores per CPU and an x86_64 architecture. |
| Software Dependencies | Yes | Our code is implemented in Julia 1.9.0, and the plots are generated with the Stats Plots.jl package. Other dependencies are listed in the Readme.md. |
| Experiment Setup | Yes | Empirical stopping time We study the impact of large sets of arms (up to K = 1000) in ε-BAI for (ε, δ) = (0.1, 0.01)... Throughout this section, we will be using EB-TCε0 with slack ε0 = 0.1. While IDS proportions are used for the experiments on the empirical stopping time, we use fixed β = 1/2 for the empirical simple regret. For the rate of decrease of (εn)n, we will be considering two archetypal choices: (a) polynomial by taking εn = n α/2 and (b) polylogarithmic by taking εn = log(n) α/2. We compare empirically those two rates of decrease for different choices of α, namely α {0.05, 0.1, 0.5}. To tackle BAI, we consider the GLR0 stopping rule (3) with (ε, δ) = (0, 0.01) and the heuristic threshold c(n, δ) = log((1 + log n)/δ). |