Optimal Regret Is Achievable with Bounded Approximate Inference Error: An Enhanced Bayesian Upper Confidence Bound Framework
Authors: Ziyi Huang
Henry Lam
Amirhossein Meisami
Haofeng Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: Bayesian bandits
approximate Bayesian inference
Bayesian Upper Confidence Bound
optimal regret order
bounded inference error

Abstract: Bayesian bandit algorithms with approximate Bayesian inference have been widely used in real-world applications. However, there is a large discrepancy between the superior practical performance of these approaches and their theoretical justification. Previous research only indicates a negative theoretical result: Thompson sampling could have a worst-case linear regret $\Omega(T)$ with a constant threshold on the inference error measured by one $\alpha$-divergence. To bridge this gap, we propose an Enhanced Bayesian Upper Confidence Bound (EBUCB) framework that can efficiently accommodate bandit problems in the presence of approximate inference. Our theoretical analysis demonstrates that for Bernoulli multi-armed bandits, EBUCB can achieve the optimal regret order $O(\log T)$ if the inference error measured by two different $\alpha$-divergences is less than a constant, regardless of how large this constant is. To our best knowledge, our study provides the first theoretical regret bound that is better than $o(T)$ in the setting of constant approximate inference error. Furthermore, in concordance with the negative results in previous studies, we show that only one bounded $\alpha$-divergence is insufficient to guarantee a sub-linear regret.

Optimal Regret Is Achievable with Bounded Approximate Inference Error: An Enhanced Bayesian Upper Confidence Bound Framework
1 Ziyi Huang, 'Henry Lam, 2 Amirhossein Meisami, 'Haofeng Zhang Columbia University, New York, NY, USA
Adobe Inc., San Jose, CA, USA
zh2354, kh12114, 2211444222223335mmmmm edu, meisami @adobe.coom 022300
Abstract
Bayesian bandit algorithms with approximate Bayesian inference have been widely used in real-world applications. However, there is a large discrepancy between the superior practical performance of these approaches and their theoretical justifi- cation. Previous research only indicates negative theoretical result: Thompson sampling could have a worst-case linear regret I?(T) with a constant threshold the inference error measured by one a-divergence. To bridge this gap, we propose an Enhanced Bayesian Upper Confidence Bound (EBUCB) framework that can efficiently accommodate bandit problems in the presence of approximate inference. Our theoretical analysis demonstrates that for Bernoulli multi-armor bandits, EBUCB achieve the optimal regret order O(log T') if the inference error measured by two different a-divergences! is less than a constant, regardless how large this constant is. To our best knowledge, our study provides the first theo- retical regret bound that is better than o(T) in the setting of constant approximate inference error. Furthermore, in concordance with the negative results in previous studies, we show that only one bounded a-divergence is insufficient to guarantee a sub-linear regret.
Introduction
The stochastic bandit problem, dated back to [77. is important sequential decision-making problem that aims to find optimal adaptive strategies to maximize cumulative reward. At each time step, the learning agent chooses action among all possible actions and observes its corresponding reward (but not others), and thus requires a balance between exploration and exploitation. Previous theoretical studies mainly focus on exact Bayesian bandit problems, requiring access to exact posterior distributions. However, their work cannot be easily applied to complex models such as deep neural networks, where maintaining exact posterior distributions tends to be intractable (36). In contrast, approximate Bayesian bandit methods are widely employed in real-world applications with state-
of-the-art performances [36 33 45
50 comparison with exact algorithms, approximate
Bayesian bandit algorithms are more challenging to analyze, as the inaccessibility of exact posterior sampling adds another level of discrepancy, and the resulting theory and solutions hence also differ substantially.
Few theoretical studies have been developed around Bayesian bandit approaches with approximate inference, despite their superior practical performance. (28) gave a theoretical analysis of an ap- proximate sampling method called Ensemble Sampling, which possessed constant Kullback-Leibler divergence (KL divergence) error from the exact posterior and thus indicated a linear regret. [34]
Authors are listed alphabetically.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

showed that with a constant threshold on the inference error in terms of a-divergence (a generaliza- tion of KL divergence), regardless of how small the threshold is, Thompson sampling with general approximate inference could have a linear regret in the worst case. Their work also showed that Thompson sampling combined with a small amount of forced exploration could achieve o(T) regret upper bound, but no better result than oT)) was shown. Moreover, this improvement was mostly credited to the forced exploration rather than the intrinsic property of Thompson sampling. It appears that [34] illustrated a paradox that approximate Bayesian bandit methods worked well empirically but failed theoretically. Thus, further study regarding the fundamental understanding of approximate Bayesian bandit methods is necessary.
Motivated by the negative results in 34 (MCMC) Langevin algorithm in multi -armed Thompson sampling so that the inference error would vanish along with increased sample numbers. 48 extended (30 to the contextual bandit problems and integrated contextual Thompson sampling with the Langevin algorithm that allowed the approximate posterior distribution to be sufficiently close to the exact posterior distribution. Hence, both works 48 30
30 leveraged an efficient Markov chain Monte Carlo
had similar feature in terms of vanishing inference error. However, in other inference approaches, such as variational inference [8]. the approximate posteriors might incur a systematic computational bias. To accommodate the latter scenario, we consider general Bayesian inference approach that allows bounded inference error:
Is it possible to achieve the optimal regret order Ollog T) with a constant (non-vanishing) threshold on the inference error?
This question is not well investigated in previous literature, even for Bernoulli bandits. 34 showed that the answer is No for Thompson sampling when the inference error measured by only one a- divergence is bounded. In this study, we will provide a novel theoretical framework and point out that the answer could be Yes when the inference error measured by two different a-divergences is bounded where one a is greater than 1, and the other a is less than O. This assumption guarantees that the approximate posterior is close to the exact posterior from two different "directions". Our finding implies that the problem of sub-optimal regret in the presence of approximate inference may not arise from the constant but from the design of the inference error. Our study takes the first step in deriving positive answers in the presence of constant approximate inference error, which provides some theoretical support for the superior performance of approximate Bayesian bandit methods.
In this study, we extend the work of the Bayesian Upper Confidence Bound (BUCB) 21 20 42 17
to the setting of approximate inference and propose enhanced Bayesian bandit algorithm that can efficiently accommodate approximate inference, termed as Enhanced Bayesian Upper Confidence Bound (EBUCB). In particular, we redesign the quantile choice in the algorithm to address the challenge of approximate inference: The original choice of 1 provides the best regret bound without approximate inference, but in the presence of approximate inference, it leads to an undesirable quantile shift which degrades the performance. By adjusting the quantile choice, we theoretically demonstrate that EBUCB can achieve the optimal regret order Olog T') if the inference error measured by two different a-divergences (a) > 1 and 022 < 0) is bounded. We also provide insights in the other direction: Instead of two different a-divergences, controlling one a-divergence alone is not sufficient to guarantee sub-linear regret for both Thompson sampling, BUCB, and EBUCB. This further suggests that naive approximate inference methods that only minimize one a-divergence alone could perform poorly, and thus it is critical to design approaches with two different a-divergences reduced.
Our main contributions are summarized as follows:
1) We propose a general Bayesian bandit framework, named EBUCB, to address the challenge of approximate inference. Our theoretical study shows that for Bernoulli bandits, EBUCB can achieve a (log T') regret upper bound when the inference eπror measured by two different a-divergences bounded. To the best of our knowledge, with constant approximate inference error, there is no existing result showing a regret upper bound that is better than o(T), even for Bernoulli bandits.
2) We develop a novel sensitivity analysis of quantile shift with respect to inference error. This provides a fundamental tool to analyze Bayesian quantiles in the presence of approximate inference, which holds promise for broader applications, e.g., when the inference error is time-dependent.
3) We demonstrate that one bounded c--iiverencee alone is insufficient to guarantee sub-linear regret. Worst-case examples are constructed and illustrated where Thompson sampling/BUCB/EE
has ?(T)) regret if only one a-divergence is bounded. Hence, special consideration reducing two different a-divergences is necessary for real-world applications.
2

---

4) Our experimental evaluations corroborate our theory well, showing that our EBUCB is consistently superior to BUCB and Thompson sampling on multiple approximate inference settings.
Related Work, Bandit problems and their theoretical optimality have been extensively studied over decades 27 [0]. The seminal paper [55 (and subsequently [T]] established the first problem-
dependent frequentist regret lower bound, showing that without any prior knowledge on the distri- butions, regret of order (log is unavoidable. Two popular lines of Bayesian bandit algorithms, Thompson sampling T [2, [6] and BUCB [21 20], had been shown to match the lower bound, which indicated the theoretical optimality of those algorithms. Beyond Gaussian processes 42] and
linear models [ [3], exact computation of the posterior distribution is generally intractable, and thus, the approximate Bayesian inference techniques are necessary.
Some recent work focused on designing specialized methods to construct Bayesian indices since previous studies had demonstrated that Thompson sampling with constant inference error could exhibit linear regret in the worst-case scenario 28
S0 constructed Langevin algorithms to generate approximate samples with decreasing inference error and showed an optimal problem- dependent frequentist regret. [32] proposed variational Bayesian optimistic sampling, suggesting solving convex optimization problem over the simplex every time step. Unlike these researches, our study presents general results that only depend on the error threshold of approximate inference, rather than some specific approximate inference approaches.
34
Beyond Bayesian, another mainstream of bandit algorithms to address the exploration cetprtttioncxpliitatiiinno tradeoff is upper confidence bound (UCB)-typ frequentist algorithms 5
1 15 51
24 29 43
12 revealed that Thompson sampling empirically outperformed UCB algorithms in practice, partly because UCB was typically conservative, its configuration was data-independent which led to over-exploration [18]. BUCB [21] could be viewed as middle ground between Thompson sampling and UCB. On the other hand, empirical studies [20] showed that Thompson sampling and BUCB performed similarly well in general.
2 Methodology
The stochastic multi-armed bandit problem consists of set of K actions (arms), each with stochastic scalar reward following a probability distribution vi (i = 1,... K). At each time step = 1,... T, where T is the time horizon, the agent chooses an action A, [K] and in return observes an independent reward X, drawn from the associated probability distribution VA." The goal is to devise strategy A (At) to maximize the accumulated rewards through the observations from historical interactions.
In general, wise strategy should be sequential, in the sense that the upcoming actions are determined
and adjusted by the past observations: letting F; = o (A1, ... Ar, .x,) be the o-field generated by the observations up to time f, A, is or (F U measuuabbee, where Ug is a uniform random variable independent from Fr-1 (as algorithms may be randomized). More precisely, let μı (j [K] denote the mean reward of the action j (i.e., the mean of the distribution vt), and without loss of generality, we assume that μ4 = max (1j. Then maximizing the rewards is equivalent to minimizing the
(frequentist) regret, which is defined as the expected difference between the reward accumulated by an "ideal" strategy (a strategy that always playing the best action), and the reward accumulated by a strategy A:
R(T A) E Tp1
Σ
X
Σ (1 (A.)
(1)
The expectation is taken with respect to both the randomness in the sequence of successive rewards from each action denoted by (Y,,s)seN, and the possible randomization of the algorithm, (U)) Let (t) = Σ 1A,, = j) denote the number of draws from action j up to time f, so that X, = NA,,NA, (1)- Moreover, let As = Ei= Yj.x be the empirical mean of the first rewards from action j and let (t) be the empirical mean of action j after rounds of the bandit algorithm. Therefore (t) = 0 if (t) 0. (t) (,,N,(t) otherwise.
Note that the true mean rewards μ (wI, ux) are fixed and unknown to the agent. In order to perform Thompson sampling, or more generally, Bayesian approaches, we artificially define prior distribution Il, μ. Let II, be the exact posterior distribution of μ Fc-1 with density function me
3

---

Algorithm Enhanced Bayesian Upper Confidence Bound (EBUCB) with Approximate Inference
Input: T (time horizon), Πo Qo (initial prior 14), (parameters of the quantile), and real-value increasing sequence {rr J such that 7/2 + as + 00 for t = 1 to T do
for each action j = 1, 1.... K do Compute quz(1) Qu(Ti, Qt-1,)).
end for
Draw action A, arg max quy()
j=I...,K
Get reward X, AA.NA.(0)) Obtain the approximate distribution Q
end for
with marginal distributions "r,1;-.. Tt,K for actions 1...., K. Specifically, if at time step t, the agent chooses action A₁ = j and consequently observes X; =Y,,NA, (t), the Bayesian update for action j is
Tt.j x vol (x.)))+e-.,;(0))
(2)
whereas for of j. = At each time step t. we assume that the exact posterior computation in (2) cannot be obtained explicitly and approximate inference method is able to give an approximate distribution Qe (instead of I1)). We use q: to denote the density function of Q..
First, we consider standard case where the exact posterior is accessible. In Thompson sampling D sample in is drawn from the posterior distribution II,-1 and then an action A, is selected using the following strategy: A, = i if m; = max, my. In BUCB (2I), we compute the quantile of the posterior distribution (t)(t) Qu(1 E(log Ty IT- ) for each action j. where Qu(7, () is
the quantile function associated the distribution p. such that Pa(X S Qu(?, - 7. Then
select action A, as follows: A, = if (t)(t) max, (t).
concrete example, Bernoulli multi-armed bandit problems with a standard setting used in seminal papers [ 21 22 In these problems, each (stochastic) reward follows Bernoulli distribution V; Bernoulli (1;) and these distributions are independent of each other. The prior To, is typically chosen to be the independent and identically distributed (i.i.d.) Beta(1, 1), or the uniform distribution for every action j. Then the posterior distribution for action is Beta distribution II Beta(1 (t), 1 (1) - (t)),, where Sy) Σ 1 (A, = j]XX, is the empirical cumulative reward from action up to time L. Then, Thompson sampling/BUCB chooses the samples/quantiles of the posterior II, Beta (t), 1 (t) - (t) respectively at each time step.
Next, we move to
In the presence of approximate inference, Thompson sampling draws the sample m from Q--1, as the exact IT,- is not accessible. Correspondingly, we modify the specific sequence of quantiles chosen by the BUCB algorithm with general sequence of {7) )ryanntutleess and term it Enhanced Bayesian Upper Confidence Bound (EBUCB) algorithm. The detailed pseudo algorithm of EBUCB described in Algorithm [ Note that the choice of 7he should address the presence of inference error and should be trailed to the specific definition of inference error; See Remark 3.10 in Section
3 Theoretical Analysis
In this section, we present a theoretical analysis of EBUCB. In Section 3.1 we provide the necessary background of a-divergence on approximate inference error measurement. Then in Section 3..2] we develop a novel sensitivity analysis of quantile shift with respect to inference error. This provides fundamental tool to analyze Bayesian quantiles in the presence of approximate inference. The general results therein will be used for our derivation for the regret upper bound of EBUCB in Section 3.3 and are also potentially useful for broad applications, e.g., when the inference error is time-dependent. Lastly, in Section 3.4, we provide examples where Thompson sampling/BUCH/EBUCC has linear regret with arbitrarily small inference error measured by one a-divergence alone. All proofs are given in the Appendix.

---

3.1 The Alpha Divergence for Inference Error Measurement
The a-divergence, generalizing the KL divergence, is common way to measure errors in inference methods.
Definition 3.1. The a-divergence between two distributions Pi and P2 with density functions pi (œ) and p2(2) is defined as: (P P2) a(a-1j (S (z))"")((() -a - 1), where R and the case of a and is defined as the limit.
Note that different studies use the a parameter in different ways. Herein, our definition of a- divergence does not follow Renyi's definition of a-divergence [5); Instead, we follow a generalized version of Tsallis's a-divergence, which is adopted by [52 31 34]. Compared with Renyi's a- divergence, Tsallis's a-divergennc does not involve log function, and has the following property:
Proposition 3.2 (Positivity and symmetry). For any R. (a P2) N 0 and Da P2)
(P,,
The a-divergence contains many distances such as KT((22, Pi)(a - 0). KI(P,, P2) + 1). Hellinger distance (a = 0.5), and x² divergence (a 2). a-divergence is widely used in [6]. which is one of the most popular approaches in Bayesian ap- proximate inference. Moreover, it was also adopted in previous studies on Thompson sampling 28 In particular, the KL divergence ((a ))-divergence) is: 334
variational inference 8
23
with approximate inference
LL P2) = (z) log
Px(x) dr. In approximate Bayesian inference, the exact posterior dis- Pz(z)
tribution TT, and the approximate distribution Qe may differ from each other. To provide a statistical analysis of approximate sampling methods, we use the a-divergence as the measurement of inference error (statistical distance) between 11, and Qt. Our starting point is the following:
Assumption 3.3. Suppose that there exists positive value (0, +-00 and two different parameters on > and 02 < 0 such that
Da. (Qss 14.) S e, Vt E [T]. E [K], Day 10ggI1e). S e, Vt E [T] E [K].
(3)
This assumption is adapted from (34 but we enhance theirs with two bounded a-divergences, as 34 showed one bounded a-divergence was not sufficient to guarantee the sublinear regret. However, in the following, show that the optimal regret order Olog T) is indeed achievable under Assumption with two bounded a-divergences. Intuitively, P2 is flatten to cover Pi 's entire support when minimizing D. (P1, P2) with large a (greater than 1), while when a is small (less than 0), Pa fits the Pi's dominant mode; See (31) for the implication of a-divergence. Therefore, Assumption 3.3 guarantees that the approximate posterior is close to the exact posterior from two different directions". It is worth mentioning that when one a-divergence is small, it does not necessarily imply that any other a-divergences are large or infinite. fact, as long as the two distributions have densities with the same support, then any a-divergence between them is finite. Note that Assumption 3.1 does not require the threshold to be small; instead, can be any finite positive number. We pinpoint that this assumption, as well as our subsequent results, are very general in the sense that does not depend on any specific methods of approximate inference. To enhance credibility on Assumption 3.3 we make several additional remarks in Section A
3.3
3.2 Quantile Shift with Inference Error
In this section, develop novel sensitivity analysis of quantile shift with respect inference error, which implies that under Assumption 3.3 the y-quantiles of Ih and Q., only differs from a bound depending on e. We provide a general result first, which is rigorously stated as follows:
Theorem 3.4. Consider any two distributions P1 and P2 with densities (z()) and P2(2). Ler R
denote the quantile function of the distribution i.e. i.e., (p) Qu(p, P.) (i 1, 2). Let 7
Let dn, satisfy that Ri(r) = R2(1 + dy,c) where -T & 8n S
a) If (P), < where > then
8 S 1 - 7 (Ea((a + 1) (1 - --
Note that when > 1, (ea(a- 1) + 1)r-a < 1 and (1 7) 7
5

---

b) Da e where a < 0, then
dy 2 - - (ea(aa - 1) 1) + 1)r (1- (1-))=
Note that when a < 0, (eaaaa-11 - 1) > 1 and (1 7) >
c) Suppose that E (0,1) and 2 ala-T). Then for any dy E [-7,1 - 7.. there exist two
-1
1
distributions Pi and P2 such that (PI, Pa) S e. This implies that the condition (P P2) S cannot control the quantile shift between P1 and P2 in general when E (0,
Theorem 3.4 states that 7-quantile of the distribution Pi is the ( dy (esenniunttle of the distribution
Pe where the quantile shift d, has the following properties. a) The upper bound of 6y.e is close to 0 if Da (P, P2) with a is bounded: b) The lower bound of 6y.e is close to 0 if (P,, P2) with < 0 is bounded; c) A slightly large bound on D D (PI.P2) with 0 < a < 1 cannot control the shift 6y in general, which gives the intuition that a E (0, 1) is not implemented in Assumption 3.3
This theorem is distribution-fee free, in the sense that the bound of 6y, does not depend on any specific distributions (noting that distribution changes as t evolves in bandit problems). In particular, a)+b)
in Theorem 3.4 shows that Ce.o (1 7) -- -1-1 2 6q, (1 7) 2 -Ce.a (1 - -2-1, with
0n > and 02 < O where Cr,a = (Eae(a 1) + 1)-- independent of y or distributions, and thus independent of the time step in our EBUCB algorithm. This observation is important in the T.eorem3.44relicn 3.4 on the following lemma, which provides quantile-based representation of a-divergence.
robustness of using quantiles in the EBUCB. The proof of Theorem
Lemma 3.5. Under the same conditions in Theorem 3.4 we have that for any a-divergence, (a,P,, ( R2 (Ri(a))) du-1
a(a-1)
3.3 Finite-Time Regret Bound for EBUCB
In this section, we derive finite-time upper bound of problem-dependent frequentist regret for our EBUCB algorithm in Bernoulli numti-armed bandit problems. Without loss of generality, we assume action 1 is optimal in the subsequent theorems.
To begin with, we first express the frequentist regret as R(T,A) = E Ei (#1 - [A.] =
sufficient to study each term E [N) in order to bound the regret R(T,A) For (p, q) E [0, 1J2, we denote the Bernoulli KL divergence between two points by d(p, 9) plog(E) & + (1 - p) log ( with 0 Olog 0 = 0 01og (0/0) = 0 and x log(z/0) +o0 for x 0 by convention. We also denote that dt (p, q) d(p, (0p.gggl( {p < q} for convenience. (t)) so its (closed) support is [o, 1].
Σ5=1 - MT) (N) by ① Therefore,
Note that ,r. (x) is the density of B (O, We put a basic assumption on the approximate distribution Qt,- Assumption 3.6. Qr, has the density (z) whose support is [0, 1] for any E [T].j E [K].
+
The following is our main theorem, which establishes finite-time regret bound for our EBUCB algorithm.
Theorem 3.7. Suppose Assumptions 3.3 and 3.6 hold. Let Me,1 = (Ea1 -) 1) 1) < 1,
ύ an-1 > O. Ma (ear((a22 1) 1) uu L, and āz -5 > 0. For any { >
choosing the parameter such that cā2
in the EBUCB algorithm and setting i 1 (lng T)e (S > 0), the number of draws of any sub- sub-optimal action j 2 2 is upper-bounder by
(5áz + cōrz M 2e
ETN,
+ o
(á2
if0 < (ā2 < 1, and
E[N, (1 + () log(T)) + o(log
d(uj, M1)
f 2 1.

---

Theorem 3.7 provides an exact finite-time regret bound and the o(-) term in Theorem 3.7 has an exact finite-time closed-form expression that holds for any time horizon T; See Step 4 in the proof of Theorem 3.7 in Appendix C We only show the most dominant term of the regret bound and shrink the rest to the o(-) term to improve the readability of the main paper. Note that this bound has explicit dependence on 6, which M and Ma, in Step 4 in the proof of Theorem 3.7 Obviously, the error terms I and M2 in the bound increase as increases. However, this dependence on e does not impact the dominating term too much. The exact posterior will be more "concentrated" on the true mean with small variability as the time t increases, and the impact from the error will vanish; See Remark 3.9
It is easy to see that to minimize the regret upper bound, we may choose (= - in Theorem 3.7
Corollary 3.8. Under the same conditions in Theorem 3.7 for any { {> 0, choosing the parameter
such that co2 2 5 in the EBUCB algorithm and setling Tt (1og the number of draws
(1+5) S1
of any sub-optimal action j 2 2 upper-bounded by E[N, S a(ay.m))
Iog(T)+
+ o(log T).
This result states that with the c error threshold, the regret of the EBUCB algorithm is bounded above by (log T regardless of how large c is, which reaches the same order (log T) of the problem- dependent frequentist regret lower bound [25]. In comparison with the exact lower bound, there is slight difference in the multiplier before the order (log T)): Our upper bound in Corollary 3.8 has
the additional multiplier & 1, which arises from the approximate inference when estimating the d2
posterior distributions (Assumption 3.3). If in addition Assumption 3.3 holds for any a₁ > 1 and
any ag < 0, then we can let ä1 + by taking a + +00 and 02 00 to match the exact lower bound.
02
((y) log(T) + olog T) matching the exact lower bound. Prior to our work, was unclear in the literature whether the optimal regret order O(log T) could be achieved in the presence of bounded approximate inference error. Our result provides a positive answer to this question, despite the fact that the inference error may cause the multiplier & before the order (log T). To the best of our knowledge, this is the first algorithm providing the regret upper bound that is better than oT)) in 34 with bounded approximate inference error.
In the absence of approximate inference, 21 showed that (T)) I
(1+E)
22
As discussed in (21), the horizon- -eiiedded term (log T in Corollary [.8 only an artifact of the theoretical analysis to obtain a finite-time regret upper bound. In practice, the model with choice == (i.e., without the horizon-dependen term) already achieves superior performance. This is confirmed by our experiments in Section 4 A similar observation in BUCB was indicated in (21).
Remark 3.9. It might appear little surprising that the result in Corollary 3.8 indicates regret upper bound with the dominating term Olog T) that does not depend on e, as one may expect that a large e allows the "full swap" between the posterior of the optimal action and the posterior of suboptimal action, making any Bayesian-based approaches unable to distinguish them. However, benefiting from historical observations, the exact posterior will be more "concentrated"" on the true mean with small variability, which will keep enlarging the a-divergence between two actions. This indicates that, for a fixed c, the a-divergence between the exact posteriors of two actions can be sufficiently large as t increases and ultimately exceeds e. Hence, the "full swap" will not happen when / is large.
Remark 3.10. The قι,ق in EBUCB, instead of the original in BUCB, is a delicate choice to address the tradeoff between making the regret optimal without approximate inference and the presence of inference error. On a technical level, a power Ç cclose to 1 in t improves the regret bound without the presence of approximate inference but simultaneously leads to high-level quantile shift caused by approximate inference. Choosing Ç
is subtle balance of these two.
The technical derivation of Theorem 3.7 depends on analyzing the quantiles of the approximate distributions used in the EBUCB algorithm. In particular, one of the major techniques in our analysis Lemma[C.]] Appendix C It provides explicit upper and lower bounds on the tails of approximate distributions to control the quantiles designed by the EBUCB algorithm. It is obtained by combining the quantile shift between the approximate and exact posterior distributions that developed in Theorem 3.4 (Section 3.2) with the tight bounds on the quantiles of the exact posterior distributions (the proof of Lemma in (1.). This result is then used to bound the expectation of decomposition of N2(T)
in Lemma C.2 that links N2 (T) to the over-estimation of the optimal arm.
7

---

3,4 Negative Results
We show that one bounded a-divergence alone cannot guarantee sub-linear regret. We provide two worst-case examples, one where Thompson sampling has a linear regret, and the other where BUCB/EBUCB has linear regret, even when the inference error measured by one a-divergence small. A similar study on Thompson sampling was conducted in [34] with special focus on the inference error on the joint distribution of all actions. our study, nevertheless, we focus on setting where the inference error on the distribution of each action is assumed: See Remark[A.3 Therefore, the examples in [34] cannot be directly applied in our setting. Moreover, our second example shows that BUCB/EBUCB could have linear regret if only one a-divergence is considered, which is new
Assumption 3.11. Suppose that there exists a positive value E (0, +oo) such that
Da(Qu, TT,)) <, AI [7]. [K].
(4)
We establish the following theorem for Thompson sampling:
Theorem 3.12. Consider a Bernoulli multi-armen bandit problem where the number of actions is K = 2 and μn > 122. The prior Lo. is chosen to be the i...d Beta(1, 1), or the uniform distribution for every action j 1,2. For any given <, and any error threshold >> there exists a sequence of distributions Qt-1 such that for all 1:
1) The probability of sampling from Qt11 choosing action greater than a positive constant
independent of t.
2) Qt-1 satisfies Assumptions and 3.17
Therefore Thompson sumpling from the approximate distribution Q.-1 will cause finite-time linear frequentist regret: R(T, A)) = (
This theorem shows that making one a-divergence small constant alone, even for each action j. is not sufficient to guarantee a sub-linear regret of Thompson sampling. Note that Theorem is an enhancement of the results in 34 in the sense that the Q, constructed by theorem satisfies more restrictive assumptions. We can derive similar observation for the BUCB/EBUCB algorithm as follows:
Theorem 3.13. Consider Bernoulli multi-armed bandit problem where the number of actions is K = and μ1 > (22. The prior To, is chosen to be the i..dd Beta(1, 1), or the uniform distribution for every action j = 1.2. Consider the general EBUCB algorithm described in Algorithm | For any given a < 1 and any error threshold > O, there exists constant To (only depending on e, o, and the sequence {(te3) and a sequence of distributions Q--1 such that for all 2
1) The EBUCB algorithm always chooses action 2 when I 2 To-
2) Q--1 satisfies Assumptions (.6]and3.11.
Therefore the EBUCB algorithm from the approximate distribution Q--1 will cause finite-time linear frequentist regret: R(T, A) [2(T).
This theorem shows that making one a-divergence a small constant alone, even for each action j. is insufficient to guarantee a sub-linear regret of BUCB/EBUCB. We emphasize that the examples in Theorems 3.12 and 3.13 are in the worst-case sense, indicating that there exist worst-case examples where Thompson Lumplig/EBBUCB exhibits a linear regret if only one a-divergence is bounded. However, this does not imply that EBUCB and Thompson sampling would fail average in the presence of approximate inference. In fact, Theorem 3.7 shows that a sub-linear regret can be achieved if the inference error measured by two different a-divergences is bounded.
4 Experiments
In this section, we conduct numerical experiments to show the correctness of our theory In Section 4.1 we compare the performance of EBUCB with the following baselines: BUCB (using its originally proposed quantile and Q, II, since the exact posterior distribution I1, is unavailable) and Thompson sampling (using Q as II,). In Section 4.2, we construct worst-case examples showing that both EBUCB and Thompson sampling can degenerate linear regret if only one a-divergence is bounded. We consider the Bernoulli multi-armed bandit problem which has two actions with mean rewards
TThe source code for experiments is available at htthtps:: http:////ggttabb.ooo////////////
8

---

(P1) with w=0.9
(P1) with w=0.8
(P1) with w=0.7
Time Dimp
(P2) with w=0.9
(P2) with w=0.8
(P2) with w=0.7
EBUCB (c 0)
Thompson Sampling
BUCB (c 0)
BUCB (c
EBUCB 5)
Figure 1: Comparison of EBUCB and baselines with generally misspecified posteriors under different problem settings. Results are averaged over 10 runs with shaded standard errors.
Thompson Sampling
0)
EBUCB (c = 0)
1.000
120
100
380
302
500
Smpp
Then
Figure 2: Results of Thompson sampling, BUCB, and EBUCB with worst-case misspecified posteriors under different problem settings, Results are averaged over 10 runs with shaded standard errors.
[0.7, 0.3], and use Beta(1, 1) the prior distribution of mean reward for each action. At each time step t, the exact posterior distribution for each action Beta(1 + S,(t), 1 + (t) (()))))())))))))))))))()))(()))) where (y(t) is the empirical cumulative reward from action j up to time and (t) is the number of draws from action j up to time
4.1 Generally Misspecified Posteriors
Suppose the posterior distributions are misspecified to the following distributions:
(PL): (1 - w) Beta(1 + S,(), 50 5,(0) w Beta( 1 1+5)() 1 N2 - (5;(),;
2
2
(P2): :1 w) Beta + (t),, (c) ()) (eta + S,(1), (1) - S,()))
where w = 0.9, 0.8. 0.7. Figure presents the results of EBUCB and the baselines. Overall, EBUCB achieves consistently superior performance than the baselines, and it outperforms BUCB with considerable improvements. These results confirm the effectiveness of EBUCB across multiple settings. Moreover, EBUCB performs well without the horizon-dependent term (i.e., c in Corollary 3.8 This brings EBUCB practical advantages in real-world applications, as it does not require advanced knowledge of the horizon (i.e., anytime). similar observation of BUCB was also noticed in (21]

---

4.2 Worst-Case Misspecified Posteriors
We consider the worst-case examples, Equations (3 and (14), presented in the proof of Theorems 3.12 and 3.13 where the posterior distributions are misspecified using one a-divergence. The results of Thompson sampling, BUCB, and EBUCB are displayed in Figure 2 From these worst-case examples, observe that: 1) Thompson sampling exhibits linear regret after 1. As shown in Theorem 3.12 the linear coefficient (i.c., the slope) of the regret depends on the level r that corresponds to the inference error. Specifically, the slope of the regret is increased along with the increased value of 7, as illustrated in both Figure 2 and the proof of Theorem 12 2) BUCB/EBU UCB exhibits linear regret with constant slope μr jlz after 2 Tu. where To is the time threshold introduced in Theorem 3.13 after which BUCB/EBUCB always chooses the sub-optimal action, The artificial choice of is to make To 100, 200, 333 where Yr, f. See the proof of Theorem 3.13
In summary, our experiments evidently demonstrate the superior performance of our proposed EBUCB on multi-armed bandit problems with generally misspecified posteriors. Our results also align closely with our theory that making one a-divergence a small constant alone is insufficient to Hence, making two different
guarantee sub-linear regret of Thompson Bunpling/BUBB/BBUR a-divergences bounded is necessary for the sub-linear regret upper bound.
5 Conclusions and Future Work
In this paper, we propose general Bayesian bandit algorithm, Enhanced Bayesian Upper Confidence Bound (EBUCB), that achieves superior performance for Bernoulli bandit problems with approximate inference. We prove that, if the inference error measured by two different a-divergences is less than constant, EBUCB can achieve the optimal regret order Olog T). Additionally, we construct worse-case examples to show the necessity of bounding two different a-divergences, which is further validated by our experiments. We consider the study of other problem settings as meaningful future research that could be built upon our current framework, e.g., extending to the general exponential family bandit problems by leveraging the techniques in [20]. We will also extend our current framework to contextual bandit problems and investigate the performance of contextual Bayesian bandit algorithms with approximate inference [36].
Acknowledgments and Disclosure of Funding
This work has been supported in part by the National Science Foundation under grants CAREER CMMI-18347I0 and IIS- 1849280, and the Cheung- Koogg Innovation Doctoral Fellowship. The authors thank the anonymous reviewers for their constructive comments which have helped greatly improve the quality of our paper.
References
[1] S. Agrawal and N. Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on Learning Theory, pages 39-1, 2012.
[2] S. Agrawal and N. Goyal. Further optimal regret bounds for thompson sampling. In Artificial Intelligence and Statistics, pages 09-117,, 2013.
[3] S. Agrawal and N. Goyal. Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning, pages 127-135, 2013.
[4] C. Andrieu, N. De Freitas, A. Doucet, and M. I. Jordan. An introduction to meme for machine learning. Machine Learning, 50(1):5-43, 2003.
[5] Auer. Using confidence bounds for exploitation-exxlorrtion trade-offs. Journal of Machine Learning Research, 3(Nov):397-42. 2002.
[6] Auer, Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2):235-256, 2002.
10

