Improving the Expected Improvement Algorithm
Authors: Chao Qin, Diego Klabjan, Daniel Russo
NeurIPS 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our main theoretical contribution is a complete characterization of the asymptotic proportion of samples TTEI allocates to each arm as a function of the true (unknown) arm means. These particular sampling proportions have been shown to be optimal from several perspectives [4, 12, 9, 19, 8], and this enables us to establish two different optimality results for TTEI. The first concerns the rate at which the algorithm gains confidence about the identity of the optimal arm as the total number of samples collected grows. Next we study the so-called fixed confidence setting, where the algorithm is able to stop at any point and return an estimate of the optimal arm. We show that when applied with the stopping rule of Garivier and Kaufmann [8], TTEI essentially minimizes the expected number of samples required among all rules obeying a constraint on the probability of incorrect selection. (...) To test the empirical performance of TTEI, we conduct several numerical experiments. |
| Researcher Affiliation | Academia | Chao Qin Columbia Business School New York, NY 10027 cqin22@gsb.columbia.edu Diego Klabjan Northwestern University Evanston, IL 60208 d-klabjan@northwestern.edu Daniel Russo Columbia Business School New York, NY 10027 djr2174@gsb.columbia.edu |
| Pseudocode | No | The paper describes the algorithms (Expected Improvement and Top-Two Expected Improvement) mathematically and in prose, but does not include a formal pseudocode block or algorithm listing. |
| Open Source Code | No | The paper does not provide any statement or link indicating that the source code for the methodology described is publicly available. |
| Open Datasets | No | The paper describes problem instances (e.g., '[5, 4, 1, 1, 1]') and a general problem setting (best-arm identification in a multiarmed bandit), but does not provide concrete access information (link, DOI, formal citation) to a specific publicly available dataset used for training. |
| Dataset Splits | No | The paper does not provide specific details on training, validation, and test dataset splits, such as percentages or sample counts. The terms 'train' and 'validation' are used in the context of Bayesian updates, not data partitioning. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware (e.g., CPU, GPU models, memory) used for running the experiments. |
| Software Dependencies | No | The paper does not provide specific software dependency details with version numbers, such as programming languages, libraries, or specialized solvers. |
| Experiment Setup | Yes | In both experiments, we fix the common known variance σ2 = 1 and the number of arms k = 5. We consider three instances [µ1, . . . , µ5] = [5, 4, 1, 1, 1], [5, 4, 3, 2, 1] and [2, 0.8, 0.6, 0.4, 0.2]. The optimal parameter β equals 0.48, 0.45 and 0.35, respectively. (...) TTEI with adaptive β (a TTEI) works as follows: it starts with β = 1/2 and updates β = ˆβ every 10 rounds where ˆβ is the maximizer of equation (2) based on plug-in estimators for the unknown arm-means. |