# Problem Dependent View on Structured Thresholding Bandit Problems

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

## 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 (most cited first, 14 of 14)

- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Stochastic Zeroth-order Optimization in High Dimensions](https://mlsanity.com/paper/1710.10551/) (2017)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.5096/) (2014)
- [Thresholding Bandit for Dose-ranging: The Impact of Monotonicity](https://mlsanity.com/paper/1711.04454/) (2017)
- [Thresholding Bandits with Augmented UCB](https://mlsanity.com/paper/1704.02281/) (2017)
- [The Influence of Shape Constraints on the Thresholding Bandit Problem](https://mlsanity.com/paper/2006.10006/) (2020)
- [Unimodal Thompson Sampling for Graph-Structured Arms](https://mlsanity.com/paper/1611.05724/) (2016)
- [Deterministic and Probabilistic Binary Search in Graphs](https://mlsanity.com/paper/1503.00805/) (2015)
- [Asynchronous Parallel Empirical Variance Guided Algorithms for the Thresholding Bandit Problem](https://mlsanity.com/paper/1704.04567/) (2017)
- [Unimodal Bandits without Smoothness](https://mlsanity.com/paper/1406.7447/) (2014)
- [Adaptive Sampling for Convex Regression](https://mlsanity.com/paper/1808.04523/) (2018)
- [On Zeroth-Order Stochastic Convex Optimization via Random Walks](https://mlsanity.com/paper/1402.2667/) (2014)

## Built on by (most cited first, 5 of 5)

- [On the Existence of a Complexity in Fixed Budget Bandit Identification](https://mlsanity.com/paper/2303.09468/) (2023)
- [LinearAPT: An Adaptive Algorithm for the Fixed-Budget Thresholding Linear Bandit Problem](https://mlsanity.com/paper/2403.06230/) (2024)
- [Choosing Answers in varepsilon-Best-Answer Identification for Linear Bandits](https://mlsanity.com/paper/2206.04456/) (2022)
- [Active Seriation: Efficient Ordering Recovery with Statistical Guarantees](https://mlsanity.com/paper/2603.15336/) (2026)
- [Threshold-Based Optimal Arm Selection in Monotonic Bandits: Regret Lower Bounds and Algorithms](https://mlsanity.com/paper/2509.02119/) (2025)

## 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.