# Fixed-Budget Best-Arm Identification in Sparse Linear Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 42 references that are in the map.
- First posted on arXiv 1 Nov 2023.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [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)
- [High-Dimensional Sparse Linear Bandits](https://mlsanity.com/paper/2011.04020/) (2020)
- [Doubly-Robust Lasso Bandit](https://mlsanity.com/paper/1907.11362/) (2019)
- [An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits](https://mlsanity.com/paper/2006.11685/) (2020)
- [Sparsity-Agnostic Lasso Bandit](https://mlsanity.com/paper/2007.08477/) (2020)
- [Fully adaptive algorithm for pure exploration in linear bandits](https://mlsanity.com/paper/1710.05552/) (2017)
- [Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/2105.13017/) (2021)
- [Fixed-Budget Best-Arm Identification in Structured Bandits](https://mlsanity.com/paper/2106.04763/) (2021)
- [A Simple Unified Framework for High Dimensional Bandit Problems](https://mlsanity.com/paper/2102.09626/) (2021)
- [PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits](https://mlsanity.com/paper/2210.15345/) (2022)
- [Thresholded Lasso Bandit](https://mlsanity.com/paper/2010.11994/) (2020)
- [Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2211.05964/) (2022)

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

- [Efficient Prompt Optimization Through the Lens of Best Arm Identification](https://mlsanity.com/paper/2402.09723/) (2024)

## Abstract (arXiv)

We study the best-arm identification problem in sparse linear bandits under the fixed-budget setting. In sparse linear bandits, the unknown feature vector θ^* may be of large dimension d, but only a few, say s ll d of these features have non-zero values. We design a two-phase algorithm, Lasso and Optimal-Design- (Lasso-OD) based linear best-arm identification. The first phase of Lasso-OD leverages the sparsity of the feature vector by applying the thresholded Lasso introduced by Zhou (2009), which estimates the support of θ^* correctly with high probability using rewards from the selected arms and a judicious choice of the design matrix. The second phase of Lasso-OD applies the OD-LinBAI algorithm by Yang and Tan (2022) on that estimated support. We derive a non-asymptotic upper bound on the error probability of Lasso-OD by carefully choosing hyperparameters (such as Lasso's regularization parameter) and balancing the error probabilities of both phases. For fixed sparsity s and budget T, the exponent in the error probability of Lasso-OD depends on s but not on the dimension d, yielding a significant performance improvement for sparse and high-dimensional linear bandits. Furthermore, we show that Lasso-OD is almost minimax optimal in the exponent. Finally, we provide numerical examples to demonstrate the significant performance improvement over the existing algorithms for non-sparse linear bandits such as OD-LinBAI, BayesGap, Peace, LinearExploration, and GSE.