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

arXiv:2605.15663v1 Announce Type: new Abstract: We study the minimax sample complexity of arepsilon-best arm identification in linear bandits. Given a compact action set X that spans R^d and an unknown reward vector hetainR^d, the goal is to output an arm widehat{x}inX such that langle widehat{x},hetarangle ge max_{xinX} langle x,hetarangle - arepsilon with probability at least 1-elta, using as few samples as possible. First, we present a non-adaptive fixed-design method with sample complexity O!left(frac{dlog(1/elta)}{arepsilon^2}+frac{w(X)^2}{arepsilon^2}right), where w(X) is a Gaussian width term dependent on X, and we prove a matching lower bound Omega!left(frac{dlog(1/elta)}{arepsilon^2}+frac{w(X)^2}{arepsilon^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 ell_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 ell_2-norm estimation subroutine: we design an adaptive algorithm that uses O!left(frac{dlog(1/elta)}{arepsilon^2}right) samples from the unit ell_2 ball in R^d and outputs an estimate widehat r satisfying |widehat r-|heta|_2|le arepsilon with probability at least 1-elta, where heta is the unknown reward vector.

Source: arXiv cs.LG | 2026-05-18