Improved Bayes Regret Bounds for Multi-Task Hierarchical Bayesian Bandit Algorithms

Authors: jiechao  guan
hui  xiong
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-06 03:29:37

Abstract: Hierarchical Bayesian bandit refers to the multi-task bandit problem in which bandit tasks are assumed to be drawn from the same distribution. In this work, we provide improved Bayes regret bounds for hierarchical Bayesian bandit algorithms in the multi-task linear bandit and semi-bandit settings. For the multi-task linear bandit, we first analyze the preexisting hierarchical Thompson sampling (HierTS) algorithm, and improve its gap-independent Bayes regret bound from $O(m\sqrt{n\log{n}\log{(mn)}})$ to $O(m\sqrt{n\log{n}})$ in the case of infinite action set, with $m$ being the number of tasks and $n$ the number of iterations per task. In the case of finite action set, we propose a novel hierarchical Bayesian bandit algorithm, named hierarchical BayesUCB (HierBayesUCB), that achieves the logarithmic but gap-dependent regret bound $O(m\log{(mn)}\log{n})$ under mild assumptions. All of the above regret bounds hold in many variants of hierarchical Bayesian linear bandit problem, including when the tasks are solved sequentially or concurrently. Furthermore, we extend the aforementioned HierTS and HierBayesUCB algorithms to the multi-task combinatorial semi-bandit setting. Concretely, our combinatorial HierTS algorithm attains comparable Bayes regret bound $O(m\sqrt{n}\log{n})$ with respect to the latest one. Moreover, our combinatorial HierBayesUCB yields a sharper Bayes regret bound $O(m\log{(mn)}\log{n})$. Experiments are conducted to validate the soundness of our theoretical results for multi-task bandit algorithms.

Main paper: 
 introduction: 
 A stochastic bandit [26, 6, 27] is a sequential decision-making problem where at each round, an agent has to choose an action, and receives a stochastic reward without knowing its expected value. The gap between the cumulative reward of optimal actions in hindsight and the cumulative reward of agent is defined as regret. The goal is to minimize regret, through a combination of exploring different actions and exploiting those with high rewards in the past. Typical applications of bandit algorithms include news article recommendation [28] , computational advertisement [20] , and dynamic pricing [24] . For example, in news article recommendation, the agent must choose a news article for a user. The actions in this bandit setting are articles and the reward could be an indicator of a click from user.When the agent has to solve multiple bandit tasks, many machine learning researchers resort to multi-task learning/meta-learning paradigm [8, 34] to benefit task adaptation. The existing works focused on the multi-task bandit problem can be categorized into three main groups: (1) The first group attempts to learn a low-dimensional representation shared by different bandit tasks, to derive a sharper cumulative regret bound than that derived by learning each task independently [19, 10] . (2) The second group leverages the similarity of contexts (e.g. the feature of actions) in bandit tasks to improve agent's ability to predict rewards in a new task [14, 36] . (3) The third group chooses to maintain a meta-distribution over the hyper-parameters of within-task bandit algorithms (like Tsallis-INF [23] , OFUL [9] , and Thompson sampling [25, 7, 17] ), and draws informative hyper-parameters from the meta-distribution for efficient regret minimization. Our work falls into the third group and formulates the problem of learning similar bandit tasks in a hierarchical Bayesian bandit model [17] . Specifically, in hierarchical Bayesian bandit setting, each bandit task is characterized by a task parameter. Different bandit task parameters are assumed to be independently and identically distributed according to the same distribution. At each round, the learning agent interacts with one or several bandit tasks, which correspond to the sequential and concurrent bandit settings respectively. Many existing works considered hierarchical Bayesian bandit problem, and proposed Thompson sampling [33] type algorithms to solve it [25, 7, 36] . The latest work [17] proposed hierarchical Thompson sampling (HierTS) algorithm and developed a gap-independent Bayes regret bound O(m n log n log (mn)) in the Gaussian linear bandit setting, where m is the number of bandit tasks and n the number of iterations per task. However, it is still unclear for us whether we can derive sharper regret bounds or how to extend hierarchical Bayesian bandit algorithms to the more general multi-task bandit setting.In this work, we attempt to tackle the above two issues, by providing improved Bayes regret bounds for hierarchical Bayesian bandit algorithms in the multi-task Gaussian linear bandit and semi-bandit setting. Firstly, in the linear bandit setting, we improve the multi-task Bayes regret bound of HierTS to O(m √ n log n) in the case of infinite action set, strengthening the latest bound in [17, Thm 3 ] by a factor of O( log (mn)). In the case of finite action set, we propose a novel hierarchical Bayesian bandit algorithm, named hierarchical BayesUCB (HierBayesUCB), that achieves the logarithmic but gap-dependent regret bound O(m log (mn) log n) under mild assumptions. All of the above regret bounds for linear bandit hold in both the sequential and concurrent setting. Secondly, we extend the aforementioned HierTS and HierBayesUCB algorithms to the multi-task Gaussian combinatorial semi-bandit setting. Concretely, our combinatorial HierTS algorithm attains comparable Bayes regret bound O(m √ n log n) with respect to the latest one in [7, Thm 6] . Moreover, our combinatorial HierBayesUCB yields a sharper but gap-dependent regret bound O(m log (mn) log n). Extensive experiments in the Gaussian linear bandit setting are conducted to support our theoretical results.Overall, our theoretical contributions are four-fold: (1) In the case of infinite action set, we provide a tighter Bayes regret bound O(m √ n log n) for HierTS. This bound improves the latest result by a factor of O( log (mn)). (2) In the case of finite action set, we propose a novel HierBayesUCB algorithm, and provide gap-dependent logarithmic Bayes regret bound O(m log (mn) log n) for it.(3) We generalize the above regret bounds for linear bandit from sequential setting to the more challenging concurrent setting. (4) We extend both HierTS and HierBayesUCB algorithms to the more general multi-task combinatorial semi-bandit setting and derive improved Bayes regret bounds. 
related work: 
 Frequentist Regret Bounds for Stochastic Linear Bandit. In the frequentist stochastic bandit setting, we do not assume the bandit task parameter is sampled from a fixed distribution. The frequentist regret is thus for any fixed task parameter, without taking expectation over the distribution of task parameter. (1) In the case of finite action set: [5] for the first time investigated the stochastic linear bandit problem and proposed an algorithm with a frequentist regret of O( √ dn log 3/2 n), where d is the dimension of action space and n is the number of rounds. [29] developed a new algorithm and improved the regret bound to O( √ dn log n). [12] showed that the lower frequentist regret bound in the finite action set is Ω( √ dn).(2) In the case of infinite action set: Both [13] and [30] proposed algorithms that achieve O(d √ n log 3/2 n) regret. The regret bound was further improved in [1, 15] to O(d √ n log n), by designing novel linear bandit algorithms or utilizing advanced martingale methods.Bayes Regret Bounds for Bayesian Linear Bandit. In the Bayesian stochastic bandit setting, the Bayes regret is the expected cumulative regret whose expectation is taken over the draw of task parameter from a distribution. It is not difficult to see that the frequentist regret upper bound implies a Bayes regret upper bound, because the former holds for any task parameter. (1) When the action set is infinite: [30] showed that in the Gaussian linear bandit setting, the Bayes regret of any Bayesian bandit algorithm is lower bounded by Ω( √ n). [31] for the first time gave the Bayes regret bound of O(d √ n log n) for both Thompson sampling (TS) and BayesUCB [22] algorithms. Recently, [21] provided an improved Bayes regret O(d √ n log n) for TS algorithm with a concise proof. (2) When the action set is finite: [32] derived a tight regret bound of O( √ dn) for TS algorithm with sub-Gaussian reward noise, via a novel information-theoretic approach. Recently, [3] developed a logarithmic Bayes regret bound O(d 2 log 2 n) for BayesUCB algorithm in the Gaussian bandit setting.Frequentist Regret Bounds for Multi-Task Linear Bandit Problems. Under the representation learning paradigm, the frequentist regret bounds in [19, 10] for multi-task linear bandits scales as O(m √ nk), where k is the dimension of low-dimensional representation. The expected frequentist regret upper bound for multi-task adversarial linear bandit in [23] is O(m n log (1 + nV )), with V being the similarity among multiple adversarial bandit tasks. Nevertheless, we should mention that all of these frequentist regret bounds for multi-task linear bandit problem are not tighter than Ω(m √ n).Bayes Regret Bounds for Multi-Task Bayesian Linear Bandit/Semi-Bandit. The most related works to ours are [25, 7, 17] , which provided hierarchical-type Thompson sampling algorithms for multi-task bandit and derived Bayes regret bounds in the Gaussian reward setting. We list these Bayes regret bounds in Table 1 for direct comparisons. Among them, the latest work [17] proposed the HierTS algorithm and obtained its regret bound of O(m n log n log (mn)), [7] derived the first Bayes regret bound for multi-task hierarchical Bayesian semi-bandit algorithm. In this work, we provide for HierTS improved Bayes regret bound of O(m √ n log n) in Theorem 5.1. We also propose a novel HierBayesUCB algorithm that achieves logarithmic regret bound O(m log n log (nm)). We finally extend HierTS and HierBayesUCB to the semi-bandit setting and derive improved theoretical results. Other works utilized action features or structure information to derive Bayes regret bounds for multi-task bandit [36, 37] , e.g. the Bayes regret bound in [36] is O(m √ n log n + m log 2 (mn)).Hierarchical Bayesian Bandit Algorithms. Hierarchical Bayesian bandit algorithm was first proposed by [25] to solve multi-task bandit problems. More hierarchical-type Thompson sampling algorithms based on multi-task/meta learning frameworks were developed with improved theoretical guarantees and empirical performance [7, 17, 36, 37] . There also existed other works investigating hierarchical Bayesian bandit algorithms within the single-task bandit setting. For example, [16] extended the two-level hierarchical Bayesian bandit framework to the deeper multiple-level hierarchial Bayesian bandit framework. [2] generalized the single-effect-parameter HierTS algorithm (i.e. the action parameter is centered at a single latent variable) to the mixed-effect bandit framework where each action is associated with a parameter that depends upon one or multiple effect parameters. 
problem setting: 
 For any positive integer n, denote [n] = {1, 2, ..., n} for brevity. For any square matrix M ∈ R d×d , denote λ 1 (M ), λ d (M ) as its maximum and minimum eigenvalues respectively, denote κ(M ) = λ 1 (M )/λ d (M ) as its condition number. The action set A ⊆ B(0, B) ⊆ R d is assumed to be compact for some positive constant B > 0, where B(0, B) is the closed ball centered at the origin. We use , to denote the inner-product between vectors, use w(a) or w a to denote the a-th element of vector w.Single-Task Bandit. A stochastic bandit problem is characterized by an unknown parameter θ with an action set A. Each action a ∈ A under the bandit instance θ is associated with a reward distribution P(•|a, θ). The reward mean of action a under θ is denoted as r(a; θ) = E Y ∼P(•|a;θ) [Y ],and the optimal action under θ is denoted as A * = arg max a∈A r(a; θ). In the stochastic linear bandit setting, the mean reward of action a ∈ A is r(a, θ) = a θ. In Bayesian bandit problem, we further assume that the task parameter θ is independently and identically distributed (i.i.d.) according to a task parameter distribution P(•|µ * ), which is characterized by an unknown hyper-parameter µ * .Single-Task Semi-Bandit. In the semi-bandit setting, the action set A = [K] is a set of finite items. A = {A ⊆ A : |A| ≤ L} is a family of subsets of A with up to L items, where L ≤ K. w ∈ R K is a weight vector. The weight of a set A ∈ A is defined as a∈A w(a). We assume that the weights w are drawn i.i.d. from a distribution, and the mean weight is denoted as w=E[w]. Following previous work [38] , we focus on the coherent case [39] which assumes that the agent knows a feature matrix Φ ∈ R K×d , such that w = Φθ, where θ is the task parameter drawn from P(•|µ * ). The reward of a subset A ∈ A under the bandit instance θ is defined as r(A; θ) = a∈A (Φθ)(a) = a∈A Φ a , θ , where Φ a is the transpose of the a-th row of matrix Φ. We further assume that Φ a ≤ B, ∀a ∈ A .Hierarchical Bayesian Multi-Task Bandit/Semi-Bandit. In this setting, the agent interacts with m tasks sequentially or concurrently. First, sample the hyper-parameter µ * from a hyper-prior Q. Therefore, the goal of the agent in hierarchical Bayesian multi-task bandit/semi-bandit setting is to interact with m tasks efficiently and minimize the following cumulative multi-task Bayes regret:EQUATIONwhere A s, * = arg max a∈A r(a; θ s, * ) is the optimal action for task s ∈ [m] in the bandit setting, and A s, * ∈ arg max A∈A r(A; θ s, * ) is the optimal subset for task s ∈ [m] in the semi-bandit setting.The expectation is taken over µ * , all task parameters (θ s, * ) s∈[m] , all actions (A t ) t≥1 , all stochastic rewards (Y t ) t≥1 . We further assume that the action set A is the same across different tasks for ease of exposition, and assume that the learning agent interacts with any task s ∈ [m] for at most n rounds for convenient comparison with exiting regret upper bounds for multi-task bandit/semi-bandit problem. 
