mlsanityData to 7 Oct 2026

An optimal algorithm for the Thresholding Bandit Problem

arXiv 1605.08671 ↗First posted 27 May 2016stat.ML cs.LGcited by 62

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 11; 2022: 11; 2023: 8; 2024: 10; 2025: 13; 2026: 9.

62 papers.

Sort:

By area:

  1. 2021Best Arm Identification with Safety Constraintscited by 25
  2. 2021Online certification of preference-based fairness for personalized recommender systemscited by 22
  3. 2023On the Existence of a Complexity in Fixed Budget Bandit Identificationcited by 19
  4. 2021A/B/n Testing with Control in the Presence of Subpopulationscited by 17
  5. 2021Nearly Optimal Algorithms for Level Set Estimationcited by 17
  6. 2021Maillard Sampling: Boltzmann Exploration Done Optimallycited by 13
  7. 2023Bandit Pareto Set Identification: the Fixed Budget Settingcited by 13
  8. 2022Interactively Learning Preference Constraints in Linear Banditscited by 11
  9. 2022Almost Cost-Free Communication in Federated Best Arm Identificationcited by 11
  10. 2022Non-Asymptotic Analysis of a UCB-based Top Two Algorithmcited by 11
  11. 2022Constrained Pure Exploration Multi-Armed Bandits with a Fixed Budgetcited by 9
  12. 2023Differential Good Arm Identificationcited by 8
38 more
  1. 2025Strategic Scaling of Test-Time Compute: A Bandit Learning Approachcited by 8
  2. 2024Query-Efficient Correlation Clustering with Noisy Oraclecited by 7
  3. 2024Active clustering with bandit feedbackcited by 7
  4. 2023An Anytime Algorithm for Good Arm Identificationcited by 6
  5. 2021Problem Dependent View on Structured Thresholding Bandit Problemscited by 5
  6. 2024lil'HDoC: An Algorithm for Good Arm Identification under Small Threshold Gapcited by 5
  7. 2024Reward Maximization for Pure Exploration: Minimax Optimal Good Arm Identification for Nonparametric Multi-Armed Banditscited by 5
  8. 2021Combinatorial Pure Exploration with Bottleneck Reward Functioncited by 4
  9. 2021Online Sign Identification: Minimization of the Number of Errors in Thresholding Banditscited by 3
  10. 2024Testing the Feasibility of Linear Programs with Bandit Feedbackcited by 3
  11. 2021Continuous Mean-Covariance Banditscited by 2
  12. 2021Contextual Combinatorial Multi-output GP Bandits with Group Constraintscited by 2
  13. 2022AutoFR: Automated Filter Rule Generation for Adblockingcited by 2
  14. 2022Safety Aware Changepoint Detection for Piecewise i.i.d. Banditscited by 2
  15. 2022Adaptive Identification of Populations with Treatment Benefit in Clinical Trials: Machine Learning Challenges and Solutionscited by 2
  16. 2023Improving the Knowledge Gradient Algorithmcited by 2
  17. 2024Adaptive Experiment Design with Synthetic Controlscited by 2
  18. 2024Representative Arm Identification: A fixed confidence approach to identify cluster representativescited by 2
  19. 2024Near Optimal Pure Exploration in Logistic Banditscited by 2
  20. 2025The Batch Complexity of Bandit Pure Explorationcited by 2
  21. 2025Bandit Pareto Set Identification in a Multi-Output Linear Modelcited by 2
  22. 2021Best Arm Identification under Additive Transfer Banditscited by 1
  23. 2022Choosing Answers in varepsilon-Best-Answer Identification for Linear Banditscited by 1
  24. 2022Adaptive Data Depth via Multi-Armed Banditscited by 1
  25. 2023Efficient Determination of Safety Requirements for Perception Systemscited by 1
  26. 2024Thresholding Data Shapley for Data Cleansing Using Multi-Armed Banditscited by 1
  27. 2025Online Clustering of Data Sequences with Bandit Informationcited by 1
  28. 2025Multi-thresholding Good Arm Identification with Bandit Feedbackcited by 1
  29. 2025Policy Testing in Markov Decision Processescited by 1
  30. 2025Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validationcited by 1
  31. 2025Near Optimal Non-asymptotic Sample Complexity of 1-Identificationcited by 1
  32. 2025Constrained Best Arm Identification with Tests for Feasibilitycited by 1
  33. 2026Fixed-Budget Constrained Best Arm Identification in Grouped Banditscited by 1
  34. 2026Best of both worlds: Stochastic & adversarial best-arm identificationcited by 1
  35. 2026Adaptive Test-Time Compute Allocation with Evolving In-Context Demonstrationscited by 1
  36. 2026Anytime-valid Optimal Policy Identificationcited by 1
  37. 2026Best-Arm Identification with Generative Proxycited by 1
  38. 2022Neural Bandits for Data Mining: Searching for Dangerous Polypharmacycited by 0

50 most cited of 62 All 62 (JSON)