Thresholding Bandit with Optimal Aggregate Regret

2019/05/27 by Tao Chao, Saúl A. Blanco, Tao, Chao +5 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1905.11046

openalex publication_date 2019/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the thresholding bandit problem, whose goal is to find arms of mean rewards above a given threshold θ, with a fixed budget of T trials. We introduce LSA, a new, simple and anytime algorithm that aims to minimize the aggregate regret (or the expected number of mis-classified arms). We prove that our algorithm is instance-wise asymptotically optimal. We also provide comprehensive empirical results to demonstrate the algorithm's superior performance over existing algorithms under a variety of different scenarios.

Cited by

• Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation

Related

• Sparse Stochastic Bandits
• Threshold-Based Optimal Arm Selection in Monotonic Bandits: Regret Lower Bounds and Algorithms
• Regret Minimization in Heavy-Tailed Bandits
• Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits\n with Super Heavy-Tailed Payoffs
• An optimal algorithm for the Thresholding Bandit Problem