Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits

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 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 (extup{extsc{SLE-UCB}}), a new tunable algorithm combining a running lower-envelope index with a decreasing pull-count stabilizer. extup{extsc{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.

Related

• Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits
• Replicability is Asymptotically Free in Multi-armed Bandits
• Trading off rewards and errors in multi-armed bandits

Source: arXiv cs.LG | 2026-08-19