mlsanityData to 7 Oct 2026

Fixed-Budget Best-Arm Identification in Structured Bandits

arXiv 2106.04763 ↗First posted 9 Jun 2021cs.LGcited by 22

Not on the map. Why?

Abstract (arXiv)

Best-arm identification (BAI) in a fixed-budget setting is a bandit problem where the learning agent maximizes the probability of identifying the optimal (best) arm after a fixed number of observations. Most works on this topic study unstructured problems with a small number of arms, which limits their applicability. We propose a general tractable algorithm that incorporates the structure, by successively eliminating suboptimal arms based on their mean reward estimates from a joint generalization model. We analyze our algorithm in linear and generalized linear models (GLMs), and propose a practical implementation based on a G-optimal design. In linear models, our algorithm has competitive error guarantees to prior works and performs at least as well empirically. In GLMs, this is the first practical algorithm with analysis for fixed-budget BAI.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). Builds on 13 of its 56 references that are in the map. First posted on arXiv 9 Jun 2021.

Builds on

13 of 56 references.

References · 13

  1. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 280
  2. 2018Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Samplingcited by 166
  3. 2020Provable Meta-Learning of Linear Representationscited by 161
  4. 2014Best-Arm Identification in Linear Banditscited by 98
  5. 2016Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problemcited by 79
  6. 2019Randomized Exploration in Generalized Linear Banditscited by 70
  7. 2020Optimal Best-arm Identification in Linear Banditscited by 70
  8. 2019Non-Asymptotic Pure Exploration by Solving Gamescited by 62
  9. 2020Gamification of Pure Exploration for Linear Banditscited by 61
  10. 2020An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Banditscited by 45
  11. 2017Fully adaptive algorithm for pure exploration in linear banditscited by 43
  12. 2017Artificial Intelligence and Statisticscited by 43
1 more
  1. 2017Fast Rates for Bandit Optimization with Upper-Confidence Frank-Wolfecited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 5; 2024: 11; 2025: 3; 2026: 1.

22 papers.

Sort:

By area:

  1. 2024Efficient multi-prompt evaluation of LLMscited by 72
  2. 2024Efficient Prompt Optimization Through the Lens of Best Arm Identificationcited by 35
  3. 2023Active learning for data streams: a surveycited by 29
  4. 2024A Unified Confidence Sequence for Generalized Linear Models, with Applications to Banditscited by 27
  5. 2023On the Existence of a Complexity in Fixed Budget Bandit Identificationcited by 19
  6. 2024Optimal Design for Human Preference Elicitationcited by 17
  7. 2022Bayesian Fixed-Budget Best-Arm Identificationcited by 12
  8. 2023Best Arm Identification with Fixed Budget: A Large Deviation Perspectivecited by 12
  9. 2022Meta-Learning for Simple Regret Minimizationcited by 10
  10. 2024Hyperband-based Bayesian Optimization for Black-box Prompt Selectioncited by 9
  11. 2025Active Learning for Direct Preference Optimizationcited by 9
  12. 2024Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Banditscited by 4
10 more
  1. 2024Enhancing Preference-based Linear Bandits via Human Response Timecited by 3
  2. 2023A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationaritycited by 2
  3. 2024Fixed-Budget Differentially Private Best Arm Identificationcited by 2
  4. 2025Bandit Pareto Set Identification in a Multi-Output Linear Modelcited by 2
  5. 2023Fixed-Budget Best-Arm Identification in Sparse Linear Banditscited by 1
  6. 2024Identifying the Best Arm in the Presence of Global Environment Shiftscited by 1
  7. 2025Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budgetcited by 1
  8. 2024Experimental Design for Active Transductive Inference in Large Language Modelscited by 0
  9. 2024Multi-Agent Best Arm Identification in Stochastic Linear Banditscited by 0
  10. 2026On The Complexity of Best-Arm Identification in Non-Stationary Linear Banditscited by 0