Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits
Authors: Tianyuan Jin
Pan Xu
Xiaokui Xiao
Anima Anandkumar
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bandit algorithms
Thompson sampling
exponential family distribution
finite-time regret bound
minimax optimality
asymptotic optimality

Abstract: We study the regret of Thompson sampling (TS) algorithms for exponential family bandits, where the reward distribution is from a one-dimensional exponential family, which covers many common reward distributions including Bernoulli, Gaussian, Gamma, Exponential, etc. We propose a Thompson sampling algorithm, termed ExpTS, which uses a novel sampling distribution to avoid the under-estimation of the optimal arm. We provide a tight regret analysis for ExpTS, which simultaneously yields both the finite-time regret bound as well as the asymptotic regret bound. In particular, for a $K$-armed bandit with exponential family rewards, ExpTS over a horizon $T$ is sub-UCB (a strong criterion for the finite-time regret that is problem-dependent), minimax optimal up to a factor $\sqrt{\log K}$, and asymptotically optimal, for exponential family rewards. Moreover, we propose ExpTS$^+$, by adding a greedy exploitation step in addition to the sampling distribution used in ExpTS, to avoid the over-estimation of sub-optimal arms. ExpTS$^+$ is an anytime bandit algorithm and achieves the minimax optimality and asymptotic optimality simultaneously for exponential family reward distributions. Our proof techniques are general and conceptually simple and can be easily applied to analyze standard Thompson sampling with specific reward distributions.

Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed
Bandits
Tianyuan Jin National University of Singapore tianyuanCu. mus edu
Pan Xu
Duke University pan. xu@duke. pan.xu@duke. edu
Xiaokui Xiao National University of Singapore xkxiao@nus. edu. sg
Anima Anandkumar
California Institute of Technology anima@caltech. edu
Abstract
We study the regret of Thompson sampling (TS) algorithms for exponential family bandits, where the reward distribution from a one-dimensional exponential fam- ily, which covers many common reward distributions including Bernoulli, Gaussian, Gamma, Exponential, etc. We propose a Thompson sampling algorithm, termed ExpTS, which uses novel sampling distribution avoid the under-estimation of the optimal arm. We provide tight regret analysis for ExpTS, which simulta- neously yields both the finite-tima regret bound well as the asymptotic regret bound. In particular, for a K-armed bandit with exponential family rewards, Ex- PTS over horizon T is sub-UCB (a strong criterion for the finite-time regret that is problem-dependent) minimax optimal up to a factor vlog K, and asymptoti- cally optimal, for exponential family rewards. Moreover, we propose ExpTS+, by adding greedy exploitation step in addition to the sampling distribution used in ExpTS, to avoid the over-estimation of sub-optimal arms. ExpTS+ + an anytime bandit algorithm and achieves the minimax optimality and asymptotic optimality simultaneously for exponential family reward distributions. Our proof techniques are general and conceptually simple and can be easily applied to analyze standard Thompson sampling with specific reward distributions.
Introduction
The Multi-Armed Bandit (MAB) problem is centered around fundamental model for balancing the exploration versus exploitation trade-off in many online decision problems. In this problem, the agent is given environment with set of K arms [K] {1,2. K). At each time step f, the agent pulls an arm A, E [K] based on observations of previous t time steps, and then a reward r, is revealed at the end of the step. In real-world applications, reward distributions often have different forms such as Bernoulli, Gaussian, etc. As suggested by Auer et al. (8 9. Agrawal and Goyal (5). Lattimore 299 Garivier et al. [16]. good bandit strategy should be general enough to cover sufficiently rich family of reward distributions. In this paper, we assume the reward r; is independently generated from some canonical one- me-parameter exponential family of distributions with a mean value A.A. It is rich family that covers many common distributions including Bernoulli, Gaussian, Gamma, Exponential, and others.
The goal of bandit strategy is usually to maximize the cumulative reward over T time steps, which equivalent minimizing the regret, defined as the expected cumulative difference between playing
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the best arm and playing the arm according to the strategy: R = T | H4; BI rz]. We assume, without loss of generality, μl [ (4 is the best arm throughout this paper. For fixed bandit instance (i.e., mean rewards yı. MA are fixed), Lai and Robbins [26] shows that for distributions that are continuously parameterized by their means,
(T)
Σ 14 kI(
lim T-00 logT
(1.1)
1311
where Kl(us; (1) is the Kullback-Leibler divergence between two distributions with mean μ4i and po 11-14 is said to be asymplotically A bandit strategy satisfying lini--oo R2, //ooooT =Eis k[]
optimal achieve the asymptotic optimality in regret. The asymptotic optimality is one of the most important statistical properties in regret minimization, which shows that an algorithm is consistently good when it is played for infinite steps and thus should be basic theoretical requirement of any good bandit strategy [8]
In practice, we can only run the bandit algorithm for a finite number T steps, which is the time horizon of interest in real-world applications. Therefore, the finite-time regret is the ultimate property of practical bandit strategy in regret minimization problems. A strong notion of finite-time regret bounds is called the sub-UCB criteria [29]. An algorithm is sub-UCB if there exist universal constants C1, C2 such that for any problem instances,
R (T) = C1
Σ (E[K].AD>0
C2
Σ
log A,
(1.2)
:E[K]AA.S0
where A, - 111 P4 is the sub-optimal gap between arm and arm i. Note that the regret bound in 1.2 is a problem-dependent bound since it depends on the bandit instance and the sub-optimal gaps. Sub-UCB is an important metric for fimite-time regret bound and has been adopted by recent work of Lattimore (29] Bian and Jun [10]. Another special type of finite-time bounds is called the worst-case regret, which is defined as the finite-time regret of an algorithm on any possible bandit instance within a bandit class. Specifically, for a finite time horizon T, Auer et al. g proves that any strategy has at least worst-case regret Q (T) for a K-armed bandit. We say the strategy that achieves a worst-case regret O ((VTT) is minimax optimal or achieves the minimax optimality. Different from the asymptotic optimality, the minimax optimality characterizes the worst-case performance of the bandit strategy in finite steps.
16 29 have been pursing the afore- mentioned theoretical properties of bandit algorithms: generality, asymptotic optimality, problem- dependent finite-time time regret, and minimax optimality. However, most of them focus on one or two properties and sacrifice the others. Moreover, many of existing theoretical analyses of bandit strategies are for optimism- algorithm. The theoretical analysis of Thompson sampling (TS) is much less understood until recently, which has been shown to exhibit superior practical performances compared to the state-of- the-art methods [13 [4] Specifically, its finite-time regret, asymptotic optimality, and near minimax optimality have been studied by Agrawal and Goyal 3 4 (5) for Bernoulli rewards. Jin et al. 200 proved the minimax optimality of 'T for sub-Gaussian rewards. For exponential family reward distributions, the asymptotic optimality is shown by Korda et al. 225. but no finite-tima regret of TS is provided. See Table I for comprehensive comparison of these results.
A vast body of literature in multi-armes bandits 6 5 22
32
In this paper, we study the regret of Thompson sampling for exponential family reward distributions and address all the theoretical properties of TS. We propose a variant of TS algorithm with general sampling distribution and a tight analysis for frequentist regret bounds. Our analysis simultaneously yields both the finite-time regret bound and the asymptotic regret bound.
Specifically, the main contributions of this paper are summarized as follows:
We propose ExpTS, a general variant of Thompson sampling, that uses a novel sampling distribution with tight anti-concentration bound to avoid the under-estimation of the optimal arm and a tight concentration bound to avoid the over-estimation of sub-optimal arms. For exponential family of reward distributions, we prove that ExpTS is the first Thompson sampling algorithm achieving the finite-timm -imte--tme regret bounds. We
sub-UCB criteria, which is a strong notion of problem-depende further show that ExpTS is also simultaneously minimax optimal up to factor of vlog K, as well asymptotically optimal, where K is the number of arms.
We also propose ExpTS- which explores between the sample generated in ExpTS and the em- pirical mean reward for each arm, to get rid of the extra Vlog K factor in the worst-case regret.

---

Table I: Comparisons of different Thompson sampling algorithms K-armed bandits over horizon T. For any algorithm, Asym. Opt is the indicator whether it is asymptotically optimal, minimax ratio is the scaling of its worst-case regret w.r.t. the minimax optimal regret OVVV.T), where V is the variance of reward distributions, and sub-UCB is the indicator if it satisfies the sub-UCB criteria.
Asym. Opt
Finite- Time Regret
Algorithm
Reward Type
Anytime
Reference
Minimax Ratio Sub-UCB
TS TS TS
Berouuli
yes
Vog T v log K
yes
4
Bemoulli
yes
Exponential Family
yes
yes
MOTS
sub-Gaussian
no
1
no no
20
MOTS-J J
Gaussian
yes
1
no
20
ExpTS
Exponential Family yes Vlog K
yes yes
This paper
ExpTS*
Exponential Family
yes
no yes
This paper
4 S did not explicitly show that their regret bounds are sub-UCB. However, the intermediate results
in their proofs might imply sub-UCB regret bounds.
Thus ExpTS is the first Thompson sampling algorithm that is simultaneously minimax and asymptotically optimal for exponential family of reward distributions.
Our regret analysis ExpTSS can be easily extended to analyze standard Thompson sampling with common reward distributions. We prove that standard Thompson sampling without inflating the posterior distribution is minimax optimal up to a factor of Vlog K, which matches the regret lower bound for standard Thompson sampling in Agrawal and Goyal [5]. Similar to the idea of ExpTS*. + we can add a greedy exploration step to the posterior distributions used in these variants of TS, and then the algorithms are simultaneously minimax and asymptotically optimal.
Our techniques are novel and conceptually simple. First, we introduce a lower confidence bound in the regret decomposition to avoid the under-estimation of the optimal arm, which is important in obtaining the finite-time regret bound. Specifically, Jin et al. 20 (Lemma in their paper) shows that for Gaussian reward distributions, Gaussian-TS has regret bound at least in the order of Q( / KKT log if the standard regret decomposition in existing analysis of Thompson sampling [5 30 20 is adopted. With our new regret decomposition that is conditioned on the lower confidence bound introduced in this paper, we improve the worst-case regret of Gaussian- -S for Gaussian reward distributions O( DVKTloog K).
Second, we do not require the closed form of the reward distribution, but only make use of the corresponding concentration bounds. This means our results can be readily extended to other reward distributions. For example, we can extend ExpTS* to sub-Gaussian reward distributions and the algorithm is simultaneously minimax and asymptotically optima which improve the results of MOTS proposed by Jin et al. (20) (see Table IT.
Third, the idea of ExpTS* is simple and can be used to remove the extra vlog K factor in the worst-case regret. We note that MOTS 20 can also achieve the minimax optimal via the clipped Gaussian. However, it is not clear how to generalize the clipping idea to the exponential family of reward distribution. Moreover, it uses the MOSS ( index for clipping, which needs to know the horizon T in advance and thus cannot be extended to the anytime setting, while ExpTS is an anytime bandit algorithm which does not need to know the horizon length in advance.
Notations. We let T be the total number of time steps, K be the total number of arms, and [K] 21,2,... KK. For simplicity, we assume arm is the optimal throughout this paper, i.e., 1 max pa. We denote log + (x) max (0, log x) and A; = un Uái i [K] \ (1) for the
'This is common trick in the literature. In particular, for Bernoulli rewards, instead of using Beta posterior, Agrawal and Goyal S consider Thompson sampling with Gaussian posterior, whose variance larger. Moreover, Jin et al. 200 inflate the variance of the sampling distribution by a factor 1/p. where < 1. However, both of these methods lose the asymptotic optimality.
NNote that sub Gaussaan is non- parammeree family and thus the lower bound [T.] by Lai and Robbins 26
does not directly apply to general sub Gaussian distribution. Following similar work in the literature (20). in this paper, when we say an algorithm achieves the asymptotic optimality for sub- So--aussiia rewards, we mean its regret matches the asymptotic lower bound for Gaussian rewards, which is a stronger notion.
3

---

gap between arm 1 and arm i. We let E = be the number of pulls of arm i at the time step t, (t)(t) == ( [r, 1[A, - = be the average reward of arm at the time step i, and Ais be the average reward of arm after its s-th pull. We reserve notations C1, C2 : to be positive universal constants that are independent of problem parameters.
2 Related Work
There are series of works pursuing the asymptotic regret bound and worst-case regret bound for MAB. For asymptotic optimality, UCB algorithms [3 29]. Thompson sampling [23 25 20). Bayes-UCB 22] and other methods [0] are all shown to be asymptotically optimal. Among
them, only a few 15 12 25| can be extended to exponential families of distributions. One notable
result in Cappé et al. [12 shows that for [0, 1] bounded distribution, there exists an algorithm that has regret E A, log T ///k( μ1) + O(E (log 4) log log T' A which is better than (.2). It is an interesting problem whether we can achieve such regret for unbounded reward distributions. For the worst-case regret, MOSS [6] is the first algorithm proved to be minimax optimal. Later, KL-UUB++ [5), AdaUCB (29). MOTS (20 also join the family. The anytime version of MOSS is studied by Degenne and Perchet [14. There are also some works that focus on the near optimal problem-dependent regret bound 127 28 As far as we know, no algorithm has been proved to achieve the sub-UCB criteria, asymptotic optimality, and minimax optimality simultaneously for exponential family reward distributions.
For Thompson sampling, Russo and Van Roy 33] studied the Bayesian regret. They show that the Bayesian regret of Thompson sampling never worse than the regret of UCB. Bubeck and Liu [IT] further showed the Bayesian regret of Thompson sampling is optimal using the regret
analysis of MOSS. There are also a line of works focused on the frequentist regret of TS. Agrawal
and Goyal 3 proposed the first finite time regret analysis for TS. Kaufmann et al. 23 Agrawal
and Goyal proved that TS with Beta posteriors asymptotically optimal for Bernoulli reward distributions. Korda al. [25] extended the asymptotic optimality the exponential family of reward distributions. Subsequently, for Bernoulli rewards, Agrawal and Goyal [5] proved that TS with Beta prior is asymptotically optimal and has worst-case regret O ((KTT)) log T'. Besides, they showed that TS with Gaussian posteriors can achieve a better worst-case regret bound O( log K). They also proved that for Bernoulli rewards, TS with Gaussian posteriors has worst-cass regret least O( 0(VKTlog K). Very recently, Jin et al. (20) proposed the MOTS algorithm that can achieve the minimax optimal regret O(VKT) for multi-armed bandits with sub- Sab-Gaussian rewards but at the cost of losing the asymptotic optimality by a multiplicative factor of 1/p, where 0 < p is an arbitrarily fixed constant. For bandits with Gaussian rewards, Jin et al. (20) proved that MOTS combined with Rayleigh distribution can achieve the minimax optimality and the asymptotic optimality simultancously. We refer readers to Tables and 2 for more details.
3 Preliminary on Exponential Family Distributions
17 32 is a parametric set of probability distributions with respect to some reference measure, with the density function given by
dieeedmmeniioall canonical exponential family 15
(x() = exp(x0 b(0) + c(x)),
where 0 is the model parameter, and e is a real function. Denote the measure of po()) as vg. Then, the above definition can be rewritten as
dva (x) = exp(x0 b(0)). dp
for some measure P and b(0) = log(, ex dp(x)). We make the classic assumption used by Garivier and Cappé (15). Ménard and Garivier [32 that b(0) is twice differentiable with continuous second derivative. Then, we can verify that exponential families have the following properties:
6' (0()) Erro and
6"(0) [ar > 0.
'Cappé et al. [12 used a more general notation (-a((,)) -) for any distribution supported in [0, 1J, which is equivalent to the kl(:)) notation for the one-exponential family distribution studied in our paper.

---

Let = E(po]. The above equality means that the mapping between the mean value of v/() and the parameter 0 is one-to-one. Hence, exponential family of distributions can also be parameterized by the mean value μr = (0). Note that (0) > O for all 0, which implies (())) is invertible and its inverse function 1 satisfies 0 1 (n). In this paper, we will use the notion of Kullback-Leeibe
(KI.) divergence. The KI. divergence between two exponential family distributions with parameter 0 and 0' respectively is defined as follows:
KL ver) b((') b(0) 6' ('0) 0).
(3.1)
Recall that the mapping + is one-to-one. We can define an equivalent notion of the KL divergence between random variables My and Vy function of the mean values μ and pt respectively:
kl(j, - (L Uer) );
where [0[r0] = y and [|p0] = n.. Similarly, we define V(a) = (ar( as the variance of an
exponential family random variable uy with mean μe. We assume the variances of exponential family distributions used in this paper are bounded by constant V > O: V - < +00. We have the following property of the KL divergence between exponential family distributions.
Proposition 3.1 (Harremoës (17). Let y and p' be the mean values of two exponential family distributions. The Kullback-Leible divergence between them can be calculated as follows:
p I- 11 dr. /.d P ((x)*
kl(
(3.2)
Based on Proposition [.11. we can also verify the following properties. Proposition 3.2 (Jin et al. [9)). For all μ and p'. we have
kl(p, 2 (i= -=)) In addition, for e > 0 and μ S p² e, we can obtain that kl(p, 2 dd(p.p'' c) and ((H,,') S kl(H e.p.)
(3.3)
(3.4)
Exponential families cover many of the most common distributions used in practice such as Bernoulli, exponential, Gamma, and Gaussian distributions. In particular, for two Gaussian distributions with the same known variance o² but different means μ and μ², we can choose V-) = o², and it holds that kl(u, n²) = (H+ n²)² /(2o)). For two Bernoulli distributions with means and μ respectively, the variance upper bound is set V 1/4. Thus can recover the result in Proposition 3.1 as kl(,, n²)= = μ log(p/p² p/) + (1) log(( (1- p)/(1- p²)). For exponential and Gamma distributions, suffices to ensure the variance id bounded as long as we assume the mean value is bounded.
The definition of one-dimensional exponential family in our paper is (o = cxp(10 b(i) + c(x)).
which is the same that used by Garivier and Cappé [15], Harremoës 17 Jin et al. [19, Ménard
and Garivier 332 as well as Cappé et al. [12]. The -ie-dimensional exponential family considered in
Korda et al. 25 (po (2) exp( [
b(0) + c(x))) is more general than that in the aforementioned papers (see page 4 in Korda et al. (25) Lai and Robbins (26) considers parametric distributions that
satisfies some mild conditions, which is also more general than ours. Moreover, Cappé et al. [12
also considered the general reward distributions supported in [o, 1], which is not compatible to ours.
4 Thompson Sampling for Exponential Family Reward Distributions
We present general variant of Thompson sampling for exponential family rewards in Algorithm [ named as ExpTS. At round I, ExpTS maintains an estimate of a sampling distribution for each arm, denoted as P. The algorithm generates a sample parameter 0, (L) for each arm i independently from their sampling distribution and chooses the arm that attains the largest sample parameter. For each arm i [K]. the sampling distribution P is usually defined as function of the total number of pulls (t) and the empirical average reward fi (t). After pulling the chosen arm, the algorithm updates (t))) and (t) for each arm based on the reward r; it receives and proceeds to the next round.
Since we study the frequentist regret bound of Algorithm ExpTS not restricted as a Bayesian that the sampling distribution does not have to be a posterior distribution derived from a pre-defined prior distribution. Therefore, we call P. the sampling distribution instead of the posterior distribution as in Bayesian regret analysis of Thompson sampling 33 I.I. To obtain the finite-time regret bound of ExpTS for exponential family rewards, we will discuss the choice of general sampling distribution and new proof technique.
method. It has been shown [
20
24
36
5

---

Algorithm 1 Exponential Family Thompson Sampling (ExpTS)
Input: Arm set [K]
2: Initialization: Play each arm once and set TiK = 1; let (K: be the observed reward of
playing arm
3: for = K + 1. K.KK + do
4: For all i [K], sample (t) independently from (t),
5: Play arm A, = arg [a]] (1) and observe the reward
6: For all i E [K], update the mean reward estimator and the number of pulls:
(4(() = [t - 1) p. 1) +r, Ar}
T((t= = T,(t 1) 1fi }A}
Ti(t - 1) +) A
7: end for
4.1 Challenges in Regret Analysis for Exponential Family Bandits
Before we choose a specific sampling distribution P for ExpTS, we first discuss the main challenges in the finite-time regret analysis of Thompson sampling, which is the main motivation for our design of P in the next subsection.
of the Optimal Arm. Denote P4i as the average reward of arm i after its s-th pull, (t) the number of pulls of arm at time and P( s) as the sampling distribution of arm i after its s-th pull. The regret of the algorithm contributed by pulling arm i is [T (T)). where (T) is the total number of pulls of arm All existing analyses of finite-time regret bounds for TS 33 20 decompose this regret term as A A,E(T,(T) I D; + h2 (A, A. T, 0, (1)..... A (T)), where ( is a quantity characterizing the over-estimation of arm i which can be easily dealt with by some concentration properties of the sampling distribution (see Lemma A.3 for more details). The term D; characterizes the under-nstimation of the optimal arm 1, which is usually bounded as follows.
T
1
1
D. = A
Epia
(4.1)
Gia(E)
where Gis(e) = 11 +), Fis is the CDF of the sampling distribution P( 8), and e = ((i)). In other words, Gi) = P(O > #ı - -)) is the probability that the best arm will not from the mean reward by margin e. Furthermore, in (4.1) as the result of union bound indicating how many samples TS requires to ensure that at least one sample of the best arm {01 (t)) is larger than μ4 If (c) is too small, arm could be significantly
be under-estimane
interpret the quantity
eetti-estimated,, and thus D, will be unbounded. In fact, as shown in Lemma 5 by Jin et al. (20). for MAB with Gaussian rewards, TS using Gaussian posteriors will unavoidably suffer from the lower bound of K D; = 26 (KTlllg)
To address the above issue, we introduce lower confidence bound for measuring the under-estimation problem. We use a new decomposition of the regret that bounds D, with the following term
(Gil [ 2 Low.}
A Σ Ban.
(4.2)
1=1
where Low, is lower confidence bound of Tiss Intuitively, due to the concentration of arm I's rewards, the probability of ç0ıx S Low, very small. Thus, even when Gia(e) is small, the overall regret can be well controlled.
In the regret analysis of TS, we can bound (4.2 from two facets: (1) the lower confidence bound can be proved using the concentration property of the reward distribution; and (2) the term Gia(e) = (t) > #1 - E) can be upper bounded by the anti-concentration property for the sampling distribution P. To achieve an optimal regret, one needs to carefully balance the interplay between these two bounds. For specific reward distribution (e.g., Gaussian, Bernoulli) as studied by Agrawal and Goyal [5]. Jin et al. (20), there are already tight anti anti-concentration inequalities for the reward distribution, and thus the lower confidence bound is tight. Therefore, by choosing Gaussian or Bernoulli as the prior (which leads to Gaussian or Beta sampling distribution P), we can use existing anti-concentration bounds for Gaussian 2 Formula 7.1.13] or Beta 18 Prop. A.4] distributions to obtain a tight bound of G1)

---

In this paper, we study the general exponential family of reward distributions, which has no closed form. Thus we cannot obtain tight concentration bound for fis as in special cases such as Gaussian or Bernoulli rewards. This increases the hardness of tightly bounding term (4.2) and it is imperative for us to design sampling distribution P with tight anti-concentration bound that can carefully control (c) without any knowledge of the closed form distribution of the average reward A1s- Due to the generality of exponential family distributions, it is challenging and nontrivial to find such a sampling distribution to obtain tight finite-time regret bound.
4.2 Sampling Distribution Design in Exponential Family Bandits
In this subsection, show how choose sampling distribution P that has tight anti-concentration bound to overcome the under-estimation of the optimal arm and concentration bound to overcome the over-estimation of the suboptimal arms.
For the simplicity of notation, we denote P(u, n)) as the sampling distribution, where μ and n are some input parameters. In particular, for ExpTS, we will choose (t:(t) and n (i(t) for arm i [K] at round t. We define P P(u, n) as distribution with PDF
(bbb-bbbaaa))) Al(a,)) nbn, 1 μl nbn (l).,))
[a; μ4, n) = 1/2 kl(u, =)) "bb.,
(4.3)
2V(x)
where (kI(p, = denotes the derivative of kl(p,r) with respect x, and bn a function of n and will be chosen later.
We assume the reward is supported in Rmiin Rmaax] Note that Rmin O, and Rinax Bernoulli rewards, and Rauin = -00, and Rmax = 0o for Gaussian rewards. Let p(x) and g(x) be the density functions of two exponential family distributions with mean values H&p and My respectively. pla)
for
By the definition in Section we have kl(ppp: Myy KL(p(z), q(x)) = Rams p(z) log g(a) dr.
Proposition 4.1. If the mean reward of q(z) is equal the maximum value in its support, i.e., M4 = Rmax we will have kl(u, Rmax)) = 3o for any p < Rmax-
Proof. First consider the case that Rmax < co. Since the mean value concentrates on the maximum value, we must have q(x)) = for x < Rmax which immediately implies kl(u, Rmax) oo for any μ < Rmax- For the case that Rmax 0o, from 3.3 and the assumption that V co, also
have kl, 0o) = (oo 4)² /V V= DC.
Similarly, we can also prove that kl(u,, Rmii) = oc for Rmin- Based on these properties, can easily verify that a sample from the proposed sampling distribution 0 ~ P has the following tail bounds: for 2 E [H,, Rmax), it holds that
Ramax
Rmax
PPO 2 2)
((; = 11/2 nb, kl(p.))
-1/2e nbn -lla,z))
(4.4)
and for 2 E (Rmiu 14], it holds that
P(O S 2) 1"
[1; = 1/2e nbn -nn k(((a))
1/22 nbn kl
(4.5)
Rumin
Rmin
Note that Buuee f(z; p1 = f(x; p, n)dr + Buns (Ls;,,n)dx 1, which indicates the PDF of P is well-defined.
Intuition for the Design of the Sampling Distribution. The tail bounds in 4.4) and (.5) provide proper anti-concentration and concentration bounds for the sampling distribution P as long as we have corresponding lower and upper bounds of e -nh, (nh,,kk((..2)) When is large, we will choose b, to be close to 1, and thus (4.4) and (4.5) ensure that the sample of the corresponding arm concentrates in the interval (μ - e, f + E) with an exponentially small probability e -nkk(p-cc.tte, which is crucial for achieving a tight finite-time regret.
How to Sample from P. We show that sampling from tractable when the CDF of invertible. In particular, according to (.4) and (45)), the CDF of P(,, is
1/2e -nh, 1n2 ((((a))
p
F(x)
1/2e nb, k1(xz))
p.
7

---

Table 2: Comparisons of different algorithms K-armed bandits horizon T. For any algorithm, Asym. Opt is the indicator whether it is asymptotically optimal, minimax ratio is the scaling of its worst-case regret w.r.t. the minimax optimal regret O(vVKT), sub-UCE indicates whether it satisfies the sub-UCB criteria, and Anytime indicates whether it needs the knowledge of the horizon length T in advance.
Algorithm
Reward Type
Asym. Opt
Finite-Time Regret
Anytime
References
Minimax Ratio
Sub-UCB
MOSS
0. 1 0.
no
Anytime MOSS
no
no yes
KL-UCB++
Exponential Family
yes
no
32
OCUCB
sub- Gabs-Gass Gaussian
no
Vlog log
yes
yes
AdaUCB
yes
yes
n1
MS
aub-Gaussian
yes
Vlog K
yes
yes
10
ExpTS
Exponential Family
yes
vlog 1
yes
yes
This paper
ExpTS*
Exponential Family
no
yes
This paper
To sample from P(u, n), we can first pick y uniformly random from [0, 1]. Then, for y 2 1/2, we solve the equation y = 1 - 1/2e- -b,, kl((,.r) for æ (a 2 μ1), which is equivalent to solving 1og(1/(2(1= - (nbb) kl(,,)). For y I 1/2, we solve the equation = 1/2c 1/2e-mbb-KK(H.r for S μ), which is equivalent to solving log(
kl(u, æ). If b(0) is reversible and the mapping 8 + is giver"] then according to (3.1) (l x)) is also reversible for æ. We can obtain an Altematively, also use approximate sampling methods such as Monte Carlo Markov Chain and Hastings-Metropon 25 or gradient based Langevin Monte Carlo 35
(mzb,
exact sample from distribution P by solving kl z)
(1/(2y))/
to obtain samples from the target distribution.
4.3
Regret Analysis of ExpTS for Exponential Family Rewards
Now we present the regret bound of ExpTS for general exponential family bandits. The sampling distribution used in Algorithm i defined in (4.).
Theorem 4.2. Let bn = (n 1)/n. Let P be the sampling distribution defined in Section 4.2
There
exist universal constants Co, C1 > 0 such that the regret of Algorithm 7 Asatisfies
Vlog(TA./V)
(T) Co
Σ
A
max SE
A. T,
(4.6)
A
:E[K]:a,>>
K
RT( S Ci
A.r +
VVKT log
(4.7)
1=2
where X > 16/V/T, and also satisfies the following asymptotic bound simultaneously:
(T)
K
A
lim T-200
(4.8)
T
Remark 4.3. Similar to the argument by Auer and Oriner AZ], we can see that the logarithm term in (4.6) is the main term for suitable X. For instance, if we choose X 16/V/T, we will have max4e[K) A.SA (,,,,, A,T < VVT. which is in the order O(V/A:) due A S X. Thus it is obvious to see that the regret in (4.6) satisfies the MCB criteria.
It is worth highlighting that ExpTS is anytime algorithm and simultaneously satisfies the sub-UCB criteria in (T.2), the minimax optimal regret up to a factor Vlgg K, and the asymptotically optimal regret. EXpTSS also the first Thompson sampling algorithm that provides finite-time regret bounds for exponential family of rewards. Compared with state-of-the-art MAB algorithms listed Table 2 ExpTS is comparable to the best known UCB algorithms that work for exponential family of reward distributions and no algorithms can dominate ExpTS. In particular, compared with MS [10 and
TTis is true for distributions such Gaussian with known variance, exponential distribution, and Bernouli.

---

OCUCB (28), ExpTSS is asymptotically optimal for exponential family of rewards, while MS is only asymptotically optimal for uub-Gaussian rewards and OCUCB is not asymptotically optimal. We note that Exponential Family does not cover the sub-Gaussian rewards. However, since we only use the tail bound to approximate the reward distribution, Exp'TSs can also be extended to solve sub-Gaussian reward bandits, which we leave as a future open direction.
4.4 Simple Variants for Gaussian and Bernoulli Reward Distributions
The choice of P in 4.3) seems complicated for a general exponential family reward distribution, even though we only need the sampling distribution to satisfy a nice tail bound derived from this reward distribution. When the reward distribution has a closed form such as Gaussian and Bernoulli distributions, we can replace d with the posterior in standard Thompson sampling and obtain the asymptotic and finite-time regrets in the previous section.
Theorem 4,4. If the reward follows Gaussian distribution with a known variance V, we can set the sampling distribution in Algorithm Mas as (T.(),, V/T,(t). The resulting algorithm (denoted as Gaussian- -SS) enjoys the same regret bounds presented in Theorem 4.2)
Remark 4.5. Lemma 5 in Jin el al. [20] shows for Gaussian rewards, Gaussian-T'S has a regret bound at least 52( (2VVVK KT Klogg T) if the standard regret decomposition discussed in Section 4.1 is
adopted in the proof 15 30 20J. With our new regret decomposition and the lower confidence bound
introduced in (4.2) we improve it O(VVKT log K).
Jin et al. 120 also shows that their algorithms MOTS/MOTS-J can overcome the under-estimation However, they are either at the cost of sacrificing the asymptotic optimality or not
issue of
generalizable to exponential family bandits. In specific, (1) For Gaussian rewards, MOTS [20] enlarges the variance of Gaussian posterior by factor of 1/p. where p E (0, 1), which loses the asymptotic optimality by a factor of 1/p resultantly. (2) For Gaussian rewards, MOTS-J 1201 introduces the Rayleigh posterior asymptotic optimality. However, it is not clear whether the idea can be generalized to exponential family rewards. Interestingly, their experimental results show that compared with Rayleigh posterior, Gaussian posterior actually has a smaller regret empirically. Therefore, to use a Gaussian sampling distribution, the new regret decomposition and the novel lower confidence bound in our paper is better way to overcome the under-estimation issue of Gaussian-TS.
overcome the underrestimation while maintaining the
Theorem 4.6. If the reward distribution is Bernoulli, we can set the sampling distribution in Algorithm 7 as Beta posterior (t) 1, Ttt St(t) + 1), where S;(t) is the number of successes among the T, (t) plays of arm We denote the resulting algorithm as Bernoulli-TS. which enjoys the same regret bounds in Theorem 4.2
Agrawal and Goyal 3 proved that for Bernoulli rewards, Thompson sampling with Beta posterior is asymptotically optimal and has worst-case regret in the order of OlVKTlog T). Our regret analysis improves the worst-case regret to O(VKT'og K). They also proved that Gaussian-TS applied to the Bernoulli reward setting has regret O(VKT KT log K). However, no asymptotic regret was guaranteed in this setting.
Minimax Optimal Thompson Sampling for Exponential Family Rewards
In this section, in order to remove the extra logarithm term in the worst-case regret of ExpTS, we introduce a new sampling distribution that adds a greedy exploration step to the sampling distribution used in ExpTSS. Specifically, the new algorithm ExpTS* is the same as ExpTS but uses new sampling distribution p+ (1, n). A sample is generated from p+ (n, n) in the following way: = μ with probability 1 1/K and 0 ~ P(H, n) with probability 1/K.
Over-Estimation of Sub-Spuppoo Optt---p Arms. We first elaborate the over-estimation issue of sub-optimal arms, which results in the extra vlog K term in the worst-case regret of Thompson sampling. To explain, suppose that the sample of each arm has a probability p P(B((t) Z (t)) to become larger than the sample of arm 1. Note that when this event happens, the algorithm chooses the wrong arm and thus incurs a regret. Intuitively, the probability of making a mistake will be K - times larger due to the union bound over K 1 sub-optimal arms, which leads to an additional vlog K factor in the corst-case regret. To reduce the probability P(O, (1) 2 (1)). ExpTS* adds a greedy step that chooses the ExpTS sample with probability 1/K and chooses the arm with the largest

---

empirical average reward with probability 1 1/K. Then we can prove that for sufficiently large with high probability we have Ais 8 (t) and in this case it holds that ((),(t) 2 0 (t)) = P/K. K. Thus the extra factor vlog K in regret is removed.
In specifie, we have the following theorem showing that ExpTS* is asymptotically optimal and minimax optimal simultancously.
Theorem 5.1. Let bn
(n- -1)nn.
There exists constant C
0 such that ExpTS* satisfies
K (T) S Ci E VVKT)
(T) T-30 log T
R
K
A
and
lim
kl MI)
This is the first time that the Thompson sampling algorithm achieves the minimax and asymptotically optimal regret for exponential family of reward distributions. Moreover, ExpTS* is also an anytime algorithm since it does not need to know the horizon T in advance.
Remark 5.2 SSub-Gaussial Rewards). In the proof of Theorem 5.1 we do not need the strict form of
the PDF of the empirical mean reward fise but only need the maximal inequality (LemmaHH.) This means that the proof can be straightforwardy extended to sub- Gaussian reward distributions, where similar maximal inequality holds f21y.
It is worth noting that MOTS proposed by (20) (Thompson sampling with a clipped Gaussian posterior) also achieves the minimax optimal regret for nub-Gaussian rewards, but it can not keep the asymptotic optimality simultaneously with the same algorithm parameters. In particular, to achieve the minimax optimality, MOTS will have an additional p in the asymptolic regret with O < p < 1. Moreover, different from ExpTSt, MOTS is only designed for thus is not an anytime algorithm.
for fixed T setting and
we can derive new algorithms Gaussian-TS- and Bernoulli-TS* for Gaussian and Bernoulli rewards by replacing the sampling distribution in Exp'T'S. However, the posterior distribution does not fully satisfy the properties shown Section 4.2 In particular, the factor bn <. in Theorem 5.1 an essential requirement for the asymptotic analyses whereas the posterior distribution does not have this factor. Due these extra challenges, the proof techniques used for Theorem can can not be directly applied to these two new algorithms, and it is interesting to further investigate whether they are simultaneously minimax and asymptotically optimal.
Remark 5.3 (Gaussian and Bernoulli Rewards). Following the idea in Section 4.4
6 Conclusions
We studied Thompson sampling for exponential family of reward distributions. We proposed the ExpTS algorithm and proved it satisfies the sub-UCB criteria for problem-dependent finite-time regret, as well as achieves the asymptotic optimality and the minimax optimality up to factor of Vlog K for exponential family rewards. Furthermore, we proposed variant of ExpTS, dubbed ExpTS+. that adds a greedy exploration step to balance between the sample generated in ExpTS and the empirical mean reward for each arm. We proved that ExpTS* + is simultancously minimax and asymptotically optimal. We also extended our proof techniques to standard Thompson sampling with common posterior distributions and improved existing results. This work is mainly focused on the theoretical optimality of Thompson sampling type algorithms. It would be an interesting future direction to investigate the empirical performance of ExpTS and ExpTS*
Acknowledgement
We thank the anonymous reviewers and the area chair for their helpful comments. This research is supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: AISG-PhD/2021 1000022--1--00 -01-004[T]], by ASTAR, Singapore under Grant A19E3b0099, and by Bren Named Chair Professorship at Caltech. In particular, T. Jin is supported by the National Research Foundation, Singapore under its Al Singapore Programme (AISG Award No: AISG-PhD/2021-01 004(T]). X. Xiao is supported by ASTAR, Singapore under Grant A A1E330099, A. Anandkumar is partially supported by Bren Named Chair Professorship at Caltech. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
10

---

References
[1] Mare Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In Artificial Intelligence and Statistics, pages 176-184. PMLR, 2017. (p.5)
[2] Milton Abramowitz and Irene A Stegun. Handbook of mathematical functions with formulas, graphs, and mathematical tables, volume 55. US Government printing office, 1964. (pp. and 41
[3] Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pages 39-1, 2012. (pp. and 6
[4] Shipra Agrawal and Navin Goyal. Further optimal regret bounds for thompson sampling. In Artificial intelligence and statistics, pages 99-107, 2013. (pp. and
[5] Shipra Agrawal and Navin Goyal. Near-optimal regret bounds for thompson sampling. Journal of the ACM (JACM), 64(5):30, 2017. (pp.
and 29
[6] Jvan-Yves Audibert and Sébastien Bubeck. Minimax policies for adversarial and stochastic
bandits. In COLT, pages 217-226, 2009. (pp. 2 and
[7] Peter Auer and Ronald Ortner. Ucb revisited: Improved regret bounds for the stochastic multi-armed bandit problem. Periodica Muthematica Hungarica, 61(1-2):55-65, 2010. (p. (
[8] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(223): 256, 2002. (pp. and
(9] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal computing, 32(1):48-777 77, 2002. (p-
[10] Jie Bian and Kwang-Sung Jun. Maillard sampling: Boltzmann exploration done optimally. arXiv preprint arXiv: 100e22//1..3290 1.03290, 2021. (pp. 2 and 8
[11] Sébastien Bubeck and Che-Yo Yu Liu. Prior-free and prior-dependent regret bounds for thompson sampling. In Advances Neural Information Processing Systems, pages 638-646, 2013. (pp. and
[12] Olivier Cappé, Aurélien Garivier, Odalric-Ambrym Maillard, Rémi Munos, and Gilles Stoltz. Kullback-leibler upper confidence bounds for optimal sequential allocation. The Annals of
Statistics, pages 1546-1541, 2013. (pp. and
[13] Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In Advances in neural information processing systems, pages 2249-2257, 2011. (p. 2
[14] Rémy Degenne and Vianney Perchet. Anytime optimal algorithms in stochastic multi-armed bandits. In International Conference on Machine Learning, pages 1587-1595. PMLR, 2016.
(pp.
and 8
[15] Aurélien Garivier and Olivier Cappé. The kl-ucb algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference on learning theory, pages 359-376, 2011.
(pp. and 5
[16] Aurélien Garivier, Hédi Hadiji, Pierre Menard, and Gilles Stoltz. Kl-ucb-switch: optimal regret bounds for stochastic bandits from both deserebutioonddeeedeett and a distribution-free viewpoints. arXiv preprint arXiv: 180.05507, 2018. (pp. [)
[17] Peter Harremoös. Bounds on tail probabilities in exponential families. arXiv preprint arXiv:1601.05179 2016. (pp. and
[18] Emil Jeřábek. Dual weak pigeonhole principle, boolean complexity, and derandomization. Annals of Pure and Applied Logic, 129(1-3):1-37, 2004. (pp. 6and
and
[19] Tianyuan Jin, Jing Tang, Pan Xu, Keke Huang, Xiaokui Xiao, and Quanquan Gu. Almost optimal anytime algorithm for batched multi-armed bandits. In International Conference on Machine Learning, pages 5065-5073. PMLR, 2021. (p.
11

---

[20] Tianyuan Jin, Pan Xu, Jieming Shi, Xiaokui Xiao, and Quanquan Gu. MOTS: Minimax Optimal Thompson Sampling. In International Conference on Machine Learning, pages 5074-5083
PMLR, 2021. (pp. 3 6
and T0
[21] Tianyuan Jin, Pan Xu, Xiaokui Xiao, and Quanquan Gu. Double explore-the--oomiit Asymp- totic optimality and beyond. In Conference on Learning Theory, pages 2021. (pp. and T0]
PMLR,
[22] Emilie Kaufmann. On bayesian index policies for sequential resource allocation. arXiv preprint arXiv: 190, 2016. (pp. aadd4)
[23] Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. International conference on algorithmic learning theory, pages 199-213. Springer, 2012. (p.4)
[24] Wonyoung Kim, Gi-soo Kim, and Myunghee Cho Paik. Doubly robust thompson sampling with linear payoffs. Advances in Neural Information Processing Systems, 34, 2021. (p. 5
[25] Nathaniel Korda, Emilie Kaufmann, and Remi Munos. Thompson sampling for 1-dimensional exponential family bandits. In Advances in neural information processing systems, pages 1 1448- 1456, 2013. (pp.
1456,
and 8
[26] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Ad- vances in applied muthematics, 6(1):4 22, 1985. (pp. and 5
[27] Tor Lattimore. Optimally confident ucb: Improved regret for finite-armed bandits. arXiv preprint arXiv: 1507. 078800 2015. (p.
[28] Tor Lattimore. Regret analysis of the finite-horizon gittins index strategy for multi-armed bandits. In Conference on Learning Theory, pages 1214-1245, 2016. (pp. and
[29] Tor Lattimore. Refining the confidence level for optimistic bandit strategies. The Journal of Machine Learning Research, 19(1):765-796, 2018. (pp. and X
[30] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
(pp.
and I6]
[31] Odalric-Ambry Maillard, Rémi Munos, and Gilles Stoltz. A finite-time analysis of multi- armed bandits problems with kullback-leibler divergences. In Proceedings of the 24th annual Conference On Learning Theory, pages 497-514, 2011. (p.
[32] Pierre Ménard and Aurélien Garivier. minimax and asymptotically optimal algorithm for stochastic bandits. In International Conference on Algorithmic Learning Theory, pages 223-237- 2017. (pp-
and
[33] Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics 2014. (pp. and
of Operations Research,
[34] Siwei Wang and Wei Chen. Thompson sampling for combinatorial Conference on Machine Learning, pages
In International
2018. (p-
[35] Pan Xu, Hongkai Zheng, Eric V Mazumdar, Kamyar Azizzadenesheli, and Animashree Anand- kumar. Langevin monte carlo for contextual bandits. In International Conference on Machine Learning, pages 24830-24850. PMLR, 2022. ())
[36] Tong Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning. arXiv preprint 10000221 2021. (p. 5)
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] All the proofs are provided in the appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "n1ODPTzG0C", "reviewer": "Reviewer_mKp1", "summary": "This work studies the regret of Thompson sampling (TS) for exponential family reward distributed multi-armed bandits, by addressing all its theoretical properties.\n\nAfter a careful summary of their work, an informative related work Section 2 and necessary preliminaries in Section 3, the authors argue in Section 4.1. that the existing finite-time regret TS analysis based on the under-estimation of the optimal arm can be improved by introducing a lower confidence bound on such under-estimation.\n\nTo that end, they present a new decomposition of the regret that allows for a new approach to algorithm analysis and design. Specifically, they propose in Section 4.2 a sampling distribution that results in a variant of TS (denoted Exp-TS), with its subsequent frequentist regret analysis provided in Section 4.3.\n\nThe analysis simultaneously yields both the finite-time regret bound and the asymptotic regret bound: they prove that Exp-TS is the first algorithm to achieve the sub-UCB criteria, asymptotic optimality, and minimax optimality simultaneously for exponential family reward distributions.\n\nIn addition, they are able to show that when the exponential reward distribution has a closed form (e.g., Gaussian and Bernoulli), the posteriors in standard Thompson sampling relate to the proposed sampling distribution and therefore, obey asymptotic and finite-time regrets as well.\n\nFinally, they introduce in Section 5 a new sampling distribution that adds a greedy exploration step to the sampling distribution used in ExpTS to remove the extra logarithm term in the worst-case regret of ExpTS, and show that this new algorithm ExpTS$^+$ is minimax optimal. To do so, a procedure to mitigate the over-estimation of sub-optimal arms is proposed. ", "questions": "The authors claim that the proposed sampling distribution in Equation 4.3 \"_seems complicated for a general exponential family reward distribution, even though they only need the sampling distribution to satisfy a nice tail bound derived from this reward distribution._\" Given that they show in Section 4.4. that usual conjugate priors in Gaussian and Bernoulli distributed rewards do meet such requirements, could the authors discuss what priors (or which properties of the priors) on other exponential-family rewards would meet the necessary distribution requirements?  ", "limitations": "Given the theoretical nature of this work, there is minimal immediate impact on society, and limitations are somehow implicit in the modeling and theoretical assumptions.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work is very relevant as it studies a rich family of bandit reward distributions, i.e., the exponential family of distributions that covers commonly used ones (Bernoulli, Gaussian, Gamma, and Exponential).\n\nThe novelty and significance of this work's contributions are:\n\n- A proof that ExpTS is an algorithm that, for exponential family of reward distributions, achieves the sub-UCB criteria, and is simultaneously minimax optimal (up to a factor of $\\sqrt{log K})$ and asymptotically optimal. In addition, they show how a greedy extension of ExpTS is actually able to remove the extra $\\sqrt{log K}$ minimax optimality factor. \n\n- A novel proof that both TS with Gaussian rewards and Gaussian posteriors, and Bernoulli rewards with Beta posteriors, are asymptotically optimal and minimax optimal up to a factor of $\\sqrt{log K}$\n\n- A novel, yet conceptually simple set of techniques, to analyze not only the frequentist regret of existing algorithms, but to also enable the proposal and analysis of new algorithms. Specifically, a regret decomposition that is conditioned on a lower confidence bound introduced in Equation 4.2", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "lfkJ4IcvrBc", "reviewer": "Reviewer_vJ2N", "summary": "The paper contributes to the growing body of works, where new `optimistic' TS algorithms are designed with sampling distributions that are updated in a non-Bayesian fashion but yields better regret bounds. This paper presents two variations of the Thompson Sampling (TS) algorithm ExpTS and ExpTS$^+$ to solve a K-armed bandit problem. Instead of considering the Bayesian posterior as the sampling distribution, they construct a new sampling distribution that is updated using past rewards and the number of trials for each arm. The sampling distribution in ExpTS is designed to avoid the under-estimation of the optimal arm and over-estimation of the sub-optimal arms. ExpTS$^+$ is like ExpTS but with a greedy step to choose an action from ExpTS. Under the assumption that the rewards are modeled as a distribution from the exponential family of distributions with finite variance, they are able to show that the frequentist regret bound of\n1. ExpTS is asymptotically optimal, sub-UCB, and minimax optimal up to a factor of  $\\sqrt{\\log K}$, and\n2. ExpTS$^+$  is minimax optimal and asymptotically optimal. \nMoreover, the author improves upon the existing regret bounds for Beta-Bernoulli and Gaussian-Gaussian bandits with their new regret decomposition.", "questions": "Major:\n79 -It is not clear what is making ExpTS+ minimax optimal but not sub-UCB. Please elaborate with more clarity.\n\nTable 1: Incorrect row 2 (refer Theorem 1.2 in [1] )\n\n94-97: Are these lines correct? The lower bound for TS for Gaussian reward ($O(\\sqrt{KT\\log K})$) was already established in Theorem 1.4 in [1] (and [2]). \n\n135-136- The statement is confusing. One cannot have Gaussian posterior with a Bernoulli reward.\n\nA.3: I didn't follow the second inequality in A.3. Why there is T in the denominator of the first expression? Please elaborate.\n\n528:  I am not sure, I followed the argument here. Please elaborate \n\nA.7:  How the first term in the third inequality is bounded by $V/\\epsilon^2$ and the second term is bounded by the second term in the 4th inequality using 3.3. Please elaborate.\n\n571: I don't think I follow the inequality described here to prove A18.\n\nMinor:\n\n116: Asymptotic - > Asymptotically\n\n130: Beta not beta\n\n146: measure 'of' $p(\\theta)$ as ..\n\n299: :loose\n\n\nRef..\n[1]. Shipra Agrawal and Navin Goyal. Near-optimal regret bounds for Thompson sampling. Journal of the ACM (JACM), 64(5):30, 2017.", "limitations": "The authors briefly address some of the limitations of their work in the conclusion. ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. I think the paper is well-written, and the ideas presented are novel and clearly described. In particular, the authors explain the importance of their approach and analysis in Sec. 4.1 and the second para. of Sec. 5.\n2. The construction of the sampling distribution (in sec 4.2) with all the nice properties is novel and the key contribution of this paper.\n3. The author improves upon the existing regret bounds for Beta-Bernoulli and Gaussian-Gaussian bandits with their new regret decomposition.\n4. The proofs in the Appendix A are structured well and looks correct to me, however the authors may address some of my question to enhance clarity. (The length of the paper (including Appendices with proofs) is too long to review for a conference paper.)\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "LNw3ONc3p1B", "reviewer": "Reviewer_XukM", "summary": "This paper considers stochastic sampling in the multi-armed bandit problem. This problem involves K arms and the goal of the algorithm is to draw the arm of the largest mean as many times as possible. A class of algorithms called Thompson sampling, which conducts a greedy assuming that the posterior is correct, is known to be efficient. This paper considers a version of Thompson sampling with an incorrect posterior. \n\nTo argue the advantages of the proposed algorithm, this paper considers three criteria for good algorithms. Namely, \n* Asymptotic optimality  \n* Finite-time guarantee (sub-UCB, minimax)\n* anytime algorithm\n\nThe proposed algorithm ExpTS is described in Table 1, which samples from the posterior based on a distribution that is inspired by the large deviation asymptotics (4.3). ExpTS+ is a version of ExpTS that mixes greedy and ExpTS. \n\nClass of distributions:\nThis paper considers a one-parameter exponential family distribution (if I understand correctly, the setting is the same as [Cappe et al. 2013]).\n\n[Cappe et al. 2013] \"Kullback-Leibler upper confidence bounds for optimal sequential allocation\" Olivier Cappe, Aurelien Garivier, Odalric-Ambrym Maillard, Remi Munos, Gilles Stoltz\n\nThe paper is well-written. In my view, there are several issues in this paper that I discuss below. In particular, some of the setup and terms are different from the ones generally used in the community (and wrong in some ways). Besides, the algorithm modifies the posterior without addressing the corresponding anti-concentration of the original TS, which does not contribute to the understanding of the Thompson sampling itself. Given these, I think the paper requires some revision.\n\nIssues \n* Incorrect mathematical definition: I guess \"finite-time\" is used in a wrong way. If I understand correctly, sub-UCB (1.2) bound and O(\\sqrt{KT}) regret bounds are not finite-time (Landau notation is asymptotic). Usually finite-time analysis refers to the bound where all the terms are explicitly written as functions of model parameters. Moreover, I do not think most (all?) of TS analysis does not have a sub-UCB bound in the sense of (1.2). For example, if there is a term that is 1/Delta_i^2, then it is not sub-UCB because it diverges faster than (1.2) when we fix T and takes a small Delta). \n* The tradeoff relation is not very clear: the asymptotic rate on the top of log T is different in (1.1) and (1.2), which are not in a tradeoff relation. A more natural bound is a finite-time version of (1.1). There may be a tradeoff between minimax regret and the relative-divergence bound of (1.1).\n* Comparison with existing results: [23] consider TS for 1-parameter exponential family and showed its asymptotical optimality (which I think is one of the closest papers to this). They stated that \"Our result is asymptotic, but the only stage where the constants are not explicitly derivable from knowledge of F, T , and θ0 is in Lemma 9.\" I guess this bound is from a limited understanding of the anti-concentration property of TS. Authors should mention whether this bound can be made finite-time or if there need a modification such as ExpTS that is targeted to improve the anti-concentration property.\n* No simulation: The computational aspect of the proposed algorithm is not mentioned (nor simulations), which limits the utility of the proposed algorithm. The sampling method from the distribution is mentioned (L258-L266) and it looks like the simulation is doable.\n\n## At the end of the discussion phase:\n\nA least agreement is that the minimax optimality is the most important part of this paper. I still think there are many concerns remain in the current version of paper, which I write in the following.\n\nFor clarification, the most relevant papers are (references are current version)\n* [25] \"Thompson sampling for 1-dimensional exponential family bandits.\" Korda et al. -> Asymptotic optimality of Thompson sampling for 1-dim exponential family\n* [20] \"MOTS: Minimax Optimal Thompson Sampling\" Jin et al. -> Asymptotic + minimax optimality of a version of TS for Gaussian bandits\n* [5] \"Near-optimal regret bounds for Thompson sampling\" Agrawal et al. -> TS is not minimax optimal up to $\\sqrt{\\log K}$\n\nGiven these results, the novelty of this paper is\n* A version of TS, applicable to V-bounded 1-dim exponential family that is asymototical+minimax optimal\n* Finite-time (+ sub-UCB) analysis of it.\n\nI consider the contributions are incremental given such an asymptotical analysis is already known in [25] for TS and minimax improvement is previously done in [20] for Gaussian by \"inflating\" posterior just like this paper, but it is okay if it were properly presented and complemented by experimental results. \n\nFor me, there remain concerns on the paper. Major ones of them are as follows. \n\n* Confusion on the analysis and performance of the algorithm: Table 1 is ill-defined if I understand each notion correctly. The authors place \"Minimax Ratio\" and \"Sub-UCB\" (even though these are defined in terms of asymptotics) inside \"Finite-Time Regret\". In fact, this is not even a comparison of algorithms. Finite-time or asymptotic is the property of *an analysis* (i.e., giving all constants explicitly or not), whereas all other properties are of *an algorithm*. \n\n* Limited characterization of the minimax property. [5] considers a misspecified instance where the rewards are fixed rather than drawn from the anticipated distributions, so this is not a lower bound in the true sense. A bit larger bound of $O(\\sqrt{KT \\log T})$ derived from the process of upper-bounding the regret; the remark \"L223: using Gaussian posteriors will unavoidably suffer\nfrom the lower bound of $\\Omega(\\sqrt{KT \\log T})$\" needs a fix (this is not a lower bound).\n\n* No simulations are provided: p2 motivates the finite-time sub-UCB bound is important in the practical value of $T$, but there is no simulation provided even though \"We show that sampling from P is tractable (Line 277)\". I think deriving a minimax example where this algorithm is expected to shine is easy ($\\mu_1 = \\sqrt{K/T}, \\mu_2-\\mu_K = 0$?). \n\n* Possibly no tradeoffs. They consider \"there is a tradeoff between minimax optimal regret and sub-UCB regret\" but open. If I understand correctly, if there is a tradeoff between $A$ and $B$, then $A \\cap B = \\emptyset$ (or show some evidence that $A \\cap B$ is unlikely). If it is open then it is not a tradeoff. Regarding the boundedness of $V$, their explanation does not make sense at least for the exponential distribution. \n\n* Lack of comparison on the existing theoretical results: Limited discussion on connecting the results with relevant papers. Regarding whether the finite-time analysis of TS can be done for [25] (only single term is asymptotic in [25]), they commented \"The idea of [25] is totally different from ours.\" and did not provide any discussion on the most closely related paper. During the answer A9 (optimal algorithm for 1-parameter exponential family), they did not aware of existing literature in 2015.", "questions": "* Does the original TS has plausible anti-concentration? Lemma 9 in [23] is essentially unremovable (which motivates the introduction of ExpTS) or not? Do ExpTS and original TS match for some limit?\n* Tradeoff relation: Among the properties considered in this paper (asymptotic optimality, finite-time bounds, anytime property), which of them are in the tradeoff relations? \n* How well ExpTS perform in practice (with some synthetic/real data simulations)?\n\n* Is there any reason that one cannot demonstrate the same rate as the asymptotic rate?\n>L227: In this paper, we study the general exponential family of reward distribution, which has no closed form. Thus we cannot obtain a tight concentration bound for µˆ1s as in special cases such as Gaussian or Bernoulli rewards. \n* I think having closed form is not directly related to the tightness of the concentration inequality. (probably the author cannot derive the concentration inequality of KL-divergence rate for some hardness)", "limitations": "* Ethically sound.\n* No simulations on the performance of the proposed method.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n* Algorithm and related analysis: Showed that sampling from a (mock-)posterior can achieve optimality as well as finite-time exponential concentration, not only Bernoulli and Gaussian but also some class of exponential family.\n* Minimax optimality: Discussion on minimax regret of TS for exponential distribution bandits\n\nWeaknesses\n* Characterization needs some fix\n* Limited contribution to the understanding of TS for exponential bandits, on top of related work [18,23].\n* Some gap between what the community wants and what this paper has done", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HXI2nVfYFgz", "reviewer": "Reviewer_vJHc", "summary": "The paper proposes a new Thompson sampling algorithm by designing proper sampling distributions for exponential family reward distributions. Three contributions: (1) new algorithm (2) showing that the standard TS enjoys a $\\sqrt{\\log(K)}$ minimax ratio (without inflating the posterior distribution) and (3) a simple greedy trick to achieve a constant minimax ratio.", "questions": "* L168: missing a square for (mu-mu')\n* L169-170: I did not follow why we are setting V(.) = 1/4. I mean, we don't get to choose V(.); it is given from the definition of a specific exponential family distribution?\n* L209-210: I would remove the word 'a regret' there since it sounds like it is about the regret lower bound rather than the lower bound on $D_i$.\n  * Furthermore, looking into Lemma 5 of Jin et al., it seems that D_i = \\Omega(\\sqrt{KT\\log(T)}) is not correct (and rather a typo). It seems we need to say K D_i = \\Omega(\\sqrt{KT\\log(T)}) ?\n* It'd be great to have a figure showing plots of PDFs for the sample distribution.\n* what's the role of b_n? Anything goes wrong if we set $b_n=1$\n* How does the empirical performance of ExpTS fair with TS? \n* L254: \"when n is large, we will choose b_n to be close to 0\" ⇒ this contradicts to b_n in Theorem 4.1?\n* L276-277: to claim that ExpTS is comparable to the best known UCB, we need to define the scope. For Gaussian rewards, AdaUCB has a strictly better guarantee than ExpTS.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: high\n\nQuality: high\n\nClarity: high\n\nSignificant: medium-high\n\nThe key contribution, to me, is the novel analysis described around Eq 4.2. In fact, proving/disproving that the standard Thompson sampling (without inflating the posterior distribution, which breaks the asymptotic optimality) has the minimax rate of $O(\\sqrt{\\log(K)})$ was an open problem. Note Agrawal & Goyal (2017) have shown this rate with Gaussian TS but they in fact inflate the posterior variance by a constant factor. \n\nOn clarity, I appreciate that the authors point out specific section/formula numbers from the references; not many people do this these days.\n\nWhile the sampling distribution is novel, I am not entirely convinced that it is necessary, but at least it is a nice addition to the library of variations of TS. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept