Pure Exploration with Multiple Correct Answers

Understand

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.