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\subseteq 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]}\cup \{\bar{2},\dots ,\overline{r+1}\}$, we prove a closed-form recursion for the adaptive value of every reachable state. We obtain $\mathrm{A}(H_r)=\frac{5r}{8}+O(\sqrt{r})$ and $\mathrm{B}(H_r)=\frac{r}{2}+{\log }_{2}r-{\log }_2{\log }_{2}r+O(1)$, hence ${\lim }_{r\to \infty }\mathrm{A}(H_r)/\mathrm{B}(H_r)=\frac{5}{4}$ exactly. Third, our capping theory bounds natural amplification constructions. For atoms whose adaptivity ratios are uniformly bounded by $C_0$, unions with disjoint label blocks obey $\mathrm{A}\le (C_0+2)\mathrm{B}$ at any finite nesting depth. An exact Hamming-ball formula shows that the additive localization surcharge already reaches $\Theta (\sqrt{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 $\Omega (k)$ separation: $q,\mathrm{B},\mathrm{F}=\Omega (k)$, and the concept class must have at least exponential size.