Search papers, labs, and topics across Lattice.
This paper investigates the trade-off between worst-case regret and instability in multi-armed bandit algorithms, revealing that comparable regret can be achieved with varying allocations across independent runs. The authors establish a finite-time lower bound for the product of regret and instability, demonstrating that $\mathcal R_{K,T}\mathcal S_{K,T}\ge C T^{3/2}$, and introduce the Stabilized Lower-Envelope UCB (SLE-UCB) algorithm, which achieves a matching bound of $O(T^{3/2}\log K)$. This work addresses a critical gap in understanding the regret-instability frontier, providing a new perspective on algorithm performance without relying on regularity assumptions.
Regret and instability in multi-armed bandits are fundamentally intertwined, with a new algorithm that optimally balances both while matching established lower bounds.
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.
