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

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.