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

Kaifei Wang; Yinyu Ye; Han Zhong

stat.MLAug 18, 2026

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

Authors: Kaifei Wang, Yinyu Ye, Han Zhong

Organizations: Peking University · Stanford University · Shanghai Jiao Tong University

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

Figures & tables

Panel of Figure 1 — Figure 1: Schematic $K$ -dependent regret–instability product comparison, with logarithmic factors and constants suppressed in the axis annotations. The solid blue and dashed orange curves denote the lower bound and the SLE-UCB upper bound, respectively. In the regret regime covered by Theorem 3.1 , the gray region is excluded and the product bounds differ by at most a factor $\log K$ .

Panel of Figure 2 — Figure 2: Offline and online selection ( $K=3$ , $T=8$ ). An item $(i,n)$ represents the $n$ -th pull of arm $i$ , has value $V_{i,n}=I_{i}(n-1)$ , and is post-initial when $n\geq 2$ . Consider a permutation $(\omega(1),\omega(2),\omega(3))=(2,3,1)$ . Assume $I_{2}(1)>I_{1}(1)>I_{3}(1)=I_{1}(2)>I_{2}(2)$ and all other indices are smaller. For offline selection, after sorting $V_{i,n}=I_{i}(n-1)$ by decreasing value and resolving the tie using $\omega$ , the first five items in the offline post-initial order are $(2,2),(1,2),(3,2),(1,3),(2,3)$ . For online selection, the first five choices after initialization are $2\to 1\to 3\to 1\to 2$ , which corresponds to the same items $(2,2),(1,2),(3,2),(1,3),(2,3)$ as in the offline selection.

Explore similar work

Sep 29, 2026

Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity

We study multi-armed bandits (MAB) with multiple optimal arms, motivated by the fact that many practical decision making problems admit multiple correct answers. For

K

-armed bandits with

A

optimal arms, we first provide a sharper analysis of previous sub-sampling algorithms (De Heide et al., 2021; Zhu and Nowak, 2020), establishing a

\tilde{O}\Big(\frac{K-A}{\sqrt{KA}}\sqrt{T} \Big)

minimax regret, where

T

is the total number of interactions and

\tilde O(\cdot)

drops all constant and logarithmic factors, improving the previous

\tilde{O}(\sqrt{KT/A})

regret. We then provide a matching lower bound up to logarithmic factors, indicating that our established rate is nearly minimax-optimal. We further show that the knowledge of

A

up to

\tilde{O}(1)

factors is necessary to achieve near-optimal regret, as near-optimal algorithms for one number of optimal arms must incur substantially larger regret than optimal regret for a smaller number. Overall, our results provide a comprehensive minimax characterization of

K

-armed bandits with

A

over the entire range of

1 \leq A \leq K-1

Kaixuan Ji, Qiwei Di, Qingyue Zhao +2

Department of Computer Science, University of California, Los Angeles, CA 90095, USA

Multi-Armed Bandits Minimax Regret Regret Minimization

Ask PDF

May 6, 2026

Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning

We study the distribution of regret in stochastic multi-armed bandits and episodic reinforcement learning through a unified framework. We formalize a distributional regret bound as a probabilistic guarantee that holds uniformly over all confidence levels

δ\in (0,1]

, thereby characterizing the regret distribution across the full range of

δ

. We present a simple UCBVI-style algorithm with exploration bonus

\min\{c_{1,k}/N, c_{2,k}/\sqrt{N}\}

, where

N

denotes the visit count and

(c_{1,k},c_{2,k})

are user-specified parameters. For arbitrary parameter sequences, we derive general gap-independent and gap-dependent distributional regret bounds, yielding a principled characterization of how the parameters control the trade-off between expected performance, tail risk, and instance-dependent behavior. In particular, our bounds achieve optimal trade-offs between expected and distributional regret in both minimax and instance-dependent regimes. As a special case, for multi-armed bandits with

A

arms and horizon

T

, we obtain a distributional regret bound of order

\mathcal{O}(\sqrt{AT}\log(1/δ))

, confirming the conjecture of Lattimore & Szepesvári (2020, Section 17.1) for the first time.

Harin Lee, Min-hwan Oh

University of Washington · Seoul National University

Multi-Armed Bandits Regret Minimization in RL UCB Algorithms Model-Based RL

Ask PDF

Apr 16, 2026

Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards

We study the tail behavior of regret in stochastic multi-armed bandits for algorithms that are asymptotically optimal in expectation. While minimizing expected regret is the classical objective, recent work shows that even such algorithms can exhibit heavy regret tails, incurring large regret with non-negligible probability. Existing sharp characterizations of regret tails are largely restricted to parametric settings, such as single-parameter exponential families. In this work, we extend the

\KLinf

-UCB algorithm of to a broad nonparametric class of reward distributions satisfying mild assumptions, and establish its asymptotic optimality in expectation. We then analyze the tail behavior of its regret and derive a novel upper bound on the regret tail probability. As special cases, our results recover regret-tail guarantees for both bounded-support and heavy-tailed (moment-bounded) bandit models. Moreover, for the special case of finitely-supported reward distributions, our upper bound matches the known lower bound exactly. Our results thus provide a unified and tight characterization of regret tails for asymptotically optimal KL-based UCB algorithms, going beyond parametric models.

Subhodip Panda, Shubhada Agrawal

Department of ECE · Indian Institute of Science · Bangalore, India

Multi-Armed Bandits UCB Algorithms

Ask PDF