No Regrets for Learning the Prior in Bandits
Year: 2022

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.

heading: 1 Introduction
text: We study the problem of maximizing the total reward, or minimizing the total regret, in a sequence of stochastic bandit instances [29, 4, 31]. We consider a Bayesian version of the problem, where the bandit instances are drawn from some distribution. More specifically, the learning agent interacts with m bandit instances in 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 i ∈ [K] in task s ∈ [m] is pi(·; θs,∗), where θs,∗ is a shared parameter of all arms in task s. When arm i is pulled in task s, the agent receives a random reward from pi(·; θs,∗). The parameters θ1,∗, . . . , θm,∗ are drawn independently of each other from a task prior P (·;µ∗). The task prior is parameterized by an unknown meta-parameter µ∗, which is drawn from a meta-prior Q. The agent does not know µ∗ or θ1,∗, . . . , θm,∗. However, it knows Q and the parametric forms of all distributions, which help it to learn about µ∗. This is a form of meta-learning [39, 40, 7, 8], where the agent learns to act from interactions with bandit instances.
A 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 1 is optimal for any θ in the support of P (·;µ∗). If µ∗ was known, any reasonable algorithm would only pull arm 1 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 a 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 µ∗?
We make the following contributions. First, we propose a Thompson sampling algorithm for our problem, which we call AdaTS. AdaTS maintains a distribution over the meta-parameter µ∗, which concentrates over time and is marginalized out when interacting with individual bandit instances. Second, we propose computationally-efficient implementations of AdaTS for multi-armed bandits [29, 4], linear bandits [14, 1], and combinatorial semi-bandits [19, 13, 26]. These implementations are for specific reward distributions and conjugate task priors. Third, we bound the n-round Bayes regret of AdaTS in linear bandits and semi-bandits, and multi-armed bandits as a special case. The Bayes regret is defined by taking an expectation over all random quantities, including µ∗ ∼ Q. Our bounds show that not knowing µ∗ has a minimal impact on the regret as the number of tasks grows, of only Õ( √ mn). This is in a sharp contrast to prior work [28], where this is Õ( √ mn2). Finally,
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
our experiments show that AdaTS quickly adapts to the unknown meta-parameter µ∗, is robust to meta-prior misspecification, and performs well even in 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 are 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 in advance.

heading: 2 Setting
text: We first introduce our notation. The set {1, . . . , n} is denoted by [n]. The indicator 1{E} denotes that event E occurs. The i-th entry of vector v is vi. If the vector or its index are already subindexed, we write v(i). We use Õ for the big-O notation up to polylogarithmic factors. A diagonal matrix with entries v is denoted diag (v). We use the terms “arm” and “action” interchangeably, depending on the context.
Our setting was proposed in Kveton et al. [28] and is defined as follows. Each bandit problem instance has K arms. Each arm i ∈ [K] is defined by distribution pi(·; θ) with parameter θ ∈ Θ. The parameter θ is shared among all arms. The mean of pi(·; θ) is denoted by r(i; θ). The learning agent interacts with m instances, one at each of m tasks. At the beginning of task s ∈ [m], an instance θs,∗ ∈ Θ is sampled i.i.d. from a task prior P (·;µ∗), which is parameterized by µ∗. The agent interacts with θs,∗ for n rounds. In round t ∈ [n], it pulls one arm and observes a stochastic realization of its reward. We denote the pulled arm in round t of task s by As,t ∈ [K], the realized rewards of all arms in round t of task s by Ys,t ∈ RK ,
and the reward of arm i ∈ [K] by Ys,t(i) ∼ pi(·; θs,∗). We assume that the realized rewards Ys,t are i.i.d. with respect to both s and t. A graphical model of our environment is drawn in Figure 1. We define the distribution-specific parameters µq, Σq, Σ0, and σ2 when we instantiate our framework. Our terminology is summarized in Appendix A.
The n-round regret of an agent or algorithm over m tasks with task prior P (·;µ∗) is defined as
R(m,n;µ∗) = m∑ s=1 E [ n∑ t=1 r(As,∗; θs,∗)− r(As,t; θs,∗) ∣∣∣∣∣µ∗ ] , (1)
where As,∗ = arg max i∈[K] r(i; θs,∗) is the optimal arm in the random problem instance θs,∗ in task s ∈ [m]. The above expectation is over problem instances θs,∗ ∼ P (·;µ∗), their realized rewards, and also pulled arms. Note that µ∗ is fixed. Russo and Van Roy [36] showed that the Bayes regret, which matches the definition in (1) in any task, of Thompson sampling in a K-armed bandit with n rounds is Õ( √ Kn). So, when TS is applied independently in each task, R(m,n;µ∗) = Õ(m √ Kn).
Our goal is to attain a comparable regret without knowing µ∗. 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 a meta-prior. Accordingly, we consider R(m,n) = E [R(m,n;µ∗)] as a metric and call it the Bayes regret. Our approach is motivated by hierarchical Bayesian models [20], where the uncertainty in prior parameters, such as µ∗, is represented by another distribution, such as Q. In these models, Q is called a hyper-prior and µ∗ is called a hyper-parameter. We attempt to learn µ∗ from sequential interactions with instances θs,∗ ∼ P (·;µ∗), which are also unknown. The agent can only observe their noisy realizations Ys,t.

