An optimal algorithm for the Thresholding Bandit Problem
arXiv:1605.08671
Abstract
We study a specific \textit{combinatorial pure exploration stochastic bandit problem} where the learner aims at finding the set of arms whose means are above a given threshold, up to a given precision, and \textit{for a fixed time horizon}. We propose a parameter-free algorithm based on an original heuristic, and prove that it is optimal for this problem by deriving matching upper and lower bounds. To the best of our knowledge, this is the first non-trivial pure exploration setting with \textit{fixed budget} for which optimal strategies are constructed.
ICML 2016
References in corpus (2)
Cited by in corpus (22)
- On Multi-Armed Bandit Designs for Dose-Finding Clinical Trials
- Thresholding Bandits with Augmented UCB
- Pure Exploration with Multiple Correct Answers
- A Bandit Approach to Multiple Testing with False Discovery Control
- Beyond the Click-Through Rate: Web Link Selection with Multi-level Feedback
- Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration
- Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits
- Finding All ε-Good Arms in Stochastic Bandits
- Adaptive Monte Carlo Multiple Testing via Multi-Armed Bandits
- Asynchronous Parallel Empirical Variance Guided Algorithms for the Thresholding Bandit Problem
- Weighted Empirical Risk Minimization: Sample Selection Bias Correction based on Importance Sampling
- Best Arm Identification with Safety Constraints
- Thresholding Bandit Problem with Both Duels and Pulls
- The Influence of Shape Constraints on the Thresholding Bandit Problem
- Continuous Mean-Covariance Bandits
- Combinatorial Pure Exploration with Bottleneck Reward Function
- A PAC algorithm in relative precision for bandit problem with costly sampling
- Anomaly Detection in Hierarchical Data Streams under Unknown Models
- Thresholding Graph Bandits with GrAPL
- Lexicographic Multiarmed Bandit
- Adaptive Double-Exploration Tradeoff for Outlier Detection
- Maillard Sampling: Boltzmann Exploration Done Optimally