mlsanityData to 14 Oct 2026

Problem Dependent View on Structured Thresholding Bandit Problems

arXiv 2106.10166 ↗First posted 18 Jun 2021stat.ML cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

We investigate the problem dependent regime in the stochastic Thresholding Bandit problem (TBP) under several shape constraints. In the TBP, the objective of the learner is to output, at the end of a sequential game, the set of arms whose means are above a given threshold. The vanilla, unstructured, case is already well studied in the literature. Taking K as the number of arms, we consider the case where (i) the sequence of arm's means (μk)k=1K is monotonically increasing (MTBP) and (ii) the case where (μk)k=1K is concave (CTBP). We consider both cases in the problem dependent regime and study the probability of error - i.e. the probability to mis-classify at least one arm. In the fixed budget setting, we provide upper and lower bounds for the probability of error in both the concave and monotone settings, as well as associated algorithms. In both settings the bounds match in the problem dependent regime up to universal constants in the exponential.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 14 of its 23 references that are in the map. First posted on arXiv 18 Jun 2021.

Builds on

14 of 23 references.

References · 14

  1. 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 79
  2. 2017Stochastic Zeroth-order Optimization in High Dimensionscited by 63
  3. 2016An optimal algorithm for the Thresholding Bandit Problemcited by 62
  4. 2016Combinatorial Multi-Armed Bandit with General Reward Functionscited by 56
  5. 2014Unimodal Bandits: Regret Lower Bounds and Optimal Algorithmscited by 37
  6. 2017Thresholding Bandit for Dose-ranging: The Impact of Monotonicitycited by 16
  7. 2017Thresholding Bandits with Augmented UCBcited by 11
  8. 2020The Influence of Shape Constraints on the Thresholding Bandit Problemcited by 11
  9. 2016Unimodal Thompson Sampling for Graph-Structured Armscited by 8
  10. 2015Deterministic and Probabilistic Binary Search in Graphscited by 6
  11. 2017Asynchronous Parallel Empirical Variance Guided Algorithms for the Thresholding Bandit Problemcited by 6
  12. 2014Unimodal Bandits without Smoothnesscited by 4
2 more
  1. 2018Adaptive Sampling for Convex Regressioncited by 2
  2. 2014On Zeroth-Order Stochastic Convex Optimization via Random Walkscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 1; 2024: 1; 2025: 1; 2026: 1.

5 papers.

  1. 2023On the Existence of a Complexity in Fixed Budget Bandit Identificationcited by 20
  2. 2024LinearAPT: An Adaptive Algorithm for the Fixed-Budget Thresholding Linear Bandit Problemcited by 2
  3. 2022Choosing Answers in varepsilon-Best-Answer Identification for Linear Banditscited by 1
  4. 2026Active Seriation: Efficient Ordering Recovery with Statistical Guaranteescited by 1
  5. 2025Threshold-Based Optimal Arm Selection in Monotonic Bandits: Regret Lower Bounds and Algorithmscited by 0