# Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits

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

## Key facts

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

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

- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [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)
- [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)
- [Fixed-Confidence Guarantees for Bayesian Best-Arm Identification](https://mlsanity.com/paper/1910.10945/) (2019)
- [Best Arm Identification in Generalized Linear Bandits](https://mlsanity.com/paper/1905.08224/) (2019)
- [On Sequential Elimination Algorithms for Best-Arm Identification in Multi-Armed Bandits](https://mlsanity.com/paper/1609.02606/) (2016)
- [Towards Optimal and Efficient Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/1911.01695/) (2019)

## Built on by (most cited first, 30 of 32)

- [Efficient Prompt Optimization Through the Lens of Best Arm Identification](https://mlsanity.com/paper/2402.09723/) (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)
- [Best Arm Identification with Fixed Budget: A Large Deviation Perspective](https://mlsanity.com/paper/2312.12137/) (2023)
- [Active Learning for Direct Preference Optimization](https://mlsanity.com/paper/2503.01076/) (2025)
- [Automated Filtering of Human Feedback Data for Aligning Text-to-Image Diffusion Models](https://mlsanity.com/paper/2410.10166/) (2024)
- [Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Bandits](https://mlsanity.com/paper/2402.05878/) (2024)
- [Asymptotically Optimal Fixed-Budget Best Arm Identification with Variance-Dependent Bounds](https://mlsanity.com/paper/2302.02988/) (2023)
- [Optimal Best Arm Identification with Fixed Confidence in Restless Bandits](https://mlsanity.com/paper/2310.13393/) (2023)
- [Enhancing Preference-based Linear Bandits via Human Response Time](https://mlsanity.com/paper/2409.05798/) (2024)
- [Augmenting Online RL with Offline Data is All You Need: A Unified Hybrid RL Algorithm Design and Analysis](https://mlsanity.com/paper/2505.13768/) (2025)
- [A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationarity](https://mlsanity.com/paper/2307.15154/) (2023)
- [Adaptive Experimental Design for Policy Learning](https://mlsanity.com/paper/2401.03756/) (2024)
- [Fixed-Budget Differentially Private Best Arm Identification](https://mlsanity.com/paper/2401.09073/) (2024)
- [Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget](https://mlsanity.com/paper/2405.15090/) (2024)
- [Bandit Pareto Set Identification in a Multi-Output Linear Model](https://mlsanity.com/paper/2507.04255/) (2025)
- [Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit](https://mlsanity.com/paper/2310.15681/) (2023)
- [Fixed-Budget Best-Arm Identification in Sparse Linear Bandits](https://mlsanity.com/paper/2311.00481/) (2023)
- [Generalized Neyman Allocation for Locally Minimax Optimal Best-Arm Identification](https://mlsanity.com/paper/2405.19317/) (2024)
- [Identifying the Best Arm in the Presence of Global Environment Shifts](https://mlsanity.com/paper/2408.12581/) (2024)
- [Online Clustering of Data Sequences with Bandit Information](https://mlsanity.com/paper/2501.11421/) (2025)
- [Experimental Design for Semiparametric Bandits](https://mlsanity.com/paper/2506.13390/) (2025)
- [Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors](https://mlsanity.com/paper/2602.03972/) (2026)
- [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)
- [An Algorithm for Fixed Budget Best Arm Identification with Combinatorial Exploration](https://mlsanity.com/paper/2502.01429/) (2025)
- [Secure Best Arm Identification in the Presence of a Copycat](https://mlsanity.com/paper/2507.18975/) (2025)
- [Nearly Optimal Active Preference Learning and Its Application to LLM Alignment](https://mlsanity.com/paper/2602.01581/) (2026)
- [On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits](https://mlsanity.com/paper/2603.10346/) (2026)
- [Nearly Optimal Best Arm Identification for Semiparametric Bandits](https://mlsanity.com/paper/2604.03969/) (2026)

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