heading: 3 Algorithm
text: 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 Hs = (As,t, Ys,t(As,t))nt=1 the history in
Algorithm 1 AdaTS: Instance-adaptive exploration in Thompson sampling. 1: Initialize meta-prior Q0 ← Q 2: for s = 1, . . . ,m do 3: Compute meta-posterior Qs (Proposition 1) 4: Compute uncertainty-adjusted task prior Ps (Proposition 1) 5: for t = 1, . . . , n do 6: Compute posterior of θ in task s, Ps,t(θ) ∝ Ls,t(θ)Ps(θ) 7: Sample θ̃s,t ∼ Ps,t, pull arm As,t ← arg max i∈[K] r(i; θ̃s,t), and observe Ys,t(As,t)
task s and by H1:s = H1 ⊕ · · · ⊕Hs a concatenated vector of all histories in the first s tasks. The history up to round t in task s is Hs,t = (As,`, Ys,`(As,`))t−1`=1 and all history up to round t in task s is H1:s,t = H1:s−1 ⊕Hs,t. We denote the conditional probability distribution given history H1:s,t by Ps,t(·) = P (· |H1:s,t) and the corresponding conditional expectation by Es,t[·] = E [· |H1:s,t]. Our algorithm is a form of Thompson sampling [38, 11, 2, 37]. TS pulls arms proportionally to being optimal with respect to the posterior. In particular, let Ls,t(θ) = ∏t−1 `=1 pAs,`(Ys,`(As,`); θ) be the likelihood of observations in task s up to round t. If the prior P (·;µ∗) was known, the posterior of instance θ in round t would be P TSs,t(θ) ∝ Ls,t(θ)P (θ;µ∗). TS would sample θ̃t ∼ P TSs,t and pull arm At = arg max i∈[K] r(i; θ̃t).
We address the case of unknown µ∗. The key idea in our method is to maintain a posterior density of µ∗, which we call a meta-posterior. This density represents uncertainty in µ∗ given history. In task s, we denote it by Qs and define it such that P (µ∗ ∈ B |H1:s−1) = ∫ µ∈B Qs(µ) dκ1(µ) holds for any set B, where κ1 is the reference measure for µ. We use this more general notation, as opposing to dµ, because µ can be both continuous and discrete. When solving task s, Qs is used to compute an uncertainty-adjusted task prior Ps, which is a posterior density of θs,∗ given history. Formally, Ps is a density such that P (θs,∗ ∈ B |H1:s−1) = ∫ θ∈B Ps(θ) dκ2(θ) holds for any set B, where κ2 is the reference measure for θ. After computing Ps, we run TS with prior Ps to solve task s. To maintain Qs and Ps, we find it useful expressing them using a recursive update rule below. Proposition 1. Let Ls(θ) = ∏n `=1 pAs,`(Ys,`(As,`); θ) be the likelihood of observations in task s. Then for any task s ∈ [m],
Ps(θ) = ∫ µ P (θ;µ)Qs(µ) dκ1(µ) , Qs(µ) = ∫ θ Ls−1(θ)P (θ;µ) dκ2(θ)Qs−1(µ) .
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 s depends on history H1:s,t. The pseudocode of our algorithm is in Algorithm 1. Since the algorithm adapts to the unknown task prior P (·;µ∗), we call it AdaTS. AdaTS can be implemented efficiently when Ps is a conjugate prior for rewards, or a 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-posterior Qs. The difference is that MetaTS samples µ̃s ∼ Qs in task s to be optimistic with respect to the unknown µ∗. Then it runs TS with prior P (·; µ̃s). While simple and intuitive, the sampling of µ̃s induces a high variance and leads to a conservative worst-case analysis. We improve MetaTS by avoiding the 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).