---

[7] P. Auer, N. problem. SIAM Journal on Computing, 32(1))48-77, 2002.
Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit
[8] D. M. Blei, A. Kucukelbir, and D. McAuliffe. Variational inference: A review for statisticians. Journal of the American Statistical Association, 112(518):859-87) 2017.
[9] R. Brekelmans, V. Masrani, F. Wood, G. Ver Steeg, and A. Galstyan. All in the exponential family: Bregman duality in thermodynamic variational inference. In International Conference on Machine Learning, pages 1111-1122. PMLR, 2020.
[10] S. Bubeck and N. Cesa- Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. arXiv preprint arXi::/204.5721, 2012.
[11] A. N. Burnetas and M. N. Katchakis. Optimal adaptive policies for sequential allocation problems. Advances in Applied Mathematics, 17(2):122-144 142, 1996.
[12] O. Chapelle and L. Li. An empirical evaluation of thompson sampling. Advances in Neural Information Processing Systems, 24:2249-222 2011.
[13] V. Dani, T. P. Hayes, and S. M. Kakade. Stochastic linear optimization under bandit feedback. 21st Annual Conference on Learning Theory, 2008.
[14] K. Daudel et al. Mixture weights optimisation for alpha-divergence variational inference. Advances in Neural Information Processing Systems, 34:4397-440S 2021.
[15] A. Garivier and O. Cappé. The kl-ucb algorithm for bounded stochastic bandits and beyond, In Proceedings of the 24th Annual Conference on Learning Theory, pages 359-376. JMLR Workshop and Conference Proceedings, 2011.
[16] A. Gopalan, S. Mamnor, and Y. Mansour. Thompson sampling for complex online problems. In International Conference on Machine Learning, pages 100-108. PMLR, 2014.
[17] D. Guo, S. I. Ktena, K. Myana, F. Huszar, W. Shi, A. Tejani, M. Kneier, and S. Das. Deep bayesian bandits: Exploring in online personalized recommendations. In Fourteenth ACM Conference on Recommender Systems, pages 456-461, 2020.
[18] B. Hao, Y. Abbasi Yadkori, Z. Wen, and G. Cheng. Bootstrapping upper confidence bound. Advances in Neural Information Processing Systems, 32: 32:12123-12133, 2019.
[19] Hernandez-Lobato, Y. Li, M. Rowland, T. Bui, D. Hermández-Lobato, and R. Turner. Black- box alpha divergence minimization. In International Conference on Machine Learning, pages 1511-, PMLR, 2016.
[20] E. Kaufmann. On bayesian index policies for sequential resource allocation. The Annals of Statistics, 46(2):842-863 2018.
[21] E. Kaufmann, O. Cappé, and Garivier. On bayesian upper confidence bounds for bandit problems. In Artificial Intelligence and Statistics, pages 992-600. PMLR, 2012.
[22] E. Kaufmann, N. Korda, and R. Munos. Thompson sampling: An asympiotically optimal finite- time analysis. In International Conference on Algorithmic Learning Theory, pages 199-213. Springer, 2012.
[23] D. P. Kingma and M. Welling, Auto-encoding variational bayes. arXiv preprint arXiv: 131..6114. 2013.
[24] N. Korda, B. Szorenyi, and S. Li. Distributed clustering of linear bandits in peer to peer networks. International Conference on Machine Learning, pages 1301-1309, PMLR, 2016.
[25] T. L.. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4-22, 1985.
[26] Y. Li and R. F. Turner. Rényi divergence variational inference. Advances in Neural Information Processing Systems, 29, 2016.

