No Regrets for Learning the Prior in Bandits
Authors: Soumya Basu
Branislav Kveton
Manzil Zaheer
Csaba Szepesvari
Venue: NeurIPS 2021 Poster (2021)
Keywords: multi-armed bandits
meta-learning
Thompson sampling
online learning

Abstract: We propose AdaTS, a Thompson sampling algorithm that adapts sequentially to bandit tasks that it interacts with. The key idea in AdaTS is to adapt to an unknown task prior distribution by maintaining a distribution over its parameters. When solving a bandit task, that uncertainty is marginalized out and properly accounted for. AdaTS is a fully-Bayesian algorithm that can be implemented efficiently in several classes of bandit problems. We derive upper bounds on its Bayes regret that quantify the loss due to not knowing the task prior, and show that it is small. Our theory is supported by experiments, where AdaTS outperforms prior algorithms and works well even in challenging real-world problems.

No Regrets for Learning the Prior in Bandits
Soumya Basu Google
Branislav Kveton
Manzil Zaheer Google Research
Csaba Szepesvári DeepMind / University of Alberta
Google Research
Abstract
We propose AdaTS, a Thompson sampling algorithm that adapts sequentially to bandit tasks that it interacts with. The key idea in AdaTS is adapt an unknown task prior distribution by maintaining distribution over its parameters. When solving a bandit task, that uncertainty is marginalized out and properly accounted for. AdaTS is a fully-Bayesian algorithm that can be implemented efficiently in several classes bandit problems. We derive upper bounds on its Bayes regret that quantify the loss due to not knowing the task prior, and show that it is small. Our theory supported by experiments. where AdaTS outperforms prior algorithms and works well even in challenging real-world problems.
Introduction
We study the problem of maximizing the total reward, minimizing the total regret, in sequence of stochastic bandit instances [29, 4, 31J. ]. We consider a Bayesian version of the problem, where the bandit instances with m bandit instances m tasks, with one instance per task. The interaction with each task is for n rounds and with K arms. The reward distribution of arm E [K] in task [m]] is (+ (=.-0...). where 0,,, is a shared parameter of all arms in task s. When arm is pulled in task s, the agent receives random reward from (= (=)0..)). The parameters .......... On.. are drawn independently of each other from a task prior P(:; p.). The task prior is parameterized by an unknown meta- parameer Ma, which is drawn from a meta-prior Q. The agent does know fax or fi....... 6,,,. However, knows Q and the parametric forms of all distributions, which help it to learn about μt, This is form of meta-learning [39, 40. 7, 8]. where the agent learns to act from interactions with bandit instances.
drawn from some distribution. More specifically, the learning agent interacts
simple approach is to ignore the hierarchical structure of the problem and solve each bandit task independently with some bandit algorithm, such as Thompson sampling (TS) [38, 11, 2, 37]. This may be highly suboptimal. To illustrate this, imagine that arm is optimal for any 0 in the support of P(:...) If μa, was known, any reasonable algorithm would only pull arm and have zero regret over any horizon. Likewise, a clever algorithm that learns should eventually pull arm 1 most of the time, and thus have diminishing regret as it interacts with growing number of tasks. Two challenges arise when designing the clever algorithm. First, can it be computationally efficient? Second, what is the regret due to adapting to p
We make the following contributions. First, we propose a Thompson sampling algorithm for our problem, which call AdaTS. AdaTS maintains distribution over the meta-parameter μe,, which concentrates over time and is marginalized out when interacting with individual bandit instances. Second, we propose computationallly-ffiiee
implementations of AdaTS for multi-armed bandits [29, 4], linear bandits [14, IJ. and combinatorial semi-bandits [19, 13, 26]. These implementations for specific reward distributions and conjugate task priors. Third, bound the и-round Bayes regret of AdaTS in linear bandits and semi-bandits, and multi-armed bandits as special case. The Bayes regret defined by taking an expectation over all random quantities, including pa, ~ Q. Our bounds show that not knowing μa, has minimal impact on the regret as the number of tasks grows, of only Ö(ymn). This is in a sharp contrast to prior work [28], where this is Ó mmm?). Finally,
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

our experiments show that AdaTS quickly adapts to the unknown meta parameter is robust to meta-prior misspecification, and performs well even challenging classification problems.
We present a general framework for learning to explore from similar past exploration problems. One potential application is cold-start personalization in recommender systems where users tasks. The users have similar preferences, but neither the individual preferences nor their similarity is known in advance. Another application could be online regression with bandit feedback (Appendix E.2) where individual regression problems are tasks. Similar examples in the tasks have similar mean responses, which are unknown advance.
2
Setting
We first introduce our notation. The set .......n]. } denoted by [n]. The indicator L{E) denotes that event E' occurs. The i-th entry of vector is If the vector or its index are already subindexed, we write v()). We use Ô for the big-O notation up to polylogarithmic factors. A diagonal matrix with entries v denoted diag (v). We use the terms "arm" and "action" interchangeably. depending on the context.
Our setting was proposed in Kveton al. [28] and is defined as follows. Each bandit problem instance has K arms. Each arm i [K] is defined by distribution ps(=;() 0) with parameter 0 E è. The parameter θ is shared among all arms. The mean of (. 0) is denoted by r(é; 0). The learning agent interacts with m instances, one at each of m tasks. At the beginning of task s [m]. an instance 0s.- E θ is sampled i.i.d. from a task prior P(::)s,, which is parameterized by ja.. The agent interacts with 0g,= for n rounds. round E [n], it pulls one arm and observes stochastic realization of its reward. We denote the pulled arm round of task by As,t E
Hg
Σg
Σo
f
Figure 1: Graphical model of our en- vironment.
[K]. the realized rewards of all arms in round f task s by Ys R
and the reward of arm i E [K] by Yi, ~ (:(:;::] ). We assume that the realized rewards Ys,t are ii.d. with respect to both s and A graphical model of our environment is drawn in Figure 1. We define the distribution-speciine parameters plg, Eq. Co, and o² when we instantiate our framework. Our terminology is summarized Appendix A.
The n-round regret of an agent or algorithm over m tasks with task prior ((-))a)) is defined as
R(m, ni p.)
E
Σ
((Ae,xi0a.)) ((Ao,ii
14
where Ag,, arg maggmaxiesssg jE|K] 6 is the optimal arm in the random problem instance 0,,, in task E [m]. The above expectation is over problem instances 0x.- ~ P(: ps),, their realized rewards, and also pulled arms. Note that μa is fixed. Russo and Van Roy [36] showed that the Bayes regret, which matches the definition (1) in any task, of Thompson sampling in a K-armed bandit with n rounds is (nKn). So, when TS applied independently in each task, R(m, nE; ju.) = Ó(my Kn).
Our goal is to attain comparable regret without knowing fa. We frame this problem in a Bayesian fashion, where μ. Q before the learning agent interacts with the first task. The agent knows Q and we call it meta-prior. Accordingly. we consider R(m, n) = E [R(m, n.; jm.]] as a metric and call it the Bayes regret. Our approach motivated by hierarchical Bayesian models [20], where the uncertainty in prior parameters, such as Mr, is represented by another distribution, such as Q. In these models, Q is called a hyper-prior and μt, is called hyper-parameter We attempt learn p., from sequential interactions with instances 0,,, ~ P(: p.), which are also unknown. The agent can only observe their noisy realizations Y.,--
3 Algorithm
Our algorithm is presented in this section. To describe it, we need to introduce several notions of history, the past interactions of the agent. We denote by H, (Ag,,, (Ae, the history in

---

Algorithm AdaTS: Instance-adaptive exploration in Thompson sampling.
1: Initialize meta-prior Qo < Q
2: for I,...: do
3: Compute meta pecta-psttrrior Q. (Proposition 1)
4: Compute uncertaint--adjusee task prior P. (Proposition 1)
5:
for t L..... do
6: Compute posterior of in task s, (0) & C,,, (0)P,(0)
7:
Sample f,, ~ Ps pull arm As, + arg max (e( r(ē; 8s,1), and observe (A,,)),))
task and by H1:s = H1 ..... @ H, a concatenated vector of all histories the first tasks. The history up round in task s H.. is H H1ss.t = -1:--1 @ Ha.e. We denote the conditional probability distribution given history Hiss, by (-) = P (1ss,t) and the corresponding conditional expectation by E,, E- H1sse))
i (A..(()))) and all history up to round in task
Our algorithm is a form Thompson sampling [38, 11, 2, 37]. TS pulls arms proportionally to being optimal with respect to the posterior. In particular, let (0) = -I
PA,,, (Ys, As,)): be the likelihood of observations in task up to round t. If the prior ((.) was known, the posterior of instance in round / would be Pa.(()) x (0) P(0; p.). TS would sample 0, ~ p.d and pull arm
A, arg max Sε[K] r(;; 0z).
We address the case of unknown μr,. The key idea in our method is to maintain posterior density of Jaa which we call peeta-posterior. This density represents uncertainty in paa given history. task s, we denote it by Qs and define it such that P (n. E B H1:s-1) = SueB Qs deg (n) holds for any set B, where is the reference measure for μ. We this more general notation, opposing to dp, because μ can be both continuous and discrete. When solving task s, Q is used to compute an uncertainty addiusttt--djjstteed task prior Ps. which is posterior density of 02.- given history. Formally, P. is a density such that IP (0z.. E B H1 = JSeB (,(0) dieg (0) holds for any set B, where R2 the reference measure for 0. After computing Pe. we run TS with prior Pe to solve task s. To maintain Q, and Ps. we find it useful expressing them using recursive update rule below.
Proposition Let (0) = II (Y,, 0) be the likelihood of observations in task s.
Then for any task E [m].
Pa(0) / P(O: Q2(u) (M), Qa(m) =
1:000J(c... c. P(O:
dkz(0) (() Qu-1(u).
The claim is proved in Appendix A. The proof uses the Bayes rule, where we carefully account for the fact that the observations are collected adaptively, the pulled arm in round t of task depends on history H1sstt The pseudocode of our algorithm is in Algorithm 1. Since the algorithm adapts to the unknown task prior P(: p.), we call it AdaTS. AdaTS can be implemented efficiently when P. is conjugate prior for rewards, or mixture of conjugate priors. We discuss several exact and efficient implementations starting from Section 3.1.
The design of AdaTS is motivated by MetaTS [28]. which also maintains a meta meta--osteriior Qz. The difference is that MetaTS samples åá Q. in task to be optimistic with respect the unknown M4.- Then runs TS with prior 7l:; While simple and intuitive, the sampling of ã induces a high variance and leads sampling step. This leads to tighter and more general regret bounds (Section 4), beyond multi-armed bandits; while the practical performance also improves significantly (Section 5).
conservative worst-case analysis. We improve MetaTS by avoiding the
3.1 Gaussian Bandit
We start with a K-armed Gaussian bandit with mean arm rewards 0 RRK The reward distribution of arm i is (.(:; (:; 0g, o²), where >> 0 is reward noise and 02 is the mean reward of arm i. A natural conjugate prior for this problem class is P(::)) = -N Eg), where En = diag ((0 K(
known and we learn fa E K
Because the prior is multivariate Gaussian, AdaTS can be implemented efficiently with a Gaussian meta-prior Q(-) =Ni:; Pg: Eg), where My ( and Mn diag (( are known mean
3

---

parameter vector and covariance matrix, respectively, In this case, the meta-posterion in task s is also a Gaussian (. = (:V:):;;:: Ms: En), where ii, = ( and E. = diag (102,)) are defined as
As, = 02,
Hyge + g.2 t=1
Σ
Te
BE,
0, = o +
Σ
Tea {=1 Te, T +
=-1
(2)
Te, t.
+ Te,s
Here Te,; = - 1fAe+ = is the number of pulls of arm i in task E and the total reward from these pulls is Be,; = ='== 1(Ac.= (i). The above formula has a very nice interpretation. The posterior mean As.; of the meta-parameter of arm is a weighted sum of the noisy estimates of the means of arm from the past tasks /T,,/Te, and the prior. In this sum, each bandit task is essentially a single observation. The weights are proportional to the number of pulls in a task, giving the task with more pulls higher weight. They vary from (o + x-)- when the arm is pulled only once, up 0.5- This is the minimum amount of uncertainty that cannot be reduced by more pulls.
The update in (2) is by Lemma in Appendix A, which we borrow from Kveton et al. [28]. From Proposition 1, we have that the ensertainty-adjusee prior for task is (.(.) = (N: Ps. E, + Eo).
3.2 Linear Bandit with Gaussian Rewards
Now we generalize Section 3.1 and consider linear bandit [14, 1] with K arms and d dimensions. Let A Rd be an action set such that |A| = K. We refer to each a E A as an arm. Then, with a slight abuse of notation from Section the reward distribution of arm a is (a 0) WV;; a 0, o²). where 0 Rd is shared by all arms and > 0 is reward noise. A conjugate prior for this problem class is ((::))) = (:; μr, Eo), where Eg E ddd is known and we learn μl E Rd.
As in Section 3. AdaTS can be implemented efficiently with a meta-prior Q(-) = N1s Pag Eg). where My E I2d is known mean parameter vector and Eng E RRd is known covariance matrix. In this case, (. (N: is: Ex), where
B
G: σ²
C2
-1
B σ²
P.. = E,
Ej Mg +
Σ
20
+
0²
02
s-1 G
G o²
Ge o² 0²
Gt
511 q + Σ
Σn
+
02
Here Ge Er= A is the outer product of the feature vectors of the pulled arms in task l and B₁ Ei=1 Ae,YE,.(A,, is their sum weighted by their rewards. The above update follows from Lemma 7 in Appendix A, which is due to Kveton et al. [28]. From Proposition 1, the uncertainty- adjusted prior for task is Pa(-) = (N: E. + En).
We note in passing that when K = d and is the standard Euclidean basis of Rd. the lincar bandit reduces to a K-armed bandit. Since the covariance matrices are unrestricted here, the formulation in this section also shows how to generalize Section 3.1 to arbitrary covariance matrices.
3.3 Semi-Bandit with Gaussian Rewards
A stochastic combinatorial semi-bandit [19, 12, 25, 26, 42], or semi-bandit for short, is K-armes bandit where at most L S K arms are pulled in each round. After the arms are pulled, the agent observes their individual rewards and its reward is the sum of the individual rewards. Semi-bandits can be used solve online combinatorial problems, such as learning to route.
We consider a Gaussian reward distribution for each arm, as in Section 3.1. The difference in the semi-bandit formulation that the action set is A C 11, (K), where 11, (K) is the set of all subsets of [K] of size at most L. In round t of task s, the agents pulls arms As, E A. The meta-posterior is updated analogously to Section 3.1. The only difference that 11 [ = i} becomes 1 { E A
3.4 Exponential-Famie Bandit with Mixture Priors
We consider a general K-areed bandit with mean arm rewards 0 E K The reward distribution of arm i is any one-dimensional exponential-famie distribution parameterized by 0, In Bernoulli

---

bandit, this would be p=(=;0) = (er(:; A natural prior for this reward model would be a product of per-arm conjugate priors, such as the product of betas for Bernoulli rewards.
is challenging to generalize our approach beyond Gaussian models because we require more than the standard notion of conjugacy. Specifically, apply AdaTS to an exponentially-famil prior, such as the product of betas, we need a computationally tractable prior for that prior. In this case, it does not exist. We circumvent this issue by discretization. More specifically, let (P(:.))f= be a set of L potential conjugate priors, where each P(::.) is a product of one-dimensional exponential-faminn priors. Then a suitable meta-prion is a vector of initial beliefs into each potential prior. In particular, it is Q(-) Cat(:; Wg)) where w E A is the belief and A is the L-simplex
In this case, Q)( Ig f (0) j) dr=2())Q=11()) in Proposition 1 has closed form, since is standard conjugate posterior update for a distribution over 0 followed by integrating out 0. In addition, (0) ー ((e:) is mixture of exponential-famme
priors over 0. This is an instance of latent bandits [22]. For these problems, Thompson sampling can be implemented exactly and efficiently. We do not analyze this setting because prior-dependent Bayes regret bounds for this
problem class do not exist yet.
4 Regret Bounds
We first introduce common notation used in our proofs. The action set A C Rdd is fixed. Recall that a matrix E Raxd is positive semi-definite (PSD) it is symmetric and its smallest eigenvalue is non-negative. For such X, we define o (X) maXae a Xa. Although maay (X) depends on A, we suppress this dependence because A is fixed. We denote by (X) the maximum eigenvalue of X and by (X) the minimum eigenvalue of X.
We also need basic quantities from information theory. For two probability measures P and Q over a common measurable space, we use D(PI(Q) to denote the relative entropy of P with respect to Q. It is defined as [(P]l)) = ʃ log( dP
मσ dP, where dP/dQQ is the Radon-Nikodym derivative of P with respect to Q: and is infinite when P is not absolutely continuous with respect to Q. We slightly abuse our notation and let P(X) denote the probability distribution of random variable X, P(X E )). For jointly distributed random variables X and Y, we let P(X Y) be the conditional distribution of X given Y. P(X& E. YY), which -eeasurable and depends on random Y. The mutual information between X and Y is I(X;Y) D(P(X, (ETXXYY)IR Y)IIP(X) where P(X)P(Y) is the distribution of the product of P(X) and P(Y). Intuitively, Y(;;Y) measures the amount of information that either X or Y provides about the other variable. For jointly distributed X, Y, and Z, we also need the conditional mutual information between X and conditioned on Z. We define this quantity as I [X; Y 2) = [Q[i(XYY Y Z)}, where Y Z) = D(P(X, Y 2)|IP(X | P) Z)) is the random conditional mutual information between X and Y given Z. Note that f(X;Y Z) is function of 7. By the chain rule for the random conditional mutual information, f(X; Yi. Y2 Z)
B[i(X; Y1 Y2, Z) Z + f(x: Y2 Z), where expectation is over Y2 Z. We would get the usual
chain rule I(X; Y2) = Y Y2) + I(X;Y2) without Z.
4.1 Generic Regret Bound
We start with generic adaptation of the analysis of Lu and Van Roy [33] to setting. In round t of task s, we denote the pulled arm by Ag,t, its observed reward by Ya,, ~ (=: suboptimality gap by A., = :A 02.)) ) r(A,,r: a..)). For random variables X and Y, we denote by (X; Y) = i(x: Y H1:s,) the random mutual information between X and Y given history rounds of task s. Similarly, for random variables X, Y, and Z, we denote by (X: Y Z) = E (X;; ; Y Z, H1:,,) H1...d] the random mutual information between X and Y conditioned on Z, given history H1... It is helpful to think of I, as the conditional mutual information of X H1.s.1. Y H1 and Z H
and the
Hise,t of all observations from the first 1 tasks and the first
Let T s.t and c, be potentially history- deseede-d non-negative random variables such that
E,, (A.s)) & s (O.. Asts Vs,)) ) + Ex.t
(3)
5

---

holds almost surely. We want to keep both s. and cx,t "small". The following lemma provides bound on the total regret over n rounds in each of tasks in terms of T s, and Ex,
Lemma 2. Suppose that (3) holds for all [m] and E [n], for some T C..t 2 O. In addition, ler (T (Tm) and I be non-negative constants such that ee, S r I holds for all s E [m]] and
t [n] almost surely. Then
R(m, n) S I' P Him) + Σ Drayn (1 (00000.iH Ho pe: 11:--1
+
E [ec,a]
The first term above is the price for learning je,, while the second is the price for learning all 8s,- when μt, is known. Accordingly, the price for learning μs, is negligible when the mutual information terms grow slowly with and n. Specifically, we show shortly in linear bandits that I' and e,, can be set so that the last term of the bound is comparable to the rest, while a, grows slowly with m and n. At the same time, [ju,; H Hmm) and ( H. Me, H1s--) 1) are only logarithmic in and
n. Thus the price for learning μsa is Õ ((/m)) while that for learning all 0s.. O(m/n). Now we ready to prove Lemma 2.
Proof. First, we use the chain rule of random conditional mutual information and derive
(Os,s Astt Ys,)) S T (O,,, Mas Astt Ys,,) = Ts,e(1an; As,, Yua) + [S,,(s,, As,t, Va, [1...
Now take the square root of both sides, apply Va Va+ba bbb S va vā to the right-hand side, and multiply both sides by st, This yields
I Ta.y/I A.t. Yo,) S T Taa//aclumi A.t. Yo.) + I +T.. Ag,, Yo, pc)- We start with the second term in (4). Fix task From a, S T,, followed by the Cauchy-Schwar and Jensen's 's incqualities, we have
(4)
E Σ T (O,ns Acst Vs,t 1ba)
ST, nE Σ
Ts,,(0n,ni Aass Vo, Ma)
Thanks to E [I,, ((,. Ag,, Ye,l [x)] I I(0 As,t, 1, Ye. Mxx H1s5,) and the chain rule of mutual information, we have 1Ei=1 (0,e(0,, A Yo, u.)l = I(O,, / fr, H1:s-1).
Now we consider the first term in (4). We bound r x, using I, then apply the Cauchy- Schwarz and Jensen's 's inequalities, and obtain E Σ 8=1 Er=1 I Teoy Ioo La. A.., Yo.) S Tm/mll(u; H1m);
where we used the chain rule to get
E
Σ
Tan Aut, Ys.t)
ΣΣ Σ
Iuus An,, Yo. H1ss)) = I Tuu: H1m)
This completes the proof.
4.2 Linear Bandit with Gaussian Rewards
Now we derive regret bounds for linear bandits (Section 3.2). Without loss of generality, we make an assumption that the action set bounded.
Assumption 1. The arms vectors in unit ball, max.5A ||l|2 S 1.
Our analysis is for AdaTS with a small amount forced exploration in each task. This guarantees that our estimate of μ.a improves uniformly in all directions after each task s. Therefore, we assume that the action set is diverse enough to explore in all directions.
Assumption 2. There exist arms {a: ) S A such that Ae a:a ) 2 foror some >> 0.
This assumption is without loss of generality. particular, such set does not exist, the action set A can be projected into lower dimensional space where the assumption holds. AdaTS is modified follows. In each task, we initially pulls the arms {ar) to explore all directions.

---

We start by showing that (3) holds for suitably "small" s.t and Es,t- In AdaTS, in round of task the posterior distribution of 0,,, is (ps,, Eg,e), where
(Eo E.) Ag +
A
Ae.t Da.e (Eo -.)
= (Zo+ E.)
and ñ. and Σ, defined in Section 3.2. Then, from the properties of Gaussian distributions and that AdaTS samples from the posterior, we get a bound on Te, and Cx,t as a function of a tunable parameter 8 (0, 1].
Lemma 3. For all tasks E [m]] rounds E [n], and any & E (0, 11, (3) holds almost surely for
2 max (eet
se. 4V log(1 + o max o/22)
log log (1))) Ex,t = v 220o (Eag)) 28, B,,, 1|2],
where Eat is the indicator of forced exploration in round of task 8. Moreover, for each task 8, the following iestoryindeeenndent bound holds almost surely.
(1 (1 +1+ (2.
(1 (Eo) + 0² 8Y8 (Zng)
Paax(En.) S (Zo)
(5)
Lemma 3 is proved in Appendix C.3. By using the bound in (5), we get that Te. = O( Oloog((1/) and c,tt O(v8). Lemma 3 differs from Lu and Van Roy [33] in two aspects. First, it considers uncertainty in the estimate of μ4, along with 8z... Second, does not require that the rewards are bounded. Our next lemma bounds the mutual information terms in Lemma 2, by exploiting the hierarchical structure of our linear bandit model (Figure 1).
Lemma 4. For any HIss 1is, -ddapeed action sequence and any s [m]] we have
I(0 He! phx, H1: $ log (1+A AL(T))m) I(ur: H1:)) S log (1+
(1 )m
Now we are ready to prove our regret bound for the linear bandit. We take the nnuuual-ifformation bounds from Lemma 4, and the bounds on I'stt and 6s,t from Lemma and plug them into Lemma 2. Specifically, a
< >1 (Eg) + A1 (Eo) holds for any s and by Lemma 3, which yields I in Lemma 2. On the other hand, I, is bounded using the upper bound in (5), which relies foreed exploration. Our regret bound is stated below. The terms e₁ to C4 are at most polylogarithmic in d, m, and n;; and thus small. The term 02 arises due to summing up n over all tasks 8.
Theorem 5 (Linear bandit). The regret of AdaTS is bounded for any 8 (0, 1] as
R(m, n) s Cdvn + (m + 02) P.
Cydm Forced explovation
Learning bs.
Per-tark regret
where
8 log
- (E,)
log(41A1/8)log log
(E,), 1
o²
02 (1+ -2=(1
7² log m. and C3 2 M tr(C. + En). The per-task regret bounded as (Eo)
Ro(n;Ma) S cs dn
+ 225 where
(1 (Sa)
log(4[A1/6) log
AL o²
log
1+ o
The bound in Theorem 5 is sublinear in n for 8 = 1/n2. It has three terms. The first term is the regret due to learning μs, over all tasks; and it is ((Vdm)). The second term is the regret for acting in tasks under the assumption that μe, is known; and it is Ómn dn). The last term is the regret for
7

---

forced exploration; and it is O(dm). Overall, the extra regret due to unknown is D(Vdmn + dm) and is much lower than Om dn) when d < Therefore, call AdaTS no-regret algorithm for linear bandits. Our bound also reflects the fact that the regret decreases as both priors become more informative, A (Eo) + 0 and A (En) + O.
A frequentist regret bound for linear TS with finitely-man many arms is O(dyn) [3]. When applied to tasks, it would be ((dmy/) and is worse by factor of vd than our regret bound. To show that our bound reflects the structure of our problem, we compare AdaTS to two variants of linear TS that each task. The first variant knows μt, and thus has more information. Its regret can bounded by setting C1 = C2 Cg = 0 in Theorem and is lower than that of AdaTS. The second variant knows that μr, ~ (N(g 2qg but does not model that the tasks share fa.- This is analogous to assuming that 0,,- ~ (( Mng + Eo). The regret of this approach can be bounded by setting 6j = C2 = C3 0 in Theorem 5 and replacing A (2o) in o by A + Eg). Since the task regret increases linearly with m and Y (2i, + Mo) > (Mo), this approach would ultimately have higher regret than AdaTS as the number of tasks m increases.
applied independently
4.3
with Gaussian Rewards
In semiibandits (Section 3.3), we use the independence arms to decompose the per-round regret differently. Similarly to Section 4.2, we analyze AdaTs with forced exploration, where each arm is initially pulled at least once. This is always possible in at most K rounds, since there exists at least A that contains any given arm.
Let s.r (R)) and (k)) be non-negative history-dependent constants, for each arm [K], were we use (k) to refer to arm-specific quantities. Then an analogous bound to (3) is
Σ Ps E Autt) (Ta:((t) (T..)) (k)( (s,((k)) RE(K]
F., S
The term (ks, (k)) is a tuple a pulled arm and its observation in round of task s. For any k from the chain rule of mutual information, have
(O,, (k)); k (k)) S I,,((, k, Y. (k)) + (e.. k. (k)) (.(k)).
Next we combine the mutual-inffrratioo terms across rounds and tasks, as in Lemma 2, and bound corresponding s.,(()) (k) and es, (k) independently of m and n. Due to forced exploration, the estimate of μr, (k) improves for all arms as more tasks are completed, and T (kk) decreases with 8.
This leads to Theorem 6, which is proved in Appendix D.
Theorem (Semi-bandice The regret of AdaTS is bounded for any E (0,1)as
R(m, n) S Ci LLVLL + (m + 02) (s(n;;))) + Learning p.
c3 C2K3/2 3/2
+ c4o v 2ômn,
Por-tack regret
Forced exploration
where
Σ
tott 0 1+ oi +o
m log(4K/8)log (1+
C1
K
t02
kE(K] log
max
log m
= Σ
(n + 022 + og
kE kE(K))oooN>0
Cokk
KE(K]
oaam log (1+
C1
kE[K] =
The per-task regret is bounded Ro(n; S C5 KLV + V 26 ExE(K ob n, where
Σ
log(4K/8) log (1 2ban
C3
kE log
1+
To.k
The prior widths a. and 0o,k defined as in Section 3.1.

---

Gaussian 0.5001
Gaussian 1.000)
2. 1.000)
160
OracieTS
140
300
120
250
Regret
MetaTS
100
200
100
AdoTS
150
50
100
50
0
10
15
20
0
5
10
15
20
0
5
10
15
20
Task
Task
Task s
Figure 2: Comparison of AdaTS to three baselines on three bandit problems.
The bound in Theorem 6 is sublinear for 1/n2". Its form resembles Theorem 5. Specifically, the regret for learning μl, Ö( K Lmm) and for forced exploration is Ō(K*/mm). Both these are much lower than the regret for learning to act in m tasks when jr, is known, (m)) for K < Ln. Therefore, AdaTS is also no-regret algorithm for cami-bandits.
Theorem improves upon a naive application Theorem to emmi-bandits. This is because all prior width constants are averages, opposing to the maximum over arms in Theorem 5. To the best of our knowledge, such per-arm prior dependence has not been captured in emii-aandits by any prior work. To illustrate the difference, consider problem where 0o, > 0 for only K' < K arms. This means that only K' arms uncertain in the tasks. Then the bound in Theorem 6 is Ö(m KanekKiInn (I)), while the bound in Theorem would be (tn/KLn) For the arms k where Jo.k O, the regret over all tasks is sublinear in m.
5 Experiments
experiment with two synthetic problems. both problems, the number of tasks m 20 and each task has 200 rounds. The first problem is Gaussian bandit (Section 3.1) with K 2 arms. The meta-prior is (O, Eg) with Eg = IK. . the prior covariance is Σo = dāIk. and the reward noise is 1. We experiment with 0g 0.5 and do 0.1. Since og > do. the entries of 0,p- likely to have the same order as in ul. Therefore, a clever algorithm that learns μıa could have very low regret. The second problem is linear bandit (Section 3.2) in d 2 dimensions with K 5d arms. The action set is sampled from a unit sphere. The meta-prior, prior, and noise are the same as in the Gaussian bandit. All results are averaged over 100 runs.
AdaTS is compared to three baselines. The first is idealized TS with the true prior W(n,; Σn) and we call it OracleTS, OracleTS shows the minimum attainable regret. The second is agnostic TS, which ignores the structure of the problem. We call TS and implement it with prior N(, X, + En), since sample from this prior when the structure is ignored (Section 4.2). The third
B,,, can be viewed bascline is MetaTS of Kveton et al. [28]. All methods are evaluated by their cumulative regret up to task which we plot accumulates round-by-roum within each task (Figure 2). The regret of the algorithms that do not learn 14. (OracleTT and TS) is obviously linear in s, as they solve s similar tasks with the same policy (Section 2). A lower slope indicates a better policy. As no algorithm can outperform DracleTS, no regret can grow sublinearly in s.
Our results are reported in Figure 2. We start with Gaussian bandit with 0,, = 0.5. This setting is identical to Figure 1b Kveton al. [28]. We observe that AdaTS outperforms TS, which does not learn μ.,. and is comparable to OracleTS, which knows f.. Its regret is about 30% lower than that of MetaTS. Now increase the meta-prior width to = 1. this setting, meta-parameter sampling in MetaTS leads to high biases in earlier tasks. This leads to major increase in regret, while AdaTS performs comparably to DracleTS. We end with linear bandit with 0g = 1. In this experiment, AdaTS outperforms MetaTS again and has more than three times lower regret.
OracleTS
ACOTS MetaTS
Task
Task
Task
Tosk
Task
Appendix E contains more experiments. In Appendix 1. we exper- iment with more values of K and d, and show the robustness of AdaTS to missspecified meta-prior Q. In Appendix E.2, apply AdaTS to
Figure 3: Meta-learning of highly rewarding digit 1.

---

bandit classification problems. In Figure 3, we show results for one of these problems, meta-learning a highly rewarding digit the bandit setting. For each method and task s, we show the average digit corresponding to the pulled arms in round of task 8. AdaTS learns good meta meta-parameter fs, almost instantly, since its average digit in task 2 already resembles digit
Related Work
Two closest related works are Bastani et al. [6] and Kveton et al. [28]. Bastani et al. [6] proposed Thompson sampling that learns the prior from a sequence of pricing experiments. The algorithm is tailored to pricing and learns through forced exploration using conservative TS. Therefore, it is conservative. Bastani et al. [6] also did not derive prior-dependent bounds.
Our studied setting is identical to Kveton et al. [28]. However, the design of AdaTS is very different from MetaTS. MetaTS samples the meta-parameter μt, at the beginning of each task a and uses to compute the posterior of the task parameter Os... Since μs is fixed within the task, MetaTS does not have a correct posterior of a,,, given the history. AdaTS marginalizes out the uncertainty in the meta- parameter μl and thus has correct posterior of 0z,- within the task. This seemingly minor difference leads to an approach that is more principled, comparably general, has a Kully-Baeesian analysis beyond multi-armed bandits, and may have several-fold lower regret in practice. While it is possible that the analysis of MetaTS could be extended to linear bandits, the price for meta-learning would likely remain Ó m.)) This cost arises due sampling the meta parameter μl at the beginning of each task 8. The price of meta-learning in our work is mere Ō ((/m)), a huge improvement.
AdaTS is meta-learning algorithm [39, 40, 7, 8. 17, 18]. Meta-learning has long history in multi- armed bandits. Some the first works are Azar et al. [5] and Gentile et al. [21]. who proposed UCB algorithms for multi-task learning. Deshmukh et al. [15] studied multi-task learning in contextual bandits. Cella et al. [10] proposed UCB algorithm that meta-learss the mean parameter vector in a linear bandit, which is akin learning μl, in Section 3.2. Another recent work is Yang al. [43], who studied regret minimization with multiple parallel bandit instances, with the goal of learning their shared subspace. All of these works are frequentist, analyze stronger notion of regret, and often lead to conservative algorithm designs. In contrast, we leverage the fundamentals Bayesian reasoning to design a general-pune purposs algorithm that performs well when as analyzed.
Several recent papers approached the problem of learning a bandit algorithm using policy gradients [16, 9, 27, 44, 35], including learning Thompson sampling [27, 35]. These works focus offline optimization against a known bandit-instance distribution and have no convergence guarantees in general [9, 27]. Tuning of bandit algorithms is known to reduce regret [41, 34, 24, 23J. Typically it is ad-hoc and we believe that meta- meta-lcarning is a proper way of framing this problem.
7 Conclusions
We propose AdaTS, fully-Bayesian algorithm for meta-learning in bandits that adapts sequence of bandit tasks that it interacts with. AdaTS attains low regret by adapting the uncertainty in both the meta and per-task parameters. We analyze the Bayes regret of AdaTS using information-theon tools that isolate the effect of learning the meta-parameter from that of learning the per-task parameters. For linear bandits and mani-sandits, we derive novel prior-dependent regret bounds that show that the price for learning the meta-pant peota-parmmttr is low. Our experiments underscore the generality of AdaTS, good of--of-the--eeeee performance, and robustness to meta--rior misspecification.
We leave open several questions of interest. For instance, except for Section 3.4, our algorithms are for Gaussian rewards and priors, and so are their regret analyses. An extension beyond Gaussians would be of both practical and theoretical value. Our current work also relies heavily on a particular parameterization of tasks, where the mean 0,, is unknown but the covariance Eo is known. It is not immediately obvious if a compurationally-effiiiie extension to unknown Eg exists.
10

---

References
[1] Yasin Abbasi-Yaunn Yadkori, David Pal, and Csaba Szepesvari. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems 24, pages 2312-2320 2011.
[2] Shipra Agrawal and Navin Goyal. Analysis of Thompson sampling for the multi-armed bandit problem. In Proceeding of the 25th Annual Conference on Learning Theory, pages 39.1-39.26, 2012.
[3] Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoff's. In Proceedings of the 30th International Conference on Machine Learning, pages 127-135, 2013.
[4] Peter Auer, Nicolo Cesa-Bianchi. and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47:235-2555 256, 2002.
[5] Mohammad Gheshlaghi Azar, Alessandro Lazaric, and Emma Brunskill. Sequential transfer in multi-armed bandit with finite of models. In Advances in Neural Information Processing Systems 26, pages 2220-2228, 2013.
[6] Hamsa Bastani, David Simchi-Levi, and Ruihao Zhu. Meta dynamic pricing: Transfer learning across experiments. CoRR, abs/1902.10018, 2019. URL https:://aa.i...rrggge//o 1902. 10918.
[7] Jonathan Baxter. Thcoretical models learning to learn. In Learning to Learn, pages 71-94. Springer, 1998.
[8] Jonathan Baxter. model of inductive bias learning. Journal of Artificial Intelligence Research, 12:149-199 2000.
[9] Craig Boutilier, Chih- Wei Hsu, Branislav Kveton, Martin Mladenov, Csaba Szepesvari, and Manzil Zaheer. Differentiable meta meta-learming of bandit policies. In Advances in Neural Informa- tion Processing Systems 33, 2020.
[10] Leonardo Cella, Alessandro Lazaric, and Massimiliano Pontil. Meta-learning with stochastic linear bandits. In Proceedings the 37th International Conference Machine Learning, 2020.
[11] Olivier Chapelle and Lihong Li. An empirical evaluation Thompson sampling. In Advances in Neural Information Processing Systems 24, pages 2249-2257, 2012.
[12] Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework, results and applications. In Proceedings of the 30th International Conference on Machine Learning, pages 151-159, 2013. 2013.
[13] Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. CORR, abs/1407. 8339, 2014. URL htt.t:t//aaixi..rrrr./t/ abs/ 1055/1400 1407_ 8339.
[14] Varsha Dani, Thomas Hayes, and Sham Kakade. Stochastic linear optimization under bandit feedback. In Proceedings of the 21 Annual Conference on Learning Theory, pages 355-366, 2008.
[15] Aniket Anand Deshmukh, Urun Dogan, and Clayton Scott. Multi-task learning for contextual bandits. In Advances in Neural Information Processing Systems 30, pages
2017.
[16] Yan Duan, John Schulman, Xi Chen, Peter Bartlett, Ilya Sutskever, and Pieter Abbeel. RL2: Fast reinforcement learning via slow reinforcement learning. CoRR, abs/1611.00279, 2016. URL
org/ httg/abs///1ll 02779.
[17] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adap- tation of deep networks. In Proceedings of the 34th International Conference on Machine Learning, pages 1126-1135, 2017.
11

---

[18] Chelsea Finn, Kelvin Xu, and Sergey Levine. Probabilistic model-agnostic meta-learning In Advances in Neural Information Processing Systems 31, pages 9537-9548, 2018.
[19] Yi Gai, Bhaskar Krishnamachari, and Rahul Jain. Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations. IEEE/ACM Transactions on Networking, 2065):1466-144 14766,1148.1110 2012.
[20] Andrew Gelman, John Carlin, Hal Stern, David Dunson, Aki Vehtari, and Donald Rubin. Bayesian Data Analysis. Chapman & Hall, 2013.
[21] Claudio Gentile, Shuai Li, and Giovanni Zappella. Online clustering of bandits. In Proceedings of the 31st International Conference on Machine Learning, pages 757-765, 2014.
[22] Joey Hong, Branislav Kveton, Manzil Zaheer, Yinlam Chow, Amr Ahmed, and Craig Boutilier. Latent bandits revisited. In Advances in Neural Information P Processing Systems 33, 2020.
[23] Chih-Wei Hsu, Branislav Kveton, Ofer Meshi, Martin Mladenov, and Csaba Szepesvari. Empir- ical Bayes regret minimization. CoRR, abs/1904. 02664, 2019. URL http://arxxv..rrg abs/ 9904, 02664.
[24] Volodymyr Kuleshov and Doina Precup. Algorithms for multi-armed bandit problems. CoRR, abs/1402 40b//140,.608, 2014. URL http::h//// arxiv. arg/abs// 1402.. 6028.
[25] Branislav Kveton, Zheng Wen, Azin Ashkan, Hoda Eydgahi, and Brian Eriksson. Matroid bandits: Fast combinatorial optimization with learning. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, pages 420 0200429,.40 2014.
[26] Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Tight regret bounds for stochastic combinatorial semi-bandits. In Proceedings of the 18th International Conference Artificial Intelligence and Statistics, 2015.
[27] Branislav Kveton, Martin Mladenov, Chih- Wei Hsu, Manzil Zaheer, Csaba Szepesvari, and Craig Boutilier. Differentiable meta-learning in contextual bandits. CoRR, abs/2006.05094, 2020. URL httt:://aakten org als/ 22006 05094.
[28] Branislav Kveton, Mikhail Konobeev, Manzil Zaheer, Chih-War Hsu, Martin Mladenov, Craig Boutilier, and Csaba Szepesvari. Meta- Thea--hhompson sampling. In Proceedings of the 38th International Conference on Machine Learning. 2021.
[29] T. L. Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4-22, 1985.
[30] Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 350(62666 2015.
[31] Tor Lattimore and Csaba Szepesvari. Bandit Algorithms. Cambridge University Press, 2019.
[32] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. A7T Labs [Online]. Available: http://yann.ee www.yaann..eeu....m wwwwn. compe///////xxsisttt.... 2, 2010.
[33] Xiuyuan Lu and Benjamin Van Roy. Information-theorctt confidence bounds for reinforcement learning. In Advances in Neural Information Processing Systems, volume 32, 2019.
[34] Francis Maes, Louis Wehenkel, and Damien Erost. Meta-learning of exploration//xplootaiii strategies: The multi-armed bandit case. In Proceedings of the 4th International Conference on Agents and Artificial Intelligence, pages 100-115, 2012.
[35] Scungki Min, Ciamac Moallemi, and Daniel Russo. Policy gradient optimization of Thompson sampling policies. CoRR, abs/2006.16507,, 2020. URL
org harg/abba abss///////// 2006.
1 16507.
[36] Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 19(4))1221-1244 2014.
12

---

[37] Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, lan Osband, and Zheng Wen. A tutorial on Thompson sampling. Foundations and Trends in Machine Learning. 11(1):1-96, 2018.
[38] 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.
[39] Sebastian Thrun. Explanation- Bassdd Neural Network Learning Lifelong Learning Approach. PhD thesis, University Bonn, 1996.
[40] Sebastian Thrun. Lifelong learning algorithms. In Learning to Learn, pages 181-209. Springer, 1998.
[41] Joannes Vermorel and Mehryar Mohri. aanti-armed bandit algorithms and empirical evaluation. In Proceedings of the 16th European Conference on Machine Learning, pages 437-448, 2005.
[42] Zheng Wen, Branislav Kveton, and Azin Ashkan. Efficient learning in large-scale combinatorial semi-bandits. In Proceedings of the 32nd International Conference on Machine Learning, 2015.
[43] Jiaqi Yang, Wei Hu, Jason Lee, and Simon Du Provable benefits of representation learning in linear bandits. CoRR, abs/2010.06531, 2020. URL http:// /arxiv..//araiee//a/eaeee.a.i wwtp:/wwwwww.////////e.////// 06531.
[44] Kaige Yang and Laura Toni. Differentiable linear bandit algorithm. CoRR, abs/2006.03000 2020. URL http: / /awxivvvvvvv.////////a/////aaav/ org/ abs /006. 0300C.
13


Reviews:
[{"review_id": "fsRiw0Es7qB", "reviewer": "Reviewer_x5jf", "summary": "This work presents a Thompson sampling algorithm for the Bayesian \"meta-learning\" bandit problem, where bandit instances are drawn from a \"task\" distribution of known form with unknown location parameter, itself drawn from a known meta-prior.\n\nThe key ideas in the proposed AdaTS algorithm are\n1. to maintain a distribution over the unknown task prior parameter, and\n2. to marginalize such uncertainties by learning, across instances, a posterior over it.\n\nLeveraging hierarchical Bayesian modeling and conjugate priors, the authors present AdaTS, with implementations for multi-armed/linear bandits and combinatorial semi-bandits.\n\nBayesian regret bounds for the $n$-round $m$-instance AdaTS are shown to be of order $O(\\sqrt{mn})$.\n\nExperiments on synthetic datasets illustrate the added benefits of the proposed approach.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The authors present a hierarchical view of the \"meta-learning\" bandit problem and leverage the Bayesian modeling toolkit and Thompson sampling to propose AdaTS.\n\nThe work is very clearly presented, with a concise introduction (Section 1), problem setting (Section 2) and algorithm (Section 3) presentations.\n\nThe novelty of Proposition 1 (and its proof) is unclear, as it looks like a direct (sequential) application of Bayes rule. Similarly, even though they state that equations in Sections 3.2 and 3.3 are due to Kveton et al. [27], these appear to be a direct application of the conjugate prior based analysis of the Gaussian likelihood (e.g., https://en.wikipedia.org/wiki/Conjugate_prior#When_likelihood_function_is_a_continuous_distribution).\n- I would encourage the authors to explain/justify whether these are direct results of Gaussian conjugate prior based Bayesian posterior updates, or if there is any technical novelty on the presented content. \n\nAdaTS is proposed in Algorithm 1, whose originality lies on realizing that the parameter sampling step introduced by MetaTS [27] introduces high variance, which can be avoided via marginalization. In other words, the authors leverage Rao-Blackwellization (well known in the estimation theory community) to improve upon an existing algorithm that leads to tighter regret bounds and better empirical performance.\n\nSection 4 contains the theoretical analysis of the proposed algorithm, which is an information-theoretic technique that adapts the analysis of [32] to derive and proof Lemma 2: a general bound on AdaTS that conveys the price of not knowing the task prior parameter $\\mu^*$ and the regret when $\\mu^*$ is known.\n\n- A minor comment on the proof presentation of Section 4 is that in equation (3) the expectation has subscripts $s$ and $t$, to probably indicate the probability distribution over which this expectation is taken, but has not been previously defined (this is the only case where expectation is denoted with subscripts). \n\nThe authors then proceed to bound the key regret terms for the linear bandit (Section 4.2) and Gaussian semi-bandit cases (Section 4.3). The authors provide an explanation of the proof approach, and discuss the impact of priors (as a function of both the meta-prior and the task-prior parameters), showing that the price of not knowing the task-prior parameter is \"small\".\n\nThe experiments section showcases the benefits of the proposed approach, as\n1. the hierarchical modeling allows for learning across instances, and\n2. marginalization improves regret.\n\n- Since all the studied algorithms are Thompson sampling based, a suggestion here would be to consider some of the UCB-based metalearning algorithms discussed in Section 6.\n\nA final comment relates to the fact that AdaTS requires knowledge of the reward variance parameters $\\Sigma_0$ (which should be explicitly indicated in Algorithm 1):\n- An open question (somehow related to the use of Bayesian posterior updates) is whether AdaTS could be extended to the unknown $\\Sigma_0$ variance case (as this would imply t-distributed task distributions).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss the limitations of a frequentist Vs Bayesian regret analysis point of view.\n\nThe authors should more clearly convey the necessary inputs to the proposed algorithm:\n- the form and variance parameters of the task distribution $P(\\cdot)$ ---besides the form and parameters of the meta-prior $Q$ already specified.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "Mkz_ngpVtcE", "reviewer": "Reviewer_PsGp", "summary": "The paper considers the meta Thompson Sampling problem with hierarchical structure. In particular, paper considers a setting where there are m-bandits instances and within each instance, there are n-time periods as well K-arms. Here, within an instance, the parameters of the distribution corresponding to arms are sampled from a common distribution, whose parameters themselves follow a prior distribution (hence the name meta). For this problem, the paper presents a Thompson Sampling algorithm, AdaTS and proves Bayesian Regret bounds under a few common prior distributions. The regret bounds of \\sqrt{mn} seems to improve over the existing state of the art regret bounds. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The main contribution I take away from the paper is that the paper presents a more efficient sampling algorithm that achieves improved regret bounds of O(\\sqrt{mn}) in comparison to existing bounds from O(n^2 \\sqrt{m}). While this seems to be an interesting and relevant contribution, I believe the technicality contributions of this paper are incremental, which I will elaborate below. Furthermore, the paper does not provide motivating application for this problem set up. Without the motivating application, it was extremely hard to understand the problem set up and how different layers interact with each other. Connection to a realistic application, would have helped the reader appreciate the improvements in regret bounds more. I also strongly believe there is a lot of room for improving the technical presentation.\n\n1. The issue of unknown \\mu* in the analysis. On page 2, the paper seems to indicate that if \\mu* is known, the existing technical machinery in Russo and Van Roy can be leveraged to obtain the regret of O(m\\sqrt{Kn}). It appears that the paper attempts to match this bound without knowing \\mu*. Recently, there is a growing literature on the min-max regret of Thompson Sampling algorithm for a wide range of reward distribution settings including the ones considered in the paper ( see [A],  [B], [C],  [D]). Given that min-max regret is a much stronger regret notion than the Bayesian Regret (i.e. Bayesian Regret would trivially follow from min-max regret) and the existing approaches do not require the knowledge of prior, why can't these approaches be trivially extended to the obtain the regret of O(m\\sqrt{Kn})? Does this explain why it is not surprising that we will have no regret even when \\mu* is unknown?\n\n2. Ignoring the hierarchical structure of the problem. In the introduction, the paper provides a vague example of how ignoring the structure could be sub-optimal under certain settings. However, in the context of above example, it seems like the goal is to obtain a regret bound of O(m\\sqrt{Kn}), isn't that inconsistent with the expectation that this is sub-optimal? The paper also does not specifically provide bounds for the standard bandit setting (with Bernoulli rewards) which made it harder for me to reconcile with the above inconsistency. I guess one can generalize the results for Linear bandit to the standard bandit setting with K-arms by considering a K-dimensional feature vector. However, the bounds in Theorem-5 does not seem to indicate any dependency on the dimension of the feature vector or number of arms, what am I missing here? \n\n3. Interpreting Theorem 5: Line 255 on page 7 mentions that mR_\\delta is bounded as O(m\\sqrt{n}). However, by line 258, the paper claims the bound is only O(\\sqrt{mn}). What am I missing?\n\n\n\n\n[A] S. Agrawal, N. Goyal, \"Further optimal regret bounds for Thompson Sampling\", In Proceedings of the 16th International Conference on Artificial Intelligence and Statistics (AISTATS), 2013\n\n[B] S. Agrawal, N. Goyal, \"Thompson Sampling for contextual bandits with linear payoffs\". In Proceedings of the 30th International Conference on Machine Learning (ICML), 2013.\n\n[C] S. Wang, W. Chen. Thompson Sampling for Combinatorial Semi-Bandits. In Proceedings of the 35th International Conference on Machine Learning, 2018.\n\n[D] K. Jun, A. Bhargava, R. Nowak, R. Willett. Scalable Generalized Linear Bandits: Online Computation and Hashing. Part of Advances in Neural Information Processing Systems 30 (NIPS 2017). ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Theory paper, no implications to society", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hrs"}, "extra_text": {}}, {"review_id": "KHamSBCuNUY", "reviewer": "Reviewer_7ezS", "summary": "This paper studies a variant of Thompson Sampling for meta-learning. By maintaining the distribution of the parameter of the prior distribution, the proposed algorithm can adapt to the certain task it encountered with. The authors also provide Bayesian regret bound for this algorithm. Experiments are provided to support their theoretical claim showing their algorithm can outperform benchmark algorithms.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "This paper is overall clear and easy to follow and the authors also provide some examples showing the proposed general algorithm can be adapted to several bandit settings. One minor concern I have is regarding the novelty of this paper. This work could be considered as a follow-up work of MetaTS[1], where MetaTS samples $\\mu_s$ and here the authors directly use the distribution of $\\mu_s$ then sample the rewards. These two sampling mechanisms are similar theoretically. Although the author claimed that the proposed sampling method would be more robust, in general cases, will it be more difficult to implement compared to MetaTS since it needs to handle the distribution over $\\mu_s$ explicitly? \n\nAnother question is, since the MetaTS does not provide the proof for linear gaussian bandits, I wonder if the proof technique of MetaTS can be applied to this work?\n\nDue to the contribution of this paper, I'd like to suggest marginally accept this paper.\n\n[1] Kveton, Branislav, et al. \"Meta-Thompson Sampling.\" International Conference on Machine Learning (ICML), 2021.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No potential social impact is found. Regarding the presentation for the proof techniques, I suggest the authors to highlight the connection between theirs and MetaTS's. For example, can the MetaTS proof technique can be used in this proof. If not, what's the major difficulty here?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies a meta learning for bandits problem, using a hierarchical Bayesian formulation. It proposes the AdaTS algorithm, which can be instantiated to Gaussian {multi-armed, linear, combinatorial semi} bandits, and more general exponential family bandits. 

Specialized to the Gaussian bandits setting, the proposed AdaTS algorithm improves over two baselines, including (1) the prior work of MetaTS, in its regret in learning the task prior parameter \mu_* from \sqrt{mn^2} to \sqrt{mn} (2) Thompson sampling without meta-learning, in that when the task prior is sufficiently concentrated and the meta prior is sufficiently "spread out". Empirical results clearly support the claims. One limitation of the current work is that it does not have theoretical results yet in the more general exponential family bandits setting (e.g. Bernoulli bandits). 
Decision: Accept (Poster)