Pure Exploration with Multiple Correct Answers

2019/02/09 by Rémy Degenne, Degenne, Rémy, Wouter M. Koolen +1 · 7 citations
Decision Sciences · Computer Science · #Advanced Bandit Algorithms Research #Machine Learning and Algorithms #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.1902.03475

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.

Citations

• Bergeʼs maximum theorem for noncompact image sets
• Minimal Exploration in Structured Stochastic Bandits

Cited by

• Chernoff Sampling for Active Testing and Extension to Active Regression
• Constrained Best Arm Identification with Tests for Feasibility
• Dealing with Unknown Variances in Best-Arm Identification
• The True Sample Complexity of Identifying Good Arms
• Pure Exploration via Frank-Wolfe Self-Play
• Optimal Algorithms for Bandit Learning in Matching Markets
• FraPPE: Fast and Efficient Preference-based Pure Exploration

Related

• Pure Exploration with Infinite Answers
• Non-Asymptotic Pure Exploration by Solving Games
• Non-Asymptotic Analysis of (Sticky) Track-and-Stop
• Double Explore-then-Commit: Asymptotic Optimality and Beyond
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit