Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling
Authors: Aadirupa Saha
Branislav Kveton
Venue: ICLR 2024 poster (2024)
Keywords: Thompson Sampling
Multiarmed
Bandits
Gaussian
Gamma
MAB
Variance aware
Regret
Prior
Posterior
Bayesian
Tight
Guarantee
Empirical
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We address the problem of Gaussian MAB with unknown heterogeneous reward noise. We are the first to design a TS algorithm for this setting with near-optimal variance-aware regret. It is efficient, theoretically sound, and empirically competitive.

Abstract: Most bandit algorithms assume that the reward variances or their upper bounds are known, and that they are the same for all arms. This naturally leads to suboptimal performance and higher regret due to variance overestimation. On the other hand, underestimated reward variances may lead to linear regret due to committing early to a suboptimal arm. This motivated prior works on variance-adaptive frequentist algorithms, which have strong instance-dependent regret bounds but cannot incorporate prior knowledge on reward variances. We lay foundations for the Bayesian setting, which incorporates prior knowledge. This results in lower regret in practice, since the prior is used in the algorithm design, and also improved regret guarantees. Specifically, we study Gaussian bandits with \emph{unknown heterogeneous reward variances} and develop a Thompson sampling algorithm with prior-dependent Bayes regret bounds. We achieve lower regret with lower reward variances and more informative priors on them, which is precisely why we pay only for what is uncertain. This is the first such result in the bandit literature. Finally, we corroborate our theory with experiments, which demonstrate the benefit of our variance-adaptive Bayesian algorithm over prior frequentist works. We also show that our approach is robust to model misspecification and can be applied with estimated priors.

