Finite-Time Logarithmic Bayes Regret Upper Bounds
Authors: Alexia Atsidakou
Branislav Kveton
Sumeet Katariya
Constantine Caramanis
sujay sanghavi
Venue: NeurIPS 2023 poster (2023)
Keywords: Bayesian bandits
logarithmic regret bounds
multi-armed bandits
linear bandits
TL;DR: We derive the first finite-time logarithmic Bayes regret upper bounds for Bayesian bandits

Abstract: We derive the first finite-time logarithmic Bayes regret upper bounds for Bayesian bandits. In a multi-armed bandit, we obtain $O(c_\Delta \log n)$ and $O(c_h \log^2 n)$ upper bounds for an upper confidence bound algorithm, where $c_h$ and $c_\Delta$ are constants depending on the prior distribution and the gaps of bandit instances sampled from it, respectively. The latter bound asymptotically matches the lower bound of Lai (1987). Our proofs are a major technical departure from prior works, while being simple and general. To show the generality of our techniques, we apply them to linear bandits. Our results provide insights on the value of prior in the Bayesian setting, both in the objective and as a side information given to the learner. They significantly improve upon existing $\tilde{O}(\sqrt{n})$ bounds, which have become standard in the literature despite the logarithmic lower bound of Lai (1987).

Finite-Time Logarithmic Bayes Regret Upper Bounds
Alexia Atsidakou University Texas, Austin
Branislay Kveton
Sumeet Katariya Amazon
AWS Al Labs"
Constantine Caramanis University of Texas, Austin
Sujay Sanghavi
University of Texas, Austin / Amazon
Abstract
We derive the first finite-time logarithmic Bayes regret upper bounds for Bayesian bandits. In multi-armed bandit, we obtain O(ca log n) and Oce log² n) upper bounds for an upper confidence bound algorithm, where с₁ and сa are constants depending the prior distribution and the gaps of bandit instances sampled from it, respectively. The latter bound asymptotically matches the lower bound of Lai (1987). Our proofs are major technical departure from prior works, while being simple and general. To show the generality of our techniques, we apply them to linear bandits. Our results provide insights the value of prior in the Bayesian setting, both in the objective and as side information given to the learner. They significantly improve upon existing (VVR) bounds, which have become standard in the literature despite the logarithmic lower bound of Lai (1987).
Introduction
stochastic multi-armed bandit [Lai and Robbins, 1985, Auer al., 2002, Lattimore and Szepesvari, 2019] is an online learning problem where a learner sequentially interacts with an environment over rounds. In each round, the learner takes an action and receives its stochastic reward. The goal of the learner is to maximize its expected cumulative reward over rounds. The mean rewards of the actions are unknown a priori but can be learned by taking the actions. Therefore, the learner faces dilemma: explore, and learn more about the actions; exploit, and take the action with the highest estimated reward. Bandits have been successfully applied to problems where uncertainty modeling and subsequent adaptation are beneficial. One example are recommender systems [Li et al., 2010, Zhao al., 2013, Kawale al., 2015, Li et al., 2016], where the actions are recommended items and their rewards are clicks. Another example is hlyeer-paamen optimization [Li al., 2018], where the actions are values the optimized parameters and their reward optimized metric.
the
Cumulative regret minimization in stochastic bandits has been traditionally studied in two settings: frequentist [Lai and Robbins, 1985, Auer et al., 2002, Abbasi-Yadkori Yadkori et al., 201 I] and Bayesian [Gittins, 1979 Tsitsiklis, 1994, Lai, 1987, Russo and Van Roy, 2014, Russo al., 2018]. In the frequentist setting, the learner minimizes the regret with respect to fixed unknown bandit instance. In the Bayesian setting, the learner minimizes the average regret with respect to bandit instances drawn from a prior distribution. The instance is unknown but the learner knows its prior distribution. The Bayesian setting allows surprisingly simple and insightful analyses of Thompson sampling. One fundamental result in this setting is that linear Thompson sampling [Russo and Van Roy, 2014] has comparable regret bound LinUCB in the frequentist setting (Abbasi-Yadkori et al., 2011, Agrawal and Goyal, 2013, Abeille and Lazaric, 2017]. Moreover, many recent meta- and multi-task bandit works [Bastani et al., 2019, Kveton et al., 2021, Basu et al., 2021, Simchowitz et al., 2021, Wang et al., 2021, Hong et al., 2022, Aouali al., 2023] adopt the Bayes regret to analyze the stochastic
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

