Pure Exploration with Multiple Correct Answers

Abstract

We determine the sample complexity of pure exploration bandit problems with multiple good answers. We derive a lower bound using a new game equilibrium argument. We show how continuity and convexity properties of single-answer problems ensures that the Track-and-Stop algorithm has asymptotically optimal sample complexity. However, that convexity is lost when going to the multiple-answer setting. We present a new algorithm which extends Track-and-Stop to the multiple-answer case and has asymptotic sample complexity matching the lower bound.

References in corpus (5)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
• Minimal Exploration in Structured Stochastic Bandits
• An optimal algorithm for the Thresholding Bandit Problem
• Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling

Cited by in corpus (8)

• Gradient Ascent for Active Exploration in Bandit Problems
• Optimal Best-Arm Identification Methods for Tail-Risk Measures
• The True Sample Complexity of Identifying Good Arms
• Non-Asymptotic Pure Exploration by Solving Games
• Dealing with Unknown Variances in Best-Arm Identification
• Chernoff Sampling for Active Testing and Extension to Active Regression
• Stochastic Bandits with Vector Losses: Minimizing ${\ell }^{\infty }$-Norm of Relative Losses
• Near Instance Optimal Model Selection for Pure Exploration Linear Bandits