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

摘要

We study the minimax sample complexity of ε-best arm identification in linear bandits, a classical pure-exploration problem. Given a compact action set 𝒳 that spans ℝ^d and an unknown reward vector θ∈ℝ^d, the goal is to output an arm x∈𝒳 such that ⟨x,θ⟩≥max_x∈𝒳 ⟨x,θ⟩- ε with probability at least 1-δ, 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 𝒪(dlog(1/δ)/ε^2+w(𝒳)^2/ε^2), where w(𝒳) is a Gaussian width term dependent on 𝒳, and we prove a matching lower bound Ω(dlog(1/δ)/ε^2+w(𝒳)^2/ε^2) for all non-adaptive fixed-design methods. Moreover, w(𝒳)≤𝒪(d) for general 𝒳, which is tight for sets such as the unit ℓ_2 ball, and w(𝒳)≤𝒪(√(dlog|𝒳|)) when 𝒳 is finite, which is tight for the canonical basis e_1,…,e_d. We then turn to adaptive sampling. For any finite action set 𝒳, we prove the existence of an adaptive algorithm with sample complexity 𝒪(dlog(1/δ)/ε^2+dlog(|𝒳|/d)/ε^2) 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 ℓ_2 ball, m-sets, and multi-task multi-armed bandits. Finally, we show that logarithmic improvements are not the whole story. To our knowledge, we provide the first construction of an action set 𝒳 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 𝒪(dlog(1/δ)/ε^2) samples from the unit ℓ_2 ball in ℝ^d and outputs an estimate r satisfying |r-θ_2|≤ε with probability at least 1-δ, where θ is the unknown reward vector. Taken together, these results illustrate when adaptivity can offer only modest savings and when it can enable genuine polynomial gains, sharpening our understanding of the role of adaptivity and geometry in pure exploration and experimental design.