algorithm: 
 Denote H s,t =((A s, , Y s, )) <t,s∈St as the history of all interactions of agent with task s ∈ [m], andH t =(H s,t ) s∈[m]as the whole interaction history up to round t. We next introduce the specific form of Hierarchical Thompson Sampling (HierTS) and Hierarchical BayesUCB (HierBayesUCB) algorithms in the multi-task Bayesian linear bandit and semi-bandit settings, and instantiate these two algorithms to the multi-task Gaussian linear bandit (Algorithm 1) and semi-bandit (Algorithm 2) problems.At round t, hierarchical Bayesian bandit algorithm samples a hyper-parameter µ t from the hyperposterior Q t defined as Q t (µ) = P(µ * = µ|H t ), and then interacts with tasks S t ⊂ [m]. Next, we give details of bandit algorithms, and details of semi-bandit algorithms are deferred to Section 5.4.Sampling. For any task s ∈ S t , HierTS samples task parameter θ s,t from the distribution P s,t (θ|µ t ) P(θ s, * = θ|µ * = µ t , H s,t ) and takes the action A s,t = arg max a∈A a θ s,t , where P s,t (θ|µ t ) is only conditioned on H s,t due to the independence between task parameter θ s, * and other task histories. This process clearly samples bandit instance θ s,t from the true posterior P(θ s, * = θ|H t ), which is equivalent to the form: P(θ s, * = θ, µ * = µ|H t )dµ = P s,t (θ|µ)Q t (µ)dµ, where P s,t (θ|µ) ∝ L s,t (θ)P(θ|µ) is the posterior probability, L s,t (θ)= (a,y)∈Hs,t P(y|a; θ) is the likelihood function, P(θ|µ) is the prior probability by Bayes rule.Hierarchical BayesUCB. For any task s ∈ S t in round t, HierBayesUCB computes the upper confidence bound U t,s,a = a μs,t + 2 log 1 δ a Σs,t for any a ∈ A, where μs,t and Σs,t are the expectation and covariance of the distribution (i.e. P(θ s, * = θ|H t )) of θ s, * conditioned on the history H t , and then takes action with the highest upper confidence bound : A s,t ← arg max a∈A U t,s,a .The hierarchical Gaussian environment is generated as follow. In the multi-task linear bandit setting:(1) µ * ∼ N (µ q , Σ q ), (2) θ s, * |µ * ∼ N (µ * , Σ 0 ), ∀s ∈ [m], (3) Y s,t |A s,t , θ s, * ∼ N (A s,t θ s, * , σ 2 ), ∀t ≥ 1, s ∈ S t ;In the semi-bandit setting, the only difference lies in step (3) where Y s,t,a |A s,t , θ s, * ∼ N ( Φ a , θ s, * , σ 2 ) for any a ∈ A s,t . Here, µ q , µ * , θ s, * are d-dimensional vectors; Σ q , Σ 0 ∈ R d×d are positive semi-definite covariance matrices. In the above two settings, the reward noise can be regarded as N (0, σ 2 ). In the following theoretical analysis sections, we assume that all of µ q , Σ q , Σ 0 and σ are known by the agent to guarantee an analytically tractable posterior.Concretely, using some basic algebraic computations in hierarchical Gaussian model (e.g. see [25, Appendix D]), we can obtain the closed-form hyper-posterior in round t as Q t (µ) = N (µ; μt , Σt ), where the expectation μt and the covariance matrix Σt of Q t (µ) have the following explicit forms:μt = Σt Σ -1 q µ q + s∈[m] (Σ 0 + G -1 s,t ) -1 G -1 s,t B s,t , Σ-1 t = Σ -1 q + s∈[m] (Σ 0 + G -1 s,t ) -1 . (2)Algorithm 1 Hierarchical Bayesian Algorithms for Multi-Task Linear Bandit Setting On the other hand, we also need to handle P(θ s, * = θ|H t ). It is not difficult to see that, in the multi-task Gaussian linear bandit/semi-bandit setting, θ s, * |H t is Gaussian and denoted as P(θ s, * = θ|H t )=N (θ; μs,t , Σs,t ). According to Lemma B.1, μs,t and Σs,t have the following explicit forms: μs,t = Σs,t (Σ -1 0 μt +B s,t ), Σs,t = Σs,t + Σs,t Σ -1 0 Σt Σ -1 0 Σs,t .(3) 
bayes regret bounds: 
 In this section, we provide improved regret bounds of hierarchical Bayesian bandit algorithms for multi-task Gaussian linear bandit/semi-bandit problem. Concretely, we provide improved analysis for HierTS in the sequential linear bandit setting (Sections 5.1), propose a novel HierBayesUCB bandit algorithm with logarithmic regret guarantee (Section 5.2), develop regret bounds for these two algorithms in the concurrent linear bandit setting (Section 5.3), and finally extend these two algorithms to the semi-bandit setting (Section 5.4) with improved regret bounds. In the proof for our theoretical results, the most important step is to give an upper bound on the so-called posterior variance V m,n , which in the multi-task linear bandit setting is defined and upper bounded as follow: EQUATIONc 1 = σ 2 +B 2 λ 1 (Σ 0 ), c 2 = σ 2 +B 2 λ 1 (Σ 0 ) + B 2 λ 1 (Σ q )κ(Σ 0) to be used through the whole Section 5. BR(m, n) ≤ d √ 2mn mc 1 log (1 + n d ) + c 2 log (1 + m Tr(Σ q Σ -1 0 ) d ).Our explanations for the above sequential regret bound are three-fold: (1) The term md nc 1 log (1 + n/d) represents the regret bound for solving m bandit tasks, whose parameters θ s, * are drawn i.i.d. from the prior distribution N (µ * , Σ 0 ). Under this assumption, no task provides information for any other task, and hence this bound is linear in m. Similar observation was also pointed out by [25, 7, 17] .(2) The term d mnc 2 log 1+mTr(Σ q Σ -1 0 )/d represents the regret bound for learning the hyper-parameter µ * . Such bound is sublinear in m and is not a dominant term when m is large. (3) For a large m, the averaged Bayes regret bound across m tasks is ofBR(m, n)/m = O(d √ n log n), and strengthens the latest averaged bound O(d √ n log n) in [17,Thm 3] by a factor √ log n. Besides, since the lower Bayes regret bound for any Bayesian bandit algorithm is Ω(d √ n) [30] , our task-averaged Bayes regret bound is within O( √ log n) of optimality and hence is called 'Near-Optimal' sequential regret bound. We further make a detailed comparison between our regret bound in Theorem 5.1 and the regret bound [17, Thm 3] in the following remark.Remark 5.1 (Improvements of Our Theorem 5.1 over the Latest One) Our sequential regret bound has two improvements over the latest one in [17, Thm 3, shown in Table 1 ]: (1) We remove the additional log (mn) factor in both the regret bound for solving m bandit tasks and the regret bound for learning the hyper-parameter µ * . (2) In the regret bound for learning hyper-parameter µ * , [17] has a multiplicative factor κ 2 (Σ 0 ), whereas our multiplicative factor is κ(Σ 0 ). Such improvement is achieved by using technical matrix analysis proposed in Lemma C.1. and explained in Remark A.1.In this section, we attempt to provide further improved Bayes regret bounds for hierarchical bandit algorithms in the sequential bandit setting. Because the task averaged Bayes regret bound in Theorem 5.1 is near optimal, it is not easy to derive improved Bayes regret bounds under the same assumptions. Therefore, we further assume that the action set A is finite, and propose a novel hierarchical Bayesian bandit algorithm, named Hierarchical BayesUCB (HierBayesUCB), for multitask linear bandit problem. The pseudo-code of our proposed algorithm is shown in Algorithm 1.Next, we introduce some necessary notations. Let ∆s,t = θ s, * (A s, * -A s,t ), ∆ s,min = min a∈A\{As, * } θ s, * A s, * -θ s, * a , ∆ min = min s∈[m] ∆ s,min . For any > 0, let ∆ min = max{ , ∆ min }. Define the event E s,t = {∀a ∈ A : |a (θ s, * -μs,t )| ≤ 2 log 1 δ a Σs,t }.Then, analogous to [3] , we decompose the Bayes regret BR(m, n) = E t≥1 s∈St ∆ s,t into three terms: 4), HierBayesUCB can achieve the following logarithmic Bayes regret bound in the sequential bandit setting (the logarithmic bound can be extended to the concurrent setting).E t≥1,s∈St ∆ s,t 1{∆ s,t ≥ , E s,t } + 1{∆ s,t < , E s,t } + 1{Theorem 5.2 (Logarithmic Sequential Regret of HierBayesUCB) Let |S t | = 1 for any round t, and the action set A is finite with |A| < ∞. Then in the multi-task Gaussian linear bandit setting, for any δ ∈ (0, 1), > 0, the Bayes regret BR(m, n) of HierBayesUCB is upper bounded by mn +4Bδλ1 2 1 (Σ0+Σq) d 1 2 + µq Σ-1 s,1 |A| +E[ 16d log 1 δ ∆ min ] mc1 log (1+ n d )+c2 log (1+ m Tr(ΣqΣ -1 0 ) d ) .We give more explanations for the above sequential regret in terms of the following five aspects: ]. If the gap ∆ min ≤ 1/(mn), then ∆ min = 1/(mn) and this may cause a large Bayes regret upper bound.In the concurrent bandit setting, there exists a positive integer L ≤ m, such that 1 ≤ |S t | ≤ L. The concurrent bandit setting is thus more challenging than the sequential bandit setting, because the agent in the concurrent setting needs to interact with multiple bandit tasks in parallel at each round t ≥ 1, and the hyper-posterior Q t will not be updated until the end of round t. Therefore, we need to make an additional assumption on the action space A as follow to facilitate our theoretical analysis.i } d i=1 ⊆ A, a constant β > 0, such that λ d ( d i=1 a i a i ) ≥ β.This assumption is also used in previous works [7, 17] for hierarchical Bayesian linear bandit. It indicates that d i=1 a i a i is a positive definite matrix, and does not weaken the generality of our theoretical results. Actually, if R d is not spanned by actions in A, we can project A into a subspace where the assumption holds. We also need to modify the HierTS algorithm to let the agent take the basic actions {a i } d i=1 for the first d interactions in any task s ∈ [m]. This modification guarantees that the agent explores all directions within the task. Such exploration is very similar to the initialization method in UCB type K-arm bandit algorithms [6, 4] , which choose to pull each arm in the first K rounds. Definec 3 = 1 + B 2 σ -2 κ(Σ 0 ) λ 1 (Σ 0 ) + σ 2 /β that will be used throughout the concurrent Table 2 : Different Bayes regret bounds for multi-task semi-bandit problem. Bayes Regret Bound =Bound I + Bound II + Negligible Terms. m is the number of tasks, n the number of iterations per task, K the size of action set, L the number of pulled actions at each round (1 ≤ L ≤ K). Bound I is the regret bound for solving m tasks, Bound II the regret bound for learning hyper-parameter µ * .A Bound I Bound II [7, Theorem 6] [K] O m nKL log n log (nK) O mnKL log m log (nK) Our Theorem 5.4 [K] O m nL log (nL) log (nK) O L 3 2mn log m log (nK)Our Theorem 5.5 [K] O mL log (nL) log (mnK) O L 3 log (m) log (mnK)setting. Then, analogous to the proof for Theorem 5.1, we bound mnV m,n with a more refined analysis, achieving the following improved Bayes regret bound for HierTS in the concurrent setting. 2Bmd λ 1 (Σ 0 + Σ q )( √ d + µ q Σ-1 s,1)+d√ mn 2mc 1 log (1+ n d )+2c 2 c 3 log (1+ m Tr(Σ q Σ -1 0 ) d ).The concurrent regret bound in Theorem 5. (Σ 0 + Σ q )( √ d + µ q Σ-1 s,1). This is due to the fact that we take the basic actions {a i } d i=1 first for each task s ∈ [m] in the modified HierTS algorithm.(2) The bound for learning the hyper-parameter µ * has an additional multiplicative factor c 3 . This is the price for deriving regret bounds in the concurrent setting. Nevertheless, when compared with the latest concurrent regret bound in [17, Thm 4] for HierTS, our concurrent regret bound in Theorem 5.3 removes the log (mn) factor in both the regret bound for learning m bandit tasks and the regret bound for learning hyper-parameter µ * . Detailed comparisons between different concurrent regret bounds for multi-task linear bandit setting are listed in Table 3 . Furthermore, utilizing the proof strategy to demonstrate the logarithmic sequential regret for HierBayesUCB in our Theorem 5.2, we can analogously develop a logarithmic concurrent regret upper bound for HierBayesUCB algorithm, which is deferred to our Theorem C.2 in Appendix C due to the limited space of the main paper.In this section, we extend the HierTS and HierBayesUCB algorithms to the multi-task Gaussian combinatorial semi-bandit setting. The pseudo-code of them is shown in Algorithm 2. Algorithm 2 is very similar to Algorithm 1 (i.e. the multi-task linear bandit algorithms), except that the combinatorial Hi-erTS in Algorithm 2 uses the approximation/randomized algorithm ORACLE to solve combinatorial problem A * ∈ arg max A∈A a∈A w(a) and denotes the solution as A * = ORACLE(A, A , w). We adopt the ORACLE operator as in the seminal works [11, 38] to guarantee the efficiency of combinatorial HierTS semi-bandit algorithm. In this section, we only consider the sequential semi-bandit setting (i.e. |S t | = 1) for ease of presentation, and our results can be extended to the concurrent semi-bandit setting. Then, define c 4 = σ 2 + B 2 Lλ 1 (Σ 0 ) + B 2 λ 1 (Σ q )κ(Σ 0 ), we first derive the Bayes regret upper bound for combinatorial HierTS algorithm in the sequential semi-bandit setting.Theorem 5.4 Let |S t | = 1 for any t ≥ 1. Let c ≥ 2 ln nKBλ1(Σ0) √ 2π, then in the multi-task Gaussian semi-bandit setting, the Bayes regret upper bound of combinatorial HierTS is:BR(m, n) ≤ m + c √ mnL 2c 1 m log (1 + nL d ) + 2c 4 Ld log(1 + m Tr(Σ -1 0 Σ q ) d).Detailed comparisons between different Bayes regret bounds for multi-task semi-bandit problem are listed in Table 2 . We can see that, in our Theorem 5.4, both the regret bound O(m √ n log n) for learning m tasks and the regret bound O( √ mn log m log n) for learning hyper-parameter µ * can achieve the same order (w.r.t. m and n) when compared with the latest bound in [7, Thm 6] . Besides, our Bayes regret bound is logarithmic in the number K of items, whereas the Bayes regret bound in [7, Thm 6] is sublinear in K. Therefore, our regret bound becomes sharper when the size of action set is very large, e.g. K >> L. Next, we derive a gap-dependent logarithmic multi-task Bayes regret bound for our proposed combinatorial HierBayesUCB algorithm in the sequential semi-bandit setting.Theorem 5.5 Let |S t | = 1 for any t ≥ 1. Then for any > 0, δ ∈ (0, 1), in the multi-task Gaussian semi-bandit setting, the Bayes regret BR(m, n) of combinatorial HierBayesUCB is bounded bymn +4LBKδλ 1 2 1 (Σ0+Σq)(d 1 2 + µq Σ-1 s,1 ) +E 8L log 1 δ ∆ min 2c1m log (1+ nL d )+2c4Ld log(1+ m Tr(Σ -1 0 Σq) d ) .In Theorem 5.5, if we set δ = 1/(mnK), = 1/(mn), and ∆ min >> , then the regret bound O m log n log (mn) for learning m tasks is logarithmic in n. Such bound is sharper than the latest one O(m √ n log n) in [7, Thm 6] for multi-task semi-bandit. The regret bound O(log m log (mn))for learning hyper-parameter µ * is also sharper than that of O( √ mn log m log n) in [7, Thm 6 ]. Besides, since δ=1/(mnK), the whole Bayes regret bound is also logarithmic in the number K of items. Nevertheless, we should point out that our bounds hold for the multi-task semi-bandits with linear generalization, but [7] focuses on the multi-task K-arm semi-bandits without feature matrix Φ.In this section, we summarize our technical novelties in terms of the following three aspects:(1) For the improved regret bound for HierTS in Theorem 5.1: our proof has three novelties: (i) We apply a novel Cauchy-Schwartz type inequality in Lemma A.2 to bound E (θ s, * -μs,t ) A s, * H t ≤ dE (θ s, * -μs,t ) A s,t 2 H t , leading to a sharper bound without log (mn) factor:BR(m, n) ≤ E t,s∈St dA s,t Σs,t A s,t ≤ dmnV m,n ≤ O(m n log n).(ii) We use a more technical positive semi-definite matrix decomposition analysis (i.e. our Lemma A.1) to reduce the multiplicative factor κ 2 (Σ 0 ) to κ(Σ 0 ). (iii) Define a new matrix Xs,t such that the denominator in the regret is σ 2 + B 2 λ 1 (Σ 0 ), not just σ 2 , avoiding the case that the variance serves alone as the denominator. Such technical novelties are also listed explicitly in Table 4 .(2) For the improved regret bound for HierBayesUCB in Theorem 5.2 in the sequential bandit setting: our novelty lies in decomposing the Bayes regret BR(m, n) = E t≥1 s∈St ∆ s,t into three terms:E t≥1 s∈St ∆ s,t = E t≥1,s∈St ∆ s,t 1{∆ s,t ≥ , E s,t } + 1{∆ s,t < , E s,t } + 1{ Ēs,t } ,and bounding the first term with a new method as well as the property of BayesUCB algorithm as E∆ s,t 1{∆ s,t ≥ , E s,t } = E ∆ 2 s,t ∆ s,t 1{∆ s,t ≥ , E s,t } ≤ E C 2 t,A s,t 2 Σs,t log 1 δ /∆ min ≤ O m log (n) log 1 δ δ=1/mn = ===== = O m log (n) log (mn) .(3) For the improved regret bounds for HierTS and HierBayesUCB in the concurrent setting and in the semi-bandit setting: besides the aforementioned technical novelties in (1) and (2), the additional technical novelty lies in leveraging more refined analysis (e.g. using Woodbury matrix identity) to bound the gap between matrices Σ-1 t+1 and Σ-1 t (more details is shown in Lemma C.1 and Eq. ( 6)). 
