arXiv:2608.17841v1 Announce Type: cross
Abstract: Multi-armed bandit algorithms are evaluated by regret, yet comparable regret can coexist with different allocations across independent runs. We study the trade-off between worst-case regret $mathcal{R}_{K,T}$ and instability $mathcal S_{K,T}$, defined as the largest standard deviation of a terminal pull count, for $K$ arms and $T$ rounds. We prove the finite-time lower bound $mathcal R_{K,T}mathcal S_{K,T}ge C T^{3/2}$, where $C$ is independent of $K$ and $T$, under a finite-time regret condition and without the regularity assumptions imposed in the prior asymptotic analysis. We also introduce Stabilized Lower-Envelope UCB (textup{textsc{SLE-UCB}}), a new tunable algorithm combining a running lower-envelope index with a decreasing pull-count stabilizer. textup{textsc{SLE-UCB}} satisfies $mathcal R_{K,T}mathcal S_{K,T}=O(T^{3/2}log K)$, with an implicit constant independent of $K$ and $T$, matching the lower bound exactly in $T$ and within a logarithmic factor in $K$. To prove the instability bound, we develop a new offline top-prefix representation that removes path dependence from online decisions. Together with single-reward perturbations and the Efron–Stein inequality, this representation controls pull-count variance. Thus, regret and instability depend reciprocally on $K$, while their product has no polynomial dependence on $K$. These results resolve the open question raised in the literature concerning the sharp arm-dependent regret–instability frontier.