Source-linked AI summary
Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits
Kaifei Wang, Yinyu Ye, Han Zhong
TL;DR
Regret alone does not capture run-to-run variation in bandit allocations, motivating a study of the regret–instability trade-off. The paper proves a finite-time lower bound and introduces tunable SLE-UCB, whose product matches the bound in T and up to log K.
Problem
Regret can be similar across algorithms even when their realized allocations vary substantially between independent runs.
Method
The paper combines a finite-time lower-bound argument with tunable SLE-UCB and an offline top-prefix representation analyzed using perturbations and Efron–Stein.
Results
The regret–instability product is lower-bounded by C T^3/2 and SLE-UCB achieves O(T^3/2 log K), matching the T dependence and logarithmically characterizing K dependence.
Takeaways & Limitations
The results characterize the finite-time regret–instability frontier and let decision makers tune accepted regret against allocation reproducibility within the model.
Takeaways & Limitations
The analysis assumes uniformly bounded arm means and sub-Gaussian reward distributions.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies why low regret does not ensure predictable allocations and characterizes the resulting regret–instability frontier. It proves a finite-time lower bound and introduces SLE-UCB, whose tunable design matches the optimal T-dependence and is logarithmically sharp in K.
- Motivation: Regret averages performance, so algorithms with similar regret can produce different realized pull allocations across independent runs.This matters because pull counts determine treatment assignments, traffic allocation, and data available for inference.
- Contributions: A finite-time lower bound establishes that regret and instability cannot both be too small under a mild condition permitting linear-in-T regret.The proof avoids separately assuming symmetry, nondegenerate exploration, or asymptotic active learning.
- Contributions: SLE-UCB combines a running lower-envelope UCB index with a decreasing pull-count stabilizer, allowing tunable trade-offs between regret and allocation variability.The lower envelope makes the reward-dependent index component monotone, while the stabilizer creates deterministic gaps between pull counts.
- Contributions: SLE-UCB matches the lower bound exactly in T and within a factor log K in K, removing the prior log T gap and resolving the open K-dependence question to logarithmic accuracy.Varying the tuning parameter traces the near-optimal regret–instability Pareto frontier.
- Contributions: An offline top-prefix representation removes path dependence from online decisions and, combined with single-reward perturbations and the Efron–Stein inequality, yields a finite-time instability bound.The representation converts a single-reward perturbation into a controlled change in terminal pull counts.
2 Model and performance metrics
The paper studies stochastic multi-armed bandits with unknown, independent reward distributions under bounded means and sub-Gaussian rewards. It evaluates algorithms by expected regret and instability, measuring both worst-case learning loss and reproducibility of pull allocations.
- Multi-armed bandits: The model has K ≥2 arms with mutually independent i.i.d. reward sequences and optimal mean µ⋆ defined as the largest arm mean.Each arm i has reward distribution ν_i and mean µ_i.
- Assumptions: Rewards have means in [−M, M] and are σ-sub-Gaussian for fixed constants M > 0 and σ > 0.These conditions apply to every arm.
- Online learning and objective: Over T > K rounds, the algorithm selects one arm using past observations and internal randomization, then observes only that arm’s reward.The reward revealed at time t is the selected arm’s next pull reward.
- Performance metrics: Regret measures expected cumulative reward loss versus the optimal arm, while instability is the largest pull-count standard deviation across independent runs.Lower instability means more reproducible allocations; performance is evaluated in the worst case over instances satisfying the assumption.
3 Fundamental limit and Stabilized Lower-Envelope UCB
This section establishes a finite-time regret–instability lower bound for K-armed bandits and introduces SLE-UCB, which matches the optimal T-scaling up to a logarithmic factor in K. The algorithm’s tunable stabilizer traces a regret–instability frontier while its analysis uses monotone indices, an offline representation, and perturbation bounds.
- Fundamental limit: For every K ≥2 and T > K, any algorithm with R_K,T ≤ MT/8 satisfies R_K,T S_K,T ≥ C T^3/2, where C is independent of K and T.The constant depends only on the instance-class parameters (M, σ).
- Fundamental limit: At minimax regret O(√(KT)), instability must be Ω(T/√K), so minimax-regret policies cannot keep terminal pull counts tightly concentrated across all instances.The minimax regret rate is attained, for example, by MOSS.
- Stabilized Lower-Envelope UCB: SLE-UCB combines a running lower-envelope UCB index with a logarithmic stabilizer that decreases with each arm’s pull count.The algorithm selects the arm with the largest stabilized index, using clipped rewards before index computation.
- Stabilized Lower-Envelope UCB: As α increases, the SLE-UCB regret bound rises while its instability bound falls, tracing a tunable regret–instability frontier.The product guarantee is uniform in α and applies over the tuning range where the regret bound is at most O(T).
- Stabilized Lower-Envelope UCB: SLE-UCB achieves O(T^3/2 log K) for the regret–instability product, replacing the prior explicit log T factor while retaining optimal T^3/2 dependence.The sharper K-dependence relies on monotone lower-envelope indices, a deterministic stabilizer gap, an offline top-prefix representation, single-reward perturbations, and the Efron–Stein inequality.
4 Clipping bias and concentration
This section bounds the bias introduced by reward clipping and establishes concentration for the clipped-reward statistics. The clipped-reward concentration event fails with probability at most 2(KT)^−7.
- Clipping bias: Lemma 4.1 upper bounds the clipping bias between the clipped-reward expectation and the true arm mean.The clipped-reward expectation is defined as θ_i = E[Y_i,1].
- Clipping bias: Clipping changes a reward only when its absolute value exceeds B, enabling the bias bound through a truncated-tail expectation.Under |μ_i| ≤ M < B, the difference is restricted to the event |X_i,1| > B.
- Clipping bias: The clipped-reward expectation remains close enough to the true mean that the clipped UCB statistic reflects arm performance.This consequence is stated directly after Lemma 4.1.
- Clipped reward concentration: Lemma 4.2 defines a concentration event G for clipped rewards, whose complement satisfies P(Gc) ≤ 2(KT)^−7.The proof applies Hoeffding’s inequality to rewards in [−B, B] and a union bound over at most KT arm-count pairs.
5 Regret Analysis
The regret proof decomposes performance according to a concentration event, separately bounds initial and noninitial pulls, and controls the failure-event contribution. Combining these bounds and taking the supremum over admissible instances establishes the stated worst-case regret result.
- Regret decomposition: The proof decomposes regret into contributions on the concentration event G and its complement G^c.On G^c, bounded mean gaps yield regret at most 2MT, while Lemma 4.2 controls the probability of G^c.
- Worst-case guarantee: Taking the supremum over all admissible instances completes the proof of the stated worst-case regret bound.The final step applies after the combined estimates have been established for a fixed admissible instance.
- Regret on G: On G, the initialization contribution is bounded using clipped rewards, while noninitial pulls are analyzed through the SLE-UCB selection rule and lower-envelope indices.The initialization phase contributes at most 2BK; noninitial analysis compares the selected arm with an arm attaining the largest clipped mean.
- Noninitial pulls: Summing noninitial-pull bounds uses the terminal pull counts, Cauchy–Schwarz, and concavity of x log(T/x) to control the aggregate contribution.The argument evaluates each arm at its last pull and uses the identity sum_i N_i(T) = T.
- Combining bounds: The initial- and noninitial-phase estimates are combined, parameters are substituted, and elementary inequalities simplify the resulting regret bound.The proof uses β = 8Bι, B = M + 4σι, and the relations σ ≤ β and M ≤ β.
6 Instability Analysis
The instability analysis replaces path-dependent online decisions with an equivalent offline top-prefix selection rule. This representation enables variance control through tie-breaking sensitivity and single-reward perturbations combined with the Efron–Stein inequality, yielding the instability bound uniformly over admissible instances and arms.
- Variance analysis: The offline representation removes the path dependence that makes online sensitivity difficult to track, allowing Efron–Stein analysis through single-coordinate reward perturbations.Conditional on the tie-breaking permutation, the final pull count is a deterministic function of the clipped reward array.
- Offline–online equivalence: The offline top-prefix rule and online greedy SLE-UCB rule select identical item sets for every reward array, permutation, and T ≥ K.Both select all K initial items, followed by the top T − K post-initial items ordered by stabilized index values and tie-breaking priorities.
- Tie-breaking sensitivity: Changing the tie-breaking permutation alters any target arm’s final count by at most one.Only items tied at the last selected value can change, and each arm has at most one post-initial item at that value because its index sequence is strictly decreasing.
- Reward perturbations: On the concentration event for both reward arrays, replacing one clipped reward yields a bounded pull-count perturbation controlled through the lower-envelope minimizer.The proof establishes s(n) ≥ n/9 before translating index changes into pull-count changes.
- Final instability bound: The variance decomposition combines the tie-breaking and reward-perturbation bounds to prove the instability bound uniformly over admissible instances and arms.Taking the maximum over arms and then the supremum over instances completes the proof of the bound in (3.6).
7 Proof of the K-armed lower bound
The proof establishes the K-armed regret–instability lower bound by reducing fixed K to two arms and constructing a finite sequence of nearby Gaussian instances. A variance-sensitive comparison converts a large change in aggregate suboptimal pulls into instability, yielding a K-independent T^3/2 product bound.
- Fixed-K reduction: Fixed-K extension follows by padding with K − 2 independent Gaussian dummy arms while preserving the required regret and instability conditions.The reduction simulates the original two real arms on dummy-arm requests and discards the resulting rewards.
- Gaussian instance construction: Theorem 3.1 starts from an algorithm satisfying the finite-time condition R_K,T ≤ MT/8 and selects the least-pulled arm on the all-zero Gaussian instance.The selected arm becomes uniquely optimal in a family where its mean is 0 and every other arm’s mean is −∆.
- Gaussian instance construction: A recursively defined sequence of nearby gaps connects the all-zero instance to an admissible endpoint ∆⋆, with consecutive interaction-history KL divergences at most 1/2.Absolute continuity ensures positive aggregate suboptimal-pull expectation throughout the sequence, so the recursion is well defined.
- Gap amplification: At the endpoint, ∆⋆G(∆⋆) equals the instance regret and G(∆⋆) ≤ T/8; therefore some consecutive pair differs by at least 3T/(8L).Here G denotes the expected aggregate number of suboptimal pulls.
- Instability comparison: The variance-rescaled nearby-instance lemma turns this aggregate-count gap and the KL control into an instability lower bound, which is then multiplied by R_K,T.The comparison uses event probabilities under two Gaussian instances and the Bretagnolle–Huber inequality.
- K-independent conclusion: The standard Gaussian minimax construction, after scaling variance to σ^2 and restricting means to [−M, M], supplies the final K-independent T^3/2 lower bound.The construction uses one-arm mean perturbations, Pinsker’s inequality, divergence decomposition, and Cauchy–Schwarz.
8 Conclusion
The paper characterizes the finite-time regret–instability trade-off for K-armed bandits, with a K-independent lower-bound constant and SLE-UCB achieving O(T^3/2 log K). These results match in T^3/2 dependence and up to a logarithmic factor in K, characterizing the frontier to logarithmic accuracy.
- The finite-time regret–instability frontier is characterized for K-armed bandits.
- O(T^3/2 log K) is achieved by the tunable SLE-UCB algorithm, with a lower-bound constant independent of K.
- The lower and upper bounds match in their T^3/2 dependence and up to a logarithmic factor in K.