experiments: 
 In this section, we conduct experiments in the linear bandit setting to verify our theoretical results. Specifically, we show the influence of hyper-parameters (e.g. m, n, L) to the multi-task Bayes regret of HierTS and HierBayesUCB, to validate the consistency between their regret bounds and practical performance. Besides, we compare the performance between our algorithms and other baselines, to show the effectiveness of hierarchical Bayesian bandit algorithms in the multi-task bandit setting. Experimental Setting. We follow the same experimental setting as that in [7, 17] . Concretely, we conduct linear bandit experiments with Gaussian reward. The synthetic problem is defined as follows.In most experiments, we set the number of total tasks as m = 10, the dimension of action space as d = 4, the number of concurrent tasks as L = 5, the number of rounds as n = 200m/L. We focus on the finite action space with |A| = 10, and each action is sampled uniformly from [-0.5, 0.5] d . In hierarchical Bayesian model, we set the hyper-prior as zero-mean isotropic Gaussian distribution N (µ q , Σ q ) = N (0, Σ q ), where Σ q = σ 2 q I d ; and set the task variance Σ 0 = σ 2 0 I d . Unless otherwise stated, we set σ q = 1, σ 0 = 0.1, σ 2 = 0.5 for each task in most experiments. We exhibit the regret performance of HierTS algorithm with respect to five hyper-parameters m, L, σ q , σ 0 , σ in Figure 1 (a)-(e) respectively. The regret performance of HierBayesUCB is shown in Figure 2 of Appendix F.Besides, we compare HierTS/HierBayesUCB with other two TS type algorithms that do not learn the hyper-parameter µ * in a hierarchical Bayesian model. The first baseline is the vanilla TS algorithm that samples task parameter θ s, * from the marginal prior N (µ q , Σ q + Σ 0 ). The second baseline is an idealized TS algorithm that knows µ * exactly and uses the true prior N (µ * , Σ 0 ). We call the second baseline as OracleTS, since this TS algorithm accesses more information of µ * than HierTS and vanilla TS algorithm. We show the regret performance of these four bandit algorithms in Figure 1 (f) .Experimental Results. From Figure 1 , we can observe that: (1) In plot (a), the multi-task regret becomes larger with the increase of m and n, which is consistent with our regret upper bound in Theorems 5.1. (2) In plot (b), the regret increases with a higher dimension d. The number L of the concurrent tasks seems do not have a large impact on regret. (3) In plots (c)-(e), the regret decreases with a smaller variance (e.g. σ q , σ 0 and σ) in hierarchical Bayesian model, validating the provable benefits of variance-reduction in regret minimization, which is revealed in our multi-task Bayes regret upper bounds. (4) The task-averaged regret of HierTS is tighter than that of single-task TS algorithm, empirically demonstrating the advantages of multi-task Bayesian bandit optimization paradigm over single-task bandit learning. (5) Our proposed HierBayesUCB achieves lower regret than HierTS. 
