Metadata-based Multi-Task Bandits with Bayesian Hierarchical Models
Authors: Runzhe Wan
Lin Ge
Rui Song
Venue: NeurIPS 2021 Poster (2021)
Keywords: Multi-armed Bandits
Thompson sampling
Meta learning
Transfer Learning

Abstract: How to explore efficiently is a central problem in multi-armed bandits. In this paper, we introduce the metadata-based multi-task bandit problem, where the agent needs to solve a large number of related multi-armed bandit tasks and can leverage some task-specific features (i.e., metadata) to share knowledge across tasks. As a general framework, we propose to capture task relations through the lens of Bayesian hierarchical models, upon which a Thompson sampling algorithm is designed to efficiently learn task relations, share information, and minimize the cumulative regrets. Two concrete examples for Gaussian bandits and Bernoulli bandits are carefully analyzed. The Bayes regret for Gaussian bandits clearly demonstrates the benefits of information sharing with our algorithm. The proposed method is further supported by extensive experiments. 


Metadata-based Multi-Task Bandits with Bayesian Hierarchical Models
Runzhe Wan
Lin Ge Rui Song Department of Statistics North Carolina State University (rwan, 1ge, (aong]@ncsu. edu
Abstract
How to explore efficiently a central problem in multi-armed bandits. In this pa- per, we introduce the metadata-basel multi-task bandit problem, where the agent needs solve a large number of related multi-armed bandit tasks and can lever- age some task-specific features (i.e., metadata) to share knowledge across tasks. As a general framework, we propose to capture task relations through the lens of Bayesian hierarchical models, upon which Thompson sampling algorithm is designed to efficiently learn task relations, share information, and minimize the cumulative regrets. Two concrete examples for Gaussian bandits and Bernoulli bandits are carefully analyzed. The Bayes regret for Gaussian bandits clearly demonstrates the benefits of information sharing with algorithm. The pro- posed method is further supported by extensive experiments.
1 Introduction
The multi-armed bandit (MAB) is a popular framework for sequential decision making problems, where the agent will sequentially choose among few arms and receive a random reward for the arm [37]. Since the mean rewards for the arms are not known priori and must be learned through exploitaaionn trade-off. MAB receiving increasing attention and has been widely applied to areas such as clinical trials [1], recommendation systems 770, among others.
partial feedbacks, the agent is faced with the well-known
finance 54
How to explore efficiently is central problem in MAB. In many modern applications, usually have a large number of separate but related MAB tasks. For example, in e-commerce, the company needs to find the optimal display mode for each of many products, and in medical applications, each patient needs to individually undergo a series of treatment periods to find the personalized optimal treatment. These tasks typically share similar problem structures, but may have different reward distributions. Intuitively, appropriate information sharing can largely speed up our learning process and reduce the regret, while a naive pooling may cause linear regret due to the bias.
This paper is concerned with the following question: given a large number of MAB tasks, how do efficiently share information among them? The central task is capture task relations in principled way [68]. While a few approaches have been proposed (see Section (2). most them only utilize the action-reward pairs observed for each task. To our knowledge, none of the existing works can leverage another valuable information source, i.e., the metadata of each task, which contains some static task-specific features. Such metadata is commonly available in real applications [66] 68, 57], such as the demographic features of each customer or patient, or basic information of each web page or product. Although the metadata can hardly be directly utilized in single MAB task, it usually contains intrinsic information about each task, and hence can guide us to learn task relations and efficiently share knowledge in the multi-task setup. Specifically, suppose task has feature vector x; (i.e., metadata) and its expected reward vector for all arms is r;- We consider general formulation that r; is sampled from the conditional distribution (r: (x)). When P(r, (x) is
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Mean reware aarm
Mean reward arm
675
Mean reward
66c
-156
Meen reward of amm
Mean reward of amm
Festure
(a) The meta MAB setting
34
(b) There exists several task clus-
(c) X1 is continuous variable.
28
where is constant.
ters, where x, is categorical.
Figure 1: Illustrations of the task distribution (rr:) the first two subplots, each dot represents a task and the two axes denote the expected rewards for two arms. In the last subplot, we have three arms, each dot represents one arm of task, the x- axis denotes one continuous feature 21, and the y-axis denotes the expected reward. In the last two settings, the metadata is informative and can guide the exploration reduce regrets, while there is still inter-task heterogeneity that can not be captured.
informative, the metadata, being appropriately utilized, can guide our exploration and hence reduce the regret. Several specific cases of (rr,(x,) are illustrated in Figure |
As one of our motivating examples, consider that a company needs learn about the personal pref- erence of many users over several options (e.g., message templates), via sequential interactions with each user. Suppose some user features (c.g., gender, age, geography) are informative in predicting the preference. Then, even before any interactions with specific user, with high probability, based on her features and our experience with other users. Such knowledge can be concisely encoded [r))) However, т; typically can not be fully determined by x;- Given the possible heterogeneity of r; conditional on X;, the true reward distribution (and optimal arm) of this specific user still needs to be learned and confirmed via interactions with herself. There- fore, we must carefully utilize these features in a multi-tast algorithm. Indeed, we conjecture this is one way how humans adapt tasks effectively, by constructing rough first impression according to features, and then adjusting the impression gradually in the following interactions.
predict her preference
To judiciously share information and minimize cumulative regrets, we design multi-task bandit algorithm. Recall that, when (xr, ) is known a priori, Thompson sampling (TS) algorithm [53] with (P(r)(x)) the prior of for each task i is known to be (nearly) optimal in Bayes regret, for a wide range of problems (37]. However, such knowledge typically is absent, and many concerns have been raised regarding that TS is sensitive to the prior 442
7 23). In this work, aim to aggregate data from all tasks to construct an informative prior for each task. Specifically, we propose to characterize the task relations via Bayesian hierarchical model, upon which the Multi-Tass TS (MTTS) algorithm is designed to continuously learn IP(r; x:) by aggregating data. With such a design, MTTS yields similar low regret to the oracle TS algorithm which knows (P(r((x,) priori. In particular, the metadata x; allows us to efficiently capture task relations and share information. The benefits can be seen clearly from experiments and analysis.
25
Contribution. Our contributions can be summarized as follows. First of all, motivated by the usefulness of the commonly available metadata, introduce and formalize the metadata-based multi-task MAB problem. The related notion of regret imulti-task regret) is defined, which serves appropriate metric for this problem. Second, we propose to address this problem with uni- fied hierarchical Bayesian framework, which characterizes the task relations in principled way. We design TS-type algorithm, named MTTS, to continuously learn the task distribution while minimizing the cumulative regrets. The framework is general to accommodate various reward dis- tributions and sequences of interactions, and interpretable from other tasks affects one specific task and how its metadata determines its prior. Two concrete examples for Gaussian bandits and Bernoulli bandits are carefully analyzed, and efficient imple- mentations are discussed. Our formulation and framework open a door to connect the multi-task bandit problem with the rich literature on Bayesian hierarchical models. Third, theoretically demonstrate the benefits of metadata- based information sharing, by deriving the regret bounds for MTTS and several baselines under a Gaussian bandit setting. Specifically, the average multi-task regret of MTTS decreases as the number of tasks grows, while the other baselines suffer linear regret. Lastly, systematic simulation experiments are conducted investigate the performance of MTTS under different conditions, which provides meaningful insights.
can study how the information

---

2
Related Work
T0 34 351 special case, where x; First of all, our setup subsumes the meta MAB problem 28
degenerates to a constant. Meta MAB assumes the tasks arrive sequentially and are drawn from one metadala-agnoste distribution. Among these works, meta TS [4 is the most related one, which assumes the mean reward vectors {ri} are i.i.d. sampled from some distribution f(r; 0), and pool data to learn 0. The other works either pool data from accomplished tasks to optimize algorithm prperpprrameters (28) or directly optimize the policy via policy gradient [10, 33). Compared with meta MAB, our setting is more general as we allow incorporating metadata learn and capture task relations, and also allow the interactions with different tasks to arrive in arbitrary orders. The former particularly important when there exists significant heterogeneity among tasks (e.g., setting (c) in Figure D where naive pooling may lose most information; the latter allows broader applications. The results developed in this paper are equally applicable to meta MAB.
In addition to meta MAB, there are several other topics concerned with multiple bandit tasks. We review the most related papers in this section, and provide comprehensive comparison with addi- tional related works and concepts in Appendix B First of all, there is a large number of works on multi-agent bandits [2 62 17 studying that multiple agents interact with the same task concur- rently. In contrast, we consider there is inter-task heterogeneity. Given such heterogeneity, certain approaches to capture task relations are then required: when there exist useful network structures between tasks, [3] and [6] propose to utilize this knowledge to capture task relations; [6] assumes there is a finite number of task instances, considers the tasks arrive sequentially, and aims to transfer knowledge about this set of instances; [64] assumes there exist pairwise upper bounds on the differ-
ence reward distributions; clustering of bandits [22 40 and latent bandits (26 27 assume there is perfect clustered structure, that tasks in the same cluster share the same reward distribution. In contrast to all these setups, to our knowledge, this the first work that can utilize metadata, an important information source that is commonly available. Practitioners are typically familiar with feature- based methods and our work adds one useful tool to the multi-task bandits toolbox. Besides, sidelllin-bbsed approach provides nice interpretability and is flexible to accommodate arbi- trary order of interactions. Lastly, we learn task relations from data automatically, with arguably fewer structural assumptions.
In the presence of task specific features, another approach to pool information is to adapt contextual MAB (CMAB) algorithms 43 the metadata as "contexts". Specifically, one can assume a deterministic relationship r; = [x;; 0) for some function f, and then apply CMAB algorithms to learn P. However, such solution heavily relics on the realizability assumption [2I], that rÜ = f(x;; 0) holds exactly with no variation or error. When this assumption is violated, linear regret is generally unavoidable. This limitation attracts increasing attention [3] 32). In our setup, the agent will interact with each task multiple times and the metadata is fixed, which naturally enables us to relax this restrictive assumption by regarding FÚ as a random variable sampled from ((,, To our knowledge, this is the first work that can handle the realizability issue via utilizing the repeated measurement structure.
69 51
58 36 38), by neglecting the task identities and regarding
Finally, there exists a rich literature on multi-task supervised learning (see 67 for a survey), where hierarchical models 44 to construct informative priors, and [68 considered leveraging metadata to cluster tasks. Besides, this work is certainly related to single-task bandits. In particular, Thompson sampling is one of the most popular approaches with superior performance [[ [3
55 63
are a popular choice, [49
3 46 studied aggregating historical data
60 34 2 [8]. Its popularity is partially due to its flexibility to incorporate prior knowledge [14]. We provide data-driven approach to
construct such prior. Our work naturally builds on these two areas to provide an efficient solution to the metadata- based multi-task MAB problem.
3 Metadata-based Multi-task MAB
In this section, we introduce general framework for the metadata- based multi- task MAB problem. For any positive integer M, we denote the set 21, M) by [M]. Let I be the indicator function. Suppose we have large number of K K-armed bandit tasks with the same set of actions, denoted as [K]= .I.... K}. Each task instance i is specified by a tuple (r:, x,), where r; = (ri.,...,, )" is the vector of mean rewards for the K arms and x; is a p-dimensional vector of task-specific fea- a
tures (i.e., metadata). The metadata can include categorical and continuous variables, and even outputs from pre-trained language or computer vision models [16 39]. We assume these task in-
3

---

stances are i..dd sampled from some unknown task distribution Pr.x. which induces a conditional distribution P(r, We will interact with each task repeatedly. For each task i, at its t-th deci- sion point, we choose one arm Ai, E [ and then receive a random reward Ri according to RI.- -
+ C.e. where c,,t mean-zero error term.
We call this setup multi- task MAB to focus on the fact that there is more than one MAB task. New tasks may appear and interactions with different tasks may happen in arbitrary orders. When the tasks arrive in a sequential manner (i.e., task i + begins only when task is finished), our setup is an instance of meta learning
[5], which we refer as the sequential setting in this paper.
Suppose until a time point, we have interacted with N tasks, and for each task i E [AV] we have made T3 decisions. The performance of a bandit algorithm can be measured by its Bayes regret,
BR(N, (T.)) = Ex,,, Σ
EiE[M] E (maraajk) Vi,a Ti.A..))
where the expectation is taken with respect to the task instances {(r;: }: the random errors, the order of interactions, and the randomness due to the algorithm. Here, the metadata {x,} and the order of interactions enter the definition because they might affect the decisions of multi-task algorithm. When the algorithm does not share information across tasks, the definition reduces to the standard single-task Bayes regret (37] accumulated over N tasks. The Bayes regret is particularly suitable for multi-task bandits, under the task distribution view 667 34).
Given the existence of inter-task heterogeneity, the Bayes regret of any bandit algorithms will un- avoidably scale linearly with N. We next introduce new metric, refer as the multi-task regret, which allows us to clearly see the benefits of multi-task learning and can serve as an appropriate metric for multi-task bandit algorithms.
To begin with, we first review Thompson sampling (TS), which is one of the most popular bandit algorithm framework [I 53 60). For each task i, the standard single-task TS algorithm requires prior Q(r:) as the input, maintains a posterior of r., and samples an action according to its posterior probability of being the optimal one. We denote (Qr))) as TS algorithm with some distribution Q()) as the prior. Most Bayes regret guarantees for TS require the specified prior is equal to the true distribution of [53] 37.. When this condition satisfied, it well-known that this TS algorithm is (nearly) optimal for wide range of problems [53] 371. In our setup, this assumption means that, for each task i, we will apply (P(, It is natural to set such an (nearly) optimal algorithm as our skyline, which we refer to as oracle- TS.
However, it is arguably strong assumption that the agent can know P(r,(x;;) a priori, and growing literature finds that TS with a mis-specified prior can yield a poor regret due to over-exploration
53 23 Therefore, well-designed metadata- based multi-task MAB algorithm should be able to aggregate data to learn the task distribution pattern (i.e., P(r,(xx)), so as to yield similar low regrets with oracle-TS. Motivated by these discussions, we define the multi-task regret of an algorithm as the difference between its Bayes regret and the Bayes regret of oracle-TS, which can be equivalently written as
14 42
25
MTR(N, (Ti)) = Ex.r, EMEMM) EnEm) (TAAA. - -r..A..).
where A.e is the action that oracle-TS takes, and the expectation is additionally taken over its ran- domness. This regret reflects the price of not knowing the prior priori, and measures the perfor- mance of multi-task algorithm in learning the task distribution pattern while maintaining a low regret. A similar concept defined in 7 for meta learning in dynamic pricing.
4
Algorithm: MTTS
4.1 General framework
To address the metadata-based multi-task MAB problem, in this section, we introduce general hierarchical Bayesian framework to characterize the information-shariig structure among tasks, and design TS algorithm that can continuously leam P(r(x) and yield a low regret. For ease of ex- position, we assume discrete probability spaces. Our discussion is equally applicable to continuous settings. Two representative examples are given in the following subsections.
To learn P(([)), we make a model assumption that r, is sampled from f(r)|x;, 0), for a model f parameterized by the unknown parameter 0. For example, in Gaussian bandits, f(r [x, 0) can be
4

---

Algorithm 1: MTTS: Multi-task Thompson Sampling
Input : Prior TP(0) and known parameters of the hierarchical model
1 Set H = +0
2 for every decision point j do Retrieve the task index i Compute the posterior for r; as ((r: according to the hierarchical model [
(see
Section 4.2 and 4.3 for examples)
5
Sample reward vector (fr.1..... Ft,k]² PP(r/HH)
Take action A₂ argmazze[K]] Fi,a
Receive reward R2
8
Update the dataset as H + HU {(Aj, x.,
9 end
the conditional density function of a linear model with Gaussian errors (see Section 4.2
We denote
the prior of 0 as P(0). Therefore, our full model is the following Bayesian hierarchical model: (Prior)
P(())
(Inter-task)
r:|x;; 0 ~ f(ri|x;, O), [N],
(Intra-task)
Ri,t = Ene(k]] T(A = a)rca + CL, Vi E (M), E [T.].
We note that P(0) specified by the users, and our regret analysis worst-case frequentist regret bound with respect to O. Besides, the inter-task layer clearly subsumes the meta MAB model r: ((r and the CMAB model r; f(x;;; O) as two special cases.
Suppose until a decision point, we have accumulated a dataset H = [[AAA Ry, i())) where the data for all tasks have been combined and re-indexed. Here, i{j) is the task index for the jth tuple in H. x₁ = X(() is its metadata, Aj is the implemented action and R2 is the observed reward. Suppose we need to make a decision for task i at this time point. To adapt the TS algorithm, one needs compute the posterior of Tı as PP(r/ (H) according to the specified hierarchical model, sample reward vector, and then act greedily to it. Based on this framework, we designed the Multi-Task Thompson Sampling (MTTS) algorithm, which summarized as Algorithm [
Algorithm T is natural and general. Once a hierarchical model is specified, the remaining step to adapt MTTS is compute the posterior PHr: We will discuss two concrete examples in the following sections. Before we proceed, we remark that the posterior can be written as
P(r (t) = f(re)) / H)d0 & P(HL(r)) /. ((r))))) 0)d0,
(2)
where Hi the subset of H that contains the history of task i. Note that ((H)(r:) the likeli- hood for task i alone. Therefore, (2) provides a nice interpretation: up to normalization constant, 0)d0 can be regarded as a prior for task i, and this prior will be continuously up-
Sg (( ( dated by pooling data based on the hierarchical model. Specifically, data from all tasks are utilized to infer 0 via ()), which is then used to infer [P(r,)) x,) through f(r:|(( [x., O). This consistent with our motivations, that would like utilize the metadata {x,} to guide exploration (via the prior), while also using the task-specific history Hi (via the likelihood P(H()rr)) algorithm, MTTS yields desired interpretability, tasks affects one specific task, via investigating how its metadata determines its prior.
As a multi-task study how the information from other
In addition, the relationship 2 suggests computationally efficient variant of Algorithm We note two facts: (i) is typically more demanding to compute (() than P(H))r:))(() X;, 0), since the former involves regression problem and usually has explicit form, while the latter usually has analytic solutions by choosing conjugate priors; (ii) according to 2 to sample ry from PPrr (H), equivalent to first sample one ê from P(0 and then sample r, with probability proportional to ((H.lr:)f(rrll)) 0). Therefore, when it is computationally heavy to sample (rr,(H)) every time, we can instead sample Ô from P(0 H)) at lower frequency, and apply [S( 0)) to task i before sampling the next value 0. This variant can be regarded as updating the inter-task data pooling module in batch mode, and it shows desired regret in our analysis and negligible costs our experiments. Under the sequential setting, this variant is described in Algorithm 2 and the general form is given in Appendix C.2 See Section 4.3 for a concrete example.
5

---

Algorithm 2: Computationally Efficient Variant of MTTS under the Sequential Setting
Input : Prior TP(0) and known parameters of the hierarchical model
Set H = [ and P(0 (H) = PP())
2 for task i E [N] do
Sample one Ô from the current posterior P(O
3
Apply [S(f(r:) 0)) to task i for T; rounds, and collect observed data as Hi
5
Update H = HUH,
Update the posterior of 0 according to the hierarchical model T
7
end
4.2
Gaussian bandits with Bayesian linear mixed models
In this section, we focus on Gaussian bandits, where the error term G, follows N o²) for a known parameter We will first introduce linear mixed model characterize the information- sharing structure, and then derive the corresponding posterior. We use In to denote an m x m identity matrix. Let + Rº [K] + R2 be known map from the metadata-action pair d-dimensional transformed feature vector, and let D; = (ø(x;, 1).... Φ(x;, K))² We focus on the case that B(r,) (x)) is linear in o; and consider the following linear mixed model (LMM):
=-,0 + 8,, E [N]
where 0 is unknown vector, and ò; s.i.d. (O Σ) for some known covariance matrix E. In this model, the fixed effect term 9,0 captures the task relations through their metadata, and the random effect term ò; allows inter-task heterogeneity that can not be captured by the metadata. We adopt the prior distribution 0 ~ N(Hs Eg) with hyper- parameerss μ4 and Eg.
The posterior of r; under LMM has an analytic expression. We begin by introducing some notations. Recall that the history is {(A), X,, i(i))} of size n. Denote R (R)...., R.,) and A..)". Let En,s' be the (a, a')-h" entry of Σ. The LMM induces an n x n kernel matrix K, the (1, m)-th entry which is (xi, (x A..) - -E AA,,AA,, I(i(I) = i(m)). Finally, define K matrix M,, such that the ja entry of M, is T(i(J) = i) The posterior of r, follows a multivariate normal distribution, with mean and covariance as
+ Ai),,,,,).......
E(r, H() P + E" (, + 1²I,)
cov(r; [H) = (Φ + Σ) - (0,E0 + M)) + + + M,).
At each decision point, we can then follow A act. The computation is dominated by the matrix inverse of (K+o²In)) In). In Appendix C.I we introduce an efficient implementation via using the Woodbury matrix identity (50) and the block structure induced by the LMM.
aatuadta-bbasee multi-takk MAB problems via mixed effect mod- els is generally applicable. One can replace the linear form of with other functional forms and proceed similarly. As an example, mixed-effect Gaussian process model and the corresponding MTTS algorithm are derived in Appendix D.2
Remark 1. The idea of addressing
4.3 Bernoulli bandits with Beta-Bernoulli logistic models
The Bernoulli bandits, where the reward is binary random variable, is another popular MAB prob- lem. As a concrete example, consider the BeraoBern logistic model (BBLM) to characterize the iiformation-sharing structure. Recall rs,a is the expected reward of the ath arm of task i. In BBLM, ri follows a Beta distribution with (r.s,a (x.) being a logistic function & (x;, a)O. We assume the prior (No,, Eg) as well. The BBLM is then defined as
Tiça Beta Deta(logistic(( " (x;,a) v)), Va E [K], [N]
R ~ Bernoulli Σ uE(K) I(A,, = a)r.a)) Vt E [T]. [N],
where logistic(x) 1/(1 ex)=)(x)), v is known parameter, and Beta(u, v) denotes a Beta distribution with mean μ and precision th. In regression analysis, the BBLM popular for binary responses when there exist multiple levels in the data structure 20 47).

---

One challenge to adapting Algorithm to Bernoulli bandits is that the posterior does not have an explicit form. This is also common challenge to generalized linear bandits [38 36). In model (
the main challenge comes from the Beta logistic model part. We can hence follow the algorithm suggested by (2) to sample A at a lower frequency. The nice hierarchical structure of model 4 al- lows efficient computation of the posterior of 0 via approximate posterior inference algorithmss, such as Gibbs sampler (29) or variational inference [9]. For example, with Gibbs sampler, the algorithm will alternate between the first layer of 4 which involves Beta regression, and its second layer, which yields a
conjugate form. Both parts are computationally tractable. We defer the details to Appendix C.3 to save space. Finally, we note that, similar models and computation techniques can be developed for other reward variable distributions with a conjugate prior.
5 Regret Analysis
In this section, we present the regret bound for MTTS under the linear mixed model introduced in Section 4.2] We will focus simplified version of Algorithm [] due to the technical challenge to analyze the behaviour of TS with a misspecified prior. Indeed, to analyze MTTS, we need a tight bound on the difference in Bayes regret between TS with misspecified prior and TS with the correct prior. To the best of our knowledge, it is still an open and challenging problem in the literature
We consider two modifications (see Appendix G for a formal description): (i) we introduce an "alignment period" for each task, by pulling each arm once in its first K interactions, and (ii) in- stead of continuously updating the prior as in (2). we fix down a prior for each task after its alignment period, with the prior learned from data generated during all finished alignment periods. These two modifications are considered so that we can apply our "prior alignment" proof technique, which is inspired by 77] and allows to bound the multi-task regret. We note similar modifications are im- posed in the literature as well, due to similar technical challenges 7 [3]. The former modification causes an additional ((N regret, and the latter essentially utilizes less information in construct- ing the priors than Algorithm|]] [and is imposed to simplify the analysis. Even though, the modified version suffices to show the benefits of information sharing. Besides, the second modification is consistent with Algorithm| 2 and hence we provide certain guarantees to this variant. Finally, the shows desired sublinear regrets in experiments.
vanilla MTTS (Algorithm [
For a matrix A, we denote its operator norm and minimum singular value by ||A|| and mmin min((A) (A), respectively. For a vector v, we define ||o|| to be its & norm. Ô is the big-O notation that hides logarithmic terms. We make the following regularity assumptions.
Assumption 1. Jmin (B(#) 2.)) > Kc, and maz stants G1 and C1.
(++ll S KC₁ for some positive con-
Assumption 2. mar (xx,; a)ll < C2 and |10|| S for some positive constants C2 and C3.
Assumption 3. || ll Σell and |Σ] are bounded.
These regularity conditions are standard in the literature on Bayesian bandits 52, linear bandits 22 M and feature-based structured bandits [48 41.. Under these conditions, we can derive the following regret bound for the modified MTTS. For simplicity, we assume Ti =.... Tn = T.
Theorem 1. Under Assumptions - 3, when = o(N) and K < min(N, T). the multi- regret of the modified MTTS under the LMM is bounded as
MTR(N, (T:)) = O(
(Va+ =Ö(VNVVTK+ + KKK..
HoKlogT (NT) (I-K)KKKK
(5)
We remark this is worst-case frequentist regret bound with respect to O. To save space, the proof of Theorem iss is deferred to Appendix G Note that the single-task Bayes regret of oracle-TS is O( O(VTKlog based on the literature (e.g., 37). The Bayes regret of the modified MTTS then follows from the definition of multi-task regret.
Corollary 1. Under the same conditions as Theorem 7 the Bayes regret of the modified MTTS can be bounded as BR(N, (T:)) = Ö(
NK NVTR).
For comparison purposes, we informally summarize the regret bounds of several baselines in 5 To save space, the formal statements and their proofs are deferred to Appendix
Discussions.
7

---

Table 1: A summary of the multi-task regret bounds under the LMM. All logarithmic terms hidden.
MTTS (the proposed)
meta-TS
individual-TS
linear-TS TS
OSFA
Model
Pim ~ f(ri|x;; 0) vNdvTK + NK
Ti
f(r(0) NVTK
TE P(r)
T-= fx;;;; 0) =: P(r)
MTR
NVTK
NT
NT
H We consider the following algorithms: (i) One TS policy for all tasks, referred to one-size- Jit-all (OSFA); (ii) An individual TS policy for each task, referred to as individual-TS; (iii) TS for linear bandits (2), referred as linear-TS;; (iv) Meta-Thomppon sampling (meta-TS) proposed in [4]. Specifically, meta-TSS under the Gaussian bandits setting, assumes ri ~ MN,, Σ) for some unknown vector fa. and it pools data to learn μ.. To recap, OSFA ignores the inter-task heterogeneity and linear-TS assumes r; is fully determined by the metadata, while individual-TS does not share information and meta-TS fails utilize the metadata to efficiently share information.
In the MTR bound for MTTS (5). the first term is sublinear in N, which implies MTTS is contin- uously learning about Prr; xx.) and will behave closer to oracle-TS as N increases. The ((NK) term is due to the imposed K aligmment rounds in our analysis. In contrast to MTTS, the multi- task regrets of these baseline algorithms unavoidably scale linearly in N, since they fail to utilize knowledge about P(r:(x:), which can efficiently guide the exploration. The regret rates suggest that MTTS is particularly valuable in task-rich settings (N > d). When d is relatively large compared with N, certain additional structures (e.g., sparsity) can be considered. We note that, although their difference in multi-task regret is of the same order as the Bayes regret of oracle-TS, which implies the Bayes regret of MTTS, meta-TS, and individual-TS will be of the same order, the hidden mul- tiplicative factors can differ a lot. We observe a substantial gap in the experiments. Finally, OSFA and linear-TS even suffer a linear regret in T, due to the bias caused by ignoring the heterogeneity. In contrast, MTTS yields desired sublinear Bayes regret in T.
An Ö(T22)) bound on the additional regret for Bayesian bandit algorithms with a misspecified prior is provided in [56) under simple setting, where is the total- variatiin between the true prior and the misspecified one. (34) adopts recursive approach to obtain Ö( / KT + NN /T)) Bayes regret bound for meta-TS. Our bound demonstrates the usefulness of the prior alignment proof technique, which can be applied to meta-TS well. Moreover, we note that the LMM can be reduced to linear bandits with extended context (x(,x))) (17,a, o (x;, a))T, where 1i,a is length-N K vector taking value 1 at the ((i (G-1)N+aa-tth entry. Such reduction is typically ill-conditioned and direct application of results for linear bandits [52] gives us Bayes regret bound Ö K +d) which reflects the necessity to carefully utilize the information sharing structure. Besides, we note that the reduction from a hierarchical model to a contextual bandit model is typically not possible. Finally, similar to some literature on meta bandits (65) 7), we adopt the task distribution viewpoint by assuming the tasks (and hence {x: are i.i.d. and considering Assumption 1 It should be feasible to relax these assumptions following the standard proof approach with ad verrsarial contexts
2
See Appendix Gi for more details.
6 Experiments
6.1 Synthetic Experiments
Setting. We conduct simulation experiments to support our theoretical results and study the em- pirical performance of MTTS. We use model (3) and (4) bandits and Bernoulli bandits, respectively. In the main text, we present results with N = 200,
data generation model for Gaussian
T = -200, K = 8 and d = 15. We set ((x;,a) = (I "T,"" YT, where 1, is a length- K indicator vector taking value at the a-th entry, and Φ.,a is sampled from ./(0, I x). The coefficient vector 0 is sampled from NN I.). For Gaussian bandits, we set values of 01. For Bernoulli bandits, we vary the precision Φ). A higher value of 0g or và implies a larger inter-task heterogeneity conditional on the metadata. We consider two representative types of task sequence: (i) the sequential setting, where the (é+ 1)th task begins after we finish the i-th task, and (ii) the concurrent setting, where we interact with all tasks for the (-th time simultaneously.
1 and Σ of A for different
For Gaussian bandits, we compare MTTS with the four algorithms discussed in Section 5 OSFA, individual-Te linear-TS, TS, and meta-TS. Besides, we also investigate the performance of the com-
8

---

Concurrent
Sequential
of
0.25
of =05
o =1
03 0.25
of
0f
Averoge regret
200
80
80
200
40
60
60-
100
100
100
30-
20
0
100
200
100
200
100
200
0
100
200
100
200
200
200
N
MTTS
MTTS
oracleTT
IinenTTS
mete-TS
IndividuaiTS
OSPA
(a) Gaussian bandits. The regrets of OSFA are much higher in some subplots and hence hidden.
Concurrent
Sequential
0.05
4 D.1
0.2
0.05
0.1
D.2
Average regret
46
40
66
40
40
20
10-
10
10
100
100
200
200
200
N
N
MITS (ours)
oracko-TS
GLB-TS
metalT5
Individual-7s
OSFA
(b) Bernoulli bandits. larger value of di implies a larger variation r. condition on X;-
Figure 2: Average Bayes regret for various methods. Shared areas indicate the standard errors of the averages.
putationally efficient variant of MTTS in Algorithm 2 referred to as MTTS-approx. For Bernoulli bandits, we replace linear-TS with a TS algorithm for generalized linear bandits [36,, which is re- ferred to GLB-TS. The other baselines are also replaced with their Bernoulli variants. To set the priors for these TS algorithms. we apply the law of total expectation (variance) to integrate out (x, r) to specify the mean (variance) term. See Appendix [F] forr more details about the implementations.
Results. Results aggregated over 100 random seeds are presented in Figure Under the concur- rent setting, the average Bayes regrets per interaction are displayed, which shows the trend with T; under the sequential setting, the average Bayes regrets per task are displayed, which shows the trend with N. Such choice allows us to see the regret rates derived in Section 5 more clearly. Recall that the multi-task regret of an algorithm can be calculated as the difference between the Bayes regret of itself and oracle-TS. TS. For ease of comparison, also report the multi-task regrets in Appendix E.2
Overall, MTTS performs favorably compared with the other baselines. Our findings can be sum- marized as follows. First, in the sequential setting, the Bayes regret of MTTS approaches that of oracle-TS, which shows that MTTS yields a sublinear multi-task regret N. This implies MTTS is learning (P(r) x) and will eventually behave similarly to oracle-TS. In contrast, there exists a consis- tent and significant performance gap between oracle-TS and the other baselines. This demonstrates the benefit of metadata-base a sublinear Bayes regret in T. This implies MTTS learning the best arm for each task. Although individual-TS and meta-TS also yield sublinear trends, their cumulative regrets can be significantly higher. For example, in Gaussian bandits, the cumulative regret of MTTS is only 53.3% of the re- gret for individual-TS when of 0.25, and 68.2% when of 0.5. This demonstrates that, with information sharing and the guidance of metadata, MTTS can explore more efficiently. The benefit particularly important when the horizon T is not long, and MTTS enables a jump-start for each task. Third, the trend with of and & is clear: when the metadata is less useful (o² = 1 or dé = 0.2), the performance of meta-TS and individual-TS becomes closer MTTS, while linear-TS (GLB-TS) and OSFA suffer from the bias; when the metadata is highly informative, the advantage of MTTS over meta-TS and individual-TS becomes much more significant, and the performance of linear- TS (GLB-TS) becomes relatively better. Overall, MTTS shows robustness. Lastly, MTTS-approx yields similar performance with the vanilla MTTS, except when N still small.
information sharing. Second, in the concurrent setting, MTTS shows
Additional results. Results under other settings are reported in Appendix E.3 where MTTS con- sistently performs favorably, and shows reasonable trends with hyperparameters such as N. K, and d. Finally, recall that, to share information, we made a model assumption that r: 0 ~ [(r; 0). When this model correctly specified, MTTS has shown superior theoretical and numerical performance. Intuitively, this model is designed to pool information to provide infor- mative prior. As long as the learned prior provides reasonable information relative to a manually specified one, the performance of MTTS is expected to be better or at least comparable. The con-

---

Concurrent
Sequential
Average regret
45
40
25
100
OSFA
MTTS
MITS MITS-approx aрpaap
Individual-TS
IneanTTS
mete-TS
Figure 3: MovicLens: average regret for various methods. Shared arcas indicate the standard errors of the averages.
jecture is partially supported by Lemma in the appendix, which characterizes the impact of a mis- specified prior on MTR. We empirically investigate the impact of model misspecication to MTTS in Appendix E.I
where MTTS demonstrates great robustness.
6.2 MovieLens Experiments
We evaluate the empirical performance on the Moviel.ens 1M dataset (24), which consists of the ratings (reward) by 6040 users (tasks) on 3900 movies. Each user has three features (metadata), including gender, age, and occupation. The movies belong few genres (arms). We preprocessed the dataset to focus on the top genres, top occupations and users with at least 500 data points, which gives us N = 175 users. We apply Gaussian bandit algorithms considered in Section 6. recommend movie genres to each user and collect rewards by sampling corresponding records from the dataset. We repeat the experiment over 100 random seeds, with T = 100.
The regrets against the empirical oracle (which knows the user-specific optimal genre with the high- est empirical mean reward priori) are reported in Figure Overall, MTTS performs preferably and demonstrate the benefits of metadata- and meta-TS. Linear-TS and OSFA seem to suffer linear regret in T, which emphasizes the ex- istence of heterogeneity. As expected, the demographical features an user can partially predict her interests in movie genres, while there still exists strong heterogeneity even conditional on these features, which requires further personalization based on her own feedbacks.
information sharing, compared with individual-T'S
7 Discussion
In this paper, study the metadata-based multi-task MAB problem, where can utilize the meta- data to capture and Iearn task relations, so as to judiciously share knowledge. We formalize this problem under general framework and define the notion of regret. We propose address this problem with Bayesian hierarchical models and design a TS-type algorithm. MTTS, to share infor- mation and minimize regrets. Two concrete examples analyzed and efficient implementations are discussed. The usefulness of MTTS are further supported by regret bounds as well as experiment results with both synthetic and real data.
The proposed framework can be extended in several aspects. First, the variance components are assumed known for the two examples in Section 4 In practice, update these hyperparameters adaptively. See Appendix [.3 for details. Second, our work can be extended to contextual bandits, based on the idea of clustering of bandits [22] 440 when the set of task instances is finite, or the idea of contextual Markov decision process (55] when the set is
apply empirical Bayes to
infinite. See Appendix for details. Third, while analysis for MTTS can be directly extended to other functional forms, the prior alignment technique does utilize some properties of Gaussian distributions. A novel analysis of TS with mis-specified priors would be of independent interest. Besides, to our knowledge, the lower bound for the additional regret with a misspecified prior is still missing in the literature. Such bound is the difference between Bayes regrets and hence requires a quite precise description of the behaviors of Bayesian bandit algorithms. Lastly, we focus on TS-type algorithms in this paper since is straightforward to incorporate side information via the prior. The Upper-Couu Confidenee Bound (37) (UCB) is another popular algorithm framework. Though directly adapting UCB our setup is challenging, Bayesian UCB [31] naturally fits our problem and benefits from information sharing. We believe this is an interesting direction worthy of study.
10

---

References
[1] Agrawal, S.; and Goyal, N. 2013. Further optimal regret bounds for thompson sampling. In Artificial intelligence and statisties, 99-107. PMLR.
[2] Agrawal, S.; and Goyal, N. 2013. Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning, 127-135, PMLR.
[3] Anderer, A.; Bastani, H.; and Silberholz,, 2019. Adaptive Clinical Trial Designs with Surro- gates: When Should We Bother? Available at SSRN 3397464
[4] Arya, S.; and Yang, Y. 2020. Randomized allocation with nonparametric estimation for contex- tual multi-armed bandits with delayed rewards. Statistics & Probability Letters 164: 10881
[5] Auer, P. 2002. Using confidence bounds for exploitation-exploratio trade-offs. Journal of Machine Learning Research 3(Nov): 397-422.
[6] Azar, M. G.; Lazaric, A.; and Brunskill, E. 2013. Sequential transfer in multi-armed bandit with finite set of models. arXiv preprint urXivv1307.668
[7] Bastani, H.; Simchi-Levi, D.; and Zhu, R. 2019. Meta Dynamic Pricing: Transfer Learning Across Experiments. Available at SSRN 3334629.
[8] Baxter, J. 2000. A model of inductive bias learning. Journal of artificial intelligence research 12: 149-198.
[9] Blei, D. M.; Kucukelbir, A.; and McAuliffe, D. 2017. Variational inference: A review for statisticians. Journal of the American statistical Association 112(518); 859-877.
[10] Boutilier, C.: Hsu, C.-w:; Kveton, B.; Mladenov, M.; Szepesvari, C.; and Zaheer, M. 2020. Differentiable Meta-Learning of Bandit Policies.
[11] Cella, I..; Lazaric, A.; and Pontil, M. 2020. Meta-learning with stochastic linear bandits. In International Conference on Machine Learning, 1360-1370. PMLR.
[12] Cesa-Bianchi, N.; Gentile, C.; Mansour, Y.; and Minora, A. 2016. Delay and cooperation in nonstochastic bandits. In Conference on Learning Theory, 605-622. PMLR.
[13] Cesa-Bianchi, N.; Gentile, C.; and Zappella, G. 2013. A gang of bandits. Proceedings of the 26th International Conference Neural Information Processing Systems-Volume Volume 1, 737-774.
[14] Chapelle, O.; and Li, L. 2011, An empirical evaluation of thompson sampling. Advances in neural information processing systems 24: 2249-2257.
[15] Chu, W.; Li, L.; Reyzin, L.; and Schapire, R. 2011. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, 208-214. JMLR Workshop and Conference Proceedings.
[16] Devlin, J.: Chang, M.-W.; Lee, K.; and Toutanova, K. 2018. Bert: Pre-training of deep bidi- rectional transformers for language understanding. arXiv preprint 1Xiv:1810.04000
[17] Dubey, A.; et al. 2020. Cooperative multi-agent bandits with heavy tails. In International Conference on Machine Learning, 2730-2739. PMLR.
[18] Dumitrascu, B.; Feng, K.; and Engelhardt, B. E. 2018. PG-TS: Improved Thompson sampling for logistic contextual bandits. arXiv preprint arXiv:1805.00 1805.07458.
[19] Durand, A.;
Achilleos, C.; lacovides, D.; Strati, K.; Mitsis, G. D.; and Pineau, J. 2018. Con- textual bandits for adapting treatment in a mouse model de novo carcinogenesis. In Machine learning for healthcare conference, 67-82. PMLR.
[20] Forcina, A.; and Franconi, L. 1988. Regression analysis with the beta-binomial distribution. Rivista Statistica Applicata 21(1).
[21] Foster, J.; Gentile, C.: Mohri, M.; and Zimmert, 2020. Adapting to Misspecification in Contextual Bandits. Advances in Neural Information Processing Systems 33.
11

---

[22] Gentile, C.; Li, S.; and Zappella, G. 2014. Online clustering of bandits. In International Conference on Machine Learning, 757-765, PMLR.
[23] Hamidi, N.; and Bayati, M. 2020. On Worst-case Regret Linear Thompson Sampling. arXiv preprint 2006::0000066990..
[24] Harper, F. M.; and Konstan, J. A. 2015. The moviclens datasets: History and context. Acm transactions on interactive intelligent systems (tis) 5(4): 1-19.
[25] Honda, J.; and Takemura, A. 2014. Optimality of Thompson sampling for Gaussian bandits depends priors. In Artificial Intelligence and Statistics, 375-383. PMLR.
[26] Hong, J.; Kveton, B.; Zaheer, M.; Chow, Y.; Ahmed, A.; and Boutilier, C. 2020. Latent Bandits Revisited. arXiv preprint 20X.042006.08714
[27] Hong, J.; Kveton, B.; Zaheer, M.; Chow, Y.; Ahmed, A.; Ghavamzadeh, M.; and Boutilier, C. 2020. Non-Stationary Latent Bandits. arXiv preprint arXiv:2012.00386.
[28] Hsu, C.-W.; Kveton, B.; Meshi, O.; Mladenov, M.; and Szepesvari, C. 2019. Empirical Bayes regret minimization. arXiv preprint arXiv: 1rXiv:190.00264
[29] Johnson, A. A.; Jones, G. L.; et al. 2010. Gibbs sampling for Bayesian hierarchical general linear model. Electronic Journal of Statistics 4: 313-333.
[30] Kar, S.; Poor, H. V:; and Cui, S. 2011. Bandit problems in networks: Asymptotically efficient distributed allocation rules. In 2011 50th IEEE Conference on Decision and Control and European Control Conference, 1771-1778. IEEE.
[31] Kaufmann, E.; Cappé, O.; and Garivier, A. 2012. On Bayesian upper confidence bounds for bandit problems. Artificial intelligence and statisties, 592-600, PMLR.
[32] Krishnamurthy, K.; Hadad, V.; and Athey, S. 2021. Adapting to misspecification in contex- tual bandits with offline regression oracles. arXiv preprint arXi::2102.13240
[33] Krishnamurthy, S. K.; Hadad, V:; and Athey, S. 2021. Tractable contextual bandits beyond realizability. In International Conference on Artificial Intelligence and Statistics, 1423-1431. PMLR.
[34] Kveton, B.; Konobeev, M.; Zaheer, M.; Hsu, C.-w;; Mladenov, M.; Boutilier, C.; and Szepes- vari, C. 2021. Meta-Thompson Sampling. arXiv preprint urXiv:2102.06111
[35] Kveton, B.; Mladenov, M.; Hsu, C.-W:; Zaheer, M.; Szepesvari, C.; and Boutilier, C. 2021. Meta-Leaming Bandit Policies by Gradient Ascent.
[36] Kveton, B.; Zaheer, M.; Szepesvari, C.; Li, L.; Ghavamzadeh, M.; and Boutilier, C. 2020. Randomized exploration in generalized linear bandits. In International Conference on Artificial Intelligence and Statisties, 2066-2011 2076. PMLR.
[37] Lattimore, T.; and Szepesvári, C. 2020. Bandit algorithms. Cambridge University Press.
[38] Li, L.; Lu, Y.; and Zhou, D. 2017. Provably optimal algorithms for generalized linear contex- tual bandits. In International Conference Machine Learning, 2071-2080. PMLR.
[39] Li, L. H.; Yatskar, M.; Yin, D.; Hsieh, C.-J.; and Chang, K.-W. 2019. Visualbert: A simple and performant baseline for vision and language. arXiv preprini
[40] Li. S.; Karatzoglou, A.; and Gentile, C. 2016. Collaborative filtering bandits. In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, 539-548.
[41] Li, S.; and Zhang, S. 2018. Online clustering of contextual cascading bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32.
[42] Liu, C.-Y.; and Li, L. 2016. On the prior sensitivity of Thompson sampling. In International Conference Algorithmic Learning Theory, 321-336. Springer.
12

---

[43] Lu, T.; Pál, D.; and Pál, M. 2010. Contextual multi-armed bandits. In Proceedings of the Thirteenth international conference on Artificial Intelligence and Statistics, 485 492. JMLR Workshop and Conference Proceedings.
[44] Luo, L.; Yao, Y.; Gao, F.; and Zhao, C. 2018. Mixed-effeet Gaussian process modeling approach with application in injection molding processes. Journal of Process Control 62: 37-43.
[45] Modi, A.; Jiang, N.; Singh, S.; and Tewari, A. 2018. Markov decision processes with continu- ous side information. In Algorithmic Learning Theory, 597-618. PMLR.
[46] Nabi, S.; Nassif, H.; Hong, J.; Mamani, H.; and Imbens, G. 2020. Bayesian Meta-Prior Learning Using Empirical Bayes. arXiv preprint arXiv:2002.01129.
[47] Najera-Zuloaga, J.; Lee, D.-J.; and Arostegui, I. 2018. Comparison of beta-binomial regression model approaches to analyze health-related quality of life data. Statistical methods in medical research 27(10): -009.
[48] Ou, M.; Li, N.; Zhu, S.; and Jin, R. 2018. Multinomial logit bandit with linear utility functions. arXiv preprint
[49] Raina, R.; Ng. A. Y.: and Koller, D. 2006. Constructing informative priors using transfer learning. In Proceedings of the 23rd international conference on Machine learning, 713-720.
[50] Rasmussen, C. E. 2003. Gaussian processes in machine learning. In Summer school on ma- chine learning, 63-71. Springer.
[51] Reeve, H.; Mellor, J.; and Brown, G. 2018. The k-nearest neighbour ucb algorithm for multi- armed bandits with covariates. In Algorithmic Learning Theory, 725-752. PMLR.
[52] Russo, D.; and Van Roy, B. 2014. Learning optimize via posterior sampling. Mathematics of Operations Research 39(4): 1221-1243.
[53] Russo, D.; Van Roy, B.; Kazerouni, A.; Osband, I;; and Wen, Z. 2017. A tutorial on thompson sampling, arXiv preprint 177.v.170..02038
[54] Shen, W.: Wang, J.: Jiang, Y.-G.; and Zha, H. 2015. Portfolio choices with orthogonal bandit learning. In Twenty-fourth international joint conference on artificial intelligence.
[55] Shi, J.; Wang, B.; Will, E.; and West, 2012. Mixed-effects Gaussian process functional regression models with application to dose-response curve prediction. Statistics in medicine 31(26): 3165-3177
[56] Simchowitz, M.; Tosh, C.; Krishnamurthy, A.; Hsu, D.; Lykouris, T.; Dudik, M.; and Schapire, R. E. 2021. Bayesian decision- making under misspecified priors with applications to meta- learning. arXiv preprint arXiv:2107.01509
[57] Sodhani, S.; Zhang, A.; and Pineau, J. 2021. Multi- Reinforcement Learning with Context-based Representations. arXiv preprint arXiv:2102.06177.
[58] Srinivas, N.; Krause, A.;
Kakade, S. M.; and Seeger, M. 2009. Gaussian process optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995.
[59] Thrun, S. 1998. Lifelong learning algorithms. In Learning to learn, 181-209. Springer.
[60] Tomkins, S.; Liao, P.; Klasnja, P.; and Murphy, S. 2020. IntelligentPooling:: Practical Thomp- son Sampling for mHealth. arXiv preprint 20X1v:200..0157.
[61] Vaswani, S.; Schmidt, M.; and Lakshmanan, I. 2017. Horde of bandits using gaussian markov random fields. In Artificial Intelligence and Statistics, 690-699. PMLR.
[62] Wang, P.-.;; Proutiere, A.; Ariu, K.; Jedra, Y.; and Russo, A. 2020. Optimal algorithms for multiplayer multi-armed bandits. In International Conference on Artificial Intelligence and Statistics, 41 4129- PMLR.
13

---

[63] Wang, Y: and Khardon, R. 2012. Nonparametric Bayesian Mixed-effect Model: a Sparse Gaussian Process Approach. Journal of Machine Learning Research 2012: 1-27.
[64] Wang, Z.; Zhang, C.; Singh, M. K.; Riek, L.; and Chaudhuri, K. 2021. Multitask Bandit Learn- ing Through Heterogeneous Feedback Aggregation. In International Conference Artificial Intelligence and Statistics, 1531-1539 PMLR.
[65] Yang, J.; Hu, W.; Lee, J. D.; and Du, S. S. 2020. Provable Benefits of Representation Learning in Linear Bandits. arXiv preprint ar arXiv:2010.06531.
[66] You, Q.: Wu, O.; Luo, G.; and Hu, W. 2016. Metadata-Basse Based Clustered Multi-task Learning for Thread Mining in Web Communities. In International Conference on Machine Learning and Data Mining in Pattern Recognition, 421-434. Springer.
[67] Zhang, and Yang, Q. 2017. A survey on multi-task learning. arXiv preprint arXiv: 1707.08/14.
[68] Zheng, Z.; Wang, Y.: Dai, Q.: Zheng, H.; and Wang. D. 2019. Metadata-driven Task Relation Discovery for Multi-task Learning. In IJCAI, 4426 4432.
[69] Zhou, L. 2015. A survey on contextual multi-armes bandits. arXiv preprint arXiv:1508.000
[70] Zhou, Q:: Zhang, X.; Xu, and Liang, 2017. Large-scale bandit approaches for recom- mender systems. In International Conference on Neural Information Processing, 811-821. Springer.
14


Reviews:
[{"review_id": "wLGN1lCXi4E", "reviewer": "Reviewer_DATJ", "summary": "The paper considers the multi-task bandit setting with a contextual information related to the task. The setting is defined in a fully Bayesian way, pathing the way to a Thompson Sampling (TS) bandit algorithm to handle this setting. A worst-case regret bound with respect to the parameters of the task-generator is proven and experiments on synthetic data show that the proposed model has smaller regret than baselines independently of the entropy of the task with respect to the contextual information.\n", "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": "Having access to a contextual information regarding tasks, the proposed Bayesian model and the corresponding TS algorithm are strait-forward. However, the theoretical analysis and the experiments demonstrate the interest of the proposed approach with respect both to meta-learning approaches overlooking the contextual information, and to non-meta-learning approaches.\n\nAt first read, the presence of both $d$ and $K$ in the regret bound is surprising as a task is defined by its context and the unknown vector $\\theta$ of dimension $d$. Obviously, this reasoning is wrong, as a task also depends on the randomness in its generation which may be expressed by a vector $\\delta_i$ of size $K$ (see by example Equation (3)). This point could be stressed out in the paper.\n\nNote that the contextual multi-task setting may be reduced to standard contextual setting using (i) the extended context $\\Phi'(x_i, a) := (1_{i,a}^T, \\phi(x_i,k)^T)^T$, where $1_{i,a}^T$ is a length $NK$ indicator vector taking value 1 at $((i-1)*N+a)$-th entry, and (ii) the extended parameter $\\theta' = (\\delta_1^T, \\dots, \\delta_N^T, \\theta)$. Such reduction inflates the size of the contextual information, leads to badly conditioned context-vectors, and is somehow equivalent to considering the tasks as independent. However, I'm wondering how it would compare to the proposed approach in terms of regret.\n\n## typos\n* L230: I guess the parameter of the indicatrice function should be $i(l) = i(m)$  \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Recommender systems are typical application of bandit algorithms. However, by recommending the preferred items to users, they tend to restrain the user to these preferences which may raise concerns regarding the corresponding societal impact.  \n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "jgtUfr1brF7", "reviewer": "Reviewer_JzUf", "summary": "Authors provide a new solution of the problem of transfer learning across different bandit tasks. Specifically they assume policy to leverage external task-features describing task similarities. They focus on Bernoulli and Gaussian bandits as learning instances.\nThe theoretical findings have been tested on synthetic data.", "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": "Authors claimed to introduce two novel ingredients with respect to traditional works on meta-learning with bandit tasks. First they say to consider a more general setting thanks to the presence of metadata. Secondly, here task interactions are allowed to arrive in arbitrary order. Yet, they are not forced to arrive sequentially. \nTo the best of my knowledge I am not aware of the usage of metadata to explain bandit task similarites. I found the idea interesting and novel. That beind said, I would not say that this is a more general framework as it does not incorporate all the task-similarities assumptions that have been investigated in the literature. Indeed, I would consider it an alternative framework.\n\nIn the state of the art about meta-learning with bandit tasks I would incorporate the following recent works:\n- Simchowitz et al.. Bayesian decision-making under misspecified priors with applications to meta-learning. https://arxiv.org/abs/2107.01509\n- L Cella, M Pontil. Multi-Task and Meta-Learning with Sparse Linear Bandits. UAI 2021.\n- Moradipari et al.. Parameter and Feature Selection in Stochastic Linear Bandits. https://arxiv.org/abs/2106.05378\n\nAs far as the MTTS regret bound is concerned, I wonder if there is a lower bound result in the literature to better understand the quality of the proposed solution. For instance, it seems to me that setting $d=N$ the MTTS regret bound would be of order N\\sqrt{TK} which is the same of individual-TS. Am I wrong?\n\nFinally, I wonder if there are clear limitations in running experiments over real data.\nI found the paper clear and well written. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "2Q1lnyOeAF6", "reviewer": "Reviewer_sdSm", "summary": "\nThe paper studies the multi-task multi-armed bandits, where tasks are played sequentially and each task is governed by some unknown hidden parameter (metadata) which follows certain prior distribution.\n\n1. The paper comes up with a Bayesian framework for the metadata-based multi-task multi-armed bandits. \n2. The paper designs Thompson sampling-type algorithm, called MTTS, and demonstrates its supremacy over other algorithms, by proving regret bounds for the common Bernoulli / Gaussian prior cases. \n3. The paper shows detailed experimental results to corroborate the effectiveness of the algorithm MTTS.", "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": "\nThe paper proposes a new setting of multi-task bandits, and provides a rather complete answer to it by showing both theoretical and empirical results. The proofs are easy to read and easy to follow. The writing is very well. The paper also provides the codes for the experiments, which is appreciated. \n\n\nAssumption 1 is a little bit annoying to me. It is possible to remove it under other multi-task bandit setting [arXiv:2102.04132]. Since the setting in this paper is not like transfer learning (i.e. all tasks follow the same distribution), I wonder if it is possible to remove Assumption 1? The authors claim it is standard, but there are indeed some papers that does not require a counterpart of Assumption 1 (like [arXiv:2102.04132]). I think the authors should further justify it.\n\nThe paper seldom mentions the upper confidence bound (UCB) algorithms, which can definitely be used to solve this setting  (though it might get worse regret bound). I suggest the authors add a discussion about them. Also, the paper lacks a lower bound. Since the authors propose a novel notion of regret, the lower bound cannot be immediately seen, and thus I suggest the authors discuss about it.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\n### Limitations\n\nPlease refer to Main Review.\n\n### Societal Impact\n\nThe paper focuses on general framework of a wide class of problems, so I do not see any potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "1ndv6aWmIHM", "reviewer": "Reviewer_ALPC", "summary": "This paper proposes a Bayesian hierarchical modelling framework to learn shared information across multiple multi-armed bandits. It extends both meta MAB that doesn't uses task specific metadata and linear bandit models that does not assume inter-task heterogeneity. It defines a new regret, called multi-task regret and provides theoretical analysis on the regret bound compared to other methods. Simulated experiments confirm the superior performance against other baselines when the model is well specified. It also shows robustness when under some model specification. Unfortunately, there are no real data experiments to show the performance in practice.", "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": "This paper is well written. It has a good motivation and a general introduction to the problem. It has sufficient discussions on related work. The general hierarchical Bayesian model framework is natural under the problem setting, and the inference algorithm is standard in the Bayesian literature. It discusses two concrete and simple problem instantiations under linear Gaussian and Beta-Bernoulli assumptions with more extensions in the appendix.\n\nOne of the main contribution is the regret analysis using the MTR. It shows the advantage of the proposed method when the model is well specified. It would actually be useful to comment in the scenario with model misspecification, in which case I guess it will reduces to the same bound as individual TS in Table 1 (or worse depending on the type of misspecification).\n\nI am a bit disappointed about the lack of empirical evaluation on real problems.\nExperiments in the main text shows the advantage of the proposed method when the data generation process is the same as the model prior. In my opinion, it merely serves as a sanity check that the Bayesian inference algorithm works as expected. The additional experiments in E.1 to show the robustness under misspecified reward structure is actually more interest and I would suggest move it to the main text. Nonetheless, I think it would make the paper much stronger if the authors could show it outperforms contextual bandit methods by modelling the additional inter-task heterogeneity in common problems studied in that literature.\n\nAs a minor comment, as many concepts and proving techniques are inspired by [6], it maybe be helpful to the reader by mentioning it in the related work section and explaining the difference from this work.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See my comments above about the lack of real data evaluation.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thank you to the authors and the reviewers for their contributions to the conference! This paper proposes a new bandit formulation with metadata, which they solve using a Bayesian hierarchical framework. They then propose a meta Thompson sampling algorithm and show regret guarantees using prior alignment. The reviewers uniformly appreciated the paper, so my recommendation is to accept the paper. A few concerns were raised regarding the lack of a lower bound and experiments on real data. For the former, I would suggest that the authors add some discussion on why this is challenging to do. For the latter, please add the new MovieLens experiments. Additional clarifications based on the rebuttal response are of course welcome as well.
Decision: Accept (Poster)