mlsanityData to 7 Oct 2026

Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits

arXiv 2105.13017 ↗First posted 27 May 2021cs.LG cs.IT math.ITcited by 32

Not on the map. Why?

Abstract (arXiv)

We study the problem of best arm identification in linear bandits in the fixed-budget setting. By leveraging properties of the G-optimal design and incorporating it into the arm allocation rule, we design a parameter-free algorithm, Optimal Design-based Linear Best Arm Identification (OD-LinBAI). We provide a theoretical analysis of the failure probability of OD-LinBAI. Instead of all the optimality gaps, the performance of OD-LinBAI depends only on the gaps of the top d arms, where d is the effective dimension of the linear bandit instance. Complementarily, we present a minimax lower bound for this problem. The upper and lower bounds show that OD-LinBAI is minimax optimal up to constant multiplicative factors in the exponent, which is a significant theoretical improvement over existing methods (e.g., BayesGap, Peace, LinearExploration and GSE), and settles the question of ascertaining the difficulty of learning the best arm in the fixed-budget setting. Finally, numerical experiments demonstrate considerable empirical improvements over existing algorithms on a variety of real and synthetic datasets.

Key facts. Cited by 32 papers in the map (data through 7 Oct 2026). Builds on 14 of its 50 references that are in the map. First posted on arXiv 27 May 2021.

Builds on

14 of 50 references.

References · 14

  1. 2016Optimal Best Arm Identification with Fixed Confidencecited by 233
  2. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  3. 2016Simple Bayesian Algorithms for Best Arm Identificationcited by 116
  4. 2014Best-Arm Identification in Linear Banditscited by 98
  5. 2019Sequential Experimental Design for Transductive Linear Banditscited by 88
  6. 2016Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problemcited by 79
  7. 2020Optimal Best-arm Identification in Linear Banditscited by 70
  8. 2020Gamification of Pure Exploration for Linear Banditscited by 61
  9. 2020An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Banditscited by 45
  10. 2017Fully adaptive algorithm for pure exploration in linear banditscited by 43
  11. 2019Fixed-Confidence Guarantees for Bayesian Best-Arm Identificationcited by 38
  12. 2019Best Arm Identification in Generalized Linear Banditscited by 18
2 more
  1. 2016On Sequential Elimination Algorithms for Best-Arm Identification in Multi-Armed Banditscited by 12
  2. 2019Towards Optimal and Efficient Best Arm Identification in Linear Banditscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 7; 2024: 12; 2025: 7; 2026: 6.

32 papers.

Sort:

By area:

  1. 2024Efficient Prompt Optimization Through the Lens of Best Arm Identificationcited by 35
  2. 2023On the Existence of a Complexity in Fixed Budget Bandit Identificationcited by 19
  3. 2024Optimal Design for Human Preference Elicitationcited by 17
  4. 2023Best Arm Identification with Fixed Budget: A Large Deviation Perspectivecited by 12
  5. 2025Active Learning for Direct Preference Optimizationcited by 9
  6. 2024Automated Filtering of Human Feedback Data for Aligning Text-to-Image Diffusion Modelscited by 5
  7. 2024Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Banditscited by 4
  8. 2023Asymptotically Optimal Fixed-Budget Best Arm Identification with Variance-Dependent Boundscited by 3
  9. 2023Optimal Best Arm Identification with Fixed Confidence in Restless Banditscited by 3
  10. 2024Enhancing Preference-based Linear Bandits via Human Response Timecited by 3
  11. 2025Augmenting Online RL with Offline Data is All You Need: A Unified Hybrid RL Algorithm Design and Analysiscited by 3
  12. 2023A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationaritycited by 2
20 more
  1. 2024Fixed-Budget Differentially Private Best Arm Identificationcited by 2
  2. 2024Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budgetcited by 2
  3. 2025Bandit Pareto Set Identification in a Multi-Output Linear Modelcited by 2
  4. 2023Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Banditcited by 1
  5. 2023Fixed-Budget Best-Arm Identification in Sparse Linear Banditscited by 1
  6. 2024Adaptive Experimental Design for Policy Learningcited by 1
  7. 2024Generalized Neyman Allocation for Locally Minimax Optimal Best-Arm Identificationcited by 1
  8. 2024Identifying the Best Arm in the Presence of Global Environment Shiftscited by 1
  9. 2025Online Clustering of Data Sequences with Bandit Informationcited by 1
  10. 2025Experimental Design for Semiparametric Banditscited by 1
  11. 2024Experimental Design for Active Transductive Inference in Large Language Modelscited by 0
  12. 2024Multi-Agent Best Arm Identification in Stochastic Linear Banditscited by 0
  13. 2025An Algorithm for Fixed Budget Best Arm Identification with Combinatorial Explorationcited by 0
  14. 2025Secure Best Arm Identification in the Presence of a Copycatcited by 0
  15. 2026Nearly Optimal Active Preference Learning and Its Application to LLM Alignmentcited by 0
  16. 2026Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factorscited by 0
  17. 2026On The Complexity of Best-Arm Identification in Non-Stationary Linear Banditscited by 0
  18. 2026Nearly Optimal Best Arm Identification for Semiparametric Banditscited by 0
  19. 2026Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identificationcited by 0
  20. 2026MESHA: Mechanism-Enforced Sequential Halving for Strategic Linear Banditscited by 0