conclusions: 
 This paper provides improved Bayes regret bounds for hierarchical Bayesian bandit algorithms in the multi-task Gaussian linear bandit and semi-bandit setting. For linear bandit problem: in the case of infinite action set, we strengthen the preexisting regret bound O(m n log n log (mn)) of HierTS to O(m √ n log n) by a factor of O( log (mn)); in the case of finite action set, we propose a novel HierBayesUCB algorithm that achieves logarithmic regret bound O(m log (mn) log n) under mild conditions. Our regret bounds in the bandit setting hold when the agent solves tasks sequentially or concurrently. Then, we extend the above HierTS and HierBayesUCB algorithms to the multi-task semi-bandit setting and derive improved regret bounds. The synthetic experiments further support our theoretical results. Our future work aims to extend our bounds to the sub-exponential bandit setting. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: the paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: the paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: We first give the following proposition to bound the posterior variance E t≥1 s∈St A s,t 2 Σs,t in the sequential setting. We choose to give the worst-case upper bound on t≥1 s∈St A s,t 2 Σs,t .Proposition A.1 Let c 1 = σ 2 + B 2 λ 1 (Σ 0 ), c 2 = σ 2 + B 2 λ 1 (Σ 0 ) + B 2 λ 1 (Σ q )κ(Σ 0 ), then t≥1 s∈St A s,t 2 Σs,t ≤2mdc 1 log 1 + n d + 2dc 2 log (1 + m Tr Σ -1 0 Σ q d).Proof. EQUATION+ G s,t ) -1 ≤ Σ 0 , then we have A s,t Σs,t A s,t ≤ B 2 λ 1 (Σ 0 ) < B 2 λ 1 (Σ 0 ) + σ 2 . Accordingly, we define a new matrix Xs,t (Σ -1 0 + 1 B 2 λ1(Σ0)+σ 2 <t 1{s ∈ S t }A s, A s, ) -1 , and notice that Xs,t ≥ Σs,t = (Σ -1 0 + 1 σ 2 <t 1{s ∈ S t }A s, A s, ) -1 , and that Xs,1 = Σ 0 . Then recall c 1 = σ 2 + B 2 λ 1 (Σ 0 ), we have t≥1 s∈St A s,t Σs,t A s,t =c 1 t≥1 s∈St A s,t Σs,t A s,t σ 2 + B 2 λ 1 (Σ 0 ) ≤2c 1 t≥1 s∈St log 1 + A s,t Σs,t A s,t σ 2 + B 2 λ 1 (Σ 0 ) =2c 1 t≥1 log 1 + A St,t ΣSt,t A St,t σ 2 + B 2 λ 1 (Σ 0 ) =2c 1 t≥1 m s=1 1{S t = s} log 1 + A s,t Σs,t A s,t σ 2 + B 2 λ 1 (Σ 0 ) ≤2c 1 t≥1 m s=1 1{S t = s} log 1 + A s,t Xs,t A s,t σ 2 + B 2 λ 1 (Σ 0 ) =2c 1 m s=1 t≥1 1{S t = s} log det I + X 1 2 s,t A s,t A s,t X 1 2 s,t σ 2 + B 2 λ 1 (Σ 0 ) =2c 1 m s=1 t≥1 1{S t = s} log det X-1 s,t + A s,t A s,t σ 2 + B 2 λ 1 (Σ 0 ) -log det X-1 s,t =2c 1 m s=1 log det X-1 s,mn+1 -log det X-1 s,1 =2c 1 m s=1 log det I + 1 σ 2 + B 2 λ 1 (Σ 0 ) t≤mn 1{s ∈ S t }Σ 1 2 0 A s,t A s,t Σ 1 2 0 ≤2dc 1 m s=1 log Tr I + 1 σ 2 +B 2 λ1(Σ0) t≤mn 1{s ∈ S t }Σ 1 2 0 A s,t A s,t Σ 1 2 0 d =2dc 1 m s=1 log 1 + t≤mn 1{s ∈ S t }A s,t Σ 0 A s,t d(σ 2 + B 2 λ 1 (Σ 0 )) ≤2mdc 1 log 1 + n d ,where the first inequality holds because the basic inequality x ≤ 2 log (1 + x), ∀x ∈ [0, 1]; the third inequality holds due to the mean-value inequality (d i=1 λ i ) 1 d ≤ d i=1 λi d, for any λ i ≥ 0; the last inequality holds due to the fact that the agent interacts with each task s ∈ [m] at most n times.Before bounding the remaining t≥1 s∈St A s,t Σs,t Σ -1 0 Σt Σ -1 0 Σs,t A s,t , we introduce the following lemma.Lemma A.1 If the square matrices A > 0, B ≥ 0, then λ 1 (I + AB)(I + BA) -1 ≤ λ1(A) λ d (A) .Proof. According to Theorem 7.6.1 in Page 485 of [18] , there exists a non-singular matrix S, such that A = SS , and B = S -ΛS -1 , in which Λ ≥ 0 is a diagonal matrix. Then we have AB = SΛS -1 , BA = S -ΛS . Therefore, applying Weyl's inequality we haveλ d (I + AB)(I + BA) =λ d (I + SΛS -1 )(I + S -ΛS ) =λ d S(I + Λ)S -1 S -(I + Λ)S =λ d S S(I + Λ)S -1 S -(I + Λ) ≥λ d S S λ d (I + Λ)S -1 S -(I + Λ) ≥λ d S S λ d S -1 S -λ d (I + Λ) 2 ≥λ d S S /λ 1 S 1 S = λ d (A)/λ 1 (A).Remark A.1 (Smaller multiplicative factor than the latest one in [17] ) The improvement lies in our sharper upper bound on λ 1 (Σ -1 0 Σs,t Σs,t Σ -1 0 ), and detailed explanations are two-fold: (1) Previous work [17, Appendix B] directly used Weyl's inequality to upper boundEQUATION) Instead of directly using Weyl's inequality, we first propose Lemma A.1 which uses positive semi-definite matrix diagonalization technique to boundλ 1 (I + AB)(I + BA) -1 ≤ λ 1 (A) λ d (A) .Then we apply Lemma A.1 to upper boundλ 1 (Σ -1 0 Σs,t Σs,t Σ -1 0 ) = λ 1 (Σ -1 0 Σs,t Σs,t Σ -1 0 ) ≤ λ 1 (I + Σ 0 Σs,t )(I + Σs,t Σ 0 ) -1 ≤ κ(Σ 0 ),resulting in a smaller multiplicative factor than that in [17] .(EQUATIONTherefore Σt ≤ Σ q . Then applying Lemma A.1 and Weyl's inequality, we haveA s,t Σs,t Σ -1 0 Σt Σ -1 0 Σs,t A s,t ≤ B 2 λ 1 ( Σs,t Σ -1 0 Σt Σ -1 0 Σs,t ) ≤ B 2 λ 1 (Σ -1 0 Σs,t Σs,t Σ -1 0 )λ 1 ( Σt ) = B 2 λ 1 (I + Σ 0 Σs,t )(I + Σs,t Σ 0 ) -1 λ 1 ( Σt ) ≤ B 2 λ 1 (Σ q )λ 1 (Σ 0 ) λ d (Σ 0 ) ≤ B 2 λ 1 (Σ q )λ 1 (Σ 0 ) λ d (Σ 0 ) + B 2 λ 1 (Σ 0 ) + σ 2 .Meanwhile, we estimate the gap between matrix Σ-1 t+1 and matrix Σ-1 t as followEQUATIONwhere the second equality holds due to the Woodbury matrix identity, and the fifth equality holds due to the Sherman-Morrison formula. Then analogous to the proof for (1) Boundingt≥1 s∈St A s,t 2 Σs,t , recall c 2 = σ 2 + B 2 λ 1 (Σ 0 ) + B 2 λ 1 (Σ q )κ(Σ 0 ) we have t≥1 s∈St A s,t Σs,t Σ -1 0 Σt Σ -1 0 Σs,t A s,t ≤2c 2 t≥1 s∈St log 1 + A s,t Σs,t Σ -1 0 Σt Σ -1 0 Σs,t A s,t σ 2 + B 2 λ 1 (Σ 0 ) + B 2 λ 1 (Σ q )κ(Σ 0 ) =2c 2 t≥1 s∈St log det I + Σ 1 2 t Σ -1 0 Σs,t A s,t A s,t Σs,t Σ -1 0 Σ 1 2 t σ 2 + B 2 λ 1 (Σ 0 ) + B 2 λ 1 (Σ q )κ(Σ 0 ) =2c 2 t≥1 s∈St log det Σ-1 t + Σ -1 0 Σs,t A s,t A s,t Σs,t Σ -1 0 σ 2 + B 2 λ 1 (Σ 0 ) + B 2 λ 1 (Σ q )κ(Σ 0 ) -log det Σ-1 t ≤2c 2 t≥1 s∈St log det Σ-1 t+1 -log det Σ-1 t ≤2c 2 log det Σ-1 mn+1 -log det Σ-1 1 =2c 2 log det I + s∈[m] Σ 1 2 q (Σ 0 + G -1 s,mn+1 ) -1 Σ 1 2 q ≤2dc 2 log Tr I + Tr s∈[m] Σ 1 2 q (Σ 0 + G -1 s,mn+1 ) -1 Σ 1 2 q d ≤2dc 2 log (1 + m Tr Σ -1 0 Σ q d ),where the second inequality holds due to Eq. ( 5). Combining (1) and (2) finishes the whole proof.Remark A.2 Actually, we can replace the term Tr(Σ -1 0 Σ q ) in the above regret bound with O(nλ 1 (Σ q )), at the cost of a slightly larger regret upper bound, by bounding (Σ 0 + G -1 s,mn+1 ) -1 ≤ G s,mn+1 in the last but one step in the above (2), instead of bounding (Σ 0 + G -1 s,mn+1 ) -1 ≤ Σ -1 0 . Specifically, we have the following estimation:log Tr(I + s∈[m] Σ 1 2 q (Σ 0 + G -1 s,mn+1 ) -1 Σ 1 2 q ) d ≤ log Tr(I + s∈[m] Σ 1 2 q G s,mn+1 Σ 1 2 q ) d = log 1 + Tr(σ -2 s∈[m] <mn+1 1[s ∈ S ]A s, Σ q A s, ) d ≤ log 1 + σ -2 mnλ 1 (Σ q ) d ,which is O(log (mn)), slightly larger than the regret bound of O(log (m)) in our Proposition A.1.Then we can begin proving our first Bayes regret bound for HierTS in the multi-task Gaussian linear bandit setting. We first give a lemma as follow, which is useful to prove our multi-task Bayes regret bound in the sequential setting.Lemma A.2 (Proposition 2 in [21] ) Let X 1 and X 2 be arbitrary i.i.d. R m valued random variables andf 1 , f 2 measurable maps such that f 1 , f 2 : R m → R d with E f 1 (X 1 ) 2 2 , E f 2 (X 1 ) 2 2 < ∞, then |E[f 1 (X 1 ) f 2 (X 1 )]| ≤ dE[(f 1 (X 1 ) f 2 (X 2 )) 2 ].Theorem A.1 (Theorem 5.1 in the main text). Let |S t | = 1 for all rounds t ≥ 1. Then in the multi-task Gaussian linear bandit setting, the Bayes regret upper bound of HierTS is as follow:BR(m, n) ≤ √ mnd 2mdc 1 log (1 + n d ) + 2dc 2 log (1 + m Tr(Σ q Σ -1 0 ) d ) Proof.Recall that H t = (H s, ) <t,s∈S is the history up to round t, then BR(m, n) = E t≥1 s∈St E[θ s, * A s, * -θ s, * A s,t |H t ] = E t≥1 s∈St E θ s, * A s, * -E[θ s, * |H t ] E[A s,t |H t ] H t = E t≥1 s∈St E (θY t | θ, x t ∼ N (x t θ, σ 2 ). Let P(µ | H) = N (µ; μ, Σ), and G = σ -2 n t=1 x t x t . Then E[θ | H] = (Σ -1 0 + G) -1 (Σ -1 0 μ + B), cov[θ | H] =(Σ -1 0 + G) -1 + (Σ -1 0 + G) -1 Σ -1 0 ΣΣ -1 0 (Σ -1 0 + G) -1 .Proof. By definition, we have cov[θ | µ, H] = (Σ -1 0 + G) -1 , E[θ | µ, H] = cov[θ | µ, H](Σ -1 0 µ + B) where B = σ -2 n t=1 x t Y t . Hence cov[θ | µ, H] does not depend on µ. Then we have E[θ | H] = E[E[θ | µ, H] | H] = cov[θ | µ, H](Σ -1 0 E[µ | H] + B) = (Σ -1 0 + G) -1 (Σ -1 0 μ + B). On the other hand, because cov[θ | µ, H] does not depend on µ, E[cov[θ | µ, H] | H] = cov[θ | µ, H].In addition, since B is a constant conditioned on H, then according to [17, Lemma 2], we have the following result:cov[E[θ | µ, H] | H] = cov[cov[θ | µ, H]Σ -1 0 µ | H] = (Σ -1 0 + G) -1 Σ -1 0 ΣΣ -1 0 (Σ -1 0 + G) -1 .Theorem B.1 (Theorem 5.2 in the main text). Suppose the action set A is finite with |A| < ∞. Let |S t | = 1 for all rounds t ≥ 1. Then in the multi-task Gaussian linear bandit setting, the Bayes regret upper bound of Hierarchical BayesUCB is as follow:BR(m, n) ≤mn + 4B λ 1 (Σ 0 + Σ q ) d + 8d ln 1 ζ + µ q Σ-1 s,1mn|A|δ+ E 8 log 1 δ ∆ min 2mdc 1 log 1 + n d + 2dc 2 log (1 + m Tr Σ -1 0 Σ q d) .In Theorem 5.2 in the main text, we replace d + 8d ln 1 ζ in the right hand side of the above inequality with √ d for ease of exposition. Proof. Define ∆ s,t = θ s, * A s, * -θ s, * A s,t , the event E s,t = {∀a ∈ A : |a (θ s, * -μs,t )| ≤ 2 log 1 δ a Σs,t }, and C t,s,a = 2 log 1 δ a Σs,t . Then we can rewrite the multi-task Bayes regret BR(m, n) as the following equivalent form:E t≥1 s∈St ∆ s,t = t≥1 s∈St E ∆ s,t 1{∆ s,t ≥ , E s,t } + t≥1 s∈St E ∆ s,t 1{∆ s,t < , E s,t } + t≥1 s∈St E ∆ s,t 1{ Ēs,t } .Then we will bound the three terms in the RHS of the above equality respectively.(1) Bounding t≥1 s∈St E ∆ s,t 1{∆ s,t ≥ , E s,t } . Recall that U t,s,a = a μs,t + 2 log 1 δ a Σs,t , then we haveEQUATIONΣs,t∆ min ≤E 8 log 1 δ ∆ min 2mdc 1 log 1 + n d + 2dc 2 log (1 + m Tr Σ -1 0 Σ q d) .where the first inequality holds due to the fact that U First we give an upper bound of ∆ s,t = θ s, * (A s, * -A s,t ). Using Schwartz's inequality, we haveθ s, * (A s, * -A s,t ) ≤ θ s, * Σ-1 s,1 A s, * -A s,t Σs,1 ≤2B λ 1 ( Σs,1 ) θ s, * Σ-1 s,1 ≤ 2B λ 1 ( Σs,1 ) θ s, * -µ q Σ-1 s,1 + µ q Σ-1 s,1.Besides, we also have θ s, * -µ q = θ s, * -µ * + µ * -µ q ∼ N (0, Σ 0 + Σ q ) = N (0, Σs,1 ), then E θ s, * -µ q Σ-1 s,1 ≤ E Σ-1 2 s,1 (θ s, * -µ q ) 2 2 = √ d.E ∆ s,t 1{ Ēs,t } = t≥1 s∈St E E ∆ s,t 1{ Ēs,t } H t ≤2B λ 1 (Σ 0 + Σ q ) d + 8d ln 1 ζ + µ q Σ-1 s,1 t≥1 s∈St E 1{ Ēs,t } H t =2B λ 1 (Σ 0 + Σ q ) d + 8d ln 1 ζ + µ q Σ-1 s,1 t≥1 s∈St P Ēs,t H t ≤4B λ 1 (Σ 0 + Σ q ) d + 8d ln 1 ζ + µ q Σ-1 s,1 mn|A|δ,where the last inequality holds because P Ēs,t H t ≤ 2δ. Combining (1), ( 2) and (3), we achieve the final Bayes regret bound for any δ ∈ (0, 1), > 0, ζ ∈ (0, 1):BR(m, n) ≤ mn + 4B λ 1 (Σ 0 + Σ q ) d + 8d ln 1 ζ + µ q Σ-1 s,1 mn|A|δ + E 8 log 1 δ ∆ min 2mdc 1 log 1 + n d + 2dc 2 log (1 + m Tr Σ -1 0 Σ q d) . Let C t = {s ∈ S t : λ d (G s,t ) ≥ β/σ 2 }Proposition C.1 Let c 1 = σ 2 + B 2 λ 1 (Σ 0 ), c 2 = σ 2 + B 2 λ 1 (Σ 0 ) + B 2 λ 1 (Σ q )κ(Σ 0 ), c 3 = 1 + B 2 σ -2 κ(Σ 0 ) λ 1 (Σ 0 ) + σ 2 /β , then we have t≥1 s∈St 1{s ∈ C t } A s,t 2 Σs,t ≤ 2mdc 1 log (1 + n d ) + 2dc 2 c 3 log (1 + m Tr Σ -1 0 Σ q d).Proof. Note that we havet≥1 s∈St 1{s ∈ C t } A s,t 2 Σs,t = t≥1 s∈St 1{s ∈ C t }A s,t Σs,t + Σs,t Σ -1 0 Σt Σ -1 0 Σs,t A s,t .On event {s ∈ C t }, the modified HierTS samples from the posterior and actually behaves the same as the original HierTS algorithm in Algorithm 1. Then we bound the two terms in the right hand side of the above equality respectively .(1) Bounding t≥1 s∈St 1{s ∈ C t }A s,t Σs,t A s,tSimilar to the proof for Theorem A.1, we have A s,t Σs,t A s,t ≤ B 2 λ 1 (Σ 0 ) + σ 2 and Xs,t (Σ -1 0 + 1 B 2 λ1(Σ0)+σ 2 <t 1{s ∈ S t }A s, A s, ) -1 ≥ Σs,t . Then we can analogously obtaint≥1 s∈St 1{s ∈ C t }A s,t Σs,t A s,t ≤2 σ 2 + B 2 λ 1 (Σ 0 ) t≥1 s∈St 1{s ∈ C t } log 1 + A s,t Σs,t A s,t σ 2 + B 2 λ 1 (Σ 0 ) =2 σ 2 + B 2 λ 1 (Σ 0 ) t≥1 s∈St 1{s ∈ C t } log det X-1 s,t + A s,t A s,t σ 2 + B 2 λ 1 (Σ 0 ) -log det X-1 s,t ≤2 σ 2 + B 2 λ 1 (Σ 0 ) t≥1 m s=1 1{s ∈ C t } log det X-1 s,t + A s,t A s,t σ 2 + B 2 λ 1 (Σ 0 ) -log det X-1 s,t ≤2 σ 2 + B 2 λ 1 (Σ 0 ) m s=1 t≥1 1{s ∈ S t } log det X-1 s,t + A s,t A s,t σ 2 + B 2 λ 1 (Σ 0 ) -log det X-1 s,t =2 σ 2 + B 2 λ 1 (Σ 0 ) m s=1 log det X-1 s,mn+1 -log det X-1 s,1 ≤2d σ 2 + B 2 λ 1 (Σ 0 ) m s=1 log 1 + t≥1 1{s ∈ S t }A s,t Σ 0 A s,t d(σ 2 + B 2 λ 1 (Σ 0 )) ≤2md σ 2 + B 2 λ 1 (Σ 0 ) log 1 + n d = 2mdc 1 log 1 + n d ,where the second inequality holds due to the fact that, if square matrix A ≥ B ≥ 0, then det (A) ≥ det (B), and |S t | ≤ m; the last inequality holds because the agent interact with each task at most n times.(2) Bounding t≥1 s∈St 1{s ∈ C t }A s,t Σs,t Σ -1 0 Σt Σ -1 0 Σs,t A s,t Analysis. The real difference of the proof for the concurrent regret from the sequential regret lies in bounding t≥1 s∈St 1{s ∈ C t }A s,t Σs,t Σ -1 0 Σt Σ -1 0 Σs,t A s,t , because |S t | ≥ 1 and the result in Eq. ( 5) (which only holds for the case |S t | = 1) does not hold. To tackle this difference, we reduce the concurrent setting to the sequential setting. Let S t = {I tj } |St| j=1 and define S t,1:i = {I tj } i j=1 . Then at round t, let s = I ti and define Σ-1s,t Σ -1 q + z∈St,1:i-1 (Σ 0 + G -1 z,t+1 ) -1 + z∈[m]\St,1:i-1 (Σ 0 + G -1 z,t ) -1, we estimate the gap between Σ-1 s,t and Σ-1 t as follow:Σ-1 s,t -Σ-1 t = z∈St,1:i-1 (Σ 0 + G -1 z,t+1 ) -1 -(Σ 0 + G -1 z,t ) = z∈St,1:i-1 (Σ 0 + (G z,t + A z,t A z,t σ 2 ) -1 ) -1 -(Σ 0 + G -1 z,t ) = z∈St,1:i-1 Σ -1 0 Σs,t A z,t A z,t σ 2 + A z,t Σz,t A z,t Σs,t Σ -1 0 .Thus we can bound λ 1 ( Σ-1 s,t -Σ-1 t ) and tackle Σ-1 s,t instead of Σ-1 t to reduce the concurrent setting to the sequential setting. We first give a useful lemma as follow.Lemma C.1 For any fixed t ≥ 1 and i ∈ [L], suppose λ d (G s,t ) ≥ β/σ 2 and let s = I t,i . Thenλ 1 ( Σ-1 s,t Σt ) ≤ 1 + B 2 λ 1 (Σ 0 ) σ 2 λ d (Σ 0 ) λ 1 (Σ 0 ) + σ 2 β .Proof. Applying Weyl's inequality, we haveλ 1 ( Σ-1 s,t -Σ-1 t ) Σt + I = λ 1 Σ 1 2 t ( Σ-1 s,t -Σ-1 t ) Σ 1 2 t + I ≤1 + λ 1 ( Σ-1 s,t -Σ-1 t )λ 1 ( Σt ) = 1 + λ 1 ( Σ-1 s,t -Σ-1 t ) λ d ( Σ-1 t ) We first lower bound λ d ( Σ-1 t ).According to Weyl's inequality, we haveλ d ( Σ-1 t ) ≥ λ d (Σ -1 q ) + z∈[m] λ d (Σ 0 + G -1 z,t ) -1 ≥ λ d (Σ -1 q ) + z∈[m] 1 λ 1 (Σ 0 ) + λ 1 (G -1 z,t ) =λ d (Σ -1 q ) + z∈[m] 1 λ 1 (Σ 0 ) + 1 λ d (Gz,t) ≥ λ d (Σ -1 q ) + i -1 λ 1 (Σ 0 ) + σ 2 /β ,where the last inequality holds because the tasks S t,1:i-1 have been sufficiently explored. On the other hand, using our Lemma A.1 we can bound λ 1 ( Σ-1 s,t -Σ-1 t ) as followλ 1 ( Σ-1 s,t -Σ-1 t ) ≤ z∈St,1:i-1 λ 1 ( A z,t A z,t σ 2 + A z,t Σz,t A z,t )λ 1 (Σ -1 0 Σs,t Σs,t Σ -1 0 ) ≤ (i -1) B 2 σ 2 λ 1 (Σ 0 ) λ d (Σ 0 ) .Combining the above results, we haveλ 1 ( Σ-1 s,t Σt ) ≤ 1 + (i -1) B 2 σ 2 λ1(Σ0) λ d (Σ0) λ d (Σ -1 q ) + i-1 λ1(Σ0)+σ 2 /β ≤ 1 + B 2 σ 2 λ 1 (Σ 0 ) λ d (Σ 0 ) λ 1 (Σ 0 ) + σ 2 β .Then, recallc 3 = 1 + B 2 σ -2 κ(Σ 0 ) λ 1 (Σ 0 ) + σ 2 /β , we can bound t≥1 s∈St 1{s ∈ C t }A s,t Σs,t Σ -10 Σt Σ -1 0 Σs,t A s,t as follows:t≥1 s∈St 1{s ∈ C t }A s,t Σs,t Σ -1 0 Σt Σ -1 0 Σs,t A s,t = t≥1 s∈St 1{s ∈ C t }A s,t Σs,t Σ -1 0 Σ 1 2 s,t Σ-1 2 s,t Σt Σ-1 2 s,t Σ 1 2 s,t Σ -1 0 Σs,t A s,t ≤ t≥1 s∈St 1{s ∈ C t }λ 1 Σ-1 2 s,t Σt Σ-1 2 s,t A s,t Σs,t Σ -1 0 Σ 1 2 s,t Σ 1 2 s,t Σ -1 0 Σs,t A s,t ≤ 1 + B 2 σ 2 λ 1 (Σ 0 ) λ d (Σ 0 ) λ 1 (Σ 0 ) + σ 2 β E t≥1 s∈St 1{s ∈ C t }A s,t Σs,t Σ -1 0 Σs,t Σ -1 0 Σs,t A s,t ≤2c 3 c 2 log det Σ-1 mn+1 -log det Σ-1 1 ≤2dc 3 c 2 log (1 + m Tr Σ -1 0 Σ q d ),where the second inequality holds due to Lemma C.1, the third and the fourth inequality hold in the same way as that in the proof of Bounding (2) in Proposition A.1. Combining the results in (1) and(2) finishes the whole proof.Remark C.1 In the last step of proof for Lemma C.1, we boundλ 1 ( Σ-1 s,t Σt ) ≤ 1 + (i -1) B 2 σ 2 λ1(Σ0) λ d (Σ0) λ d (Σ -1 q ) + i-1 λ1(Σ0)+σ 2 /β ≤ 1 + (i -1) B 2 σ 2 λ1(Σ0) λ d (Σ0) i-1 λ1(Σ0)+σ 2 /β .Thus our upper bound is independent of the number L of the concurrent tasks. Actually, ∀i ∈ [L]:λ 1 ( Σ-1 s,t Σt ) ≤ 1 + B 2 σ 2 λ1(Σ0) λ d (Σ0) λ d (Σ -1 q ) (i-1) + 1 λ1(Σ0)+σ 2 /β ≤ 1 + B 2 σ 2 λ1(Σ0) λ d (Σ0) λ d (Σ -1 q ) L + 1 λ1(Σ0)+σ 2 /β , the sharper bound 1 + B 2 σ 2 λ 1 (Σ 0 ) λ d (Σ 0 ) λ d (Σ -1 q ) L + 1 λ 1 (Σ 0 )+σ 2 /β is L-dependent. If λ d (Σ -1 q ) L << 1 λ1(Σ0)+σ 2 /β , theinfluence of L to the regret may be large; otherwise, the influence of L to the regret may be negligible.Next, we prove the concurrent regret bound for HierTS and HierBayesUCB.Theorem C.1 (Theorem 5.3 in the main text). Let |S t | ≤ L ≤ m for all rounds t ≥ 1. Then in the multi-task Gaussian linear bandit setting, the Bayes regret bound of HierTS is as follow:BR(m, n) ≤2Bmd λ 1 (Σ 0 + Σ q )( √ d + µ q Σ-1 s,1 ) + md 2nc 1 log (1 + n d ) + √ mnd 2dc 2 c 3 log (1 + m Tr Σ -1 0 Σ q d).Proof. Recall that C t = {s ∈ S t : λ d (G s,t ) ≥ β/σ 2 } is the set of sufficiently-explored tasks at round t. Then, due to the modification of HierTS algorithm, we decompose Bayes regret BR(m, n) into two terms and bound them respectively:EQUATIONBounding E t≥1 s∈St 1{s / ∈ C t }θ s, * (A s, * -A s,t ). Similar to the proof for Theorem B.1 (3), we haveθ s, * (A s, * -A s,t ) ≤ θ s, * Σ-1 s,1 A s, * -A s,t Σs,1 ≤ 2c λ 1 ( Σs,1 ) θ s, * -µ q Σ-1 s,1 + µ q Σ-1 s,1,and E θ s, * -µ q Σ-1 s,1 ≤ E Σ-1 2 s,1 (θ s, * -µ q ) 2 2 = √ d.Recalling the independence between θ s, * and actions A s,t yieldsE t≥1 s∈St 1{s / ∈ C t }θ s, * (A s, * -A s,t ) ≤ 2B λ 1 (Σ 0 + Σ q )E t≥1 s∈St 1{s / ∈ C t }E θ s, * -µ q Σ-1 s,1 + µ q Σ-1 s,1 ≤ 2B λ 1 (Σ 0 + Σ q )( √ d + µ q Σ-1 s,1)md,The last inequality holds because in the modified HierTS, event {s / ∈ C t } occurs at most d times for any task s ∈ EQUATIONBR(m, n) ≤ mn + 4B λ 1 (Σ 0 + Σ q ) d + 8d ln 1 ζ + µ q Σ-1 s,1 mn|A|δ + 2B λ 1 (Σ 0 + Σ q ) √ d + µ q Σ-1 s,1 md + E 8 log 1 δ ∆ min 2mdc 1 log (1 + n d ) + 2dc 3 c 2 log (1 + m Tr Σ -1 0 Σ q d) .Proof. Similar to the proof of Theorem C. ,EQUATIONΣs,t+ mn + 4B λ 1 (Σ 0 + Σ q ) d + 8d ln 1 ζ + µ q Σ-1 s,1 mn|A|δ.Plugging the upper bound onEQUATIONΣs,t in Proposition C.1 into the right hand side of the above inequality finishes the whole proof.We also choose to give the worst-case upper bound on t≥1 s∈St a∈As,t Φ a Σs,t Φ a as follow.Proposition D.1 Let c 1 = σ 2 + B 2 λ 1 (Σ 0 ), c 4 = σ 2 + B 2 Lλ 1 (Σ 0 ) + B 2 λ 1 (Σ q )κ(Σ 0 ), then t≥1 s∈St a∈As,t Φ a Σs,t Φ a ≤ 2c 1 m log (1 + nL d ) + 2c 4 Ld log(1 + m Tr(Σ -1 0 Σ q ) d ). Proof. Recall that G s,t = σ -2 <t 1{s ∈ S }( a∈As,t Φ a Φ a ), B s,t = σ -2 <t 1{s ∈ S }( a∈As,t Φ a ws (a)), Σ-1 s,t = Σ -1 0 +G s,t , Σ-1 t = Σ -1 q + s∈[m] (Σ 0 +G -1 s,t ) -1 .Then, analogous to the proof for Proposition A.1, we introduce the matrix Xs,tΣ -1 0 + 1 B 2 λ1(Σ0)+σ 2 <t 1{s ∈ S }( a∈As,t Φ a Φ a ) -1 .We next bound t≥1 s∈St a∈As,t Φ a Σs,t Φ a and t≥1 s∈St a∈As,t Φ a Σs,t Σ -1 0 Σt Σ -1 0 Σs,t Φ a .(1) Bounding t≥1 s∈St a∈As,t Φ a Σs,t Φ a .t≥1 s∈St a∈As,tΦ a Σs,t Φ a =[σ 2 + B 2 λ 1 (Σ 0 )] t≥1 m s=1 1{S t = s} a∈As,t Φ a Σs,t Φ a σ 2 + B 2 λ 1 (Σ 0 ) ≤2[σ 2 + B 2 λ 1 (Σ 0 )] t≥1 m s=1 1{S t = s} a∈As,t log (1 + Φ a Σs,t Φ a σ 2 + B 2 λ 1 (Σ 0 ) ) ≤2[σ 2 + B 2 λ 1 (Σ 0 )] t≥1 m s=1 1{S t = s} a∈As,t log det(I + Σ 1 2 s,t Φ a Φ a Σ 1 2 s,t σ 2 + B 2 λ 1 (Σ 0 ) ) =2[σ 2 + B 2 λ 1 (Σ 0 )] m s=1 t≥1 a∈As,t 1{S t = s} log det( X-1 s,t + Φ a Φ a σ 2 + B 2 λ 1 (Σ 0 ) ) -log det( X-1 s,t ) =2[σ 2 + B 2 λ 1 (Σ 0 )] m s=1 log det( X-1 s,mn+1 ) -log det( X-1 s,1 ) =2[σ 2 + B 2 λ 1 (Σ 0 )] m s=1 log det I + 1 σ 2 + B 2 λ 1 (Σ 0 ) t≤mn 1{S t = s} a∈As,t Σ 1 2 s,t Φ a Φ a Σ 1 2 s,t =2[σ 2 + B 2 λ 1 (Σ 0 )] m s=1 log Tr I + 1 σ 2 +B 2 λ1(Σ0) t≤mn 1{S t = s} a∈As,t Σ 1 2 s,t Φ a Φ a Σ 1 2 s,t d =2[σ 2 + B 2 λ 1 (Σ 0 )] m s=1 log 1 + t≤mn 1{S t = s} a∈As,t Φ a Σs,t Φ a d(σ 2 + B 2 λ 1 (Σ 0 )) ≤2[σ 2 + B 2 λ 1 (Σ 0 )]m log (1 + nL d ) = 2c 1 m log (1 + nL d ).(2) Bounding t≥1 s∈St a∈As,t Φ a Σs,t Σ -1 s,t = M M . Using the Wely's inequality, we further haveEQUATIONλ 1 (I + σ -2 M M ) ≤ λ 1 (I) + λ 1 (σ -2 M M ) ≤ 1 + σ -2 a∈As,t λ 1 ( Σ 1 2 s,t Φ a Φ a Σ 1 2 s,t ) = 1 + σ -2 a∈As,t Φ a Σs,t Φ a .Then we can estimate the gap between matrix Σ-1 t+1 and Σ-1 t as follow:EQUATIONwhere the second and the sixth equality hold due to the Woodbury matrix identity. The proof for Eq. ( 6) is similar to the proof for Eq. ( 5), but requires more refined analysis (i.e. the first inequality in Eq. ( 6)) to estimate the lower bound of Σ-1 t+1 -Σ-1 t . Then recall c 4 = σ 2 + B 2 Lλ 1 (Σ 0 ) + B 2 λ 1 (Σ q )κ(Σ 0 ) for brevity, we can bound t≥1 s∈St a∈As,t Φ a Σs,t Σ -1 0 Σt Σ -1 0 Σs,t Φ a as follow:t≥1 s∈St a∈As,t Φ a Σs,t Σ -1 0 Σt Σ -1 0 Σs,t Φ a ≤2c 4 t≥1 s∈St a∈As,t log (1 + Φ a Σs,t Σ -1 0 Σt Σ -1 0 Σs,t Φ a σ 2 + B 2 Lλ 1 (Σ 0 ) + B 2 λ 1 (Σ q )κ(Σ 0 ) ) =2c 4 t≥1 s∈St a∈As,t log det(I + Σ 1 2 t Σ -1 0 Σs,t Φ a Φ a Σs,t Σ -1 0 Σ 1 2 t σ 2 + B 2 Lλ 1 (Σ 0 ) + B 2 λ 1 (Σ q )κ(Σ 0 ) ) =2c 4 t≥1 s∈St a∈As,t log det( Σ-1 t + Σ -1 0 Σs,t Φ a Φ a Σs,t Σ -1 0 σ 2 + B 2 Lλ 1 (Σ 0 ) + B 2 λ 1 (Σ q )κ(Σ 0 ) ) -log det( Σ-1 t ) ≤2c 4 L t≥1 s∈St log det( Σ-1 t+1 ) -log det( Σ-1 t ) =2c 4 L log det( Σ-1 mn+1 ) -log det( Σ-1 1 ) =2c 4 L log det(I + s∈[m] Σ 1 2 q (Σ 0 + G -1 s,mn+1 ) -1 Σ 1 2 q ) ≤2c 4 Ld log Tr(I + s∈[m] Σ 1 2 q (Σ 0 + G -1 s,mn+1 ) -1 Σ 1 2 q ) d ≤2c 4 Ld log(1 + m Tr(Σ -1 0 Σ q ) d ),where the second inequality holds due to Eq. ( 6).Lemma D.1 If a Gaussian random variable X ∼ N (µ, σ 2 ), then E[X1{X ≥ 0}] = µ 1 - Φ G (-µ σ ) + σ √ 2π exp{-µ 2 2σ 2 }. If further µ ≤ 0, then E[X1{X ≥ 0}] = σ √ 2π exp{-µ 2 2σ 2 }.Theorem D.1 (Theorem 5.4 in the main text, Regret Bound of HierTS in the Semi-Bandit Setting).Let |S t | = 1 for any t ≥ 1. Let c ≥ 2 ln nKBλ1(Σ0) √ 2π , c 1 = σ 2 + B 2 λ 1 (Σ 0 ), c 4 = σ 2 + B 2 Lλ 1 (Σ 0 ) + B 2 λ 1 (Σ q )κ(Σ 0 ), then in the multi-task Gaussian semi-bandit setting, the Bayes regret bound of combinatorial HierTS is:BR(m, n) ≤ m + c √ mnL 2c 1 m log (1 + nL d ) + 2c 4 Ld log(1 + m Tr(Σ -1 0 Σ q ) d ).Proof. Note that ws = Φθ s, * , then define g(A, θ) = a∈A Φ a , θ for brevity, we have the following result: BR(m, n) =E t≥1 s∈StΣ q ) d).Combining the above results finishes the whole proof.Theorem D.2 (Theorem 5.5 in the main text, Regret Bound of HierBayesUCB in the Semi-Bandit Setting). Let |S t | = 1 for all rounds t ≥ 1. Letc 1 = σ 2 + B 2 λ 1 (Σ 0 ), c 4 = σ 2 + B 2 Lλ 1 (Σ 0 ) + B 2 λ 1 (Σ q )κ(Σ 0 ), Then for any > 0, δ ∈ (0, 1), ζ ∈ (0, 1), in the multi-task Gaussian semi-bandit setting, the Bayes regret upper bound of combinatorial HierBayesUCB is as follow:BR(m, n) ≤E 8L log 1 δ ∆ min 2c 1 m log (1 + nL d ) + 2c 4 Ld log(1 + m Tr(Σ -1 0 Σ q ) d ) + mn + 4LB λ 1 (Σ 0 + Σ q ) d + 8d ln 1 ζ + µ q Σ-1 s,1mnKδ.In Theorem 5.5 in the main text, we replace d + 8d ln 1 ζ in the right hand side of the above inequality with √ d for ease of exposition.Proof. Define the event E s,t = {∀a ∈ A : |Φ a (θ s, * -μs,t )| ≤ 2 log 1 δ Φ a Σs,t }, and the upper confidence bound U t,s (A) = a∈A Φ a , μs,t + 2 log 1 δ Φ a Σs,t . Let ∆ s,t = g(A s, * , θ s, * )g(A s,t , θ s, * ), then we decompose the Bayes regret into three parts as follow: (2) Bounding t≥1 s∈St E ∆ s,t 1{∆ s,t < , E s,t } .E t≥1 s∈St ∆ s,t = t≥1 s∈St E ∆ s,We trivially have t≥1 s∈St E ∆ s,t 1{∆ s,t < , E s,t } ≤ mn .(3) Bounding t≥1 s∈St E ∆ s,t 1{ Ēs,t } .Note that θ s, * -µ q ∼ N (0, Σs,1 ), and E θ s, * -µ q Σ-1 s,1 ≤ E Σ-1 2 s,1 (θ s, * -µ q ) 2 2 = √ d.Φ a • θ s, * ≤2LB θ s, * 1 -ζ ≤ 2LB λ 1 (Σ 0 + Σ q ) d + 8d ln 1 ζ + µ q Σ-1 s,1, where the first inequality holds due to the Schwartz inequality. Then we have with probability 1 -ζ:t≥1 s∈St E ∆ s,t 1{ Ēs,t } = t≥1 s∈St E E ∆ s,t 1{ Ēs,t } H t ≤ 2LB λ 1 (Σ 0 + Σ q ) d + 8d ln 1 ζ + µ q Σ-1 s,1 t≥1 s∈St E 1{ Ēs,t } H t = 2LB λ 1 (Σ 0 + Σ q ) d + 8d ln 1 ζ + µ q Σ-1 s,1 t≥1 s∈St P Ēs,t H t ≤ 4LB λ 1 (Σ 0 + Σ q ) d + 8d ln 1 ζ + µ q Σ-1 s,1 mnKδ.Combining the results in (1) (2) and (3) finishes the whole proof.In this section, we explain our technical novelties for deriving near-optimal sequential regret bound for HierTS and logarithmic sequential regret bound for HierBayesUCB as follow, when compared with the latest bound in [17] (More detailed explanations can be found in Table 4 ): 4) to achieve a logarithmic Bayes regret upper bound of (log 1 δ )md log n d . Nevertheless, we also need to point out the limitations of our Bayes regret bounds:The Limitations of the Multi-Task Bayes Regret Bounds. Honestly speaking, our regret bounds have two main limitations, because they are: (i) Not advantageous when compared with single-task regret bound. This is because our Bayes regret bounds (e.g. O(m √ n log n) in Theorem 5.1) for hierarchical Bayesian bandit problem are almost the same as the summation of regret bounds of learning m Bayesian bandit task independently. This is also the limitation of existing bounds in this field (see [25, 7, 17] ). √ mnd V m,n = O( √ mnd m log n) = O(m n log n),which is almost the same as the summation of the regret bounds for learning m bandit tasks independently. Therefore, if we can upper bound the posterior-variance V m,n with a bound that is sublinear with respect to m and logarithmic w.r.t. n (e.g. a bound of O( √ m log n)), then the final Bayes regret bound will be much sharper. The upper bounds on the posterior-variance V m,n in existing works (e.g. see [25, 7, 17] in our Table 1 in the main text) are also obtained via purely algebraic techniques and are not sharp either (or even worse).(2) In the proof for Proposition A. ). Such worst-case upper bound is obtained via purely algebraic techniques, ignoring the expectation over the randomness of A s,t and Σs,t . Therefore, we may achieve sharper regret bound by considering the expectation over the randomness in the posterior variance.(3) To derive a sharper and meaningful upper bound on the posterior-varianceEQUATIONΣs,t, we need to consider other bounding technique like concentration inequality, or more technical matrix analysis, to achieve an upper bound that is sublinear w.r.t. the number m of tasks and sublinear w.r.t. the number n of iterations per task. Only in this way can we obtain a multi-task regret bound o(mn) that is sublinear w.r.t. m and sublinear w.r.t. n.(4) On the other hand, we also consider finding the lower bound of posterior-variance V m,n to show that our upper bound on V m,n is tight, or finding the lower bound of multi-task Bayes regret BR(m, n) to show that our multi-task Bayes regret upper bound could not be improved. This serves as one of our ongoing research directions. Experimental Results. From Figure 2 , we have the similar observations as that in Figure 1: (1) In plot (a), the multi-task regret of HierBayesUCB becomes larger with the increase of m and n, which is consistent with our regret upper bound in Theorems 5.2. (2) In plot (b), the regret increases with a higher dimension d, and increases with a larger number L of the concurrent tasks. (3) In plots (c)-(e), the regret decreases with a smaller variance (e.g. σ q , σ 0 and σ) in hierarchical Bayesian model, validating the provable benefits of variance-reduction in Bayes regret minimization. (4) The task-averaged regret of our proposed HierBayesUCB is smaller than that of HierTS, and such improvement becomes larger with the increase of σ q (when compared with σ q = 1.0 in Figure 1 ( (1) There also exists an additional factor log (mn).(2) There exists a paradox in this bound, i.e. variance • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 


Decision: This paper examines the Hierarchical Bayesian multi-task bandit problem, improving the Bayes regret bound of an existing algorithm (HierTS), and proposes a new algorithm (HierBayesUCB) with an improved Bayes regret bound under additional assumptions. 

Throughout the paper, the use of the term "gap-dependent/independent" analysis for Bayes regret is somewhat misleading. The information about the gap (in a frequentist sense) disappears once expectations are taken, as pointed out by Reviewer wPds. The Gap-dependent in this paper corresponds to the structure for the prior. If possible, it is recommended to rewrite Theorem 5.5, etc., using the margin conditions (see e.g., Chakraborty et al., ICML, 2023).

Nevertheless, a number of contributions are still noteworthy. Following the rebuttal and discussion, all reviewers have a favorable view of the paper's contributions and lean toward acceptance.

Reviews: review: paper_summary: paper_summary: This paper revisits the learning problems of (multi-task) Bayesian linear bandit/semi bandits, which is interesting. The improvement of the Bayesian regret bound for the multi-task Bayes regret bound of HierTS is very marginal. For the remaining presented upper bounds, there are still near-optimal up to some $\log$ factors from the regret lower bounds. I do not check the proofs in the appendix in detail, but it seems they are correct and the proofs are well written.

In the introduction section, the description
 “The gap between the cumulative reward of optimal actions in hindsight and the cumulative reward of agent 24 is defined as regret” seems not to be aligned with the learning problems to be solved. For me, I think we still use pseudo rewards. So, we may not care about the optimal actions in hindsight. Instead, we care about the action with the highest mean given a problem instance. 

Questions:

I have a question, when using the notion of Bayesian regret, why is there an instance-dependent gap? For the UCB-based algorithms, I am feeling that it is also possible to have an instance-dependent regret bound using the notion of frequentist regret. Why not do it in that way?



In Line 53, there is a typo. I guess it should be “latest” instead of “latext”.

Can you rotate Table 4? It is hard for readers who use a desktop.
strength_weakness: strength_weakness: see the first box
questions: questions: see the first box
limitations: limitations: Frequentist analysis may be more interesting, but I kind of know the reasons why not to use frequentist regret as the combination of TS and frequentist regret needs to have anti-concentration bounds, which are always hard to develop.
paper_summary: paper_summary: This paper studies the multi-task Gaussian linear bandit and semi-bandit problems. It uses a Bayesian approach to maintain a meta-distribution over the hyper-parameters of within-task parameters. It provides an improved regret bound for the for multi-task for HierTS algorithm in the case of infinite action set. For the same setting, it proposes HierBayesUCB which is the UCB counterpart of HierTS. The authors extend their algorithm to the concurrent multi-task and combinatorial semi-bandit settings as well.
strength_weakness: strength_weakness: The paper is lacking real-world dataset experiments. This could help assess the algorithm's robustness w.r.t model misspecification and gauge the theoretical results consistency w.r.t assumptions violation.
questions: questions: No questions.
limitations: limitations: Yes.
paper_summary: paper_summary: The paper improves the Bayesian regret bound for hierarchical Bayesian bandit algorithms in multi-task bandit and semi-bandit settings. Firstly, it improves the gap-independent bound by a factor of $\mathcal{O}(\sqrt{\log(mn)})$ for infinite action set, $m$ being number of tasks and $n$, the number of iterations per task. For finite action set, the authors propose and analyze HierBayesUCB algorithm and analyze its gap-dependent Bayesian regret. Finally, the paper extends these algorithms to multi-task combinatorial semi-bandit setting.
strength_weakness: strength_weakness: The main weakness of the paper is the requirement of Gaussian distributions for each layer of the hierarchy including the noise. While such an assumption facilitates the development of closed-form posteriors to ease the learning task, it is highly restrictive since in many cases, the noise is not Gaussian (assuming sub-Gaussian would be better, many classes of noise distributions including uniform, truncated Gaussian or Rademacher could be accommodated). This should at least be mentioned in the abstract since the current abstract gives the sense of a more general theory being developed in the paper.
questions: questions: Here are a few questions regarding the paper:
1. In the case of several tasks, what is the benefit of assuming a hierarchical structure rather than dealing with each task independently? In Bayesian hierarchical models, this kind of shared structure often allows borrowing of strength across the different groups (tasks here), so that the overall rate could be better -- in this case, the overall regret is linear in $m$, which seems to be similar to that of dealing with the tasks independently. Can the authors shed more light on this. 
2. Is it possible to use this result to derive frequentist regret bounds (either high probability bounds or in expectation), given either some true $\theta_{s}^*$. To keep the tasks exchangeable, one can alternatively assume a true $Q^*$ and $\{\theta_s^*\}$ as latent variables. Furthermore, in the Gaussian case, is the lower bound $\Omega(d\sqrt{n})$ tight in this hierarchical (shared) setting (note that this lower bound is for a linear bandit learning a single task, while in this case, it is not immediately obvious whether or not the shared structure across the tasks could help in the regret bound)
3. I am concerned with the Gaussian assumptions required for all the theoretical results. While the distributions for $Q$ and $\theta_{s}^*|\mu_*$ are fine to assume Gaussian (equivalent to a Gaussian prior on $(\mu_{1}^*,\dots,\mu_{m}^*)$ with dependence structure), the issue is with the Gaussian noise, which is restrictive to apply the method to broader range of problems. Unlike this work, Thompson sampling for linear bandits have been studied where the Gaussianeity assumption in the likelihood is only taken for algorithmic convenience, whereas the theoretical results only require milder assumptions like sub-Gaussianeity (e.g., [Agrawal and Goyal]). Furthermore, the paper does not deal with the case where $\mu_q, \Sigma_q, \Sigma_0, \sigma$ are unknown -- although the experiments place further priors on them, but this essentially makes the model a mixture, whereby the theoretical results are no longer valid. 
4. The term $\mathcal{V}_{m,n}$ is the posterior variance of which distribution?
5. Regarding novelty in technical contribution, it seems the application of the Cauchy Schwarz inequality from [C. Kalkanli and A. Özgür.] (line 204) results in the reduction of the extra factor of $\sqrt{\log(mn)}$ from both Theorems 5.1 and 5.3, which is the main improvement in the paper. For Theorem 5.2, it seems like the fact that $|\mathcal{A}|<\infty$ is the key to reducing the $\sqrt{n}$ factor in the averaged Bayes regret (compared to Theorem 5.1), otherwise, trivially $\Delta_{s,\min}=0$ for compact $\mathcal{A}$ -- however, the additional term of $\log(m)$ is intriguing, can the authors comment on this? The last comment in line 267 shows that if $\Delta_{\min}$ is small, then this bound is much worse, scaling as $m^{3/2}$ (also the additional $\sqrt{\log(mn)}$ reappears).
6. Can the authors comment on the technical difference to remove the polynomial dependence of $K$ to logarithmic in Theorem 5.4 for the combinatorial case?
7. The bound in Theorem 5.5 is stronger than that in [S. Basu, B. Kveton, M. Zaheer, and C. Szepesvári.] in the case $\Delta_{\min}$ is large, otherwise the comment in line 266 would result in a bound worse -- is this correct?
8. Algorithms 1 and 2: Apart from $Q$, the update step for $Q_{t+1}$ also requires the various other likelihood and model parameters (assumed known) like $\mu_q, \Sigma_q, \sigma$ which should be included as input. Also, $\delta$ is an input parameter for the HierBayesUCB algorithm. 
9. The *ORACLE* used in the semi-bandit setting: In practice, this is a combinatorially hard problem (e.g., the work by Chen, Wang and Yuan considers a $(\alpha,\beta)-$approximate oracle for efficiency). No simulation examples were shown to demonstrate the performance and more importantly, the computational complexity, for this important step in both HierTS and HierBayesUCB algorithms.
10. What are the values of $m, n$ in Figure 1(f) -- it seems like HierTS surprisingly performs very poorly, in fact, with higher $T$, vanilla TS might have better regret than HierTS. Any insights as to why this is the case? This is also related to my first question.

Other small comments: In line 153, since $t$ is mentioned as a suffix in $P_{s,t}$, it might be better to use $\mu_t$, i.e. $\mathbb{P}(\theta_{s}^*=\theta|\mu_*=\mu_t, H_{s,t})$. Also, $\hat{\mu}_{s,t}$ in line 160 is not defined till the following page (equation 3).
limitations: limitations: See the questions.
paper_summary: paper_summary: The manuscript discusses a multi-task learning problem and proposes a hierarchical Bayesian (HB) bandit approach. In this approach, the agent maintains a meta-posterior distribution over the hyperparameters of the within-task bandit problems. In the HB bandit, each bandit task is characterized by a task parameter. The paper examines both the sequential and concurrent settings for two types of bandit problems: 1) Gaussian Linear bandit and 2) Semi Bandit. In particular, for both sequential and concurrent bandit in the Gaussian Linear bandit setting:
1. The paper improves upon the existing gap-independent Bayes regret bound of HierTS from O(m \sqrt{n \log n  \log (mn)} ) to O(mn\log n) for infinite actions set where m is the number of tasks and n is the number of iterations per task. 
2. The paper also extends the HierTS and proposes a new algorithm for finite action sets, HierBayesUCB, with gap-dependent O(m \log n  \log (mn)) regret bound. 

