mlsanityData to 14 Oct 2026

Best-Arm Identification in Linear Bandits

arXiv 1409.6110 ↗First posted 22 Sep 2014cs.LGcited by 100

Not on the map. Why?

Abstract (arXiv)

We study the best-arm identification problem in linear bandit, where the rewards of the arms depend linearly on an unknown parameter θ^* and the objective is to return the arm with the largest reward. We characterize the complexity of the problem and introduce sample allocation strategies that pull arms to identify the best arm with a fixed confidence, while minimizing the sample budget. In particular, we show the importance of exploiting the global linear structure to improve the estimate of the reward of near-optimal arms. We analyze the proposed strategies and compare their empirical performance. Finally, as a by-product of our analysis, we point out the connection to the G-optimality criterion used in optimal experimental design.

Key facts. Cited by 100 papers in the map (data through 14 Oct 2026). First posted on arXiv 22 Sep 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 22; 2022: 17; 2023: 18; 2024: 14; 2025: 13; 2026: 16.

100 papers.

Sort:

By area:

  1. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisonscited by 247
  2. 2021High-Dimensional Experimental Design and Kernel Banditscited by 56
  3. 2024Efficient Prompt Optimization Through the Lens of Best Arm Identificationcited by 37
  4. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  5. 2022Contextual Bandits with Large Action Spaces: Made Practicalcited by 33
  6. 2021Minimax Optimal Fixed-Budget Best Arm Identification in Linear Banditscited by 32
  7. 2023Active learning for data streams: a surveycited by 29
  8. 2023On the Sublinear Regret of GP-UCBcited by 26
  9. 2021Best Arm Identification with Safety Constraintscited by 25
  10. 2022Revisiting Simple Regret: Fast Rates for Returning a Good Armcited by 25
  11. 2024Optimal Design for Reward Modeling in RLHFcited by 25
  12. 2021Fixed-Budget Best-Arm Identification in Structured Banditscited by 22
38 more
  1. 2021Design of Experiments for Stochastic Contextual Linear Banditscited by 18
  2. 2021Nearly Optimal Algorithms for Level Set Estimationcited by 17
  3. 2022PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Banditscited by 17
  4. 2024Optimal Design for Human Preference Elicitationcited by 17
  5. 2022Active Learning with Safety Constraintscited by 16
  6. 2022Instance-optimal PAC Algorithms for Contextual Banditscited by 16
  7. 2021Improved Algorithms for Agnostic Pool-based Active Classificationcited by 15
  8. 2022Optimal Clustering with Bandit Feedbackcited by 15
  9. 2021Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximationcited by 14
  10. 2021Pure Exploration in Kernel and Neural Banditscited by 13
  11. 2021Collaborative Pure Exploration in Kernel Banditcited by 13
  12. 2022Bayesian Fixed-Budget Best-Arm Identificationcited by 13
  13. 2021Dealing With Misspecification In Fixed-Confidence Linear Top-m Identificationcited by 12
  14. 2021Top-m identification for linear banditscited by 11
  15. 2022Variance-Aware Sparse Linear Banditscited by 11
  16. 2022Interactively Learning Preference Constraints in Linear Banditscited by 11
  17. 2023Additive Causal Bandits with Unknown Graphcited by 10
  18. 2024Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Banditscited by 10
  19. 2021A Map of Bandits for E-commercecited by 9
  20. 2022Exploration in Linear Bandits with Rich Action Sets and its Implications for Inferencecited by 9
  21. 2021The Role of Contextual Information in Best Arm Identificationcited by 8
  22. 2021Best-Arm Identification in Correlated Multi-Armed Banditscited by 8
  23. 2021Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffscited by 8
  24. 2022On Elimination Strategies for Bandit Fixed-Confidence Identificationcited by 8
  25. 2021Diffusion Approximations for a Class of Sequential Testing Problemscited by 7
  26. 2022Contextual Bandits in a Survey Experiment on Charitable Giving: Within-Experiment Outcomes versus Policy Learningcited by 7
  27. 2022Near-optimal Policy Identification in Active Reinforcement Learningcited by 7
  28. 2024Transition Constrained Bayesian Optimization via Markov Decision Processescited by 7
  29. 2021Selective Sampling for Online Best-arm Identificationcited by 6
  30. 2023Multi-task Representation Learning for Pure Exploration in Linear Banditscited by 6
  31. 2023Fixed-Budget Best-Arm Identification with Heterogeneous Reward Variancescited by 6
  32. 2023On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidencecited by 6
  33. 2023Pure Exploration in Asynchronous Federated Banditscited by 6
  34. 2021Maximizing and Satisficing in Multi-armed Bandits with Graph Informationcited by 5
  35. 2023Learning the Pareto Front Using Bootstrapped Observation Samplescited by 5
  36. 2023Multi-task Representation Learning for Pure Exploration in Bilinear Banditscited by 5
  37. 2024Experiment Planning with Function Approximationcited by 5
  38. 2024Preference-based Pure Explorationcited by 5

50 most cited of 100 All 100 (JSON)