Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits
Authors: Zixin Zhong
Wang Chi Cheung
Vincent Tan
Venue: Accepted by TMLR ()

Abstract: We study the Pareto frontier of two archetypal objectives in multi-armed bandits, namely, regret minimization (RM) and best arm identification (BAI) with a fixed horizon. It is folklore that the balance between exploitation and exploration is crucial for both RM and BAI, but exploration is more critical in achieving the optimal performance for the latter objective. To this end, we design and analyze the BoBW-lil’UCB($\gamma$) algorithm. Complementarily, by establishing lower bounds on the regret achievable by any algorithm with a given BAI failure probability, we show that (i) no algorithm can simultaneously perform optimally for both the RM and BAI objectives, and (ii) BoBW-lil’UCB($\gamma$) achieves order-wise optimal performance for RM or BAI under different values of $\gamma$. Our work elucidates the trade-off more precisely by showing how the constants in previous works depend on certain hardness parameters. Finally, we show that BoBW-lil’UCB outperforms a close competitor UCB$_\alpha$ (Degenne et al., 2019) in terms of the time complexity and the regret on diverse datasets such as MovieLens and Published Kinase Inhibitor Set.

Published in Transactions on Machine Learning Research (09/2023)
Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits
Zixin Zhong
zzhong 100raltrrtaa
Deportment of Computing Science, University of Alberta
Wang Chi Cheung
isecwe Crrus Cww.s.edu...........
Department of Industrial Systems and Management, Institute of Operations Research and Analytics, National University of Singopore
Vincent Y. F. Tan
vtan Breus. Ceseneruueed...
Department of Mathematics, Department of Electrical and Computer Engincering, Institute of Operations Research and Analytics, National University of Singapore
Reviewed on OpenReview: https: // openreview. net/ formff id= XXFDmIMJDm
Abstract
We study the Pareto frontier of two archetypal objectives in multi-armed bandits, namely, regret minimization (RM) and best arm identification (BAT) with fixed horizon. It is folklore that the balance between exploitation and exploration is crucial for both RM and BAI, but exploration is more critical in achieving the optimal performance for the latter objective. To this end, we design and analyze the BoBW-LIL UCB(r) algorithm. Complementarily, by establishing lower bounds on the regret achievable by any algorithm with a given BAI failure probability, we show that (i) no algorithm can simultaneously perform optimally for both the RM and BAI objectives, and (ii) BOBW UCC(() achieves order-wise optimal performance for RM or BAI under different values of y. Our work clucidates the trade-off more precisely by showing how the constants in previous works depend on certain hardness parameters. Finally, we show that BoBW-LI. UCB outperforms a close competitor UCB, (Dgenne et al.] 2019) in terms of the time complexity and the regret on diverse datasets such as MovieLens and Published Kinase Inhibitor Set.
1 Introduction
Consider a drug company Dandit (Drug Bandit) that wants to design an effective vaccine for a certain virus. It has a certain number feasible options, say = 10. Because Dandit has a limited budget, it can only test. vaccines for a fixed number of times, say T 1, 000. Using the limited number of tests, wants find the option that will lead to the "best" outcome, c.g., the maximum efficacy of the drug. the same time, Dandit aims to protect individuals from potentially adverse side effects of the vaccines to be tested. How can Dandit find the optimal drug design and, at the same time, protect the health of participants? We design an algorithm BoBW-LI.. UCB that allows Dandit to balance between these two competing targets. In complement, we also show that it is impossible for Dandit to achieve optimal performances for both targets simullaneouslyy and Dandit has to settle for operating on the Pareto frontier of the two objectives.
To solve Dandit's problem, we study the Cumulative Regret Minimization (RM) and Best Arm Identification (BAI) problems for stochastic bandits with fized time horizon or budget. While most existing works only study one of these two targets (Auer al. 2002a Audibert & Bubeck 2010 Degenne et al. (2019) designed

---

Published in Transactions on Machine Learning Research (09/2023)
the a algorithm for both RM and BAI with a fized confidence. Therefore, these studies are not directly applicable to Dandit's problem as Dandit is interested in obtaining the optimal item and minimizing the damage across a fixed number of tests. However, our setting dovetails neatly with company Dandit's goals. Dandit can utilize our algorithm to sequentially and adaptively select different design options to test the vaccines and to eventually balance between choosing the optimal vaccine and, in the process, mitigaling any physical damage on the participants. We also show that Dandit cannot achieve both targets optimally and simultaneously.
Beyond any specific applications, we believe this problem is of fundamental theoretical importance in the broad context of malti-armed bandits (MAB). In order to design an efficient bandit algorithm, a well-known challenge is to balance between exploitation and exploration (Auer et al. 2002a Lattimore & Szepesvári 2020; Kaufmann & Garivier 2017). Our work quantifies the Pareto frontier of RM and BAI, as well as the effects of exploitation and exploration on these two aims.
Main contributions. In stochastic bandits, there are L items with different unknown reward distributions. At each time step, a random reward is generated from each item's distribution. Based on the previous observations, learning agent selects an item and observes its reward. Given the number of time steps T E N, the agent aims to maximize the cumulative rewards and to identify the optimal item with high probability.
Our first main contribution is the BOBW-LB'UUCH RM and BAI over a fixed time horizon, which achieves Pareto-optimalltyy of RM and BAI in some regimes.
algorithm. BoBW-LI UCB(r) is designed for both
(i) On one hand, we can shrink the confidence radius of each item by increasing 7, which encourages BoBW- LIL' LIL'U UCB(() to pull items with high empirical mean rewards (exploitation) and generally leads to high rewards (i.c., small regret).
(ii) On the other hand, we can enlarge the confidence radius by decreasing to encourage the exploration of items that have not been sufficiently pulled in previous time steps (exploration); this will result in a high BAI success probability.
The parameter 7 in BoBW-LI''UCB()) can be tuned such that either its cumulative regret or its failure probability almost matches the corresponding state-of-the-arr lower bound (Lai & Robbins 1985 Carpentier (OBW-LI'UCB()) & Locatelli 2016). The performance of BoBW-LI' UCB(7) implies that exploitation is more critical in achieving the optimal performance for RM, while exploration is more crucial for BAI in stochastic bandits. We also analyze the ExP3. P algorithm proposed by Auer el al. (2002b) for both RM and BAT, which indicates the similar trade-off between these two aims in adversarial bandits.
Moreover, we evaluate the Pareto frontier of RM and BAI thooretically. In Lattimore & Szepesvári (020)) Note 33.2 and Exercise 33.5 only explore the sub-optimality for BAT of an asymppottically-optima RMM algorithm, and provide asymptotic bounds with constant E (See Section 3 for the meaning of e). Our work goes beyond the asymptotic regimes in that observation, by exploring the Pareto frontier of RM and BAI for any algorithm in Theorems 5.1 and 5.3 in the finite horizon / budget setting. Our non-asymptotic bounds quantify how the trade-off between regret and BAT probability depends on the hardness quantity H2 and gap parameter A AI,'' of an instance (see definitions in Section 2], instead of fixed constants such as e [Lattimore & Szepesvári 2020). Another relevant work is Bubeck et al. (2009). which explores the trade-off between cumulative regret and simple regret[] Due to the relation between BAI and simple regret, our results preciscly quantify the values of constants C' and D in Bubeck et al. (2009) (sce Section 5 for details). While these two works focus on the stochastic bandits, we also analyze the Pareto frontier between RM and BAI in adversarial bandits in Appendix B
Furthermore, BOBW-LI'UCB(() empirically outperforms a close competitor UCB, DDegenne et al.) 2019 in difficult scenarios in which the differences between the optimal and suboptimal items are small. While both algorithms identify the optimal item with high probability, UCB., designed for the fixed-confidence case, requires a longer horizon to do so and also suffers from larger regret. This demonstrates the superiority of BOBW-LI'UCB(Y under the fxed-budget setting, which it is specifically designed for.
Novelty, (i) We are the first to design an algorithm for both RM and BAI with a fixed budget. We can adjust the proposed BoBW-LL UCC(() algorithm to perform (near-)optimally for both RM and BAI with
When there no ambiguity, we abbreviate "cumulative regret" " as "regret".
2

---

Published in Transactions on Machine Learning Research (09/2023)
proper choices of y. (ii) The performance of BOBW-LL'UCB(C) implies that exploitation is more crucial to obtain a small regret, while exploration is more critical to shrink the BAT failure probability. (iii) We quantify the Pareto frontier of RM and BAI. We show that it is inevitable for any algorithm to compromise between RM and BAI in a fixed horizon setting. Beyond the stochastic bandits, we also provide a preliminary study on the adversarial bandits.
Literature review. Both the RM and BAI problems have been studied extensively for stochastic multi-armed bandits. Firstly, an RM algorithm aims to maximize its cumulative rewards, i.e., to minimize its regret (the gap between the highest cumulative rewards and the obtained rewards). One line of seminal works on RM involve the class of Upper Confidence Bound (UCB) algorithms (Auer et al.) 2002a Garivier & Cappé 2011
while another line of works study Thompson sampling (TS) algorithms (Agrawal & Goyaa 2012 Russo & Van Roy 2014 Agrawal & Goyal 2017). Lai & Robbins 1985 derived a lower bound on the regret of any
online algorithm.
Secondly, there are two complementary settings for BAI: (i) given T N, the agent aims to maximize the probability of finding the optimal item in at most T steps (Audibert & Bubeck, 2010 Karnin et al. 2013
Zhong et al.) 2021a]; ; (ii) given 8 > 0, the agent aims to find the optimal item with the probability of at least
1- 1-8 8 in the smallest number of time steps (Bubeck et al., 2013 Kaufmann & Kalyanakrishnan 2013). These
two settings are known as the fized-brudge and fized-conidene settings respectively. Moreover, Kaulmann
et al. (2016) presented theoretical findings for both settings, including a lower bound for two-armed bandits
and 8 lower bound for multi-armed Gaussian bandits under the fixed-budget setting. Carpentier & Locatelli (2016) established a lower bound on the fallure probability of any algorithm in fixed time horizon.
While most existing works focus solely RM or BAI, Degenne et al. (2019) explored both goals with fixed confidence and proposed the UCB, algorithm. Recently Kim et al. (2023) also focused on the fixed-coffidence setting and studied the trade-off between RM and Pareto Front Identification (PFI) in linear bandits; PFI is a generalization of BAI since in this setting each arm has a vector reward instead of a scalar one. Livc & Wang (2023) provided a novel definition of Pareto Optimality and aimed to solve a corresponding minimax multi-objective optimization problem, which has a different focus from this work. To the best of our knowledge, there is no existing analysis of a single, unified algorithm for both RM and BAI given fixed horizon. Our work fills in this gap by proposing the BOBW-LI'UCB( algorithm and proving that it achieves Pareto-optimalityy in some regimes. We also study the Pareto frontier of RM and BAI, which depends on the balance between exploitation and exploration. We show that a single algorithm cannot perform optimally for both RM and BAI simultaneously.
2 Problem Setup
For any n E N, we denote the set [I....,n) as [n]]. Let there be L E N ground items, contained in [L]. A random variable X (or its distribution) o-sub-Gaussian (a-SG) if EjcA(X-XX]] I exp(X' item i E [L] associated with a o-SG reward distribution v4, mean Wi and variance o7. The distributions (vi)e(()), means (w:) and variances {o?) are unknown to the agent. We let (9x,)(= be the i.i.d. sequence of rewards associated with item during the T time steps; each Gi. is an independent sample from 1/+
/2). Each
We focus on stochastic instances with a unique item having the highest mean reward, and assume that wi > w2 ... 2 Wt, so the unique optimal item i" = Note that the items can, in general, be arranged in any order; the ordering that w; 2 wj for < is employed to ease our discussion. We denote A := wi w, as the optimality gap of item i, and assume A1, S 1 for all i e [L]; this can be achieved by rescaling the instance if necossary. We define the minimal optimality gap
= min A $11
Clearly, A > 0. We characterize the hardness of an instance with the following canonical quantities:
1
H1 : Σ A
and H2 : Σ
(2.1)
1
1
3

---

Published in Transactions on Machine Learning Research (09/2023)
The hardness quantity H1 is involved in some near-optimal regret bounds (Auer al. 2002a Agrawal & Goyal 2012). The quantity H2 was first introduced in Audibert & Bubeck (2010) and appears in many landmark works on BAI (Jamieson et al. 2014 Karnin et al. 2013 Carpentier & Locatelli 2016
TT The agent uses online algoritho a to decide the item o7 to pull at each time step L, and the item out to output eventually. More formally, an algorithm consists of tuple л: T: ((Te)) 1/7""")) where
the sampling rule ne determines, based the observation history, the item of pull time step t. That is, the random variable t is mensuueaeee,ble, where F, == ( - 1.............. 1 9tp,e);
the recommendation rule vi chooses an item F.T that is, by definition, Fa-measurbll..
Moreover, define the pseudo-regrel Rr of π
BT(T): max 1S:SL
E
Σ 91.
E
Σ 96 it = T
E
Σ wiy
The algorithm aims to both minimize the pseudo-regret (x)x) and at the same time, to identify the optimal item with high probability, i.e, to minimize the failure probability er(x) Pr( o 1). We omit T and in the superscript or subscript when there is cause of confusion. We write (T as Ry (T, I), (x( as er (z Z) when wish to emphasize their dependence on both the algorithm and the instance I.
3 Discussion on Existing Algorithms
Although there is existing work that analyzes single algorithm for both RM and BAI in fixed horizon, it is natural to ask if an algorithm which is originally designed for RM can also perform well for BAI, and vice versa. In Table 3.1 we present the theoretical results from some existing works. We focus on algorithms that are with (potential) theoretical guarantees for both RM and BAL We define
1
H = max A
and Cp:=2
for p > 0 as in Shahrampour et al. (017)) SEQUENTIAL ELIMINATION with parameter as NSE(p), and UCB-E with parameter a as UCB-E(a). Also see Appendix A for more discussions.
We abbreviate SEQUENTIAL HALVING as SH, NONLINEAR
Table 3.1: Comparison among upper bounds for algorithms and lower bounds in stochastic bandits.
Algorithm/IInnn IIstancce
Pseudo-regret Ry
Failure Probability er
References
SH
@
exp
T 814 loga T.
Karnin et al. 2013
NSE(P)
((T)
exp
2(T L) HCCPp
Shahrampour et al. (2017
2LT1 22//23
UCB-E(alogT)
6.3a/ HI log'
Corollary A.1 Audibert & Bubeck 2010
(when a aoog T x
2M(T-1) 3alts
Hy log T (Prob-lep)
Re Lexp
T-L 14477s
BOBW-LLUUCB))
Theorems
and 4.2
To (Prob-indep)
(when 2 (1, Ha))
Stochastic Bandits
4007
(Lower Bound)
All, log T
exp
log
Lai & Robbins 1985
Carpentier & Locatelli (016
According to the discussions on RM and BAI in Lattimore & Szepesvári 2020 any algorithm with an asymptotically optimal regret would incur failure probability lower bounded by 2(T-1); this is much larger
4

---

Published in Transactions on Machine Learning Research (09/2023)
than the state-of-the-art lower bound [(exp(-400T/ (H2 log L))) by Carpentier & Locatelli 2016 Therefore, we only include algorithms that were designed for BAT in Table 3.1
Among the various BAI algorithms, SH and NSE(p) perform almost the best. However, their bounds on the failure probabilities are incomparable in general. The comparison among more BAI algorithms is provided in Table A.1 Due to the designs of SH and NSE(p); we surmise their regrets grow linearly with T, which is vacuous for the RM task.
Although UCB-E(a logT) has upper bounds both pseudo-regred and failure probability, its bound on the latter, which decays only polynomially fast. with T when is an absolute constant, is clearly suboptimal vis- à-vis the state-of-the-art lower bound by Carpentier & Locatelli 2016). In order to achieve an exponentially decaying upper bound on er (i.e., exp(-9(7))), we need lo set a O log T), and hence the regret bound (see Corollary A.1 in the supplementary) will be O OoT2/log] T), which is vacuous.
The discussion above raises natural question. Is it possible to provide a non-trivial bound on the regret for an algorithm that performs optimally for BAT over fixed horizon? This motivates us to design BOBW-LBUUCB, which can be tuned to perform near-optimally for both RM and BAL.
4 The BOBW-LIL'UCB Algorithm
We design and analyze BOBW-LL'UCBI/ (BEST OF BOTH WORLDS-LAW OF ITERATED LOGS-UCB), an algorithm for both RM and BAT in fixed horizon. By choosing parameter 7 judiciously, the guarantees of BOBW-LLL'UCBO match those of the state-of-the-art algorithms for both RM (up to log factors) and BAI (concerning the exponential term).
Algorithm 1 BoBW- UCB(()
1: Input: time budget T, size of ground set of items I,, scale a > 0, E E (0, 1), 3 2 0, and 7 E (0, 1). 2: Sample i, = =i for t = I,...,L L and set = L. For all i [L], compute Nr,L, :.LL: Ci U,,,7:
Σ lfin = i), Pie+ = Eum Ii.t 1fin = u=1
No.-
Ni.
2(1 + Nii
log(3 + (1 (1)+))
City= 50 + V
log
Una = -r. + Cia
4: for = L + I,...,T T do
5: Pull item i, = arg max vE(L) U
Update Ni Ric Ch and Un
end for
8:
Output fout = arg [e[] Di.
Design of algorithm. We design LUBB-LLL'UCC in the spirit of the law of the iterated logarithm (LII.) (Darling & Robbins 1967 Jamieson et al. 2014 We remark that it is a variation of the LMI UCB algorithm proposed by Jamicson et al. (2014). The three differences are:
(i) to construct the confidence radius Ci we replace (1 B) and 8 in LIL'CB by 5 and in BoBW- LII' LI'UCB(7) respectively;
(ii in the design of Cis,y we also replace log((1 + N),))) by log(3 + N)..):
(iii) BOBW-LL'UBB// which is designed for both RM and BAI in a fixed horizon, involves no stopping rule since it proceeds for eractly T time steps; while L.I. A.'UC designed for BAT with a fixed confidence.
Although our algorithm depends on the choices of E, B, and 7, we term as BOBW-LI'UCHE UCB()) instead of the more verbose NOBW-LILUCBA, 8) because we scale the confidence radius by only varying 7 which adjusts the performance of the algorithm. More precisely, inspired by the LIL (see Theorem C.1), we design item i's confidence radius City with Ni. (the number of time steps when item i is pulled up to and including
5

---

Published in Transactions on Machine Learning Research (09/2023)
the tth time step) and 9r,1 (the empirical mean of item i at time step t), and its upper confidence bound U4A,7 accordingly.
The design of BOBW-LL'UCB(/) allows us to shrink Clay the confidence radius of each item i, by increasing Y and vice versa. Moreover, with a fixed y, item is rarely pulled in previous time steps, it has a small Ni. and hence a large Creyy and vice versa.
(i) Therefore, when y increases, the dominant term in Usa, = 9i, + Caat becomes the empirical mean u..- Since BOBW-LI'UCB pulls the item with the largest 1 at time step t, the algorithm tends to pull the item with the largest empirical mean in this case. In other words, a large y encourages exploitation. (i) When ? decreases, the confidence radius Caay dominates Uha, Consequently, BoBW-LL'UCH is likely to pull items with large Ct,,,r, i.c., the rarely pulled items with small No,- This indicates that small y encourages exploration.
Altogether, can scale U by adjusting 7, which allows to balance exploitation and exploration and trade-off between the twin objectives RM and BAI.
Analysis for RM. We first derive problem-dependent and problem-independent bounds on the pseudo-regret of BoBW-LnIUCB(6,
Theorem 4.1 (Bounds on the pseudo-regret of BOBW-LL'UCB, Let & E (0.1), B 2 O, and y e (0, min (log(3 + 1 e)/e,1)), For all T 2 1, the pseudo-regret of BoBW-LI: satisfies
Rí R0
Σ
log(1/7) + + Ro (osoTO2VTIOO (og((T/Ln)) + +TII)+t) A
?
Purthermore, we can set 7 = (log T to oblain
logT) AI.))
RT S O 02.
RT S (0ooooTToog
#11
We observe that the order of the problem-dependent upper bound on the pseudo-regret of BoBW- LIL AILUUB((logg T) T)) almost matches that of the lower bound (Li & Robbins 1985). Morcover, the worst-case (problen-indepeendent) upper bound of BoBW-LIL' LIL-LLLUUBBII (CB()lo)))TT) is O(VTL), which matches the lower bound (VVLL) (Bubeck et al. 2012) up to log factors. This implies that we can tune the parameter y in the BOBW-LL(UCCB()) algorithm to obtain closo-to-optimal performance for RM.
We remark that when the optimal item is not unique, we can also derive analogous upper bounds on the reeue of BoBW-LIL' (EL-LLL'UCB)))) using similar line of analysis (see Proposition D.I.
Analysis for BAI Next, we upper bound the failure probability of BOBW-LI'UCB(1)
Theorem 4.2 (Bounds on the failure probability of BOBW-LL'UCB), Let E E (0, 1), 3 2 0, and y e (0, min + 1 + 8)/e, 1)). Let A, = Ma A12) for all i E [L]. For all 2 1, the faiture probubility of BOBW-LI'UCB(c) satisfies
et 2L(2+E) E
Ite
if
T-L 2 Σ
L
72a llog
2.8 log
110 A
+
+3)) (4.1)
Tog ++)
([+E)3
A?
i=1
In particular, the bound on er in
4.1 holds when 7 2 m (A, H2), where
(1A, 2. 6v2.8o0 + e)2 + 3 exp (1 + A 2
T-
For all T 1, when y assumes its lower bound 7/2 (A, H2), we have
er S δ (Lexp(-TA (1440(1++)) H2 - ))
T-L
(4.2)
When T >>> L, the gap between our upper bound in 4.2 and M(exp( (exxp(40002) 400T (H, log L))), lower bound (Carpenticr & Locatelli 2016), manifested by the (pre-cxponential) term as well as the constant in the exponent. This indicates that BoBW-LL'UCHE LCC()) can be adjusted to perform near-optimally for BAI over fixed horizon.
the state-of-thhr the art

---

Published in Transactions on Machine Learning Research (09/2023)
Further observation. As discussed earlier, BoBW-LH'UCB()) encourages more exploitation than exploration when is large (e.g. 7 (log T)) and it stimulates more exploration when 7 is small (e.g. y= (A, H2)).. Besides, Theorems 4.1 and 4.2 imply that the pseudo-regret of BoBW-LL' BoBW-un'UCBBC decreases with y while its failure probability increases with y. Therefore, to minimize the regret, we should increase y to stimulate exploitation; and we should decrease y to encourage exploration for oblaining small failure probability. This indicates that an optimal RM algorithm encourages more exploitation compared to an optimal BAI one, and vice versa.
5
Pareto Frontier of RM and BAI
Theorems 4.1 and 4.2 together suggest that BOBW-LL'UCB(()) cannot perform optimally for both RM and BAT simultaneously with a universal (or single) choice of y. In this section, prove that no algorithm can perform optimally for these two objectives simultaneously. Given a certain failure probability of an algorithm, our goal is to establish a non-trivial lower bound on its pscudo-regret.
We first consider bandit instances in which items have bounded rewards. Tet (A, R) denote the set of stochastic instances where (i) the minimal optimality gap A Z A; and (ii) there exists Ro E R such that the rewards are bounded in [Ro, Ro + R). Let (2, R, H2) denote the set of instances that (i) belong to (A. R), and (ii) have hardness quantities H₂ S H2. Theorem 5.1. Let ΦT, R, > O. Let a be any algorithm with (T, S exp(-or)/4 for all I e (A R). Then
sup RT( 2 Φ8 (L 1)R (A.T)
AH₂R*
sup (A.
RT I) 2 ΦT
8A
In Theorem 5.1 we apply the bounds Ro and Ro + R on items' rewards to classify instances. In general,
Al2 < (L- 1)/A A holds for any instance, and equality holds when A = for all i + 1. Therefore, (A, Rt) = B2 R, (I. - 1)/A2)). When It > 1, the analysis for the set (2 (T- (L- ())( better bound (higher lower bound) for the set B (A, R).
)) provides a
Our non-asymptotic bounds complete the asymptotic observation on the trade-off between regret and BAI in Lattimore & Szepesvári (2020) and quantify how the trade-off depends on the hardness quantity H2 and gap As,'s of an instance, instead of fixed constants such as Another relevant work is Bubeck et al. (2009). On one hand, Bubeck et al. (2009) explores the trade-off between the cunulative regrel. Rr and the simple regret FT and shows that any algorithm with Ry < CT) satisfies FT 2 A eex((DD((T))2 in some instance. On the other hand, our work studies the Parcto frontier Ry and the BAI failure probability er. Since êT and PT satisfy that A er $ TT I er, our Theorem 5.1 indicates that
Corollary 5.2. Let ΦT, A > 0. Let w be any algorithe salisfying
--1 sup RT(T, I) S ØT IA.1(A.1)
8A
then eT 2 exp(- and rr 2 A eexp(-0r)/4
In view of Corollary 5.2 we have precisely quantified that C= ([L-1)/(8)) and D 1 in the work of Bubeck
et al. 2009).
Furthermore, we establish a similar analysis for instances in which the variance of each item's 's reward distribution is bounded. Let (A, V) denote the set of instances where (i) the minimal optimality gap A > A: (ii) for each item i, the variance of < V. Let (A V, H2) denote the set of instances (i) that belong to B (A. V), and (ii) have hardness quantitics H2 S H2. The key difference between the proofs of these two theorems lies in the design of hard instances. We elaborate on the details in Appendix E
Theorem 5.3. Let dr, A, V.H. H2 > O. Let be any algorithm with er (T S exp( ΦT //4 for all I e (A.V). V).
(AA,V
Then
RT( dr. (L-1)V 1)V
AH&V
sup (A
sup AE
RT(T, I) 2 ΦT
2A
7

---

Published in Transactions on Machine Learning Research (09/2023)
By characterizing stochastic rewards with different statistics, Theorems 5.1 and 5.3
provide different lower
bounds on the pseudo-regret, We observe that when the rewards of items are bounded in [Ro: Ro + R] for some Ry E R, the variances of the rewards are bounded by R², /4. Therefore,
R²
R
(A R) C
A
BA R H2) C
B3
A
H2
4
4
Besides, it clear that
R C
R
(A Rt), T, B3J
A 4
Th
Bi
4
Due to the relationship among these four sets of instances, we let π be an algorithm with er (T & exp(-or)/4 in any instance of B3 (A, R² /4), and compare the derived lower bounds on its pseudo-regret [x, in Table 5.1 Table 5.1 indicates that
when the bound for B (A, R) (second column of Table 5.1 holds for B (4, R /4), the quantities L and
A are of the same order in the bounds derived for (A, T?) and (4 Tt' /4) respectively;
similarly, when the bound for (A, H2) (third column) holds for (A, R /4, H2), the quantities L and A are of the same order in the bounds for B2(A, R, H2) and B A. R H2))
Table 5.1: Lower bounds on Ry when eT Se-0r/i /4.
Instance Set (A. R)
(2 R. H2)
(A R² /4)
(4 R /4, H2)
Bound on Rr ΦT (I-11)/(8AA)
Φr AH /8
ØT (I. -I-11) (8A)
ΦT A H R² /8
Moreover, when R 1, we can apply the analysis of (A R, H2) to obtain a better bound (higher lower bound) for (A R² H2).
In any set of instances studied in Theorems 5.1 or 5.3
when Φr lincarly grows with T, which typical the bounds on er (Karnin et al. 2013 Carpentier Locatelli 2016), the corresponding bound on Pr grows linearly with (vacuous);
when the bound on Rr grows with log T as in Garivier & Cappé (001 and Lai & Robbins 1985 ΦT grows logarithmically with T (i.e., the failure probability only decays polynomially).
Thus, we cannot achieve optimal performances for both RM and BAI using any algorithm with fixed parameters. Alternatively, we can apply BOBW-LL'UCB(G to achieve the best of both objectives with proper choices of the single parameter 7.
When the time horizon T' is sufficiently large, an optimal or near-optimal RM algorithm, i.e., an algoirthm that achioves the optimal regret with order OllogT/A) usually pulls the optimal item T - oT)) times and all the suboptimal items for (log (A²?)) times; a good BAI algorithm usually focuses on the best and the second best items and pulls them for roughly the same number of times to distinguish between them. This implies that the proportion of item pulls in an order-wise optimal RM algorithm, such as UCB1, vastly different from the optimal proportion of item pulls in an BAI algorithm. Hence, a bandit algorithm that is tailored to the regret minimization task, is unlikely to yield low failure probability er, i.e., one that has a hardness parameter in the exponent close to H2.
Tightness of the upper and lower bounds. We compare the upper and lower bounds on the pseudo-regret of BOBW-LIL' UCB(7) when the horizon T + 20.
Corollary 5.4. Define the interval I(v,
TVv T) In (A, H2), min (log(B +1+ e)/c, (log 1//T,1/Y which is funclion of the instance and the fized horizon T. When I(v, T) * 0,lel no denole the online algorithom
BoBW-LI' UUC(()) with satisfying the condition that 7 E I(v, Then
RT( I) E E AH2 log
1
log )
sup
A
(EB..A
8

---

Published in Transactions on Machine Learning Research (09/2023)
We observe from Corollary 5.4 which combines Theorems 4.1
4.2 and 5.1 that the gap between the upper and lower bounds depend on the term AH₂ in the lower bound and L/A in the upper bound. As H2 < (1-1)4- -2 for any instance, when A = Á1, for all * 1 (all suboptimal items have the same suboptimality gap), equality holds, and hence the bounds match up to a small additive log(1/L) term. Corollary 5.4 implies that the parameter 7 in -OBW-LI--CCB()) is essential in tuning the algorithm such that can perform optimally for either RM or BAI. This implies that some regimes, BOBW-LI-UCBB()) achieves Pareto-optimality up to constant or small additive (e.g,, log(1/L)) terms.
Besides, to show that there are cases for which I(v, T) # 0, we use several examples here. In the instance where L = 256, W1 0.5, wi 0.45 for i + and rewards are drawn from Bernoulli distributions, if we let = 0.01, 3 = e, I(v T) is always non-empty when time horizon T 2 10t as shown in Table 5.2
Table 5.2: Intervals I(v, T) under different time horizons T Time horizon T I(v, T)
106
[1.85 x 10-?,
1.38 x 10 10-5]
107
[4.33 x 10 -3
1.61 x 10 10-6)
10
[0,
1.84 x 10-7]
109
[0,
2.07 x 10-8)
Furthermore, Corollary 5.4 suggests that the lower bound in Theorem 5.1 is almost tight, as it is achieved by BoBW-Ln'UCB()) Hence, up to terms logarithmic in the parameters such as L, we have quantified the Pareto frontier for the trade-off between RM and BAI in stochastic bandits.
6 Numerical Experiments
We mumerically compare BoBW-LI'UCB(() and UCB, they are the only algorithms that can be tuned to perform (near-) Jottmally for both RM and BAI. Since BoBW-LL'UCB(c) is designed for the exed-budget setting and UCB, is for the fixed-confidence setting, there cannot be a completely fair comparison between them. However, we attempt to perform fair comparisons as much as possible.
We evaluate the algorithms with both synthetic and real data. For BOBW-LL'UCB(G we fix 0.01, for T (fixed in specific instance)
B = e, and vary 7. For UCBa, we vary a. We run BoBW-L.n time steps, when the horizon (stopping time) of UCB, depends on its stopping rule and the instance. Due to the difference between the fixed-horizon and fixed-confidence settings, the regrets of each algorithm may be accumulated over different time horizons.
For each choice of algorithm and instance, we run 10 independent trials. Since the empirical failure probability of BoBW-L.. (UCB()) below 1% each instance (see Table H.1 in Appendix H.T), we set = 0.01 for UCB,, which guarantees that the failure probability of UCB, also below 1%. We also present the experiment results with empirical failure probabilities below 2% in Appendix H (where UCB.). We focus the comparison on (i) the time horizon each algorithm runs; and (ii) the regret incurred over its corresponding horizon. We present the averages and standard deviations of the time horizons and redthe regrets of each algorithm. More numerical results that reinforce the conclusions herein are presented in Appendix
set 5 = 0.02 for
6.1 Experiments using synthetic data
We set w1 = 0.5, and w, = 0.5 - A for all i + 1. We let Bern(a) denote the Bernoulli distribution with parameter a. We consider Bernoulli bandits, i.c., ii Bern(w:). We display some numerical results in Figure 6.1 more results are postponed to Appendix H.3
2H2 has the same units as T.- A---; hence, the terms in Q()) and O(-) also have the same units.
9

---

Published in Transactions on Machine Learning Research (09/2023)
BoBW-Ii'UCBCy)
UCB,
B9 1)
BoBW(9 x 10
Algorithm
BoBW((9 10-9)
Algorithm
BoBW(9 10-4)
BoBW((9 10-")
BoBW(9 x 10-7)
UCB
UCB
UCB4
UCB45
U.B
UCBg.0
0.0
2.5
5.0
0
Time Horizon 1e5
Regret
1e4
Time Horizon 1e5
Regret
1e4
Figure 6.1: Bernoulli instances with L-64, failure probability 11%. Left: = right: A A.1.1
Under each instance presented Figure 6.1 the regret of (oBW-Ln:'CCB()) reduced when 7 grows (see Table H.3 for exact values), which corroborates with Theorem Both the regret and the stopping time of UCB, grow with a, which corroborates with Degenne et al. (2019 Theorem 3). Moreover, observe that the standard deviations of the regrets are larger for UCB, compared to NOBW-LI'UCB(Y, which suggests that BoBW-LIL" (OB(+L) is more statistically robust and consistent in terms of the regret. Note that a larger A means that the difference between the optimal and suboptimal items is more pronounced, resulting in an easier instance. Given a fixed horizon T, our BoBW-LII (UC(()) algorithm outperforms the UCB, algorithm with a varying range of parameters and a in instances with different values of A.
6.2 Experiments on real datasets
We use two real-world datascts, the MovieLens 25M (ML-25M) dataset HHarper & Konstan 2015) and the Published Kinase Inhibilor Sel 2 (PKIS2) dataset (Drwrry et al. 2017). to evaluate the performances of and UCBa in two types of practical applications, namely, content recommendation and drug recovery. Similarly as in Zong et al. (2016); Hong al.) (2020): Zhong al. 2202bb; Mason et al. (020): Mukherjee al. (2021). we generate data based on the real-world datasots.
ML-25M dataset. GroupLenn Research provides collection of catasetss online iincluding the ML-25M dataset. These datasets describe the rating activities from MovieLens, movie recommendation service, and are widely used to evaluate the performances of bandit algorithms (Zong et al. 2016 Hong et al. 2020 Zhong
et al. 2021b The MI.-25M dataset contains about 25 million ratings across about 62 thousand movies. We choose movies with a high number ratings in our simulations. For each selected movie, we compute the empirical mean rating and generate random ratings according
standard Gaussian distribution with the corresponding mean. We aim to obtain cumulatively high ratings (RM) and identify the movie with the highest rating (BAT); these are standard objectives in online recommendation systems.
PKIS2 dataset. This repository lests 641 small molecule compounds (kinase inhibitor) against 406 protein kinases. This experiment aims to find the most effective inihibitor against a targeted kinase, and is a fundamental study in cancer drug discovery. The entrics in PKIS2 indicate the percentage control of cach inhibitor, which show the elfectiveness of inhibitors and follow log-normal distributions Blrristmaun-Frann et al. 2016). Accordingly, we generate random variables as in Mason et al. (2020): MMkkeerjee al. (2021) (see Appendix H.44 for details). We aim to find out the most effective inhibitor with the highest percentage control against specific kinase MAPKAPK5, and also obtain high percentage controls cumulatively during the online learning process. Our study may aid in understanding how best to design experimental studies that aim to identify the most effective inhibitor in a fixed number of tests (BAI in a fixed horizon), as well as to provide effective inhibitors throughout the course of study (RM).
On the left of Figure 6.2. we report. the results of the experiments on the movies with at least 50, 000 ratings from the MI.225M datasct. The other plot Figure 6.2 considers the effectiveness of 109 inhibitors test against the MAPKAPK5 kinase in the PKIS2 dataset. Both figures suggest that with high probability,
Table httpp::///ww.....// www.bii....ooo..... http::/w.w...ttaaoeoo....toottte
10

---

Published in Transactions on Machine Learning Research (09/2023)
BoBW(99 4
BoBW((9 x 10"1) 3
Algorithm
BoBW(9 10
Algorithm
BoBW(9 x 10
BoBW(99 1
BoBW(9 x 10"")
0CBs
UCBs.0
5CB
UCB4.5
UCBg.
UCB6.0
Time Horizon le4
Regret
1e4
Time Horizon 1e7
Regret
1e7
Figure 6.2: Empirical failure probability & 1%. Left: MI-25M dataset; right: PKIS2 dataset.
BoBW-nn'UCBC) can identify the most popular movie with the highest rating the most effective inhibitor against MAPKAPK5 with the highest percentage control within fixed horizon. UCB, takes longer to do so, and also suffers from larger regret. These results from the real-life datasets suggest that given a fixed horizon T' and a wide range of parameters, BoB W-LIL'UCB()) outperforms UCB, in these real-life instances, which demonstrates the potential of BoBW-Ln,UCCB()) in practical settings.
Acknowledgments
This work is supported by funding from CIFAR through Amii and NSERC and the Singapore Ministry of Education Academic Research Fund (AcRF) Tier 2 under grant numbers A-8000423-00-00 and A-8000084-01, as well as AcRF Tier under grant numbers A-8000980-00-00 and A-8000189-01-000
References
Yasin Abbasi- Yadkori, Peter Bartlett, Victor Gabillon, Alan Malek, and Michal Valko. Best of both worlds: Stochastic & adversarial best-arm identification. In Proceedinggs of the 31st Conference On Leurning Theory, volume of Proceedings of Machine Learning Research, pp. 918-949. PMLR, 06-09 Jul 2018.
Milton Abramowitz and Irene A. Stegun. Handbook of Mathematical Functions with Formulos, Graphs, and Mathematical Tables. Dover, New York, ninth edition, 1964.
Shipra Agrawal and Navin Goyal. Analysis of Thompson sampling for the multi-armed bandit problem. Proceedings of the 25th Annual Conference on Learning Theory, pp. 39.1-39.26, 2012.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In Proceedings of the 30th International Conference on Machine Learning, volume 28, pp. 127- 135, 2013.
Shipra Agrawal and Navin Goyal. Near-optimal regret bounds for Thompson sampling. Journal of the ACM (JACM), 64(5):1 24, 2017.
Jean-Yves Andibert and Sébastien Bubeck. Best arm identification in multi-armed bandits. In Proceedings of the 23th Conference on Learning Theory, pp. 41 53, 2010.
Peter Auer, Nicolo Cesa- Bianchia and Paul Fischer. Finito-time analysis of the multiarmed bandit problem. Machine Learning, 47(2-3):235 256, 2002a.
Peter Auer, Nicolò Gesa-Bianchi Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SLAM Journal of Computing, 32(1):48 77, 2002b.
Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in multi-armed bandits problems. In The 20st International conference on Algorithmic learning theory, pp. 23 37. Springer, 2009.
Sébastien Bubeck, Nicolo bandit problems. Foundations and Trends0 in Machine Learning, 5(1):1 122, 2012.
et al. Regret analysis of stochastic and nonstochastic multi-armed
Séebastian Bubeck, Tengyao Wang, and Nitin Viswanathan. Multiple identifications in multi-armed bandits. In Proceedings of the 30th International Conference Machine Learning, pp. 258 265, 2013.
11

---

Published in Transactions on Machine Learning Research (09/2023)
Alexandra Carpentier and Andrea Locatelli. Tight (lower) bounds for the fixed budget best arm identification bandit problem. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir (eds.), 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pp. 590 604, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR.
Serge Christmann-Prandee Gerard JP van Westen, George Papadatos, Fanny Beltran Escudie, Alexander Roberts, John P Overington, and Daniel Domine. Unprecedently large-scale kinase inhibitor set enabling the accurate prediction of compound -inasee activities: A way toward selective promiscuity by design? Journal of chemical information and modeling. 56(9):1654-1675, 2016.
Fan Chung and Linyuan Lu. Concentration inequalities and martingale inequalities: survey. Internet Mathematics, 3(1):79 127, 2006.
Do A Darling and Herbert Robbins. Iterated logarithm inequalities. Proceedings of the National Academy of Sciences of the United States of America, 57(5):1188, 1967.
Rémy Degenne, Thomas Nedelec, Clement Calauzenes, and Vianney Perchet. Bridging the gap between regret minimization and best arm identification, with application to A/B tests. In Proceedingss of the 22nd International Conference on Artificial Intelligence and Slatistics, pp. 1988-1996, 2019.
David H Drewry, Carrow Wells, David M Andrews, Richard Augell, Hassan Al-Ali, Alison Axtman, Stephen Capuzzi, Jonathan M Elkins, Peter Ettmayer, Mathias Frederiksen, et al. Progress towards a public chemogenomic set for protein kinases and call for contributions. PloS one, 12(())e0181555, 2017.
Devdatt P Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009.
Victor Gabillon, Mohammad Ghavanzadeh, and Alessandro Lazaric. Best arm identification: A unified approach to fixed budget and fixed confidence. In Proceedings of the 25th International Conference on Neural Information Processing Systems, 2012.
Aurélien Garivier and Olivier Cappé. The kl-ucb algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th Annual Conference on Learning Theory, pp. 359-376, 2011.
Sébastien Gerchinovitz and Tor Lattimore. Refined lower bounds for adversarial bandits. In Proceedings of the 29th International Conference Newral Information Processing Systems, pp. 1198 1206, 2016.
Friedrich Götze, Holger Sambale, and Arthur Simulis. Higher order concentration for functions of weakly dependent random variables. Electronic Journal of Probability, 24:1 19, 2019.
F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (this), 5(4): 19, 2015.
Joey Hong, Branislav Kveton, Manzil Zaheer, Yinlam Chow, Amr Ahmed, and Craig Boutilier. Latent bandits revisited. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Proceedings of the 34th Advances in Neural Information Processing Systems, volume 33, pp. 114433.. Curran Associates, Inc., 2020.
Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck. lil'ueb: An optimal exploration algorithm for multi-armed bandits. In Proceedings of the 27th Conference on Learning Theory, pp. 423 923-439, 2014.
Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In
Proceedings of the 13th International Conference on Machine Learning, pp. 1238 1246, 2013.
Emilie Kaufmann and Aurélien Garivier. Learning the distribution with largest mean: two bandit frameworks. ESAIM: Proceedings and surveys, 60:114-131, 2017.
Emilie Kaufmann and Shivaram Kalyanakrishnan. Information complexity in bandit subset selection. In Proceedings of the 26th Annual Conference on Learning Theory, pp. 228 251, 2013.
12

---

Shahin Shahrampour, Mohammad Noshad, and Vahid Tarokh. On sequential elimination algorithms for best-arm identification in multi-armed bandits. IEEE Transactions on Signal Processing, 65(16):4281-4292 2017. doi: 2..109//SPP2011.27700 Published in Transactions on Machine Learning Research (09/2023)
Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1): 2016.
Wonyoung Kim, Garud Iyengar, and Assaf Zeevi. Pareto front identification with regret minimization, 2023.
Tze Leung Lai and Herbert Robbins. Asymplotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-2 22, 1985.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Blake Mason, Lalit Jain, Ardhendu Tripathy, and Robert Nowak. Finding all e-good arms in stochastic bandits. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Proceedings of the 34th Advances in Neural Information Processing Systems, volume 33, pp. 20707 20718. Curran Associates, Inc., 2020.
Arpan Mukherjee, Ali Tajer, Pin-Yu Yu Chen, and Payel Das. Mean-based best arm identification in stochastic bandits under reward contamination. In Proceedingg of the 35th Advances in Newrul In Information Processing Systems, 2021.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathemalics of Operalions Research, 39(4):122) 1243, 2014.
David Simchi-Levi and Chonghuan Wang. Multi-armed bandit experimental design: Online decision-making and adaptive inference. In Francisco Ruiz, Jennifer Dy, and Jan- Willem van de Meent (eds.), Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 3086 3097. PMLR, 25 27 Apr 2023.
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Publishing Company, Incorpo- rated, 1st edition, 2008. ISBN 0387790519.
Chen-Yu Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Proceedings of the 31st Conference on Learning Theory, pp.
PMLR, 2018
Zixin Zhong, Wang Chi Cheung, and Vincent Tan. Probabilistic sequential shrinking: A best arm identification algorithm for stochastic bandits with corruptions. In Proceedings of the 38th International Conference on Machine Learning, 2021a.
Zixin Zhong, Wang Chi Cheung, and Vincent Y. F. Tan. Thompson sampling algorithms for cascading bandits. Journal of Machine Learning Research, 22(218):1-66, 2021b.
Julian Zimmert and Yevgeny Seldin. Tsallis-INF An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22:28-1, 2021.
Shi Zong, Hao Ni, Kenny Sung, Nan Rosemary Ke, Zheng Wen, and Branislav Kveton. Cascading bandits for large-scale recommendation problems. In Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, pp. 835 844, 2016.
13

---

Published in Transactions on Machine Learning Research (09/2023)
Supplementary Material for " "Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits
discuss the existing algorithms and relevant theoretical findings in stochastic bandits. B we (i) study the performance of UP-ADV (Audibert & Bubock 2010) and EXP3.P (Auer) ct al. 2002b) for both RM and BAI in adversarial bandits, and (ii) provide a lower bound on the BAI failure
In Appendix
In Appendix
probability and the Pareto frontier of RM and BAT in adversarial bandits. In Appendix C we list. the useful
facts that are used the analysis. In Appendices D to we present detailed proofs of our theoretical results. In Appendix H more numerical results are provided.
A Detailed discussion on existing algorithms
While most existing works only aim to perform either RM BAI, Degenne et al. (2019) designed and analyzed an algorithm called UCB, for both RM and BAI under the (ureddconfidencc selting, Given any 6, UCB, aims to minimize the number of time steps so that < 6, and, at the same time, the incurred regret Ry can also be upper bounded. Therefore, the focus of Degenne et al. (2019) differs from that of our work. We aim to study the pscudo-regret of an algorithm which can identify the best item with high probability a fized horizon T in this work.
To the best of our knowledge, their no existing work that analyzes single algorithm for both RM and BAI under the fixed- fixed-budget setting. However, it is natural to question if an algorithm which is originally designed for RM can also perform well for BAT, and vice versa. We study some algorithms that are originally designed to achieve optimal performance for cither RM or BAI.
RM. According to the discussions on RM and BAI in Lattimore & Szepesvári 2020 (see the second point in Note 33.3), for any algorithm with a regret that (nearly) matches the state-of-the lower bound (Carpentier & Locatelli 2016):
Rr(T) log
A (L(
lim inf T
1
we can ronstruct two instances I and I' with
f > W 2 w
wf = wx + + - wf), for some e
such that
cr(m, + (I) 2 (
(A.1)
This serves as a basic observation on the limitation for BAI of an algorithm that performs (oetr-)op for RM.
BAI. Audibert & Bubeck (2010) were the first to explore the BAI problem under the fixed-budget setting. Carpentier & Locatelli (2016) provided lower bound the failure probability of any algorithı..
In the spirit of UCB1 (Aur et al. 2002ah, Audibert & Bubeck (2010) designed UCB-E for BAL We let UCB-E(() denote the UCB-E algorithm when it is run with paramcter a. When T is sufficiontly large, wo can upper bound the pseudo-regret of UCB-E(a log T) (a 2 2) with a similar analysis as that for UCBI (see Proof of Theorem in Auer al. (2002a)) ). Besides, we can upper bound its failure probability with
Theorem 1 in Audibert & Bubeck (2010)
14

---

Published in Transactions on Machine Learning Research (09/2023)
Corollary A.1. Let 12.5. Assume that 96.6 E [0, 1] for all [L], and a T S 25(T ())(3)
UCB-E(a T) satisfies
R S 2a
Σ
log
+ 1+ n² )
Σ A..)) i#1
1
3
eT S (1
When the horizon T grows, Corollary A.1 indicates that the BAI failure probability of UCB-E(( log T) decays only polynomially fast. In order to achieve the upper bound ey exp(-O(T)), need to set a O(T/ log/ 7 and hence the regret bound as shown in Corollary A.1 will be O(T2/1og T), which is vacuous.
A.1 Existing results under the fxxde-budeet setting of BAI
We abbreviate SEQUENTIAL REJECTS as SR, SEQUENTIAL HALVING as SH, NONLINEAR SEQUENTIAL ELIMINATION with parameter p as NSE(p). Besides, we simplify the bounds for algorithms which were initially analyzed for more general problems than identification of the optimal item i* we define
I A
Hy max
Cp:=2
Σ TD
for >> 0 as in Shahrampour et al. (2017] We let UGAPEB(() denote the UGAPEB algorithm when it is run with parameter a. In Table A.1 We present existing bounds from some seminal works. The algorithms are listed in chronological order.
Table A.1: Comparison under the fixed-budget setting of BAI: upper bounds for algorithms and lower bounds in stochastic bandits.
Algorithm/Instance
Reference
Failure probability eT
25(T - L)
2T (- T T-
UCB-E
Audibert & Bubeck (2010)
36HHz
18112
T-L
SR
Audibert Bubeck (010
L(L - 1xexp
(1/2 + Ele 1/1)
T 1.
T T-
UGAPEB
Gabillon et al. (2012)
2T exp
16112
8112
T
SAR
Bubeck et al.
(2013)
2D exp
8(1/2 + Ei' 1/1)
T 8H2 log, L
SH
Karnin al.
(2013
3 llgg L L. exp exp
2(T L) H₁Cr
NSE(p)
Shahrampour et al. (2017)
(L. (1-11 (1-1)exp exp
4007' H2 log L
Stochastic Bandits
Carpentier & Locatelli (2016
exp
(Lower Bound)
Since SH and NSE pull a number of items "uniformly" in each phase, we surmise the regret grows like O For instance, there are log many phases in SH and at least two items uniformly pulled during each
15

---

Published in Transactions on Machine Learning Research (09/2023)
phase, at least one non-optimal item j # 1 is pulled for at least T/(L log L) times, leading to regret at least A.. [7[(Llog] T.).
As discussed in Shahrampour et al. (2017) H S H2 log L in some special cases. Therefore, SH is better than NpE(p) if we disregard the eab-ennonential term, while NSE(p) is better in some cases in its dependence on the exponential term. However, they are incomparable in general.
B Conclusion and Further Discussion on Adversarial Bandits
In Sections 5 and G we explore the Pareto frontier of RM and BAI over fixed horizon in stochastic bandits. The performance of our BoBW-LIL' UCB algorithm sheds light on the different emphases of RMM and BAI. Moreover, we prove that no algorithm can simultaneously perform optimally for both objectives and BoB W-LIL' UCB nearly achieves the Pareto-optimalltyy in some parameter regimes. However, as described in the discussion after Corollary 5.4 although our BOBW-LIL' UCB algorithm nearly achioves the Pareto Trontier, we acknowledge that there remains a small gap log(1/L) which may be closed in the future by developing another more sophisticated algorithm.
In real-life applications, it may be unrcalistic to assume i..d. stochastic rewards,meaning that the stochastic bandit model may not be appropriate. This brings the study of adversarial bandils (Auer et al. 2002b Abbasi- Yadkori et al., 2018) to the fore. Here, the rewards of each item are not necessarily drawn independently from the same distribution. In adversarial bandits, while there exists lower bound on the regret of any algorithm (Gerchinovizz & Lattimore 2016), there no lower bound on the failure probability for BAI. We fill this gap by proving a lower bound 2[exp(-15072) ?)) Theorem B.3 where A the minimal gap between the empirically-optine is almost tight it nearly matches the upper bound of UP-ADV (Abbasi- Yadkori al. 2018
items and the other items (see Appendix B. for the definitions). This bound
Furthermore, there is no existing analysis of a single algorithm that is applicable to both RM and BAT in adversarial bandits. We fill this gap by studying the performance of EXP3.P(T,,) 1) (Auer et al. 2002b) for both largets. Theorems B.1 and B.2 imply that by adjusting ExP3. P(7; 17) with 7, we can balance ween exploitation and exploration, and trade-off between the twin objectives: R.M and BAI. Besides, Theorem B.4 implics that no algorithm can simultancously perform optimally for both objectives in adversarial bandits. However, since the regret bound of ExP3.P(7; 7)) is problen-inddependenl, we cannot ascertain if ExP3. (1,. v) achieves the Pareto frontier between RM and BAI. The further study of the Pareto frontier in adversarial
bandits, especially the stochastically constrained adversarial bandits Zimmert & Seldin 2021 2018 may serve as an interesting direction for future work.
Wei & Luo
Outline. this section, we first formulate the RM and BAT problem in adversarial bandits in Appendix B.1 Next, we study the performance of UP-ADV (Audibert & Bubeck 2010) and ExP3.P (Auer et al.) 2002b for
both RM and BAI in Appendix B.2 Subsequently, we provide a lower bound on the BAI failure probability and the Pareto frontier of RM and BAT in Appendix B33] We summarize some theoretical findings in Table B.
B.1 Problem setup for adversarial bandits
In an adversarial bandit instance, we let gr.t E [0, 1] be the reward of item at time t, and let Gi,t := Et. 1 Fi. for all S SLST. T. We define the Aig.T empirical gop ween item i and in [T]] and the empirically-oplimall item it as follows:
A.ST := T -Gi,-G i = arg max GeT.
18iLL
Moreover, we define the empirically-minimal optimality gap as
A := min A "ip.
16

---

Published in Transactions on Machine Learning Research (09/2023)
We say instance is obliviously adversaria f the instance before online process. We assume the empirically-optinge item v7 is unique, which implies that AminT > O.
if {gu.)., e is sequence of rewards obliviously generated by
Moreover, we define the empirical-regret RG of an online algorithm и (as defined in Section as
T
T
R7 = max
9i.t
Σ Dip. = G pq.
Recall the definition of pseudo-regret (x) in Section 2 an instance is stochastic, ERj RG; is adversarial, ERG < R7. The aim of the agent slightly different in stochastic and adversarial bandits:
if the instance stochastic, the algorithm æ aims to both minimize the pscudo-regret R and identify the pseudo-optimal item with high probability, ie., to minimize eT(T) == Pr(cout * i7:); if the instance is adversarial, the algorithm aims to both minimize the empirical-regret RT(T)) and identify the empirically-optinall item with high probability, Le., to minimize ēr(π) Pr(fout * i7).
We omit T and/or in the superscript or subscript when there no cause of confusion. We write ( as (T I) (T) ( when we wish to emphasize their dependence both the algorithm and the instance I.
B.2 Adversarial algorithms: UP-ADV and EXP3.P
We discuss the theoretical performances of two basic algorithms in this section.
Hence, take the performance of this basic algorithm benchmark evaluate any algorithm for this target. Besides, it is clearly that the uniform pull algorithm is the same as Exp3.P algorithm with B = 0, 7=1 1. We see that UP-ADV satisfies that EîT < T, which is consistent with Theorem B.2
The UP-ADV algorithm. First of all, Abbasi- Yadkori et al. (2018) shows that a simple algorithm, which is termed as UP-ADV and chooses an item based on the uniform distribution at cach time step t, satisfics that
ē S Lexp (-
3
(B.1)
28L
Abbasi- Yadkori et al. (2018) claimed that UP-ADV performs near-optimally for BAI in adversarial bandits, which is verified by our Theorem B.3 in the next section. Besides, it is obvious that UP-ADV satisfies ER T.
A Algorithm UNIFORM PULL-ADV (UP-ADV) AAbasii- Ybbkaii-Yadkori et al. 2018
1: Input: time budget T, size of ground set of items
2: for 1= do
Choose item i, E [L] with probability 1/L.
Update the estimated cumulative gain Gi = Et Hi.u lifi = i}.
end for
6: Output iout = arg max GCT-
The ExP3.P P algorithm. After the ExP3 algorithm and its variations were proposed by Auer et al. 2002b for RM in adversarial bandits, this class of algorithms has been widely discussed as in Lattimore & Szepesvári 2020 Bubeck et al. (2012). We present EXP3.P(y,n) 1)) in Algorithm g
We first provide the upper bound on the regret of ExP3. m)) The proof similar that in Bubeck et al. 2012) and is postponed to Appendix F.]
When there no ambiguity, we say instance adversarial indicate that it obliviously adversarial.
17

---

Published in Transactions on Machine Learning Research (09/2023)
Algorithm Exp3.P(7,n) n) (Bubeck et al. (2012), Section 3.3, Fig. 3.1)
1: Input: time budget T, size of ground set of itemss L, parameters n> 0 and E [0, 1/.
2: Set pi be the uniform distribution over [L], ie., Pi, = 1/L E [L].
3: for t .,..., do
Choose item & E [L] with probability Pt,1- Compute the estimated gain for each item
Ii.t Di.s If o}
Pi,
and update the estimated cumulative gain Gi.- = Σv= Tigu-
Compute the new probability distribution over the items Pi+1 = (PI.:tt...., where
exp(nGs.))
+ 7 Etzres exp(nGre,) T.
Pi++1 = (1 (1)))-
7: end for
Output Yout = arg max GGT-
Theorem B.1 (Bounds on the regret of EXP3.P(1.))) Let 1 n> 0, Y E [0, 1/2] salisfying that Taj S 7y- Then we can upper bound the regret of ExP3. n) follows. (i) Pix any given ô (0, 1), with probability at least 5,
L2T 176
In
Rr S + In
+
( Moreover,
LPT
In
ER STT + nLT + In
+
+1.
7
We observe that EL, is exactly the same UP-ADV, and the corresponding bound provided in Theorem B.2 is with the same order as in (B.1) derived by Abbasi- et al. (2018). Our upper bound is even slightly smaller regarding the constants since we apply lighter concentration inequalities. Next, we upper bound its failure probability to identify the empirically-optimaa item 77
Theorem B.2 (Bound on the failure probability of ExP3.P). Assume GLT 2 G2, 2 ... 2 GL,T. We see that the optimal ûtem ē = 1. The failure probability of ExP3.P(7,1) satisfies
TT 4L
377(A1227/22 22.,T)²
(-TAA}
ēr S exp
Σ
exp
< Lexp
L(3 + 21, A2.TT)
4L
The key idea among the analysis of Theorem for all i E [Z] with Thcorems C.2 and C.3 The detailed proof is postponed to Appendix F.2
B.2 is to derive high-probabiilty one-sided bounds on G G
Theorems
B. and B.2 imply that by adjusting P(7, with we can balance between exploitation and exploration and trade-off between the twin objectives RM and BAL detail,
When y increases, the ExP3.P 77) algorithm tends to bahave more similarly to UP-ADV, which leads to larger regret and smaller failure probability. This indicates that large ? encourages exploitation.
When ? decreases, the ExP3.P(<: n)) algorithm tends to emphasize more on the observation from previous time steps and pull the items with high empirically means, which leads a smaller regret and larger failure probability. In other words, small encourages exploitation.
18

---

Published in Transactions on Machine Learning Research (09/2023)
B.3 Global performances of adversarial algorithms
In this section, we first lower bound the failure probability to identify the empirically-optinal item in adversarial bandits. Next, given a certain failure probability of an algorithm, we establish non-trivial lower bound on its empirical-rogret. The proofs are in Appendix G
We consider bandit instances which items have bounded rewards. Let Bi R) denole the set. of instances where (i) the empirically-miinn minimall optimality gap Ar 2 Ar in T time steps; and (ii) there exists Rg R such the rewards are bounded in [Ro, Ro + RJ. We focus on B, (Ar, 1) for brevity; the analysis can be generalized for any B₁ (A, R).
B.3.1 Lower bound on the BAI failure probability in adversarial bandits Then any algorithm. x satisfies that
Thcorem B.3. Let 0 < Ar S
(π( 1
150T A
sup 1l
exp
4
Furthermore, when 2 10,
2 65
1507 A
sup (T( 2 exp (A,,
We construct L instances with clipped Gaussian distributions, which similar to those cesigned for the analysis of lower bound regret in Gerchinovitz & Lattimore (2016).
Besides, the gap between our lower bound in Theorem B.3 and the upper bounds of UP-ADV/EXP3.PP in [B.1] and Theorem B.2 is manifested by the (pre-exponentiaa) term as well as the constant in the exponential term. This indicates that UP-ADV (P-ADV/ExP3.P(11)) n) perform near-optimally for BAI and our lower
bound in Theorem B.3 almost tight.
B.3.2 Trade-off between RM and BAI in adversarial bandits
Theorem B.4. Lel A < and T 2 10. Lel n be any algorills with (T S 2 for all E B (A,, Then
L-1
sup ER vT 1034,
TeB (A
Theorem B.4 implies that, as shown for the stochastic bandits (see Theorems and 5.3 we cannot achieve optimal performances for both RM and BAI using any algorithm with fixed parameters adversarial bandits. Besides, Theorems B.2 and B.4 indicates that
2
TTA
L-1 2(TTĀ))
sup ERy (EXP3.((x) ZeB, (A)
log
+
65
4L
103A,
However, since the upper bound on the regret of ExP3. P(r, 1)) in Theorem is problem-indeependen., we cannot ascertain if the algorithm achieves the Pareto optimality, which may serve as an interesting direction for future work. Lastly, we summarize some theoretical findings of the adversarial bandits in Table B.]
B.1
C Useful facts
C.1
Concentration
Theorem C.1 aNon-asymptotic law of the iterated logarithm; Jamieson al. (2014)
Lemma 3). Let
X1, X2,... be i.i.d. zero-mean aab-Ganssian random variables with scale 0; i.e. E AX
exp(X202 /2).
19

---

Published in Transactions on Machine Learning Research (09/2023)
Table B.1: Comparison among upper bounds for algorithms and lower bounds in adversarial bandits.
Algorithm/Instanee Inntannce
Expected empirical-regret ERy
Failure Probability êr
3T
(
Lexp
UP-ADV
28T.
Abbasi- Yadkori et al.
2018
LLT
In L
TTA
YT + nLT + In
+
L exp
ExP3.P(1.1)
17
4L
(Theorem B.1
(Theorem
B.2
2
150T A3
Adversarial Bandits
exp
65
I
(Lower Bound, Theorem
B.3
L L-1 TT 1034,
2 exp( - -bT)
Adversarial Bandits
65
(Lower Bound, Theorem B.4
(Theorem B.4
For all E E (0, 1) and 7 E (0, log(1 + t)/e), we have
Pr VT 1, 1 Σ x, s o(1 + va)
2(1 + llog
log((1 + x)r)
2+ log(( + E)
1t8
21-
Theorem C.2 (Chung & Lu 2006), Theorem 20). Let XI, ", be martingale adapted to filtration
F (Fi); salisfying
1. Var(X,[FF-1)) S of for sis n;
2. X, X + M, for sisn.
Then we have
1²
Pr (X, EX, 2 A) < exp (- 2 ?0? + at) MA/3
Theorem C.3 CChung & Lu 2006
Theorem 22). Let X1, ,,, be a martingale adopted to filtration
F (Fi); satisfying
1. Var(X,[F:-1) S of, for <is n;
2. X X; s a, + M, for < < n.
Then we have
X= Px - EX,, < - S exp 2|En (o + at) + M\/3
Theorem C.4 Abbamooitz Stegun 1964.. Formula
7.1.13; Agrawal Goyal (013)) Lemma 6: Agrawal
& Goyal (2017)
Fact 4). Let Z N (p, The following inequalities hold:
1
2
exp
< Pr(1z 1l 20) exp
exp
22 0,
22
22
22
exp
< Pr 11) > 20) VTz
exp
Yz11 1.
2/TZ
2
222
2
20

---

Published in Transactions on Machine Learning Research (09/2023)
Theorem C.5 (Standard multiplicative variant of the Chernoff- Hoeffding bound; Dubhashi & Panconesi
20009, Theorem 1.1). Suppose that XI...., XT. are independent [0, -valued random variables, and let T
X 21 Xt. Then for all (0,1),
22 Pr(X EE S -EEX) S exp
E² EX 3
Pr(X- EX EEX) S exp
[-TEX EX [xX 3
C.2 Change of measure
Lemma C.6 [Tsbakkvv 2008 Lemma 2.6). Let P and Q be two probability distributions on the same
measurable space. Then, for every measurable subset A (whose complement we denote by A),
P(A) + Q(4) 2 exp(-KT.(PI Q))-
Lemma C.7 (Gerchinovitz & Lattimore (2016), Lemma 1). Consider two instances 1 and 2. We let Ni. denote the number of pulls of item i up to and including time step t. Under instance j (j = 1,2),
we let (t=1) be the sequence of rewards of item i and ot be the pulled item at time step 1, and let Pjá denote the distribution of the gain of item i;
we assume [g = (g .t,.).. is an i.d. sequence, i.e,, gf and gi, are iid. for ti # to but iol can be independent.
we let ig be the pulled item at time step i, and let PP denote the probability law of the process Hh. )
Then, we have
KL(PP) || P2) = Σ Ep, [Ntr]] (L(P1, P2.).
C.3 KL divergence
Theorem C.8 (Pinsker's and reverse Pinsker's inequality; Götze al (2019). Lemma 4.1). Let P and Q be two distributions that are defined in the same finite space A and have the same support. We have
8(P.Q)² (T.(P) 8(P.Q)²
aQ
where 8(P,Q) = sup (PA)- - A] PP(z) - Q(x)) is the total variational distance, and aq = x Q(r).
Lemma C.9 (KL divergence between two Gaussian distributions). Let P1 N(m,, P2 N(H2,
Then
02 of + (111 -22 1
KL(PI||P)) log
σ1
20
2
Lemma C.10 (KL divergence between clipped Gaussian distributions; Lemma 7, Gerchinovitz & Lattimore 2016)). Let Z be normally distributed with mean 1/2 and variance o² > 0. Let clip max(a, min
for 5 b. Define X = clipjo.1)ZZ) and Y = clippo.1) E) for E R. Then
2²
KL(Px Py) <
202
21

---

Published in Transactions on Machine Learning Research (09/2023)
D Analysis of BoBW-LL'UCBBC) in stochastic bandits
Proposition D.1 (Bounds on the pseudo-regret of BoBW-LI'UCB(7)) Assume the distribution V4 is
sub- Gaussian with scale > 0 for all E [L], and wi 2 W2 2 ... 2 wt. Let E E (0,1), B 2 0, and
E (0, min (lnga + +1 ==++)/ee,1)) 1}). The pseudo-regret of BOBW-LL'UCHE satisfies
Rr (0(((1+)))
1
(
RT s
A
Furthermore, we can set 10 1/VT to obtain
Rr 50
log T
AL,)) )
Σ
Ry R (
D.1 Proof of Theorem
Theorem 4.1 (Bounds on the pseudo-regret of BOBW-LL'UCB, Let E (0,1), B 2 0, and y E (0, miog + 1 e)/e, 1}). For all T 2 the pseudo-regret of BoBW-Ln:UCB( satisfies
R₁ 50 0. Σ log(1/7) + +2TL)
Mn-00(2VTLLOo)
log( + 22TTT11
1
i
Furthermore, we can set 7 (log T)/T T to oblain
RT S 0
0². Σ
log
RT S 00002 (ooooTT
D
1f1
Proof. Recall that we assume w1 > W2 2 ... 2 wz. Therefore, item is optimal and Ar, > 0 for all j * Step 1: Concentration. Let E,, (vt L, 19r, wil s Caa, for all i e [4]. We apply Theorem C.1 to show that Oi Eig, holds with high probability.
Lemma D.2 (Concentration of gr,e). Pir any E (0, 1) and y E l0, 1+ =)/e). We have
Pr n Ein) (EnN)
2 21(2+e)
7
148
log(1 + +e)
Step 2: Bound on Nor for i + 1. Next, for all t > L, when
( > wi - C1 Ii--1 wi + Ci.-l
A 201111
Vi #1
holds, we have
(11,-117 I Ci,--11 > wi w; + A > wi + 20i,t-1.y > Ii,e-1 + Cia-1yy = Uni-1 Vi + },
which indicates in = 1. In other words, when i, = i for L, one of the following holds:
π11-1 $ w1 C1 -1,-1 2 w C2 D1, $ 20s,-1,79
We see that
2(1 + loog
log(3 + (1+ + E) N)e--1)
A < 20 = =100 =10t-1, +
V
No.-1
200o (1+ (E)
log(3 + (1+ (N+,)NN))-1)
< N
log
A7
7
In order to bound Not-1, derive the following lemma:
22

---

Published in Transactions on Machine Learning Research (09/2023)
Lemma D.3. For all T > 0, L.4cc/p + b2 e, have
= r clog llog(aT b)
)
1.4 (-111 log
[
b))
S clog
P
p
We apply Lemma D.3 with
200o2 (1) +)
c=
a +1++e e, and p = 7,
to obtain
200o (1 + (E) (1++1++)010 +
01 log
200a 0² (1+ +8)) = Neo.
No.11 S
log
AT,;
A7,7
1.4ac/p + is satisfied when 7 E (0. 1). Therefore, when t> T,, n Eig holds and Noa-1 > Ni, for all i + 1, we always have is 1.
Step 3: Conclusion. Consequently,
n E ]]
+ { g1.t - gi.st 1
RT
E
Σ 91 - gh.rt
=E
91 - greit)
1
5 Eny
1=1
< E
T
91.t
gient -1 n
Ein) ]]
+ Pr Pr
nei Ein
I.
1=1
i=1
T
( ]
1.
1.
E
91
girit
11(" (1==1)
=
+ +T Pr
n Ein
1+1
i=1
T
1
b
Enn
Σ 1=1
1 = j)
n
Ein
Pr
111
5=1
i=1
Σ
N1TT
Eipy
+ + Pr
Ean
Eim
111
I
Σ 141
AIJ (2+ Nan) + T Pr
n
Ein
1=1
Σ
2
2006 (1 + 2 +
log
a1 log
200a; 02 (1+ + +)))
A
7
47,7
111
1f1
22 +8)
?
14c
6
log(1 + +
200 +
(1) +e)
2an log
10.2aj o(1 + ve)(1+ + =B))
Σ 24 +
log
A
?
A1.17
1
2TI(2 +8)
7
14c
8
log(1 +
23

---

Published in Transactions on Machine Learning Research (09/2023)
We see that 01 1.4 I 2. If we divide the ground set into two classes depending on whether A1, 2 LIT,
we have
T. V T + 2L
20 + (E) +6) log
(4 VL/TV
220 + ( +3))
Rí ST.
log
VL/T
22 +&)
7
1ts
+
log + E)
4 log
220 + vE) + +
VTL
1 20002( (1+ + vE) + log
ViL/T
2T +
14c
+ 2L
log(1 + 8)
In short, we have
Rr 2 50
02. Σ
log(1/7)
+ 27 2TT
D
log(T/L7)
+ Lytt )
RT S 0
TLV
Let = (logT)/7 T)/T, we have
RT 50
00
02.
Σ
log
RT s O002VTTLoo
A
1
D.2 Proof of Theorem 4.2
Theorem 4.2 (Bounds the failure probability of BOBW-LK Let e E (0,1), 8 0, and e (0, min + 1 + e)/e, 1}). Let A, = max Artt for all i E [L]. For all T 2 1, the failure probability of BoBW-LI'UCB(c) satisfies
eT eTS 21(2+e)
1+8
if
T-h >
L
72a
log
2.8 log
1la(1+)) A
+ +B)) (4.1)
E
Log (1+E)
(1+E)3
A
i=1
In particular, the bound on er in
4.1 holds when 7 72 (A, H2), where
6.2.8o + =)²
+ 3 exp (- - AA-1 2-2)
T
m(A, 2.8 log
A
For all T 2 1, when y assumes its lower bound (A, H2), we have
T' $ Ö (Loxpl 14402 + (H2 ))
(4.2)
Proof. Recall that we assume w1 > W2 ... 2 Wt. We let A w1 W2 and A; w1 w; for all i
+
Then A Ai and A A; for i 1.
Step 1: Concentration. Tet E = (VI 2 L, 1ū.,- wel s Caan/5) for all E [Z]. Similarly to Lemma D.2
we can apply Theorem C.I to show that
2 1 2I
7 1tc
Pr
E/17
log(1 E)
24

---

Published in Transactions on Machine Learning Research (09/2023)
In the following, prove that conditioning the event {N Elyy have iout 1, which concludes the proof.
We assume Ni , holds from now on. Since dous is the item with the largest empirical mean, we have
Diou. Di.t Vi o Pout: Disat Whons Toua.r//5 we + C.TT/5 Ir.t Vi + fout-
Consequently, to show dout 1, it sufficient show that
OCT A
2CTT.1 =20 + VON
2(1 +8) llog
log(B + (1+ +)N.T)
A
Nrr
N1T 80² (E)(E))(1E))
[log( + +1++))
log
Vi E [4].
(D.1)
A7
Step 2: Upper bound N1. (i 1). To begin with, we let as and prove prove by induction that
N₂. S 720 (1) + e)
log a1 log
72a 02a + (E) + +8)² + +13) +a))++ +1 vi
(D.2)
A?
47y
Clearly, this inequality holds for all + when 15t5L L. Now assume that the inequality holds for all * 1 at time - 1(t > L). If i * i, we have Nr, NA,-1 and the inequality still holds for i. Otherwise, we have is = -iam and in particular U 2 U1,11177 Since
Un = 0i + Ci.--1y S wy + 60,,-1 U1 = -1.1-1 + C1 2 11 +
401,-14
2 w1 = w. + A..
5
5
we have
60A,111 2 A. + N
720 + (E)
log(B + (1 (1+ (1++))Ns--1)
loog
A
7
72o + ( +
a1 log
12010 (1 5)2 + B)) B))
N
log
A
A37
We obtain (a) using Lemma D.3 with E (0,
Lemma D.3. For all r > 0, 1.4ac/p +b e, have
loog(at + +b]
1.4
L.4ac
+ b) )
S elog
+ r clog
-
log
P
p
p
Subsequently, by using No. NiA-1 + 1, we obtain D.2
Step 3: Lower bound NiT (i # 1). Next, we again prove by induction that
No. 2 (100)(+++)(C))) v log log( + (1+ (1+)) min 25
Vi #1 1. (D.3)
36 36(C1,1-17)
Clearly, this incquality holds for all + when $ t < L. Now we assume that these incqualitics hold for all + 1 at time 1(1 L). i, # 1, we have
No. Nr.-1 Vi 1, NI. = N1,111
which implics that the inequalitics still hold for all i + 1. Otherwise, 4 = indicates that U1,-1 2 Ui,--1 for all i * 1. Since
U1 = -1.-1 + C1,r-17 5 wi + 601,t-1x
Un--1 = -r + C.e-1.y 2 w; + 40
5
25

---

Published in Transactions on Machine Learning Research (09/2023)
have
101,-111 < <A+ +
601,1-1.7
2(1 +c)
log(3 + ()+t))
5A; + 101,1-1,1
C,1-1,7= = =50 )
log
N1,11
4
200 + Vε)
log(3 + (1+E)N
N1.-1
log
5A, -611,-1,,
7
1
2(1
400o>(1 (1 + VE)²
log(3 + +(1 + (+)NN,a11
Ni
log
(54; + +601,1-1,))
?
2(1 + E)
N 8000 + E)(1 VE) llog
log(3 + (1+ N),,-1
(5A, + -60,,,1,,1
7
We apply u + 0 S ma, 0 and No,- = No,111 for all i + to obtain
D.3
Step 4: Lower bound on NL,T- Recall that we want to show D.1 D.3 indicates that is sulficiently to show that
(i) To show D.1 holds for all i 1,
200g (1 + =) + ve)²
log(3 + (1 N)
80 + (1)
log( + (1 + NN...)
log
A log
36(C1,T-1,))
Moreover, since A min As, it is sufficient to show xE[r]
25
1 A7
5A1
2 e CITT-1 S
36(C1,T-1,))
6
(ii) In order to show
D.1
holds for all i E [T], it is sufficient to show that
5A1 6
C1T--1,7 S
With 01 2, this implicd by
N1.--12 7202 + (3)
a1 log
72a1,30 (1 vE)
log
A7
7
AP7
2 + V=)² +
a1 log
"720,0² + (1) +))² +8) + 1.
N1. 2
log
A?
A7r
We obtain the inequality in the above display by applying Lemma D.3 Meanwhile, D.2 and Σ No. implics that
NI, -T - 2 (L 1)
720 (1++(
log
a1 log
72ajo (E) 5)² + +B) +B))
A
A77
if1
Altogether, complete the proof with
720 + (1)
[a] log
02 (1 (1) +8) ST
-+1 -T
A log
(D.4)
A77
Step 5: Conclusion. Since
21 + (1+
a1 log
72a10 + (e) 8)2 + +0))
log
A
A7T
72o + E)3
2aq
6,2aj o(1 + =)²
18) 8))
log
log
A
72
A;
26

---

Published in Transactions on Machine Learning Research (09/2023)
To show D.4 it is sufficient to have
72 (1 + =)
2a1
6v 6V/21 o(1 + +E)2
+ ST -T-L+1
log
log
A
7/2
A
72x² (1 + E)3
2a1
72 + 5)3
llog log (v2an o(1 + e)?
+ =)))
log
<T
L+1
A
7/2
4
A
1m1
T- El=
720 A
(1 + E) log (log
( A;
+ 3)
22a exp
1440² (1 + =)
Recall the definition of H2 in 2.1
H2 = Σ
A?
141
Furthermore, suffices to have
T
[622a] o(1 + +0)² + +0)))
7 221 exp
+ log
log
114
1/A7,2)
1,2
6.2.8 a(1 +)²2
T
Vv2.. 2oog log
2.8
+ exp
- 14462 3 (H2 1/
= (1 H2).
1
Note that A = 1,,. When y = (A, H2),
CT S 2L(2 +E)
(A, H2)
log(1 + +
21 +
(6/2.8 . o01 +)²
)
8))
1140/12
T L ( (11410p(1 +1 14 1/43)
2.8
exp
= <log(1 +c)]++é
A
D.3 Proof of Lemma D.2
Lemma D.2 (Concentration of (r.)). Fir any E E (0,1) and y E (0, log(3 +1++ e)/e).
We have
Pr n E
21(2 +
Y log(1 + E)
1tc
Proof. Let
E : (Vt > 1, w.l C...
Then
2(1 + E) N₂.
log(3 + (1 s)
Pr(Ei,)) = Pr
1t > L, wi| s 50 + v
log
7
Pr
VN.. 2 1,
( No.e
1
2(1 + te)
1og(3 + (1 + E)
Σ
Ji.u 162a 13 w: 50 + VENN
log
No.
7
1=1
27

---

Published in Transactions on Machine Learning Research (09/2023)
When E 10 and y (0, ++++++++0 =)/e), Theorem C.1
indicates that
2(2 +)
7
1tc
Pr(Ein) 2
log(1 + E)
Furthermore,
L
Pr n E1ny
11 - Pr
n
Ein
= -1-Pr
( Esn
im1
21
Σ Pr
Eig
2
21((2 +6)
7
lte
8
log((1 + E)
D.4 Proof of Lemma D.3
Lemma D.3. For all r > 0, 1.Aac/p p 22 e, we have
logg(a + +11 ) + T S cloo
1.4 -olog log
(LAac + b) 0)
T S clog
Proof. Let
log(at ) )
a1 log Tei clog
agc + +b) b))
f(T) clog
P
Then
a1
a2c + +b)) 2 clog
(110g ac aclog
al
a2c
) + b tb))
Tai.03 2 (Ta + clog
log
log
p
P
P
p
azC
(1 log
agc
log
+
b
2 log aclog
b
P
p
Let 01 2 1.4, then xa 2 x log x for all 1. To obtain Tar,0s
(Taz)aa)) suffices to have
a2c +b) log
a2c +b)
(1 log
(pp)) + b,
2 aclog
p
which is implied by
Q2c bbzc and 02c log
020
a001
aze
+b)
log
p
P
p
Conditioned on azc/p + e, the last inequality holds when 02 2 01 Since T S(7) is monotonically
increasing in T, and aa, aFa ie., Tar,a-a [Ta. 2 0, we have
t 2 T1.4.144 + T T-(((7) 2 0.
In other words, when 1.4ac/p + bb26 2e, e,
1.4
(1.acc)
T f(T) 7 T T1.22888 clog
log
p
p
28

---

Published in Transactions on Machine Learning Research (09/2023)
E Analysis of the Pareto frontier of RM and BAI in stochastic bandits
E.1 Proof of Theorem 5.1
Theorem 5.1. Let Φr, A, R, H2 > 0. Let a be any algorithm with eT I exp(-or)/= for all e
Bi (A, R). Then
(L - 1)R
AH2R
sup ( IJ 2 ØT
sup R.
Ry 2 ΦT
8A
IEB: (A.
Proof. Step 1: Construct instances. To begin with, we fix de E (0, 1/4] for all 2 S l S L. We let Bern(a) denole the Bernoulli distributton with parameler a. We define the following distributions:
V == Bern (1/)), Ve == Bern de)
4I < L;
1/ = (ern(1/2)
v/z = Bern(1/2 de)
AI < L.
We construct L instances such that under instance e (1 f L), the stochastic reward of item i is drawn from distribution
J = b. (u;1{i + { + (i
where b > 0. Under instance é (1 S l < L), see item l is optimal, and we define several other notations as follows:
(i) We let Jh, be the random reward of item i at time step Then L. (0,
(ii) We let 1 E ET gh.
sh,lTT denote the gap between item i and j. Then
Ai, = b. dj v2sis D = bbdde, Dii = b de + bb v2 S
(iii We denote the difficulty of the instance with
Hz(()
E(4
Then H2(1) max H2(()= < (L 116--)------ 1)6-2 ISESL
max di²
2SESL
(iv) We let if be the pulled item at time step t, and O = (it, Iec w be the sequence of pulled items and observed rewards up to and including time step t.
(v) We let P. be the measure on O and let Pt, be the measure the rewards of item i.
For simplicity, we abbreviate PT, OF as Pe, Og respectively. Morcover, we let Nr, denote the mumber of pulls of item up to and including time step L.
Step Change of measure. First of all, we apply Lemmas C.6 and C.7 to obtain that for all 1 15 6 S L,
Pr(iout + 1) + Pr(ion = 1) 2 exp(-KL(P)) P.)) 2 Ep, 0
KL(Pt, || Pr.))).
Or
Suppose the pseudo-regret is upper bounded by Reg, we have
T
Reg > Ep,
Σ 1 # 1} (ot. (2,10
Σ Epg [1 # 13 (gt, - st.+)l
L T
1. T
[1 = f (of, - -bt
ΣV
Epy 1 - -b, = 4 -Eq(1(t = El
2=
2m t=1
Σ Σ
A = =3] Σ
b de E7, [Ne.T].
2= 1=1
t=2
29

---

Published in Transactions on Machine Learning Research (09/2023)
Since H2(() (4t)(41))) ?, we have
Reg H2(1)
Ei b. de Ep, [Nerl
Ei= b. de E2, [Ne.
Ei=e(A) (1) A
b-3. dj=
Thus, by the pigeonhole principle, there exists 2 < E1 S L such that
dd Er, [Ne,,]] b b.de, Bp, [Ner]]
Reg H2(1)
Reg
+ E2, [N,
6-2 d/
b3d (1
Since de E 1041 for all - 0 L, we apply Theorem C.8 to obtain
Pr(iout +1 + Pr (fout = 1) 2 Bep(-E,,INe,, K Il Patee) 2 exp (- (--((-app
1
Reg
(2de,)
0,
Oe,
Bug H2(1)
1/4
Since Proy, (Bout fl1) 2 Pro,, (oott 1), we have
1
8Reg
max Pr(fout +() exp LSEED O2
Hz(1)b² min de 25151.
Step 3: Conclusion. We define
f2 = arg max Pr(iout + t). 1sE5L. Os
Suppose algorithm æ satisfies that
Pr (Nout # (2) S exp(-or). Oig
then we have
H2(1)b3
min de
25FST.
Reg 2 ΦT
8
When d = de > 0 for 2 S e L, we have -L (L-
Step 4: Classification of instances. Suppose algorithm π satisfies that eт( < exp(-0r)/4. Let
(A, R) denote the set of stochastic instances where (i) the minimal optimality gap A > A; and (fi) there
exists Rg E IR such the rewards are bounded in [Ro, Ro + RJ. Then
(L L-1)R
sup (A.))
(T( dT
VA. R> 0.
8A
Lei (A, R, H2) denole the set of stochastic instances that (i) belong to B, (A, R2,, and (ii) are with hardness
parameter H2 < Hz. Then, we have
AH.
sup (A,T(A
Ry
AA R. H2
30

---

Published in Transactions on Machine Learning Research (09/2023)
E.2 Proof of Theorem 5.3
Theorem 5.3. Let dr, Ar V, H2 > 0. Let be any algorithm with (T S exp((-oT)/ for all I e
(A, Then
(L-1)1 1)V
AH2V
sup RT (T,I) 2 ΦT
sup IE
[T( 2 ΦT
2A
TEB (A.))
Proof. Step 1: Construct instances. To begin with, fix any > 0, di for all 2 s es L. We define
the following distributions:
= _/1/2,00), = N(12 de,
AA < <854, L;
1/1 = 0
1/
A1 < L
We construct L instances such that under instance e (15 L), the stochastic reward of item i is drawn from distribution
o = mi + 2 + 1/11 = f).
Under instance é (1 we see item optimal, and we define several other notations as follows:
(i) We let L. be the random reward of item i at time step t. (ii) We let 1 EEE L.. sh./T denote the gap between item i and j. Then
A =d dj v2 D = de, Di. de + dg V2 j. i L.J
(ii) We denote the difficulty of the instance with
H2(l) = Σ (A2
3#L
Then H₂(1) = max H2( < (L 1) max d=². 1SLL
2
(iv) We let if be the pulled item at time step 4, and O = ( D2g Mig Mim be the sequence of pulled items and observed rewards up to and including time step t.
(v) We let Ft be the measure on Of, and let Pt, be the measure on the rewards of item i.
For simplicity, we abbreviate P/' Of as Pt, Og respectively. Moreover, we let Nr,, denote the mumber of pulls of item up to and including time step t.
Step Change of measure. First of all, we apply Lemmas C.6 and C.7 to obtain that for all 1 8 < L,
Pr(fout * 1) + Pr(ion = 1) 2 exp((KK(PP P()) = exp(-BB,1Ner)) KL(PLe Il Pt.))). O
Oe
Suppose the pseudo-regret is upper bounded by Reg, we have
T
Reg > Ep,
Σ 1 # 1} (ot. (2,00 Σ Epg [1fit
# 13 (gt,, st.,)l
L T
I. T
E2 [1 = f (ot, - ob,
Σ
Epy ( - -b = 4 -Ezy(1(t = El
2=
2m t=1
de
Egg (1 C =
de Ez, [N..]]
1=1
ビ=2
31

---

Published in Transactions on Machine Learning Research (09/2023)
Since H2(() ( ?, we have
Reg Ei de Ep, (Nrrl E di TR, (NeT) H2( (
d²=
Thus, by the pigeonhole principle, there exists 2 1 S L such that
di, Ep, [
Reg
Reg
d2 Bp,
[NG,,]]=
e Ep, [r, di H2(1)
dzi
H2(1)
Further, we apply Lemma C.9
to obtain
Reg
(2dg )
Pr(iout + 1)+ Pr
(Jout 1) exp( (Pr, [Ma..l K || Pa.&)) 2 exp
On
2
di H2(1)
20²
Since Proy, (iout +(1) 2 Pro., (fout 1), we have
max Pr(iout = 2 exp (- Hz(1)o² ISESL O2
2Reg
min de 25
Step Conclusion. We define
l == arg max Pr(iout + E). ISESL O
Suppose algorithm æ satisfies that
Pr (Pout # (22 S exp(-or).
Oig
then we have
Reg Ør H2(1)0²
min de 25
2
When d = de >0 0 for all 2 S E L.S, we have H2(1) = (I. - 1)/d2.
Step 4: Classification of instances. Suppose algorithm т satisfies that CT(π) S exp( (TT)/4 Let
B (A, V) denote the set stochastic instances where (i) the minimal optimality gap A N A; (fi) for each
item i, the variance of < V. Then
1)V
RT( 6T
VA, V > 0.
2A
(A.V
Let (A, V, Hz) denote the set of stochastic instances (i) that belong to B (A, V), and (ii) are with the hardness H2 S H2. We have
A
sup TEB (AV.V. H2)
RT (T( Ør
VA. V. H2 > 0.
2
E.3 Proof of Corollary 5.4
Corollary 5.4. Define the önterval I(v, (m,, H2), min (log( + + 1 e)/e, (log (loTT)/,T which is
function of the instance and the fixed horizon T. When I(v, T') + 0,let no denote the online algorithm
BOBW-LI'UCB(> with o satisfying the condition that y I(v, T). Then
1
log (1))
sup (A.H.))
Rr(mo, Ω AH, log
7L
A
32

---

Published in Transactions on Machine Learning Research (09/2023)
Proof. We consider the stochastic instances in B2 H2). By the classification of instances in Theorem 5.1 these instances satisly the conditions
Si.t E [0,1] Vi,4, and H2 S H2.
Therefore, the distribution is aausGausi with scale = 1/2 for all i i [L]. We assume T is sulliciently large such that
log
6v 6v2.80 + =)²
T- L +) 1/
71
2.8 log
+3) -exp
T
A
3.2.8(1 + e)²
T-
2.8 log
+ 3)
exp
36(1 + (H2 +
As result, for all instance in B2(A, 1, H2), since A 2 A and H2 H2, we have
log T T
3/2.8 1 E)2
T-L 36(1 + ( + A 2-2)
2
2.8
+ + exp
A
Fix any y E [n, (log T) On one hand, for any instance in B2 1, H2), Theorem BoBW-LL' (OBW-LI'UCB(() satisfies that
4.1 implies that
RT S of log
7 1111
On the other hand, Theorem 4.2 implies that
22 +
1-c
êt <
8
log(1 + 8)
Moreover, can apply Theorem 5.1 to obtain that
sup (A.177.
Ry RBBBB.../UCH()).))
AH2 log
7LL)
Altogether, we have
sup R1 (BBBW..I E AHz log 112 (A..(A.1.H2)
111) 5o
(T. (I.-1) log
2)
A
F Analysis of ExP3.P in adversarial bandits
F.1 Proof of Theorem B.1
Theorem B.1 (Bounds on the regret of ExP3.P(h.1) Let 17 > 0, r E [0, 1/2] satisfying that Ln S 7/- Then we can upper bound the regret of ExP3.P(X,,) n)) follows. (i) Fix any given & (0, 1), with probability at least 8,
LPT 118
Ry $ ST + nLT + In
+
(i) Moreover,
LPT
In
EaT 5TT + nIT +
+
+1
1.
7
33

---

Published in Transactions on Machine Learning Research (09/2023)
Proof. The analysis is similar to that of Theorem 3.2 in Bubeck et al. 2012 with 8 0, while the following
lemma signifies the key difference.
Lemma F.1 (Implied by Bubeck et al. (0012) Lemma 3.1). For any item i, with probability at least 1 - 6,
T
T
Pi. S
Pigt +
In
176
Replacing Lemma 3.1 in Bubeck et al. (0122) by Lemma F.1 Bubeck et al. (2012) and show that with probability 1-6,
we can adopt the analysis of Theorem 3.2
1.T 76
In
Rr ST + nLT + In
Moreover, derive that
I.2T)
In
W' = Rr - 7T 7T+ +TT+ +LT +l
+
17
P(W": In 1
L
In L
()) )===tt
Pr RT
YT
nLT
In
+
0
no
1
ERT |T + nLT In
I,2T
In L
+
1
17
17
L
In L
ERT S TT + S
nLT + in
+ 1.
1)
F.2 Proof of Theorem B.2
Theorem B.2 (Bound on the failure probability of ExP3.P). Assume GL.T G2T ... GL,T. We see that the optimal item o 1. The failure probability of ExP3.P(7,,) n), satisfies
TTA
(- -
ēr
S exp
exp
$ L exp
4L
L(3 + 2,,27/2 12 A2.iT)
4L.
Proof. For brevity, we assume G1T 2 G2. ... 2 GLTr and abbreviate AiJT as Dig for any i.j E [L]. Consequently, the optimal item 1.
Step 1: Construction of martingale. Let
B1.1 9t,t Ii.t:
X1, = =
Σ (ā. grna)
Σ
Bi.u
u=1
Now we fix arbitrary i e [L] and abbreviate Vi.t as yes Xi,e as X, for brevity when there is no ambiguity. Then we have
[i i} -1) gi,t
(H (Hi=-i- 1).
X - X,-1 = 3/ = Gi,t - gi,t = Ih.t
Pi,t
Piee
S li 5
since Gi.t 5 1,
Pi,
El i}1FF -1 F 0, Ey: E.E =0.
Elys [F- E Di.t
Piet
Since ye is martingale, we can apply Theorem
C.2 and C.3 for the analysis.
34

---

Published in Transactions on Machine Learning Research (09/2023)
Meanwhile, note that Pi, Fi-1 and again It, I 1. Since P(4 = i[Fi-1) Pi,e, the variance conditioned Ft-1 is the variance of the Bernoulli random variable with parameter Pi,t, scaled to the range [0, (t.ga//pa. pa,))- Hence, we have
= Var(yulFi1) (ar(Xx((Fr1))
Var
gi
(Ife = 1)
F(-1) ) Var
gi,t l1(e = i}
Fo-1
Pi,
Pi,
Di,t TTGie= 8)
Pi,t
2
Pt,e Pr.e)gi,
(1 - Pt,
-Var
Fi-1
Var(Ifu = +1]FF-1)
Pi,
Pi.
př.e
Pi,e
1 11-1 1)
= -i
S
= of
since Ii,t S 1.
Pi,t
Pi,t
On one hand, in order to apply Theorem C.2 upper bound - G.TT, we need to upper bound Var(X,)Fi-1); yt, and lower bound Рi.- These bounds will depend on the lower bound on Pi, On the other hand, to lower bound G.T Gi with Theorem C.3 we need to upper bound Var Var(X, F+-)Fr1)), Pi,t, and lower bound ye. This motivates to derive bounds Pi,t- Since 7 + 1 (1 7) 7) > 0, there are global bounds on {pi
G..T-Ga
7 L
s S11 7
Step 2: Bound G.r - Gi with high probability.
Upper bound Grr Gi.,. We first derive upper bounds Etm o², ye with lower bounds Pi,e
(i)
Σ
T
= Σ
T
11) ST.
L -1) 7
Pig
t=1
1=1
1-B
(ii)
yt
1
S
1= M.
Pi,t
Let 0r = 0. We apply Theorem
C.2
For all X E (0,
X²
Pr(XT EXT 2 A) S exp
EXT Σ
Eye 0.
ΣT 1== of + M2/3
Therefore, for all i E [4], A E (0,1),
X7
P(Gr - Gi 2 Ar) & exp
(F.1)
IT of + MMx333
Lower bound GRr Gar. Similarly, have X X, - S 1 M'. We apply Theorem C.3 Therefore, for all i E [4], A (0, 1), have
X
Pr( Gir -1a) exp
(F.2)
S1=l of M/A/33
Step 3: Last step. We decompose the failure probability as follows:
Lemma F.2. For any fized time budget T, we have
Pr(fout #1) s Pr Grr
--r G
TA12
+
+In
1.
Pr
- Gir 2
TA1,
+ A2.
2
2
2=2
35

---

Published in Transactions on Machine Learning Research (09/2023)
Combining F.1
F.2
and Lemma
F 2
see that
TA1,
TA12
A v 2
X
+
T.
Vi + 1,
2
X
x
Pr(lout * 1) exp
Σ exp
T
of
M' M X1/3
1=1 o7 MX/3
1=1
Let
TA1
TA1 1.2
A
A
+T 22, Vi
2
2
We now complete the proof:
T
L Σ exp
T(41,2/2 22.;)
Pr(sout # 5 exp
L/7
L(3 + 21,2/2 22,1)
i=2
7 Σ
3, 22,1)²
= exp
+
cxp
4L
L(3 + 21,/ + A22s))
1=2
F.3 Proof of Lemma F.2
Lemma F.2. For any fixed time budget T, we have
TA12 #1) s Pr GLr GI. S
L
TAI22
Pr(fout #1)
+
Pr
Gir - Gi,r 2
+ T D2, -2.
2
2
1=2
Proof. We observe that
Pr(sont
# 1) = Pr(3i # 1: G.rr 2 G1.r)
TA1.2
TA
< Pr
li x 1: G.T - Gi, 2
+T -2,ú, or GI,T- GI,T S
(F.3)
2
2
TA1
TA1.
< Pr
GI.T - GITT <
+
Σ
Pr - GiT 2
+T A
(F.4)
2
2
2=2
It is trivial to obtain F.4 with F.3
Now complete the proof with the derivation of
F. We denote
E = (G.T- G1.r
TA
ε { (G.T GeT 2
TA12
T
A2.
Vi 1.
2
We can rewrite
F.3 as P( # 1: G.T 2 GI.T) S SPUU EiT)). Hence, it is sufficient to show
{n E c } = (GiT < GiT Vi
as follows. When n E holds, for any i + 1, we have
TA 1.2
T412
Gi. < Gi, +
+ T. A2, = Gi.T - T -1,7 - +
+ +T. A2ii
2
2
TA1.
TA12
<G.T +
T
AI,
+
+T. 2 = GITT A (T -12+T- +T -A,2
2
2
= -GIT
36

---

Published in Transactions on Machine Learning Research (09/2023)
G Analysis of global performances of adversarial algorithms
G.1 Proof of Theorem B.3
Thcorom B.3. Let 0 < AT I 1. Then any algorithm. æ satisfies that
sup IT( 1 exp(-x3 10- 3T/200)
150T AT
exp
3)
4
Purthermore, when 2 10,
2 65
1507 A
sup (, 2
exp
L
Bi (A,
S2e....,Zyy Zr be sequence of i..d. Gaussian random variables with mean 1/2 and variance a² E [1, oo). Let & E (0, 1/2) be a constant that will be chosen differently in each proof. Under instance (1 S S L), Let Lh. be the random gain of item at time step t, where
Proof. Step 1: Construct instances. To begin, we let Z1. Zz,...
1/2 =i
clip (Z))
if==
9
1/2 + ifi=
Sh.
clip (4 +
ifi=
W 1.
1/2 -E
else
clip (Z 8)
else
S L L), we define notations as Note that clip(a,y == max min for a S b. Under instance follows:
(i) We let G,,,, Exm A.e and T Mi = G - G/ for all i,j E [L], which indicates that = arg max G the optimal item.
(ii) We let of be the pulled item at time step 4, and 0 = (i I2, 1om be the sequence of pulled items and observed gains up to and including time step t.
(iii) We let Py be the measure on Oj. and let Pe, be the measure on the gain of item i.
(iv) We define A == min AE. jqt
For simplicity, we abbreviate PPF Of as Pe, O2 respectively. Moreover, we let N,(1) denote the number of pulls of item i up to and including time step t.
Step 2: Change of measure. First of all, we apply Lemmas C.6 and C.7 obtain that for all 1 1 L,
Pr(fout # 1) + Pr(iont =1) 2 exp(-KK(( P2) exp( Ex, [N)(T) KL(P1, Pa.))) O,
Oe
Now we turn to bound E, [N((T)) Since Ele E, (N,(T)) = T, there exists 2 < lg S such that E2, [Ne, (T) T/L. Further, with Lemma C.10 we can see that
1
Priout # 1) + Pr(fout 1) 2 exp(-Ep, [Ne, (T) KL(PL,e, Pt.))))
0
Peg
2
1
T (2
exp
2
L
20²
Since Pro,, (lout #l) 2 Pro., (Jout 1), we have
2T
max Pr(fout #1) exp
1S85L O,
0²L
37

---

Published in Transactions on Machine Learning Research (09/2023)
Step 3: Comparison between and mii. (i) Under instance 1, since G 2 G Gj,r for all i 1, T.e., item 1 is the optimal item and all other items are suboptimal with identical rewards after T time steps, we have
min Als = -1, Gi -G2r f#1
A
cclipoon (Z) clipoo. =)]
T
T
Let X, clip (2+) clip (Zr - 8) and X = - X., Then X =TTAman min
We have
X, 2 jclip 22 + +) clip (Zi) 1fc - 4, $ - 5) = 211-
Let 1/2 E. Theorem
C.4 implies that
1
(1/2- -3)a
Pr
Z
2 : s exp
20²
(1 - 2=)²
(1-2z)²
Pr(e < Z, 1-
8) 2
exp
: p(E,0).
z
S
Hence,we have EX, e o(5,)).
Since X2 E c0,c] for all t, Xi/e,..., Xr/E are independent [o, 1]-valued random variables, Theorem C.5
indicates that for all E (0, 1),
E²EX
(1- a)Ex) 2 - exxp (-o
Pr(X -X < -EEX) S exp
+
(G.1)
3e
35
Let b= 1=1-aa a. Since EX, 2 p(e, o) for all t
(1 (1-b) (1-b)-T.p(e,.0) p(e,o)
Pr( x 2 bTe p(E,0) ) 1-1100 exp
exxp
vb (0.
3
In order words,
Pr( Å 2 be p(E,0)) )2 eexp exp (-
(1 (T- p(2,0)
vb E (0, e (0,1/2).
(ii) Under instance l (E f 1), since G G G G%Sr for all i,j $ {1,6), i.e., item & is the optimal item, item 1 is the second optimal item, and all other items with identical smaller rewards after T time steps, have
A min min Ai = A2, = Ce
G
T
[clip 0. (Ze + A) - cl. (2)).
T
T
Let X clip 1) (Ze + 8) clip (z.) and X'
Σt= X7. Then X' T We have
T
X 2 [clip (2, + 8) - clip [z:) 1f S 2, < e) = Z, 11
We again apply Theorem C.4 EX 2 E p(E,o). Moreover, Theorem
C.5 implies that
(1 b)2T p(e,o)
Pr( A 2 be p(e,o) ) 2 exp
Vb E (0,1), (0,1/2).
3
iii
Altogether, for all 1 < l < L, we have
(- (1 - 2)2T p(e,o)
Pr( A 2 be p(e,)) ) 2 -exp
vb E (0,1), (0,1/2).
(G.2)
3
38

---

Published in Transactions on Machine Learning Research (09/2023)
Step 4: Consider the instance with the largest error probability. Let 1 s ls I L satisfy that
(Vout # Es) 2 exp (-
27
Pr
Oig
0²L
Note that A min:
A are all determined by (4))==1- We let O² Oig U (Z Then for all & E (0, 1),
Pr (fout # lz)
Pr or fout + f3:
min 2 be p(e.o))
Oig
2
Pr iout o f3 A min 2 be . ple,,)) ) Pr ( A 2 be - p(e,
O'
O'
min
1
2
[ exp
(1 - b)ST p(e,0)
4
exp
12 p2 (c,
Let 1/10, 1/3, = 7/10. Then
exp (-
(1- (1-26)²
(-9 9
4 (4) 2
18
1
p(e, =1 -xx
= -xxp
exp
exp
80²
8
5
25
2
Moreover,
2T min
)2
(3/10)2 T (1/2)
Pr (oout # ab) 2 4 exp
1 - exp
1-expp
Ozg
(7/10)² (1/3)²
L (1/2)²
3
1 exp
72007 min )2
&
37
exp
49L
200
150T' A min
)²
31
2 exp
1 exp
4
T.
200
When T 2 10, since - exp(-37) -3 /200) 2 8/65, we have
150T min )2
Pr (fout # (2)) Ois
exp
65
Step 5: Classification of instances. Let Bi (AT, R) denote the set of instances where (i) the empirically- minimal optimality gap Ar 2 Ari and (ii) there exists Ro I such the rewards are bounded in [Ro. Ro R... Then
sup Pr(fon # f7)) exp(-3T/200 exp ())
150T L
VO S1
4
When T' 10,
VO Ar $1. 150T
sup Pr(iout # #it) 2 (A,,1)
exp
65
G.2 Proof of Theorem B.4
Theorem B.4. Let 0 Ar < 1 and T> 2 10. Let π be any algorithm with (r( I) S 2exp(-ux)) 6/5 for all
I E B (A,, 1). Then
1-1
sup TA,..A,..1))
ERT(T, I) 2 UT
1034,
39

---

Published in Transactions on Machine Learning Research (09/2023)
Proof. The analysis is similar to that of Theorem B.3 (See Appendix G.1 same way.
We construct L instances in the
Step 1: Change of measure. We apply Lemmas C.7 and C.6 to show that
Pr(fout + 1) + Pr(iout = 1) 2 Oi
Pr)) =
KL((Pe Pt,e)).
Oz
In order upper bound Ep, (T)), we lower bound the number of time steps that gi - gè. E, i.c.
Ze E [0, 1 - s]. Let zo 1/2 E. We again apply Theorem C.4 to obtain (G.1:
(- (1 (-11-28 - 2s)²
Pr(= S Z, S - =) 21-
p(E,0).
80²
Since the expectation of the empirical-rogret is upper bounded by Reg, we have
Reg 2 Ee,
Σ 10t 13 . (o),c - )lre) 2 Ep,
Σ 1 + 1, A Z 11--c) (0l, - )ino)
Epy [1 # 1) (clip|o.1] (Ze)
clippo.) (7 -3] 8 4 < o) Pr(e 74
Epg [1 + 13 12e - (2--e) e 2 1
- 8) p((,o))
T
1
= Σ Epp [1 * 1}] E p(e,o) = e p(E,o)
Σ t=2
Ep, (T).
Hence, there exists S 40 S such that
Reg
[No (T))
8 So.p(e 0) (I. -I-
Further, we again apply Lemma C.10 to obtain
Pr(iout
+ 1) + Pr (fout = 1)
(T)] KL(P1,to || Pto
O
Oio
1
Reg
(2s)²
--e (L-1) 20
exp
Since Pro,, (lout + to) 2 Pro,, (bout 1), we have
2e Reg
max Pr(fout # 2 exp 02 p(E, (L - 1)
1< O2
where =1 -1-ppi--- (11((122)3/(8)))
Step 2: Consider the instance with the largest error probability. Recall G.2 from the analysis of G.I For all 1 < f < L, we have
Theorem B.3 in Appendix
Pr( A 2 be - p(E,)) exp (- (1 (1 b)2T ple.,)) vb E 1), E (0,1.
3
Let S by L satisfy that
25Reg
Pr (fout # 22) exp Oz
0² p(e, (L-1)
40

---

Published in Transactions on Machine Learning Research (09/2023)
Note that min..... Aiin are all determined by {Zi We let O' Oi2 U 1 Then for all b E (0, 1), S & L,
Pr(iout x2) 2 Pr ( fout + l2. Amin be p(e,
O2
2 Pr iout 7 l2 A 2 be o(E,0))
Pr
A 2 be p(E, )
0
O'
1
2 min Reg
[ 1 [1- exp (- (1 -1- p(e;
exp
-22 (), (L- (L-1)
3
Since this inequality holds for all 1 SSs L, we let Amin miniges Amin and have
1
(-
02. 0z p² (e, 0) (I. (I- 1) 1
2 min Reg
[1-exp/ (- (1 (1- (1- (1-b)8T--pee ---eT-((ee,))
Pinnt 22) 2 exp O2
We again let E = 1/10, 1/3, === 7/10. Then p(c, 0) 2 1/2, and
1
24 Reg
(3/10)2 T (T. (1/2)
O2g
Pr Pr(iout * #62) 2
4
exp
(1/3)2 (7/10) (1/2)2 (L (L- 1)
1 exp
1
720A min Reg
37
2
exp
- exp
4
7(L- 11
200
1
1034 min Reg
37
exp
exp
4
L-1
200
When T 10, since
2 8/65, we have
2
103 min
Reg
Pr (iout # 12) 2 Oi
exp
65
Suppose algorithm æ satisfies that
2
Pr (fout fb)) <
exp( -
Or
65
then we have
L-
Reg
VT.
1032min
Step 3: Classification of instances. Suppose algorithm a satisfies that हπ(π) S 2exp(- We
again consider (A(r,))) 1) as in Theorem B.3 Recall that (A R) denote the set of instances where (i) the ampirically-mininas optimality gap Amin, 2 Ar in T time steps; and (ii) there exists Ro e R such the
rewards are bounded in [Ro Ro + R). When T 2 10,
L-1
sup ER 2 uh
YO Dr 1
103
IeBi (A,.!)
H Additional numerical results
We present the failure probabilities and counts of algorithms different instances Appendix H.1 We provide additional numerical results for both synthetic and real datasets in Appendices H.3 and respectively. We also elaborate more details about the experiment setup of the PKTS2 dataset in Appendix H.4
41

---

Published in Transactions on Machine Learning Research (09/2023)
H.1
Empirical failure probability of BOBW-LL'UCB(C)
Table H.l: Empirical failure probability below 1%
Bernoulli instances
ML-25M
PKIS2
L
64
128
22
109
0.05
0.1
0.1
0.2
BoBW 10-7)
0.83%
0.22%
0.78%
0.20%
0.96%
0.92%
BoBW 4)
0.65%
0.17%
0.62%
0.18%
0.72%
0.23%
B6BW 10-1)
0.11%
0.03%
0.14%
0.04%
0.06%
0
Table H.2: Empirical failure probability below 2%
Bernoulli instances
ML-25M
PKIS2
L
64
128
22
109
0.05
0.1
0.1
0.2
B6BW(6 10-7)
1.78%
1.60%
1.06%
0.31%
0.96%
1.68%
BoBW 10
1.21%
0.95%
0.61%
0.16%
0.72%
0.42%
BoBW x 10-1)
0.28%
0.23%
0.06%
0.03%
0.06%
0
42

---

Published in Transactions on Machine Learning Research (09/2023)
H.2 Empirical regret of algorithms with empirical failure probability below 1%
Table H.3: Empirical regret of algorithms using synthetic data
Algorithm
L
A
Average regret
Standard deviation of regret
(9 x 10
64
0.05
6.45 x 103
5.10 x 10
BoBW (9 x 10 10=
64
0.05
6.59 x 10x
1.38 x 10a
Bo 10 )
64
0.05
6.61 10
9.27
UCB3.0
64
0.05
1.84 x 104
2.31 X 103
UCB4.5
64
0.05
2.34 x 104
3.41 x 10
UCB6.0
64
0.05
2.64 x 10+
4.22 103
(9 10
))
64
0.1
3.78
10
3.74 10
(9 10
64
0.1
3.90
10a
8.53
BoBW(9 10
64
0.1
3.91
103
5.64
UCB3.0
64
0.1
8.89
10
1.12 10
UCB4.5
64
0.0
1.13
10*
1.68 103
UCB6.0
64
0.1
1.28
10*
2.07 103
B9 x 10-) 10-1)
128
0.1
6.82 x 10
3.26 x 10
(9 x 10
128
0.1
6.91 x 10
7.37
Bo x 10"")
128
0.1
6.92 x 10
4.83
UCB3.0
128
0.1
1.84 x 10*
2.21 x 10
UCB4.5
128
0.1
2.35 x 10*
3.39 x 10
UCB6.0
128
0.1
2.67 x 10
4.19 x 10
BoBW(9 x 10 10-1)
128
0.2
3.87 x 103
2.49 x 10-
BoBW(9 x 10 10-1)
128
0.2
3.95 x 103
4.47
BoBW( x 10-")
128
0.2
3.96 x 103
2.86
UCB3.0
128
0.2
8.72 x 103
1.09 x 103
UCB4.5
128
0.2
1.11 x 10
1.62 x 103
UCBè.0
128
0.2
1.26 x 10 2.01 X 103
Table H.4: Empirical regret of algorithms using the ML-25M dataset
Algorithm
L
Average regret
Standard deviation of regret
BoBW (9 10 10-1)
22
4.05
10a
113.98
BoBW (9 10-4)
22
5.16
10a
43.93
BoBW (9 10-7)
22
5.38
10
31.79
UCB 3.0
22
7.05
10a
927.60
UCB 4.5
22
11.22
103
1.77
10
UCB 6.0
22
15.04
103
2.67 10
Table H.5: Empirical regret of algorithms using the PKTS2 dataset
Algorithm
L
Average regret
Standard deviation of regret
B9 x 10-1)
109
8.63 x 10
2.31 x 103
B9 x 10-4)
109
8.73 x 106
1.55 x 103
BoBW(9 x 10 1)
109
8.78
10"
1.32 x 10x
UCB3.
109
17.01 x 106
2.33 x 106
UCB45
109
21.50 x 106
2.94 x 106
UCB6.0
109
26.31 x 10
3.71 x 10
43

---

Published in Transactions on Machine Learning Research (09/2023)
H.3 Experiments using synthetic data
In this section, we present more numerical results for larger instances with L. 128 items. These figures yield the same conclusions in Section 6.1
Experiments with empirical failure probabilities below 1%.
BoBW-lirUCBY)
UCB
BoBW(9 10-1)
Algorithm
BoBW(9 4)
BoBW(9 10-7)
UCBs
UCB4
UCB
0.0
0.5
1.0
1.5
2.0
2.5
3,0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
Time Horizon
Regret
1e4
Figure H.l: Empirical failure probability
1%:
128, A 0.1, 4 Bern(w;).
BoBW(9 )
Algorithm
BoBW(9 10
BoBW(9 10-?)
UCB,
UCB45
UCB6.0
0.00
0.25
0.50
1.00
1.25
Time Horizon
1e4
Regret
1e4
Figure H.2: Empirical failure probability S 1%: L 128,
A 0.2, Ber.(w.).
Experiments with empirical failure probabilities below 2%.
BoBW(9 2)
Algorithm
BoBW(9 10-4)
BoBW(9 x 10
UCBs,0
UCB
UCBs.0
0.0
0.5
Time Horizon
1e5
Regret
1e4
Figure H.3: Empirical failure probability S 2%: L = 64, A = 0.05, 14 Bern(w.).
BoBW(9 x 10-2)
Algorithm
BoBW(9 10
BoBW(9 10-7
UCB45
UCBs.
0.00
0.25
0.50
0.75
1.00
1.25
1.50
0.00
0.25
0.50
0.75 Regret
1.00
1.25
Horizon
le5
1e4
Figure H.4: Empirical faihrre probability
2%: L 64, A 0.1, 14 Bern
44

---

Published in Transactions on Machine Learning Research (09/2023)
BoBW(( )
Algorithi
BoBW(9 10
BoBW(9 10
UCB
UCB45
UCBs.0
0.0
0.5
1.0
2.0
2.5
3.0
0.0
0.5
1.0
1.5 Regret
2.0
2.5
3.0
Time Horizon
1e5
1e4
Figure H.5: Empirical failure probability
2%:
128, A 0.1, 24 Bern(w,).
BoBW(9 x 10-2)
Algorithm
BoBW(9 10
BoBW(9 10-7)
UCB3.0
UCB4.5
UCBa.0
0.00
0.25
0.50
0.75 Regret
1.00
1.25
Time Horizon
1c4
1e4
Figure H.6: Empiriaal failure probability 2%: = 128, A 0.2, 44 Bern(w;).
H.4 Experiments using real data
PKIS2 dataset. The repository tosts 641 small molecule compounds (kinase inhibitor) against 406 protein kinases. This experiment aims to find the most effective inihibitor against a largeted kinase, and is a fundamental study in cancer drug discovery. PKIS2 presents a 'percentage inhibition' for each inhibitor, which is averaged over several trials. For each entry, normalize it to be between 0 and and then obtain the percenlage control by subtracting each of the normalized entries from 1. The percentage control help understand how effective the inhibitor is against the targeted kinase. Since Christmann-Franck et al. (2016) reported that these values have log-now log-normal distributions with variance less than 1, we sample random variables form a standard normal distribution with the log of the percent control as the mean; the similar setup was used Mason al. (2020); Mukherjee et al. (202T). In our experiment, we select. the inhibitors tested against one specific kinase MAPKAPK5. We aim find out the most effective inhibitor with the highest percentage control against MAPKAPK5, and also obtain high percentage controls cunulatively during the process. Our results may benefit the experiments that test inhibitors with genuine cancer patients, which helps to identify the most effective inhibitor with fixed number of tests and provide effective solutions to the attendants during the tests.
Experiments with empirical failure probabilities below 2%.
BoBW(9 10-1)
Algorithm
BoBW(9
BoBW(9 1)
UCB
UCB45
UCBs.
6
8
0.00
0.25
0.50
0.75
1.00
1.25
1.50
Time Horizon
1e4
Regret
1e4
Figure H.7: Empirical failure probability < 2%. ML-25M: L 22 movies with at least 50, 000 ratings.
45

---

Published in Transactions on Machine Learning Research (09/2023)
BoBW(9 10
Algorithm
BoBW(9 1)
BoBW(9 10-2)
U.B
UCB4,5
U.Bs.0
0.00
0.25
0.50
0.75
1.00
1.25
1.50
0.0
0.5
1,0
1.5 Regret
2.0
2.5
Time Horizon
1e7
1e7
Figure H.8: Empirical failure probability S 2%. PKIS2: L = 109 inhibitors tested against MAPKAPK5.
46


Reviews:
[{"review_id": "NY2E9VbsjE", "reviewer": "Reviewer_2ndQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is very well written. It was a pleasure to read it. The discussion on previous work was substantial, well researched and easy to read.\n\n2.  The algorithmic contribution is solid and matches the objectives of the paper as well as the verbiage used by the authors when explaining their contributions.\n\n3. All facets of the problem are explored in detail including lower bounds. \n\n4. The experimental evaluation us thorough and tries out their methods beyond synthetic problems. \n\nWeaknesses:\n\nI didn't find any major flaws in this work. It is likely it has already gone through several rounds of reviewing. It is in great shape. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a Best of Both worlds algorithm for best arm identification in multi-armed bandits. The algorithm BoBW-LIL'UCB($\\gamma$) recovers the Pareto frontier for regret minimization and best arm identification. Additionally they also a series of lower bounds showing the no algorithm can perform optimally for BA and RM objectives simultaneously. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "As I mentioned in the previous vignette, I didn't find any major issues with this work. I only found a minor 'issue'. In corollary 5.2 there is a boundary condition that is not properly handled. If $\\sup_{\\mathcal{I} \\in \\mathcal{B}_1(\\underbar \\Delta, 1)} R_T(\\pi, \\mathcal{I}) = \\phi_T \\frac{(L-1) \\bar{R}}{8 \\underbar \\Delta}$ I am not sure the implication is clear. ", "broader_impact_concerns": "This work does not raise any major broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CvkCjM9qun", "reviewer": "Reviewer_F4h1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "It appears that while the algorithm can be tuned to achieve optimal (or near-optimal) cumulative regret by setting $\\gamma = \\log T/T$, it cannot be calibrated for BAI at a near-optimal rate as this requires setting $\\gamma = \\gamma_1\\left( \\Delta, H_2 \\right)$, which requires knowledge of the primitives. Is this true?\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work conducts inquiry into the competing objectives of cumulative regret minimization and best arm identification in the stochastic multi-armed bandit problem, and attempts to flesh out a Pareto frontier of achievable performance between the two. This is shown via a lower bound on the cumulative regret of any algorithm that achieves BAI with a given failure rate. The authors also propose a UCB-style algorithm (similar to the one in Jamieson et al. (2014)) that can be fine-tuned to trade off performance between the two objectives. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I am curious if the logarithmic factor in the problem-independent bound can be shaved off?\n\nAlso, how would the failure probability $e_T$ look like under classical UCB1 (Auer et al. (2002)) with an exploration coefficient of $\\alpha$? This is similar to UCB-E(α log T ) but with $\\log t$ instead of $\\log T$. Essentially, does knowledge of horizon buy you any gains in the failure rate? Also, the failure probability of UCB-E(α log T ), as it appears in Table 3.1, is misleadingly problem-independent. Please include the condition on $T$ and $H_2$ from Corollary A.1 to avoid ambiguity.", "broader_impact_concerns": "Broader impact statement N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6IunOTSstA", "reviewer": "Reviewer_uXLo", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: To my knowledge, this is the first paper studies the Pareto frontier of regret minimization and best arm identification in the fixed budget setting. This paper developed both upper and lower bounds for this setting, and I believe such results are important and interesting.\n\nWeaknesses: For the best arm identification setting, it seems that the optimal guarantee is only achieved when some problem-dependent parameter is known to the learner (e.g., the minimum reward gap $\\Delta$ in Theorem 4.2). Can authors comment on this issue? E.g., is it possible to achieve the optimal guarantee without knowing such parameters?\n\nWhile I appreciate the authors analyzing many existing algorithms for the proposed setting, I would encourage the authors to add more comparison algorithms, e.g., the vanilla LIL'UCB algorithm. Or highlighting why the vanilla LIL'UCB cannot achieve the optimal guarantees (after adapting it to the fixed budget setting, which should not be hard).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies regret minimization and best arm identification for multi-armed bandits. The main contributions are:\n1. The authors developed a new algorithm called BoBW-LIL'UCB. By specifically tuning a parameter $\\gamma$ of the algorithm, this new algorithm can either achieve the optimal guarantee for regret minimization of best arm identification (in the fixed budget setting).\n2. The authors theoretically quantify the Pareto frontier of regret minimization and best arm identification, and show that cannot hope to simultaneously achieve the optimal guarantees for both regret minimization and best action identification.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the weaknesses section.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a Best of Both worlds algorithm for best arm identification in multi-armed bandits. The algorithm recovers the Pareto frontier for regret minimization and best arm identification. Further they prove lower bounds showing the no algorithm can perform optimally for BA and RM objectives simultaneously.

The reviewers unanimously liked the paper and found the paper well written and well presented. The results were appreciated by the reviewers. Happy to recommend an accept.
Decision: Accept (poster)