UCB Exploration for Fixed-Budget Bayesian Best Arm Identification
Authors: Rong J.B. Zhu
Yanqi Qiu
Venue: Accepted by TMLR ()

Abstract: We study best-arm identification (BAI) in the fixed-budget setting. Adaptive allocations based on upper confidence bounds (UCBs), such as UCBE, are known to work well in BAI. However, it is well-known that its optimal regret is theoretically dependent on instances, which we show to be an artifact in many fixed-budget BAI problems. In this paper we propose an UCB exploration algorithm that is both theoretically and empirically efficient for the fixed budget BAI problem under a Bayesian setting. The key idea is to learn prior information, which can enhance the performance of UCB-based BAI algorithm as it has done in the cumulative regret minimization problem. We establish bounds on the failure
probability and the simple regret for the Bayesian BAI problem, providing upper bounds of order $\tilde{O}(\sqrt{K/n})$, up to logarithmic factors, where $n$ represents the budget and $K$ denotes the number of arms. Furthermore, we demonstrate through empirical results that our approach consistently outperforms state-of-the-art baselines.

Published in Transactions on Machine Learning Research (10/2024)
UCB Exploration for Fixed-Budget Bayesian Best Arm Iden- tification
Rong J.B. Zhu
rongzhudffudnneetuco
Institute of Science and Technology for Broin- imain-inspired Intelligence, Fudon University
Yanqi Qiu
yanqii mimiiiiii@hhtmmmi..oo
School of Mathematics and Statistics, Wuhan University
Reviewed on OpenReview: https: // openreview. net/ forum?? id- BqS473krYa
Abstract
We study best-arm identification (BAI) in the fixed-budger setting. Adaptive allocations based on upper confidence bounds (UCBs), such as UCBE, are known to work well BAL However, it is well-known that its optimal regret is theoretically dependent on instances, which show to be an artifact in many fixed-budget BAI problems. In this paper propose an UCB exploration algorithm that is both theoretically and empirically efficient for the fixed budget BAI problem under Bayesian setting. The key idea is to learn prior information, which can enhance the performance of UCB-based BAI algorithm as it has done in the cumulative regret minimization problem. We establish bounds on the failure probability and the simple regret for the Bayesian BAT problem, providing upper bounds of O(yK/n) K/n), up to logarithmic factors, where represents the budget and K denotes the number of arms. Furthermore, we demonstrate through empirical results that approach consistently outperforms state-of-the-ate baselines.
order Õ(v
1 Introduction
We study best-arm identification (BAI) in stochastic multi-armed bandits (Audibert et al., 2010; Karnin et al., 2013; Even-Dar et al., 2006; Bubeck et al., 2009; Jamieson et al., 2014; Kaufmann et al., 2015). In this problem, the learning agent sequentially interacts with the environment by pulling arms and recciving their rewards, which are sampled i.i.d. from their distributions. At the end, the agent. must commit. to a single arm. In the standard bandit setting, the agent maximizes its cumulative reward (Lai Robbins, 1985; Auer et al., 2002; Lattimore & Szepesvári, 2019; Zhu & Rigotti, 2021). In fixed-budget BAI (Audibert et al., 2010; Karmin et al., 2013; Jamieson & Talwalkar, 2013; Li et al., 2018), the agent maximizes the probability of choosing the best arm within fixed budget. In fixed-confidence BAT, the agent minimizes the budget to attain a target confidence level for identifying the best arm (Even-Dar et al., 2006; Audibert et al., 2010; Karnin et al., 2013). Here we focus on budget BAI
Adaptive allocations based on upper confidence bounds (UCBs) are known work well fixed-budget BAL For example, UCBE (Audibert et al., 2010) is optimal, with failure probability decreasing exponentially up to logarithmic factors. However, it relies learning to the adaptive variant performing significantly worse (Karnin et al., 2013). As a result, phase-based algorithms with uniform exploration in cach phase, such as successive rejects (SR) (Audibert et al., 2010) and sequential halving (SH) (Karnin et al., 2013), have been shown lo work better in practice. Furthermore, it should be noted that irrespective the choice of the algorithms, ie., UCB-base algorithms or phase- algorithms, the optimal regret that decays exponentially are conditioned on the gaps between the maximal arm and the other arms not being small. If the gaps are small, the regret may decay polynomially instead of exponentially, will demonstrate in the next section.
plug-in approach of an unknown problem complexity term,

---

Published in Transactions on Machine Learning Research (10/2024)
It is well known that side information, such as the prior distribution of arm means, can improve the statistical efficiency of the cumulative regret minimization problem (Thompson, 1933; Chapelle & Li, 2011; Zhu & Kveton, 2022a). Motivated by this, we propose a novel, theoretically and empirically efficient, and instance- independent UCB exploration algorithm for identifying the best arm by learning the prior information of arm means. We consider a Bayesian prior selting on arm means, where arm means are sampled i.i.d. from a Gaussian distribution, with mean No and variance oß- The mean Ne shared among the arms. The variance of characterizes the spread of the arms. A lower où means that the optimal arm is harder identify, since the gaps between the optimal and suboptimal arms are smaller on average. Our study shows that learning the prior of arm means also improves the performance of the UCB-based BAT algorithm and makes it more practical, as it has done in the cumulative regret minimization problem.
Further, we adopt random effect bandits (Zhu & Kveton, 2022a) to learn the prior information. From the random effect bandits, we obtain the posterior distribution of the arm means, then apply the UCB-basod strategy for Bayesian BAI. The algorithm works as follows. In round E [n], pulls the arm with the highest UCB, observes its reward, and then updates the estimated arm means and their high-probability confidence intervals. We call it Random effect UCB Exploration (RUE).
We make several contributions. First, we show that instance-deppndencee can compromise the optimality of the UCBE algorithm, which can be considered as an artifact in many BAT problems. Second, we present an alternative formulation of the BAI problem that incorporates the prior distribution of arm means. Third, we bound the gap between the maximal arm and the others in probability. This result provides a principled basis for Bayesian BAI. Fourth, we propose the efficient, practical, and Instance-independent UCB exploration for the BAT problem, the RUE algorithm. Learning the prior information, RUE yields superior best-arm identification performance compared to statteoffthheart methods in empirical studies. Fifth, we analyze the failure probability and simple Bayes regret of RUE, and derive their upper bounds of Ö(VK/n), up to logarithmic factors. Here n represents the budget and K denotes the number of arms. Our analysis features a sharp bound on the prior gap through order statistics, and a careful comparison of the prior gap and confidence interval for bounding the error probability. Finally, we evaluate RUE empirically on a range of problems and observe that it outperforms sequential halving and successive rejects in broad domains, even works better than similarly to the infcasible UCBE in various domains. All proofs are in the appendix.
2 Exponentially Decaying Bounds in Fixed- BAI: An Artifact
Consider a fixed-budget BAI problem having K arms with mean (k, & E [K], and horizon of rounds (or budgets). In round & [n], the agent pulls arm 4 [K] and observes its reward, drawn independently of the past. At the end of round n, the agent selects arm Jn. The BAT problem concerns whether the final recommendation Jn is the optimal one or not. For sake of simplicity, we will assume that there is unique optimal arm. Let 8" = arg m Pe be the optimal arm and p., Mir
Some BAT fixed-budget. algorithms, such as UCBE and SH, are considered (nearly) optimal since they can achieve an exponentially decaying failure probability that depends on the instance. However the property of exponentially decaying failure probability conditioned. To illustrate this point, we will use UCBE as an example. Audibert et al. (2010) defines the problem complexity of the BAI problem
H
Σ A KE
where As us. ph for k * it and Ar- min μ4 p (denoted as Amin), and shows that when the exploration degree is taken appropriately, the probability of error of UCBE for K-armed bandit with rewards in [0, 1] satisfies
n K
en < 2nK exp
18H
However, the optimality of UCBE depends on H, which relies on As. particularly the minimum gap Amin- Here, we emphasize the significant impact of the minimum gap Amin- In situations where the minimum gap
2

---

Published in Transactions on Machine Learning Research (10/2024)
is small (i...,min I (5An-) log n) 1/2 implying H 2 24mm n/(27logn)) the upper bound has
2n exp
71
~ 2nk exp
n
2 2K 1/2
18H
18H
Unfortunately, the small-gap condition Amin I (54n log n) may not be small in practice. For instance, in a BAI problem with n = 10000, the small-gap regime is defined by Amin S 0.223 which is not considered small by any means.
Even when considering the lower bound, the small-gap issue remains prevalent. In Audibert et al. (2010), it is demonstrated that for Bernoulli rewards with parameters in [p, - p], where p E (0,1/2), the probability of error for UCBE satisfies
(5 + o(1))
en exp
p(1 p)1
where H H2 & log(2K)H (scc details in Audibert et al. (2010)). Consider an example where = 0.2. In cases where Amin S ((32n) log n)2/2, neglecting the contribution of the o(1) lerm, the lower bound can be expressed
5n
32n
exp
P(1
H2
2 exp (-H))
2
1/2
However, it is worth noting that the small-gap condition Amin S ((32n) log n) may not be small in practical scenarios. For instance, in fixed-budget BAI problem with n 1000, the small-gap regime is defined by Amin & 0.0147 which may not be considered very small in many fixed-budget BAT problems either.
Therefore, the exponentially decaying bounds on failure probability can be regarded as an artifact in many fixed-budget BAI problems.
At last, the presence of the small-gap problem also affects the choice of exploration degree, the upper bound of UCBE necessitates the parameter to be less than 25(n K)/(3/f). However, in these scenarios, this bound is on the order log n, which leads to logarithmic exploration instead of linear exploration in the fixed-budget BAT problem.
2.1 Scenario with Full-Information
Now, let us consider a two-arm bandit problem and examine a scenario where we have complete information: each arm & = 1,2 is pulled n times and its outcomes are observed. We assume that = 1 is the optimal arm. In this instance, we can assume that the mean reward of each arm & follows a normal distribution: Pe ~ ((rk,, -=t)), where x² represents the variance of reward noise. The probability of error can be bounded follows:
e : S (2) = Pr(6 A),
(1)
where A μ1 - and d= = (ī2 - (2)) - (م] m1) ~ (0, 20 /n). From Section 7.1 of Feller (1968), we have a lower bound of e
n1²
-1/2
n122
-3/27
1
n42
e 2
exp
=: 6
(2)
20²
26
V2T
4
Now we show that this lower error bound (2) also encounters the small-gap issue. Specifically, for the small-gap condition where A < (2an-1 1/2 with a controlling the gap size, the error bound in the full-information scenario given by
ह = (2Tr) -1/2 log (logn)-1/ - (o logn) 3/2
-2 -a/(20)
Assuming that n satisfies a log > 1, we have that when a 2 0²,
き > -2
1/2 ///l1///og// Tog 1/(log m) 3)332 3/ -1/2 1/2 Ó(
3

---

Published in Transactions on Machine Learning Research (10/2024)
Therefore, even within the realm of infeasible full information in fixed-budget BAI problems, the exponentially decaying bounds on failure probability are also artifacts. Furthermore, the error order can exceed (n-11/² depending on the gap size.
This scenario shows that achieving exponentially decaying regrets in fixed-budget BAI is infeasible when the small-gap issue is present. Therefore, the aim of this paper not to develop an algorithm with exponentially decaying bounds, but rather to create an algorithm that significantly addresses the small-gap issue and achieves polynomially decaying regret bounds.
3 A Bayesian Formulation for Best-Arm Identification
In this paper assume that the reward, denoted as Tki associated with arm k, is generated from (unknown) distribution with mean Pk. We assume that the reward noise, represented as т Mk: adheres to a vrssub-Gaussian for a constant v <> O. We introduce the assumption of random arm means on the BAT problem. Specifically, we assume that the mean arm reward Pk each arm & E [K] follows the following model
Pk MI + ò
(3)
where 6% NO of) and WO0, og) a Gaussian distribution with zero mean and variance of As a result, the mean reward of arm k pk, is stochastic variable with mean d4 and variance of Recently, Komiyama et al. (2023) considers a Baysian BAI selting where they assume the uniform continuity of the conditional probability density functions. Different from theirs, make parametric perspective on priors Pk. Our model setting has of to represent the variability of the arm means. With lower variance oi the differences among the arms are smaller. Therefore, it is harder to learn the optimal arm, as the variability of the arm means is smaller. The priors μk, E [K], are taken into account through (p)
Different from the algorithms that rely on H, in the Bayesian BAI setting pxx - μ4 for i + 1", can be arbitrarily small. Fortunately we can control the probability that the gap p4 14 less than a for any 0. This is our key in the Bayesian BAT problem. Define
e. (a) Pr sup p. - 146 sa lifi"
for any a > 0. The probability e, represents the likelihood that the optimal arm 1" at least a better than the other arms. In other words, it reflects the probability of obtaining a gap between and the other arms that is less than a based on the prior distribution. In the BAI problem, decreases as the numbers of pulls increases, allowing for control over the probability. This highlights the inherent difficulty of the Bayesian BAI problem when dealing with the prior distribution of (μи)&E(K)-
Theorem 3.1. Assume pe, for & E [K], are independently and identically distributed from N N(Ho ( Then for a 0,
ex S Cka/oo
where OK = 4/22n K y (422
+
V2
This thcorem provides principled basis for Bayesian BAI in the following aspect. For any a > O, the probability of bounding the gap by is inversely proportional to the s.d. of arm means, do, and logarithmic of the number of arms, K. It means that the effect of increasing K e, is negligible up to logarithmic factor.
We end this section by comparing of with Amin- In our Bayesian BAI setting, of = E[(pu pa)) which represents the expected value of the squared deviation of μ from Ago This measure does not rely on the minimum gap Amin- In other words, of can be ((1) even if Amin o(1) Typically, of 0(1), which largely avoids the small-gap problem. Furthermore, as shown in Section 5, our analysis accommodates a smaller of = O(1/K)
4

---

Published in Transactions on Machine Learning Research (10/2024)
4 Algorithm
In Section 4.1 we show the Bayesian estimation, and provide heuristic motivation for why the use of confidence intervals is applicable to Bayesian BAL At last we propose variant of the UCB algorithm in Section 4.2.
4.1 Estimation
For arm & and round t, we denote by Th the number of its pulls by round t, and by T T,,T the sequence its associated rewards.
We use Gaussian likelihood function to design our algorithm. More precisely, suppose that the likelihood of reward Tk,Tes time t, given Pkx were given by the pdf of Gaussian distribution M(pg, where we take x² 8- for 0 < 8 1. We emphasize that the Gaussian likelihood model for rewards is only used above to design the amm.rithm. The assumptions on the actual reward distribution are the v'-sub-Gaussian assumption. This setup is analogous to the one described in Agrawal & Goyal (2013).
Let the history H, = (Ie, Ti, )==1 In the context where the prior for μ is given by N (HH, oō), deriving the posterior distribution utilized by our algorithm is straightforward:
He N (RR,, T..).
(4)
Here, the posterior mean f of pi is given by
Ak,t (1 - wk,))oo + Wh.Th..
(5)
where what = o0/(08 +T, and
-1
Te,t
Fo.
(1 Tkat
Wk,t
rk.j
1==1
k=1
The posterior variance The is given by
(1 1--wy Wk.e)
(6)
Thtt
Thet
K
Σ Th - wh,r)
The following proposition motivates the use of confidence intervals in Bayesian BAI. Proposition 4.1. Let AE = po pkk For any sub sub-optimal arm l + i", we have
Pr(fu,n An Hn) S exp
+ exp
ST
8
Proposition 4.1 shows that the probability of failing to identify the best arm depends on the gap A and -h. for 1: E [K]. This result shows that the widths of the confidence intervals affect the failure probability. Motivated by this observation, we design an efficient UCB-base based BAI algorithm by using the estimates from random effect bandits.
4.2 Random-Effee UCB Exploration
We apply random effect bandits to BAI, and propose novel UCB-based exploration algorithm, called Random effect UCB Exploration (RUE). In RUE, the upper confidence bound of arm k in round is
UR Pu.--1 + / 27 log
5

---

Published in Transactions on Machine Learning Research (10/2024)
Different from ReUCB (Zhu & Kveton, 2022a), which minimizes the cumulative regret and uses the degree of exploration log I, RUE uses the degree of exploration 2 2ogg,, since BAT requires high-probability confidence intervals only at the final round. In round t, the algorithm pulls the arm with the highest UCB 4 = arg [K] Uk,t and collects the associated reward. Any fixed tic-breaking rule can be used for multiple maximal.
Algorithm RUE for best-arm identification.
Initialization: Pull each arm twice for t 2K + I,..., do
3: Calculate UR = PA,c-1 + (2T log n
4: Pull the arm with the highest Uk., for k E [K]
5: Collect the reward associated the chosen arm
6: end for
Return estimated best arm Jn arg max PR.m
In RUE, the priors (μK))e[K] are taken into account through the variances oj and o², Various methods for obtaining consistent ostimators of o and ø² are available, including the method of moments, maximum likelihood, and restricted maximum likelihood. See Robinson (1991) for details. One practical implication of this is that unlike UCBE, our algorithm focuses on learning the prior implement the algorithm. This feature of RUE can have surprising practical benefits.
5 Analysis
We first bound the probability that RUE fails to identify the best arm. Let en be the probability that RUE fails to identify the best arm
Pr(h
which is over both the stochastic rewards and randomness in arm means (μи)Rε(K)- The main novelty in our analysis is that we control the failure probability of carefully comparing the gap of (Fx) and the confidence bounds.
Theorem 5.1. Consider Algorithm in a K-armed bandit with a budget n 2 4(K - 1). Denote p = (K(a) + +2) + oKo + +2) oB) and Ho (K + 2 002 Then the faiture probability of Algorithm is
HolK - 11 logn
Hy log n
3(20 2j +1
en STV
K(n - 1(K-4K1)) 1)) +2Kn-mhh 2Kn V
nk
where 7 =2= (411+4p)
4p)-1(22+ 4p) 4p)ck and m 10// +00))(( 4p) 20-02-0-000
Following the Bayesian failure probability of RUE in Theorem 5.1, we bound its simple Bayes regret
sr, = Elu, - [.a.).
where the expectation is over stochastic rewards and the randomness (μu)RE(K)- By applying Theorem 5.1, demonstrate in the following theorem that the simple Bayes regret is KK/).
Theorem 5.2. Consider Algorithm in Kaareed bandit with budget 4(K - 1). Under the condition
of Theorem 5. the simple Bayes regret of RUE is
2Ho(K - -1)
2H, logn
+ 40p 4 K Kn [nnmmK+1 Kn s120 1o2) 1
22m
8r, SK/
KM
nk
K(n 4(K 1))
where 4(1 + 4p) Log

---

Published in Transactions on Machine Learning Research (10/2024)
5.1 Discussion
The parameter å in Theorems 5.1 and 5.2 controls the last term of the bounds. When ô S last term is O(K/n). As introduced in Section 4.1, 8 == a 222 denotes the ratio of v² to the variance o² of the Gaussian likelihood designed in the algorithm. The condition on å implies that larger o² than v² is required in the Gaussian likelihood. This requirement is analogous to that in Agrawal & Goyal (2013). Moreover, Kn - -K++ = ((Knn) when mK 2 2. Typically when K > og. o², we have = 1, which impllies m s that the upper bounds on the failure probability and the simple Bayes regret are Ö(v Hs/n) respectively.
o2m 2(2of+02)) the
Clearly, the condition mk 2 permits of = O(1/K). Hence, Theorems 5,1 and 5.2 state
Here characterize the hardness of the task using the quantity H, (K (K which relies the parameter set of bandits (K, o o²). The quantity Hs increases as the number of arms K increases, the noise variance x² increases, or the variability of the arms' mcans o² decrcascs. Obviously, H₁ O(K when of = 0(1 or o = O(1/K), given that o² = 0(1). In this case, the upper bounds are O(vK/n). This indicates that the bounds remain O(VK/n), even when of are small (i.e., o = O(I/K)).
As demonstrated in Section 2, the upper bound on the failure probability of UCBE exhibits an exponential decay that is conditioned on the value of Amin- When Amin is small, their bound degenerates to a polynomially decay, resulting a failure probability of Ö(Kn=)) where > depends on how small Amin is. In contrast, the bounds provided Theorems 5.1 and 5.2 are instance--indeeendent, meaning that they solely depend on the budget n and the bandit class defined by the number of arms and the variances, denoted as (K, og o²), for which RUE is designed. These bounds not influenced by the specific instances within the class, ensuring their independence from the particular characteristics of each instance. Nevertheless, as shown in Section 3, ob characterizes the variability of the arms' means μ4 in relation to μo: thereby permitting very small Amin- Consequently, the small-gap issue does not pose significant challenge in our algorithm.
5.2 Proof Outline
Here we outline the proof. Comprehensive details can be found in the Appendix. Without loss of generality, we assume arm the optimal arm, i.c., f4- = Ar. Note that the initial round is 2K + 1, since every arm is pulled twice in the first 2K rounds. Denote
cha-1 2T log
We define the events that all confidence intervals from round 2K + 1 to round n hold as,
E (Vk [K]t (2K + I,..., ,n] |a4 fur nck,t)
where 7 1/(1+4p).
The error probability is decomposed as
Pr Pf Mn, > 0)
=Pr (P - PJ,) (pi, m1) > () Pr + Pr ((AJ.. - pJJ) - (Pi, - -m) A.. 18) Pr
<Pr(As, < <Cnc + (.) + Pr (8),
(7)
From (7); en is decomposed into two terms. The first term compare the prior's gap with the upper confidence bounds. The second term is the probability that the confidence intervals do not hold.
Denote 8 = 1 K-lop=a and
20z0² log
Ōk
Wk E [K]. V Thno + to2
(8)
Because čz can be bounded by Ck, Ck I v Bünn as shown in Zhu & Kveton (2022a). Thus, we have that
Pr (As, < n(ei, + c)..))) SPr (An, < <n/Blenn ttn.n)

