mlsanityData to 7 Oct 2026

Optimal Best-arm Identification in Linear Bandits

arXiv 2006.16073 ↗First posted 29 Jun 2020stat.ML cs.LGcited by 70

Not on the map. Why?

Abstract (arXiv)

We study the problem of best-arm identification with fixed confidence in stochastic linear bandits. The objective is to identify the best arm with a given level of certainty while minimizing the sampling budget. We devise a simple algorithm whose sampling complexity matches known instance-specific lower bounds, asymptotically almost surely and in expectation. The algorithm relies on an arm sampling rule that tracks an optimal proportion of arm draws, and that remarkably can be updated as rarely as we wish, without compromising its theoretical guarantees. Moreover, unlike existing best-arm identification strategies, our algorithm uses a stopping rule that does not depend on the number of arms. Experimental results suggest that our algorithm significantly outperforms existing algorithms. The paper further provides a first analysis of the best-arm identification problem in linear bandits with a continuous set of arms.

Key facts. Cited by 70 papers in the map (data through 7 Oct 2026). First posted on arXiv 29 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 10; 2023: 17; 2024: 7; 2025: 15; 2026: 13.

70 papers.

Sort:

By area:

  1. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  2. 2024Efficient Prompt Optimization Through the Lens of Best Arm Identificationcited by 35
  3. 2021Minimax Optimal Fixed-Budget Best Arm Identification in Linear Banditscited by 32
  4. 2023Active learning for data streams: a surveycited by 29
  5. 2021Fixed-Budget Best-Arm Identification in Structured Banditscited by 22
  6. 2021Design of Experiments for Stochastic Contextual Linear Banditscited by 18
  7. 2022Optimal Clustering with Bandit Feedbackcited by 15
  8. 2022Information-Directed Selection for Top-Two Algorithmscited by 15
  9. 2025Sequential Learning of the Pareto Front for Multi-objective Banditscited by 13
  10. 2025Sample Efficient Demonstration Selection for In-Context Learningcited by 12
  11. 2021Dealing With Misspecification In Fixed-Confidence Linear Top-m Identificationcited by 11
  12. 2022Variance-Aware Sparse Linear Banditscited by 11
38 more
  1. 2023Pure Exploration in Bandits with Linear Constraintscited by 10
  2. 2021The Role of Contextual Information in Best Arm Identificationcited by 8
  3. 2021Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffscited by 8
  4. 2022On Elimination Strategies for Bandit Fixed-Confidence Identificationcited by 8
  5. 2023Towards Instance-Optimality in Online PAC Reinforcement Learningcited by 7
  6. 2024Optimal Batched Linear Banditscited by 7
  7. 2022On the complexity of All varepsilon-Best Arms Identificationcited by 6
  8. 2022Contextual Bandits in a Survey Experiment on Charitable Giving: Within-Experiment Outcomes versus Policy Learningcited by 6
  9. 2023Multi-task Representation Learning for Pure Exploration in Linear Banditscited by 6
  10. 2023Pure Exploration in Asynchronous Federated Banditscited by 6
  11. 2024Best-Arm Identification in Unimodal Banditscited by 6
  12. 2024Experiment Planning with Function Approximationcited by 5
  13. 2025Adaptive Exploration for Multi-Reward Multi-Policy Evaluationcited by 5
  14. 2022Best Policy Identification in Linear MDPscited by 4
  15. 2023Price of Safety in Linear Best Arm Identificationcited by 4
  16. 2023Thompson Exploration with Best Challenger Rule in Best Arm Identificationcited by 4
  17. 2022SPRT-based Efficient Best Arm Identification in Stochastic Banditscited by 3
  18. 2023Certified Multi-Fidelity Zeroth-Order Optimizationcited by 3
  19. 2023Optimal Exploration is no harder than Thompson Samplingcited by 3
  20. 2023Data-driven optimal stopping: A pure exploration analysiscited by 3
  21. 2024Preference-based Pure Explorationcited by 3
  22. 2025Pure Exploration with Feedback Graphscited by 3
  23. 2025Augmenting Online RL with Offline Data is All You Need: A Unified Hybrid RL Algorithm Design and Analysiscited by 3
  24. 2023Best Arm Identification in Stochastic Bandits: Beyond β-optimalitycited by 2
  25. 2023Best Arm Identification in Bandits with Limited Precision Samplingcited by 2
  26. 2023A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationaritycited by 2
  27. 2024Near Optimal Pure Exploration in Logistic Banditscited by 2
  28. 2025Bandit Pareto Set Identification in a Multi-Output Linear Modelcited by 2
  29. 2021Pure Exploration with Structured Preference Feedbackcited by 1
  30. 2022Choosing Answers in varepsilon-Best-Answer Identification for Linear Banditscited by 1
  31. 2023Pure Exploration under Mediators' Feedbackcited by 1
  32. 2023Fixed-Budget Best-Arm Identification in Sparse Linear Banditscited by 1
  33. 2025Online Clustering of Data Sequences with Bandit Informationcited by 1
  34. 2025Variance-Optimal Arm Selection: Misallocation Minimization and Best Arm Identificationcited by 1
  35. 2025Policy Testing in Markov Decision Processescited by 1
  36. 2025Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budgetcited by 1
  37. 2025Experimental Design for Semiparametric Banditscited by 1
  38. 2026Anytime-valid Optimal Policy Identificationcited by 1

50 most cited of 70 All 70 (JSON)