Moreover, the paper extends the HierTS and HierBayesUCB for multi-task Gaussian combinatorial semi-bandit setting and derives regret bounds of O(m \sqrt{n} \log n) and O(m \log (mn \log n)).
strength_weakness: strength_weakness: Many parts of the paper can be significantly improved: 
	
1. [Novelty] I don’t think we need the last paragraph in the introduction. Instead, the authors should briefly describe the technical novelty they have introduced to improve the HierTS regret bound for both the sequential and concurrent bandit over the existing works. Why was the previous analysis not sufficient?   What is their novel and non-trivial contribution beyond BayesUCB? Please broadly discuss the novelties summarized in the appendix in the main paper, as this is your main contribution that led to improved bounds. Also, discuss the novelty in the techniques beyond using the improved inequality from [21].

2. 140-141: Why do we need this assumption of at least n-round interaction, and how is it ensured in the algorithm?

3. Alg1 and 2:  How do the algorithms choose the set \mathcal{S}_t of the tasks at each time t? Even the task sequence is also not input to the algorithm. It is not clear to me.


4. What is \hat \mu and \hat \simga in Alg 1 (HierBayesUCB)?  It is not defined yet. I found it to be defined later in (3).

5. display (4): If the order of V_m,n is the same as derived in [17] up to multiplicative factors, how does it help to improve the regret bound?  I cannot find the intuition to understand what improved the bound. The authors must discuss this in the main part of the paper.
questions: questions: 1. L228-229: Please elaborate more on how you have achieved this.