Published as a conference paper at ICLR 2024
ONLY PAY FOR WHAT IS UNCERTAIN: VARIANCE-ADAPTIVG THOMPSON SAMPLING
Aadirupa ;aha'; Branislav Kveton² Apple, 2 Amazon
ABSTRACT
Most bandit algorithms assume that the reward variances their upper bounds are known, and that they are the same for all arms. This naturally leads to suboptimal performance and higher regret due to variance overestimation. On the other hand, underestimated reward variances may lead to linear regret due to committing early suboptimal arm. This motivated prior works on variance-adaptive frequentist algorithms, which have strong instance- porate prior knowledge on reward variances. We lay foundations for the Bayesian setting. which incorporates prior knowledge. This results in lower regret in practice, since the prior is used the algorithm design, and also improved regret guarantees. Specifically, we study Gaussian bandits with unknown helerogeneous reward vari- ances and develop a Thompson sampling algorithm with prior-dependent Bayes regret bounds. We achieve lower regret with lower reward variances and more informative priors on them, which is precisely why we pay only for what is uncer- tain. This is the first such result in the bandit literature. Finally, theory with experiments, which demonstrate the benefit of our variance-an addapiv Bayesian algorithm over prior frequentist works. We also show that our approach is robust to model misspecification and can be applied with estimated priors.
regret bounds but cannot incor-
corroborate our
INTRODUCTION
stochastic bandit (Lai & Robbins 1985 Auer et al. 2002 Lattimore & Szepesvári 2020) is an online learning problem where a learning agent sequentially interacts with an environment over n rounds. In each round, the agent pulls an arm and receives a stochastic reward. The mean rewards of the arms are initially unknown and the agent learns them by pulling the arms. Therefore, the agent faces an
dilemma: explore, and learn more about the arms by pulling them; or exploit, and commit to the arm with the highest estimated reward. An example of this setting is recommender system, where the arm is a recommendation and the reward is a click.
Most bandit algorithms assume that the reward variance or its upper bound is known. For instance, the confidence intervals in UCB1 (Auer et al. 2002) are derived under the assumption that the rewards [0, 1]. and hence su-su--Gansia for 0.5. In Bernoulli KL-UCB (Garivier & Cappe 2011 and Thompson sampling (TS) (Agrawal & Goyal 2012), tighter confidence intervals are derived for Bernoulli rewards. Specifically, Bernoulli random variable with either low or high mean also has a low variance. In general, the reward variance may be hard to specify (Audibert et al.) (2099)). While overestimating is typically safe, this decreases the learning rate of the bandit algorithm and thus increases its regret. On the other hand, when the variance is underestimated, this may lead to linear regret because the algorithm can commit to an arm without sufficient evidence.
We motivate learning of reward variances by the following example. Take a movie recommender that learns to recommend highest rated movies in a "Trending Now" carousel. The movies are rated on scale [1, 5J. Some movies, such as The Godfather, are classics. Therefore, their ratings are high on average and have low variance. On the other hand, ratings of low-budget movies are often low on average and have low variance, due to the quality of the presentation. Finally, most movies are made for a specific audience, such as Star Wars, and thus have high variance in ratings. Clearly, any
"Correponniigg email: aadi rupa. saha@gma com

---

Published as a conference paper at ICLR 2024
sensible learning algorithm would require fewer queries to estimate the mean ratings of movies with low variances. Since the variance is unknown priori, adaptation is necessary. This would reduce the overall query complexity and improve statistical efficiency-ar as one should- we only pay for what is uncertain. This example is not limited to movies and applies to other domains, such as online shopping. Our work answers the following questions in affirmative:
Can we quickly learn the right representation of the reward distribution for efficient learning? ? What is the right dependence of the learner's performance (regret) versus the prior parameters and reward variances? Can we design an algorithm to achieve that rate? Does the regret decrease with lower reward variances and more informative priors on them?
Unknown reward variances are major concern and thus have been studied extensively. In the cumu- lative regret setting, AAudibert et al. (2009b) proposed an algorithm based on upper confidence bounds (UCBs) and Mukherjee et al. (2018) proposed an climination algorithm. In best-arm identification (BAD (Audibert et al.[2000b Bubeck et al. 2009). several papers studied the fixed-budget (Gabillon
et al.
2011| et al. 2020 [Saha et al. 2020 Lalitha al. 2023) and fixed-confidence (Lu et al.
2021
Zhou & Tian 2022 Jourdan et al. 2022) settings with unknown reward variances. All above
works studied frequentist algorithms. On the other hand, Bayesian algorithms based on posterior
sampling (Thompson] 1933 Chapelle & Li 2011: Agrawal & Goyal 2012 Russo & Van Roy 2014
Russo et al.) 2018: Kveton al.] [021] Hong al. 2022b) perform well in practice, but learning of
reward variances in these algorithms is understudied.
We consider the Bayesian setting (Russo & Van Roy 2014 and introduce it in detail in Section 3 This is because Bayesian algorithms are very practical (Chapelle& & Li| 2011 Russo et al. 2018 Kveton
jt al. 202T) and Bayesian analyses are the only bandit analyses that can capture the dependence on prior (Russo& & Van Roy 2016 Lu & Van Roy] 2019: Hong et al. 2022b a). More specifically, as the
prior becomes more informative, Bayes regret bounds go to zero, and so does the Bayes regret of Thompson sampling. Frequentist regret bounds do not have this behavior because they are proved for any bandit instance, which is unrelated to the prior in the bandit algorithm (Agrawal & Goyal 2012) 2013b). In fact, all frequentist regret bounds for Bayesian algorithms assumee sufficiently which is analogous to being uninformative. Taking an expectation of frequentist regret bounds over instances sampled from the prior does not yield the right dependence the prior. In our experiments, we show that as the prior becomes more informative, our bounds become tighter than the frequentist bounds. This shows the benefit of Bayesian analyses.
prior,
Bayesian analyses have two shortcomings. First, they are on average over bandit instances sampled from the prior. This relates the bandit instances to the prior in the bandit algorithm and allows prior-dependent analysis. Second, to derive closed-form posteriors and use them in the analysis, modeling assumptions are needed. In our work, we assume Gaussian noise, which less general than the sub-Gan Gaussian noise that is typically used in frequentist analyses (Abbasi- Yadkori et al. 2011). Our contributions are summarized next.
Contributions:
(1) To warm up, we start with Thompson sampling in a K-armed Gaussian bandit with known heterogeneous reward variances (Section f Its regret bound (Theorem [ decreases as reward variances decrease. It also approaches zero as the prior variances of mean arm rewards go to zero, since a Bayesian learning agent knows the bandit instance with certainty in this case. (2) We propose Thompson sampling algorithm VarTs for a K K-armed Gaussian bandit with unknown heterogeneous reward variances (Section 55. VarTS maintains a joint Gaussian -aaussian-Gaamaa posterior for the mean and precision of the rewards of all arms and samples from it in each round. (3) We prove Bayes regret bound for VarTS (Theorem 2). which decreases with lower reward variances and more informative priors on them. This is the first such regret bound. The novelty in our analysis is in handling random confidence interval widths due to random reward variances. The bound captures the same trade-offs as if the variance was known, replaced by the corresponding dependee quantities. (4) We evaluate VarTS on various types of reward distributions, from Bernoulli to beta to Gaussian (Section 6). Our evaluation shows that VarTS outperforms all existing baselines, even with an estimated prior. This showcases the generality and robustness of our method.
2 RELATED WORK
Classic K-armed bandits have been studied for over three decades (Lai & Robbins 1985 Lai 1987)
Two popular techniques for solving these problems are UCBs Auur 2002 Audibert et al. 2009a
2

---

Published as a conference paper at ICLR 2024
Ménard & Garivier 2017) and Thompson sampling (Thompson 1933 Agrawal & Goyal 2012
Bubeck & Liu| 2013). Recent works on TS matched the minimax optimal rate in K Karrmed bandits
(Jin et all 2021]. Vin et al. (2023) designed a minimax and asymptotically optimal TS. Improved TS
algorithms for combinatorial bandits and semi-bandits have also been proposed (Perrault et al. 2020
Perrault 2022). The focus of our work is TS that adapts unknown reward variances.
The beginnings of variance- aadantiv algorithms can be traced to Auer et al. (2022) Auer et al. 2002) proposed a variance-adaptive UCB1 for Gaussian bandits, called UCB1-Normal, where the reward distribution of arm i is N (pss of) and o; >> O is known by the learning agent. The n-round regret of
this algorithm is O [Eipe of
A: log n where A; - Pa- - A4 is the gap of arm and a" is the arm with the highest mean reward μug The first UCB algorithm for unknown reward variances with an analysis was UCB-V by Audibert et al. (2009b). The key idea in the algorithm is to design high- probability confidence intervals based on empirical Bernstein bounds. The n-round regret of UCB-V is O EEipeenn
( + +b) logn) where is upper bound the absolute value of rewards. In summary, variance adaptation in UCB-V incurs only a small penalty of Obk log n). Mukherjee et al. (2018) proposed an elimination- based variant of UCB-V that attains the optimal gap-free regret of O(VKn) While empirical Bernstein bounds are general, they tend to be conservative in practice. This was observed by Garivier & Cappe (2011) and we observe the same trend in our experiments (Section 6 Our work can be viewed as a similar development to UCB-V in Thompson sampling. We show that Thompson sampling with unknown reward variances (Section (5) incurs only a slightly higher regret than the one with known variances (Section 4.. by a multiplicative factor. Compared to UCB-V, the algorithm is highly practical.
Two closest papers to our work are Honda & Takemura (2014); Zhu & Tan (020). Both papers propose variance-adaption Thompson sampling and bound its regret. There are three key differences from our work. First, the algorithms Honda & Takemura (2014): & Tan 2020) are designed for the frequentist setting. Specifically, they have fixed sufficiently- prior and enjoy per-instance regret bound under this prior. While this is a strong guarantee, the algorithms can perform poorly when priors are narrower and thus more informative. Truly Bayesian algorithm designs, proposed in our work, can be analyzed for any informative prior. Second, the analyses Honda & Takemura (2014); Zhu & Tan ) are frequentist. Therefore, they cannot justify the use of more informative priors. We prove regret bounds that decrease with lower reward variances and more informative priors on them. Finally, the regret bounds of Honda & Takemura (2014); Zhu & Tan (2020) are asymptotic. We provide strong finite-time guarantees. We discuss these difference in more detail after Theorem and demonstrate them empirically in Section 6
Another line of related works are variance-dependen regret bounds for d-dimensional linear con- textual bandits (Kim et al. 2022, Zhao et al. 2022 2023; Zhang et al. 2021). These works address the problem of time dependent variance adaptivity. They derive frequentist regret bounds that scale as (Ipoly(d)//1+ Ex= ).), where of is unknown reward variance in round t. This setting is different from ours in two aspects. First, the reward variances change over time but are fixed across the arms. We do the opposite in our work. Second, their algorithm designs and analyses frequentist, and thus do not exploit prior knowledge. On the other hand, we focus only on K Karmed bandits, which is a special case of linear bandits.
3 PROBLEM SETUP
Notation. The set {l...., n. is denoted by [n]. The indicator 1 {E} denotes that event E occurs. We use boldface letters to denote vectors. For any vector v E TRd,, we denote its i-th entry by o; or v(i.. We denote the entry-wise square of v by v². A diagonal matrix with entries v is diag (v). Ô is the big notation up to polylogarithmic factors. Gaussian, Gamma, and Gaussian Gamma distributions are denoted by A. Gam, and NG. respectively. For any random variables X and Y, we abbreviate [ X, Y] X] as E E x].
Setting. A bandit instance is pair of mean arm rewards and reward variances, (μ, o²), where f E TR. K a vector of mean arm rewards, 2² e TR a vector of reward variances, and K is the number of arms. We propose algorithms and analyze them for both when the reward variances o² are known (Section 4 and unknown (Section
3

---

Published as a conference paper at ICLR 2024
Feedback model. The agent interacts with the bandit instance (11, o²) for rounds. In round t [n].
it pulls an arm and observes its stochastic reward. We denote the pulled arm in round by A₁ E [ stochastic reward vector of all arms in round by 2t E RK and the reward of arm E [K] by Te, E IR. The rewards are sampled from a Gaussian distribution, Zi,i ~ ((1,, of). The interactions of the agent up to round t are summarized by a history H, (A1, (A,,
Bayesian bandit setting. We consider Bayesian multi-armed bandit (Russo & Van Roy 2014 Russo et al. 2018 Kveton et al. 2021 Hong et al. 2022b) where the bandit instance is either fully or partially random:
(i). When reward variances are known (Section 4). the bandit instance (14, or) is generated as follows. The mean arm rewards are sampled from a Gaussian distribution, μe ~ Po = N (No, diag (oā) ). where 14g E R and of E IR are the prior means and variances of μa, respectively. Both obo and oî are assumed to be known by the agent. The reward variances ṭ² are also known.
(ii). When reward variances are unknown (Section 55. the bandit instance (It, or) is sampled from a Gaussian- Gamana prior. Specifically, for any arm the mean and variance of its rewards are sampled as (1is o; 2) ~ [G Ko,,, io 80,), where (Ho, Ko; Cig. 9b) are known prior parameters. This can also be seen as sampling o, Gam(ao, f0,3) and then μ4s ~ N N(Po,i: No. follows from the basic properties of the Coussian-Gamma distribution (Lemma 3 in Appendix).
< This equivalence
Regret. We measure the n-round Bayes regret of a learning agent with instance prior Po as:
R₂ E 1A11- [A,];
(1)
where A = arg [K] (4 is the optimal arm. The above expectation is over mean arm rewards μ drawn from the prior distribution, unlike in the frequentist setting where f would be unknown but fixed (Lattimore & Szepesvári] (020). The randomness in the expectation includes how the agent chooses A, and the randomness in bandit feedback A "N(A,,
We depart from the classic bandit setting (Auer et al. 2002 Abbasi-Yadkori al. 2011| Lattimore & Szzpesvári 2020) in two major ways. First, we consider Gaussian reward noise, as opposing to a more general sub- uub-Gaussian noise. The Gaussian noise and corresponding conjugate priors lead to closed-form posteriors in our algorithms and analyses, which simplifies them. This is why this choice has been popular in recent Bayesian analyses (Lu & Van Roy 2019 Kveton et al., 2021; Wan et al.] Hong et al. 2022b a) Second, our regret is Bayesian, on average over bandit instances. An alternative would be the frequentist regret, which holds for any bounded bandit instance. We choose the Bayes regret because it can capture the relation between the bandit instance and its prior, and thus show benefits of informative priors. We discuss this in depth throughout the paper, and especially after Theorem I and Theorem 2 To alleviate concerns about Gaussian posteriors in the algorithm design, we experiment with non- Gaussian bandit problems in Section
GAUSSIAN BANDIT WITH KNOWN VARIANCES
We start with the Bayesian setting with Gaussian rewards and known heterogeneous reward variances.
In [.1 we introduce Thompson sampling algorithm (Thompson) 1933 Chapelle & Li 2011) Agrawal & Goyal 2012) for this setting. Gaussian TS is straightforward and appeared in many prior We state and discuss its regret bound in Section 4.2
works, starting with Agrawal & Goyal 2013a).
The bound scales roughly as:
EK Vnlogn / log log (1+
One notable property of the bound is that it goes to zero when the reward variances of or the prior variances of the mean arm rewards o3, do. Although the bound is novel, proof mostly follows Kveton et al. (2021). We mainly state to contrast it with the main result in Section 5
4.1 GAUSSIAN THOMPSON SAMPLING
The key idea in our algorithm is to maintain a posterior distribution over the unknown mean arm rewards ja and act optimistically with respect samples from it. Since fe and its rewards are sampled
4

---

Published as a conference paper at ICLR 2024
from Gaussian distributions, the posterior is also Gaussian. Specifically, the posterior distribution of arm in round t is N ( (f,)) where Pe, and oi, are the posterior mean and variance, respectively, of arm in round t. These quantities are initialized as ur Mo, and 01, := 00,3-
Our algorithm is presented in Algorithm| (Appendixx A and we call Gaussian TS due to Gaussian rewards. The algorithm works as follows. In round t, it samples the mean reward of each arm i from its posterior, Pr,i ~ ( of,)) After that, the arm with the highest posterior-samples mean reward pulled, A, arg [ je, Finally, the algorithm observes stochastic reward of arm A,, It, (HA. ), and updates its posteriors (Lemma 7 in Appendix) as:
0 1414
2
1
/4415 ==
Bo.i
Ne+1 of
0,s + NN+11100
0.
where 12-1, = N.-1(1) Ex= 1(A, = i) a is the empirical mean reward of arm the beginning
of round t ++1 1 and No41 (i) is the number of its pulls. The complete pseudocode of Algorithm is given in Appendix AA]
4.2 REGRET ANALYSIS
Before analyzing Algorithm|] T we recall the setting again. The mean arm rewards are sampled from Gaussian prior, μ ~ Po = N (Ht. diag (oā)), ), where μ4 E R and of E R
K 20 are the prior means
and variances of μ., respectively. The reward of arm i in round t is sampled as Tt,; NN,,, of). Both do and oū. and reward variances o²² are fixed and known. Our regret bound is stated below. Theorem 1 (Variance-dependen regret bound for known variances). Consider the above setting. Then for any > the Bayes regret of Gaussian TS is bounded as:
K
K Σ of
R
nd + /2n
+ + nog (1og(1+no + log(1/8).
The complete proof of Theorem iss in Appendix We discuss the bound below.
Dependence on all parameters of interest and prior. For = 1/n, the bound in Theorem scales
roughly as Ô nn term Theorem 1 which order-wise dominated by the second term when 5 = 1/n. Our bound has several properties that discuss next. First, it matches the usual /n dependence of all classic Bayes regret bounds (Russo & Van Roy 2014 2016 Lu & Van Roy] 2019). Second, it increases with variances of of individual arm rewards, which is expected because higher reward variances make learning harder. Third, the bound can be viewed as a generalization of existing bounds that assume homogeneous reward variances. Specifically, Kveton et al. (2021) proved O(Vo2K')) Bayes regret bound in Lemma 4 under the assumption that the reward distribution of arm is (M1; ) We match it when a, for all arms i. Fourth, the bound approaches zero as 0o -> 0. In this setting, Gaussian TS knows the mean arm rewards almost with certainty because their prior variances o² are low, and thus no exploration necessary. This is unique property of Bayes regret bounds that not captured by any frequentist analysis, such as that of UCB1-Normal (Auer et al. 2002).
of log (1+ 0, V EK o8.1 Note that we ignore the first
Regret optimality, Starting with the seminal works of Russo & Van Roy 2014 2016), most Bayes regret bounds are Õ(Vr)) and do not have finite-time instance deeenddet lower bounds. Lattimore & Szepesvári (2020) derived a (2(v Kn) asymptotic lower bound for a K-armed bandit as n - oo (Theorem 35.1). Our regret bound (Theorem[] matches this rate when all variances the same, To, = o. for all i E [K]. In addition, it provides an improved dependence on lower reward variances and more informative priors, which implies faster learning rates in these regimes. In fact, when the prior variances of all mean arm rewards go to zero, oo,; - 0 for all i E [K]. our bound goes to zero; expected. Therefore, conjecture that our regret bound is worst-case optimal. The only other lower bound that This lower bound is asymptotic and applics only to exponential-famme family reward distributions with a single parameter, which excludes Gaussian distributions because they have two parameters. The
aware of is (log" n.) for a K --areed bandit (Theorem 3 in Lai 1987)) )).
5

---

Published as a conference paper at ICLR 2024
lower bound was recently matched in Bernoulli bandit by Atsidakou et al. (202)). This indicates that logarithmic upper bounds may be possible in our setting. To conclude, we believe that deriving a tight finite-time ( ((vKn) lower bound for our setting or a logarithmic upper bound are important problems, and we leave them for future work.
GAUSSIAN BANDIT WITH UNKNOWN VARIANCES
Our main contribution is the Bayesian setting with Gaussian rewards and unknown heterogeneous reward variances. Similarly to Section 4 we propose a Thompson sampling algorithm for this setting in Section 5.1 We state and discuss its regret bound in Section 5.2 The bound scales roughly
Vnlogn E
Ei=l no. Bo.: log 1 + ko.))
where cro. 1 a proxy for the reward variance of in equation and k plays the role of / Since the dependencies are analogous, the bound captures the structure of the problem similarly to equation 2 Our main novelty lies in handling the uncertainty of reward variances o², which is unique among all existing TS proofs.
Bo.s
5.1 ALGORRTHH VarTS
we maintain a posterior distribution over the unknown mean arm rewards i and act optimistically with respect to samples from it. The challenge is that the reward variances o² are also unknown. To overcome it, we use the fact that the posterior of (J4, 0;-) is a Gaussian-Gamme distribution when the prior is and the rewards Gaussian. We represent the posterior hierarchically, in an equivalent form (Lemma in Appendix), as follows. The posterior distribution of the mean reward of in round & is A (it,, [.)). where jie; and oi, are the posterior mean and sampled variance, respectively. The variance is o², = Re,c where Kt.i = ((N((i) and λ is a posterior- sampled reward precision of arm i in round The posterior distribution of λς, is Gam St,s). where 0, and Br,, denote its shape and rate parameters, respectively. All posterior parameters are initialized by their prior values (Mo,a Ko,s, Op,i Bo,i).
As in Algorithm[] !
Our algorithm is presented in Algorithm and we call it VarTS, because it adapts to the unknown reward variances of arms. The algorithm works as follows. In round f, it first samples the precision of each arm from its posterior, Ae,i Gam(a,,; 3,,;), and then it samples the mean arm reward from its posterior, i ( w.,.d...) ). After that, the arm with the highest posterior-sampled mean reward is pulled, A, == arg [ Pe,s. Finally, the algorithm observes stochastic reward of arm A,, At,A, ~ ((AA,, o A,), and updates its posteriors (lines 7-13 in Algorithm 2). The complete pseudocode Algorithm 2]s given in Appendix C
5.2 REGRET ANALYSIS
We recall that the bandit instance (μ,, or) is sampled from Caussian-Gamma distribution: for any arm i, the mean and variance of its rewards sampled (14, ., NG Ko,i, Og,is (0,s). where (no, Ki, (ko, Bo) known prior parameters. This can also be seen first sampling o; Gam(oo, Bu,s) and then μ4; NN(po, no,, d.). Our regret bound is stated below.
-2
Theorem (Variance-dependen regret bound for unknown variances). Consider the above setting and let Coo for all arms E [ Then for any 8 O, the Bayes regret of VarTS is bounded as:
Rn s (ooooo///// (1/8) + 8Cknkk/22m
where C² -
Bot
2 Ko,i
(oo, 1) + 5lgg
0.5
n No,i
is drier-dependent constant.
ap,5-1
2 The difficulty lies in tightly bounding confidence intervals of random reward means with unknown reward variances, to obtain the right dependence on Bu. and 1 This is algebraically challenging due complicated posterior updates of Gaussian-Gammn distributions in
Proof of Theorem
ao,--1 Ko.

---

Published as a conference paper at ICLR 2024
To overcome these difficulties, we carefully condition random variables each other together with their appropriate histories, and then combine them using Jensen's 's and Cauchy-Sehii Schwarz inequalities. The key lemmas along with the complete proof of Theorem 2 are in Appendix
Algorithm 2
Dependence on all parameters of interest and prior. For ò = 1/n,, the bound in Theorem is
Ö(VCn). The dependence on vn is the same as in Theorem A closer examination of C' reveals many similarities with Theorem
First, since o,-² ~ Gam(ao.i: So,i), we know that of is sampled from an Inverse-Gamma distribution with the same parameters. The mean of this distribution 80.:/(a0. - 1). Hence, 90,/(aa,, 1) in
Theorem 2 plays the role of of in Theorem and represents the effective reward variance.
Second, Ku.; in the Gaussian-Gamma prior plays the role of of / i in the known variance setting (Murphy 2007). Therefore, as Ko,; + oc, the bound in Theorem 2 should go to zero, similarly to Theorem This is indeed the case and a very unique property of Bayes regret bounds, which is not captured by Honda & Takemura (2014); [Zhou & Tian (2022).
Finally, we take 0g Рo, - oc while keeping (o,i/ 1) fixed. Since the mean and variance of the Inverse-Gannn the mean of the variance prior is fixed while narrow its width. In this case, expect the bound in Theorem 2 to approach Theorem which happens because 0.5/(Ho,:(ao. 1)) vanishes. After that, the bounds are similar up multiplicative factor of 5.
distribution are /o,s/ax,, 1) and / ((ao,; - (au, - 2)), respectively,
Existing frequentist regret bounds for variance-adaptive Thomson sampling, Honda & Takemura (2014); Zhuu& & Tan (2020) proposed crriance-adaptive Thompson sampling and bounded its regret. These works differ from us in three aspects. First, the algorithms of Honda & Takemura 2014); Zhu
Tan (2020) are designed for the frequentist setting. Specifically, they have fixed sufficiently prior, and enjoy per-instance regret bound under this prior. As an example, the algorithm of Zhu & Tan (2020) for p + oo (Remark 4) is essentially VarTs with Ho.: O, Ko. 0. ao. 0.5.
and Mo. = 0.5. While per-instance regret bounds are strong, the algorithms of Honda & Takemura (2014); Zhu & Tan (2020) can perform poorly when priors are narrower and thus more informative.
Truly Bayesian algorithm designs, as proposed in our work, can be analyzed for any informative prior. Second, the analyses Honda & Takemura (0114); Zhu & Tan (2020) are frequentist. This means that they cannot justify the use of more informative priors and are essentially similar to those of frequentist upper confidence bound algorithms. As an example, in Remark 4 of Zhu & Tan (2020),
the authors derive O (Eepe<pa 1 logn) regret bound, where A; = Pa- μ4 and a" is the arm A. with the highest mean reward 14: This bound clearly does not depend on prior parameters, which we incorporate in our bounds. Specifically, our bound in Theorem decreases with lower reward variances and more informative priors on them. Finally, the regret bounds of Honda & Takemura (2014): Zhu & Tan (020)) are asymptotic. We provide strong finite-time guarantees.
6 EXPERIMENTS
We also study the empirical performance of our proposed algorithms. Since VarTS does not assume that the reward variances are known, and thus is more realistic than Algorithm [ we focus on VarTS. We conduct four experiments. First, evaluate VarTs in Bernoulli bandit, which is standard bandit benchmark. Second, we experiment with beta reward distributions. Their support is [o, 1], as in Bernoulli distributions, but their variances are not fully determined by their means. Since VarTs is designed for Gaussian bandits, the first two experiments also evaluate the robustness of VarTs to model misspecification. Third, we experiment with a Gaussian bandit. Finally, we vary the number of arms and observe how the performance of VarTS scales with problem size.
6.1 EXPERIMENTAL SETUP
All problem instances in our experiments are Bayesian bandits. The mean arm rewards are drawn from prior distribution. In Gaussian bandits, VarTS is run with the true (no, Ko, Coo, Bo). In other problems, the hyper- aaper-parameters of VarTs are set using the method of moments (Pearson 1936) and samples from the prior. In particular, for given Bayesian bandit, let ã. and v, be the estimated mean and variance of the mean reward of arm sampled from its prior, respectively. Moreover, let X, and is be the estimated mean and variance of the precision of the reward distribution of arm i sampled
7

---

Published as a conference paper at ICLR 2024
(a) Bernoulli bandit
(b) Beta bandit
(c) Gaussian bandit
UCB1
Bernoulli T-TS
TS14
155
UCB1 Tuned.
150
Gaussian cII
150
VarTS
Regret
UCB-Y
TS20
100
100
100
50
50
50
500
1000
1500
2000
500
1000
1500
2000
500
1000
1500
2000
Round
Round
Round
Figure 1: VarTs compared to 7 baselines. The plots share legends.
Bemoulli bandit
Beta bandit
Gaussian bandit
10a
10a
10a
UCB1
Bernouli-e-15
TS14
UEB1 -unedd
Gaussian
VerTS
Regret
10a
UCB V-
Regret
10
7S20
Regret
10a
10
10
101
10a
2
2
2
2
2
2
2
2a
2
2
Number of arms
Number of arms
Number of arms
Figure 2: VarTS with 7 baselines as we vary the number of arms K. The plots share legends.
from its prior, respectively, Then, using these statistics, we estimate the unknown seperpprraeeter of the prior as Ma,i P4. So.; X 00,, / )i and Ko,; B/, (on,)))))))))
We compare VarTS to several baselines. UCB1 (Auer et al. 2002) is the most popular algorithm for stochastic K-armed bandits with [o, 1] rewards. does not adapt reward variances and thus may be too conservative in our setting. We also consider variance-adaptive UCB algorithms: UCB1-Tuned (Auer et al., 2002) and UCB-V (Audibert al.) 2009b). UCB1-Tuned is heuristic that performs well in practice. UCB-V uses empirical Bernstein confidence intervals and has theoretical guarantees. We implement both algorithms for [0, 1] rewards. The next two baselines are Bernoulli and Gaussian TS (Agrawal & Goyal 2013a). Bernoulli TS has a uniform Beta(1, 1) prior. When the rewards Yr,; are not binary, we clip them to [0, 1] and then apply Bernoulli rounding: the reward replaced with with probability Y,, and 0 otherwise. Gaussian TS has a (0 1) prior and unit reward variances. We modify both algorithms to explore using the posterior sample 1/ K fraction time and the posterior mean otherwise, as proposed and analyzed in Jin et al. 2023). This significantly reduces the regret of Gaussian TS while the regret of Bernoulli TS remains comparable. We refer to these algorithms as c-T. The last two baselines are Thompson sampling with unknown reward variances (Honda & Takemura 2014 Zhu & Tan 2020). We implement Algorithm I in Honda & Takemura (2014) and call it TS14, and Algorithm 3 in Zhu & Tan (2020) for p co and call it TS20. Note that TS20 is VarTS where μo, 0, Ko, = O, oo, = 0.5, and Po. = 0.5. The shortcoming of all TS baselines is that they are designed have frequentist per-instance guarantees. Therefore, their priors are set too conservatively to compete with VarTS, which takes the true prior or its estimate as an input. In all simulations, the horizon n 200 and they are averaged over 000 randomly initialized runs.
The baselines in our experiments were chosen to cover well existing variance- variance-adaptive adaptive/ not adaptive and Bayesian frequentist bandit algorithms: UCB1-Tuned, UCB-V, TS14, and TS20 adapt to unknown reward variances; while UCB1 and c-TS do not, c-TS, TS14, and TS20 are Bayesian algorithms; while UCB1, UCB1-Tuned, and UCB-V are frequentist algorithms.
6.2 BERNOULLI BANDIT
We start with a Bernoulli bandit with = 10 arms. The mean reward of arm E [K], (4; is sampled i..dd. from prior Beta(i, K + 1-110 i). Since E [us] = i/(K + 1) and std [us] z 1/VK + I, higher prior means indicate higher μ4, although arm K may not have the highest mean reward.
Our results are reported in Figure Th. We observe that VarTs and Bernoulli e-TS have the lowest regret. The latter is not surprising since Bernoulli c-TS is designed for this problem class. The fact
8

---

Published as a conference paper at ICLR 2024
that match its performance is testament to adapting reward variances and using priors. Three out of four of the next best-performing algorithms (UCB1-Tuned, TS14, and TS20) adapt to reward variances but do not use informative priors. The frequentist algorithms with regret bounds (UCB1 and UCB-V) have the highest regret because they are too conservative.
6.3 BETA BANDIT
The bandit problem in the second experiment a variant of Section 6.2 where the reward distribution of arm is Beta(sp4; s(1 -1;)) for
10. Roughly speaking, this means that the reward variance of arm is 10 lower than in Section 6.2 The rest of the setup is the same.
Our results reported in Figure Db. We observe only differences from Figure Db. First, VarTs outperforms Bernoulli e-TS because it learns that the arms have 10 times lower reward variances than in Figure Th. Therefore, can be more aggressive in pulling the optimal arm. Second, both TS14 and TS20 outperform UCB1-Tuned, possibly due to more principled learning of reward variances.
6.4 GAUSSIAN BANDIT
The third experiment is with a Gaussian bandit where both the means and variances of rewards are sampled i.i.d. from prior with parameters yo,; i/(K 1), Ko,; K, oo. = 4, and Bo, 1. For this setting, E [pa] = i/(K + 1) and std [ua] = 1/vK + Therefore, higher prior means indicate higher f4g, although arm K may not have the highest mean reward. Since the average reward variance 0.25, bandit algorithms for (0, 1] rewards are expected to work well.
Our results are reported in Figure We observe that UCB1-Tuned has the lowest regret and VarTs performs similarly. This shows the practicality of our design, which analyzable and comparable to well-known heuristic without guarantees. All other algorithms have at least 50% higher regret. As before, the frequentist algorithms with regret bounds (UCB1 and UCB-V) are overly conservative and among the worst performing baselines.
6.5 SCALABILITY
We vary the number of arms K and observe how the performance of VarTS scales with problem size. This experiment is done in Bernoulli (Section 6.2). beta (Section 6.3). and Gaussian (Section 6..4 bandits. Our results in Figure
that the gap between VarTS and the baselines increases with K. For K = 32 and Bernoulli bandit, VarTS has at least 3 times lower regret than any baseline. For K = 32 and beta bandit, VarTS has at least 5 times lower regret than any baseline. For K = 32 and Gaussian bandit, VarTS has at least 2 times lower regret than any bascline. These gains are driven by adaptation to reward variances and using priors, on both the mean and variance of the rewards.
7 CONCLUSIONS
We study the problem of learning to act in multi-armed Bayesian bandit with Gaussian rewards and heterogeneous reward variances. As first step, we present a Thompson sampling algorithm for the setting of known reward variances and bound its regret (Theorem D. The bound scales as
of log [1+n=, n.ez)) Therefore, it goes to zero the reward variances of or the vn log EK10?
prior variances of the mean arm rewards oă. decrease. Our main contribution is VarTS, variance- adaptive TS algorithm for Gaussian bandits with unknown heterogeneous reward variances. The algorithmic novelty lies in maintaining joint Coussian-Gammm posterior for the mean and variance of rewards of each arm. We prove Bayes regret bound for VarTS (Theorem ( that scales similarly
to the known variance bound. More specifically, it / Vnllog
ΣK
K
Bo.:
log (1+ No. where
Co.
$o. T is proxy for the reward variance of and Ko, plays the role of o/./0?. Our bound captures the effect of the prior on learning reward variances and is the first such bound.
Potential future directions include extending our framework to infinite arms, which would require a different set of assumptions on the priors and reward distributions for tractable solutions. Another very practical and general direction would incorporating context and changing reward variances
over time, in Kim et al. (2022): /Zho al. (202 2023 Zhang et al. (201))

---

Published as a conference paper at ICLR 2024
REFERENCES
Yasin Abhasi-Yadkori, David Pal, and Csaba Szepesvari. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems 24, pp. 2312-2320, 2011.
Shipra Agrawal and Navin Goyal. Analysis of Thompson sampling for the multi-armed bandit problem. In Proceedings of the 25th Annual Conference on Learning Theory, pp. 39.1-39.26. 2012.
Shipra Agrawal and Navin Goyal. Further optimal regret bounds for Thompson sampling. In Proceedings of the 16th International Conference on Artificial Intelligence and Statistics, pp. 99-107, 2013a.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In Proceedings of the 30th International Conference Machine Learning, pp. 127-135, 2013b.
Alexia Atsidakou, Branislav Kveton, Sumeet Katariya, Constantine Caramanis, and Sujay Sanghavi. Finite-time logarithmic Bayes regret upper bounds. In Advances in Neural Information Processing Systems 36, 2023.
Jean-Yves Audibert, Sébastien Bubeck, al. Minimax policies for adversarial and stochastic bandits. In COLT, volume 7, pp. 1-122, 2009a.
Jean-Yves Audibert, Rémi Munos, and Csaba Szepesvári. Exploration-explorrttinn tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410619):1866-1102 2009b.
Peter Auer. Using confidence bounds for exploitation-exxloraiion trade-offs. Journal of Machine Learning Research, 3:397-422, 4222, 2002.
Peter Auer, Nicolo Desa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47:235-255 256,,25,2220 2002.
Sébastien Bubeck and Che- Yu Liu. Prior-free and prior-dependent regret bounds for Thompson sampling. Advances in neural information processing systems, 26, 2013.
Sebastien Bubeck, Remi Munos, and Gilles Stoltz. Pure exploration in multi-armed bandits problems. In Proceedings of the 20th International Conference Algorithmic Learning Theory, pp. 23-37, 2009.
Olivier Chapelle and Lihong Li. An empirical evaluation of Thompson sampling. In Advances in Neural Information Processing Systems 24, pp.
2011.
John D Cook. Inverse gamma distribution. online: http://www. johndcook. com/inverse gamma. pdf. Tech. Rep, 2008.
Marco Faella, Alberto Finzi, and Luigi Sauro. Rapidly finding the best arm using variance. In Proceedings of the 24th European Conference on Artificial Intelligence, 2020.
Victor Gabillon, Mohammad Ghavamzadeh. Alessandro Lazaric, and Sebastien Bubeck. Multi-bandit best arm identification. In Advances in Neural Information Processing Systems 24, 2011.
Aurelien Garivier and Olivier Cappe. The KL-UCB algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th Annual Conference on Learning Theory, pp. 356-376. 201
Andrew Gelman and Jennifer Hill. Data Analysis Using Regression and Multileve/ftierarchical Models. Cambridge University Press, New York, NY, 2007.
Junya Honda and Akimichi Takemura. Optimality of Thompson sampling for Gaussian bandits depends on priors. In Proceedings of the 17th International Conference on Artificial Intelligence and Statistics, 2014.
Joey Hong, Branislav Kveton, Sumeet Katariya, Manzil Zaheer, and Mohammad Ghavamzadeh. Deep hierarchy in bandits. Proceedings of the 39th International Conference on Machine Learning, 2022a.
10

---

Published as a conference paper at ICLR 2024
Joey Hong, Branislav Kveton, Manzil Zaheer, and Mohammad Ghavamzadeh. Hierarchical Bayesian bandits. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, 2022b.
Tianyuan Jin, Pan Xu, Jieming Shi, Xiaokui Xiao, and Quanquan Gu. Mots: Minimax optimal Thompson sampling. In International Conference Machine Leurning, pp. 5074-5083. PMLR, 2021.
Tianyuan Jin, Xianglin Yang, Xiaokui Xiao, and Pan Xu. Thompson sampling with less exploration is fast and optimal. In Proceedings of the 40th International Conference on Machine Learning, 2023.
Mare Jourdan, Remy Degenne, and Emilie Kaufmann. Dealing with unknown variances in best- arm identification. CoRR, abs/2210.00974, 2022. URL /tt.tp/////ax....rrr///////// wttp//gg/aabbua.ao/ae/////////
00974
Yeoneung Kim, Insoon Yang, and Kwang-Sung Jun. Improved regret analysis for variance-adaptive linear bandits and horizon-free linear mixture MDPs. Advances in Neural Information Processing Systems, 35:1060-1077 2022.
Branislav Kveton, Mikhail Konobeev, Manzil Zaheer, Chih- Wei Hsu, Martin Mladenov. Craig Boutilier, and Csaba Szepesvari. Meta-Thompson sampling. In Proceedings of the 38th Interna- fional Conference on Machine Learning, 2021.
Tze Leung Lai. Adaptive treatment allocation and the multi-armed bandit problem. The Annals of Statistics, 15(3):1091-1114 1987.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4-22, 1985.
Anusha Lalitha, Kousha Kalantari, Yifei Ma, Anoop Deoras, and Branislav Kveton. Fixed-budgee best- arm identification with heterogeneous reward variances. In Uncertainty in Artificial Intelligence, pp. 1164-1173. PMIR, 2023.
Tor Lattimore and Csaba Szepesvári. Bandil algorithms. Cambridge University Press, 2020.
Pinyan Lu, Chao Tao, and Xiaojin Zhang. Variance- dependent best arm identification. In Proceedings of the 37th Conference on Uncertainty in Artificial Intelligence, 2021.
Xiuyuan Lu and Benjamin Van Roy. Information-theorree confidence bounds for reinforcement learning. Advances in Neural Information Processing Systems 32, 2019.
Pierre Ménard and Aurélien Garivier. A minimax and asymptotically optimal algorithm for stochastic bandits. In International Conference on Algorithmic Learning Theory, pp. 223 223-237. PMLR, 2017.
Subhojyoti Mukherjee, KP Naveen, Nandan Sudarsanam, and Ravindran Balaraman. Efficient-ucbv: An almost optimal algorithm using variance estimates. AAAI Conference on Artificial Intelligence, 32, 2018.
Kevin P Murphy. Conjugate Bayesian analysis of the Gaussian distribution. def. 1(2o2):16, 2007.
Karl Pearson. Method of moments and method of maximum likelihood. Biometrika, 28(1/2):34-59, 1936.
Pierre Perrault. When combinatorial Thompson sampling meets approximation regret. Advances in Neural Information Processing Systems, 35: 16617766-776111 2022.
Pierre Perrault, Etienne Boursier, Michal Valko, and Vianney Perchet. Statistical efficiency of Thompson sampling for combinatorial semi- mandis. Advances in Neural Information Processing Systems, 33:5429-5440. 2020.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 1221112221 2014.
11

---

Published as a conference paper at ICLR 2024
Daniel Russo and Benjamin Van Roy. An cittrmmmationthhhreee analysis of Thompson sampling. Journal of Machine Learning Research, 17(68):1-30) 2016.
Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A tutorial on Thompson sampling. Foundations and Trends in Machine Learning, 11(1):1-96, 2018.
Aadirupa Saha, Pierre Gaillard, and Michal Valko. Improved sleeping bandits with stochastic action sets and adversarial rewards. In International Conference on Machine Learning, pp. 8357-8366.
PMLR, 2020.
William R. Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3-4);285-294 1933.
Runzhe Wan, Lin Ge, and Rui Song. Metadata-based multi-task bandits with Bayesian hierarchical models. In Advances in Neural Information Processing Systems 34, 2021.
Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S Du. Improved variance-awai confidence sets for linear bandits and linear mixture MDP. Advances Neurul Information Processing Systems, 34:4342-4355 2021.
Heyang Zhao, Dongruo Zhou, Jiafan He, and Quanquan Gu. Bandit learning with general function classes: Heteroscedastic noise and variance-dependen regret bounds. 2022.
Heyang Zhao, Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. arXiv preprint arXiv:2302. 10371, 2023.
Ruida Zhou and Chao Tian. Approximate top-m arm identification with heterogeneous reward variances. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, 2022.
Qiuyu Zhu and Vincent Tan. Thompson sampling algorithms for mean-variance bandits. In Interna- tional Conference on Machine Learning, pp. 11,99-1 1608. PMLR, 2020.
12


Reviews:
[{"review_id": "Ai6Zc50IQc", "reviewer": "Reviewer_Lfwz", "summary": "This work develops a new Thompson sampling algorithm and proves prior-dependent Bayes regret bounds for K-armed Gaussian bandits. It studies the problem in both settings where the reward variances are known and unknown. The algorithm can achieve lower regret when the\nreward variances are low, which indicates the trade-off of the learner’s performance (regret) versus the prior parameters and reward\nvariances. The authors evaluate their new algorithms with numerical experiments comparing with other baselines.", "questions": "1. Is it possible to deal with distributions other than the Gaussian-Gamma prior distribution?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well organized. The presentation is unambiguous.\n2. The paper provides a new regret bound dependent on reward variances and informative priors.\n3. The paper conducts numerical experiments to justify the main results.", "weaknesses": "1. The variance aware regret bound depends on the summation of the variance across all the arms $\\sum_{i=1}^K \\sigma_i^2$. This can \n reduce the dependency of the number of arms $K$ to a variance-dependent result. However, the standard method to deal with large $K$ is to use function approximation. I feel confused about the relationship of these two methods. Can the result in this work be generalized to the bandit problem with function approximation?\n2. The Bayesian regret studied in this work is usually weaker than the frequentist regret.\n3. Algorithm 2 is under the standard Thompson sampling framework, and the posterior sampling updates seem similar to previous works, for example, [Zhu & Tan., 2020].  Are there any novel techniques in the algorithm design, or do the new results come from the analysis?\n4. There are some mistakes in the literature review. In the study of $d$-dimensional linear contextual bandits, they did not always keep the fixed variance across the arms. For example, in [Kim et al., 2022] and  [Zhao et al.,2023] mentioned in the paper, the stochastic noise at time step $k$, $\\epsilon_k$, is a random variable dependent on $\\mathcal F_k = \\sigma(x_1,\\epsilon_1,\\ldots,x_{k-1},\\epsilon_{k-1}, x_k)$ with $\\mathbb{E}[\\epsilon_k | \\mathcal F_k] = 0$ and $\\mathbb{E}[\\epsilon_k^2 | \\mathcal F_k] = \\sigma_k^2$. They do not assume the variances are fixed across arms.\n5. Some typos: should the bound in page 7 be $\\tilde O(C\\sqrt{n})$?\n\n=============== Post Rebuttal ===================\n\nThanks for the response for the authors. After reading what the authors mentioned in the response, I still believe that there is no need to make such assumptions on the fixed variance across the arms. The notation $\\sigma _ k ^ 2$ means the variance in round $k$, which can change when the selected arms are different (otherwise, the conditional expectation on $\\mathcal F_k = \\sigma(x_1,\\epsilon_1,\\ldots,x_{k-1},\\epsilon_{k-1}, x_k)$ is meaningless.) I agree that assuming the fixed variance across the arms is a common practice. But for completeness, I suggest the authors mention the possibility of dealing with more general cases. I greatly appreciate the effort the authors made.  However, after careful consideration, I remain unconvinced about the paper's novelty, leading me to keep my scores.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "0QRGdukePl", "reviewer": "Reviewer_u1uV", "summary": "This paper studies the two-parameter Thompson Sampling with Bayesian regret. When the variance is known, the regret bound presented in this paper scales as $\\sqrt{n\\sum_{i=1}^{K}\\sigma_i^2}\\cdot \\log n$, which is optimal up to a $\\log n$ factor. In the case of unknown variance, the regret bound resembles that of the known variance scenario. Experimental findings indicate that the Thompson Sampling algorithm introduced in this study outperforms other baseline methods, including UCB and traditional Thompson Sampling.", "questions": "In Bayesian analysis, regret bounds are typically derived using the Upper Confidence Bound (UCB) method, as illustrated in works like \"Prior-free and prior-dependent regret bounds for Thompson Sampling.\" However, this paper presents an alternative approach. It raises the question of whether it is possible to obtain the regret bound through a UCB method.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "See summary.", "weaknesses": "However, there are certain limitations to this paper:\n\n1. The techniques used to prove Bayesian regret have been extensively explored in previous literature and are considerably more straightforward than those for frequentist regret. More crucially, Bayesian regret is a subset of frequentist regret. This is because the latter always implies Bayesian regret, but the reverse is not true. \n2. The regret bound presented is not particularly stringent. It is a log n factor away from the optimal regret.\n3. The paper omits some crucial related work such as: \n    (1) Minimax policies for adversarial and stochastic bandits;\n    (2) Mots: minimax optimal thompson sampling;\n    (3) A minimax and asymptotically optimal algorithm for stochastic bandits;\n    (4) Prior-free and prior-dependent regret bounds for thompson sampling\n    (5) Thompson Sampling with less exploration is fast and optimal. It would be beneficial to see the baselines (2) (3) and (5) incorporated into the experiments.\n4. The experimental framework is anchored in the Bayesian context. It would be enlightening to witness experiments in the general setting, i.e., no prior on the means and variance of arms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "gV8mttTGLW", "reviewer": "Reviewer_RHSZ", "summary": "The authors investigate Gaussian bandits with heterogeneous reward variances, both known and unknown. For known variances, they introduce a Thompson sampling algorithm, achieving a Bayes regret bound that decreases as variances decrease. When variances are unknown, they present the VarTS algorithm, which employs a joint Gaussian-Gamma posterior for the mean and precision of all arm rewards. They establish a Bayes regret bound for VarTS that decreases with decreasing variances and stronger priors. Extensive experiments confirm VarTS's efficacy across different reward distributions.", "questions": "1) The detailed proof of Theorem 2 stands out as the main technical contribution in the paper. However, the current discussion on page 6 is somewhat succinct. A more in-depth exploration of the core ideas behind the proof would greatly benefit readers in grasping its implications.\n2) Is it possible to derive finite-time prior-dependent regret bound for Bernoulli TS or Beta TS?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1) This paper pioneers the study of Gaussian bandits with unknown heterogeneous reward variances and introduces the VarTS algorithm, leveraging a Gaussian-Gamma posterior for the task.\n2) The authors provide Bayes regret bounds that captures the effect of the prior on learning reward variances for Gaussian bandits with both known and unknown heterogeneous reward variances. The regret analysis for the unknown variance scenario is novel.\n3) Numerical experiments encompass not just Gaussian but also Bernoulli and beta distributions, demonstrating the generality and robustness of the proposed method.", "weaknesses": "1) As mentioned on page 5, the finite-time Bayes regret lower bound for Gaussian bandits remains unresolved, making the optimality of the Bayes regret bounds in Theorems 1 and 2 ambiguous. Furthermore, the current optimality discussion focuses on the order of $K, n$, but there should also be a discussion on its dependency on the prior and reward variances.\n2) The algorithm design for Gaussian bandits with unknown heterogeneous rewards seems as standard as the typical TS algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "PZAgtrElSE", "reviewer": "Reviewer_tUNz", "summary": "This paper addresses the challenge of optimizing bandit algorithms in the context of varying reward variances. Most bandit algorithms assume fixed reward variances or upper bounds on them, leading to suboptimal performance due to the inaccurate estimation of these variances. In this work, the authors lay the foundation for a Bayesian approach that incorporates prior knowledge about reward variances, resulting in lower regret and improved performance. They specifically focus on Gaussian bandits with unknown heterogeneous reward variances and develop a Thompson sampling algorithm with prior-dependent Bayes regret bounds.", "questions": "I am not convinced that this is a fundamental step in dealing with the problem of the general case of unknown variance in the case of non-Gaussian reward. Can you give more details on this ?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "They introduce a Thompson sampling algorithm for Gaussian bandits with known heterogeneous reward variances and provide regret bounds that decrease as reward variances decrease. This is a significant advancement in the context of bandit algorithms.\n\nThey propose a Thompson sampling algorithm (VarTS) for Gaussian bandits with unknown heterogeneous reward variances. VarTS maintains a joint Gaussian-Gamma posterior for mean rewards and precision, resulting in Bayes regret bounds that decrease with lower reward variances and more informative priors.\n\nThe paper thoroughly evaluates VarTS on various reward distributions, demonstrating its superiority over existing baselines. The results highlight the generality and robustness of the proposed algorithm.\n\nThe work distinguishes itself from prior research by providing strong finite-time regret guarantees, as opposed to asymptotic bounds.\n\nThey discuss the differences between their Bayesian approach and frequentist algorithms, highlighting the ability to leverage more informative priors in their design", "weaknesses": "The paper primarily focuses on Gaussian bandits with heterogeneous reward variances. While this is a significant step, the approach may not be directly applicable to other types of bandit problems with different reward distributions. The generalizability of the proposed method to various scenarios is not thoroughly explored.\n\nBayesian regret is often considered as easier than frequentist regret.\n\nYou may need to cite https://arxiv.org/abs/2006.06613 and https://arxiv.org/abs/2302.11182 as they analysed a Gaussian thompson sampling policy in a quite general setting which is related and relevant to the present paper.\n\nI was thinking the Gaussian-Gamma prior was already used for the analysis of TS, but it seems that I am wrong since I cound not find back the ref.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "y5P1mfpOye", "reviewer": "Reviewer_oe9F", "summary": "The submission studied multi-armed bandits. The reward-generating process of each arm follows a different Gaussian-Gamma distribution. The submission proposed two Bayesian methods (Algorithms 1 and 2) and provided two prior-dependent regret bounds (Theorems 1 and 2). The proposed method (VarTS) is compared with seven existing methods in experiments.", "questions": "(d) The main paper categorizes the methods using Bayesian/frequentist approaches or the identical $\\sigma$/distinct $\\sigma_i$ settings. Could you please also reflect on these different baselines in the experiments, helping the reader to compare and contrast the differences between considering/not considering the prior information?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The submission addresses the unknown reward variance. The regret is a finite-time analysis, and the bounds show how the reward variance affects the regret.", "weaknesses": "(a) Assuming Gaussian bandits would be impractical when facing realistic applications. As a complement, the analysis should discuss the cost of mis-modeling and show how to control this additional cost to obtain a meaningful regret bound. (In contrast, the experiments indeed consider distributions other than Gaussian.)\n\n(b) The submission lacks a clarification that connects the novelty claimed in Contribution-(3) to the analysis in the appendix. This information would help evaluate and understand the technical contribution(s) of this submission.\n\n(c) The variance-dependent bounds (Theorems 1 and 2) would be better justified if we could see curves of the proposed methods that vary according to the change of the unknown parameters in experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)