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

preprint2026arXivOpen access

Abstract

We study the minimax sample complexity of ε\varepsilon-best arm identification in linear bandits. Given a compact action set X\mathcal{X} that spans Rd\mathbb{R}^d and an unknown reward vector θ∈Rdθ\in\mathbb{R}^d, the goal is to output an arm x^∈X\widehat{x}\in\mathcal{X} such that ⟨x^,θ⟩≥max⁡x∈X⟨x,θ⟩−ε\langle \widehat{x},θ\rangle \ge \max_{x\in\mathcal{X}} \langle x,θ\rangle - \varepsilon with probability at least 1−δ1-δ, using as few samples as possible. First, we present a non-adaptive fixed-design method with sample complexity O ⁣(dlog⁡(1/δ)ε2+w(X)2ε2)\mathcal{O}\!\left(\frac{d\log(1/δ)}{\varepsilon^2}+\frac{w(\mathcal{X})^2}{\varepsilon^2}\right), where w(X)w(\mathcal{X}) is a Gaussian width term dependent on X\mathcal{X}, and we prove a matching lower bound Ω ⁣(dlog⁡(1/δ)ε2+w(X)2ε2)Ω\!\left(\frac{d\log(1/δ)}{\varepsilon^2}+\frac{w(\mathcal{X})^2}{\varepsilon^2}\right) 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\ell_2 ball, mm-sets, and multi-task multi-armed bandits. Finally, we provide the first construction of an action set X\mathcal{X} for which adaptivity yields a polynomial-factor improvement over every non-adaptive algorithm. A key ingredient behind this separation is an ℓ2\ell_2-norm estimation subroutine: we design an adaptive algorithm that uses O ⁣(dlog⁡(1/δ)ε2)\mathcal{O}\!\left(\frac{d\log(1/δ)}{\varepsilon^2}\right) samples from the unit ℓ2\ell_2 ball in Rd\mathbb{R}^d and outputs an estimate r^\widehat r satisfying ∣r^−∥θ∥2∣≤ε|\widehat r-\|θ\|_2|\le \varepsilon with probability at least 1−δ1-δ, where θθ is the unknown reward vector.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.