Minor:

- Single task semi-Bandit: L 121-122—The authors should mention in the introduction and abstract that they consider coherent cases of semi-bandit problems.

- L53: Latest

- L143:  Fix  ‘=‘

- L159: insert ‘and’
limitations: limitations: The nature of the work is theoretical.

Comments: title: Thank you for the response.
Thank you for the response.
Response to the Review by Reviewer rxXv (Part 2/2)
Response to the Review by Reviewer diEN (Part 4/4)
Response to the Review by Reviewer diEN (Part 3/4)
Response to the Review by Reviewer diEN (Part 2/4)
comment: Dear Reviewer rxXv,\
     Thank you for the response. We benefit a lot from your reviews and kind suggestions. We will take them into the revision of this paper and give more explanations for our technical contributions. Thank you!\
Best,\
Authors
I thank the authors for their detailed response. I will maintain my score.
Dear Reviewer diEN,\
       Many thanks for your response. We appreciate your support very much, and really benefit a lot from your detailed reviews. We will take your suggestions into the revision to improve the quality of this paper. Thank you!

Best,\
Authors
Thanks for the response. I am overall satisfied with the responses and will raise my score to 6. However, based on the discussion, I feel there are a lot of interesting directions to pursue on various fronts within the current setup.
**Q6. Display (4): If the order of $\mathcal{V} _{m,n}$ is the same as derived in [17] up to multiplicative factors, how does it help to improve the regret bound?**\
A6: Thanks. Our explanations are two-fold: \
$\mathbf{(1)}$ It is true that the order of $\mathcal{V} _{m,n}$ is the same (w.r.t. $m$ and $n$) as derived in [17], but our bound on $\mathcal{V} _{m,n}$ has a smaller multiplicative factor (i.e. using our proposed Lemma B.1 to reduce $\kappa^{2}(\Sigma _{0})$ to $\kappa(\Sigma _{0})$), this is where our first improvement lies in.\
$\mathbf{(2)}$ The improvement of the order of regret bound (i.e. w.r.t. to $m$ and $n$) is actually attributed to the novel strategy to transform the multi-task Bayes regret $\mathcal{BR}(m,n)$ into an intermediate regret upper bound that involves the posterior variance $\mathcal{V} _{m,n}$ as the dominant term. Previous work [17, Lemma 1] used traditional UCB bounding technique (with the confidence factor $\delta \in (0,1)$) to derive the intermediate regret upper bound $\sqrt{mn\mathcal{V} _{m,n} \log{(1/\delta)}} + mn\delta$, resulting in the additional multiplicative factor $\sqrt{\log{(1/\delta)}}$ which is $\sqrt{\log{(mn)}}$ if we set $\delta = \frac{1}{mn}$. Our strategies differ from [17] in the following two aspects:\
$\mathbf{(i)}$ For the improved regret bound of HierTS in Theorem 5.1: we leverage a novel Cauchy-Schwartz inequality from [21] to transform the multi-task Bayes regret $\mathcal{BR}(m,n)$ into an intermediate regret upper bound of $O(\sqrt{mn\mathcal{V} _{mn}})$, which is different from the UCB bounding technique and hence removes the additional $\sqrt{\log{(1/\delta)}}$ factor.\
$\mathbf{(ii)}$ For the improved regret bound of HierBayesUCB in Theorem 5.2: we choose to decompose the Bayes regret $\mathcal{BR}(m,n)=\mathbb{E}\sum _{t\geq1}\sum _{s \in \mathcal{S} _{t}}\Delta _{s,t}$ into three terms:
$$\mathbb{E}\sum _{t\geq1}\sum _{s \in \mathcal{S} _{t}}\Delta _{s,t}=\mathbb{E}\sum _{t \geq 1,s \in \mathcal{S} _{t}}\Delta _{s,t}\big[\mathbf{1}\lbrace\Delta _{s,t}\geq \epsilon, E _{s,t}\rbrace + \mathbf{1}\lbrace\Delta _{s,t}< \epsilon,E _{s,t}\rbrace +\mathbf{1}\lbrace \bar{E} _{s,t}\rbrace\big] ,$$ and bound the first term (the main term) with the property of BayesUCB algorithm (with confidence factor $\delta \in (0,1)$) as follow $$ \mathbb{E}\Delta _{s,t} \mathbf{1}\lbrace\Delta _{s,t} \geq \epsilon, E _{s,t}\rbrace=\mathbb{E}\frac{\Delta _{s,t}^{2}}{\Delta _{s,t}} \mathbf{1}\lbrace\Delta _{s,t} \geq \epsilon, E _{s,t}\rbrace \leq \mathbb{E}\frac{C _{t,s, A _{s,t}}^{2}}{\Delta _{\min}^{\epsilon}},$$ leading to the improved intermediate regret bound of $\sum _{t\geq 1, s\in \mathcal{S} _{t}}\frac{8\log{\frac{1}{\delta}}\lVert A _{s,t}\rVert _{\hat{\Sigma} _{s,t}}}{\Delta _{\min}^{\epsilon}}=O(\mathcal{V} _{m,n}\log{\frac{1}{\delta}})$, which is of $O(m\log{n}\log{(mn)})$ if we set $\delta = \frac{1}{mn}$.