---

Published in Transactions on Machine Learning Research (10/2024)
Now we investigate to bound for any & * 1. Denote Amin
Pr (Ae S BBB(C,, + an,)E
min
A.. We define the following event of comparing a.,. with min: k#1
& = fōim S Amin/(BB(C + +n))--
We can show that
Pr A / (E
Baga² log n Ti + o² o 1
Pr (EIEE) = Pr Amin < <1+
Then we investigate Tin- We show that
Ti, 2 n - 2(K - 1)(1 + A) log 2(K - 1).
(9)
For decoupling Ti. and Amin, define the following event of controlling the minimum gap:
& E2 { 2 2(1 +
(K ( logn
On the event &2, (9) follows that
Tf. I. + + azn/22 1) 1)
Thus, have that
230002 log Ti { + o²
Pr Amin < <(1
200 log
<Pr
A Amin < (1 1)
1) 02 E
+ Pr (EsEE
ofn/2 20 K
30 log
o0 log
+
ojnn 40z(K - 1) 20
n (K 11)
where the last step is from applying Theorem 3.1. Therefore, the first term of the decomposition in (7) is bounded.
At last, we investigate the second term of the decomposition in (7). Given our analysis of the algorithm, it is imperative to note that these models may be entirely unrelated to the actual reward distribution. Consequently, we cannot make the assumption that the posterior distribution of μĄ u4-given the historical data is Gaussian, with the posterior mean Pu.z- Instead, we opt for a decomposition approach, as detailed below. Denote 31 1 K-too//oo (oğ + o²). Define the following event:
Egs- = {Irme - mel S / 110../22
We have that
n Pr
a 02 pk T2.10 + o²
nRRt
K n
Pr (8)
S
Pr
(Esk)
(10)
We aim to bound the two terms in (10). Utilizing the properties of sub-Gaussian distributions, it follows that To. Po is sub- Gabussssiann By applying the mub-Gaussian tail inequality, we obtain that
8 Fo, pal
nēke 2
< <exp (- (-11 (1+4p))002
Pr
T +
8

---

Published in Transactions on Machine Learning Research (10/2024)
On the other hand, exploiting the mbb-Gaussian property of F,, Mks we have
(- (55(1 4p) +
31 log
Pr (Ear) S exp
Therefore, the theorem is proved.
6 Experiments
We conduct two kinds of experiments. In Section 6.1, μ4 are random, where various settings considered. In Section 6.2, Ak are fixed. Note that our modcling assumptions are violated here. We show these experiments of fixed fou because they are benchmarks established by Audibert et al. (2010) and Karnin et al. (2013).
Our baselines include the state-of-the-ar Successive Rejects (SR) (Audibert et al., 2010), Sequential Halving (SH) (Karnin et al., 2013), the UCB-exploration (UCBE) (Audibert et al., 2010), and Top- Two Thompson sampling (TTTS) (Russo, 2020). As mentioned in Section 4.2, in the implementation of RUE, we use the estimates of the variances of and o². Therefore, hyperparameters are required for RUE. UCBE is implemented 2n/ HI since this parameter works the best overall according to Audibert et al. (2010) and Karnin et al. (2013). We do not report the adaptive variant of UCBE because it performs much worse than UCBE; even worse than SH (Karnin et al., 2013). Note UCBE is infeasible since it requires the knowledge of a problem complexity parameter H, which depends on gaps. Additionally, we assess the two-stage algorithm proposed by Komiyama et al. (2023), but it does not perform well in our experiments (see Figure in the Appendix). Consequently, we exclude their method from our comparison.
with parameter
6.1
Random /Ak
For random (s: we have the following three sctups:
(R1) Gaussian rewards with mean Aa and variance 6² = 1, where ~ ((0,00000000 0.5) for E [K].
(R2) The same μ4 as RI, but the rewards are Bernoulli rewards with means pk.
(R3) Bernoulli rewards with μ ~ ~0000..5) for E [K].
These sctups allow us explore how the performance of RUE compare against benchmarks under various distributions of noise and reward means. Although we assume Gaussian distribution in our Bayesian BAT formulation, we also evaluate the performance of RUE for R3 when the assumption does not hold.
We report the performance for K = 20. Due to the randomness of pk: the gaps and the difficulty of BAI varies. Therefore, we conduct our experiments on 50 sampled pı,...,/KK /KK- For each set, we evaluate the performance RUE and state-of- thetrrr algorithms, and then report the average performance. Like the case of fixed μu, we also set a = 2 through three random setups.
The maximum budgets values based on the median complexity terms in experiments, which H = 2000 for R1 and R2, and H RJ 5500 for R3. Then we study various budget settings performance varies when the budget is less than H and double of H.
set to N 5000 for R1 and R2, and to N 12000 for R3. We choose these
(N/4, N//, N), so that we can show how the
In Figure 1, we report the average performance over 50 experiments, and also boxplots of the relative performance of the baselines SR, SH, UCBE, and TTTS with respect to RUE. We observe that, except for performing better or worse than TTTS in R3, RUE dominates other methods in all three setups, and even works better than UCBE. For example, for the case of n N/2 in R3, the error probabilities of RUE are smaller 23%, 24%, and 31%, respectively, than UCBE, SH, and SR. These results shows the flexibility of RUE across various distributions of reward noise and across various distributions of reward means.
6.2 Fixed 1*
Like Karnin al. (2013), we study six different experimental sctups comprehensively assess the RUE's
performance:
(F1) One group of suboptimal arms: p 0.45 for k 2.

---

Published in Transactions on Machine Learning Research (10/2024)
0.30
error probabiitt
eoTo probabilty
enoor probablity
0.20
0.1 0.2
0.2
SR SH
0.10
UCSE
TTTS
RUE
0.00
5000
1250
2500
5000
12000
budget
budget
budget
0.15
000 8
error difference
0.10
emorr difference
000
ap
error difference
0.05
0.00
-0.05
-0.30
1250
2500
5000
1250
2500
5000
3000
6000
12000
budget
budget
budget
(a) Setup R1
(b) Setup R2
(c) Setup R3
Figure 1: Random μg- Upper panel: the average performance among 50 experiments. The bars denote the standard error of the mean among 50 experiments. The lower panel: the error difference of the performance of the baselines, SR, SH, and UCBE, respectively, with respect to that of RUE among all 50 experiments.
(F2) Two groups suboptimal arms: μa 0.45 for &o 2....., and μk = 0.3 otherwise.
(F3) Three groups of suboptimal arms: μ4 0.48 for ......., μt 0.4 for h 6..... : 13 and μ* 0.3 otherwise.
(F4) Arithmetic: The suboptimality of the arms form arithmetic series where μl2 0.5 1/(5K) and
μК 0.25.
(F5) Geometic: The suboptimality of the arms form an geometric series where = 0.5 - 1/(5K) and
μK = 0.25.
(F6) One real competitor: μr = 0.5 - 1/(OK)) and μ = 0.45 for = 3,...., K.
In all setups, the reward distributions are Bernoulli and the mean reward of the best arm is 0.5. The number of arms K 20. We also examine K E {40, 80} in Figure of Appendix, show how RUE scales with K.
We set H as the maximal budget for matching the hardness and for the limit of resources. Then study various budget settings E {[H/2], [H , 2 H") so that can show the performance when the budget is less or more than H. In RUE, we plug in the estimators of the variances Ø² and of as in Zhu & Kveton (2022a).
Figure 2 shows results for our six problems. We have the following observations. First, RUE consistently outperforms SH and in all problems (except for the [2/2], [M]] of FI, where it's a little worse than SR). Take F2 as an example. For the budget [H/2], [H], and 2 H]H], the error probabilities of RUE are smaller 10%, 20%, and 66%, respectively, than SH. Second, comparing the infeasible UCBE, RUE outperforms it in F3,F5-F6, performs similarly to it in F4, and performs worse than it in F1 and F2. Third, comparing to TTTS, RUE outperforms it in most cases but performs slightly worse in n H for F4 and F6. Fourth, comparing with various K E {40, 80} in Figure of Appendix, we observe that the outperformance of RUE over others grows as increases. In summary, the observations suggest that RUE is expected to work well in various domains.
7 Related Work
Bubeck al. (2009) showed that algorithms with most logarithmic cumulative regret, such as UCB1 (Auer et al., 2002), are not suitable for BAI; and proposed to explore aggressively using O(vn) confidence
10

---

Published in Transactions on Machine Learning Research (10/2024)
F1
F2
F3
6.4
SH
63 04
eno probability
UCBE
TTT5
error Arronaati
BnT probabliig
RUE
0.3
02
00
0.1
0.1
0.0
60
3800
7601 budget
15202
1550
3101 budget
6202
5488
10975 budget
21950
F4
F5
F6
04
0.3
enor probabili
error probability
0
0.
0.1
01
00
7003
14006
28012
6286
12773
25546
20900
41800 budget
83600
budget
budget
Figure Fixed pk. All standard errors are less than 0.016 and not reported. Each experiment is with budgets H/2, H, and 2H (labels of the x axis). The dotted lines denote error probabilities 0 and 0.2, just for visual clarity.
intervals. Motivated by it, Audibert et al. (2010) considered the fixed budget setting, where UCBE and successive rejects are proposed for BAI. UCBE and its adaptive version have O(vn) confidence intervals. comparison, our work shows that a UCB- based algorithm with O(Vlogn) confidence intervals performs well in BAI On the other hand, the infeasible UCBE algorithm depends on the unknown gap, while the estimatod gap makes the adaptive UCBE less efficient. Our algorithm does not rely on the actual or estimated gaps. Karnin et al. (2013) proposed sequential halving, which popular in hyperparameter optimization (Jamicson & Talwalkar, 2015; Li et al., 2018). Different from the method, this work focuses efficient exploration based on upper confidence bounds.
Fixed-confidence sctting was introduced by Even-Dar et al. (2006), who proposed successive climination for BAI. Mannor Tsitsiklis (2004) derived light disstibbutionddeeeddeeu lower bounds for several variants of successive elimination, Jamieson et al. (2014) proposed li-UUCB; Tánezos (2017) extended lil-UC the KL-based confidence bounds (Garivier & Cappe, 2001; Kaufmann & Kalyanakrishnan, 2013), and Shang al. (2020) adjusted TTTS (Russo, 2020) for fixed-confidence guarantees. In comparison, we focus the fixed-budget setting.
Although the fixed-confidence setting and the bixed-budget setting seem "dual" to each other, they perform differently in several domains. Recently, Qin (2022) proposed an open problem regarding whether there exists an algorithm other than uniform sampling itself that performs uniformly no worse than uniform sampling in the fixed-budget sctting. Degenne (2023) and Wang et al. (2023) demonstratod that the fixed-budget setting, there are no such universally superior adaptive algorithms in several BAI problems. These studies show that the expected probability of error of BAI in the budget setting may be significantly different from that in the fixed-confidence setting. Our paper presents another observation in the fixed-budget setting: exponentially decaying bounds in fixed-budget BAI are an artifact.
Zhu Kveton (2022a;b) proposed random effect bandits for cumulative regret minimization. Our work can be viewed as an extension of Zhu & Kveton (2022a) best-arm identification. We show that the prior information is helpful develop an efficient, practical UCB exploration algorithm for the Bayesian BAI problem.
11

---

Published in Transactions on Machine Learning Research (10/2024)
Recently, Bayesian BAI has received attention. Russo (2020) proposed Bayesian algorithms, top-two variants of Thompson sampling (TTTS), that are tailored to identifying the best arm. His analysis focused on the frequentist consistency and rate of convergence of the posterior distribution. Shang et al. (2020) followed his work and proposed a variant of TTTS for justifying its use for fixed-confidence guarantecs. Different from theirs, we propose a variant of UCB exploration by using the prior information ion and show its efficiency by analyzing the error probability and the simple Bayes regret. Komiyama et al. (2023) and Azizi al. (2023) derived lower bound for this setting and a two-phase algorithm that matches it. However, empirically their algorithm works badly as shown in Appendix. Recently, Atsidakou et al. (2023) introduced Bayesian version of the SH algorithm and provided prior-dependent bound on the probability of error in multi-armed bandits. Furthermore, Nguyen et al. (2024) established upper prior-dependent bounds on the expected probability of error of prior-informed BAI in Structured Bandils.
Our Bayesian BAT formulation is also related to Bayesian optimization (Snock et al., 2012) which assumes a Gaussian process prior and updates the posterior with new observations. Similar to Bayesian optimization, the Bayesian BAT setting uses Gaussian prior to learn configuration evaluations. However, unlike Bayesian optimization, the Gaussian prior in the Bayesian BAI setting models reward means of individual arms.
8 Conclusions
We introduce a formulation of the Bayesian fixed-budget BAI problem by modeling the arm means, and propose RUE, an efficient, instance-independent UCB exploration for fixed-budget BAL We empirically show that RUE outperforms SH and SR in broad domains, even works better than or similarly to the infeasible UCBE in various domains. We derive ((/K/n) bounds on its Bayesian failure probability and simple Bayes regret. Inspired by Li et al. (2018), which demonstrates that BAT can be applied to hyper-parameter optimization, our proposed RUE has potential for use in investigation in the future.
optimization. This application warrants serious
Nevertheless, an inherent limitation of this study is the absence of a corresponding lower bound, as obtaining one for fixed-budget BAI is a challenging task (Qin, 2022). Another limitation is that the analysis in this paper ouly focuses on the Gaussian settings. Nevertheless, RUE does not assume any distributional form, since the setting in (3) does not assume any particular distribution, but only assumes that the first- and second-order moments of μ4 are bounded. Morcover, our empirical results show that RUE works well in broad domains where the Gaussian assumptions are violated. Therefore, an interesting question is to provide the bound on the failure probability under sub-Gaussian settings.
In our analysis, we assume that o² and of are known. However, in practice we substitute these parameters with their estimates. Investigating the effect of this substitution in the Bayesian setting is extremely challenging since we need to integrate the error probability over the posterior of these parameters. We leave this challenging problem as a future direction for research. Nevertheless, we expect this effect to be small since the agent's estimates of these parameters should converge to their true values as the agent gathers more data.
Author Contributions
Rong J.B. Zhu designed and performed the research, performed the analysis and experiments, and wrote the paper. Yanqi Qiu provided the proof for Lemma A.1.
Acknowledgements
We are very grateful to Branislav Kveton for insightful discussions and invaluable comments on the preliminary version of this paper. We thank the Assigned Action Editor, Marcello Restelli, and the three reviewers for their insightful comments and suggestions that significantly improve this paper.
12

---

Published in Transactions on Machine Learning Research (10/2024)
References
S. Agrawal and N. Goyal. Thompson sampling for contextual bandits with linear payoffs. In Proceedings of the 30th International Conference on Machine Learning, 2013.
A. Atsidakou, S. Katariya, S. Sanghavi, and B. Kveton. Bayesian fixed-budget best-arm identification. arXiv:2211.05572,, 2023.
J.-Y. Audibert, S. Bubeck, and R. Munos. Best arm identification in multi-armed bandits. In Proceedings of the 23rd Conference on Learning Theory, 2010.
P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite time analysis of the multiarmed bandit problem. Machine Learning, 47:235-250 256, 2002.
J. Azizi, B. Kveton, M. Ghavamzadeh, and S. Katariya. Meta-learning for simple regret minimization. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 6709-6717, 2023.
S. Bubeck, R. Munos, and Stoltz. G. Pure exploration in multi-armed bandits problems. In International Conference on Algorithmic. Learning Theory, 2009.
O. Chapelle and L. Li. An empirical evaluation of Thompson sampling. In Advances in Neural Information Processing Systems, volume 24, 2011.
R. Degenne. On the existence of a complexity in fixed budget bandit identification. NKXV:23033094466 2023.
E. Even-Dar, S. Mannor, and Y. Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Leurning Research, 7(1079-1105), 2006.
W. Feller. An Introduction to Probability Theory and Its Applications, volume 1. New York: Wiley, third edition, 1968.
Garivier and O. Cappe. The KL-UCB algorithm for bounded stochastic bandits and beyond. In Proceading of the 24th Annual Conference on Learning Theory, pp. 359 376, 2001.
K. Jamieson and A. Talwalkar. Non-stochastic best arm identification and hyperparameter optimization. In International Conference on Artificial Intelligence and Statistics, 2015.
Jamieson, M. Malloy, R. Nowak, and S. Bubeck. lil' UCB An optimal exploration algorithm for multi- armed bandits. In Proceedings of The 27th Conference on Learning Theory, volume 35 of Proceedings of Machine Learning Research, pp. 423 439. PMLR, 13-15 Jun 2014.
Z. Karnin, T. Koren, and O. Somekh. Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning, 2013.
E. Kaufmann and S. Kalyanakrishnan. Information complexity bandit subset selection. Proceedings of The 36th Conference on Leorning Theory, 2013.
E. Kaufmam,, O Cappé, and A. Garivier. On the complexity of best arm identification in multi-armed bandit models. Journal of Machine Learning Research, 16:1-42, 2015.
J. Komiyama, K. Ariu, M. Kato, and C. Qin. Rate-optimal bayesian simple regret in best arm identification. Mathematics of Operations Research, 2023.
T. L. Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Muthemalics, 6(1):4 22, 1985.
T. Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2019.
L. Li, K. Jamieson, G. DeSalvo, A. Rostamizadeh, and A. Talwalkar. Hyperband: novel bandit-based approach to hyperparameter optimization. Journal of Machine Learning Research, 18:1-52, 2018.
13

---

Published in Transactions on Machine Learning Research (10/2024)
S. Mannor and J.N. Tsitsiklis. The sample complexity of exploration in the multi-armed bandit problem. The Journal of Machine Learning Research, 5:623 648, 2004.
N. Nguyen, I. Aouali, A. György, and C. Vernade. Prior-dependent allocations for bayesian fixed-budget best-arm identification in structured bandits. arXiv:2402.06887,, 2024.
C. Qin. Open problem: Optimal best arm identification with fixed-budget. In Proceedings of Thirly Fifth Conference on Learning Theory, volume 178, pp. 5650 5654, 2022.
G.K. Robinson. That blup is a good thing: The estimation of random effects (with discussion). Statistionl Science, 6:15 51, 1991.
D. Russo. Simple bayesian algorithms for best-arm identification. Operations Research, 68(6))1625 1647, 2020.
Shang, de Heide, E. Kaufmann, P. Ménard, and M. Valko. Fixed-conffidence guarantees for bayesian best-arm identification. In Proceedings of The 23vd International Conference on Artificial Intelligence and Statistics, volume 108, 2020.
J. Snoek, H. Larochelle, and R. Adams. Practical bayesian optimization of machine learning algorithms. Advances in Neural Information Processing Systems, 2012.
E. Tánczos, R. Nowak, and B. Mankoff. A KL-LUCB bandit algorithm for large-scale crowdsourcing. In Advances in Newral Information Processing Systems, 2017.
W.R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25:285-204 1933.
P.-. Wang, K. Ariu, and A. Prouticre. On uniformly optimal algorithms for best arm identification in two-armed bandits with fixed budget. arXiv:2308. 12000, 2023.
R.J.B. Zhu and B. Kveton. Random effect bandits. In Proceedings of The 25th International Conference Artificial Intellignnce and Statistics, volume 151, 3091-3107, 2022a..
R.J.B. Zhu and B. Kveton. Robust contextual linear bandits. arXiv:2210. 14488, 2022b.
R.J.B. Zhu and M. Rigotti. Deep bandits show off: A simple efficient exploration in deep networks.
A Advances Newral Information Processing Systems, 2021.
14

---

Published in Transactions on Machine Learning Research (10/2024)
A Appendix
A.1 Proof of Theorem 3.1
First we provide the following lemma, which provides a basic tool for bounding the gap pa - Ma. Then we show that the probability e, depends on of and In K by following Lemma A.1.
Lemma A.1. Assume X& for = 1,..., K, are independent and identioally distributed from (0 1). Denole (1) 2 ((2) 2 ... X(K) the non-increasing re- re-ordering of XK.. Then there exists a constant C' > 0, such that for all integers K 2 2 and for a > 0,
Pr(X()) - X(2) 5 S C(In KY
Proof. Denote n(a) (r(X(1) X(2) S aa). Let (x)) and ((x) be the cumulative distribution function and the density function, respectively, of X,, From the joint distribution of ((1)xX(2)) (Fact 2 in the Appendix), we have that
m(a) K(K - 1) 0s5a- (z)
K(KK - 1)
((x2) k - f(x2) + 2)d22d2
OSSSARRIER
K(K - 1)
(12) K- 2 (x2) (0(22 + aa) (x22)ddr2
JGER
D(x2 + +a)dd( K-1 (K - (K-1) / (12
K
B2ER
12ER
K K
((12) K-1 (akkk-(oe f(52 + a)do2 - (K- -1
JIER
K
((x2) k (xx2 + 0x) ax)
#zER
It follows that
(1aa)= = -K
(122) K-1
f'(22 -
a)dr2.
Fix e > 0 (which will be choosen later on). For any integer K 2 2, let ax > 0 be the unique solution to the equation
12 = cK
In K
Set
Ti(a)= = -K -K
(112) K1 (((2 + adde2;
T2(a) = K /
1(zz) K- k + a)daz.
Z2Sax
We can now write
v'(a) = (i( + T2(a).
For the term Ti (a), by noting that f' + a) < for all x2 and ((x2)) S 1, we have
Ti(a) < -K f 1 f2 + addr
K aie/2
Kf((a + Kf(ax)
/2T
15

---

Published in Transactions on Machine Learning Research (10/2024)
For the term (a),, we have
T2(a)] S K sup
(x22)
/ If + a)lday
225ax
425UK
/
( = 2K
< (k((k)) K-1
((ax) K-1
R2ER
22T
Using the classical estimate
e 12
@(1) 1
22T 12 +1
obtain
(a) <
K
dic/2
+
2K
((ax) K-1
V2
22T
k-1
K
o /2
2K
1
aK +
-
S
e
+
c
2
22T
By our choice of ak, we have e ok//2
ax In K ck
hence
ak InK
2K
[1
1
0
In K
K-1
T/(a) S
c²2T
2t
2T
u + 1
ck
For K large enough such that cK/ In K 2 Ve, we have azeak 2 and thus og > 1. Then
cK
R2 2 12
In K
Tt. follows that for K large enough, we have
cK
1 I S /
2ln
In K
Consequently, for K large enough and a > 0,
(1)a) < In K
in
In )
cK
+
2K
(1
1 In K K-1
c/T)
2t
2 ck
Using the elementary inequality: for any x >
2 (1 - 1-- In(1 1/x)) = exp(-x
Σx xk) S _!
km
we obtain that, for any integer K 2 2,
(K-1)
2K
1
In K
K-1
2K
In K
2/2zak
1
2
2T
ck
V
2 2/2x
ck
2K
(k-1)
2
2/2eck
K-
2/200 2N
/2T
V2T
2
2
<
K²
K
10200
v /2m
22T
Now let us take
C
4v2x
16

---

Published in Transactions on Machine Learning Research (10/2024)
We obtain that, for K large enough,
In K CV
cK
2 V2T
('()) -
In
+
In K
By the mean value theorem, obtain
In CVT
cK
nTa)=
+
a.
K
2
This clearly implies the desired result.
Denote P(1) 2 M(2) 2 MM(R the non- non-increasing re-ordering of ;i.....;K. MKK. We have
(a)) = Pr (M() 142) <a) Pr (oo 1 (M(1) M(2)) <0 a).
Then the theorem is direct result of Lemma A.1.
A.2 Proof of Proposition 4.1
Let be the midpoint between piu and prm Then
Pr(ūx,n As ml Hm)
Pr(pe e)Pr(Pann 2 Pu mlliis > v) + Pr(firr a S v)Pr((ae.n 2 Pi allii S 11)
< Pr(Ak.m 20) + Pr(Ass S 1)
Pr(Ak.n μb 2 4x/2) + Pr(Ase p4- S Ax/2) S exp [- + exp (87;
where the last step direct result of the Gaussian tail bound shown in Appendix A.6.
A.3 Proof of Theorem 5.1
Without loss of generality, we assume arm is the optimal arm, ie., p4 μ1. Note that the initial round is 2K + 1, since every arm is pulled twice in the first 2K rounds. Denote
Ck 2 log n.
We define the events that all confidence intervals from round 2K + 1 to round n hold as,
E = (Ak K] (2K + 1...., ... |p4 fuual $ nek,
where = 1/(1++44p)
The arror probability dccomposed as
Pr Pr An, 0) ((DJ... (1,a.) ) - (fi,n - m1) A,, Pr)
+ Pr ((fJ... - (J,)) - (A1,0 - P1) > A, (8) Pr (8)
< Pr (A,, < mT(1, + (.) + Pr (E)
(11)
From (11), en is decomposed into two terms. The first term is to compare the prior's gap with the upper confidence bounds. The second term the probability that the confidence intervals do not hold.
At first, we focus on investigating the first term of the decomposition in (11). Denote 8 = ==1+ K- 111k-lop' and K-log/ (o) + o²). Noting that C just relies its corresponding Tk Tk,n, using Ōk instead of
17

---

Published in Transactions on Machine Learning Research (10/2024)
Ck, breaks the dependence of arm & other arms. Because Čk, be bounded by Ck,zi CK, S v VB0k,n
shown in Zhu & Kveton (2022a). Thus, we have that
(r 7 + c)m Pr (As, < kn/B(G + +Zmm))
(12)
Now we bound Pr (Ax S / + (xE)) for any + 1. Denote Amin min Ar. We define the following event of comparing čτ,n with Ami:
kØ1
& = (ōr, S Amin/ + ()))
We have that
Pr A BVB( + (.,))E)
A A / (1 + n) + n B6 ( (1, + ()) (E)
I Pr
I Pr
A (1 + 1) mli,) + Pr (E1
(13)
We shall show As 2 77(1 + 11 Bex,n given and & when r satisfies 2n(1 + 1) /3/31 + 1 1 1 0. In the following we take 77 = 1/(1 + 4p). Lemma A.2 shows that on the event & the following result holds:
A 2 (1 1 BiCK, (1 1) Be,.
implying that, on the events & and E,,
4 2 - (1- n) B2 771 + 11 Bök
where the second inequality is from satisfying 27(1 + 11) 3/3: + 1
15 O. Thus, (13) follows that
Pr AA < B1BB(E,, + (() s (E( = Pr (Amin < (1+
Boz0² log n Tino + oz E
(14)
Now we investigate Ti, Lemma A.2 shows that on the event & for k + 1,
Th, 2 22 21 30² logn.
Bo²
It follows that
T2,x n
Σ Th 2 TTa kyl
2(K - 1)(1 + >)> 30 log - 2(K 1).
(15)
For decoupling Tı, and Amin, we define the following event of controlling the minimum gap:
& f 2 2(1 + /)
1) -
log
On the event &,, (15) follows that
T In + 0z > o/n/2 - 20 + +
18

---

Published in Transactions on Machine Learning Research (10/2024)
Thus, we have that
23030 log Ti, + o²
Pr Amin (1 +
200 log Bn/2 200 K - 1) 0² 18
Srr
V A min < <11+ <(1+
2216
+ Pr (821))
2,00 log ofn/2 20 K - 1) 02
=Pr
Amiu <(1+7)
Pr AAiin < <1 11) / 1)302n
-log log
sck(1+ m)) (1
2 logn
4/302 log
(16)
osn/2- 20 - 1) 0²
nn(KK -
where the last step from Lemma A.1.
At last, we investigale the second term of the decomposition in (11). Define the following event: for each arm k
Egk: {IFKE - ual nn knVBiiu. Bicu,122
From (4), we have that
Pr (E)
<
Pr (lAx, - Mkl > nccke)
k=
Pr (lo? (Tx,/ ~F) mx) + wk,e mx) > mcxk.)
1= t=1
Pr 2 (T + o - pal ny 31C,e/1))) Pr (Est)
(17)
where the last inequality is from whe < 1 and Cb. 2 VBičk,n as shown in Zhu & Kveton (2022a).
We shall investigate Pr (T= + o² | erties of sub-Guutunn Gaussinsiin, Fa. - po sub-Gaussian with the parameters
mxl > T/FTC,,12 and Pr (Exx) respectively. From the prop-
2
K
V
Wk.t Tr.e
Σ
Wr 2T. + 2² TT,A) 2 K + 12/2),
where the inequality from the Cauchy Schwarz inequality and Te 2 2. It follows that
2,3 (T + K log
Pr (TT02/TT + o ual > nV Biēn.12) <2exp
4(1 + 40) 22/2)
3,oo log
<2exp
(18)
(1 + 2p)
where the first step from the sub-Gaussian tail inequality and the second step from Th, 2 2 and o² v² On the other hand, we have
Pr (Esx) 2 exxp
(- 2TT 2 2100 log 4v2 0²)
< 2exp (-811 + 4p) (20 +
310 logn
19

---

Published in Transactions on Machine Learning Research (10/2024)
where the first step is from the sub-Gaussian tail inequality and noticing o² = = =2/6, and the last step is from TE.t 2 2. Denote (1 4 200, we have
Pm
Pr (E) S 2Kn mk+1 + 2Kn =
(19)
Therefore, combing (14), (16), and (17), the theorem is proved.
A.4 Proof of Theorem 5.2
Let P(1) max k [K]] and P(K) min fna k [K]}. We have that
STn
Pr(Jn = k)B Jra, P.J. Jn, = k]
leftt
Se, E [Ma) m(x) S 20 /2 log Ken,
where the first. inequality is from μ.,, 2 M(K): and the last step is due to the fact of E [M(D) pao) S
200 K. Combing Theorem 5.1, the proof is concluded.
A.5 Lemmas
Lemma A.2. On the event E, We have the following two results: for k +
Tk. 22 (1 1)² log
(20)
(1 (1-1) (1 s (1+ / 381, + A..
(21)
Proof. (20) is obviously true at time t -K +1. We assume that holds at time t t2 2K + 1. I++1 # k then TR.+1 TR, thus it still holds. If Je+1 k, means that Pa,t + Ck.t 2 fi + C1.z- Note that on E, we have that
PI. + C1 2 Mi, and Pu. + Ch. S Pa + (1 + 1)22
They follows
(1 + 1)ck 2 As.
Thus, Tei S 2A 11) logn holds due to Th. Boto (Tk o²) shown in Lemma A.3. By using
TRA+1 TR., 1, we prove (20).
(21) is obviously true at the initial time t 2 + 1. We assume that it holds at time t 2 2K +1. If I441 # 1, then T1++1 = Ti,, thus it still holds. If [+1 = 1, it means that
Pk. + C,et S fiit + C1
Note that on E, we have that
A + C1 S pn (1 + 1)0,,, and faa + Caet 2 us (1 n)
They follow
(1 - n)Ck. S (1 + D)CL, + Ag.
Since CK,t 2 Vir and 61 S B shown Lemina A.3, we have that
(1 - 11-n)Ba Bia. $ (1 n) Ben, + A
By using TR,t+1 = Tk,t + 1, we prove (21).
Lemma A.3. (Lemmas 8 5 in Zhu & Kueton (2022a))
0f
of
T2 +02 (1 K- 0//0////0// + +²))) S -h <
(1 + 2-
Th. + 2
20

---

Published in Transactions on Machine Learning Research (10/2024)
A.6 Some Properties
Fact 1 (Gaussian lail bound) Let X be Gaussian random variable, i.e., X ~ NN1 o²), then for all >> 0,
(- a²
Pr(X 2 a) S exp
20
Fact 2 (Joint distribution of ordered statistics) Denote F(x) P(X S 2) and f(x) its density. Let
X()) 2 ((2) 2 ... 2 X(k)- For 2 the density of (X(1), ((2)) is
p(22, n(nn () (og))
Fact 3 (Some results on Gaussian)
2T 12 +1 exp(-12/2) < +(() Pr(X 1) 1) W2x
exp(-12/2),
Pr(X(2) < = [0))'* + n -(0]1000)"-
A.7 More Results Experiments
Performance of the two-stage algorithm We show the empirical studies of the Iwo-stage algorithm. For overall checking the performance, we check under various q 0.1, 0.2,... ..... 0.9, we report their performance under Setup F4 in Figure 3. The figure shows the Two-Stage algorithm is bad under various q.
0.8
errrr probability
error probability
0.6
0.4
0.4
n=7003
0.2
n=14006
n=28012
0.0
0.1
0.3
0.5
0.7
0.9
0.2
0.4
0.6
0.8
1
q
q
(a) Fixed Setup F4
(b) Random Setup R2
Figure 3: The error probability of the Two-Stage algorithm with various values, averaged over 1000
independent executions (results standard deviations of less than 0.016).
Impact of arm number K. We ran the experiments with n 20, 40, 80 arms in order to examine how the performance of each algorithm scales as the number of arms grow. We report the result on the arithmetic sctting (Setup F4) in Figure 4, where K 40 and 80 are shown. Comparing various K, the benefit using RUE increases as K increases.
21

---

Published in Transactions on Machine Learning Research (10/2024)
K=20
K=40
K=80
01 02 0.3 04
sroo probabiltyy
0.
SH
UCBE TTTS
RUE
10
7003
14006
28012
20716
57431 budget
114862
1c+05
2e405 budget
4c-05
budget
Figure 4: The probability of the different algorithms in Sctup F4 with more arms, 40 and 80 arms (left and right subfigures respectively). The results are averaged over 1000 independent executions (all standard errors are less than 0.016 and not reported). For K = 80, we set N = 400000 as the maximal budget for the limit of resources when 2/1 is too big.
22


Reviews:
[{"review_id": "mavp0OEwgU", "reviewer": "Reviewer_aRGJ", "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- The novel framework of Bayesian BAI (in which the mean rewards of different arms are sampled from a normal distribution) is interesting and makes sense to me. It reminds me of an assumption commonly used in Bayesian optimization: people often assume that the reward function is sampled from a Gaussian process, and also assume that the noise is Gaussian or sub-Gaussian (it would be great if you discuss the connections with Bayesian optimization from this perspective).\n- For the experiments, I particularly like the ones with fixed mean rewards $\\mu_k$, since it potentially shows the performance of the method in practical scenarios where the Bayesian assumption is likely to be violated.\n\nWeaknesses:\n- As the authors also commented in the Conclusion section, the proposed method requires the mean reward variance $\\sigma_0^2$ to be known. But I also understand that such assumptions are not uncommon in the bandit literature, and that the paper discussed methods to estimate it when it's unknown. So this may not be a major concern.\n- Section 5.1, first line: a formula for $\\delta$ is given here, which is required for the failure probability and simple regret to be exponentially decreasing. What's the intuition behind this formula? When is this formula likely to be satisfied? I think some discussions are needed.\n- Also in Section 5.1, although I agree that the failure probability and simple regret can be exponentially decreasing for very small reward gaps, however, if I understand correctly, it's hard to characterize how small the reward gap can be. This is because the final theoretical results depend on $\\sigma_0$. The consequence is that making comparisons with classical BAI (and justifying the theoretical advantage of the proposed method) is not so straightforward.\n- In the experiments in Section 6.1, why do you draw the $\\mu_k$'s from a uniform distribution? Why not a Gaussian distribution as in your assumptions?\n- In your experiments, did you use the estimated $\\sigma_0^2$ or the groundtruth one?\n- The figure legends are missing in Figure 1.", "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 presents a novel method for fixed-budget Bayesian best-arm identification (BAI). The paper proposes a new perspective on Bayesian BAI, in which the mean reward of all arms are sampled i.i.d. from a Gaussian distribution with a fixed variance. The observed rewards are corrupted by a sub-Gaussian noise. Analysis of both the failure probability and expected simple regret are given, and intuitive comparisons are made w.r.t. prior BAI works. The main theoretical advantage of the theoretical results in this work is that the failure probability is exponentially decaying even for small reward gaps (in other words, small variance of mean rewards). Experiments are performed, for both random and non-random mean rewards, to show that the propose method works competitively.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- In addition to what I've discussed above, another interesting thing about the paper is that the algorithm is in fact almost the same as classical UCB (except for a small difference in the exploration parameter). So, does this mean that UCB can both achieve BAI and cumulative regret minimization? I think some discussions would be helpful.", "broader_impact_concerns": "No ethical concerns since the paper is more theoretical.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8mkXWNAqdV", "reviewer": "Reviewer_RtAM", "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\n* The writing is well-structured.\n* The math appears to be mostly correct, and the mistakes appear to be minor or correctable.\n* The general method is reasonably interesting\n\n# Weaknesses\n\n* The main motivation, which is that gap-based error bounds become trivial when gaps are small, is not really solved by this method or analytic framework. Similar trivial bounds result from this work as well, when $\\sigma_0$ is small. (More on this below.)\n* The math has some fairly basic math errors, some of which appear to be simple mis-statements, others appear to be conceptual errors.\n* In the proof outline from the main text, the notation $\\tilde c_{k,n}$ is used, but the term is not actually defined till the appendix. \n* The literature review is likely out of date. There are no references after 2022, and this is a fast-moving field. I would imagine that many relevant works have been published in the past two years. In order to maintain anonymity, I purposely did not do a literature review in case this paper exists as a preprint. \n\n## Trivial Bounds for Small $\\sigma_0$\n\nThe right side of the bound in Theorem 5.1 goes to $\\infty$. In particular, as  $\\sigma_0\\to 0$, we get the following limits:\n* $\\gamma \\sqrt{H_b}\\to \\infty$\n* $Kn^{-mK+1}\\to Kn$\n\nSo, it suffers from similar problems as the instance-dependent bounds (which depend on gap calculations)\n\nSimilarly, the regret bound of Theorem 5.2 is trivial for small $\\sigma_0$. (It goes to $\\infty$ for the same reasons.)\n\nAs a result, the discussion throughout the paper about $\\tilde O(\\sqrt{K/n})$ bounds appears to be incorrect, or at best, rather misleading. \n\n## Incorrectness of Proposition 4.1\n\nThe most glaring mathematical error is Proposition 4.1. The right side of the probability expression is a random variable, depending on the number of times the arms have been pulled. So, this is not a sensible expression. The only way to make sense is to be examining some sort of conditional probability, such as conditioning on the arm pull counts.\n\nLuckily, it appears that Proposition 4.1 is not actually used in the main analysis.\n\n## Smaller Math Errors\n\n- In the use of sub-Gaussian concentration bounds, one-sided bounds appear to be used for two-sided expressions, in many cases. Most likely, these bounds need to increase by a factor of 2. \n- The event $\\mathcal{E}_3$ should really be a collection events for each arm, $k$.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 presents a Bayesian algorithm for best-arm identification, based on a variation of the Upper Confidence Bound method, and then bounds the resulting error probability and regret (in a Bayesian sense). The method is compared with existing methods numerically, and is shown to perform well.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Explain more carefully the effect of small $\\sigma_0$, and determine whether this method / analysis actually gives any advantage over the prior gap-dependent bounds.\n* Specifically fix the incorrect language about the $\\tilde O(\\sqrt{K/n})$ bounds. \n* Fix the math errors.\n* Update the literature review.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "OOoHjxOh5f", "reviewer": "Reviewer_VTwj", "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:\n1. Important theoretical results regarding the proposed algorithm are provided.\n2. The proposed algorithm is empirically evaluated.\n3. The writing and exposition is generally clear and easy to understand.\n\n### Weaknesses/Questions:\n1. The paper claims that UCBE in the ordinary fixed budget BAI setting is instance dependent because in some instances, when the problem complexity $H$ is greater than some threshold dependent on $K$ and $n$, the exponentially decaying bound becomes polynomial. However, the provided bounds for RUE are also polynomial. Is the factor of $\\sqrt{K}$ improvement the best we can do with the additional side information of the prior? Are there some instance specific conditions where we can recover the exponential bound? In principle, we should be able to do better with more information and assumptions.\n2. How does the work in this paper compared to the Bayesian BAI methods in \"Simple Bayesian Algorithms for Best-Arm Identification\" by Russo (2016) ? Are the theoretical results comparable? Why weren't the algorithms from this paper evaluated in the empirical studies? It seems to be closer to the studied setting than UCBE and the other non-Bayesian BAI algorithms.", "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 best-arm identification (BAI) in the fixed budget setting with Bayesian assumptions on the mean arm rewards; specifically, they assume the means are themselves sampled from a Gaussian distribution. The paper claims that, for existing BAI fixed budget algorithms with exponentially decaying failure probability bounds, these bounds are actually instance-dependent and may be only polynomially decaying in some instances. The paper develops an algorithm called RUE (Random Effects UCB Exploration) which may be seen as a conversion of a previous ReUCB (Zhu & Kveton, 2022) algorithm for multi-armed bandits (under the Bayesian assumptions) to the BAI setting. The paper provides upper bounds on the failure probability and simple Bayes regret for RUE and shows that they are both of order $\\mathcal{O}(\\sqrt{K/n})$ up to log factors. RUE is compared to previous (non-Bayesian) BAI algorithms and to one Bayesian BAI algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Would strengthen work:\n1. Please answer the questions in the previous section, and add the discussion to the paper for clarity.\n2. Compare the algorithm to the Bayesian BAI algorithms in Russo (2016), or justify why they are not comparable.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a novel approach to fixed-budget Bayesian Best-Arm Identification (BAI), with significant theoretical contributions and experimental validation. Initially, the reviewers had concerns regarding mathematical rigor, theoretical explanations, and comparisons to prior work. However, after the authors' detailed and well-received rebuttal, all three reviewers now recommend acceptance, highlighting the value of the work and acknowledging that the issues raised have been satisfactorily addressed.

While the paper is in good shape, minor revisions are still needed. Specifically, some adjustments to the use of mathematical notation (such as replacing Big-O with Big-Omega where appropriate) and a correction to the definition of the supremum in the probability expression are required. Additionally, a few formatting issues, such as appendix numbering, should be addressed for clarity.

With these small revisions, the paper is ready for publication and is a valuable contribution to the bandit community.
Decision: Accept (poster)