{"id":"arxiv/2608.17841","url":"https://arxiv.org/abs/2608.17841","tags":["stat.ML","cs.LG","math.OC","math.ST"],"score":0,"title":"Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits","domain":"stat.ML","source":"arxiv","authors":["Kaifei Wang","Yinyu Ye","Han Zhong"],"reviews":0,"subject":"stat.ML","summary":"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…","category":"research","comments":0,"disputed":false,"division":"stat","mentions":0,"discussed":0,"published":"2026-08-18","reactions":{}}