**Q7. L228-229: Please elaborate more on how you have achieved this.**\
A7: Thanks. The improvement lies in our upper bound on $\lambda _{1}(\Sigma _{0}^{-1}\tilde{\Sigma} _{s,t}\tilde{\Sigma} _{s,t} \Sigma _{0}^{-1})$, and detailed explanations are two-fold:\
$\mathbf{(1)}$ Previous work [17, Appendix B] directly used Weyl’s inequality to upper bound $$\lambda _{1}(\Sigma _{0}^{-1}\tilde{\Sigma} _{s,t}\tilde{\Sigma} _{s,t} \Sigma _{0}^{-1}) \leq \lambda _{1}^{2}(\Sigma _{0}^{-1}) \lambda _{1}^{2}(\tilde{\Sigma} _{s,t}) \leq \lambda _{1}^{2}(\Sigma _{0}^{-1}) \lambda _{1}^{2}(\Sigma _{0}) = \kappa^{2}(\Sigma _{0}).$$
$\mathbf{(2)}$ Instead of directly using Weyl’s inequality, we first propose Lemma B.1 which uses positive semi-definite matrix diagonalization technique to bound $$\lambda _{1}\big[\big((I+AB)(I+BA)\big)^{-1}\big]\leq \frac{\lambda _{1}(A)}{\lambda _{d}(A)}.$$ Then we apply Lemma B.1 to upper bound 
$$\lambda _{1}(\Sigma _{0}^{-1}\tilde{\Sigma} _{s,t}\tilde{\Sigma} _{s,t} \Sigma _{0}^{-1}) = \lambda _{1}(\Sigma _{0}^{-1}\tilde{\Sigma} _{s,t}\tilde{\Sigma} _{s,t} \Sigma _{0}^{-1})\leq \lambda _{1}\big[\big((I+\Sigma _{0}\tilde{\Sigma} _{s,t})(I+\tilde{\Sigma} _{s,t}\Sigma _{0})\big)^{-1}\big] \leq \kappa(\Sigma _{0}),$$ resulting in a smaller multiplicative factor than that in [17].

