The Price of Adaptivity in Bandit Multiclass Classification: Minimal Separation and Sharp Tower Asymptotics

We resolve the existence component of a foundational open problem posed at NeurIPS 2024 concerning the price of adversarial adaptivity in bandit multiclass classification. The optimal expected mistake bound against an adaptive adversary is at most a multiplicative O(k) above the oblivious bound, where k = |Y|. We prove that genuine concept classes H ⊆ Y^X can incur a strict adaptive–oblivious gap. First, a four-function class on two points with k = 3 has adaptive value 35/29 and oblivious value 7/6. No class of at most three functions separates, so four is optimal. Second, for the multi-shield towers H_r = {0,1}^[r] ∪ {2̄, …, (r+1)‾}, we prove a closed-form recursion for the adaptive value of every reachable state. We obtain A(H_r) = 5r/8 + O(√r) and B(H_r) = r/2 + log₂ r − log₂ log₂ r + O(1), hence limr→∞ A(H_r)/B(H_r) = 5/4 exactly. Third, our capping theory bounds natural amplification constructions. For atoms whose adaptivity ratios are uniformly bounded by C₀, unions with disjoint label blocks obey A ≤ (C₀ + 2)B at any finite nesting depth. An exact Hamming-ball formula shows that the additive localization surcharge already reaches Θ(√n) for two overlapping layers. Every exact value has a certificate: primal–dual certificates at each game state for adaptive play, and explicit priors and sequences for oblivious play. The included standard-library script re-checks them all. We also establish necessary conditions for linear Ω(k) separation: q, B, F = Ω(k), and the concept class must have at least exponential size.