Best Arm Identification for Bandits with Shifting Means

Lukas Zierahn; Wouter M. Koolen; Shubhada Agrawal; Christina Katsimerou; Dirk van der Hoeven

stat.MLOct 7, 2026

Best Arm Identification for Bandits with Shifting Means

Authors: Lukas Zierahn, Wouter M. Koolen, Shubhada Agrawal, Christina Katsimerou, Dirk van der Hoeven

Organizations: CWI and Booking.com Science Park 123 1098 XG Amsterdam · CWI and University of Twente Science Park 123 1098 XG Amsterdam · Indian Institute of Science (IISc), Bengaluru CV Raman Rd, Bengaluru, Karnataka 560012, India · Booking.com Oosterdokskade 163, 1011 DL Amsterdam · Leiden University Rapenburg 70, 2311 EZ Leiden

Abstract

We study the best arm identification problem in a stochastic environment with a novel form of adversarial perturbations, which we coin Shifting Means. While classically the mean rewards of the $K$ arms are stable in time, in Shifting Means only the gaps $\boldsymbolΔ$ between mean rewards are stable, while their common shift may be determined adversarially in each round. The objective of the learner is to identify the best arm with high probability while minimizing sample complexity (the fixed confidence setting). Handling shifts requires new tools: we show that algorithms employing a Generalized Likelihood Ratio Test (GLRT) stopping rule, including the popular Track-and-Stop, fail under time-varying shifts. Instead, we propose Importance Weights for Shifting Means ( $\mathsf{ISM}$ ). Assuming means bounded by $U$ and $σ^2$ -sub-Gaussian rewards, we show $\mathsf{ISM}$ to be $δ$ -correct and to enjoy a sample complexity bound of order $K (σ^2 + U^2) Δ_{\min}^{-2} \ln \frac{1}δ$ . We also present a matching (up to constant factors) worst-case lower bound and evaluate our results empirically.

Figures & tables

$\delta$	$\frac{1}{D^{*}}\ln\frac{1}{\delta}$	$\frac{1}{D^{*}}\ln\frac{K-1}{\delta}$	Lemma 3	Empirical	Empirical Overhead
$10^{-1}$	11 434	16 889	69 702	[28 085, 29 470]	[145.62%, 157.74%]
$10^{-10}$	114 340	119 796	211 870	[140 868, 143 920]	[23.20%, 25.87%]
$10^{-100}$	1 143 403	1 148 858	1 384 182	[1 199 222, 1 207 930]	[4.88%, 5.64%]

Table 1: Theoretical predictions and practical measurement of sample complexity for the bandit as laid out in Section 6 at different

\delta

. For Lemma 3 we took as the variance proxy

\rho^{2}

the largest worst-case variance in Table 2 . The empirical value is given as a 95% confidence interval of 1000 samples. The ratio is the real overhead not predicted by theory, that is, it is the relative percentage difference between the first and second last entry of the table.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 1: Histograms of stopping times in

1000

runs. The first three figures use

U=1

and vary

\delta

, the dashed lines are (green) the expected stopping time as predicted by Theorem 4 , (black) the empirical average stopping time, and (red) the stopping time as predicted by Lemma 3 (as also spelled out in Table 1 ). The last figure fixes

\delta=1/10

and mis-specifies

U=1,\frac{1}{2},\frac{1}{4}

. Here the dashes show the average stopping times.

U=\frac{1}{4}

admits 4 mistakes, all other runs were perfect.

$a$	$b$	$\Delta_{b}$	$\lambda_{t,a,b}$	$\alpha_{t,a,b}$	$\beta_{t,a,b}$	Drift $\E_{t}[z_{t,a,b}]$	$\var_{t}[z_{t,a,b}]$ bound
1	2	0.05	0.00805581	0.000100929	0.000100477	0.000201384	0.00038665
1	3	0.07	0.0057545	0.000104116	0.000097315	0.000201384	0.000374914
1	4	0.1	0.00402871	0.000105826	0.000095661	0.000201384	0.0003842

Appendix

Table 2: Optimised parameters for the pairs

a\neq b

involving the best arm

a=a^{*}=1

. The drifts are perfectly equalised. The worst-case variances are computed as described in Appendix I . They are not optimised to be similar, but they turn out to be.

Explore similar work

Best of both worlds: Stochastic & adversarial best-arm identification
Apr 16, 2026Yasin Abbasi-Yadkori, Peter L. Bartlett, Victor Gabillon +2Stochastic Multi-Armed Bandits Bounded Adversary
Adobe Research, USA · University of California, Berkeley, USA · Queensland University of Technology - ACEMS, Australia +2
Trading off rewards and errors in multi-armed bandits
May 1, 2026Akram Erraqabi, Alessandro Lazaric, Michal Valko +2Stochastic Multi-Armed Bandits Regret
Inria SequeL · CMU · EnLearn
Fundamental Limitations of Fixed-Budget Best-Arm Identification
Jul 13, 2026Motti GoldbergerStochastic Multi-Armed Bandits Token Budget Allocation
Yale University

Apr 16, 2026, stat.MLJ/K move · Enter open · S save

Best of both worlds: Stochastic & adversarial best-arm identification

Yasin Abbasi-Yadkori, Peter L. Bartlett, Victor Gabillon, Alan Malek+1

Adobe Research, USA · University of California, Berkeley, USA · Queensland University of Technology - ACEMS, Australia+2

Stochastic Multi-Armed Bandits Bounded Adversary Bandits Learning-Augmented Algorithms Stochastic World

Open paper AskPDF arXiv

We study bandit best-arm identification with arbitrary and potentially adversarial rewards. A simple random uniform learner obtains the optimal rate of error in the adversarial scenario. However, this type of strategy is suboptimal when the rewards are sampled stochastically. Therefore, we ask: Can we design a learner that performs optimally in both the stochastic and adversarial problems while not being aware of the nature of the rewards? First, we show that designing such a learner is impossible in general. In particular, to be robust to adversarial rewards, we can only guarantee optimal rates of error on a subset of the stochastic problems. We give a lower bound that characterizes the optimal rate in stochastic problems if the strategy is constrained to be robust to adversarial rewards. Finally, we design a simple parameter-free algorithm and show that its probability of error matches (up to log factors) the lower bound in stochastic problems, and it is also robust to adversarial ones.

Abstract

Explore similar work

Best of both worlds: Stochastic & adversarial best-arm identification

Trading off rewards and errors in multi-armed bandits

Fundamental Limitations of Fixed-Budget Best-Arm Identification