The Influence of Shape Constraints on the Thresholding Bandit Problem

Abstract

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 $({\mu }_k{)}_k$ is monotonically increasing MTBP, (iii) the case where $({\mu }_k{)}_k$ is unimodal UTBP and (iv) the case where $({\mu }_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.

References in corpus (14)

• Optimal Best Arm Identification with Fixed Confidence
• Combinatorial Multi-Armed Bandit with General Reward Functions
• An optimal algorithm for the Thresholding Bandit Problem
• Stochastic Zeroth-order Optimization in High Dimensions
• Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms
• Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
• On Zeroth-Order Stochastic Convex Optimization via Random Walks
• Thresholding Bandits with Augmented UCB
• Unimodal Bandits without Smoothness
• Thresholding Bandit for Dose-ranging: The Impact of Monotonicity
• The Geometry of Generalized Binary Search
• Asynchronous Parallel Empirical Variance Guided Algorithms for the Thresholding Bandit Problem
• Thresholding Bandit Problem with Both Duels and Pulls
• Adaptive Sampling for Convex Regression