# On the Power of Adaptivity for varepsilon-Best Arm Identification in Linear Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 31 references that are in the map.
- First posted on arXiv 15 May 2026.

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

- [Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversaries](https://mlsanity.com/paper/2504.00461/) (2025)
- [On the Universal Near Optimality of Hedge in Combinatorial Settings](https://mlsanity.com/paper/2510.17099/) (2025)

## Abstract (arXiv)

We study the minimax sample complexity of varepsilon-best arm identification in linear bandits. Given a compact action set X that spans ℝd and an unknown reward vector θ∈ℝd, the goal is to output an arm widehatx∈X such that langle widehatx,θrangle ≥ maxx∈X langle x,θrangle - varepsilon with probability at least 1-δ, using as few samples as possible. First, we present a non-adaptive fixed-design method with sample complexity O!left(fracdlog(1/δ)varepsilon2+fracw(X)2varepsilon2right), where w(X) is a Gaussian width term dependent on X, and we prove a matching lower bound Omega!left(fracdlog(1/δ)varepsilon2+fracw(X)2varepsilon2right) for all non-adaptive fixed-design methods. We then turn to adaptive sampling. We raise an important structural question: beyond the canonical basis, are there structured action sets for which adaptivity yields only logarithmic-factor improvements over the optimal non-adaptive rate? We answer in the affirmative for several natural action sets, namely the hypercube, the ℓ2 ball, m-sets, and multi-task multi-armed bandits. Finally, we provide the first construction of an action set X for which adaptivity yields a polynomial-factor improvement over every non-adaptive algorithm. A key ingredient behind this separation is an ℓ2-norm estimation subroutine: we design an adaptive algorithm that uses O!left(fracdlog(1/δ)varepsilon2right) samples from the unit ℓ2 ball in ℝd and outputs an estimate widehat r satisfying |widehat r-|θ|2|≤ varepsilon with probability at least 1-δ, where θ is the unknown reward vector.