heading: 3.1 Gaussian Bandit
text: We start with a K-armed Gaussian bandit with mean arm rewards θ ∈ RK . The reward distribution of arm i is pi(·; θ) = N (·; θi, σ2), where σ > 0 is reward noise and θi is the mean reward of arm i. A natural conjugate prior for this problem class is P (·;µ) = N (·;µ,Σ0), where Σ0 = diag ( (σ20,i) K i=1 ) is known and we learn µ ∈ RK . Because the prior is a multivariate Gaussian, AdaTS can be implemented efficiently with a Gaussian meta-prior Q(·) = N (·;µq,Σq), where µq = (µq,i)Ki=1 and Σq = diag ( (σ2q,i) K i=1 ) are known mean
parameter vector and covariance matrix, respectively. In this case, the meta-posterior in task s is also a Gaussian Qs(·) = N (·; µ̂s, Σ̂s), where µ̂s = (µ̂s,i)Ki=1 and Σ̂s = diag ( (σ̂2s,i) K i=1 ) are defined as
µ̂s,i = σ̂ 2 s,i ( µq,i σ2q,i + s−1∑ `=1 T`,i T`,i σ20,i + σ 2 B`,i T`,i ) , σ̂−2s,i = σ −2 q,i + s−1∑ `=1 T`,i T`,i σ20,i + σ 2 . (2)
Here T`,i = ∑n t=1 1{A`,t = i} is the number of pulls of arm i in task ` and the total reward from
these pulls is B`,i = ∑n t=1 1{A`,t = i}Y`,t(i). The above formula has a very nice interpretation. The posterior mean µ̂s,i of the meta-parameter of arm i is a weighted sum of the noisy estimates of the means of arm i from the past tasks B`,i/T`,i 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 a higher weight. They vary from (σ20,i + σ
2)−1, when the arm is pulled only once, up to σ−20,i . This is the minimum amount of uncertainty that cannot be reduced by more pulls.
The update in (2) is by Lemma 7 in Appendix A, which we borrow from Kveton et al. [28]. From Proposition 1, we have that the uncertainty-adjusted prior for task s is Ps(·) = N (·; µ̂s, Σ̂s + Σ0).

heading: 3.2 Linear Bandit with Gaussian Rewards
text: Now we generalize Section 3.1 and consider a 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 ∈ A as an arm. Then, with a slight abuse of notation from Section 2, the reward distribution of arm a is pa(·; θ) = N (·; a>θ, σ2), where θ ∈ Rd is shared by all arms and σ > 0 is reward noise. A conjugate prior for this problem class is P (·;µ) = N (·;µ,Σ0), where Σ0 ∈ Rd×d is known and we learn µ ∈ Rd. As in Section 3.1, AdaTS can be implemented efficiently with a meta-prior Q(·) = N (·;µq,Σq), where µq ∈ Rd is a known mean parameter vector and Σq ∈ Rd×d is a known covariance matrix. In this case, Qs(·) = N (·; µ̂s, Σ̂s), where
µ̂s = Σ̂s ( Σ−1q µq + s−1∑ `=1 B` σ2 − G` σ2 ( Σ−10 + G` σ2 )−1 B` σ2 ) ,
Σ̂−1s = Σ −1 q + s−1∑ `=1 G` σ2 − G` σ2 ( Σ−10 + G` σ2 )−1 G` σ2 .
Here G` = ∑n t=1A`,tA > `,t is the outer product of the feature vectors of the pulled arms in task ` and
B` = ∑n t=1A`,tY`,t(A`,t) 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 uncertaintyadjusted prior for task s is Ps(·) = N (·; µ̂s, Σ̂s + Σ0).
We note in passing that when K = d and A is the standard Euclidean basis of Rd, the linear 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.

heading: 3.3 Semi-Bandit with Gaussian Rewards
text: A stochastic combinatorial semi-bandit [19, 12, 25, 26, 42], or semi-bandit for short, is a K-armed bandit where at most L ≤ 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 to 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 is that the action set is A ⊆ ΠL(K), where ΠL(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,t ∈ A. The meta-posterior is updated analogously to Section 3.1. The only difference is that 1{A`,t = i} becomes 1{i ∈ A`,t}.

heading: 3.4 Exponential-Family Bandit with Mixture Priors
text: We consider a general K-armed bandit with mean arm rewards θ ∈ RK . The reward distribution of arm i is any one-dimensional exponential-family distribution parameterized by θi. In a Bernoulli
bandit, this would be pi(·; θ) = Ber(·; θi). 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.
It is challenging to generalize our approach beyond Gaussian models because we require more than the standard notion of conjugacy. Specifically, to apply AdaTS to an exponentially-family 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 (·; j)}Lj=1 be a set of L potential conjugate priors, where each P (·; j) is a product of one-dimensional exponential-family priors. Then a suitable meta-prior is a vector of initial beliefs into each potential prior. In particular, it is Q(·) = Cat(·;wq), where wq ∈ ∆L−1 is the belief and ∆L is the L-simplex. In this case, Qs(j) = ∫ θ Ls−1(θ)P (θ; j) dκ2(θ)Qs−1(j) in Proposition 1 has a closed form, since it is a standard conjugate posterior update for a distribution over θ followed by integrating out θ. In addition, Ps(θ) = ∑L j=1Qs(j)P (θ; j) is a mixture of exponential-family priors over θ. 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.

heading: 4 Regret Bounds
text: We first introduce common notation used in our proofs. The action set A ⊆ Rd is fixed. Recall that a matrix X ∈ Rd×d is positive semi-definite (PSD) if it is symmetric and its smallest eigenvalue is non-negative. For such X , we define σ2max(X) = maxa∈A a
>Xa. Although σ2max(X) depends on A, we suppress this dependence because A is fixed. We denote by λ1(X) the maximum eigenvalue of X and by λd(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(P ||Q) to denote the relative entropy of P with respect to Q. It is defined as D(P ||Q) = ∫ log( dPdQ ) dP , where dP/dQ 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 ∈ ·). For jointly distributed random variables X and Y , we let P (X | Y ) be the conditional distribution of X given Y , P (X ∈ · | Y ), which is Y -measurable and depends on random Y . The mutual information between X and Y is I(X;Y ) = D(P (X,Y )||P (X)P (Y )), where P (X)P (Y ) is the distribution of the product of P (X) and P (Y ). Intuitively, I(X;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 Y conditioned on Z. We define this quantity as I(X;Y | Z) = E[Î(X;Y | Z)], where Î(X;Y | Z) = D(P (X,Y | Z)||P (X | Z)P (Y | Z)) is the random conditional mutual information between X and Y given Z. Note that Î(X;Y | Z) is a function of Z. By the chain rule for the random conditional mutual information, Î(X;Y1, Y2 | Z) = E[Î(X;Y1 | Y2, Z) | Z] + Î(X;Y2 | Z), where expectation is over Y2 | Z. We would get the usual chain rule I(X;Y1, Y2) = I(X;Y1 | Y2) + I(X;Y2) without Z.

heading: 4.1 Generic Regret Bound
text: We start with a generic adaptation of the analysis of Lu and Van Roy [33] to our setting. In round t of task s, we denote the pulled arm by As,t, its observed reward by Ys,t ∼ pAs,t(·; θs,∗), and the suboptimality gap by ∆s,t = r(As,∗; θs,∗)−r(As,t; θs,∗). For random variables X and Y , we denote by Is,t(X;Y ) = Î(X;Y | H1:s,t) the random mutual information between X and Y given history H1:s,t of all observations from the first s− 1 tasks and the first t− 1 rounds of task s. Similarly, for random variables X , Y , and Z, we denote by Is,t(X;Y | Z) = E[Î(X;Y | Z,H1:s,t) | H1:s,t] the random mutual information between X and Y conditioned on Z, given history H1:s,t. It is helpful to think of Is,t as the conditional mutual information of X | H1:s,t, Y | H1:s,t, and Z | H1:s,t. Let Γs,t and s,t be potentially history-dependent non-negative random variables such that
Es,t[∆s,t] ≤ Γs,t √ Is,t(θs,∗;As,t, Ys,t) + s,t (3)
holds almost surely. We want to keep both Γs,t and s,t “small”. The following lemma provides a bound on the total regret over n rounds in each of m tasks in terms of Γs,t and s,t. Lemma 2. Suppose that (3) holds for all s ∈ [m] and t ∈ [n], for some Γs,t, s,t ≥ 0. In addition, let (Γs)s∈[m] and Γ be non-negative constants such that Γs,t ≤ Γs ≤ Γ holds for all s ∈ [m] and t ∈ [n] almost surely. Then
R(m,n) ≤ Γ √ mnI(µ∗;H1:m) + m∑ s=1 Γs √ nI(θs,∗;Hs | µ∗, H1:s−1) + m∑ s=1 n∑ t=1 E [ s,t] .
The first term above is the price for learning µ∗, while the second is the price for learning all θs,∗ when µ∗ is known. Accordingly, the price for learning µ∗ is negligible when the mutual information terms grow slowly with m and n. Specifically, we show shortly in linear bandits that Γs,t and s,t can be set so that the last term of the bound is comparable to the rest, while Γs,t grows slowly with m and n. At the same time, I(µ∗;H1:m) and I(θs,∗;Hs | µ∗, H1:s−1) are only logarithmic in m and n. Thus the price for learning µ∗ is Õ( √ mn) while that for learning all θs,∗ is Õ(m √ n). Now we are ready to prove Lemma 2.
Proof. First, we use the chain rule of random conditional mutual information and derive
Is,t(θs,∗;As,t, Ys,t) ≤ Is,t(θs,∗, µ∗;As,t, Ys,t) = Is,t(µ∗;As,t, Ys,t) + Is,t(θs,∗;As,t, Ys,t | µ∗) .
Now we take the square root of both sides, apply √ a+ b ≤ √ a + √ b to the right-hand side, and multiply both sides by Γs,t. This yields
Γs,t √ Is,t(θs,∗;As,t, Ys,t) ≤ Γs,t √ Is,t(µ∗;As,t, Ys,t) + Γs,t √ Is,t(θs,∗;As,t, Ys,t | µ∗) . (4)
We start with the second term in (4). Fix task s. From Γs,t ≤ Γs, followed by the Cauchy-Schwarz and Jensen’s inequalities, we have
E [ n∑ t=1 Γs,t √ Is,t(θs,∗;As,t, Ys,t | µ∗) ] ≤ Γs √√√√nE[ n∑ t=1 Is,t(θs,∗;As,t, Ys,t | µ∗) ] .
Thanks to E [Is,t(θs,∗;As,t, Ys,t | µ∗)] = I(θs,∗;As,t, Ys,t | µ∗, H1:s,t) and the chain rule of mutual information, we have E [ ∑n t=1 Is,t(θs,∗;As,t, Ys,t | µ∗)] = I(θs,∗;Hs | µ∗, H1:s−1).
Now we consider the first term in (4). We bound Γs,t using Γ, then apply the Cauchy-Schwarz and Jensen’s inequalities, and obtain E [∑m
s=1 ∑n t=1 Γs,t √ Is,t(µ∗;As,t, Ys,t) ] ≤ Γ √ mnI(µ∗;H1:m);
where we used the chain rule to get
E [ m∑ s=1 n∑ t=1 Is,t(µ∗;As,t, Ys,t) ] = m∑ s=1 n∑ t=1 I(µ∗;As,t, Ys,t | H1:s,t) = I(µ∗;H1:m) .
This completes the proof.

heading: 4.2 Linear Bandit with Gaussian Rewards
text: Now we derive regret bounds for linear bandits (Section 3.2). Without loss of generality, we make an assumption that the action set is bounded. Assumption 1. The arms are vectors in a unit ball, maxa∈A ‖a‖2 ≤ 1.
Our analysis is for AdaTS with a small amount of forced exploration in each task. This guarantees that our estimate of µ∗ 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 {ai}di=1 ⊆ A such that λd( ∑d i=1 aia > i ) ≥ η for some η > 0.
This assumption is without loss of generality. In particular, if such a set does not exist, the action set A can be projected into a lower dimensional space where the assumption holds. AdaTS is modified as follows. In each task, we initially pulls the arms {ai}di=1 to explore all directions.
We start by showing that (3) holds for suitably “small” Γs,t and s,t. In AdaTS, in round t of task s, the posterior distribution of θs,∗ is N (µ̂s,t, Σ̂s,t), where
µ̂s,t = Σ̂s,t ( (Σ0 + Σ̂s) −1µ̂s +
t−1∑ `=1 As,`Ys,` σ2 ) , Σ̂−1s,t = (Σ0 + Σ̂s) −1 + t−1∑ `=1 As,`A > s,` σ2 ,
and µ̂s and Σ̂s are defined in Section 3.2. Then, from the properties of Gaussian distributions and that AdaTS samples from the posterior, we get a bound on Γs,t and s,t as a function of a tunable parameter δ ∈ (0, 1]. Lemma 3. For all tasks s ∈ [m], rounds t ∈ [n], and any δ ∈ (0, 1], (3) holds almost surely for
Γs,t = 4
√ σ2max(Σ̂s,t)
log(1 + σ2max(Σ̂s,t)/σ 2)
log(4|A|/δ) , s,t = √ 2δσ2max(Σ̂s,t) + 2Es,tEs,t[‖θs,∗‖2] ,
where Es,t is the indicator of forced exploration in round t of task s. Moreover, for each task s, the following history-independent bound holds almost surely,
σ2max(Σ̂s,t) ≤ λ1(Σ0)
1 + λ1(Σq) ( 1 + σ 2 ηλ1(Σ0) ) λ1(Σ0) + σ2/η + sλ1(Σq)  . (5) Lemma 3 is proved in Appendix C.3. By using the bound in (5), we get that Γs,t = O( √ log(1/δ)) and s,t = O( √ δ). Lemma 3 differs from Lu and Van Roy [33] in two aspects. First, it considers uncertainty in the estimate of µ∗ along with θs,∗. Second, it 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 H1:s,t-adapted action sequence and any s ∈ [m], we have
I(θs,∗;Hs | µ∗, H1:s−1) ≤ d2 log ( 1 + λ1(Σ0)nσ2 ) , I(µ∗;H1:m) ≤ d2 log ( 1 + λ1(Σq)m λd(Σ0)+σ2/n ) .
Now we are ready to prove our regret bound for the linear bandit. We take the mutual-information bounds from Lemma 4, and the bounds on Γs,t and s,t from Lemma 3, and plug them into Lemma 2. Specifically, σ2max(Σ̂s,t) ≤ λ1(Σq) + λ1(Σ0) holds for any s and t by Lemma 3, which yields Γ in Lemma 2. On the other hand, Γs is bounded using the upper bound in (5), which relies on forced exploration. Our regret bound is stated below. The terms c1 to c4 are at most polylogarithmic in d, m, and n; and thus small. The term c2 arises due to summing up Γs over all tasks s. Theorem 5 (Linear bandit). The regret of AdaTS is bounded for any δ ∈ (0, 1] as
R(m,n) ≤ c1 √ dmn︸ ︷︷ ︸
Learning of µ∗ + (m+ c2)Rδ(n;µ∗)︸ ︷︷ ︸ Per-task regret + c3dm︸ ︷︷ ︸ Forced exploration ,
where
c1 =
√ 8
λ1(Σq)+λ1(Σ0)
log ( 1+
λ1(Σq)+λ1(Σ0) σ2 ) log(4|A|/δ) log (1 + λ1(Σq)mλd(Σ0)+σ2/n) , c2 = ( 1 + σ 2
ηλ1(Σ0)
) logm, and c3 = 2 √ ‖µq‖22 + tr(Σq + Σ0). The per-task regret is bounded as
Rδ(n;µ∗) ≤ c4 √ dn+ √ 2δλ1(Σ0)n, where
c4 =
√ 8 λ1(Σ0)
log ( 1+
λ1(Σ0) σ2 ) log(4|A|/δ) log (1 + λ1(Σ0)nσ2 ) . The bound in Theorem 5 is sublinear in n for δ = 1/n2. It has three terms. The first term is the regret due to learning µ∗ over all tasks; and it is Õ( √ dmn). The second term is the regret for acting in
m tasks under the assumption that µ∗ is known; and it is Õ(m √ dn). The last term is the regret for
forced exploration; and it is Õ(dm). Overall, the extra regret due to unknown µ∗ is Õ( √ dmn+ dm)
and is much lower than Õ(m √ dn) when d n. Therefore, we call AdaTS a no-regret algorithm for linear bandits. Our bound also reflects the fact that the regret decreases as both priors become more informative, λ1(Σ0)→ 0 and λ1(Σq)→ 0. A frequentist regret bound for linear TS with finitely-many arms is Õ(d √ n) [3]. When applied to m tasks, it would be Õ(dm √ n) and is worse by a factor of √ d 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 are applied independently to each task. The first variant knows µ∗ and thus has more information. Its regret can bounded by setting c1 = c2 = c3 = 0 in Theorem 5 and is lower than that of AdaTS. The second variant knows that µ∗ ∼ N (µq,Σq) but does not model that the tasks share µ∗. This is analogous to assuming that θs,∗ ∼ N (µq,Σq + Σ0). The regret of this approach can be bounded by setting c1 = c2 = c3 = 0 in Theorem 5 and replacing λ1(Σ0) in c4 by λ1(Σq + Σ0). Since the task regret increases linearly with m and λ1(Σq + Σ0) > λ1(Σ0), this approach would ultimately have a higher regret than AdaTS as the number of tasks m increases.

heading: 4.3 Semi-Bandit with Gaussian Rewards
text: In semi-bandits (Section 3.3), we use the independence of 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 one a ∈ A that contains any given arm. Let Γs,t(k) and s,t(k) be non-negative history-dependent constants, for each arm k ∈ [K], were we use (k) to refer to arm-specific quantities. Then an analogous bound to (3) is
Es,t[∆s,t] ≤ ∑ k∈[K] Ps,t(k ∈ As,t) ( Γs,t(k) √ Is,t(θs,∗(k); k, Ys,t(k)) + s,t(k) ) .
The term (k, Ys,t(k)) is a tuple of a pulled arm k and its observation in round t of task s. For any k, from the chain rule of mutual information, we have
Is,t(θs,∗(k); k, Ys,t(k)) ≤ Is,t(µ∗(k); k, Ys,t(k)) + Is,t(θs,∗(k); k, Ys,t(k) | µ∗(k)) . Next we combine the mutual-information terms across all rounds and tasks, as in Lemma 2, and bound corresponding Γs,t(k) and s,t(k) independently of m and n. Due to forced exploration, the estimate of µ∗(k) improves for all arms k as more tasks are completed, and Γs,t(k) decreases with s. This leads to Theorem 6, which is proved in Appendix D. Theorem 6 (Semi-bandit). The regret of AdaTS is bounded for any δ ∈ (0, 1] as
R(m,n) ≤ c1 √ KLmn︸ ︷︷ ︸
Learning of µ∗ + (m+ c2)Rδ(n;µ∗)︸ ︷︷ ︸ Per-task regret + c3K 3/2m︸ ︷︷ ︸ Forced exploration + c4σ √ 2δmn ,
where
c1 = 4 √√√√ 1K ∑ k∈[K]
σ2q,k+σ 2 0,k
log ( 1+ σ2q,k+σ 2 0,k
σ2
) log(4K/δ) log (1 + σ2q,km σ20,k+σ 2/n ) ,
c2 =
( 1 + max
k∈[K]:σ0,k>0 σ2 σ20,k
) logm, c3 = 2 √∑ k∈[K] (µ2q,k + σ 2 q,k + σ 2 0,k) ,
c4 = √ 1 K ∑ k∈[K]:σ0,k=0 log ( 1 + σ2q,km σ2 ) .
The per-task regret is bounded as Rδ(n;µ∗) ≤ c5 √ KLn+ √ 2δ 1K ∑ k∈[K] σ 2 0,kn, where
c5 = 4 √√√√ 1K ∑ k∈[K]:σ0,k>0
σ20,k
log ( 1+
σ20,k σ2 ) log(4K/δ) log (1 + σ20,knσ2 ) . The prior widths σq,k and σ0,k are defined as in Section 3.1.
The bound in Theorem 6 is sublinear in n for δ = 1/n2. Its form resembles Theorem 5. Specifically, the regret for learning µ∗ is Õ( √ KLmn) and for forced exploration is Õ(K3/2m). Both of these
are much lower than the regret for learning to act in m tasks when µ∗ is known, Õ(m √ KLn), for K Ln. Therefore, AdaTS is also a no-regret algorithm for semi-bandits. Theorem 6 improves upon a naive application of Theorem 5 to semi-bandits. This is because all prior width constants are averages, as 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 semi-bandits by any prior work. To illustrate the difference, consider a problem where σ0,k > 0 for only K ′ K arms. This means that only K ′ arms are uncertain in the tasks. Then the bound in Theorem 6 is Õ(m √ K ′Ln), while the bound in Theorem 5 would be Õ(m √ KLn). For the arms k where σ0,k = 0, the regret over all tasks is sublinear in m.

heading: 5 Experiments
text: We experiment with two synthetic problems. In both problems, the number of tasks is m = 20 and each task has n = 200 rounds. The first problem is a Gaussian bandit (Section 3.1) with K = 2 arms. The meta-prior is N (0,Σq) with Σq = σ2qIK , the prior covariance is Σ0 = σ20IK , and the reward noise is σ = 1. We experiment with σq ≥ 0.5 and σ0 = 0.1. Since σq σ0, the entries of θs,∗ are likely to have the same order as in µ∗. Therefore, a clever algorithm that learns µ∗ could have very low regret. The second problem is a 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 N (µ∗,Σ0) 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 it TS and implement it with prior N (0,Σq + Σ0), since θs,∗ can be viewed as a sample from this prior when the structure is ignored (Section 4.2). The third baseline is MetaTS of Kveton et al. [28]. All methods are evaluated by their cumulative regret up to task s, which we plot as it accumulates round-by-round within each task (Figure 2). The regret of the algorithms that do not learn µ∗ (OracleTS 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 OracleTS, no regret can grow sublinearly in s.
Our results are reported in Figure 2. We start with a Gaussian bandit with σq = 0.5. This setting is identical to Figure 1b of Kveton et al. [28]. We observe that AdaTS outperforms TS, which does not learn µ∗, and is comparable to OracleTS, which knows µ∗. Its regret is about 30% lower than that of MetaTS. Now we increase the meta-prior width to σq = 1. In this setting, meta-parameter sampling in MetaTS leads to high biases in earlier tasks. This leads to a major increase in regret, while AdaTS performs comparably to OracleTS. We end with a linear bandit with σq = 1. In this experiment, AdaTS outperforms MetaTS again and has more than three times lower regret.
Appendix E contains more experiments. In Appendix E.1, we experiment with more values of K and d, and show the robustness of AdaTS to missspecified meta-prior Q. In Appendix E.2, we apply AdaTS to
bandit classification problems. In Figure 3, we show results for one of these problems, meta-learning a highly rewarding digit 1 in the bandit setting. For each method and task s, we show the average digit corresponding to the pulled arms in round 1 of task s. AdaTS learns a good meta-parameter µ∗ almost instantly, since its average digit in task 2 already resembles digit 1.

heading: 6 Related Work
text: 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 µs at the beginning of each task s and uses it to compute the posterior of the task parameter θs,∗. Since µs is fixed within the task, MetaTS does not have a correct posterior of θs,∗ given the history. AdaTS marginalizes out the uncertainty in the meta-parameter µ∗ and thus has a correct posterior of θs,∗ within the task. This seemingly minor difference leads to an approach that is more principled, comparably general, has a fully-Bayesian 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 Õ( √ mn2). This cost arises due sampling the meta-parameter µs at the beginning of each task s. The price of meta-learning in our work is mere Õ( √ mn), a huge improvement.
AdaTS is a meta-learning algorithm [39, 40, 7, 8, 17, 18]. Meta-learning has a long history in multiarmed bandits. Some of 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 a UCB algorithm that meta-learns the mean parameter vector in a linear bandit, which is akin to learning µ∗ in Section 3.2. Another recent work is Yang et 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 a stronger notion of regret, and often lead to conservative algorithm designs. In contrast, we leverage the fundamentals of Bayesian reasoning to design a general-purpose algorithm that performs well when run 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 on 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, 23]. Typically it is ad-hoc and we believe that meta-learning is a proper way of framing this problem.

heading: 7 Conclusions
text: We propose AdaTS, a fully-Bayesian algorithm for meta-learning in bandits that adapts to a 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-theory tools that isolate the effect of learning the meta-parameter from that of learning the per-task parameters. For linear bandits and semi-bandits, we derive novel prior-dependent regret bounds that show that the price for learning the meta-parameter is low. Our experiments underscore the generality of AdaTS, good out-of-the-box performance, and robustness to meta-prior 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 θs,∗ is unknown but the covariance Σ0 is known. It is not immediately obvious if a computationally-efficient extension to unknown Σ0 exists.

Review summaries:
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. 

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.  The key ideas in the proposed AdaTS algorithm are 1. to maintain a distribution over the unknown task prior parameter, and 2. to marginalize such uncertainties by learning, across instances, a posterior over it.  Leveraging hierarchical Bayesian modeling and conjugate priors, the authors present AdaTS, with implementations for multi-armed/linear bandits and combinatorial semi-bandits.  Bayesian regret bounds for the $n$-round $m$-instance AdaTS are shown to be of order $O(\sqrt{mn})$.  Experiments on synthetic datasets illustrate the added benefits of the proposed approach.

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.