# Fixed-Budget Best-Arm Identification in Structured Bandits

arXiv: https://arxiv.org/abs/2106.04763 · HTML: https://mlsanity.com/paper/2106.04763/

## Key facts

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

## Builds on (most cited first, 13 of 13)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling](https://mlsanity.com/paper/1802.09127/) (2018)
- [Provable Meta-Learning of Linear Representations](https://mlsanity.com/paper/2002.11684/) (2020)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [Randomized Exploration in Generalized Linear Bandits](https://mlsanity.com/paper/1906.08947/) (2019)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits](https://mlsanity.com/paper/2006.11685/) (2020)
- [Fully adaptive algorithm for pure exploration in linear bandits](https://mlsanity.com/paper/1710.05552/) (2017)
- [Artificial Intelligence and Statistics](https://mlsanity.com/paper/1712.03779/) (2017)
- [Fast Rates for Bandit Optimization with Upper-Confidence Frank-Wolfe](https://mlsanity.com/paper/1702.06917/) (2017)

## Built on by (most cited first, 22 of 22)

- [Efficient multi-prompt evaluation of LLMs](https://mlsanity.com/paper/2405.17202/) (2024)
- [Efficient Prompt Optimization Through the Lens of Best Arm Identification](https://mlsanity.com/paper/2402.09723/) (2024)
- [Active learning for data streams: a survey](https://mlsanity.com/paper/2302.08893/) (2023)
- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [On the Existence of a Complexity in Fixed Budget Bandit Identification](https://mlsanity.com/paper/2303.09468/) (2023)
- [Optimal Design for Human Preference Elicitation](https://mlsanity.com/paper/2404.13895/) (2024)
- [Bayesian Fixed-Budget Best-Arm Identification](https://mlsanity.com/paper/2211.08572/) (2022)
- [Best Arm Identification with Fixed Budget: A Large Deviation Perspective](https://mlsanity.com/paper/2312.12137/) (2023)
- [Meta-Learning for Simple Regret Minimization](https://mlsanity.com/paper/2202.12888/) (2022)
- [Hyperband-based Bayesian Optimization for Black-box Prompt Selection](https://mlsanity.com/paper/2412.07820/) (2024)
- [Active Learning for Direct Preference Optimization](https://mlsanity.com/paper/2503.01076/) (2025)
- [Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Bandits](https://mlsanity.com/paper/2402.05878/) (2024)
- [Enhancing Preference-based Linear Bandits via Human Response Time](https://mlsanity.com/paper/2409.05798/) (2024)
- [A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationarity](https://mlsanity.com/paper/2307.15154/) (2023)
- [Fixed-Budget Differentially Private Best Arm Identification](https://mlsanity.com/paper/2401.09073/) (2024)
- [Bandit Pareto Set Identification in a Multi-Output Linear Model](https://mlsanity.com/paper/2507.04255/) (2025)
- [Fixed-Budget Best-Arm Identification in Sparse Linear Bandits](https://mlsanity.com/paper/2311.00481/) (2023)
- [Identifying the Best Arm in the Presence of Global Environment Shifts](https://mlsanity.com/paper/2408.12581/) (2024)
- [Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget](https://mlsanity.com/paper/2506.02386/) (2025)
- [Experimental Design for Active Transductive Inference in Large Language Models](https://mlsanity.com/paper/2404.08846/) (2024)
- [Multi-Agent Best Arm Identification in Stochastic Linear Bandits](https://mlsanity.com/paper/2411.13690/) (2024)
- [On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits](https://mlsanity.com/paper/2603.10346/) (2026)

## 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.