mlsanityData to 7 Oct 2026

Pure Exploration with Multiple Correct Answers

arXiv 1902.03475 ↗First posted 9 Feb 2019cs.LG stat.MLcited by 60

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 60 papers in the map (data through 7 Oct 2026). First posted on arXiv 9 Feb 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 9; 2023: 9; 2024: 9; 2025: 16; 2026: 9.

60 papers.

Sort:

By area:

  1. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  2. 2022Top Two Algorithms Revisitedcited by 34
  3. 2022Revisiting Simple Regret: Fast Rates for Returning a Good Armcited by 25
  4. 2021Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedbackcited by 19
  5. 2023On the Existence of a Complexity in Fixed Budget Bandit Identificationcited by 19
  6. 2021A/B/n Testing with Control in the Presence of Subpopulationscited by 17
  7. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
  8. 2022Information-Directed Selection for Top-Two Algorithmscited by 15
  9. 2023Adaptive Algorithms for Relaxed Pareto Set Identificationcited by 13
  10. 2023Best Arm Identification with Fixed Budget: A Large Deviation Perspectivecited by 12
  11. 2021Top-m identification for linear banditscited by 11
  12. 2021Dealing With Misspecification In Fixed-Confidence Linear Top-m Identificationcited by 11
38 more
  1. 2022On Elimination Strategies for Bandit Fixed-Confidence Identificationcited by 8
  2. 2023Best Arm Identification with Fairness Constraints on Subpopulationscited by 8
  3. 2024Optimal Multi-Fidelity Best-Arm Identificationcited by 8
  4. 2021A Non-asymptotic Approach to Best-Arm Identification for Gaussian Banditscited by 7
  5. 2023Towards Instance-Optimality in Online PAC Reinforcement Learningcited by 7
  6. 2024Query-Efficient Correlation Clustering with Noisy Oraclecited by 7
  7. 2023An Anytime Algorithm for Good Arm Identificationcited by 6
  8. 2024Best-Arm Identification in Unimodal Banditscited by 6
  9. 2024Reward Maximization for Pure Exploration: Minimax Optimal Good Arm Identification for Nonparametric Multi-Armed Banditscited by 5
  10. 2021Near Instance Optimal Model Selection for Pure Exploration Linear Banditscited by 4
  11. 2021Online Sign Identification: Minimization of the Number of Errors in Thresholding Banditscited by 3
  12. 2022Measurement-based Admission Control in Sliced Networks: A Best Arm Identification Approachcited by 3
  13. 2023Optimal Best Arm Identification with Fixed Confidence in Restless Banditscited by 3
  14. 2024Testing the Feasibility of Linear Programs with Bandit Feedbackcited by 3
  15. 2024Preference-based Pure Explorationcited by 3
  16. 2025Pure Exploration with Feedback Graphscited by 3
  17. 2025Towards Regulatory-Confirmed Adaptive Clinical Trials: Machine Learning Opportunities and Solutionscited by 3
  18. 2022Adaptive Identification of Populations with Treatment Benefit in Clinical Trials: Machine Learning Challenges and Solutionscited by 2
  19. 2024Representative Arm Identification: A fixed confidence approach to identify cluster representativescited by 2
  20. 2025The Batch Complexity of Bandit Pure Explorationcited by 2
  21. 2025Optimal Best-Arm Identification under Fixed Confidence with Multiple Optimacited by 2
  22. 2025Best Group Identification in Multi-Objective Banditscited by 2
  23. 2025Constrained Pareto Set Identification with Bandit Feedbackcited by 2
  24. 2025FraPPE: Fast and Efficient Preference-based Pure Explorationcited by 2
  25. 2026On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularizationcited by 2
  26. 2022Choosing Answers in varepsilon-Best-Answer Identification for Linear Banditscited by 1
  27. 2023Pure Exploration under Mediators' Feedbackcited by 1
  28. 2025Policy Testing in Markov Decision Processescited by 1
  29. 2025Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validationcited by 1
  30. 2025Near Optimal Non-asymptotic Sample Complexity of 1-Identificationcited by 1
  31. 2025Fixed-Confidence Multiple Change Point Identification under Bandit Feedbackcited by 1
  32. 2025Pure Exploration via Frank-Wolfe Self-Playcited by 1
  33. 2025Constrained Best Arm Identification with Tests for Feasibilitycited by 1
  34. 2022Gaussian Process Classification Banditscited by 0
  35. 2023An Asymptotically Optimal Algorithm for the Convex Hull Membership Problemcited by 0
  36. 2024Optimal Thresholding Linear Banditcited by 0
  37. 2024Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraintscited by 0
  38. 2025Near Optimal Best Arm Identification for Clustered Banditscited by 0

50 most cited of 60 All 60 (JSON)