# An optimal algorithm for the Thresholding Bandit Problem

Source: [An optimal algorithm for the Thresholding Bandit Problem](<https://www.sota2.com/research/paper/68fa62841e209131ce9f9c9c>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T20:21:33.904Z

Authors: Andrea Locatelli, Maurilio Gutzeit, Alexandra Carpentier

Published: 2016-05-27T14:35:29.000Z

## Abstract

We study a specific \\textit{combinatorial pure exploration stochastic bandit problem} where the learner aims at finding the set of arms whose means are above a given threshold, up to a given precision, and \\textit{for a fixed time horizon}. We propose a parameter-free algorithm based on an original heuristic, and prove that it is optimal for this problem by deriving matching upper and lower bounds. To the best of our knowledge, this is the first non-trivial pure exploration setting with \\textit{fixed budget} for which optimal strategies are constructed.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [e-good arm identification on Example 1](<https://www.sota2.com/research/sota/e-good-arm-identification-on-example-1.md>): e-good arm identification; Example 1; False Selection Probability: 17.

- [e-good arm identification on Example 3](<https://www.sota2.com/research/sota/e-good-arm-identification-on-example-3.md>): e-good arm identification; Example 3; False Selection Probability: 0.49.

- [e-good arm identification on Example 2](<https://www.sota2.com/research/sota/e-good-arm-identification-on-example-2.md>): e-good arm identification; Example 2; False Selection Probability: 25.

- [e-good arm identification on Dose-finding](<https://www.sota2.com/research/sota/e-good-arm-identification-on-dose-finding.md>): e-good arm identification; Dose-finding; False Selection Probability: 53.

- [e-good arm identification on Drug Selection](<https://www.sota2.com/research/sota/e-good-arm-identification-on-drug-selection.md>): e-good arm identification; Drug Selection; False Selection Probability: 70.

- [e-good arm identification on Caption 854](<https://www.sota2.com/research/sota/e-good-arm-identification-on-caption-854.md>): e-good arm identification; Caption 854; False Selection Probability: 48.

- [e-good arm identification on Caption 853](<https://www.sota2.com/research/sota/e-good-arm-identification-on-caption-853.md>): e-good arm identification; Caption 853; Probability of False Selection: 0.35.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1605.08671>)

[PDF](<https://arxiv.org/pdf/1605.08671.pdf>)