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

We study the minimax sample complexity of $\varepsilon$-best arm identification in linear bandits, a classical pure-exploration problem. Given a compact action set $\mathcal{X}$ that spans $\mathbb{R}^d$ and an unknown reward vector $\theta\in\mathbb{R}^d$, the goal is to output an arm $\widehat{x}\in\mathcal{X}$ such that $⟨\widehat{x},\theta⟩\ge \max_{x\in\mathcal{X}} ⟨x,\theta⟩- \varepsilon$ with probability at least $1-\delta$, using as few samples as possible. Our aim is to better understand the power and limitations of adaptivity in this setting. We begin with non-adaptive algorithms. We present a non-adaptive fixed-design method with sample complexity $\mathcal{O}\!\left(\frac{d\log(1/\delta)}{\varepsilon^2}+\frac{w(\mathcal{X})^2}{\varepsilon^2}\right)$, where $w(\mathcal{X})$ is a Gaussian width term dependent on $\mathcal{X}$, and we prove a matching lower bound $\Omega\!\left(\frac{d\log(1/\delta)}{\varepsilon^2}+\frac{w(\mathcal{X})^2}{\varepsilon^2}\right)$ for all non-adaptive fixed-design methods. Moreover, $w(\mathcal{X})\le \mathcal{O}(d)$ for general $\mathcal{X}$, which is tight for sets such as the unit $\ell_2$ ball, and $w(\mathcal{X})\le \mathcal{O}(\sqrt{d\log|\mathcal{X}|})$ when $\mathcal{X}$ is finite, which is tight for the canonical basis ${e_1,\ldots,e_d}$. We then turn to adaptive sampling. For any finite action set $\mathcal{X}$, we prove the existence of an adaptive algorithm with sample complexity $\mathcal{O}\!\left(\frac{d\log(1/\delta)}{\varepsilon^2}+\frac{d\log(|\mathcal{X}|/d)}{\varepsilon^2}\right)$ via a generalization of Median Elimination, which is known to yield a $\log d$ improvement for the canonical basis. This raises a 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 mult