structure of their problems, that the bandit tasks are similar because their parameters are sampled i..d. from a task distribution.
Many bandit algorithms have frequentist regret bounds that match a lower bound. As an example, in K-armed bandit with the minimum gap A and horizon n, the gap-dependent O(K -1 log n) regret bound of UCB1 [Auer et al., 2002] matches the gap-dependent {2( A log n) lower bound of Lai and Robbins [1985]. Moreover, the sap-free Ö(v Kn) regret bound of UCB1 matches, up to logarithmic factors, the gap-free S2( (V) lower bound of Auer et al. [1995]. The extra logarithmic factor in the Ö(v Kn) bound can be eliminated by modifying UCB1 [Audibert and Bubeck, 2009], In contrast, and despite the popularity of the model, matching upper and lower bounds mostly do not exist in the Bayesian setting. Specifically, Lai [1987] proved asymptotic cp. log' n upper and lower bounds, where C₁ is a prior-dependent constant. However, all recent Bayes regret bounds are Ö( (())) [Russo and Van Roy, 2014, 2016, Lu and Van Roy, 2019, Hong et al., 2020, Kveton et al., 2021]. This leaves open the question of finite-time logarithmic regret bounds in the Bayesian setting.
In this work, we answer this question positively and make the following contributions:
1. We derive the first finite-time logarithmic Bayes regret upper bounds for a Bayesian upper confidence bound (UCB) algorithm. The bounds are Oca log n) and (c2, log" n), where and ca are constants depending on the prior distribution h and the gaps of random bandit instances sampled from h, respectively. The latter matches the lower bound of Lai [1987] asymptotically. When compared to prior ((yr) bounds, we better characterize low-regret regimes, where the random gaps are large.
2. To show the value of prior as a side information, we also derive a finite-time logarithmic Bayes regret upper bound for frequentist UCB algorithm. The bound changes only little as the prior becomes more informative, while the regret bound for the Bayesian algorithm eventually goes to zero. The bounds match asymptotically when n -> oo and the prior is overtaken by data.
3. To show the generality of our approach, we prove O(des log" n) Bayes regret bound for a Bayesian linear bandit algorithm, where denotes the number dimensions and ca is a constant depending on random gaps. This bound also improves with better prior.
4. Our analyses major departure from all recent Bayesian bandit analyses, starting with Russo and Van Roy [2014]. Roughly speaking, we first bound the regret in a fixed bandit instance, similarly to frequentist analyses, and then integrate out the random gap.
5. We show the tightness of our bounds empirically and compare them to prior bounds.
This paper is organized as follows. In Section 2, we introduce the setting of Bayesian bandits. In Section 3, we present a Bayesian upper confidence bound algorithm called BayesUCB [Kaufmann et al., 2012]. In Section 4, we derive finite-time logarithmic Bayes regret bounds for BayesUCB, in both multi-armed and linear bandits. These the first such bounds ever derived. In Section 5, we compare our bounds to prior works and show that one matches an existing lower bound [Lai, 1987] asymptotically, In Section 6, we evaluate the bounds empirically. We conclude in Section 7.
2
Setting
We start with introducing our notation. Random variables are capitalized, except for Greek letters like 0. For any positive integer n, we define [n]] = {I..... n2.. The indicator function is [. The i-th entry of vector is vú. If the vector is already indexed, such as Uy, we write U3 We denote the maximum and minimum eigenvalues of matrix M E Rdxd by > (M) and Aa(M),, respectvell.
Our setting is defined as follows. We have multi-armed bandit [Lai and Robbins. 1985, Lai, 1987, Auer et al., 2002, Abbasi- Yadkori et al., 201 1] with an action set A. Each action E A is associated with reward distribution Pa ()) which is parameterized by an unknown model parameter shared by all actions. The learner interacts with the bandit instance for rounds indexed by t E [n]. In each round t, it takes an action A, E A and observes its stochastic reward Y, ~ PA. (:; 0). The rewards are sampled independently across the rounds. We denote the mean of pa P=(:;0) 0) by pa (0) and call it
'The work started at Amazon Search.
2

---

Algorithm BayesUCB
1: for t 1,...,, do
2: Compute the posterior distribution of & using prior and history H,
3: for each action A do
4:
Compute U according to (1)
5:
Take action A arg max aEA U2aa and observe its reward Y
the mean reward of action a. The optimal action is A, = arg max aeA (0) and its mean reward is J.a (0) = HA..(1 (0). For fixed model parameter 8, the n-round regret of policy is defined as
(0(00) (0) -
R(n; 0)
E
where the expectation is taken over both random observations Y, and actions A,. The suboptimality gup of action a is A.. (0) Ma (0) and the minimum gap is Amin = minaaed)(A41 A..
Two settings are common in stochastic bandits. In the frequentist setting [Lai and Robbins, 1985, Auer et al., 2002, AbbaiiYadkoor et al., 201 IJ, the learner has no additional information about 0 and its objective is to minimize the worst-case regret for any bounded 0. We study the Bayesian setting [Gittins, 1979, Lai, 1987, Russo and Van Roy, 2014, Russo et al., 2018], where the model parameter O is drawn from prior distribution that is given to the learner as a side information. The goal of the learner is to minimize the n-round Bayes regret R(n) = E R(; 0)], where the expectation is taken over the random model parameter @ h. Note that A., Aes and min are random because they depend on the random instance 6.
3 Algorithm
We study a Bayesian upper confidence bound algorithm called BayesUCB [Kaufmann et al., 2012]. The algorithm was analyzed in the Bayesian setting by Russo and Van Roy [2014]. The key idea in BayesUCB to take the action with the highest UCB with respect the posterior distribution of model parameter 0. This differentiates it from frequentist algorithms, such as UCB1 [Auer et al., 2002] and LinUCB [Abbasi- -abkasi-Yadkori al., 2011], where the UCBs are computed using a frequentist maximum likelihood estimate (MLE) of the model parameter.
Let H, (Ae, Yı) Et be the history of taken actions and their observed rewards up round t. The Bayesian UCB for the mean reward of action at round is
Ur. 1aa (0e) + Cr.a
where Ú, is the posterior mean estimate of 0 at round i and Ct, is a confidence interval width for action a at round t. The posterior distribution of model parameter is computed from prior h and history H, using Bayes' rule. The width is chosen so that 1mt, (0:) Pa (0)) I Cr.a holds with a high probability conditioned any history H, Technically speaking, Craa is a half-width but call it width to simplify terminology.
Our algorithm is presented in Algorithm 1. We instantiate it in Gaussian bandit in Section 3.1, in Bernoulli bandit in Section 3.2, and in a linear bandit with Gaussian rewards in Section 3.3. These settings are of practical interest because they lead to cnaputationalll--fffiiii implementations that can be analyzed due to fooeed-form posteriors [Lu and Van Roy, 2019, Kveton et al., 2021, Basu et al., 2021, Wang et al., 2021, Hong et al., 2022]. While we focus deriving logarithmic Bayes regret bounds for BayesUCB, we believe that similar analyses can be done for Thompson sampling [Thompson, 1933, Chapelle and Li, 2012, Agrawal and Goyal, 2012, 2013, Russo and Van Roy, 2014, Russo et al., 2018]. This extension is non-trivial because a key step in our analysis is that the action with the highest UCB is taken (Section 5.3).
3.1 Gaussian Bandit
In K-armed Gaussian bandit, the action set is A [K] and the model parameter is R Each action E A has a Gaussian reward distribution, Pa (-) _N o²), where 02 is its mean and
3

---

0 is a known reward noise. Thus (0) = aa The model parameter is drawn from a known Gaussian prior fi(.) = Po G where oo E I2 is vector of prior means and op > i prior width.
The posterior distribution of the mean reward of action at round t is; 0,,0, t,a), where
L.a (% + -
is the posterior variance, Nr.. -E= 1(A a} is the number of observations of action up to round t, and
L- Σ - a}
00,
oi On Mu,a
is the posterior mean. This follows from classic result, that the posterior distribution of the mean of a Gaussian random variable with a Gaussian prior a Gaussian [Bishop, 2006]. The Bayesian
UCB of action a at round & Uz,a = dr + Ct.o where Cr.a / 20 log(1/6) the confidence interval width and E (0, 1) is failure probability of the confidence interval.
3.2 Bernoulli Bandit
In KCarmed Bernoulii bandit, the action set is = [K] and the model parameter is R Each action AA has Bernuulli reward distribution, P= Ber(-; 8a). where 6, is its mean. Hence
Ha (0) = Oa- Each parameter O₂ is drawn from known prior Beta(:; Ba), where Oaa > 0 and Ga > 0 positive and negative prior pseudo-counts, respectively.
The posterior distribution the mean reward of action a at round is Beta(:; at,a: B,,a) where
t-1
011a = Ga + Σ
[[A
Be. = Ba 1(A a) (1-
E=1
This follows from a classic result, that the posterior distribution of the mean of a Bernoulli random variable with beta prior is a beta distribution [Bishop, 2006). The corresponding Bayesian UCB is Uza oe, + Ct.a, where
0r,- aiaa
log(1/6)
log(1/6) 2(O + Ba + Nt.a + 1)
Ct,a = V 2(0 + fr.a + 1)
01,a + Br.a"
denote the posterior mean and confidence interval width, respectively, of action a at round I; and 5 E (0, 1) is failure probability of the confidence interval. The confidence interval is derived using the fact that Beta(:; at Br,a) is sub-Gaussian distribution with variance proxy a(a +3 tN. +Ne.+
[Marchal and Arbel, 2017].
3.3 Linear Bandit with Gaussian Rewards
We also study linear bandits [Dani et al., 2008, Abbasi- Yadkori et al., 201 with a finite number of actions A C dd in d dimensions. The model parameter is 0 Rd All actions AA have Gaussian reward distributions, (-(::) = =V(:: a TT. T,, a²), where a > 0 is a known reward noise. Therefore, the mean reward of action a is pa (0)
The parameter is drawn from known multivariate Gaussian prior f(-)) (-; 0o. Eo). where 9g Rd is its mean and En Rdxd is its covariance. represented by a positive semi- cemi-definite (PSD) matrix.
The posterior distribution of 0 at round / is (1; Ú,, Ex), where
1-1
[-1 E = (2T + + G, = G Σ A
0, = Ei
100 10 00 +
Σ ArYe
Here O, and Et, are the posterior mean and covariance 0, respectively, and G, the outer product of the feature vectors of the taken actions up round t. These formulas follow from a classic result,

---

that the posterior distribution of a linear model parameter with a Gaussian prior and observations is Gaussian [Bishop, 2006]. The Bayesian UCB of action at round is Uta a 0g + Cr where Ctaa V 2llg is the confidence interval width, å (0, 1) is failure probability of the confidence interval, and |a]| = Va Ma.
4 Logarithmic Bayes Regret Upper Bounds
In this section, we present finite-time logarithmic Bayes regret bounds for BayesUCB. We derive them for both K-armed and linear bandits. One bound matches an existing lower bound of Lai [1987] asymptotically and all improve upon prior ((yr) bounds. We discuss this in detail in Section 5,
4.1 BayesUCB in Gaussian Bandit
Our first regret bound is for BayesUCB in K-armed Gaussian bandit. It depends on random gaps. To control the gaps, we clip them as A = max E). The bound is stated below.
Theorem 1. For any ε > 0 and (0, 1), the n-round Bayes regret of BayesUCB in K-armed Gaussian bandit is bounded as
80" log(1/0)
A²
R(n)= I E
+
A
o
aFAA.
where C = =n + 2( 2 log + 2K)oo kō is a low-order term.
The proof is in Appendix A.1. For = 1/n and 8 1/n, the bound is O(ca logn), where ca is constant depending on the gaps of random bandit instances. The dependence on on in the low-order term C can be reduced to min {ao, o7) } by more elaborate analysis, where the regret of taking each action for the first time is bounded separately. This also applies to Corollary 2.
Now derive upper bound Theorem that eliminates the dependence on random gaps. To state it, we need to introduce additional notation. For any action a, we denote all action parameters except for by 0-o (01.... 0 0.+1................. 0x) and the corresponding optimal action in 0_.. by 0- = maxxe..4. (a} 0,. We denote by fa the prior density of 02 and by h-a the prior density of 0-a. Since the prior is factored (Section 3.1), note that h())- = ha ho.(0.)) (0.) (0-a) ). for any and action a. To keep the result clean, we state it for "sufficiently" large prior variance. A complete statement for all prior variances is given in Appendix Bayesian algorithmms since their regret decreases with more informative prior. In fact, show in Appendix B that the regret of BayesUCB is ((1) for a sufficiently small ao.
We note that the setting of small prior variances favors
Corollary 2. Let o 2
8log(1/8)n' log lo Then there exist functions Ça RR 1R+ [
such
Vlogn that the n-round Bayes regret of BayesUCB in K-armed Gaussian bandit is bounded as
5/O
R(n) < 802 log(1 (1/) log
Σ aEA o_..
ha(0% Ea(0 h- (0 do C,
20 log
where C= 8 K log( (00gl//11//o// logn + 2( 2 21g 2K)ooKnō + 1 is low-order term.
The proof is in Appendix A.2. For d 1/n, the bound is Oce, log² n), where es depends on prior but not on the gaps of random bandit instances. This bound motivated by Lai [1987]. The terms & arise due to the intermediate value theorem for function hg. Similar terms appear in Lai [1987] but vanish in their final asymptotic claims. The rate 1/v Vlog in the definition of & cannot be reduced 1/polylog without increasing dependence on n in other parts of the bound.
The complexity term EaEA Sa ha(0; (At)) h de_, in Corollary 2 is the same as in Lai [1987] and can be interpreted as follows. Consider the asymptotic regime of n + co. Then, since the range of &a is [ viewed the distance between prior means. In Gaussian bandit with K actions, has closed form of 1 exp (M0.1 -Mo.2)" A general upper bound for K > actions is given below. 103
: vlognl the term simplifies to EeEA ha h (0-a) de_a and can be
5

---

Lemma 3. In a K --rredd Gaussian bandit with prior h(-) = (N: Ho. k(lx). k), we have
Σ/. EEAA B__
(Mu.a 1o0.0' )²
ha (a(( h-o(t-a) d S 2/ TOO VEAa'sa
exp
400
The bound is proved in Appendix A.3 and has several interesting properties that capture low-regret regimes. First, as the prior becomes more informative and concentrated, do - the bound goes to zero. Second, when the gaps of bandit instances sampled from the prior are large, low regret is also expected. This can happen when the prior means become more separated. |0o, M0,a' - oc, or the prior becomes wider, - xc. Our bound goes to zero in both of these cases. This also implies that Bayes regret bounds are not necessarily monotone in prior parameters, such as dg-
4.2 UCB1 in Gaussian Bandit
Using similar approach, we prove a Bayes regret bound for UCB1 [Auer al., 2002]. We view it as BayesUCB (Section 3.1) where o = oc and each action E is initially taken once at round = This generalizes classie UCB1 was proved by Lai [1987] (claim (i) in their Theorem 3). We derive a finite-time prior-dependent Bayes regret bound below.
noise. An asymptotic Bayes regret bound for UCB1
Theorem There exist functions Ea IR +
such that the n-round Bayes regret of UCB1
in K K-armed Gaussian bandit is bounded Vlogn
R(n) - S02 log (0lgg(1/))) (1/8)
Σ
/
ha(0; (a
aEA -_a
where C= log( + + 2( 2log(110)))))) 2K)oKnn + E.EA E [A +1
The proof is in Appendix A.4. For 1/n, the bound is O log² n) and similar to Corollary 2. The main difference is in the additional factor 2 log in Corollary 2, which decreases the bound. This means that the regret of BayesUCB improves do decreases while that of UCB1 may not change much. In fact, the regret bound BayesUCB is O(1) as on - (Appendix B) while that UCB1 remains logarithmic. This is expected because BayesUCB has more information about the random instance as og decreases, while the frequentist algorithm oblivious to the prior.
4.3 BayesUCB in Bernoulli Bandit
Theorem and Corollary can be straightforwardly extended to Bernoulli bandits because
PP (10a - Or.al 2 Cr.a He < 25
holds for any action and history H, (Section 3.2). We state the extension below and prove it in Appendix A.S.
Theorem 5. For any E > 0 and (0, 1), the n-round Bayes regret of BayesUCB in K-armed Bernoulli bandit is bounded as
log(1/5) (a, Ba + 1)
R(n)
S
+C.
A:
u.
where = en + 2Kn is a low-order term.
Moreover, let X = min.EA aa + Bo + and S 2 1og((15)) log log Then
R(n) < 2 log((1)) logn
A
Σ
h.(0" (G. h2 h CC,
2 log nh
aE
where C logKog(L/0) 2Kn8 + is low-order term.

---

4.4 BayesUCE in Linear Bandit
Now we present a gap-dependent Bayes regret bound for BayesUCB in a linear bandit with a finite number of actions. The bound depends on random minimum gap. To control the gap, clip it as A min max m))
Theorem 6. Suppose that ||0||2 I L. holds with probability at least 1 - 8.. Let ||a||2 & I, for any action a E A. Then for any e > and (0,1), the n-round Bayes regret of linear BayesUCB is bounded as
U,max d
U. Ti
R(n)= S SE
log
1
log(1/8) + KL6
A
log
+
T D.max
o²d
with probability at least 1 - 82, where 00,aax
The proof is in Appendix A.6. For = 1/n and 1/n, the bound is O ca log n). where ca is constant depending the gaps of random bandit instances. The bound is remarkably similar to the frequentist Odd A min log² n) bound in Theorem 5 of Abbasi- Yadkori et al. [2011], I], where Amin is the minimum gap. There are two differences. First, integrate A A over the prior. Second, bound decreases as the prior becomes more informative, m, -> O.
In a Gaussian bandit, the bound becomes O(KE [1/ min. log" n). Therefore, it is comparable to Theorem up to additional logarithmic factor in This is due to a more general proof technique, which allows for dependencies between the mean rewards of actions. We also note that Theorem does not assume that the prior is factored, unlike Theorem 1.
5 Comparison to Prior Works
This section is organized follows. Section 5.1, we show that the bound in Theorem 5 matches an existing lower bound of Lai [1987] asymptotically. In Section 5.2, we compare our logarithmic bounds to prior Ō(vī) bounds. Finally, in Section 5.3, we outline the key steps in our analyses and how they differ from prior works.
5.1 Matching Lower Bound
In frequentist bandit analyses, it is standard to compare asymptotic lower bounds to finite-time upper bounds because finite-time logarithmic lower bounds do exist [Lattimore and Szepesvari, 2019]. We follow the same approach when arguing that our finite-time upper bounds are order optimal.
The results in Lai [1987] are for single-parameter exponential-farte family reward distributions, which excludes Gaussian rewards. Therefore, we argue about the tightness of Theorem 5 only. Specifically, we take the second bound in Theorem 5, set 8 = 1/n, and let n - co. this case, 2 n
-> 0 and (.(-) + 0, and the bound matches up to constant factors the lower bound in Lai [1987] (claim (ii) in their Theorem 3), which
E/ ha(0 h- (1.0a)) do_a) GE
Ω log"
Lai [1987] also matched this lower bound with an asymptotic upper bound for frequentist policy.
Our finite-time site--time upper bounds also reveal an interesting difference from the asymptotic lower bound in (2), which may deserve more future attention. More specifically, the regret bound of BayesUCB (Corollary 2) improves with prior information while that of UCB1 (Theorem 4) does not. We observe these improvements empirically as well (Section and Appendix D). However, both bounds are the same asymptotically. This is because the benefit of knowing the prior vanishes in asymptotic analyses, -
since 20 log + 0 in Corollary 2 as n - co. This motivates the need for finite-time logarithmic Bayes regret lower bounds, which do not exist.
7

---

5.2 Prior Bayes Regret Upper Bounds
Theorem and Corollary 2 are major improvements upon existing Ō(vn) bounds. For instance, take a prior-dependent bound Lemma 4 of Kveton et al. [2021], which holds for both BayesUCB and Thompson sampling due to well-known equivalence of their analyses [Russo and Van Roy, 2014, Hong al., 2020]. For ò 1/n, their leading term becomes
4 2 K log (V n++
o2o0 (Vn+o2og V Vo200 ²
Similarly to Theorem and Corollary 2, (3) decreases as the prior concentrates and becomes more informative, da + However, the bound is Ö(vn). Moreover, does not depend on prior means Mo or the gaps of random bandit instances. Therefore, it cannot capture low-regret regimes due to large random gaps A Theorem or a small complexity term in Corollary We demonstrate empirically in Section 6.
When the random gaps A Theorem are small or the complexity term in Corollary 2 large, our bounds can be worse than Ō(yr)) bounds. This is analogous to the relation of the gap-dependent eep-dependent
and gap-free frequentist bounds [Lattimore and Szepesvari, 2019]. Specifically, bound of UCB1 in a K-armed bandit with 1-sub-Gaussian rewards (Theorem 7.1) is O A -! min log n), where min is the minimum gap. A corresponding gap-free bound (Theorem 7.2) is O(v log n.. V((K (K log n)/n). To get the best bound, the The latter is smaller when the gap is small, Amia = o( olv
/
minimum of the two should be taken, and the same is true in our Bayesian setting.
No rrpendeepnndent Bayes regret lower bound exists in linear bandits. Thus we treat E [1/44 minl in Theorem 6 as the complexity term and do not further bound it in Corollary 2. To compare our bound fairly to existing Ö ((yn) bounds,
derive Ō(yn) bound in Appendix C, by relatively minor change in the proof of Theorem A similar bound can be obtained by adapting the proofs of Lu and Van Roy [2019] and Hong al. [2022] to linear bandit with a finite number of actions. The leading term of the bound is
20 m.a dn
2 Ú.
2
log
1 +
log(1/8).
o2d
log [
Similarly to Theorem 6, (4) decreases as the prior becomes more informative, U,,aax > O. However, the bound is Ö(yr) and does not depend on the gaps of random bandit instances. Hence it cannot capture low-regret regimes due large random minimum gap Amiu Theorem We validate empirically in Section 6.
5.3 Technical Novelty
All modern Bayesian analyses follow Russo and Van Roy [2014], who derived the first finite-time time Ö(Vi) Bayes regret bounds for BayesUCB and Thompson sampling. The key idea in their analyses is that conditioned on history, the optimal and taken actions are identically distributed, and that the upper confidence bounds are deterministic functions of the history. This is where the randomness of instances in Bayesian bandits is used. Using this, the regret at round is bounded by the confidence interval width of the taken action, and the usual Ö(vn) bounds can be obtained by summing up the confidence interval widths over rounds.
The main difference in our work is that we first bound the regret in fixed bandit instance, similarly to frequentist analyses. The bound involves A- and is derived using biased Bayesian confidence intervals. The rest of our analysis is Bayesian in two parts: we prove that the confidence intervals fail with low probability and bound random A following similar technique to Lai [1987]. The resulting logarithmic Bayes regret bounds cannot be derived using the techniques of Russo and Van Roy [2014], as these become loose when the confidence interval widths are introduced.
Asymptotic logarithmic Bayes regret bounds were derived in Lai [1987]. From this analysis, we use only the technique for bounding - when proving Corollary 2 and Theorem 5. The central part of our proof is a finite-time per-instance bound on the number of times that suboptimal action taken. This quantity is bounded based on the assumption that the action with the highest UCB is taken. A
8

---

(a) Decreasing width
(b) Increasing gap
BayesUCe
10a
UCB1
BayesUCa log
UCBI log bound
Regrot
00 bound
10a
10a
0.4
5.0
Prior gap
Figure 1: Gaussian bandit as (a) the prior width du and (b) the prior gap Do change.
comparable argument in Theorem of Lai [1987] is asymptotic and on average over random bandit instances.
Experiments
We experiment with UCB algorithms in two environments: Gaussian bandits (Section 3.1) and linear bandits with Gaussian rewards (Section 3.3). In both experiments, the horizon All results are averaged over 10 000 random runs. Shaded regions in the plots are standard errors of the estimates. They are generally small because the number of runs is high.
000 rounds.
6.1 Gaussian Bandit
The first problem is K-armed bandit with K 10 actions (Section 3.1). The prior width is do 1. The prior mean is Ho, where foo1 = Do and /40.a = 0 for a > 1. We set Ag = 1 and call the prior gap. We vary d and Do in our experiments, and observe how the regret and its upper bounds change as the problem hardness varies (Sections 4. and 5.2).
We plot five trends: (a) Bayes regret of BayesUCB. (b) Bayes regret of UCB1 (Section 4.2). which is comparable frequentist algorithm to BayesUCB. (c) A leading term of the BayesUCB regret bound in Theorem 1, where 1/n and 8 = 1/n. (d) A leading term of the UCB1 regret bound: This is the same (c) with σo oo. (c) An existing Ö(v') regret bound in (3).
Our results are reported in Figure We observe three major trends. First, the regret of BayesUCB decreases as the problem becomes easier, either - O or Ao - oc. It is also lower than that of UCB1, which does leverage the prior. Second, the regret bound BayesUCB is tighter than that of UCB1, due to capturing the benefit of the prior. Finally, the logarithmic regret bounds are tighter than the Ö(vn) bound. In addition, the ((vn) bound depends on the prior only through on and thus remains constant as the prior gap Ao changes.
In Appendix D, we compare BayesUCB to UCB1 more comprehensively for various K, a, Ag. and oo. In all experiments, BayesUCB has lower regret than UCB1. This also happens when the noise is not Gaussian, which a testament to the robustness of Bayesian methods to model misspecification.
6.2 Linear Bandit with Gaussian Rewards
The second problem is a linear bandit with K 30 actions in d 10 dimensions (Section 3.3). The prior covariance is En = 0. The prior mean is 6g. where 0, = Ao and 6,,, -1 for >> 1. As Section 6.1, we set A.
and call it the prior gap. The action set A is generated as follows. The first d actions are the canonical basis in Rdd The remaining K - d actions are sampled uniformly random from the positive orthant and scaled unit length. This ensures that the first action has the highest mean reward, of Ag. under the prior mean Og. We vary do and Ao. and observe how the regret and its upper bounds change as the problem hardness varies (Sections 4.4 and 5.2). We plot three trends: (a) Bayes regret of BayesUCB. (b) A leading term of the BayesUCB regret bound in Theorem 6, where ma, Fo. 1/n, and 1/n. (c) An existing ((vr)) regret bound in (4).

---

(a) Decreasing width
(6) Increasing prior gap
BayesUCB
10a
10a
BayesUCB log bound g
((- bound
Ragnot
10
10a
10a
10a
0.4
0.6
Prior gap
Figure 2: Linear bandit as (a) the prior width do and (b) the prior gap Ao change.
Our results are reported in Figure 2 and we observe three major trends. First, the regret of BayesUCB decreases as the problem becomes easier, either dg - 0 or Åg - co. Second, the regret bound of BayesUCB decreases the problem becomes casier. Finally, our logarithmic regret bound can also be tighter than the ((vni bound. In particular, the Ō(vT) bound depends on the prior only through du. and thus remains constant as the prior gap An changes. We discuss when our bounds could be looser than (V))) bounds in Section 5.2.
7 Conclusions
Finite-time logarithmic frequentist regret bounds are the standard way of analyzing K-armed bandits [Auer et al., 2002, Garivier and Cappe, 201 1, Agrawal and Goyal, 2012]. our work, we prove the first comparable finite-time bounds, logarithmic in n, in the Bayesian setting. This is major step in theory and significant improvement upon prior Ö(vn) Bayes regret bounds that have become standard the literature. Comparing to frequentist regret bounds, our bounds capture the value of prior information given to the learner. Our proof technique is general and also apply it to linear bandits.
This work can be extended in many directions. First, our analyses only need closed-form posteriors, which are available for other reward distributions than Gaussian and Bernoulli. Second, our linear bandit analysis (Section 4.4) seems preliminary when compared to our multi-armed bandit analyses. As an example, the complexity term E (1/Af min in Theorem 6 could be bounded as in Corollary and Theorem 5, We do not do this because the main reason for deriving the O log n) bound in Theorem 5, an upper bound the corresponding O(cs log n) bound, is that it matches the lower bound in (2). No such instance-dependen lower bound exists in Bayesian linear bandits. Third, we believe that our approach can be extended to information- theorry bounds [Russo and Van Roy, 2016] and discuss it in Appendix F. Fourth, although we only analyze BayesUCB, we believe that similar guarantees can be obtained for Thompson sampling. Finally, would like to extend results to reinforcement learning, for instance by building on the work of Lu and Van Roy [2019].
There have been recent attempts in theory [Wagenmaker and Foster, 2023] to design general adaptive algorithms with finite-time instance-dependent bounds based on optimal allocations. The promise of these methods is higher statistical efficiency than exploring by optimism, which adopt in this work. One their shortcomings is that they are not guaranteed to be computationally efficient, as discussed in Section 2.2 of Wagenmaker and Foster [2023]. This work is also frequentist.
References
Yasin Abbasi-Yadkorf David Pal, and Csaba Szepesvari. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems 24, pages 2312-2320, 201
Mare Abeille and Alessandro Lazaric. Linear Thompson sampling revisited. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017.
10

---

Shipra Agrawal and Navin Goyal. Analysis of Thompson sampling for the multi- bandit problem. In Proceedings of the 25th Anmual Conference on Learning Theory, pages 39.1 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, pages 127-135, 2013.
Imad Aouali, Branislav Kveton, and Sumeet Katariya. Mixed-effect Thompson sampling. In Proceedings of the 26th International Conference on Artificial Intelligence and Statisties, 2023.
Jean-Yves Audibert and Sebastien Bubeck. Minimax policies for adversarial and stochastic bandits. In Proceedings of the 22nd Annual Conference Learning Theory, 2009.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert Schapire. Gambling in a rigged casino:
The adversarial multi-armed bandit problem. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pages 322-331, 1995.
Peter Auer, Nicolo Cesa- BisncBianchi, and Paul Fischer. Finite- time analysis of the multiarmed bandit problem. Machine Learning 47:235-2550 256, 2002.
Hamsa Bastani, David Simchi-Levi. and Ruihao Zhu. Meta dynamic pricing: Transfer learning across experiments. CoRR, abs/1902. 10918, 2019. URL https: /tap://///aiviia///a////s orgg abs /190999.... 1 10918.
Soumya Basu, Branislav Kveton, Manzil Zaheer, and Csaba Szepesvari. No regrets for learning the prior in bandits. In Advances in Neural Information Processing Systems 34, 2021.
Christopher Bishop. Pattern Recognition and Machine Learning. Springer, New York, NY, 2006.
Olivier Chapelle and Lihong Li. An empirical evaluation of Thompson sampling. In Advances in Neural Information Processing Systems 24, pages 2249-2257, 2012.
Varsha Dani, Thomas Hayes, and Sham Kakade. Stochastic linear optimization under bandit feedback.
In Proceedings of the 2t Annual Conference on Learning Theory, pages 355-366, 2008
Aurelien Garivier and Olivier Cappe. The KL--UCB algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th Annual Conference on Learning Theory, pages 359-376, 2011.
John Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society. Series B (Methozological)) 41:148-177, 1979.
Joey Hong, Branislav Kveton, Manzil Zaheer, Yinlam Chow, Amr Ahmed, and Craig Boutilier. Latent bandits revisited. In Advances Neurul Information Processing Systems 33, 2020.
Joey Hong, Branislav Kveton, Manzil Zaheer, and Mohammad Ghavamzadeh. Hierarchical Bayesian bandits. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, 2022.
Emilie Kaufmann, Olivier Cappe, and Aurelien Garivier. On Bayesian upper confidence bounds for bandit problems. In Proceedings of the 15th International Conference on Artificial Intelligence and Statistics, pages 592-600, 2012.
Jaya Kawale, Hung Bui, Branislav Kveton, Long Tran-Thanh, and Sanjay Chawla. Efficient Thomp- son sampling for online matrix-factorization recommendation. In Advances in Neural Information Processing Systems 28, pages 1297-1305, 2015.
Branislav Kveton, Mikhail Konobeev, Manzil Zaheer, Chih-War Hsu, Martin Mladenov, Craig Boutilier, and Csaba Szepesvari. Meta-Thompson sampling. In Proceedings of the 38th Interna- tional Conference on Machine Learning, 2021.
Tze Leung Lai. Adaptive treatment allocation and the multi-armed bandit problem. The Annals of Statistics, 15(3): 1091-110911114 1987.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4-22, 1985.

---

Tor Lattimore and Csaba Szepesvari. Bandit Algorithms. Cambridge University Press, 2019.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual-bandit approach to personal- ized news article recommendation. Proceedings of the 19th International Conference on World Wide Web, 2010.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. Journal of Machine Learning Research, 18(185)1-52,22 2018.
Shuai Li, Alexandros Karatzoglou, and Claudio Gentile. Collaborative filtering bandits. In Proceed- ings of the 39th Annual International ACM SIGIR Conference, 2016.
Xiuyuan Lu and Benjamin Van Roy. cntemaation-thoreeti confidence bounds for reinforcement learning. Advances in Neural Information Processing Systems 32, 2019.
Olivier Marchal and Julyan Arbel. On the sub-Gaussianity of the beta and Dirichlet distributions. Electronic Communications in Probability, 22:1-14, 2017.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 32(4):1221-1243, 2014.
Daniel Russo and Benjamin Van Roy. An information- -thooretic analysis of Thompson sampling. Journal of Machine Learning Research, 17(68):1-30 2016.
Daniel Russo, Benjamin Van Roy, Abbas Kazeroumi, Ian Osband, and Zheng Wen. tutorial on Thompson sampling. Foundations and Trends in Machine Learning, 1(1):1-96, 2018
Max Simchowitz, Christopher Tosh, Akshay Krishnamurthy, Daniel Hsu, Thodoris Lykouris, Miro Dudik, and Robert Schapire. Bayesian decision-making under misspecified priors with applications to meta-learning In Advances in Neural Information Processing Systems 34, 2021.
William R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-294, 1933.
John Tsitsiklis. A short proof of the gittins index theorem. Neural Computation, 4(1):194-199, 1994.
Andrew Wagenmaker and Dylan Foster. Instance-optimality in interactive decision making: Toward non-asymptotic theory. Proceedings of the 36th Annual Conference on Learning Theory, 2023.
Zhi Wang, Chicheng Zhang, Manish Kumar Singh, Laurel Riek, and Kamalika Chaudhuri. Mul- titask bandit learning through heterogeneous feedback aggregation. In Proceedings of the 24th International Conference on Artificial Intelliencee and Statistics, 2021.
Xiaoxue Zhao, Weinan Zhang, and Jun Wang. Interactive collaborative filtering. In Proceedings of the 22nd ACM International Conference on Information and Knowledge Management, pages 1411-1420, 2013.
12

---

A Proofs
We present general approach for deriving finite-time logarithmic Bayes regret bounds. We start with K-armed bandits and then extend it to linear bandits.
A.1 Proof of Theorem 1
Let E, Va E A: 10. - 0e.al S Cr.a
be the event that all confidence intervals at round t hold. Fix & > We start with decomposing the n-round regret as
E E.A
L 28 +
B BIA <
(5)
t=1
We bound the first term using the design BayesUCB and its closed-form posteriors.
Case 1: Event E, occurs and the gap is large, A., e. Since F, occurs and the action with the highest UCB is taken, the regret round can bounded as
A 0 OA, S OA. ULA. ULA, OA, S SU,A,, OA, 2Cr,
In the second inequality, we use that AA. U1 event Eg. This implies that event E,, action a can taken only
2 llog(1/0)
Ao 5 2Cra
2 207, 20200, log(115)
31 00 + 2222
which can be rearranged as
80 log(1/8) 0²0 2000
No.a
A
Therefore, the number of times that action is taken rounds while all confidence intervals hold, N. = Σí= 1(A, a, }, is bounded as
3 log(1/5)
No
0²00²
(6)
A
Now apply this inequality to bound the first term in (5) as
Σ 26
2c, E.) E
Σ a.
8o log(1/5)
0z00² 2o 114. 2
(7)
A
Case 2: The gap is small, As. s. Then naively Σ E EA <
< En.
Case 3: Event E, does not occur. The last term in (5) can be bounded as
E
A A,
1 { []
(8)
E
E
[OA.. ( H.]]
<
E
E
[OA. U.A.)) F H.] E [U ( H.]]
(OA. 11E.) H.] + (0r... -1A.)1(E) [E)) Ho] (E(CAA H.]
<
E
To bound the resulting terms, that O. Br.a Hr NN oP.a)-
Lemma 7. For any action E A, round E [nn), and history He,
(0. - 0r,)1 He] S K8.
13

---

Proof. Let Er,a = {10.- 1la--rach -dr,a S Sra We start with decomposing E, into individual Er, as (0a - 01,a) } Ha - E [10s Drall (aaa)
He +
IR 0a
0r f (Fr, } He
#0
To bound the first term, we use that 0a - Os He ~ NO0, aaa)) Thus
x22
E 10- 0ral1 E He S
I Texp
dr
20%
V
C=Cra
207
00
x2²
exp
dr
x=
dx
20,
20
S 0n6.
π
To bound the second term, we use the independence of the distributions for and a',
E [10. 0r, ( He]
[10. dcall He] (Er,r Ha)
The probability is at most 25 and the expectation can be bounded
10. 0cal
H1 = V(.. 02,)2
H₂ S
(0a - 0r,a) (0n-0r,a) Hl Ōzaa 500
This completes the proof.
The first two terms in (8) can be bounded using a union bound over a E .A and Lemma 7. For the last term, we use that Cr,a I 22 log(1/5) and a union bound in P (E, H.) to get
E CC,A 1 H.} & 2202 (og( H.) s 2 lo/2og
Finally, we sum up the upper bounds on (8) over all rounds [n]]
A.2 Proof of Corollary 2
The key idea in the proof is to integrate out the random gap in (7). Fix action E and thresholds E2 >> O. We consider two cases.
Case 1: Diminishing gaps E < A. S E2. Let
(97) arg max ha (8 xE(s.ca)
and N₂ be defined as Appendix A.I. Then
/
E B[A < An <62)]
A Naa d0a (0
J0_, 00=0=-0
(frie N. d0,
$ P-n 00-00-62
ha - Ea())) h d0 dd
where the inequality by the definition of Ea. Now the inner integral is independent of ha and thus can be easily bounded. Specifically, the upper bound in (6) and simple integration yield
0 0, 00--2
/
0--
80² log(1/8)
A.No d0.
o, 200 -0.) d0,
0% On
0. 00-00-- -2
02 22)
80² log(1 (og(1/5))) (log E2 loge)
20
14

---

For = 1/n and E2 = 1/v l/vlogn, we get
0i-
o²
a²
0.=00--0
NaNa a0, x log(1 ( log
20% log n
20gn²
4o21og(1/ ( log log (9)
80 80 log(1/6) log
20 log n
The last inequality holds for og 2
[l) log log Case 2: Large gaps D. > E2. Here (6) together with 62 1/Vlog get
8o log(1/0)
E I > +2) E
1 (44, > E2)
< <80² <80 (og( (10)
Aa
Finally, we chain all inequalities.
A.3 Proof of Lemma
We have that
Σ/e
ha (aa( h-((-aa) do-
REA 0_a
Σ
Σ (a((Oa)))
II o'
ha- (Dar) do
aEd 0-a
a'sa
(a( (0w)) d0,
aEA Fa Aod
(0a )0,a)²
(0.z po,a 20
exp
d0a
2To aEA Og'
20
(10,a (0,a") )2
exp
2 TO
40
a a' fá
where the last step is by completing the square and integrating out Og'
A.4 Proof of Theorem
The regret bound of UCB1 is proved similarly to Theorem 1 and Corollary 2. This is because UCB1 can be viewed as BayesUCB where do 3o and each action E is initially taken once at round t a. Since do oo, the confidence interval becomes
20 log(1/8)
Ci,a
No
The proof differs in two steps. First, the regret in the first K rounds is bounded by E. E [... Second, the concentration argument (Case Appendix A. changes because the bandit instance fixed and the estimated model parameter 0, is random. We detail below.
Case 3: Event F, does not occur. The last term in (5) can be bounded as
E A 11 [
(II)
E [(AA. 01.)1 E, []]
E (0A. U.A. 1 E.}
0] +E (UL.A - (1.) []]
E (BA. - (...)) E
0 + (0... - 01.)1 (E.) ((E))
To bound the resulting terms, that O, br, 1 NN(0, /2/N...
15

---

Lemma 8. For any action E A, round t > K, and Ni.o 21. 1,
I (0. 0c.a) 0)
20
Proof. Let Ecia {10.- - -c,all s Cra).. We start with decomposing E, into individual Er,a
E (0g 0r,0) (ee) S 00 10a-01,a [ |0]
E
0 0r,0
Eear)
a'za
To bound the first term, we use that 0₂ ora
10
NN0, 0² /Nr.).
Thus
2
x2²
E 0. 0r.01 {
rexp
dx
2TT²²
20 /NNta
20
x²2
exp
dæ
NNt.a
dx
20
/N
Cz=Cr,
20²
S 0d.
π Nia
To bound the second term, use the independence of the distributions for and a',
E 10. - &r,a 0r ( }
|0]
IE 00. 0r 0 (Ee,a' ())
The probability is at most 26 and the expectation can be bounded as
E 10. 0.al =B [Vo. 0,,a) 0 /B E [000 0r
o²
So.
N₂,
This completes the proof.
The first two terms in (11) can be bounded using a union bound over E A and Lemma 8. For the last term, we use that Cr,a S /20² log(1/6) and union bound in P E, @)) to get
E [C..A, 1 0] s 20 log(1/8)F [E, 8) s 2 2 log log (1/8)aK6.
Finally, we sum up the upper bounds on (11) over all rounds E [n].
A.5 Proof of Theorem
Let E. { Va E A: 10, - dr,l S Cra. } be the event that all confidence intervals at round hold.
Fix > 0. We decompose the n-round regret in (5) and then bound each resulting term next.
Case 1: Event E, occurs and the gap large, AA. 2 E. As in Appendix A.I.
AA. 0A. 0A. < OA. ULA + UL,, 0A, S UL,,, 0A, S 2Cr,A,
In the second inequality, we use that 1, & U,A. on event E,. This implics that on event E,, action can be taken only if
21og(1/6) (a, + 3, 1).
Nea <
A3
Now we apply this incquality to bound the first term in (5) as
12
2 log(1/8)
Σ EEA 2e, FAI SE
Σ
(ara Ba + 1)A..) 1(Aa 2 26)
A.
a.f.
Case 2: The gap small, AA, < Then naively ET E EA 1(AA, <EHl < <n.
16

---

Case 3: Event E, does not occur. Since 0g E [0, 1], the last term in (5) can be bounded as
E IA 11 [b E TP [2 H.)] s 2K8.
This completes the first part of the proof.
The second claim is proved in Appendix A.2 and we only comment on what differs. For ē 1/n and E2 = 1/ s/vlognu n, (9) becomes
0
0
log(11/)
No d0. V
1(0. - 0a) d0
0g 10-05-00
0. 0--0:-0
0% On
1(2 E²)
2
loge)
2
A
x
-log(110)) logn 2 2log n
+
log(1/5) log log n
2n²
- 2lo((1/0) log log
The last inequality holds for logg(1/))) n² log logn. n. Moreover, (10) becomes
2 log(110)
1 1,4. > {2) log((1/0) Vl
E E.A.,N > 1 < E
A.
This completes the second part of the proof.
A.6
Proof of Theorem 6
Let
E, = Va E A: (0-00000))) \2log(L/0)lall..
(12)
be an event that high- confidence intervals for mean rewards at round hold. Our proof has three parts.
Case 1: Event E, occurs and the gap large, A., 2 E. Then
1
A
A
S
(A.O
ATO)² S (ATO U.A, + UL - AT
A4
A
AC
min
min
4
Cl,A, (lg6(1/) ||Ac13,
A (UI.A - A 0)
A-
A
min
The first inequality follows from definitions of AA, and A and that the gap is large, 4 2 The second inequality holds because AT A, 0 2 0 by definition and UL ULA 2 by the design of BayesUCB. The third inequality holds because A 0 ULA. I 0 on event E, Specifically, for any action a A on event E..
aTo Ura a -0--0))
Cra S Ctaa Ot,a 0.
The last inequality follows from the definition of event Ez. Specifically, for any action A on event F,,
UL.a - TO = T TTOaa 0) + Cr,a S Ct,a + Craa =0
Case 2: The gap small, As, S s. Then naively AA. S..
Case 3: Event F, does not occur. Then A 1 (F.. A|| ( S 2I.,, [P.). where
2LL. is trivial upper bound on AA, We bound the event in expectation as follows.
Lemma 9, For any round E [n] and history Hr, we have that (Fr H.) s 2K5.
Proof. First, note that for any history H..
P (E
H.) < Σ IP.. [a (0- - (0)) 2 /2log(1 (|8))|),,,
H.
aEA

---

By definition, 0 0 H, ~ (O,, E,), and therefore a [(0 - -0)))//laals, H2 ~ NO 1) for any action a E A. It immediately follows that
P (laT 0:)1 2 2 /2log(1/8)]lals; He) = 26.
This completes the proof.
Finally, we chain all inequalities, add them over all rounds, and get
1
7
R(n)= I SIE
Σ
log(1/6) en 4L.,, Knd.
A
min
The sum can bounded using a worst-case argument below, which yields our claim. Lemma 10. The of posterior variances is bounded
T. d
mmax ?
Σ A I
log
1
log [
o2d
Proof. We start with an upper bound on the posterior variance of the mean reward estimate of any action. In any round & [n]. by Weyl's inequalities, we have
(xx) = (1 + G.) ') = X (Eo' + G.) S Ao (ET') = AIo)
Thus, when ||al|2 S L for any action E A, we have max.5. |alls, (Eo) 0 max-
Now bound the sum of posterior variances Σi=1 || Fix round and note that
A = - A. < e1 log(1 + - - A,,, = ei deg to -25, A. A,A, (13)
0²
for
maax
1 log(1 + a
20 o
This upper bound is derived follows. For any [0,
x log(1 11 + log(1 [ + x) <
u log(1 (1 + u)
max [0
log(1 +
log(1 + x).
log(1 +
Then we set 2A E, and use the definition 00,max.
The next step bounding the logarithmic term in (13), which can be rewritten as
deg + - A,A, $t2) = log det + -2 AAAA)) log det
Because of that, when we sum over all rounds, we get telescoping and the total contribution of all terms at most
log (Ta - A.A. Σ.) log del ($,41)) log dE
log det
< log
5-1 2 tr
tr
1 n
ddlog
1
tr ( A A
o2d
n
=d
1 Rdd
A En
o Tdmaxx" 1
S dllog
o2d
This completes the proof.
18

---

B Complete Statement of Corollary
Theorem 11. Let o 8 (106 n² log log Then there exist functions Ea R. Vlgn such that the n-round Bayes regret of BayesUCB in K K-armed Gaussian bandit is bounded as
o²
Σ/
R(n)= - 80 1og(1 log
ha (a(())) h-a
C,
20 log n
aEA 0-n
where = 80² log(1/6) + (2 2log(116)) 1)ooKnō + a low-order term.
Moreover, when oB 8104(1/6) log logn' the regret bounded as
2 2/olog(1/8) +1 K8 1.
R(n)
V8 /8log(1/6) log log
The first claim is proved in Appendix A.2. The second claim can be proved as follows. Take Theorem 1, set e = 0, and consider the three cases Appendix A.1.
Proof.
Case I: Event E, occurs and the gap is large, A. E. On event E,, action can be taken only if
log(1/0) Aa S V 00" a- 22 s 203 log (1/5) s 2/ 4n2 log log
n
Therefore, the corresponding n-round regret is bounded by 1.
Case 2: The gap small, A,, < E. This case cannot happen because E = 0.
Case 3: Event E, does not occur. The n-round regret is bounded by
2 2/2log(1/0)) + K8.
(2 2ogg11g(1/)) + 1)ooKnd <
v V8log(1/8) log log
This completes the proof.
C Gap-Free Regret Bound of BayesUCB in Linear Bandit
Let E, be the event in (12). Our proof has three parts.
Case 1: Event E, occurs and the gap is large, A 2 E. Then
AA, A50 0 A, ATO A U.A + ULA, A, ULA ATO S The first inequality holds because Ut, U.A. 2 0 by the design of BayesUCB. The second one uses that ATO U.A < 0. Specifically, for any action A event E,,
a To U.a T(o Q.) Ct. & Ct.a Ct,a = 0.
The last inequality follows from the definition of event E,, Specifically, for any action A on event F,,
Ur. a To = a T(O - 0) + Cr. I Cr,a + Ct,a 2Cr,a
Cases 2 and are bounded as in Appendix A.6. Now we chain all inequalities, add them over all rounds, and get
R(n) < 2E
|1A.ls..
/ 2 2log(110) en Kn8
< 2,
E
|
/2n log(1 + +nn 4LL,Kn8,
where the last inequality uses the Cauchy-Schwar inequality and the concavity of the square root. Finally, the sum Σr= ||4,1] is bounded using Lemma 10. This completes the proof.
19

---

(a) Gaussian noise
Box noise
10a
10
Regret difference
10
Regret difference
10A
10
10"
10a
10a
20
40
60
0
20
40
Instance
Instance
Figure 3: The difference in regret of UCB1 and BayesUCB on 81 Bayesian bandit instances, sorted by the difference. In plot (a), the noise is Gaussian (0, o²). In plot (b), the noise is with probability 0.5 and -a otherwise.
D Comparison of BayesUCB and UCB1
We report the difference in regret of UCB1 and BayesUCB on 81 Bayesian bandit instances. These instances are obtained by all combinations of E (5, 10, 20) actions, reward noise a {0.5, 1, 2}. prior gap Au {0.5, 1, 2), and prior width do {0.5, 2). The horizon is 1 1.000 rounds and all results are averaged over 1 0000 random runs.
Our results are reported in Figure 3. In Figure 3a, the noise is Gaussian NNO, o²). In Figure 3b, the noise a with probability 0.5 and -a otherwise. Therefore, this noise is の² -a---uu-Gaause -ub-Gaussian, of the same magnitude as (0, o but far from it in terms of the distribution. This tests the robustness of BayesUCB to Gaussian posterior updates. UCB1 only needs -ussub-Gaussian noise. both plots, and in all 81 Bayesian bandit instances, BayesUCB has a lower regret than UCB1. It is also remarkably robust to noise misspecification, although we cannot prove it.
E
Note on Information-Theory Bounds
Our approach could be used to derive Bayesian information -hoormttoon-hhory bounds [Russo and Van Roy, 2016]. The key step in these bounds, where the information theoooyttthryyyooo term It,a for action a at round arises, AA, & T TT,Ae where is the highest possible ratio of regret to information gain. As in Case in Appendix A.6, the n-round regret can be bounded
T2
Σ 1=1
Σ t=1
A2
4.A.
DA.
A
A
min
1=1
The term E I.,, be bounded using worst-case argument by O n) bound.
20


Reviews:
[{"review_id": "gAI47iaNE0", "reviewer": "Reviewer_7MLE", "summary": "The paper studies the multi-arm bandit (MAB) problem, which is an online learning problem where a learner interacts with an environment over multiple rounds. In each round the learner would make an action, and each different action will incur a reward sampled from some distribution parametrized by an unknown $\\theta$. The goal is to get highest expected cumulative reward overtime, or in other words, to minimize the cumulative \"regret\" of not choosing the best action in each round. Here \"best\" means an action incurring the highest expected reward. The paper focuses on Bayesian MAB, where the unknown parameter $\\theta$ itself is generated from some known prior.\n\nThe paper proves several improved regret bounds for various Bayesian MAB settings, including: proving finite-time logarithmic Bayesian regret bounds for a Bayesian UCB algorithm in a Gaussian bandit, deriving a finite-time logarithmic Bayesian regret bound for a frequentist UCB algorithm to demonstrate the value of the prior as side information, proving a Bayesian regret bound for a Bayesian linear bandit algorithm, and empirically comparing the tightness of the bounds to prior bounds.\n", "questions": "First, The paper under consideration falls outside my domain and I never bid for it (Regrettably I wasn't given any alternative submissions to assess). Despite my limited familiarity with MAB, the problems delineated in the manuscript, such as the Gaussian bandits, seem both intuitive and natural. The lower bound result referenced, by Lai et al., dates back several decades. Given this context, I presume these matters have been thoroughly examined within the domain. \n\nGiven this, one thing that appears perplexing to me is the paper's claim of exponential improvements over prior best results. Such a significant leap over such basic problems, usually suggests the introduction of some truly innovative ideas in the analysis. However, the proof seems quite innocuous and it's not immediately clear to me what is the core idea that leads to the improvement.\n\nIt will be very helpful if the authors can add one or two paragraphs elucidating previous results. Specifically, what is the major barrier that prevents them from achieving this logarithmic bound, and how the authors manages to overcome that barrier.\n", "limitations": "N/A", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors provide a logarithmic regret bounds for some basic Bayesian MAB problems, which improves exponentially on previous best result and matches an asymptotic lower bound. This seems to me a breakthrough.\n", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for valuable feedback and appreciating the significance of our results. For technical novelty, please see the **global rebuttal**. If you have any additional concerns, please reach out to us to discuss them.\n\nWe also wanted to add the following note. We improve over prior bounds when the complexity term, $1 / \\Delta$ in expectation, is small. This allows us to capture easy bandit instances that the prior works did not capture. When $1 / \\Delta$ in expectation is high, our bounds can be worse than $\\tilde{O}(\\sqrt{n})$ bounds. This is analogous to the relation of frequentist gap-dependent and gap-free  bounds in bandits. To get the best bound, the minimum of the two should be taken."}, {"review_id": "UJtTO9uQv3", "reviewer": "Reviewer_H2AN", "summary": "This paper derives a finite-time regret bound for BayesUCB in Bayesian bandits. In Gaussian bandits, the bound grows linearly in $c_h \\log^2(n)$, where $n$ is the time horizon, and $c_h$ is a constant determined by the prior. The bound matches that given by Lai (1987). A regret bound of BayesUCB in linear bandit is also established. Numerical experiments have also been conducted to support the theoretical findings. ", "questions": "There are some minor issues in writing. Below are a couple examples: \n1. In line 57, the paper reads “$A_t \\in \\mathcal{A}$.” However, $A_t$ is a random variable taking values in $\\mathcal{A}$, so the statement is not precise. \n2. In line 83, it reads” $C_{t,a}$ is a confidence interval.” However, $C_{t,a}$ should be half the length of the confidence interval. \n3. Typo in line 97: should remove “a” from “the posterior distribution is a Gaussian.”\n\n\n", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper studies an important problem and derives useful regret bounds. The paper is also well-organized and easy to follow. \n", "weaknesses": "In terms of presentation/ writing, I wish the paper could be more polished. Some of the examples are listed in “Questions.”\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for appreciating the usefulness of our results and their writing suggestions. $A_t$ is indeed a random variable with values in $\\mathcal{A}$. The reviewer is also right that $C_{t, a}$ is a half of the width of the confidence interval centered at the posterior mean.\n\nIf you have any additional concerns, please reach out to us to discuss them."}, {"review_id": "VYPxVVYflC", "reviewer": "Reviewer_o1t4", "summary": "The authors consider the Bayesian bandits problem and provide first finite-time logarithmic regret upper bounds by analyzing the BayesUCB algorithm from a new perspective, departing from previous studies. Their theoretical results demonstrate the significance of the prior. Additionally, the authors showcase the versatility of their analysis techniques by applying them to  linear bandits. Furthermore, they substantiate the tightness of their bounds through numerical evaluations. ", "questions": "Please see the points mentioned in the weaknesses above and provide comments on them.", "limitations": "I don't see any issue on societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The authors provide first finite-time logarithmic regret upper bounds for Bayesian bandits, which improve the existing $\\tilde{O}(\\sqrt{n})$ bounds and highlight the significance of the prior. \nThe authors provide experimental results for both Gaussian bandits and linear bandits with Gaussian rewards. \nThe experimental results substantiate the theoretical findings. \nThe results and the addressed problem hold substantial significance and are likely to capture the interest of a broad audience in Neurips. ", "weaknesses": "I have two primary concerns regarding this work and would like to request the authors to provide additional clarifications. \n\n==Weakness 1==\n\nWhile the authors present finite-time logarithmic regret upper bounds for Bayesian bandits, it is worth noting that Lai [1987] provide both asymptotic logarithmic upper and lower bounds. Therefore, it would be beneficial for the authors to explicitly highlight the key challenges associated with analyzing the finite-time case. This clarification would help readers better understand the distinctive aspects of the two settings.\n\n==Weakness 2==\n\nFrom a theoretical standpoint, the authors demonstrate the tightness of their results by comparing them with the asymptotic lower bound presented in Lai [1987]. This may raise concerns about the rigors. Additionally, it introduces a logical paradox concerning the contribution of the paper. If the theoretical analysis between the finite-time and asymptotic cases significantly differs, the comparison may not be sufficiently robust. On the other hand, if the comparison holds, it might suggest that the current results have somewhat limited contributions.\n\n==Minor Comment==\n\nRegarding the title, I suggest revising it to \"Finite-Time Logarithmic Bayes Regret Upper Bounds\" instead of the current title \"Logarithmic Bayes Regret Bounds.\" This change may be appropriate because Lai [1987] already covers both asymptotic logarithmic upper and lower bounds for Bayesian bandits.\n\nReference \n\nTze Leung Lai. Adaptive treatment allocation and the multi-armed bandit problem. The Annals of Statistics, 15(3):1091–1114, 1987.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for valuable feedback and noting the significance of our results. We address your concerns below. If you have any additional concerns, please reach out to us to discuss them.\n\n**Q1: Key challenges in analyzing the finite-time case**\n\nPlease see the **global rebuttal**.\n\n**Q2: Finite-time regret upper bounds are compared to asymptotic regret lower bounds**\n\nIn frequentist bandit analyses, it is standard to compare asymptotic lower bounds to finite-time upper bounds because finite-time logarithmic lower bounds do not exist. This is why we did not stress this particular point. Using the same reasoning, our discussion after Corollary 2 shows that the Bayes regret of BayesUCB is order optimal as $n \\to \\infty$.\n\nThat being said, our finite-time upper bounds also reveal an interesting difference from the asymptotic lower bound in [2], which deserves more future attention. Specifically, the regret bound of BayesUCB (Bayesian algorithm in Corollary 2) improves with prior information given to the algorithm while that of UCB1 (frequentist algorithm in Theorem 4) does not. We observe these improvements empirically as well (Section 6). However, both bounds are asymptotically order-optimal when compared to the lower bound in [2] (Section 4.2) because the benefit of knowing the prior vanishes in asymptotic analyses. This motivates the need for finite-time logarithmic Bayes regret lower bounds, which do not exist.\n\n**Make paper title more precise:** Agreed.\n\n**References**\n\n> [1] Russo and Van Roy. Learning to optimize via posterior sampling, 2014.\n\n> [2] Lai. Adaptive treatment allocation and the multi-armed bandit problem, 1987."}, {"review_id": "obvaCIMsyf", "reviewer": "Reviewer_MGeP", "summary": "This paper considers a Bayesian setting of the multi-armed bandit problem and provides finite-time regret bounds. For the Gaussian bandits with independent priors, the authors provide regret analyses for BayesUCB and UCB1 algorithms. Both bounds scale as $O(c_h \\log^2 n)$ and match the lower bound by Lai (1987) up to constant factors. For the Linear bandits with Gaussian rewards, the authors provide an analysis for BayesUCB and the bound scales as $ O(c_\\Delta \\text{polylog}n)$. The empirical results corroborate the tightness of the bounds.", "questions": "If possible, \n\n- Could you provide the reasoning/intuition behind why it would be difficult to have matching upper bounds with constants asymptotically together with the finite round bounds?\n- Why the factored assumption is necessary or may not be? \n- Could you make contrast your proof with the proof of Lai (1987)? What techniques/devices make it possible to bound with a finite sample?\n- Why would it be difficult to get a lower bound with the linear bandit setting?\n- Would it be possible to get Bayesian regret bound for the linear bandit setting by integrating the complexity term without finite inverse gap  assumption?\n", "limitations": "See the Weaknesses section.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper gives the first finite time bound for the Bayesian regret minimization problem with logarithmic regret for Gaussian reward and Gaussian prior setting. In the case of the multi-armed (unstructured) bandit setting, for both BayesUCB and UCB1, the order of $O(c_h \\log^2 n)$ Bayesian regret bound is given. For the linear Gaussian bandit case with bounded inverse gap, the bound does not scale with the number of arms and scales as $O(c_\\Delta \\text{polylog} n)$. ", "weaknesses": "Lai (1987) provides an upper bound that exactly matches the lower bound, including the universal constants. The authors' bound does not seem to match it asymptotically. \n\n\nThere is an assumption that the prior is factored. (Lai (1987) has weaker condition on the prior distribution (3.16) - (3.18) in Theorem 3.) I believe this assumption should be more explicitly stated/discussed in the main theorem. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for valuable feedback. We address your concerns below. If you have any additional concerns, please reach out to us to discuss them.\n\n**Q1: Not all constants in the upper bound match asymptotically**\n\nWe believe that you mean $\\sigma^2$ in the leading term of Corollary 2. If not, please respond to us and clarify. In our analysis, this term arises due to a high-probability upper bound on the number of times that a suboptimal action is taken, which naturally depends on reward variance $\\sigma^2$. In the asymptotic analysis in [2], in the first step of the proof of Theorem 3(i), the authors take a step that roughly translates to $(\\theta_i - \\theta_j) / [(\\theta_i - \\theta_j)^2 / 2 \\sigma^2] \\sim 2 (\\theta_i - \\theta_j)^{-1}$ in a Gaussian bandit. Thus $\\sigma \\sim 1$ and our upper bounds would match. We will add a discussion on this to the paper.\n\n**Q2: Is the factored prior assumption necessary?**\n\nThe factored assumption is not needed in the algorithm design. This is because BayesUCB in a Gaussian bandit (Section 3.1) can be implemented as BayesUCB in a linear bandit with Gaussian rewards (Section 3.2), where the actions are the standard Euclidean basis.\n\nTo obtain the bounds in Section 4.1, we rely on the assumption that the posterior distribution of each action depends only on that action, in Equation 5 in Section 5.1. However, since a Gaussian bandit is a special case of a linear bandit with Gaussian rewards, the logarithmic regret bound in Theorem 5 also applies.\n\n**Q3: Novelty in techniques**\n\nPlease see the **global rebuttal**.\n\n**Q4: Lower bound in the linear bandit**\n\nWe did not attempt to derive it. The main goal of this paper were finite-time logarithmic Bayes regret upper bounds.\n\n**Q5: Integrating the complexity term in Theorem 5**\n\nThis is certainly possible and an interesting direction for future work. We did not do it because the main reason for deriving Corollary 2, an upper bound on Theorem 1 that does not involve $1 / \\Delta$, is that it matches an asymptotic lower bound in [2]. No such instance-dependent lower bound exists in Bayesian linear bandits.\n\n**References**\n\n> [1] Russo and Van Roy. Learning to optimize via posterior sampling, 2014.\n\n> [2] Lai. Adaptive treatment allocation and the multi-armed bandit problem, 1987."}, {"review_id": "ShJeTmIpb8", "reviewer": "Reviewer_Q5oQ", "summary": "This paper proves logarithmic (in horizon $n$) regret bounds for Bayesian bandits using the BayesUCB algorithm. They specifically study the settings of Gaussian MABs and Gaussian linear bandits. This improves on prior works which show the more standard $\\sqrt{n}$ bounds on regret.", "questions": "\n1. Can the authors elaborate on how the techniques in the paper differ from prior works, and/or are clearer and simpler to understand? \n\n    a) From my understanding, the main parts of the analysis seem pretty similar to the standard frequentist analysis (i.e., the construction of confidence intervals and bounding the regret when the confidence interval event holds).\n\n2. The parameter $\\epsilon$ seems a bit mysterious to me. It seems like it is a parameter that is used only in the analysis. Perhaps the results could be more clearly stated in the main text by just setting $\\epsilon$ to the canonical values.\n\n3. The bounds that are obtained are not that easy to interpret.\n\n    a) Any intuition for what the $\\xi_a$ functions accomplish (e.g., in line 225)? Can one improve the range for $\\xi_a$ to be $\\Theta(1/\\mathrm{poly}(n))$? A slightly unsatisfying aspect of the claim when one takes $n\\to \\infty$ is that $1/\\sqrt{\\log n}$ goes to zero very slowly.\n\n    b) What is the intuition for the $\\sum_a \\int_{\\theta_{-a}}$ term? It seems like this comes from prior analysis. Why does it capture the dependence on the prior?\n\n    c) The linear gaussian bandit bound can be used to recover (a version) of the gaussian MAB bound. Can you discuss this? Is this tight in the relevant problem parameters? If not, why?\n\n4. line 147-148: the claim about the setting where $\\sigma_0 \\to \\infty$ is not clear to me why the complexity term should approach zero. Can this be formalized?\n\n5. Can the ideas be extended beyond Gaussian settings, and/or can they handle some degree of model misspecification (e.g., what happens if the rewards are close to gaussian in some distance metric).\n\n6. Experiments:\n    \n     a) Did you tune the confidence widths for the BayesUCB and UCB1 algorithm?\n     b) Can confidence bands be plotted?\n     c) I think the most interesting part is the comparison between BayesUCB and UCB1. Your theory suggests that BayesUCB improves over UCB1 because it takes into account the prior. Can this be demonstrated more robustly, i.e. for a range of experimental parameters. Also, we would expect this to happen in well-specified settings where the rewards are actually Gaussian. It would be interesting to see if this phenomena is robust and holds for real-world datasets (otherwise, in some sense, it might not be interesting to study BayesUCB...)\n    d) Why are your plotted bounds not monotone in $\\sigma_0 and \\Delta_0$? (Taking a step back, is this something that one should expect?)\n    e) In some regimes, your bounds for the linear setting are worse than the established $\\sqrt{n}$ bounds. Why is this so? Does this point to some looseness in the analysis?\n\n7) At a high level, why is BayesUCB interesting to study, and how does it compare to other Bayesian approaches, e.g., Thompson sampling? Which should one choose to use in practice?\n", "limitations": "None.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Generally the writing is good. Problem setup and results are clear, as well as points of comparison with classical asymptotic guarantees.\n- The proofs are simple and easy to understand.\n- Numerical simulations are run to back up the validity of the theory.", "weaknesses": "- On the technical side, I'm not sure where the contributions are. The abstract states that \"our proofs mark a technical departure from prior works\". Can this be made more explicit in the technical discussion?\n- Several questions about the experiments, see next section. Generally the scope of the experiments is rather limited (which may be fine since this is primarily a theoretical work). \n\nSome comments on writing:\n- line 65: \"any bounded $\\theta$\": since we have not specified a specific parametric model here (it is not even clear that $\\theta$ must lie in some Euclidean space) a description of $\\theta$ being bounded seems premature here.\n- as a matter of writing style, it is a bit strange to put part of the inequality inline and the other half in display equations (such as line 120).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for valuable feedback and detailed questions. We address your concerns below. If you have any additional concerns, please reach out to us to discuss them.\n\n**Q1: Novelty in techniques**\n\nPlease see the **global rebuttal**.\n\n**Q2: Parameter $\\varepsilon$**\n\nThis is an upper bound on the regret of actions bounded trivially in the bounds, by $\\varepsilon n$. We suggest $\\varepsilon = 1 / n$, and say it right after Theorems 1 and 5.\n\n**Q3: Bounds are hard to interpret**\n\n**a) Role of $\\xi_a$**\n\nThe terms $\\xi_a$ arise due to the intermediate value theorem for function $h_a$ when the gaps are in $[1 / n, 1 / \\sqrt{\\log n}]$. Similar terms appear in the analysis of [2] but vanish in the final asymptotic bound. The rate $1 / \\sqrt{\\log n}$ cannot be changed to $1 / \\text{poly}{\\log n}$ without increasing dependence on $n$ in other parts of the bound.\n\n**b) How does the complexity term of [2] capture prior dependence?**\n\nThe term is indeed not easy to interpret in general. Roughly speaking, it captures the difference between prior means. In a Gaussian bandit with $K = 2$ actions, it has a closed form\n\n$$2 \\sqrt{\\frac{2}{\\pi \\sigma_0^2}} \\exp[- (\\mu_{0, 1} - \\mu_{0, 2})^2 / 4 \\sigma_0^2]$$\n\nProposition 3 gives a general upper bound for $K > 2$ actions.\n\n**c) Does the linear bandit bound recover the Gaussian bandit bound?**\n\nThe bound is $O(K^2 \\mathbb{E}[1 / \\Delta_{\\min}] \\log^2 n)$ in a $K$-armed bandit and thus not tight. This is similar to the frequentist gap-dependent bound of\n\n> Abbasi-Yadkori, Pal, and Szepesvari. Improved algorithms for linear stochastic bandits, 2011.\n\nnot being tight in a multi-armed bandit. The reason is that the bound is proved for large action spaces.\n\n**Q4: Complexity term goes to zero as $\\sigma_0 \\to \\infty$**\n\nEach term in the complexity term is a product of factors $\\sqrt{c_1 / \\sigma_0^2}$ and $\\exp[-c_2 / \\sigma_0^2]$ for some constants $c_1, c_2 > 0$. As $\\sigma_0 \\to \\infty$, the former factor goes to $0$ while the latter goes to $1$. As a result, the complexity term goes to zero.\n\n**Q5: Extension beyond Gaussians**\n\nOur work can be extended to Bernoulli bandits with factored beta priors (second paragraph in Section 7) as follows. Let $\\mathrm{Beta}(\\alpha_a, \\beta_a)$ be the prior distribution of the mean reward of action $a$ and $N_{t, a, +}$ be the number of positive observations of action $a$ up to round $t$. Then the posterior mean and confidence interval width in Section 3.1 are\n\n$$\\hat{\\theta}\\_{t, a} = \\frac{\\alpha_a + N_{t, a, +}}{\\alpha_a + \\beta_a + N_{t, a}}$$\n\nand\n\n$$C_{t, a} = \\sqrt{\\frac{\\log(1 / \\delta)}{2 (\\alpha_a + \\beta_a + N_{t, a} + 1)}}$$\n\nIn Corollary 2, the constant at the leading complexity term of action $a$ changes to\n\n$$2 \\log(1 / \\delta) \\log n - (\\alpha_a + \\beta_a + 1) / (2 \\log n)$$\n\nand the bound would have the same interpretation as before. In fact, all theory in Sections 4.1 and 4.2 can be extended similarly.\n\nTheoretically-sound handling of model misspecification in Bayesian algorithms and analyses is generally difficult. We report empirical results for model misspecification in Q6.\n\n**Q6: Experiments**\n\n**a) Are confidence widths tuned?**\n\nNo. Implemented as analyzed.\n\n**b) Can you plot confidence bands?**\n\nWe believe that you mean standard errors in BayesUCB and UCB1 plots in Figure 1. Note that they are plotted. They are just very narrow due to a high number of runs ($1000$).\n\n**c) More extensive comparison of BayesUCB and UCB1**\n\nSee Figure 1 in the attached pdf to the **global rebuttal**. We report the difference in regret of UCB1 and BayesUCB on $81$ Bayesian bandit instances, obtained by all combinations of\n\n* Number of actions $K \\in \\\\{5, 10, 20\\\\}$\n* Reward noise $\\sigma \\in \\\\{0.5, 1, 2\\\\}$\n* Prior gap $\\Delta_0 \\in \\\\{0.5, 1, 2\\\\}$\n* Prior width $\\sigma_0 \\in \\\\{0.5, 1, 2\\\\}$\n\nIn Figure 1a, the noise is Gaussian $\\mathcal{N}(0, \\sigma^2)$. In Figure 1b, the noise is $\\sigma$ with probability $0.5$ and $- \\sigma$ otherwise. This noise is $\\sigma^2$-sub-Gaussian, the same magnitude as $\\mathcal{N}(0, \\sigma^2)$ but far from it in terms of the distribution. This tests the robustness of BayesUCB to assuming Gaussian noise in the posterior updates. UCB1 only requires $\\sigma^2$-sub-Gaussian noise. All results are averaged over $1000$ runs.\n\nOut of $162 = 2 \\cdot 81$ tested instances, UCB1 improves upon BayesUCB only once. In this case, the difference in regret is almost zero and likely due to the randomness of only $1000$ runs. BayesUCB is remarkably robust to noise misspecification, although this is hard to prove.\n\n**d) Are Bayes regret bounds monotone?**\n\nNot necessarily. As an example, the upper bound on the complexity term in Proposition 3 goes to zero when either $\\sigma_0 \\to 0$ or $\\sigma_0 \\to \\infty$. We discuss this right after Proposition 3.\n\n**e) Our bounds can be worse than prior bounds**\n\nWe improve over prior bounds when the complexity term, $1 / \\Delta$ in expectation, is small. This allows us to capture easy bandit instances that the prior works did not capture. When $1 / \\Delta$ in expectation is high, our bounds can be worse than $\\tilde{O}(\\sqrt{n})$ bounds. This is analogous to the relation of frequentist gap-dependent and gap-free  bounds in bandits. To get the best bound, the minimum of the two should be taken.\n\n**Q7: Why is BayesUCB interesting to study?**\n\nBayesUCB is empirically competitive with Thompson sampling. This was reported, for instance, in Figures 1, 2, and 4 in\n\n> Kveton, Meshi, Zoghi, and Qin. On the value of prior in online learning to rank, 2022.\n\nIt is easier to analyze though because it acts according to an upper confidence bound. Since the submission of this work, we extended the arguments in Section 4.1 to Thompson sampling.\n\n**References**\n\n> [1] Russo and Van Roy. Learning to optimize via posterior sampling, 2014.\n\n> [2] Lai. Adaptive treatment allocation and the multi-armed bandit problem, 1987."}]

Author rebuttal:
We would like to thank all reviewers for feedback, and appreciating the novelty of our work and its potential impact. One comment that appeared in most reviews is that the technical novelty of the work was never clearly presented in one place. We summarize it below and address all other comments in your respective rebuttals.

**Technical novelty**

All modern Bayesian analyses follow the work of [1], which derived the first finite-time $\tilde{O}(\sqrt{n})$ Bayes regret bounds for BayesUCB and Thompson sampling. The key idea in these analyses is that conditioned on the history, the optimal and taken actions are identically distributed, and that upper confidence bounds are deterministic functions of the history. This is the main step where the randomness of instances in Bayesian bandits is used. Based on this, the regret in round $t$ is bounded by the confidence interval width of the taken action, and the usual $\tilde{O}(\sqrt{n})$ bounds can be obtained by summing up the confidence interval widths over $n$ rounds.

In our work, we first bound the regret in a fixed bandit instance, similarly to existing frequentist analyses. The bound involves $1 / \Delta$ and is derived using biased Bayesian confidence intervals. The rest of our analysis is Bayesian in two parts: we (1) prove that the confidence intervals fail with a low probability and (2) bound random $1 / \Delta$, following a similar technique to [2]. The resulting logarithmic Bayes regret bounds cannot be derived using the techniques in [1], as these become loose when the confidence interval widths are introduced.

Asymptotic logarithmic Bayes regret bounds were derived in [2]. From this analysis, we only reuse the technique for bounding $1 / \Delta$ in expectation, when proving Corollary 2 to Theorem 1. The central part of our proof is a finite-time per-instance bound on the number of times that a suboptimal action is taken. A comparable argument in [2], in their Theorem 2, is an asymptotic bound on average over the bandit instances. To show the generality of our technique, we also apply it to a structured linear bandit problem.

**References**

> [1] Russo and Van Roy. Learning to optimize via posterior sampling, 2014.

> [2] Lai. Adaptive treatment allocation and the multi-armed bandit problem, 1987.

Meta-review: Gap dependent bounds for bandits have been known for decades. This paper shows that a Bayesian algorithm with slightly biased estimates can enjoy finite time gap dependent bounds like those first proved for UCB. The reviewers all like the paper and the contribution is meaningful and novel. But, at the same time, the contribution isn't ground breaking and is not likely to lead to any new practical recommendations for users of bandit algorithms.
Decision: Accept (poster)