---

[27] Y. Li, Y. Wang, and Y. Zhou. Nearly minimax minimax-optimal regret for linearly parameterized bandits. In Conference on Learning Theory, pages 2173-2174. PMLR, 2019.
[28] X. Lu and B. Van Roy. Ensemble sampling. Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 3260-3268, 2017.
[29] K. Mahadik, Q Wu, S. Li, and A. Sabne. Fast distributed bandits for online recommendation systems. In Proceedings of the 34th ACM International Conference on Supercomputing, pages 1-13, 2020.
[30] E. Mazumdar, A. Pacchiano, Y. Ma, M. Jordan, and P. Bartlett. On approximate thompson sampling with langevin algorithms. In International Conference on Machine Learning, pages 6797-6807. PMLR, 2020.
[31] T. Minka et al. Divergence measures and message passing. Technical report, Citeseer, 2005.
[32] B. O'Donoghue and T. Lattimore. Variational bayesian optimistic sampling. Advances in Neural Information Processing Systems, 34, 2021.
[33] I. Osband, C. Blundell, A. Pritzel, and B. Van Roy. Deep exploration via bootstrapped dqn. Advances in Neural Information Processing Systems, 29:4026-4034 2016.
[34] M. Phan, Y. Abbasi- and J. Domke. Thompson sampling with approximate inference. arXiv preprint arXiv: 04990, 2019.
[35] A. Rényi. On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume Contributions the Theory of Statistics, volume 4. pages 547-562. University of California Press, 1961.
[36] C. Riquelme, G. Tucker, and J. Snoek. Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling. In International Conference on Learning Representations, 2018.
[37] H. Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5)-527-535, 1952.
[38] Ruiz and Titsias. contrastive divergence for combining variational inference and meme.
In International Conference on Machine Learning, pages 5537-5545. PMLR, 2019.
[39] D. Russo and B. Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 1221-:12211,24, 2014.
[40] Y. Seldin, C. Szepesvári, P. Auer, and Y. Abbasi-Yadkori. Evaluation and analysis of the performance of the exp3 algorithm in stochastic environments. In European Workshop Reinforcement Learning, pages 103-116. PMLR, 2013.
[41] J. Snoek, O. Rippel, K. Swersky, R. Kiros, N. Satish, N. Sundaram, M. Patwary, M. Prabhat, and R. Adams. Scalable bayesian optimization using deep neural networks. In International Conference on Machine Learning, pages 2171-2180. PMLR, 2015.
[42] N. Srinivas, A. Krause, S. M. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3999, 2009.
[43] B. Szorenyi, Busa-Fekete. Hegedus, Ormándi, M. Jelasity, and Kégl. Gossip- distributed stochastic bandit algorithms. In International Conference on Machine Learning. pages 19-27. PMLR, 2013.
[44] W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285 2944, 1933.
[45] I. Urteaga and C. Wiggins. Variational inference for the multi-armed contextual bandit. In International Conference on Artificial Intelligence and Statistics, pages 698-706. PMLR, 2018
[46] N. Wan, Li, and N. Hovakimyan. f-divergence variational inference. Advances in Neural Information Processing Systems, 13:17770-17379, 2020.
12

---

[47] D. Wang, H. Liu, and Q. Liu. Variational inference with tail-adaptive f-divergence. Advances in Neural Information Processing Systems, 31, 2018.
[48] Xu, Zheng, E. V. Mazumdar, K. Azizzadenesheli, and A. Anandkumar. Langevin monte carlo for contextual bandits. In International Conference on Machine Learning, pages 24830- 24850. PMLR, 2022.
[49] Y. Yang, D. Pati, and A. Bhattacharya. a-variational inference with statistical guarantees. The Annals of Statistics, 48(2):886 905, 2020.
[50] W. Zhang, D. Zhou, L. Li, and Gu. Neural thompson sampling. In International Conference on Learning Representations, 2021.
[51] D. Zhou, L. Li, and Q. Gu. Neural contextual bandits with ucb-based exploration. In Interna- tional Conference on Machine Learning, pages 11492-11500 PMI.R, 2020.
[52] H. Zhu and R. Rohwer. Information geometric measurements generalisation. Technical Report. Aston University, Birmingham, UK, 1995.
13

---

