# The Influence of Shape Constraints on the Thresholding Bandit Problem

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2020.

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

- [Best Arm Identification with Safety Constraints](https://mlsanity.com/paper/2111.12151/) (2021)
- [A/B/n Testing with Control in the Presence of Subpopulations](https://mlsanity.com/paper/2110.15573/) (2021)
- [Active clustering with bandit feedback](https://mlsanity.com/paper/2406.11485/) (2024)
- [Best-Arm Identification in Unimodal Bandits](https://mlsanity.com/paper/2411.01898/) (2024)
- [Problem Dependent View on Structured Thresholding Bandit Problems](https://mlsanity.com/paper/2106.10166/) (2021)
- [Online Sign Identification: Minimization of the Number of Errors in Thresholding Bandits](https://mlsanity.com/paper/2110.09133/) (2021)
- [LinearAPT: An Adaptive Algorithm for the Fixed-Budget Thresholding Linear Bandit Problem](https://mlsanity.com/paper/2403.06230/) (2024)
- [Active Seriation: Efficient Ordering Recovery with Statistical Guarantees](https://mlsanity.com/paper/2603.15336/) (2026)
- [Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints](https://mlsanity.com/paper/2410.18844/) (2024)
- [Locally Differentially Private Thresholding Bandits](https://mlsanity.com/paper/2507.23073/) (2025)
- [The Sample Complexity of Multiple Change Point Identification under Bandit Feedback](https://mlsanity.com/paper/2605.13252/) (2026)

## Abstract (arXiv)

We investigate the stochastic Thresholding Bandit problem (TBP) under several shape constraints. On top of (i) the vanilla, unstructured TBP, we consider the case where (ii) the sequence of arm's means (μk)k is monotonically increasing MTBP, (iii) the case where (μk)k is unimodal UTBP and (iv) the case where (μk)k is concave CTBP. In the TBP problem the aim is to output, at the end of the sequential game, the set of arms whose means are above a given threshold. The regret is the highest gap between a misclassified arm and the threshold. In the fixed budget setting, we provide problem independent minimax rates for the expected regret in all settings, as well as associated algorithms. We prove that the minimax rates for the regret are (i) √log(K)K/T for TBP, (ii) √log(K)/T for MTBP, (iii) √K/T for UTBP and (iv) √loglog K/T for CTBP, where K is the number of arms and T is the budget. These rates demonstrate that the dependence on K of the minimax regret varies significantly depending on the shape constraint. This highlights the fact that the shape constraints modify fundamentally the nature of the TBP.