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
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 Δ 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 (ISM). Assuming means bounded by U and σ2-sub-Gaussian rewards, we show ISM to be δ-correct and to enjoy a sample complexity bound of order K(σ2+U2)Δmin−2lnδ1. We also present a matching (up to constant factors) worst-case lower bound and evaluate our results empirically.
Figures & tables
δ
D∗1lnδ1
D∗1lnδK−1
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 δ . For Lemma 3 we took as the variance proxy ρ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 δ , 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 δ=1/10 and mis-specifies U=1,21,41 . Here the dashes show the average stopping times. U=41 admits 4 mistakes, all other runs were perfect.
a
b
Δb
λt,a,b
αt,a,b
βt,a,b
Drift \Et[zt,a,b]
\vart[zt,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=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.
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.
Yasin Abbasi-Yadkori, Peter L. Bartlett, Victor Gabillon +2
Adobe Research, USA · University of California, Berkeley, USA · Queensland University of Technology - ACEMS, Australia +2
In multi-armed bandits, the most-explored arms are the most informative, while reward maximization typically pulls only the best arm. We study the tradeoff between identifying arm means accurately and accumulating reward, and present an algorithm with regret guarantees that interpolates between the two objectives. We provide both upper and lower bounds and validate empirically.
Akram Erraqabi, Alessandro Lazaric, Michal Valko +2
In fixed-budget best-arm identification, also known as ranking and selection, an algorithm has a sampling budget to distribute across K arms. Each sample provides noisy feedback about that arm's mean, and the goal is to identify the arm with the largest mean. A common performance benchmark is the static oracle: a non-adaptive strategy that knows the means in advance and chooses fixed sampling proportions to maximize the exponential decay rate of the probability of incorrect identification. Several adaptive algorithms have been constructed such that their sampling proportions converge to the static oracle proportions. However, it has remained open whether any algorithm could match the static oracle's error decay rate uniformly across all problem instances. We answer this in the negative. For any K≥3 and for rewards drawn from any one-parameter natural exponential family, we show that for any algorithm, there is at least one instance where the error decay rate is at most (1+8log(K))−1 times that of the static oracle. This also answers the open question posed by Qin (2022), showing that fixed-budget best-arm identification does not admit a complexity.