# An optimal algorithm for the Thresholding Bandit Problem

arXiv: https://arxiv.org/abs/1605.08671 · HTML: https://mlsanity.com/paper/1605.08671/

## Key facts

- Cited by 62 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2016.

## Built on by (most cited first, 30 of 62)

- [Best Arm Identification with Safety Constraints](https://mlsanity.com/paper/2111.12151/) (2021)
- [Online certification of preference-based fairness for personalized recommender systems](https://mlsanity.com/paper/2104.14527/) (2021)
- [On the Existence of a Complexity in Fixed Budget Bandit Identification](https://mlsanity.com/paper/2303.09468/) (2023)
- [A/B/n Testing with Control in the Presence of Subpopulations](https://mlsanity.com/paper/2110.15573/) (2021)
- [Nearly Optimal Algorithms for Level Set Estimation](https://mlsanity.com/paper/2111.01768/) (2021)
- [Bandit Pareto Set Identification: the Fixed Budget Setting](https://mlsanity.com/paper/2311.03992/) (2023)
- [Maillard Sampling: Boltzmann Exploration Done Optimally](https://mlsanity.com/paper/2111.03290/) (2021)
- [Interactively Learning Preference Constraints in Linear Bandits](https://mlsanity.com/paper/2206.05255/) (2022)
- [Almost Cost-Free Communication in Federated Best Arm Identification](https://mlsanity.com/paper/2208.09215/) (2022)
- [Non-Asymptotic Analysis of a UCB-based Top Two Algorithm](https://mlsanity.com/paper/2210.05431/) (2022)
- [Constrained Pure Exploration Multi-Armed Bandits with a Fixed Budget](https://mlsanity.com/paper/2211.14768/) (2022)
- [Differential Good Arm Identification](https://mlsanity.com/paper/2303.07154/) (2023)
- [Strategic Scaling of Test-Time Compute: A Bandit Learning Approach](https://mlsanity.com/paper/2506.12721/) (2025)
- [Query-Efficient Correlation Clustering with Noisy Oracle](https://mlsanity.com/paper/2402.01400/) (2024)
- [Active clustering with bandit feedback](https://mlsanity.com/paper/2406.11485/) (2024)
- [An Anytime Algorithm for Good Arm Identification](https://mlsanity.com/paper/2310.10359/) (2023)
- [Problem Dependent View on Structured Thresholding Bandit Problems](https://mlsanity.com/paper/2106.10166/) (2021)
- [lil'HDoC: An Algorithm for Good Arm Identification under Small Threshold Gap](https://mlsanity.com/paper/2401.15879/) (2024)
- [Reward Maximization for Pure Exploration: Minimax Optimal Good Arm Identification for Nonparametric Multi-Armed Bandits](https://mlsanity.com/paper/2410.15564/) (2024)
- [Combinatorial Pure Exploration with Bottleneck Reward Function](https://mlsanity.com/paper/2102.12094/) (2021)
- [Online Sign Identification: Minimization of the Number of Errors in Thresholding Bandits](https://mlsanity.com/paper/2110.09133/) (2021)
- [Testing the Feasibility of Linear Programs with Bandit Feedback](https://mlsanity.com/paper/2406.15648/) (2024)
- [The Batch Complexity of Bandit Pure Exploration](https://mlsanity.com/paper/2502.01425/) (2025)
- [Continuous Mean-Covariance Bandits](https://mlsanity.com/paper/2102.12090/) (2021)
- [Contextual Combinatorial Multi-output GP Bandits with Group Constraints](https://mlsanity.com/paper/2111.14778/) (2021)
- [AutoFR: Automated Filter Rule Generation for Adblocking](https://mlsanity.com/paper/2202.12872/) (2022)
- [Safety Aware Changepoint Detection for Piecewise i.i.d. Bandits](https://mlsanity.com/paper/2205.13689/) (2022)
- [Adaptive Identification of Populations with Treatment Benefit in Clinical Trials: Machine Learning Challenges and Solutions](https://mlsanity.com/paper/2208.05844/) (2022)
- [Improving the Knowledge Gradient Algorithm](https://mlsanity.com/paper/2310.17901/) (2023)
- [Adaptive Experiment Design with Synthetic Controls](https://mlsanity.com/paper/2401.17205/) (2024)

## Abstract (arXiv)

We study a specific textitcombinatorial 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 textitfor 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 textitfixed budget for which optimal strategies are constructed.