Abstract
We study the minimax sample complexity of ε-best arm identification in linear bandits. Given a compact action set X that spans R^d and an unknown reward vector θ∈R^d, the goal is to output an arm x∈X such that x,θ ≥ max_x∈X x,θ - ε with probability at least 1-δ, using as few samples as possible. First, we present a non-adaptive fixed-design method with sample complexity O(dlog(1/δ)/ε²+w(X)²/ε²), where w(X) is a Gaussian width term dependent on X, and we prove a matching lower bound Ω(dlog(1/δ)/ε²+w(X)²/ε²) 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 ℓ₂ 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 ℓ₂-norm estimation subroutine: we design an adaptive algorithm that uses O(dlog(1/δ)/ε²) samples from the unit ℓ₂ ball in R^d and outputs an estimate r satisfying | r-θ₂|≤ ε with probability at least 1-δ, where θ is the unknown reward vector.