The Influence of Shape Constraints on the Thresholding Bandit Problem
This work addresses the problem of efficiently identifying arms above a threshold in bandit settings for researchers in sequential decision-making, providing theoretical insights but is incremental as it extends known constraints to TBP.
The paper tackles the stochastic Thresholding Bandit Problem (TBP) under shape constraints like monotonicity, unimodality, and concavity, deriving minimax regret rates that vary with the constraint, such as √(log(K)K/T) for vanilla TBP and √(log log K/T) for concave TBP.
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) $\sqrt{\log(K)K/T}$ for TBP, (ii) $\sqrt{\log(K)/T}$ for MTBP, (iii) $\sqrt{K/T}$ for UTBP and (iv) $\sqrt{\log\log 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.