Appendices
We provide further results and discussions in this appendix. Section A presents detailed discussions
on Assumption 3.3 Section B presents proofs for the results in Section 3.2 in the main paper. Section
presents proots for the results in Section
3.3
Section D presents proots for the results in Section
3 Section presents additional experimental results.
Appendix A Remarks on Assumption 3.3
Remark A.1 (Constant Threshold). A constant threshold assumption inference error appears in [34. In this study, we adopt a similar assumption as [34), since no standard assumptions are in place due to the infancy of this field. In practice, keeping inference error below constant threshold is not only feasible but also can be improved. As a concrete example, [30] showed that the inference
error of an efficient Langevin MCMC algorithm decreases at the order of O D(1/vN,1 (t)) 48 also
establish similar consistency results. On a high level, more data are collected, the approximate and exact posteriors both become more concentrated, but they could concentrate to the same point of true mean rewards, as [30] showed. In addition to MCMC algorithms 44) which typically produce consistent posterior, our assumption also fits other Bayesian inference algorithms, such as variational inference [8). that output approximate posteriors with systematic computational bias.
In fact, the negative results in the presence of constant inference error shown by B motivate another research direction: A natural idea for obtaining positive results is to construct "hiihly-effective" Bayesian inference approach with vanishing inference error as the number of samples increases, as studied in 30 48
However, our results demonstrate that the Ollog regret upper bound is achievable even with non-vanishing inference error, without requiring specific "highly-effective" Bayesian inference approaches.
Remark A.2 (a-divergence). Studies beyond KL divergence
38
using a-divergence 26 19
14 49 or more generally f-divergence [46] 47), have appeared in recent research. These studies demonstrated the potential use of general a-divergence and other types of divergence in practical model design. Moreover, from a practical perspective, the two a-divergences between the estimated and the exact posterior distributions could be small, even if only one a-divergence is used to construct the approximate distribution. This might be the reason for the superior performance of approximate Bayesian bandit algorithms that consider only the KL divergence in practice.
Remark A.3 (Independent Prior). In multi-armed bandit problems, the prior distribution of mean rewards Ho is typically chosen to be independent among each action lo. ...., Io,, K. as this is the most reasonable and natural way without further information [T 21 20 30]. this case, the posteriors must also be independent among each action because of the Bayesian update (2). Therefore, our
study focuses on the inference error on the distribution of each action in (3). which appears to be more realistic than the inference error on the joint distribution of all actions assumed in [34].
Appendix B Proofs of Results in Section 3.2
Proof of Theorem 3.4 Note that R1(7) = R2(7 + 6,.c) implies (R) = = 5y and Obviously R (R,
and ( = 1. On a high level, our proof technique is to split the (P,,,, P3) into two parts using the quantile-based representation of a-divergence in Lemma 3.5 and then use Jensen's 's inequality (since a(a- is a convex function
R1 (R2(7+ +x,.)) ))
of x > 0 for any * 0. I) derive bound for 6,,e.
14

---

By Lemma 3.5
and Jensen's 's inequality,
Da Da P2)
1
d
R2 (Ra(W)))
1-a
du 1
ala 111-1)_ 0
du
a(a-1)
a(a - 1) [-) ((4,
{ R22 (B((())) (
1-a
du+
1
1 log
to (R)
d
1-a
du
du
a(a -1) -1) y
du
ala - 1)
1 ('
d R₂ (R1 (2)
1-a
1-
( 1 ("² d Rτ (R1 (1)
1-a
1
(RI(u))dcu)
a(a -1
du
a(a - 1) 7
1 11-7
7 J, du
a(a o(a-1) 1)
Ry (R((3)) RRz (
BB (R( 2 (Ri
?
+ a(a - 1)
a(a - 1)
1-7
a(a - 1)
On.e (
1-a
1 1-7
11 8g.ee
1-a
(5)
ala- 1)
7
alaa - 1)
a(a - 1)
First, we note that for any y E (0,1) and any dy,e E 1-7,1- - 7), achievable. To see this, consider
the above inequality is indeed
7+ p1 (I))
if R1(7) if > R1(7)
p2(x) =
(6)
--g- pı (21)
Simple calculations give
f p2(x)= 7 7 82,0
7 8y.0
7 Hy,e
1 1-7 67
F (R(((T)))+
(1 (R))((
7 - 7
(1 (1-7)
=
1 1-9
7
where Fi is the edf of Pl, and
(o,
1
P2(2))
1-a pi(t)de-1)
a(a - 1)
Pi (x))
1
7' dyne
1-a (T(R((7)) +
7 Szse
1-a (1- (R. (R)()))) -1)
a(a- - 1)
7
?
Y + Eyge
1-7
(1- Oyyee
1-a
a(aa 1) Therefore, the P1 and P2 constructed in Equation
7
alaa -1]
y
a(a 1)
6 show that the inequality (5) is indeed achievable.
Next, we consider the function
9(5) a(a ala-1) (2+0) 1-a
1 1-y
( (1 (1-9-5)
1-a
1
(1
7
ala 1)
ae 1)
Taking the derivative of g(ö) with respect to 6, we obtain
0'(0) = - 1
( 7
7 (7+0)
1
1 (1-7-0)
a
1 1-9
08)8) = 7 +
-a-1
1-7-0 0
1
-a-1
> 0.
1-- 1-7
is easy to see that g( is strictly decreasing when E (-7, 0) and strictly increasing when 8 E (0, (-)) with minimum g(0) 0. This fact shows that e 2 g()) is equivalent to 8 in interval around 0, i.e., 8 E [ 8) [-7,, 1 - 7). More explicitly, we can obtain explicit bound for g, 8. In the following, we will show that in some cases, the bound for becomes too loose in the sense that å can be close to - or 8 can be close to - 7, in which cases we cannot obtain any useful information.
15

---

1) Suppose that a > 1. When dG, > 0, we have
γ
7 8y.ee
1-a
? ( 2 (
1-a
g0
2
0( - 1)
?
a(a - 1)
0(10 - 1)
as dy,e S 7, Therefore = (a, P2) implies that
1-7
1- Ogge
Set a(a-1)
a(a 1)
which is equivalent to
1 1-9 7- 8yse --xc
(Eala (ca(a-1) (1o(a=1)+1))=
z
1 -
1 1-7
Hence have
dyp S 1 7 1)
1) (1 -
Note that when a > 1, the lower bound of oy.e can be similarly derived but it becomes vicious. To see this, we notice that whenever
Remark.
(ea(a -0 1) + 7) 1 g -2 S dyg < <0,
(7)
we have that
11) (1
7
11-7 (1-7-897) 8y.e)
1-a
a(a a(a- - 1) S 1 7-7
-7 a(a - 1)
1 1-7-
ala 1) a(a a(a-1) 1)
as
7 --55 6, and
7 7 11+0e
1-a
7
Y+ (ea(a- 1) 7) gott p 1-a
= =+ ala 1)
-(a-1)
7
a(a= 1)
?
which ensures e 2 (a(P,, Pa). However, the lower bound in Equation is too loose:
lim (ea((a - 1) + 7) r ク ++00
which can be sufficiently close to - if is sufficiently large.
b) Suppose that a < O. When dy < 0, we have
7 1 1-a
1-a [--7 ?
7
7
0
a(a 1)
ala - 1) 2 Da(P))PP)) implies that
as 7 8y O. Therefore
1-?
1- (1-7--pp0
(1-9-- -dy,e)
set 1 a(a-1)
a(a-1)
which is equivalent to
1 7 - S
( /eala 1) (ca(a-1)+1
1-7
1-7
Hence we have
89.6 2 1-11--- -
1) (1-7)
(8)
Remark. Note that when a O, the upper bound of dy.e can be similarly derived but it becomes vicious. To see this, we notice that whenever
S 6,, < min((ea(a - 1) + 7) 1- y -7,1 1-1
we have that
1-7
1 11-7 8y
1-a
-7 ala - ala 1) a(a- ( ala - 1)
1
S 1-7
1
a(a - 1)
1 7-
16

---

as 7 S dne < 0 and
1-a
( (y+dye Sy.e)
7
y+ +calaa - 1) 7) yo yot -
S a(a 1)
=t a(a - 1)
a(a 1011
7
which ensures
2 Da(P1, P2). However, the lower bound in Equation
is too loose:
lim (ea(a 1) + 7) 7) u 7 +00
so the lower bound in Equation p can be 1 - is large.
c) Note that when a E (0, a(aa 1) < O and thus we have
?
( ( 8g.e
1-a
(7-7)
1-a
a(a - 1)
7
ala
- 1)
and
1-y
(1 (1- 11-2- 1
Ogis
1 1-7
(1 11-7- 1---(11-))
00
a(aa 1)
a/a - 1)
as -y S 8n.e= $
Hence, as long as é 2 a(a-1) we always have
7 a(xxx - 1)
( (z+dge
1-a 1 1-7
1 11 dyge
al - 1) Se
10
for any Sy,e E || 1-,1--1.. 7|. Moreover, as we discussed below Equation there exist two distributions P1 and P3 such that
( for any on E 1l-7:11 1-,11-11 7]
7 Da(P,,P)) a(a 1 1)
(
1-a 1-7 (2t0rx)
a(a-1) (
1 (1 (1-7-80x Eyse
1-a
1-7
a(a - 1)
which shows that (P, P2) 6 holds for such P1 and P2. This implies that the condition (o(P,, I cannot control the quantile shift between P1 and P/ in general when E (0, 1). O
Proof of Lemma 3.5 Let F1 and F3 be the edfs of P1 and P2 respectively. Since Fi and F2 are
absolute continuous and strictly increasing (as they have positive densities), we have that F2 (R, (u)) for 1. Taking the derivative with respect both sides of (u), u, we obtain
(R(())))..()))) =
(10)
where (u)
dR.(w) da
Note that we have the following equality:
dRg (v)
R (Bi(u)) = (u)
du
du
(=)
R' (v)) (v=R(()
(v))
= -R((u) R2 (2 (e))))
by Equation 10
= (R((2) (u)).
(11)
17

---

Using integration by substitution, for a-divergence, we obtain that
(a, = a(a 11) (/
(m()) do -1)
(1(())
(((2)do-1)
a(a- - 1)
P2(x)
Pr (1 a-1
(()((
a(a - 1)
(2))
9-1 (()
-1
a(a - 1)
(o. (u)p2 Ri (M) (R))))) 1- du (1
by Equation 10
a(a 1)
(Jo'
R₂ (R(
du - 1) by Equation 11
a(a-1) a(a - 1)
du
Similarly, for KL divergence, we obtain that
P1 (R (((((()))R((()) (2))
KL Pa) = log
f. log
(1)p222 (R) (u) (u)du
J log (U) du by Equation (TO)
(u)))
L'¹ log ( d Rr (R(()) du by Equation
du
Appendix C Proofs of Results in Section 3.3
first prove two useful lemmas.
Lemma C.1. Under the same condition in Theorem 3.7 the quantiles of the approximate distributions quy(t) (t) chosen by the EBUCB algorithm satisfies the following bound:
(1(() S qu (1) - (1)
where
{d
St((t) (t)
Çân log(t) + că2 log(log T) - log(Me,1)
(t) arg max
<
(4)
(t)
Sy(t) (t(
Çā2 log(t) + că2 log(log 7) log(Me.2) (o)((N(()))))))))))))))))))))))) +2)
(t(() arg max
d
2,(t)
N2 +1
Proof of Lemma
Recall that Mr,1 = (ean (a1 - 1) + +1) < 1, = 2 0. Mc =
(Eag (ag 1) 1) 1-
ā2 --- 0. First notice that by Theorem 3.4 part (where P
18

---

corresponds to Qt.5 we have
qu,(t) = Qu(1
(6log T)e" Qo-15)
Qu(1
+ 6 Bsloo 2ye 11g)1.)
15 T)e
Qu((
+
Me,1 Kân (log T)a 1.5)
(loog Tye
ts
(log TYe
Me,1
=u((1 (5u (log Ty 115-
(11--1 1) and we have use the fact that Qu is non-decreasing. Now apply the proof of Lemma in [21], the tight bounds of the quantiles of the Beta distributions, to obtain
since Da, (Q.
Me,1 Qu(1 Ko (log T) 11-
log
(d
St)()
(cdn (log 276
Sarg max
(t(()) -2))
(t)
x> Ny())
aar max {d
[t)() (1(1)* x
Çāi log(t) + cāj log(log T)
log log(Mc.1)
(1(1)
#> (,())
My(0
(1)
Similarly, by Theorem 3.4 part b) (where P1 corresponds to Qt,5-2), we have that
(t) Qu(1
((oog T Q2-1,))
Qu(1
+ 81 isuox 2y0 .e 1k-1,))
(<(log TTe
1
Qu(1
Me, fzāz (log T) 11.),j)
t (logg Ty:
t T)o
M
Qu(1
(50z (log T)caz" 11.
since Da, (I Qt.j-)) S and we have use the fact that Qu is non-decreasing. Now we apply the proof of Lemma I in (21) the tight bounds of the quantiles of the Beta distributions, to obtain
Me,2 Qu(1 (502 (log T)
log
S,(1)
M,.2 (1o2 ry
(N₃())+2)
d
2 arg max
(t) + 11.0)
(t +1
2,00 Ny00-1
{d
St(()
Çāz log(t) + căæ log(log T) -olooogMM. (M,)) log (N) 2)
2 arg max 3,(0) Netn
(t(() +1 x
(t) +1
(1)
Therefore, we conclude that
(t(t) < (t) s (t).
19

---

Based on Lemma C.1 we can obtain UCB-type decomposition of the number of draws of any sub-optimal action j 2 2 as follows.
Lemma C.2. Under the same condition in Theorem 3.7
we have that for any constant Br,
N2(T) S Σ 1im
(12)
Σ 3 (A; = 2)}.
Proof of Lemma C.2
We have that, by definition,
(T) Σ 1fA, = 2]
T
T - Br -
1((/1 - -
Σ
sa())) =2)
==1
T
T
1(p1 - -3 > [((t))
Σ
11(m1 3r (t)) 2)}
T 1 + Σ
Σ
1( Br - Tz 0 (A, 2)}
t=1
1=1
where the last inequality follows from the fact that (t) 2 u (t) and when A, 2. (1(() S (t()) (2()).
Therefore, to obtain Theorem 3.7
it sufficient to analyze the two terms Lemma
Proof of Theorem 3.7 Without loss of generality, we let j = 2. (Note that we have assumed the we only need to bound the two following two terms:
action 1 optimal.) By Lemma C.2
T
D =
Σ (mn Br> > u (O),
D2 = Σ 1(m Br < a2(1)) (A, = 2))
Let Bx V log
We further split D2 into two parts:
D1,1
Σ
1(11 Br > (1),N(1)) +2 (log T)
t=1
D12 = Σ 1111 Br (t), + 2 (log ))
[=1
Step 1: Consider D1.1.
Note that Çā log(t) + cāæ log(log (log T) log(Me.2) Nt()) +
Çāz log(t) + (cāz - 2) log(log T) - log (M..2)
(t) +
in 24 (1) when (1 + 2 < (log 2 Hence have that
My (1) Z arg max {dl
(t)
Çã2 log(!) + (cā2 2) log(log log(Me.)) } = = 1= -. (1)
(1) + 1
N1 (t) +1
x>
when N₂ + 2 < (log (logT)². 2 This shows that
D1,1
Σ
Hp > (0)
1=1
20

---

Similarly to the proof in [21], with a straightforward adaptation of the proof of theorem 10 in [3 we obtain the following self-normalized inequality
Lemma C.3.
P(u ū, (8) - (6log(t) exp((( 1) ő = (āz log(!) + (cā²² 2) log(log 7) - log( (,
where
Lemma
C.3
leads to the following upper bound of D1,1:
T
1
<
P( > (t))
1=1
(gáylog()) + (că² 2) log T) log(Me,)) log(t) + +1) taa (log T)
Ma2e
< 1 +
l=2
M2
1++ + Σ
(ā2 cō2 2 -2+1)
zzoz (log T)oo244
11+ (5ā2 + cā.
Ma
T
dx
(log T'
25ā2
1=2 1-11
s1+ + (ā2 cā2)
Me
1
dx
(log 7") cā -4 T'ccá
T 25ā2
Şāstcäs
Mazer1 ca2
< 1 + (āz + cā2
M
T1-(02-1
< 11
if < Çā2 1
(log T'agg-
1-50z
1-Coz
1 + (ā² + 0d2
(log To log(T)
M
S + (S0r + câ2) Moze
if Çā² 2 1
for cα2 2 5.
Step Consider D1.2. Note that in this term, the optimal action has been sufficiently drawn to be well estimated, so we can use a loose bound
T
Si(()
B(Di,)] S 1m Br
(t) (1) + +2 (log 7)2)
This right-hand side only depends on the draws from action and has been studied in Theorem I in 21 so we apply their results:
1
B
T-1
Step 3: Consider D2. Using the same technique as in lemma 7 in 15], D2 is bounded by
D2 S Σ Msst (f2(1), ((e())0) (Br) S <ā, log(T) cā log(log 7) log(Me,1)
For { > O, we let
(1 + ((ā) log(T) + cā log(log - log (M,()
Kr.
1(12,11)
Then D2 can be rewritten as
[Kr T
D2 <
1+
Σ
(fr -3))= S Çāj log(T)) + cā, log(log T) - log (M.())))))
==1
Kr.e+11
(12(t))) -BT) S d(H2,H1)
[KTTeJ +
Σ
1+
Kr.l++1
(ie((t)) I d1H2.H1)
2
KT..
Σ
+ 3r
1+
m1
(2 p1)
o= kt
21

---

where the last inequality follows from the same technique in the proof of Theorem 1 in [21] by noting that the function g(4) d+ (iz(())))
q)) is convex and differentiable and g'(4) 9-
((1-9) 1 l(
((
(s)).. Hence, for T 2 exp Following the proof of Theorem
2(1+E)1+E/2)
.w obtain d(ua.ue) + BT (1(1-13 T46/2
2 S d(pam))
T+E
21
(as well as [5] we obtain
T
P d (R2(t), 5 d(12-H1))
D & Kr.
+
1+
Kr
(1 E/2)
S KT.et + (min #2), 11 (1 21)))²
Step Combing the above results, we obtain that if 0 Çā² < 1,
[[)) SE(D1.1] + 1] [
(ā² + cāz) MapeeT (āp
(1+ (CCā log(T) + cāi log(log T) (M.1
< +
1 1 (ūx
d(v2, K1)
+ E/2)²
{3(min(u2(1 (12) 11 m1) m1))
(ā² + cāiz Mc M
+ ((7
Çāz
and if Çā² 2 1, (T)] <1[11,1] + E( + 2[D
(1+ + {{ā; lTg(T) + cāj log(log - loog(MM.))) d(p2,H1)
$ + (< + cāi) M M2 +
E/22
+ {2 (2), M1 (1 (1)))²
(1 + E)ā () log(?) + o(log 7).
d(H2,111
Note that the final step (Step 4) in the above proof provides an exact finite-time regret bound that holds for any time horizon T. It explicitly expresses the o(-) term Theorem 3.7 The error terms M,J and M, depending on e appear in this regret bound explicitly, Obviously, M.l and Ma in the bound increase as increases.
In general, our above derivations depend bounds for specific distributions (Beta posterior distribu- tions with inference errors in our setting). a direction to generalize these results to more general bandit problems more general families of distributions. For instance, 20 extends the setting of Beta posterior distribution to the exponential family that includes Gaussian (without approximate inference). Combining (20 with techniques in Sections 3.2 and 3.3 may lead to analyzing the exponential family with approximate inference. This, however, requires some additional careful technical derivation beyond our current bounds in Bernoulli with approximate inference, which is future research direction.
Appendix D
Proofs of Results in Section 3.4
Proof of Theorem
3.12 We can explicitly construct such a distribution Q₁ as follows:
(1.2 = n (x22
(1 (1-F ne. (x1) if0 < < b. b < <
2t. (x11
(be)
(13)
22

---

where Ft,1 is the cumulative distribution function (cdf) of 11,11 and r > 1, b E (0, 1) will be specified later.
First, note that by setting
91, 2,,
= 0 and 9r.2 = 72.2 with the same support [0. 1J. satisfying Assumptions 3.6 and 3.11 on action 2.
we have Dr, (1,, Qt.2)
We set by Qu( (T,2)) (0, 1), the } q-quantile of the distribution IT, (or equivalently, Qt,2). Let Fr,1 be the cdf of 11, We have Fr, (bt) E (0, 1). For r > 1, we set
-1.. (211 if0 < 21 < be (e,
(m))
(x1)
bf < x <1
Step 1: We show that qr,1 (z1) is indeed a density satisfying Assumption
3.6 on action = 1. First of
all, it is obvious that 11.1 > 0 on (0, 1) as TT, > on (0, 1). Moreover
L/ qr,1 (21)
/ qr, (x1((1)d2) + ["¹ (x1()1)d2
pbi (11 (b)( Te,1 (x1)( + [ 1 r (o
(b,(
1 11 Fe,1 Pr, (be) + (1 - (b.():))
(be)
1.
Step 2: We show that there exists (independent of t) such that qr, satisfies Assumption 3.11 on action j = 1.
We have that when < <0
< <1 1:
1
b.
(x.1
-a
dxi + L (x)(
-a (T,1(21) (x.1
(Q,, (1,)
Te, (x))
dri
a(a-11
1,,1
1
(% (2,1
(b.)
-a
dx (" Te,1 ddo
dxr
a(a -1)
1)
+ - Pr,((be)) -a
1
((1
(bc)
(1
Fi,1(bi) +r Fi,((b))) -
a(a 1)
1- (1
(r.)(b)))
We note that
(bx)
r- 1 Fr,((b)) =
(1 (b,()
1 1- [1 (F.)((b))
as r 1. Hence we have
1) -1) Then for < (ca(a 1) + 1) (only if ca(a - 1) + 0, otherwise put too as the upper bound on r), we have that
Da,,,, IT,1) a(a - 1) Pr- (br) + 0 - (b.)):))
a(a - (ra-1).
Da(Qu,1 11,11 S
When 0: Do(Qr.1, TT,1) = KI,(TT,,1, Qt.1)
(T11(111) dxg + (' Te,( log ( 41,1
) dx (11(21))
(1r)
1- 111 ((,)(be)) ) don ('' (e)( log (r) dx
(bb)
ne,1 (11)
Fi,1 (br)
log
(b,) + log (r) (1 -F,((b))
[(1 Fr.
23

---

We note that
(b,)
r + Ft,1(be)
1 1 (1 (b)()
$
1 =1 -Fr,((b))
=
as r > 1. Hence we have
L Q1,1) S log (r) (b.) log (r)) (1 (b,((b))) log (r).
Then for 1 < <. e., we have that
D (T,1)) = KL Q1,1) & log (r) - log (c*) = c.
Step 3:
We show that the probability of sampling from Q.- choosing action 2 is greater than a positive constant [1 -1- which thus leads to a linear regret.
In fact, the probability of sampling from Qt-1 choosing action given by 1 2 x1). Therefore we have that
Po:-, (12 2 11) 2 QQ (x2 2 b 2 x1) PQ.-1, b( (2) b(-1)
since Qt-1,1 and Qt-1,2 are independent.
PQ--1a 2 b1-1) =
since 4-11 is the 2 -qquantile of the distribution 1T, and pr-12 > on (0.
11-1)= =1 (1 (b 2 r
PQ. In (a) S b-- = Pq. I. (1) 2 b1-1)
by our construction of Q.-1,1. Therefore we have that
PQ-1 21) マ/ (1 1 0.
We conclude that the lower bound of the average expected regret given by
T Σ (p1 (P1-M) (N)-)))NN((()2 (PI -22) 2 7
) I(T))
R(T.
leading to linear regret.
Proof of Theorem 3.13
We can explicitly construct such a distribution Qr as follows:
(x,1 = Tt, (x1)
if0 < 01 < b if
(x,2 =
(14)
Fb,((b)) (22)
z1 < 1
where Ft, is the edf of IT,2 and 1, b, (0, will be specified later.
First, note that by setting
4.1 Tt,1
we have D. 1 Qτ.1) = 0 and 9t,1 = T1 with the same support [o, 1]. satisfying Assumptions
3.6 and 3.1l action 1.
We Qu(
(0, 1), the 7 -u--ntietele of the distribution It,1 (or equivalently, 1. Let F,, be the edf of 21,2. We have (b, E (0, 1). For > 1, we set
m (#2)
if < < b. if < <
(12(222)
(bee
Fia(be)
24

---

Step 1: We show that (0,2(12) is indeed density satisfying Assumption 3.6 on action j = 2. First of
all, is obvious that 9t,2 > 0 on (0, 1) as Tt. (0, 1). Moreover
L. (12((2))22 (22(22)d22 + (nd 91,2 (1.2(22)dzg)
1 - (b,) (122
n. Pr,((b))
1 ((,)))))
Fi2((bi) + 1 1- ((,(bb)
(1 Fr,2(b:))
1.
Step 2: We show that there exists on action j = 2.
(independent of () such that dr satisfies Assumption 3.11
We have that when < =0r00<a<
Da(Qu22 (4,2) = a(a-1) (%o"
by (e,2(12)
T02(222)
dx + / T1,2(022)
(12((2))
dr² -
(),2(222)
(2,2(22))
TT,2(02) a dx² + [' T(,((12)
(be)
dr2 -1
a(a- -) 1)
(b)))
b1
1
Fr,e(
Fu,((b)))))) +
(1 - Piz((b)) -1
ala - 1)
(b.(
We note that
1 ((,(
r -- (b,(
1 (b,2(b)))
1 (bbb())))
as > 1. Hence we have
Da (1 Qr,2) s a(a-1) 1) (r "0-aF, (bb) + + Ft,2(b:)) -1) (ra--))
Then for < < (ea(a 1) + 1) (only if ea(a - 1) + otherwise we put to0 as the upper bound on r), we have that
Da(Qr,2 I1,22) Sc
When a = 0.
Do(Qr2 Hx22) KL Qc.2) 1/ Tr,2 log Tr.((12) (2,2(12)
drg [' TT,2 log Tr,2(12)
dxz
(0,2(12)
h
1 - Fe,e(be) dxz
((,((12) log (r) drz
(T,( log
be
Foe(b1)
log (r) (r)
(b,((b)) + log
(1 - Fez(bb))
Fiz()))
We note that
1 (r,((bt)
(b,(
(bbb(())
(b))
1. Hence we have
LI Qr.2) I log (r) (b,2(b:) log (r) (1 Fi,((be)) log (r).
Then for 1 <r<c we have that
Do(Qu2, 11,2) = KL Q+.2) < log (r) = log (e*) = e.
Therefore, we conclude that there exists an r >> 1 (independent of L) such that 41,2 satisfies Assumption 3.1T on action j = Take this r > and notice that since 7t - as > +00, there must exists
T 0 such that for any > To. we have that 7 >
25

---

Step 3: We show that the EBUCB algorithm always chooses action when t 2 To, which thus leads linear regret.
We note that when 2 To. by definition,
PQ-11 (01 S bz-1) 1T (2) S (e-1) 7M
1
PQi-1a (02 S b1-1) r -1-1,2(0-11) - <ttt
which implies that
Qu(Ti, Q1-1,)= = < Qu(Ti, Qr-1,2)
Therefore after time step / 2 To. the EBUCB algorithm will always choose the action 2. We conclude that the lower bound of the average expected regret is given by
R(T. A)
Σ (1 P1- BN, 2 (M1 P2) To) (2(T) j=1
leading to a linear regret.
Appendix E
Additional Experiments
In this section, we present additional experimental results. We enrich our experiments by studying an increasing number of arms as well as multiple new problem instances with different inference errors. These results further support our findings in Section that EBUCB without the horizon-dependent term (i.e., 0) performs the best.
Suppose the posterior distributions misspecified to the following distributions:
(1 - w) * Beta(1 + Sy(1), + N2(1) - S,(()) + w Beta(T(1 + Sy()), [(1 + N₃(() S,(1))
where j E [K]. We conduct two experiments: 1) The Bernoulli multi-armed bandit problem has K actions with the following mean rewards:
K 2: mean rewards [0.7, 0.3]
K 4: mean rewards [0.9, 0.7, 0.5, 0.3]
K 8: mean rewards [0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2]
K 16: mean rewards [0.9, 0.85, 0.8, 0.75, 0.7, 0.65, 0.6, 0.55, 0.5, 0.45, 0.4, 0.35, 0.3, 0.25, 0.2,
0.15]
Let 0.5. Let w 0.9. The results are shown in Figure beloo.
2) We also study different values in the appropriate distribution that lead to different inference errors. Consider r 0.05, 0.1, 0.2, 0.5, 2, 5, 10, 15 in the experiments. Let K with mean rewards = [0.7, 0.3]. Let w 0.9.
The results are shown in Figure below.
26

---

0=0.0; T=0.KK22 K=2
K=0
15
10
230
400
800
500
1200
200
600
1000
T- 0.S; K-
--05; K
20
60
20
T= 2=2 2
F= K
25
20
15
10
T K
K 16
20
20
Figure 3: Experiments with different K with r = 0.5, 2. The curve-algorithm correspondence is the
same as Figure
27

---

40
90
30
90
20
230
400
800
500
1200
230
400
800
800
1200
0=
200
100
000
100
1200
200
100
000
100
1000
=
r
200
400
800
500
1200
200
1200
T 10
r 15
2
Figure 4: Experiments with different r. The curve-algorithm correspondence is the same in Figure
28


Reviews:
[{"review_id": "tA8JeDD6sf", "reviewer": "Reviewer_XLXW", "summary": "This paper considers the standard multi armed bandit problem with a prior on rewards, allowing the design of Bayesian algorithms such as Thompson sampling and Bayesian UCB. The problem of interest is when the exact posterior distributions are not available. Rather an approximate posterior is available. It has been known that even with a small constant alpha divergence error between the true and approximate posterior, Thompson sampling does not converge. This paper shows that with a two bounded alpha divergence (see Assumption 3.3) Bayesian UCB achives order optimal regret bound. ", "questions": "1. Could authors provide more intuition into the significance of their results for the complex settings where the distributions are approximated. It seems the results are limited to simple settings where the posterior is easily obtained. Could authors intuitively explain why small alpha divergence is not enough and two alpha divergence works. \n\n2. As small alpha divergence is not enough and only two alpha divergence works in this setting, one would expect Theorem 3.7 to fail when $\\alpha_1=\\alpha_2$. In line 254, it is stated that we may choose $\\zeta=\\frac{1}{\\tilde{\\alpha}_2}$. If, in addition, we set $\\alpha_1=\\alpha_2$, implying $\\tilde{\\alpha}_1=\\tilde{\\alpha}_2$, the upper bound in Theorem 3.7 still seems to work. Could authors explain what happens here when $\\alpha_1=\\alpha_2$ and if the Theorem fails. \n", "limitations": "As mentioned above, the main limitation of the paper seems to be the simple setting, where the posteriors are available in closed form. The results do not seem to be extendable to more complex setting where approximate distributions are actually relevant. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The problem of designing Bayesian optimization algorithms which find the optimal action in the presence of approximate distributions is very interesting. ", "weaknesses": "The setting is motivated with the difficulty of obtaining true distributions that often arises in complex models and when using methods such as variationally inference. The results are however proven on a system of Bernoulli distributions where the posterior is available in closed form. I think this break the logic on motivation to a great extent. \n\nWhile I tried to read all the proofs and details, I could not obtain a good intuition into why small alpha divergence is not enough and two alpha divergence works; how can this be used when applied to for example MCMC or variational inference. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer for the careful reading and valuable feedback. We address the reviewer's concerns below.\n\nQ1. \"Significance of current results for the complex settings\". The key contribution conveyed in this paper is the theoretical insights and guidelines that positively support the practical use of approximate Bayesian inference in bandits. This, to the best of our knowledge, has not been addressed in the previous literature, even in Bernoulli bandit problems. \n\nOur results contribute to understanding the approximate Bayesian bandit methods with complex settings from the following aspects: \n\n1) Our study takes the very first step in investigating the theory paradox in approximate Bayesian bandit methods. As such, we validate our current framework on a basic problem setting, the Bernoulli bandit problems, and consider the more general bandit problems as our future research directions. Our framework is generic, and could be further extended to more complex settings. Below is a direction to undertake for more complex settings:\nGeneralization to the exponential family: Kaufmann, E., [2018] extends the bound for Beta posterior distribution to the exponential family that includes Gaussian (without approximate inference). By combining Kaufmann, E., [2018] with our techniques in Section 3.2, our results could be generalized to the exponential family with approximate inference. This, however, requires some additional careful technical derivation beyond our current bounds in Bernoulli with approximate inference, which will be our future research direction. \n\n2) Our study provides theoretical support for the superior performance of approximate Bayesian bandit methods, which is not limited to the basic settings. With bounded inference error, Phan et al. [2019] indicated negative theoretical results in multi-armed bandit problems, which contradicts the superior performance of approximate Bayesian bandit methods in practice. To this end, our work resolves this paradox by showing positive results, and further provides direct guidance for real-world algorithm design.\n\n3) The two $\\alpha$ s should be in different regions (one $\\alpha$ greater than 1, and the other $\\alpha$ less than 0) to guarantee that $P_2$ is close to $P_1$ from both “directions”. As we have discussed after Assumption 3.3, “Intuitively speaking, minimizing $D_\\alpha(P_1, P_2)$ when $\\alpha$ is large (greater than 1), $P_2$ is flattened to cover $P_1$’s entire support, while when $\\alpha$ is small (less than 0), $P_2$ fits the $P_1$’s dominant mode.” Therefore, with one bounded alpha divergence, one can only guarantee that $P_2$ is close to $P_1$ from one “direction”, which could lead to the degenerating performance when using the approximate distribution.\n\nQ2. \"$\\alpha_1$ = $\\alpha_2$\". In Assumption 3.3, we explicitly state that two parameters should satisfy that $\\alpha_1 > 1$ and $\\alpha_2 < 0$. Therefore, Theorem 3.7 excludes the setting where $\\alpha_1$ = $\\alpha_2$ or $\\alpha_1$ is close to $\\alpha_2$.\n\nIn particular, the two $\\alpha$ s should be in different regions (one $\\alpha$ greater than 1, and the other $\\alpha$ less than 0) to guarantee that $P_2$ is close to $P_1$ from both “directions”. As we have discussed after Assumption 3.3, “Intuitively speaking, minimizing $D_\\alpha(P_1, P_2)$ when $\\alpha$ is large (greater than 1), $P_2$ is flattened to cover $P_1$’s entire support, while when $\\alpha$ is small (less than 0), $P_2$ fits the $P_1$’s dominant mode.” Therefore, with one bounded alpha divergence, one can only guarantee that $P_2$ is close to $P_1$ from one “direction”.\n\nMoreover, in general, if Assumption 3.3 holds for $\\alpha_1 <0$ and $\\alpha_2 < 0$, even if $\\alpha_1$ and $\\alpha_2$ are different, we cannot obtain a sublinear regret in Theorem 3.7, where the counterexamples can be similarly constructed as in Theorem 3.12/3.13.\n\nTo further address the author’s concern, we will revise and add the following to the introduction section to clarify that two $\\alpha$ s should be in different regions: \n\n“However, we will provide a novel theoretical framework and point out that the answer could be 'Yes' when the inference error measured by two different $\\alpha$-divergence is bounded where one $\\alpha$ is greater than 1, and the other $\\alpha$ is less than 0 (which guarantees that the approximate posterior is close to the exact posterior from both “directions”). ”\n\n\n"}, {"review_id": "trBVR0jFOi", "reviewer": "Reviewer_Fvi2", "summary": "This paper studies Bayesian bandits with approximate inference errors. The authors proposed an algorithm called the Enhanced Bayesian Upper Confidence Bound (EBUCB). Under a two-bounded $\\alpha$-divergence assumption, the authors show that EBUCB can achieve the optimal logarithmic regret. The authors also show that with sub-linear regret cannot be achieved with only one-bounded $\\alpha$-divergence. ", "questions": "See the weaknesses part.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors provide the first $\\log(T)$-type of regret for Bayesian bandits with constant approximation error (under 2-bounded $\\alpha$-approximation). This result is obtained based on a novel sensitivity analysis of quantile shift. Both the result and the analysis look interesting to me. The authors also show that, under 1-bounded $\\alpha$-approximation, one cannot obtain sub-linear regret; this negative result further justifies the necessity of 2-bounded $\\alpha$-approximation (Assumption 3.3).", "weaknesses": "My main concern is that the developed results are only for Bernoulli bandits, not for more general distributions (not even for the Gaussian distribution). Can authors comment on why Bernoulli is needed in the current analysis? Or what prevents the derived results from being extended to other distributions?\n\nAnother question I have is regarding the constant approximation error for the 2-bounded $\\alpha$-approximation (i.e., the $\\epsilon$ term in Assumption 3.3). It seems a bit weird to me that the regret bound doesn't depend (too much) on the $\\epsilon$ (e.g., in Corollary 3.8). Can authors comment on the reasons behind this?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly thank the reviewer for the careful reading and valuable comments. We address the reviewer's concerns below.\n\nQ1. \"Bernoulli settings and the potential extension to other distributions\". One of the major techniques in our analysis is Lemma C.1, which provides tight upper and lower bounds on the tails of approximate distributions to control the quantiles chosen by the EBUCB algorithm. In general, this bound depends on specific distributions, which are Beta distributions plus inference errors in our setting. It is possible to generalize this bound to a certain family of distributions. For instance, Kaufmann, E., [2018] extends the bound for Beta posterior distribution to the exponential family that includes Gaussian (without approximate inference). We believe that by combining Kaufmann, E., [2018] with our techniques in Section 3.2, our results could be generalized to the exponential family with approximate inference. This, however, requires some additional careful technical derivation beyond our current bounds in Bernoulli with approximate inference, which will be our future research direction. \n\nQ2. \"Dependency on $\\epsilon$\". The regret bound indeed contains $\\epsilon$. The exact finite-time upper bound is provided in Step 4 in the proof of Theorem 3.7 (We only show the most dominant term of the regret bound in the main paper to improve the readability). It includes the explicit dependence on $\\epsilon$, which is $M_{\\epsilon,1}$ and $M_{\\epsilon,2}$ there, and obviously the error about $M_{\\epsilon,1}$ and $M_{\\epsilon,2}$ increase as $\\epsilon$ increases.\n\nHowever, this dependence on $\\epsilon$ does not appear in the dominating term. The main reason is that the exact posterior will be more \"concentrated\" on the true mean with little variability as the time t increases, and the impact from the $\\epsilon$ error will vanish. We have some related discussions in Remark 3.9. \n\nTo elaborate more, we use a simple example to provide some intuitions. Consider two actions with true mean rewards 0.3 and 0.4. Then after time t, their exact posteriors will be approximately Beta(0.3N_1(t), 0.7N_1(t)) and Beta(0.4N_2(t), 0.6N_2(t)), which is ``concentrated” more and more around the mean rewards 0.3 and 0.4 as t increases. The alpha divergence between Beta(0.3N_1(t), 0.7N_1(t)) and Beta(0.4N_2(t), 0.6N_2(t)) goes to infinity when both N_1(t) and N_2(t) go to infinity (which is true by the information lower bound). Therefore, the $\\alpha$-divergence between the exact posteriors of two actions will keep increasing as t increases (finally larger than $\\epsilon$). Hence, intuitively speaking, the $\\epsilon$ error can only “substantially” impact the regret up to some time step $T_0$, and this additional error is indeed captured by our error bound: You can see the terms $M_{\\epsilon,1}$ and $M_{\\epsilon,2}$ that depending on $\\epsilon$ in Step 4 in the proof of Theorem 3.7. However, they are not the dominating term since after time $T_0$, $\\epsilon$ error cannot impact the regret too much as the alpha divergence between Beta(0.3N_1(t), 0.7N_1(t)) and Beta(0.4N_2(t), 0.6N_2(t)) has been sufficiently large."}, {"review_id": "dbTzWHTFP8", "reviewer": "Reviewer_tsC9", "summary": "In this paper, the authors consider Bayesian bandit algorithms where exact posterior is not available and\nonly approximations are available.\nThe authors prove that if $\\alpha_1$-divergence and $\\alpha_2$-divergence between the exact posterior and approximation are small,\nthen a modification of Bayesian UCB (EBUCB) achieves $O(\\log T)$ regret.\nIn the previous work, it is known that Thompson sampling with approximate inference has $\\Omega(T)$ regret.\nThe authors also show negative results for EBUCB and Thompson sampling under the condition on \nonly one $\\alpha$-divergence.\nFinally, in synthetic environments the authors confirm their theoretical findings.", "questions": "1. In Corollary 3.8, does the small $o$ notation hides $\\varepsilon$? Could you briefly discuss its dependence?", "limitations": "Limitations are not discussed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper solves an important problem (Bayesian bandit algorithms using an approximation of the posterior) and provides a nice result (the upper bound has $O(\\log T)$-regret and the dominant term does not depend on $\\varepsilon$, which is surprising).\n2. Although the environments are simple and synthetic, they conducted experiments. ", "weaknesses": "1. In Corollary 3.8, the dependence of $\\varepsilon$ is hidden (not discussed).\n2. The optimal parameters of the algorithm are not known in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer for the careful reading and valuable comments. We address the reviewer's concerns below.\n\nQ1. \"Dependency on $\\epsilon$\". The regret bound indeed contains $\\epsilon$. The exact finite-time upper bound is provided in Step 4 in the proof of Theorem 3.7 (We only show the most dominant term of the regret bound in the main paper to improve the readability). It includes the explicit dependence on $\\epsilon$, which is $M_{\\epsilon,1}$ and $M_{\\epsilon,2}$ there, and obviously the error about $M_{\\epsilon,1}$ and $M_{\\epsilon,2}$ increase as $\\epsilon$ increases.\n\nHowever, this dependence on $\\epsilon$ does not appear in the dominating term. The main reason is that the exact posterior will be more \"concentrated\" on the true mean with little variability as the time t increases, and the impact from the $\\epsilon$ error will vanish. We have some related discussions in Remark 3.9. \n\nTo elaborate more, we use a simple example to provide some intuitions. Consider two actions with true mean rewards 0.3 and 0.4. Then after time t, their exact posteriors will be approximately Beta(0.3N_1(t), 0.7N_1(t)) and Beta(0.4N_2(t), 0.6N_2(t)), which is ``concentrated” more and more around the mean rewards 0.3 and 0.4 as t increases. The alpha divergence between Beta(0.3N_1(t), 0.7N_1(t)) and Beta(0.4N_2(t), 0.6N_2(t)) goes to infinity when both N_1(t) and N_2(t) go to infinity (which is true by the information lower bound). Therefore, the $\\alpha$-divergence between the exact posteriors of two actions will keep increasing as t increases (finally larger than $\\epsilon$). Hence, intuitively speaking, the $\\epsilon$ error can only “substantially” impact the regret up to some time step $T_0$, and this additional error is indeed captured by our error bound: You can see the terms $M_{\\epsilon,1}$ and $M_{\\epsilon,2}$ that depending on $\\epsilon$ in Step 4 in the proof of Theorem 3.7. However, they are not the dominating term since after time $T_0$, $\\epsilon$ error cannot impact the regret too much as the alpha divergence between Beta(0.3N_1(t), 0.7N_1(t)) and Beta(0.4N_2(t), 0.6N_2(t)) has been sufficiently large.\n\nQ2. \"Optimal Parameters\". The exact values of $\\alpha_1$ and $\\alpha_2$ depend on the users’ choice of the Bayesian inference algorithms. Our theoretical results are built upon a general Assumption 3.1 where the Bayesian inference algorithms are not specified. "}]

Author rebuttal:

Meta-review: This paper makes a solid contribution, but there was a disagreement on the impact since the paper considers the Bernoulli bandits where the closed form expressions are available. While this is certainly a weakness, I believe the contribution is still meaningful in that it successfully delivers the message that a constant approximation ratio the approximate inference can still lead to a sublinear regret bound. This is worth being known in the community.
Decision: Accept (poster)