**Q8. Single task semi-Bandit: L 121-122—The authors should mention in the introduction and abstract that they consider coherent cases of semi-bandit problems.**\
A8: Thanks for your suggestion, we will clarify in the introduction and abstract that we consider coherent cases of semi-bandit problems in the revised version.

**References**\
[17] Hierarchical Bayesian Bandits. AISTATS 2022.\
[21] An Improved Regret Bound for Thompson Sampling in the Gaussian Linear Bandit Setting. ISIT 2021.
**Q13. No simulation examples were shown to demonstrate the performance of *ORACLE*. operator and more importantly, the computational complexity, for this important step in both HierTS and HierBayesUCB algorithms.**\
A13: Thanks for pointing this out. It is true that in the current work we did not conduct simulation experiments to demonstrate the performance of *ORACLE* operator and combinatorial HierTS/HiereBayesUCB. This paper mainly focuses on providing improved regret analysis and novel algorithms for hierarchical Bayesian bandit/semi-bandit settings. Practical implementation of the proposed hierarchical semi-bandit algorithms is left as one of our research directions.

**Q14. What are the values of $m,n$ in Figure 1(f) -- it seems like HierTS surprisingly performs very poorly, in fact, with higher $T$, vanilla TS might have better regret than HierTS.**\
A14: Thanks. As shown in Experiment section, we set $m=10, n=400$ in Figure 1(f). There are two insights behind the performance of HierTS in Figure 1(f): \
$\mathbf{(1)}$ It is true that in Figure 1(f) (where we set $\sigma _{q}=1$) HierTS outperforms vanilla TS by a small margin. But in Figure 2(f) (where we set a smaller $\sigma _{q}=0.5$) HierTS outperforms vanilla TS much better. Therefore, the outperformance of HierTS over vanilla TS could vary in different hierarchical Bayesian bandit environments. \
$\mathbf{(2)}$ The different outperformance of HierTS over vanilla TS is consistent with our regret bound in Theorem 5.1 for HierTS: our regret bound involves terms $\lambda _{1}(\Sigma _{q})$ and $tr(\Sigma _{q} \Sigma _{0}^{-1})$, which reveals that a larger variance $\sigma _{q}$ leads to a larger regret bound. Hence, the larger variance $\sigma _{q} =1.0$ in Figure 1(f) leads to larger regret of HierTS than that in Figure 2(f) (with a smaller variance $\sigma _{q} =0.5$).

**Q15. In line 153, since $t$ is mentioned as a suffix in $\mathbb{P} _{s,t}$, it might be better to use $\mathbb{P}(\theta _{s,\star}=\theta | \mu _{*}=\mu _{t}, H _{s,t})$. Also, $\mu _{s,t}$ in line 160 is not defined till the following page (equation 3).**\
A15: Thank you for the kind suggestion, we will use $\mathbb{P}(\theta _{s,\star}=\theta | \mu _{\star}=\mu _{t}, H _{s,t})$ in the final version. Besides, $\hat{\mu}$ and $\hat{\sigma}$ in line 160 are the expectation and covariance of the conditional distribution (given the history $H$) of the true task parameter $\theta _{*}$, and we will clarify them when introducing HierBayesUCB algorithm in the revised version.

**References**\
[1] Improved Algorithms for Linear Stochastic Bandits. NeurIPS 2011.\
[7] No Regrets for Learning the Prior in Bandits. NeurIPS 2021.\
[15] Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures. NeurIPS 2023.\
[17] Hierarchical Bayesian Bandits. AISTATS 2022.\
[21] An Improved Regret Bound for Thompson Sampling in the Gaussian Linear Bandit Setting. ISIT 2021.\
[25] Meta-Thompson Sampling. ICML 2021.\
[30] Linearly Parameterized Bandits. MoOR 2010.\
[31] Learning to Optimize via Posterior Sampling. MoOR 2011.\
[32] An Information-Theoretic Analysis of Thompson Sampling. JMLR 2016.
**Q10. Can the authors comment on the technical difference to remove the polynomial dependence of $K$ to logarithmic in Theorem 5.4 for the combinatorial case?.**\
A10: Thanks. We need to admit that the improvement of the polynomial dependence of $K$ to logarithmic in Theorem 5.4 is actually attributed to the $d$-dimensional feature representation of each action. Detailed explanations lie in the two following aspects:\
$\mathbf{(1)}$ If we use our Theorem 5.4 to derive regret bounds for multi-task $K$-armed bandit, then $d=K$ and we need to set the feature representation of the $k$-th arm ($k \in [K]$) as the one-hot vector whose $k$-th element is $1$ and others $0$. Then we need to replace $d$ in our Theorem 5.4 with $K$, and will still get a regret bound for multi-task $K$-armed bandit with polynomial dependence of $K$.\
$\mathbf{(2)}$ Even though our Theorem 5.4 will lead to a regret bound with polynomial dependence of $K$ for traditional $K$-armed bandit problem (without feature representation), our Theorem 5.4 still reveals an insight that: if the size $K$ of arms is truly large (e.g. $K >1000$), representing each action/arm with a $d$-dimensional feature ($d < K$) will result in a sharper regret bound without the polynomial dependence of $K$.

**Q11. The bound in Theorem 5.5 is stronger than that in [S. Basu, NeurIPS2021] in the case $\Delta _{\min}^{\epsilon}$ is large, otherwise the comment in line 266 would result in a bound worse, is this correct?**\
A11: Thanks. It is true that if the gap $\Delta _{\min}^{\epsilon}$ is small and $\epsilon=\frac{1}{mn}$, our bounds in Theorems 5.2 and 5.5 become worse. However, if we choose $\epsilon = \frac{1}{\sqrt{n}}$ (or choose $\epsilon = \frac{1}{n}$ as explained in Answer 9 to **Question 9**), we can still obtain a good regret bound even if the gap $\Delta _{\min}^{\epsilon}$ is small. Detailed explanations are two-fold and will be added in the final version:\
$\mathbf{(1)}$ If we set $\epsilon = \frac{1}{\sqrt{n}}$, $\delta = \frac{1}{n}$, and $\Delta _{\min} >> \epsilon$ (i.e. $\Delta _{\min}$ is large), our regret bound in Theorem 5.2 (similar regret bound in Theorem 5.5 can be derived in a similar way) is of order $O(m\sqrt{n} + m\log^{2}{n}) = O(m\sqrt{n})$ and is still improved over the latest bound $O(m\sqrt{n\log{n}\log{(mn)}})$ in [17, Theorem 3] in Table 1.\
$\mathbf{(2)}$ If we set $\epsilon = \frac{1}{\sqrt{n}}$, $\delta = \frac{1}{n}$, and $\Delta _{\min} \leq \epsilon$ (i.e. $\Delta _{\min}$ is small), our regret bound in Theorem 5.2 is of order $O(m\sqrt{n}+\sqrt{n}\log{n} [m\log{n}])=O(m\sqrt{n}\log^{2}{n})$, which is still comparable with the latest one $O(m\sqrt{n\log{n}\log{(mn)}})$ in [17, Theorem 3].

**Q12. Algorithms 1 and 2: Apart from $Q$, the update step for $Q _{t+1}$ also requires the various other likelihood and model parameters (assumed known) like $\mu _{q}, \Sigma _{q}, \sigma$, which should be included as input.**\
A12: Sorry for the confusion. Actually Algorithms 1 and 2 are general forms of HierTS/HierBayesUCB algorithms (hence for any hierarchical distribution assumption), not the specific forms of HierTS/HierBayesUCB algorithms under hierarchical Gaussian assumption. Therefore, the input of general HierTS/HierBayesUCB algorithms does not necessarily include model parameters like $\mu _{q}, \Sigma _{q}, \sigma$. We will correct the step **Update $Q _{t+1}$ with Eq.(2)** in Algorithms 1 and 2 with **Update $Q _{t+1}$** to avoid confusion in the revised version.
**Q6. The paper does not deal with the case where $\mu _{q}, \Sigma _{q}, \Sigma _{0}, \sigma$ are unknown.**\
A6: Thanks for your comments. Our explanations are two-fold:\
$\mathbf{(1)}$ It is true that the current version is unable to deal with the case where $\mu _{q}, \Sigma _{q}, \Sigma _{0}, \sigma$ are unknown, and this may be one limitation of the algebraic bounding technique (see more explanations in Remark F.1) to derive Bayes regret bounds (in [7,17,25] and ours) for hierarchical Bayesian bandit algorithms. \
$\mathbf{(2)}$ To deal with the case where $\mu _{q}, \Sigma _{q}, \Sigma _{0}, \sigma$ are unknown, we believe we need to leverage other tools (like information-theoretic analysis) to analyze general cases.

**Q7. The term $\mathcal{V} _{m,n}$ is the posterior variance of which distribution?.**\
A7: Sorry for the confusion, our explanations are two-fold:\
$\mathbf{(1)}$ The posterior variance $\mathcal{V} _{m,n} \leq \mathbb{E}\Big[\sum _{t\geq 1}\sum _{s \in \mathcal{S} _{t}}\lVert A _{s,t}\rVert _{\hat{\Sigma} _{s,t}}^{2}\Big]$ is just a notation, not the variance of certain random variable. And the expectation is taken over the randomness of the random variables $A _{s,t}$, $\hat{\Sigma} _{s,t}$.\
$\mathbf{(2)}$ $\mathcal{V} _{m,n}$ measures the variation change of the Mahalanobis-norm of the actions $A _{s,t}$. Therefore, we call it posterior variance as in previous works [7,17].

**Q8. For Theorem 5.2, it seems like the fact that $\lvert\mathcal{A}\rvert < \infty$ is the key to reducing the $\sqrt{n}$ factor in the averaged Bayes regret (compared to Theorem 5.1).**\
A8: Thanks. Our explanations lie in the following two aspects:\
$\mathbf{(1)}$ Actually the fact hat $\lvert\mathcal{A}\rvert < \infty$ is $\mathbf{not}$ the key to reducing the $\sqrt{n}$ factor, because $\lvert\mathcal{A}\rvert$ is the multiplicative factor in the regret bound of Theorem 5.2 and $\lvert\mathcal{A}\rvert < \infty$ is used to ensure that the regret bound will not be infinity.\
$\mathbf{(2)}$ The key to reducing the $\sqrt{n}$ factor in Theorem 5.1 is actually the following strategy to decompose the Bayes regret into three terms: $$ \mathcal{BR}(m,n)=\mathbb{E}\sum_{t\geq1}\sum_{s \in \mathcal{S} _{t}}\Delta _{s,t}=\mathbb{E}\sum _{t\geq 1,s \in \mathcal{S} _{t}}\Delta _{s,t}\big[\mathbf{1}\lbrace\Delta _{s,t}\geq \epsilon, E _{s,t}\rbrace + \mathbf{1}\lbrace\Delta _{s,t}< \epsilon,E _{s,t}\rbrace +\mathbf{1}\lbrace \bar{E} _{s,t}\rbrace\big],$$ and we use the equal transformation $\Delta _{s,t}\mathbf{1}\lbrace\Delta _{s,t}\geq \epsilon, E _{s,t}\rbrace=\frac{\Delta _{s,t}^{2}}{\Delta _{s,t}} \mathbf{1}\lbrace\Delta _{s,t}\geq \epsilon, E _{s,t}\rbrace$ to bound the first term as $$ \mathbb{E}\sum _{t\geq 1,s \in \mathcal{S} _{t}}\Delta _{s,t}\big[\mathbf{1}\lbrace\Delta _{s,t}\geq \epsilon, E _{s,t}\rbrace\big] \leq  \mathbb{E}\sum _{t\geq 1,s \in \mathcal{S} _{t}}\frac{\Delta _{s,t}^{2}}{\Delta _{\min}^{\epsilon}} \leq \mathbb{E}\sum _{t\geq 1,s \in \mathcal{S} _{t}}\frac{(8\log{\frac{1}{\delta}})\lVert A _{s,t}\rVert _{\hat{\Sigma} _{s,t}}^{2}}{\Delta _{\min}^{\epsilon}} = O(\frac{\log{\frac{1}{\delta}}\mathcal{V} _{m,n}}{\Delta _{\min}^{\epsilon}}),$$ leading to the regret bound of order $O(\frac{m\log{n} \log{\frac{1}{\delta}}}{\Delta _{\min}^{\epsilon}})$ in Theorem 5.2 which removes the $\sqrt{n}$ factor in Theorem 5.1.

**Q9. The additional term of $\log{m}$ in Theorem 5.2 is intriguing, can the authors comment on this?**\
A9: Thanks for pointing this out. Our comments are two-fold:\
$\mathbf{(1)}$ The regret bound in our Theorem 5.2 is (informal form) $$O(mn[\epsilon+\delta]+\frac{\log{\frac{1}{\delta}}}{\Delta _{\min}^{\epsilon}}m\log{n}),$$ and becomes $O(\log{(nm)}m\log{n})$ if we set $\delta = \frac{1}{nm}$, $\epsilon = \frac{1}{mn}$ and $\Delta _{\min} > \epsilon$ is large. Therefore, the additional term of $\log{m}$ is actually caused by setting the confidence factor $\delta = \frac{1}{mn}$, which to some extent is an unavoidable term when combining $m$ regret bounds for UCB-type algorithms.\
$\mathbf{(2)}$ We can also remove the additional term of $\log{m}$ by setting $\delta = \frac{1}{n}$, then our Bayes regret bound in Theorem 5.2 becomes $O([mn\epsilon + m]+ \frac{\log{n}}{\Delta _{\min}^{\epsilon}}m\log{n})$, which is order of $O(m\log^{2}{n})$ if we set $\epsilon =\frac{1}{mn}$ and the gap $\Delta _{\min} > >\epsilon$ is large.