Improved Bayes Regret Bounds for Multi-Task Hierarchical Bayesian Bandit Algorithms
Authors: Jiechao Guan
Hui Xiong
Venue: NeurIPS 2024 poster (2024)
Keywords: hierarchical Bayesian bandi/semi-bandit
multi-task bandit
Bayes regret bound
Thompson sampling algorithm
BayesUCB algorithm
Primary area: bandits
TL;DR: We propose novel algorithms and provide improved Bayes regret bounds for multi-task hierarchical Bayesian bandi/semi-bandit setting.

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.

Improved Bayes Regret Bounds for Multi-Task Hierarchical Bayesian Bandit Algorithms
Jiechao Guan'
Hui Xiong
1 AI Thrust, The Hong Kong University of Science and Technology (Guangzhou), China Department of Computer Science and Engineering, HKUST, China {j kjiehhaguan,
@hkust-gz cn
Abstract
Hierarchical Bayesian bandit refers to the multi-task bandit problem 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 algo- rithms in the multi-task linear bandit and semi-bandit settings. For the multi-task linear bandit, we first analyze the preexisting hicrarchical Thompson sampling (HierTS) algorithm, and improve its gap-independent Bayes regret bound from Om n log n log (mn)) to Omm/n log n) in the case of infinite action set, with m being the number of tasks and n the number iterations per task. In the case of finite action set, we propose novel hierarchical Bayesian bandit algorithm, named hierarchical BayesUCB (HierBayysUCCB). that achieves the logarithmic but gap-dependent regret bound (m log (mm) log n) under mild assumptions. All of the above regret bounds hold many variants of hierarchical Bayesian linear bandit problem, including when the tasks are solved sequentially or concurrently. Furthermore, we extend the aforementioned HierTS and HierBayesUCD algorithms the multi-task combinatorial semi-bandii setting. Concretely, our combinatorial HierTS algorithm attains comparable Bayes regret bound Omm log n) with respect the latest one. Moreover, our combinatorial HierBayesUCB yields a sharper Bayes regret bound (m log (mn) log n). Experiments are conducted to validate the soundness of our theoretical results for multi-task bandit algorithms.
Introduction
is a sequential decision-making problem where at each round, an agent has choose action, and receives a stochastic reward without knowing expected value. The gap between the cumulative reward of optimal actions in hindsight and the cumulative reward of agent defined as regret. The goal is 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 news article for user. The actions in this bandit setting are articles and the reward could an indicator of a click from user.
A stochastic bandit 26
6 27
When the agent has to solve multiple bandit tasks, many machine learning researchers resort to multi-task learning/meta-learning paradigm R 34 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 learn low-dimensional representation shared by different bandit tasks, derive sharper cumulative regret bound than that derived by learning each task independently [19] 10). (2)
The second group leverages the similarity of contexts (c.g. the feature of actions) in bandit tasks to improve agent's 's ability to predict rewards in a new task [14] 36). (3) The third group chooses to
CCoresponding Author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

maintain a meta-distribution over the hyper-parameters of within-task bandit algorithms (like Tsallis- INF [23]. OFUL (9. and Thompson sampling [25] 7 [7], 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 pa- rameter. 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 the sequential and concurrent bandit settings respectively. Many ex- isting works considered hierarchical Bayesian bandit problem, and proposed Thompson sampling [33 type algorithms to solve it [25] 7 33). The latest work (17) proposed hierarchical Thompson sampling (HierTS) algorithm and developed a gap-independent Bayes regret bound ((m / 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, 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-bandin setting. Firstly, in the linear bandit setting, we improve the multi-task Bayes regret bound of HierTS to Ommy/ log r2) in the case of infinite action set, strengthening the latest bound in [7 Thm 3] by a factor of ( (loog (mn)).. In the case of finite action set, we propose novel hierarchical Bayesian bandit algorithm, named hierarchical BCyesUCB (HierBayysSUCB), that achieves the logarithmic but gap-dependent regret bound Om log (rmn) 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- talti-task Gaussian combinatorial cuni-bandit setting. Concretely, our combinatorial HierTS algorithm attains comparable Bayes regret bound O h log n) with respect to the latest one in 77 Thm 6]. Moreover, our combinatorial BierBByysUUB yields a sharper but gap-dependent regret bound (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 log n) for HierTS, This bound improves the latest result by factor of O(ylog (mn)). (2) In the case of finite action set, propose novel HierBayesUCB algorithm, and provide gap-dependent logarithmic Bayes regret bound (( 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 HierBayes UCB algorithms to the more general multi-task combinatorial semi-bandit setting and derive improved Bayes regret bounds.
2 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 frequentist regret of O(vdn log n), where 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(v 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 B3 and [30] proposed
algorithms that achieve (d 3/2 n) regret. The regret bound was further improved in [S] to Od n 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 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 infinite: (30) showed that in the Gaussian linear bandit setting, the Bayes regret of any Bayesian bandit algorithm is lower bounded by 2( Z)) [3 for the first time gave the Bayes regret bound of Old./ 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 concise proof. (2)
When the action set is finite: 32 derived tight regret bound of O dn) for TS algorithm with
2

---

sub- Sab-Gaussian reward noise, via a novel information -eeoooetthhhhhcccccoo approach. Recently, B developed a logarithmic Bayes regret bound Od log" 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 ((m))n)), where & is the dimension of oww-dimensional representation. The expected frequentist
regret upper bound for multi--ask adversarial linear bandit in (23) is / n log (1 + VV),, 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 2(m
The most related works to ours are [25] [7], 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 T for direct comparisons. Among them, the latest work [17 proposed the HierT' algorithm and obtained its regret bound of ((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 log n.) in Theorem 5.1 We also propose novel HierBayes algorithm that achieves logarithmic regret bound (m log log (mmm)). 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] 337, c.g. the Bayes regret bound in (36) is O(m n log n + m log" (mn)).
Bayes Regret Bounds for Multi-Task Bayesian Linear Bandit/Semi-Bannt
Hierarchical Bayesian Bandit Algorithms. Hierarchical Bayesian bandit algorithm was first pro- posed by 25 to solve multi-task bandit problems. More hierarchical-type Thompson sampling algorithms based on multi-task/mmet learning frameworks were developed with improved theoretical guarantees and empirical performance (7 [7] (37. There also existed other works investigating hierarchical Bayesian bandit algorithms within the single-task bandit setting. For example, (16] ex- tended the two-level hierarchical Bayesian bandit framework to the deeper multiple-level hierarchial Bayesian bandit framework. [2) generalized the lungl--ffecctpprrmett HierTS algorithm (i.e. the action parameter is centered at 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.
3 Problem Setting
For any positive integer nt, denote [v] = {1, 2,,,,..,, n for brevity. For any square matrix M E Rx denote (MM), (a(M) as its maximum and minimum eigenvalues respectively, denote x(M)=
A (M))Aa as its condition number. The action set A C B B) C I2d is assumed to be compact for some positive constant B > O, where B(0, B) is the closed ball centered at the origin. We use (.) to denote the inner-product between vectors, use (a) or w. 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 E A under the bandit instance 0 is associated with reward distribution (P(-|a, 0). The reward mean of action a under is denoted as r(a; 0) = Ey-rr()a [Y]. and the optimal action under 0 is denoted as A.- arg max, r(a; 0). In the stochastic linear bandit setting, the mean reward of action a E is r(a, 0) = a In Bayesian bandit problem, we further assume that the task parameter 0 is independently and identically distributed (i.i.d.) according to task parameter distribution P(- (u..), which is characterized by an unknown hyper- parammerr /!a-
Single- Task of = (A C A: |A| S L} is a family of subsets of A with up L items, where L S K. w R is a weight vector. The weight of set A E s/ is defined as EocA w(a). We assume that the weights w are drawn i.i.d. from a distribution, and the mean weight is denoted as W= Following previous work (38), we focus the coherent case 30 which assumes that the agent knows feature matrix T E IR R xd such that w = +0, where 0 is the task parameter drawn from TP(-|14)) ). The reward of a subset A E of under the bandit instance 0 is defined as r(A: = =aEA (a) = = a. O). where O. is the transpose of the a-th row of matrix &. We further assume that || - B, Va E A.
In the semi-bandit setting, the action set A= = [K] is set of finite items.
Bandit/Semi-Banditt In this setting, the agent interacts with mn tasks sequentially or concurrently. First, sample the hyper-parameter nt, from hyper-prior Q. Then, for each task E (m), sample the task parameter 0z.- independently from distribution P(-)u.). The learning process can be detailed as follows. At round > 1, the agent interacts with a set
Hierarchical Bayesian Multi-Task
3

---

of tasks S S (m], takes a series of actions A, = (As,))ES,, and receives a series of rewards Y, (Ys.)s.s.. In the bandit setting, Y,,- ~ [(-|AA,,; 8,,, a stochastic reward obtained by taking action Ag,t in task 8 E St; in the semi-bandit setting, Ys,t = (W.,(aa) JaEE,, is a series of stochastic rewards, where Ws.t = Ws + T/s.t w, = $0.... and I/s is a K K-ddmensionaa random noise. The full hierarchical Bayesian
http://eemi-baddii model in the m-task learning setting is exhibited as follow:
(1) p. Q; (2) 02 ~ (..) As E [ml; (3) Y,,r| As,,, 0z,. ~ P(- Os,,), VL 2 1,8 E St.
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:
BR(m, n) E
- r r(A,,t; )).
121 SES,
where As,. arg aa. r(a; 02..) is the optimal action for task E [m]] in the bandit setting, and As,. E arg max r r(A;0,,> 0,,,) is the optimal subset for task & E [m]] in the semi-bandit setting. The expectation is taken over ju, all task parameters (0 seEm). all actions (Az)12 all stochastic rewards (Y1)221. We further assume that the action set A is the same across different tasks for case of exposition, and assume that the learning agent interacts with any task E [m]] for at most n rounds for convenient comparison with exiting regret upper bounds for multi-task bandit/semi-bande problem.
Algorithm
Denote ((,,=((As,,) )E,,.ES,, as the history of all interactions of agent with task &E [mi] and H,=(H as the whole interaction history up round l. We next introduce the specific form of Hierarchical Thompson Sampling (HierTSS) and Hierarchical BayesUCB (HierBayesUCCi) in the multi-task Bayesian linear bandit and semi-bandit settings, and instantiate these two algorithms to the multi-task Gaussian linear bandit (Algorithm[) I
algorithms
and semi-bandit (A (Algorithm 2 problems.
4.1 Hierarchical Thompson Sampling and Hierarchical BayesUCB
At round I, hierarchical Bayesian bandit algorithm samples a typer-parameter μr from the hyper- posterior Q, defined as Q+(m)) = P(u, = ju| He), and then interacts with tasks S, C [m]. Next, we give details of bandit algorithms, and details of semi-bandit algorithms are deferred to Section 5.4
Hierarchical Thompson Sampling. For any task E S,, HierTS samples task parameter Os,t from the distribution (0):)) - IP(O... = 0p,, = μr, Ha,)) and takes the action A., arg ma a 0s,,, where IPs,. (0)p()) is only conditioned on H., due to the independence be- tween task parameter P,,, and other task histories. This process clearly samples bandit instance l,, from the true posterior P(O_.- = HH,,,, which is equivalent to the form: I P(O,. = O nr, H(H,) dd = f ... (0)p) (H)d),, where (0)(()))) x PO) is the posterior probability. C. (0) !. P(y.ee aa: 0) is the likelihood funetion, P(()μ) is the prior probability by Bayes rule.
Hierarchical BayesUCB. For any task E S, in round f, HierBayesUCB computes the upper confidence bound Ur,,,= = a Paatty 2 log Allalls,, for any E A, where Aa. and E., are the expectation and covariance of the distribution (i.e. IP(O,.. = A H.)) of 0s., conditioned on the history He, and then takes action with the highest upper confidence bound Ae,t < arg max Ut.
4.2 Multi-Task Gaussian Linear Bandit and Semi-Bandit
The hierarchical Gaussian environment is generated as follow. In the multi-task linear ban- dit setting: (1) pa NMg, E,), (2) 0,, ~ N Σo), Vs E [m]. (3) Y=,,AA,,, Oa,, N(AA, 02), Vt 1, S In the semi-bandit setting, the only difference lies in step (3) where Y.,,a A 0z., NN (,..)) for any a E Ag,t. Here, Hgg M., 0.,0,.. are d-dimensional vectors; Eg, Eo E Bddd are positive semi-definite covariance matrices. In the above two settings, the reward noise can be regarded as (1 d²). In the following theoretical analysis sections, assume that all of Mg: Egg Eo and a 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 DJ). we can obtain the closed-form form hyper-posterior in round as Q+(u)) = N N(s pr, E.), where the expectation ti and the covariance matrix Σ, of Qe(p) have the following explicit forms:
Fh = E, (5 2 + Σ (Eo + Gzl)) G Baa), 5 E 1 +
Σ
(Eo + G.l)) -1 (2)
[E(m]
2E (ml

---

Algorithm Hicrarchical Bayesian Algorithms Algorithm 2 Hierarchical Bayesian Algorithms
for Multi-Task Linear Bandit Setting
for Multi-Task Combinatorial Semi-Bandit Setting
1: Input: Hyper-prior Q
1: Input: Hyper-prior Q, features & E IR Kxd
2: Initialize Q1 +
2: Initialize Q1 < Q
3: for = 1...... do
3: for f == 2...... do
4: Sample hyper- ayper-parameter pe Qt
4: Sample
Hr ~ Qt
5: Observe tasks S, S [m]
5: Observe tasks S, S [m]
6: for S, do
6: for E St do
7:
Option (HierTS)::
7: Option I (HierTS):
Compute (s, (e)) L.), (4)
Compute P.... ..,,(0 (4)) x (0)(())((()
Sample task parameter P P., 14)
Sample task parameter Out P.P P..e 144)
Take action A., t- arg max a 0g.t
Compute OR..TORACEEAA ,,,0
Option II (Hise)ByyeSUCCB):
Option II (HierBayesUUBB::
Set U1,s,a =a. T + V log }|allss
Compute (A,) = Enca(a" Pa +
for any a E A
2 & Ilalls for all A
Take action Ag, ( f- arg aa Una 8: Observe reward Y,,,
Compute As,t = arg max.ed (A)
Chooose And observe (1))aA),
9: end for
9:
end for
10: Update Q++1
10:
Update Q++1
11:
end for
11:
end for
Here, in the bandit setting ==.==--2 1/8 E St)A,,AAT, and Ba,t = =0-2 188 E Ae) s,, in the semi-bandit setting Gz,t 00 Etet 1(s E Se) (.0.)) and B, Ex {s E &.) Da (a)) After the hyper-parameter (4. is sampled from (1),,, we sample task parameter 0z (0: Ms,t, E.,) for task s, where M..t = (2o 14 + B.,)) is the posterior mean, Σg1 E + G..t the posterior covariance matrix. Such posterior of a linear model is obtained with a Gaussian prior N(,,, Σo) and Gaussian observations (Ys,))s<c,sess, by Bayes rule.
On the other hand, also need to handle P(O... 0 H,). It is not difficult to see that, in the multi-task Gaussian linear bandit/semi-bant bandit setting, 0z.- H,, is Gaussian and denoted as IP(,... e H.) =N)==(((; Pa,,, Ee,t). According to Lemma B.1 P.,t and Ex,t have the following explicit forms:
Pa.: -s: Pu+BBa Ba,r,, E.. Ee,e + Eo.2i "5, S
5 Bayes Regret Bounds
In this section, we provide improved regret bounds of hierarchical Bayesian bandit algorithms for multi-task Gaussian linear bandit/semi-bant problem. Concretely, we provide improved analysis for HierTS in the sequential linear bandit setting (Sections 5. propose a novel HierBayesUCB bandit algorithm with logarithmic regret guarantee (Section [.22,, develop regret bounds for these two algorithms in the concurrent linear bandit setting (Section (.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 to give upper bound on the so-called posterior variance Vm,,, which in the multi-task linear bandit setting is defined and upper bounded as follow:
Vm,n E Σ MEΣIN 14.. <0mm (") dl dloo (T))
Although the above bound Vm, achieves the same order (w.r.t. m, n and d) that in the latest bound of (17 Sect BJ, our bound has a smaller multiplicative factor (see more details in Table In the multi-task semi- bandit setting, the posterior variance V.,.. E
EaEA, 1. S.,,
and can be bounded in similar way. To finish the whole proof, our strategy consists of main steps: (1) The first step is to transform the multi-task Bayes regret (R(m, n2) into an intermediate regret upper bound that involves the posterior variance Vm,,, as the dominant term. (2) The second step is to bound V Vm.., with Eq. (4). Combining the results in steps (1) and (2) yields Bayes regret bound for multi-task hierarchical Bayesian
aeddii/semi--aadee algorithms. Detailed comparisons between our regret bounds and others in the bandit setting are shown in Table [ Next, we define
e =o2+ (En), C2 = x²+B²A, (Eo) + BaA, (F,.))<EE))))) to be used through the whole Section
5

---

Table 1: Different Bayes regret bounds for multi-task d-dimensional linear (or K- Kaaredd) bandit problem in the sequential setting. m is the number of tasks, n the number of iterations per task, A is the action set. Bayes Regret Bound =Bound I + Bound II + Negligible Terms, where Bound I is the regret bound for solving m tasks, Bound II the regret bound for learning hyper-parameter 14..
Bayes Regret Bound
Bound
Bound II
25
Theorem 3]
Finite
O Omm/Kn Ton//Knogg logn)
On K m log (n) log (K)
Theorem 5]
Finite
O (m he////n(logg (log log (n (A))
0 ( dmnnnllogm m) log (n Al)
17
Theorem 3]
Infinite
(md /nndd/nlbe log ( log (mr)
O (d /m log (m) log ( (mz)
Our Theorem 5.1
Infinite
0 0(mdy n log (2)
(O mr log (
Our Theorem 5.2
Finite
Omddoog (7) log (mn))
Odlogg (1) log (mn)
5.1 Improved Regret Bound for HierTS in the Sequential Bandit Setting
In the sequential bandit setting, |S.] = 1. Then, conditioned on H,, it is not difficult to see that in
Bayes regret, each term EiOT, As, 0 As. Hy] = E[(O... -Pa,,) (i,))A,,,, A.,
Hr]. |
and we use a novel
Cauchy-Schwartz type inequality from [21] Prop 2] to bound [[(Os... (,,,)) T As,. |H.], leading
to (R,m, n) < E Ee21 Eves, V /dE [(0,,,, ( A..) 2 [11a] Expand the expression in the
right hand side of the above inequality, we then have BR n) I Er, VdAT, S
v /dmmmmmmp reducing the Bayes regret bound to the posterior variance bound problem. Recalling Eq. 44 achieves our first improved Bayes regret upper bound in the sequential linear bandit setting.
- 1 for any round t. Then in the multi-task Gaussian linear bandit setting, the Bayes regret upper bound of HierTS is as follow:
Theorem 5.1 (Near- Optimal Sequential Regret) Let |
(R(m, n)) S dd 2m/ y mei log (1 + 7) + 02 log (1 + Tr(E,
Our explanations for the above sequential regret bound are three-fold:
(1) The term
n/d) mdv/nc log (1+ (1/d) represents the regret bound for solving m bandit tasks, whose parame- ters 0z.. are drawn i.i.d. from the prior distribution N(,, Eo). Under this assumption, task provides information for any other task, and hence this bound is linear in m. Similar observation was
also pointed out by 225 7 17 (2) The term dy mncy log(1 (og1+mIIIEEFF5)// represents the regret bound for learning the hyper-parameter μ4, Such bound is sublinear in m and is not dominant term when m is large. (3) For a large m, the averaged Bayes regret bound across m tasks is of BR(m, n)/ n//m = Old'n log n). and strengthens the latest averaged bound O(d log n) in [17 Thm 3] by a factor / Vlogn. Besides, since the lower Bayes regret bound for any Bayesian bandit algorithm is (2) [30], our task-averaged Bayes regret bound is within O( D(Vlog n) of optimality and hence is called MNear-Optimal sequential regret bound. We further make a detailed comparison between our regret bound in Theorem and the regret bound [7 Thm 3] in the following remark.
Remark 5.1 (Improvements of Our Theorem 5.1 lover the Latest One) Our sequential regret bound has two improvements over the latest one in [I7. Thm 3, shown in Table Ty: (1) We remove the additional /log (mn) factor both the regret bound for solving m bandit tasks and the regret bound for learning the hyper- pare--prramttr paz (2) In the regret bound for learning hyper-paramets parameter pa,, [[7] has multiplicative factor x²2 (Eo), whereas our multiplicative factor is k(Eo). Such improvement is achieved by using technical mairix analysis proposed in Lemma C. and explained in Remark
5.2 Logarithmic Regret Bound for BayeS in the Sequential Bandit Setting
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 is near optimal, it not easy to derive improved Bayes regret bounds under the same assumptions. Therefore, further assume that the action set A is finite, and propose novel

---

hierarchical Bayesian bandit algorithm, named Hierarchical BayesUCB (HierBayesUCCB) for multi- task linear bandit problem. The pseudo-code of our proposed algorithm shown in Algorithm
Next, we introduce some necessary notations. Let As,t = (As, - AA,,),, As,min = mi (0,, a), Amin = min As,min- For any > 0. let A
max (e, minn]. Define the event Egge= = {Va E A: : |a (aT(0e,, - Me,e)l S v 2 log _ Illalls.... Then, analogous []] we decompose the Bayes regret (R(m, n) =BE EvES,A into three terms: E Ei21, A., 2 c, Es,,} + 1f < c, F + 1 ((Es,)]. We can bound the last two terms trivially with mnle + 28 maxx,, (.s.))) |LAl]. For the first term, we use the fact that As, H4 Lid. | well as the Upper Confidence Bound (UCB) technique reduce it to an intermediate upper bound (Ei21.ess) ||.A,,t1l II S..... log / minss.| Ar. Combining the upper bound over Vm,. in Eq. (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).
Theorem 5.2 (Logarithmicc Sequential Regret of HierBayesUCB) Let |S.] | for any round t, and the action set A is finite with (A] < cc. Then in the mulfi-task Gaussian linear bandit setting, for any 6 E (0, 1), > 0, the Bayes regret (R(m, n) of HierBayesUCB is upper bounded by
16d b [me log (1+ )02 log (1+ m TT(TT }. Ammi
mm c+4B6A7 (Eo+E,)
+1m,,1ss::) (d++,, +
d
We give more explanations for the above sequential regret in terms of the following five aspects:
(1) If let ā = 1/(m), = 1/(m) and Amin >> the above sequential regret bound is of O( log (mn)(mdlogg log (5) + dl log (*) ))) The term O(mdd (mn) log (ā)) represents the regret bound for solving m bandit tasks and is linear in m. Such bound is sharper than the corresponding bound O(md log (5) in our Theorem 5.1 by a multiplicative factor O( O(ylog (n/d) dd/nnll log (mn)), which is less than 1 especially when m
(2) The term Odd (mn) log !h )) represents the regret bound for learning the hyper- hyper-parameter jua, and its contribution to the Bayes regret bound can be negligible. Besides, this bound is sharper than the bound (dl mm log (m/d) d)) in Theorem 5.1 (3) The averaged Bayes regret bound across tasks can be regarded as (R,m, n) /mm = Old log (mn) logn). n). which is logarithmic in n. Therefore, we call our regret bound as 'Logarithmic' sequential regret bound. Moreover, if there exists fixed positive integer << n, such that S n²', then our task-averaged Bayes regret BR (m, n)/m /mm O(dEI A 1 llog n)) matches the latest single-task Bayes regret bound in 3 Thm 5] and is remarkably similar to the frequentist regret Odd min log" n) in [I] Thm 5]. . (4) We can obtain sharper bounds by setting 6, e as different values. For example, by setting 8 = 1/n, our regret bound becomes O(mmcc + m] + logn m log n)).
min
which is of order O(m log" n) if we set = 1/(m)) and the gap Amin >> E is large. (5) We also need to point out that, the Bayes regret bound in Theorem 5.2 scales with B(x!_ If the gap A Amin < 1/ (m)), then A = 1/mm) and this may cause large Bayes regret upper bound.
5.3 Improved Regret Bounds of Hier and HierBayesUCB in the Concurrent Bandit Setting
In the concurrent bandit setting, there exists a positive integer L m, such that 1 < |St| < L. The concurrent bandit setting is thus more challenging than the sequential bandit setting, because the agent the concurrent setting needs to interact with multiple bandit tasks in parallel at each round Qe will not be updated until the end of round t. Therefore, we need to
t t2 1, and the make an additional assumption on the action space A as follow to facilitate our theoretical analysis.
Assumption 5.1 There exist actions {a:}a CAA constant B 8>0, 0, such that > >a(E a;a.) > B.
This assumption is also used in previous works 77 17 for hierarchical Bayesian linear bandit. It indicates that Σ a,a is a positive definite matrix, and does not weaken the generality of our theoretical results. Actually, if Rd 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, | for the first d interactions in any task 8 E [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 Kaarm bandit algorithms (6. 4. which choose to pull each arm in the first K
rounds. Define C3 = 1 + B² - <(E)) (Zo) + o² / that will be used throughout the concurrent
7

---

Table 2: Different Bayes regret bounds for multi-task
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 S K). Bound I is the regret bound for solving m tasks, Bound II the regret bound for learning hyper-parameter Ja..
Bayes Regret Bound
A
Bound
Bound II
7 Theorem 6]
[
Qmm//KKLoognoog (nK))
O V l//nkk L log m log (nK))
Our Theorem 5.4
[K]
(nl.) log (nK))
O [122 Vmn mm log m log (nK))
Our Theorem 5.5
[K]
OmLL (n)) log (mnK))
O log (m) log (mnK))
setting. Then, analogous to the proof for Theorem 5.1 we bound v /mrremm.. with more refined analysis, achieving the following improved Bayes regret bound for HierTS in the concurrent setting.
Under Assumption 5.1 let S | S for any round 2 1. Then in the multi-task Gaussian linear bandit setting, the Bayes regret BR(m, n) of HierTS is upper bounded by
Theorem 5.3
2mmd Ai +i)( 11 || Hd 2mc; log (1+ (1+ log (1+ m. Tr(2,
d
The concurrent regret bound in Theorem 5.3 achieves almost the same order (w.r.. m, n. d) as the sequential regret bound in Theorem [..] but differs in two aspects: (1) The bound for learning m i.i.d. bandit tasks has an additional term Bmd / Ai (Eoo + E.y)
I|//)l=;;)) This due to the fact that we take the basic actions {a first for each task E [m] in the modified HierTS algorithm. (2) The bound for learning the hyper-parameter μ4, has additional multiplicative factor c3. This is the price for deriving regret bounds in the concurrent setting. Nevertheless, when compared with the latest concurrent regret bound in [7 Thm 4] for HierTS, our concurrent regret bound in Theorem [.3 removes the Vlog (mn) factor in both the regret bound for learning bandit tasks and the regret bound for learning hyper-parameter pa. Detailed comparisons between different concurrent regret bounds for multi-task linear bandit setting listed in Table 3 Furthermore, utilizing the proof strategy to demonstrate the logarithmic sequential regret for HierBBaysUCCH in our Theorem [5.2 we can analogously develop 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.
5.4 Improved Regret Bounds for HierTS and HierBayes in the Semi-Bandi Setting
In this section, extend the HierTS and HierBayesUCB algorithms to the multi-task Gaussian com- binatorial semi-bandit setting. The pseudo-code of them is shown in Algorithm 2 Algorithm is very similar to Algorithm 1 (i.e. the multi-task linear bandit algorithms), except that the combinatorial Hi- algorithm ORACLE to solve combinatorial problem A, arg Aax EeEA w(a) and denotes the solution A, ORACLE(A, e, w). We adopt the ORACLE operator as in the seminal works 38) to guarantee the efficiency of com- binatorial HierTS semi-bandit algorithm. In this section, we only consider the sequential semi-bandit setting (i.e. |S,| = 1) for ease of presentation, and our results can be extended to the concurrent semi-bandee setting. Then, define C1 = 0² + B² (Eo) + B² X² (E.),x(22) we first derive the Bayes regret upper bound for combinatorial HierTS algorithm in the sequential semi-bandit setting.
erT'S in Algorithm 2 uses the approximation//rndomiiin
Theorem 5.4 Let |Se| = 1 for any I. 2 1. Let c 2 /2
(X then in the multi-task V
Gaussian semi-bandit setting, the Bayes regret upper bound of combinatorial HierTS is:
m Tr(Ea'Egg) d
BR(m, n) S m evmnly 201m log (1 2 20 2cg
Detailed comparisons between different Bayes regret bounds for multi-tase tasti-task semi-bandit problem are listed in 2 We can see that, our Theorem 5.4 both the regret bound O(m log n) for learning tasks and the regret bound O(y log m log n) for learning hyper-parameter μa, 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
8

---

17 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 task Bayes regret bound for our proposed combinatorial HierBayesU/CB algorithm in the sequential semi-bandi setting.
Theorem 5.5 Let [St] for any 2 1. Then for any e > 0,8 E (0, 1), in the mudti task Gaussian semi-bandit setting, the Bayes regret (R(m, n) of combinatorial HierBayesUCB is bounded by
mn| mTle-A (d) +1|0, 11ll:, +
8L log 8
20am log (1+ nL,, + Ld log(1
m Tr(ED EEg)
imin
d
In Theorem 5.5 if we set = (/(mnK)) c = = 1/(mn), and Aiin >> e, then the regret bound (m log n log (m)) for learning m tasks is logarithmic n. Such bound sharper than the latest one O(myn log n) in 7 Thm 6] for multi-task coni-bandit. The regret bound (log m log (mn)) for learning hyper-parameter μ4, is also sharper than that of O( P(/m log m logn) in 77 Thm 6]. Besides, since 6-1/(mmh items. Nevertheless, should point out that our bounds hold for the multi-task semi-bandits with linear generalization, but 7 focuses on the multi-task K Karr remi-bandits without feature matrix ob
the whole Bayes regret bound is also logarithmic in the number K of
5.5 Technical Novelties for Deriving Improved Regret Bounds
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-Schwart type inequality in Lemma A.2 to bound [0,, Po,e)* As,* He] S
V [IE ((O,,. (e,,) T A.,)) 2 H.... leading to sharper bound without / Vlog (me) factor:
BR(m, n) S Σ VaAT,Ee.As.. S VdmnV S O(m /imn//lognn
t,
(ii) We use more technical positive semi-definite matrix decomposition analysis (i.e. our Lemma to reduce the multiplicative factor x²2 x²²(E) to k(Eo). (iii) Define a new matrix X.,, such that the denominator in the regret is 0² + B Xı (Eio). not just 0², avoiding the case that the variance serves alone the denominator. Such technical novelties are also listed explicitly in Table
(2) For the improved regnet bound for HierBayes UCB in Theorem 5.2 in the sequential bandit setting: novelty lies in decomposing the Bayes regret (m,, n) E E.>1 E.es. As,t into three terms:
E
Σ Σ
A.. = Σ A., c, E.,) 1(4., <e E..) + 1(Es,:))
SES.
12,,
and bounding the first term with new method as well the property of BayesUCB algorithm
A s. I(A,t 2 e, F.s,) S E. A
CLa.A.
E. 1(D, 2 F..t)
A,,t
resulting in the final improved gap-dependent regret bound for HierBayesUCB as follows
Σ |AA,,ll 121,ESS
log / min S O0mlog (n) log 8
6= 1/ma
(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 Σ7t1 and E-- (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, ni, L) to the multi-task Bayes regret of HierTS and HierBayesUCBB, 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.

---

Linear Bandit (d (=1)
Linear Bandi: (m 10, 0.5)
Liner Bandit (4 4, Lx5)
800
1000
6pm
1.50
432
Rogret
Ragntt
6,-2
100
50
100
200
0
10
10
100
2000
300
400
Number of Tasks
Number of Concurent Trokes 7.
Round
(a) Regrets w.r.t. different m
(b) Regrets w.r.t. different I.
(c) Regrets w.r.t. different og
Linser Bandit (d 4, no 2-5)
Bardit Z::)
Linear R, dy 1.0)
10:00
CrackeT
0um23
10C0
300
HieHS
15
num12
200
200
500
100
100
300
200
Round
Round
(d) Regrets w.r.t. different do
(c) Regrets w.r.t. different a
(f) Regrets of different algorithms
Figure 1: Regrets of HierTS algorithm with respect to (w.rt.) different hyper-parameters.
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 = 200mm LL. We focus on the finite action space with |A| = 10, and each action is sampled uniformly from [-0.5, 0.5)4. In hierarchical Bayesian model, we set the hyper-prior as zero-mean isotropic Gaussian distribution Ning [g)) = E.))., where Σg = o² a and set the task variance Eg = of l- Unless otherwise stated, we set 0g = 1, on = 0.1, 6² 0.5 for each task in most experiments. We exhibit the regret performance of HierTS algorithm with respect to five (a)-(e) respectively. The regret performance of HierBayesUCB is shown in Figure O Appendix F
m, L, oy: 0o, o in Figurel
Besides, we compare HierTT//HirBayyeSUCG with other two TS type algorithms that do not learn the hyper-parameter μ² in a hierarchical Bayesian model. The first bascline is the vanilla TS algorithm that samples task parameter 6,,, from the marginal prior N (P2. Eg + Eo). The second baseline an idealized TS algorithm that knows μ.x exactly and uses the true prior N (M,, Eo). 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).
observe that: (1) In plot (a), the multi-tast 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 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 (c.g. Tg. To and σ)) in hierarchical Bayesian model, validating the provable benefits of variance-reductio
Experimental Results. From Figure [
in regret minimization, which is revealed in our multi-task Bayes regret upper bounds. (4) The task-averaged regret of HierTS 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.
7 Conclusions
This paper provides improved Bayes regret bounds for hierarchical Bayesian bandit algorithms the multi-task Gaussian linear bandit and semi-bandit setting. For linear bandit problem: in the case of infinite action set, strengthen the preexisting regret bound O(m log log (mn)) of HierTS to Ommy' log n)) by a factor of O( Plo (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-rask 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.
10

---

Acknowledgments and Disclosure of Funding
Jiechao sincerely appreciates the financial support from the People's Government of Guangzhou Municipality for his postdoctoral project. We thank all reviewers for their constructive suggestions improve the quality of this paper. This work was supported in part by the National Key R&D in part by the National Natural Science Foundation
Program of China (Grant No.20033FF0725000 of China (Grant No. 00.92270204), part by the guangdong Basic and Applied Basic Research Foun- dation No. 11.220231111120007777 51122057), in part by Baannghou-HKKSSTRR Joint Funding Program (Grant No.2023443300008, Education Bureau of Guangzhou Municipality.
References
[1] Y. Abbasi- Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. In NeurlPS, pages 2312-2320, 2011.
[2] Aouali, B. Kveton, and Katariya, Mixed-effeee thompson sampling. In AISTATS, pages 2087-2115, 2023.
[3] A. Atsidakou, B. Kveton, S. Katariya, C. Caramanis, and sujay sanghavi. Finite-time logarithmic bayes regret upper bounds. NewrlPS, 2023.
[4] J. Audibert and S. Bubeck. Minimax policies for adversarial and stochastic bandits. In Conference on Learning Theory (COLT), 2009.
[5] Auer. Using confidence bounds for exploitation-exxloratio trade-offs. Journal of Machine Learning Research (JMLR), 3:397-423 2002.
[6] Auer, Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, (7(-3))235--256 2002.
[7] S. Basu, B. Kveton, M. Zaheer, and C. Szepesvári. No regrets for learning the prior in bandits. In NeurlPS, pages 28029-280411 2021.
[8] R. Caruana. Multitask learning. Machine Learning, 28(1):41-75, 1997.
[9] L. Cella, A. Lazaric, and M. Pontil. Meta-learning with stochastic linear bandits. In ICML, pages 1360-1370, 2020.
[10] L. Cella, K. Lounici, G. Pacreau, and M. Pontil. Multi-task representation learning with stochastic linear bandits. AISTATS, pages 4822 4847, 2023.
[11] W. Chen, Y. Wang, and Y. Yuan. Combinatorial multi-armed bandit: General framework and applications. In ICML, pages 151-159, 2013.
[12] W. Chu, L. Li, L.. Reyzin, and R. E. Schapire. Contextual bandits with linear payoff functions. In AISTATS, pages 208-214, 2011.
[13] V. Dani, T. P. Hayes, and S. M. Kakade. Stochastic linear optimization under bandit feedback. In Conference on Learning Theory (COLT)) pages 355-366, 2008
[14] A. A. Deshmukh, Ü. Dogan, and C. Scott. Multi-task learning for contextual bandits. In NeurlPS, pages 4848-4856, 2017.
[15] H. Flynn, D. Reeb, M. Kandemir, and J. Peters. Improved algorithms for stochastic linear bandits using tail bounds for martingale mixtures. In NewrIPS, 2023.
[16] J. Hong, B. Kveton, S. Katariya, M. Zaheer, and M. Ghavamzadeh. Deep hierarchy in bandits. In ICML, pages 8833-8851, 2022.
[17] Hong, B. Kveton, M. Zaheer, and M. Ghavamzadeh. Hierarchical bayesian bandits. In AISTATS, pages 7724-7741, 2022.
[18] R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, 2012.

---

[19] J. Hu. X. Chen, C. Jin, L. Li, and L. Wang. Near-optimal representation learning for linear bandits and linear RL. In ICML, pages 4349-4358, 2021.
[20] S. Kale, L. Reyzin, and R. E. Schapire. Non-stochastic bandit slate problems. In NeurIPS, pages 1054-1062, 2010.
[21] C. Kalkanli and A. Özgür. An improved regret bound for thompson sampling in the gaussian linear bandit setting. In IEEE International Symposium on Information Theory (ISIT), pages 2783-2788, 2020.
[22] E. Kaufmann, O. Cappe, and A. Garivier. On bayesian upper confidence bounds for bandit problems. In AISTATS, pages 592-600, 2012.
[23] M. Khodak, I. Osadchiy, K. Harris, M. Balcan, K. Y. Levy, R. Meir, and Z. S. Wu. Meta-learning adversarial bandit algorithms. In NeurIPS, 2023.
[24] R. D. Kleinberg and T. Leighton. The value of knowing demand curve: Bounds on regret for online posted-price auctions. In Symposium on Foundations Computer Science (FOCS), pages 594-600 605,605,222 2003.
[25] B. Kveton, M. Konobeev, M. Zaheer, C. Hsu, M. Mladenov, C. Boutilier, and C. Szepesvári. Meta-thompson sampling. In ICML, pages 5884-5893, 2021.
[26] T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6:4-222, 1985.
[27] T. Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[28] L. Li, W. Chu, J. Langford, and R. E. Schapire. A contextual-bandit approach to personalized news article recommendation. In International Conference on World Wide Web (WWW), pages 661-670, 2010.
[29] Y. Li, Y. Wang, and Y. Zhou. Nearly minimax-optimal regret for linearly parameterized bandits. In Conference on Learning Theory (COLT), pages 2173-2174, 2019.
[30] P. Rusmevichientong and J. N. Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395-411, 2010.
[31] D. Russo and B. Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4): 1221-12221223 2014.
[32] D. Russo and B. V. Roy. An information-theorrtie analysis of thompson sampling. Journal of Machine Learning Research (JMLR), 17:68:1-68 1-68:30, 2016.
[33] W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25:285-294, 1933.
[34] S. Thrun and L. Pratt. Learning Learn. Kluwer Academic Publishers, 1998.
[35] M. J. Wainwright. High--Dimnssooal Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, 2019.
[36] R. Wan, L. Ge, and R. Song. Metadata-based multi-task bandits with bayesian hierarchical models. In NeurIPS, pages 29655-29668, 2021.
[37] R. Wan, L. Ge, and R. Song. Towards scalable and robust structured bandits: meta-learning framework. In AISTATS, pages 1144 1173, 2023.
[38] Z. Wen, Kveton, and Ashkan. Efficient learning in large-scale combinatorial semi-bandits In ICML, pages 1113-1122, 2015.
[39] Z. Wen and B. V. Roy. Efficient exploration and value function generalization in deterministic systems. In NeurlPS, pages 3021-3029, 2013.
12

---

APPENDIX
Proofs for Regret Bound of HierTS in the Sequential Bandit Setting
We first give the following proposition to bound the posterior variance E Ei21 EsEs, 1| D.. in the sequential setting. We choose to give the worst-case upper bound on Σ,²/ Exes, |
Proposition A.1 Leta = 0² + (P))( c2= = + (Bo) + (Fg))()))(( then 52mder log (1+ ")= + 2dc² log (1 +
m TT 1 Ezn) )
ΣΣ AAnell3
d
11 .ES.
Proof. Note that | Sin
50 54 10 10.011150000 s.,t)) As,t, then we bound Eiz1 Eves, || Eee and E1z1 Exes, 1,, 11 15, respectively.
= (Ts + Deyt 5
(1) Bounding E1z1 ExEs, ||A,,113 Note that E.tt (2T + G,,:) -1 S Eo, then we have AT, I Bd (Eo) < <B²>1(Eu) + 0². Accordingly, we define a new matrix Xy,1 - (E 12) +02 Eist 1ls E Si) A1),,,,4,,))+ and notice that Xx,, 2 Eg,t (Ej² + 2/ Ees
S. A.A.A,AA,
and that X., = Vo. Then recall c₁ = o² + A1 we have
ΣΣ S.,ttAAsst
A AT,
=0
0² (20)
SES
log (1+ A
22c
0² (Zo)
121 NES,
S.,t A
-201
log (1 + 0² + B²A1 (En)
121
m
AT, Aeet
=2c
Σ
1(; = log (1
0² + (
121
A Aoit
<2c
Σ
1(8 = log (1 + 0² + B² (Eo)
(21 s=1
x3 Ag, 1A A,,, X2,1 5.1
-2c1
1( = $) let (T
0² + Ba \₂ (En)
s=1 121
A,,
2e1
1(S = $} log det (X x
log det X
0² + 12 12
m
-2c1
logdet (X - log det X-11
2e1
log det (T + 0²+ B2>r (Eo)
Σ
1f8 S.j2. Ast J, zi)
1=1
Ismm
m
Tr (I+ + o² Dz (Eo)
Eismn lfs E S A,,
<2de
log
d
13

---

Eismn E [fsESi)AT, S, d(o2+ 13A1(200)
=2dc log (1+
==1
<2mde log (1 ) )).
where the first inequality holds because the basic inequality S log (1 + x), Vr E [0, 1]: the third
inequality holds due to the mean-value inequality (I[=_ A,) < Σ for any X; 2 0; the last
inequality holds due the fact that the agent interacts with each task s [m] at most n times.
Before bounding the remaining Σ121 Exes, A E E ing lemma.
En E. As,t introduce the follow-
Lemma A.1 If the square matrices A 0, B 2 0, then X [((1 + AB)(I + BA)) =1 S
(z(A) Aa(
Proof. According to Theorem 7.6.1 in Page 485 of [8], there exists non-singular matrix S, such that A = SS and B = S AS-1, in which A 2 0 is a diagonal matrix. Then we have AB = SAS-1, BA S AST. Therefore, applying Weyl's inequality we have
+ + BA)
=>a(ST (A0(SSSS((+))-----110
2Aa(S ()((())))((()))----111 (I++A))
2 2Aa(sT ())((
= (A((A//A(AA)
Remark A.1 (Smaller multiplicative factor than the latest one in (17)) The improvement lies in our sharper upper bound on Xj EE, and detailed explanations are two-fold: (1) Previous work (17 Appendix B] directly used Weyl's inequality upper bound
A1 "1,,'',,,E.,,0"
S AE (AE
x² (Eo)-
(2) Instead of directly using Weyl's inequality, we first propose Lemma A.1 which uses positive semi-definite matrix diagonalization technique bound
+[([++AB + BA)) -1 - A1(A)
Xa(A)
Then we apply Lemma A.1 | to upper bound
( (1++ E. <((E)),
resulting in a smaller multiplicative factor than that in [17]
(2) Bounding Eiz1 Eves,
AT A0, Eo S.,,t Ast-- First recall that
je (25 My +
Σ
Batt Ge + G.,)) -1 BB,r) Eg (27g My +
Σ
(Co (o,
sc(m]
sc(m]
Σ-1 = + Σ Get Ga + G.,)) G = 21 + Σ (Eo + G
sE[m]
sEim
Therefore Eg < Egg Then applying Lemma A.1 and Weyl's inequality, we have
A Eg E
1- E Ast < B² X1 ($., EE EE.) < B² B2>1 1 E. S Do 11)
(Ex) < B² (EE)))((EE) B (E B2 (Eo) +02.
B [(1 EoE..) (1+ -
Aa(2o)
Aa(2io)
14

---

Meanwhile, we estimate the gap between matrix 2+1 and matrix Σ,1 as follow
D - --- = -Eo + (Gs,t + o A A ( - (5g + Gz)))
- (55
2, + AA, -111- (E0
1 E1 10 1
-Ipl - (5gt) + 0 3 AA, (,1) 11
Imy - [T (I 25 4, 4
-
U
1 1 (1 2 1
1
Σ 1,, s, -0 En
2² + A Σ 2 Agt
D 02 (Z,) + (E)((E)))(
(5)
where the second equality holds due to the Woodbury matrix identity, and the fifth equality holds due to the therman-Morrison formula. Then analogous to the proof for (1) Bounding Eiz Eves, ||r,, E..." recall C2 = 0²2 + (Eo) + B² (x,))(())) we have
ΣΣ 121 SES,
AT a 20 Ei E As,t
AT, Σ En Ee,Aoo
<20₂
log (1+
0² + B2 (Eo) + B (E))
(21 SES,
2 Σ A 1
-202
log det (1+
0² + B2 \1 (2)) + B x Eg )o
(21 SES,
ES A, A Eo
-20
log det (Er
+ +2 B2 (Eo) + B X X (En))x()))) - -log det (S:
221 sES
<20₂
Σ
[log det (Eiti) log det (Σ, ')]
121 SES,
<20g
log det
(Sm++1)
- log det [1]
22e log del (1+)
Σ
Dg (Eo + G Gz ) )
<E(m]
(T())= + Tr (E Em
Eg (Eo + G -157)
<2der log
d
<2dez log (1 m Tr (2 En)
2n))
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(27) in the above regret bound with
((n)1(Eg) at the cost of slightly larger regret upper bound, by bounding (Eo G,,nn+1) Gsmmn41 in the last but one step in the above (2), instead of bounding (Eo + G < 2
Specifically, we have the following estimation:
Tr(1 + Hr(IE Σ (Eo + G (o)lnntt) -1
log
Tr(I + Exeiml
E G Gs Ex))
< log
d
15

---

Eeemntz 1[s E T.
= loo
1 (1+
d
o mm (Eng)
S Slog
d
which is Olog (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-tass Gaussian linear bandit setting. We first give lemma as follow, which is useful to prove our multi-task Bayes regret bound in the sequential setting.
Lemma A.2 (Proposition 2 in (277) Let X1 and X2 be arbitrary iidd Rd valued random variables and SI f2 measurable maps such that J1, J2 I + Re with E (Xx))))) (2) oo,
then (X,)(X,)) (x(x))) S
(Xx)) f2(X2))
Theorem A.1 (Theorem 5.1 in the main text). Let |S = for all rounds 2 1. Then in the multi-task Gaussian linear bandit setting, the Bayes vegret upper bound of HierTS is as follow:
BR(m,n) S /mndy 2mder log (1 ")) 2dcz log (1 m. TT(2gg00
Proof. Recall that H, = (H, is the history up to round f, then
BR(m, n) =
E As,. - 0 A., H..]
t #ES
Σ
Σ
E T0_ As.- - Bl0,. 100..|HH, H.] TE[ H1. H.]
22 sES.
E
E (O.,, Pa.c) Ao,- Hell
12 sES.
$
dE ((O,,, Po,1)T (o,.)Ab..) Ao.t) H.]
SES,
dE (0,, (0.) (sse)) As. Hi)
SES,
dE [[], S Asii]
121 BES.
Vmnd
E
EΣX 121 121
|A
where both the second and the fifth equality hold due to the independence between A.,t and Os,- conditioned on Hy; the first inequality holds by applying Lemma A.2 with functions fi (1 3/2 = y1. fz(y1, 82) = y/2 for any 81, 4/2 Rdd and the random variable X2 (0,,- As,, ) HH, X2 (with the second element as A,,t) is the i.i.d. copy of X1; the second inequality holds due to Jensen's s
inequality. Plugging the upper bound over E EE>1 Eees, A| I in Proposition A.1 into the above result obtains the Bayes regret bound for HierTS.
B Proofs for Regret Bound of Hie in the Sequential Bandit Setting
Lemma B.1 Let 0 ~ N(u, En) and = (I,, Yo) be n observations generated as Y,
0,3, ~ N(x 0,"). Lei IP(μ H) = Ni n, E), and G -2 Dth utae. Then
B
H = (
B):
covl0 H = = + G) + (5) + G) -
- 12, GG
16

---

Proof. By definition, we have cov μ. H| = (= G E H| cov(0 μ, (_ p
B) where B Ei=1 Y. Hence cov ( p. H] does not depend on p.. Then have
E H = E HI H) cov(0 μr, H| ( 'B H + B) (-0
G) (E,
B).
On the other hand, because cov(@ μ. H| does not depend on μs, E/covie p, H
H cov 0
μ. H). In addition, since B is constant conditioned on H, then according to 17 Lemma 2], we have the following result:
cov E n. H] H] cov|cov[0 n. 1 = - -
Theorem B.1 (Theorem 5.2 in the main text). Suppose the action set A is finite with AA < co. Let
[S|| for all rounds t > I. Then in the multi-task Gaussian linear bandit setting, the Bayes regret
upper bound of Hierarchical BayesUCB is as follow:
BR(m, n) Smne + 4B / + + d+ / sd In g+ + 11 (:nj)mm()) Al8
8 log 8 (2mder log (1+ + ") 2de2 log (1 + Ir (I0 (2 E
Amin
In Theorem 5.2 in the main text, we replace V /d 1 Id & in the right hand side of the above
inequality with v d for ease of exposition.
Proof. Define De,t- 07,.Ass 0 A, Ag, the event E.,t {Va A (0,, (o,e) $
2 log &Ilalls,., J. and Cr,s,aa = / log } &llalls... Then we can rewrite the multi-task Bayes regret
[R(m, n) as the following equivalent form:
E FIΣEAAA A. - C.E[A,,.1
2 E..
B[A,, E 121sES.
< Es,tl
ΣΣ
[Bar]].
121sES.
121sES,
121eES.
Then will bound the three terms in the RHS of the above equality respectively.
(1) Bounding E(21 Exes, E[A,, 2 E,,,,]] Recall that U = a Csst
/ / log [|alls,,. then we have
ΣΣ B(A 2 c,
12 sES,
(0T
As,a Au,
OT Astt)
Σ 12 sES;
E
11A,, 2 c,, E.it
A.s
(OT An, Unadd + UtiiAAoe - 0,,, Aut))
Σ
E
1 2 c, Ex,, H.]]
Art.
121 sES.
(UL,,,A,, - As,t)
Σ sES.
E
11D,,t e, Bo,) H.]]
As,t
ICP. A.
121 seS.
min
(8l +) Al Sa.
A min
121 SES.
8 8log
1
n 2mdcs log (1 + ") 2doz log (1 1+
Tr (Io EEg)
<E
d
min
where the first inequality holds due to the fact that U U.S.Ar, 2 ULS,A, in the BayesUCB algorithm; the second inequality holds because when event Es, occurs, Ag Uta.d the third inequality
17

---

holds due to the definition of ui, and the last inequality due to the result in Proposition A.1
(2) Bounding Σiz1 E E ((Ast
<
e, E.,),
We
trivially
have
Σi>1 E.es. E| 1( e, Es, S mnc.
(3) Bounding Eiz1 Eoes, B {
First we give an upper bound of A. = f2 (Agit - As,t) Using Schwartz's inequality, we have
0,, 02 (A., Aaa)) 1|0 |5 || Aocllss.
<2B A1 (E.. 1)110 ||573 S 2B (1(().)) (100.. My Myl1s,,1 + -llullls:))
Besides, we also have 0s,+ - My = 0s.t ue + M. - u4 ~ No 20 + 2ny) = NNO E,,1), then
E [ll0,,,. Myl Mel|s - V E| و (8,,x My)11B Vd. According to B35 Exp 2.11], we have with probability C. 110,,- - Halls, $ v / t. Therefore, with probability Ç over the draw of {0s,.) )EE(m) have
Σ E 11,
f21 SES,
Σ Σ
E E A [E, H.]]
121 sES,
<BB V X1 A1
(/i++ /d ? + +Ilualls
ΣΣ E[1(Ea+H(
sEs
-2B v A1 (En + Edliii+ /ddn + ||
Σ Σ
P(E.. H.)
12
SAB A1 + E. V /
Ç )mm))))))
where the last inequality holds because TP( [F.. H,) S 26. Combining (1), (2) and (3), we achieve the final Bayes regret bound for any E (0, 1), > Ç e (0,
BR(m,n) n) S mic + 4B AB An An /
+ En)( pod++8di
//ddn 1 G
+ 11/a )s-=)mml|A1
log .in
{ 2mmde log (1 + 7) + 2dc2 log (1+ m Tr (E }
+ E
d
C Proofs for Regret Bounds of HierTS and HierBayesUCB in the Concurrent Bandit Setting
Let C, (s E S; >a(G.,,) 2 2/o0²) be the set of sufficiently-exploreed tasks round f. We first give the following proposition to bound the posterior variance E EΣ Eves. 1 C.HlA,,, S
in the concurrent setting, Analogous to the proof for Proposition A.I we choose to give the worst-case
upper bound on Σ1>1 E.Es. 1(s A. follow.
Proposition C.1 Let C1 = 0² + (Eo), c2 02 - B²A( + (EX)((E)((Eo) c3 = =1+ B 2 Pn(E)) (A (Eo) + 02 13.. then we have
ΣΣ 1(s C.HAAA,,,, 2mde log (1+ 7) 2do2c3 log (1 m Tr (5o [.g 22 SES.
d
18

---

Proof. Note that we have
Σ E 11s E C. - EE 1(s E C.AAf(Es + L "o Ee,e) Es,))A, As,e. f21 seS.
xE1
On event {s C,), the modified HierTS samples from the posterior and actually behaves the same as the original HierTS algorithm in Algorithm the above equality respectively.
[
Then we bound the two terms in the right hand side of
(1) Bounding E1z1 Eses, 1(s C
Similar to the proof for Theorem A.1 we have AT, S B²X1(Eo) + 0² and X,,, -
(Ep²) + (Po) Ees 1s E (. 2 Eg,. Then we can analogously obtain
Σ Σ 11s E C.AA
(21 SES.
1(s Es Ci (1 + AT, AT, 02 + B² (Ev)
52(0² + (Eo)
ΣΣ
2 #ES.
A
=2[0² + B2O1(E
Σ
Σ
1(s CG (Xxt + 02 + Ba Ba (Eo)
log det X
2 sES.
m
Aut alt
52(0" + (Eo]
Σ
ifs [log det det (X
log det X,,1]
02 + Ba (Eo)
m
A
52(0² + (2o)
Σ 1ss Si) det det (85,1 0² + B²d (En)
) log det X,,1|
121
=2(0² + B2or(Eo)]
Σ
[log det (X - llg X
<2d 0² (20) Σ log (1+ Σis1 1/8 S,
d(o2 + B²X1 (Eo))
<2mdl + B² [Eo)] log (1 + 7) = 2mdeer log (1 + m
7)
where the second inequality holds due to the fact that, if square matrix 2 B 2 O, then det (A) 2 det (B), and |S,| S m, the last inequality holds because the agent interact with each task at most times.
(2) Bounding Eiz1 Exes. 11s E C.
(E.1) ".
Analysis. The real difference of the proof for the concurrent regret from the sequential regret lies in bounding Σiz1 Eves, 1(s E A, E E "E Eg - ) As,t, because |S,| 2 and the result in Eq. 5 (which only holds for the case | = 1) does not hold. To tackle this difference, we reduce the
concurrent setting to the sequential setting. Let S, (4,)) |Sd] and define S {4g}}=1- Then at
round f, let s = In and define Σ A -و + >>>.,,... (Eo + - + (m (Eo +
G=!l) -1 we estimate the gap between Σ-1 and Σ- follow:
Σー - Σ = Σ
(Eo + ( -1 (Eo + Gz,l)
2ES
A,,
Σ #ESt.
(En + (Gza +
- -Eo + GZt)
G²
A, 2,
Σ 155
Dit 0² + AT As,
Thus we can bound A (5-] - 5 and tackle S instead of 5 to reduce the concurrent setting to the sequential setting. We first give useful lemma follow.
19

---

Lemma C.1 For any fixed t 2 1 and i E [L] suppose Aa(G,,1) 2 3/0²
and let s = It Then
B2A1 (>1(En) + 0²
( 1 σ² )²>a(Io)
3 8).
Proof. Applying Weyl's inequality, have
A1 ( 1 + 1) = \1 (E7 ( En E
+ I)
A X1 0. Et
$1 + ( = 1 +
Xa(E;²)
We first lower bound >a(E, ). According to Weyl's inequality, we have
)a(ET)) 2 \a( + Σ
Aa((S0 + GZ))"1) 2 Ad(2) + Σ
A1 + X1 (G
=E[m]
=e(m
i-1
=\d(E;1)+ + Σ
1 (Eo) + 03
A1(Eo) + G..)..)
ZE m
where the last inequality holds because the tasks Sr, -1111 have been sufficiently explored. On the other hand, using our Lemma A.1 we can bound a1 A1( 5.t E as follow
A,
B² X1 (Eo) 0² Xa(Coo)
( - -E Σ A1 o² A S. Aes
111 Ee, s
=ESt,a8-1
Combining the above results, we have
(i- (i- 1) B Xr (En)
B² (E.o)
o² D (20)) 1g1.
X (2 S1+
Ad(
S 11
>a(E.T) + i-1
o² >a()
Then, recall C3 = + 2x (Eo) + 0²/3]. we can bound E1z1 Exes, 1(s E C.) C 3/ Et, Zy 'E
I-1,,
Ax,t as follows:
Σ Σ
1/s C.) (2, E220 -. A.,
12 sES,
-
1/s C.) A S
Sq 8,8 Sp S S Ass
(21 SES,
1/s ECJA
(1 E A
15 5
E
&E
B2 A (En)
(21) + } Σ Σ
E
1(s E C,4,,,
11 Eg 11 Ass
o²
121sEs, sES,
<20302 log det (2mm+1) - log det (2i
<2dege2 log + m Tr (2
d
where the second inequality holds due Lemma C.I the third and the fourth inequality hold in the same way as that in the proof of Bounding (2) in Proposition A.I 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
B² An (E)) (i-1)
1)
B² dr (Ea) (1-
\EE 11+ Ae 71
0Z (
S
11
oF Ae(Eo)
1-1
Thus our upper bound is independent of the number L of the concurrent lasks. Actually, Vi E [L]:
(Eo)
B² (En)
>1 (1
S1+
51+
oF X2
Xa )
(1500-007
L
X1(2))+0773
20

---

is L-dependent. If AalE7')
the sharper bound +
(1 the
dy (2a))=2118
influence of I. to the regret may 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 [St] S L S. m. for all rounds 2 1. Then in the multi-lask Gaussian linear bandit setting, the Bayes regret bound of HierTS is as follow:
BR(m,n) 528md AE + Ex)(vV [| + +mdd 2ner log (1 + n2 d)
+ Vmndd 2dc203 log m Tr (Fo Fng) (Z01)
Proof. Recall that C. = {s E Aa(G.,.) 8/0²} } is the of sufficientl-eeploreed 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:
(R(m,)) n) = E ΣV
Σ
1s & C.)0
As,)) + ΣE 1ss EC.OO,, Ast)
+.EE
121 sES,
121
(1) Bounding E E111 Eses, 1/ & C.)O (An, Aat). Similar to the proof for Theorem B.
(3), we have
T,, (A., Aut) S |10,, ::-1 ||,,, Auclls,, I 20V A (E. -1100,.--,lll;;- Molls, l|nalss!:)
and E [110,r- - Halls ! Sv E S (0a.- = Vd. Recalling the independence between 0,,- and actions As, yields
E Σ Σ
1 & C,, A..1)
121 sES,
< 2B
Ai + E Σ Σ 1f & C.) Malls + I1 ||malll:3)
C2l sES
< <BB Ai + (vd (lualss.))md
The last inequality holds because in the modified HierTS, event {s & C.} occurs at most d times for any task
[m]]
(2) Bounding EΣn E.es, 11s E & It suffices to apply the upper bound in Proposi-
tion
Combining the upper bounds in steps (1) and (2) obtains the final Bayes regret bound for HierTS in the concurrent setting.
Theorem C.2 (Logarithmic Regret Bound for HierBayesUCB in the Concurrent Bandit Setting). Suppose the action set A is finite with [A] < cc. Let [Sy & LL for all rounds t 2 1. Then the multi-task Gaussian linear bandit setling, the Bayes regret bound HierTS is as follow:
BR(m, n) S mne + 4B /ii(Eo + E,0( [d
d+
8d 5
+ ||lallss,
( Am]
+ 2B / Ai + Ex) (vd+ |1 1 E
8 log
22mde log (1 + ") + 2d0302 log (1 Tr (2i Enn)
}}
A min
d
Proof. Similar to the proof of Theorem
C.I +
decompose the Bayes regret as BR(m, n)
E EE21 Eees, 1(s & (.0,,,AA... Ard))
E E121 E.es, 1(s e C.JOT,, Aet). Then
21

---

Table 3: Different Bayes regret bounds for multi-task d-dimensional linear bandit problem in the concurrent setting. m is the number of tasks, n is the number of iterations per task, A is the action set. Bayes Regret Bound =Bound Bound II Negligible Terms, where Bound I is the regret bound for solving m tasks, Bound II the regret bound for learning hyper-parameter μ4..
Bayes Regret Bound
[A]
Bound I
Bound II
Theorem 4]
Infinite
(mdd log (3) log (mn)
(d mn log (m) log (ma)
Our Theorem 5.3
Infinite
(md n log (5)
Oldymn log (²)
Our Theorem C.2
Finite
O Omd log (3) log (mn)
Od (7) log (mn)
we bound the first term with the proof for Theorem C. (1), bound the second term with the proof for
Theorem B.1
Then with probability 1 over the draw of {0s.)>x[(m)
Blog&
BR(m, n) S 2B A1 + (v + ll )md + E
ΣΣΣ
B[1fs Eall,, 3...
A min
+ min + / >1 - =Za ( d+ v /d ? /1moll m A|8.
Plugging the upper bound on Σ1z1 E.es, E[ E C.3ll E in Proposition C.1 into the right hand side of the above inequality finishes the whole proof.
D Proofs for Regret Bounds of HierTS and HierBayesUCB in the Semi-Bandit Setting
We also choose to give the worst-case upper bound on Eiz1 Eees, EoEa,, E, Pa as follow.
Proposition D.I Let o² + B2)1(Eo), as o² L Ba (E,,)s (E())) then
Φ T D Da S 2e (1 + nL n 2ea Lo + m Tr(E Egg EE Σ (21 121 aEA.,t
d
Proof. Recall that G.tt = 0 lfs E SE DaD Ba,t 0022 1fs e EiEEE, (a)), E.11 = Do E Eg E (Co (Eo+ Then, analogous 1--=0ap0
to the proof for Proposition A.1 we introduce the matrix X.,1 (Eo + B2x1(Eo)to2 Eecr 1fs E
( ta
We next bound Σςz1 Eses, Exed,, TI. and E 'E,
E1Z1 ExEs, EoEd.. TI E.
(1) Bounding Eis1 Eoss, EoEA,, TTS. S..
Σ SES aEA,,1
T T Db
=10² + (Eo)
11S 5 Σ
0² B²d1 (2o)
22 s=1
a
m
4J_ STS $ g² + B2 (En)
2210² + (EA) Σ Σ
I(S: = $) Σ
log
121
AEA..
Σ DT
5210² + BAA(
Σ
1(S; = =} Σ
log det([ + 02 + B² (20)
=1
A,A,,
22

---

4.00 a
-2 + B2A1 (Zo)
Σ 1(S: 8} (xx1 +
log det (et((x
0² + Ba (Eo)
s=1 121 aEA.,
m
-2 + B"A1(Eo)]
log det (et(XX,,ii) xm log det( det((x
=2|0² + (2oo)
Σ
log det (1 + 3²+1BAN(Eo)
Σ
1[S,=s} = Σ
ksm
aEA,,
Tr (T+ oz+B'A1(Zo) Eigma 1 = 8) EnE
-2|0² + B2A1(Eo))
log
d
Σ log (1 + Eismn 1(8, s} s EaEA.. d(o2 + B² (Eo))
D D0
-2(0² + B²\1 (Eo)
52/0² + B² (oo) (1+ n/,
d 20m log (1+ nT. d'
(2) Bounding Ei21 ExEo, EoEA,, E. E. -2, Vt 2 L,s E S₁, Va E Au,, we have 1 2e 20
20
<
+ LB (2i)+ -
a.. Meanwhile, define the matrix M A E
Pay
Σ3 T
a, ag.
s, s Ba
RRdx|An,1, we have
EOEA,, 1. MM Using the Wely's inequality, we further have
A 2 M) S (1) (o 51+0-2 Σ
Σ
aEA.
aEA.,1
Then we can estimate the gap between matrix 1n1 and E as follow:
1 - -T-
=(Eo + (G.,t + -2 Σ L
-
--1))-1))---
-Eo + G
aEA,
=Ep - - (E0 G. 0-2
Σ
$ ) -'=0'
E I G.,))-Eaa'
AEA,,
-Sr - (ijz) + -2
$
T)
T
aEA,
-x [ (T+ Σ
-
5-1
aEA,,
=x - 3
- ' + M M) M -
2 - 10 MAa (I 10 2M M)
-I jo
MM
X1 o 2M M)
>
1
MM
1+o EaEd,
E EoEA, Do 1.
r² + EaEA,. BTS. Da
Σ 1 EoEA,, D Li 2ny
0² B (Ea) + Bº EEg (i En)
23

---

where the second and the sixth equality hold due to the Woodbury matrix identity. The proof for Eq. (6)
similar to the proof for Eq. (5). but requires more refined analysis (i.e. the first inequality in Eq. (6)
estimate the lower bound of 2 " Then recall C₁ o² LA1 + 1 (2i))((2))
for brevity, we can bound Σ121 Eses, EoEr,,.
D -. E200 E La EEEEE
as follow:
ΣE Σ 121 SES, aEA,,t
D Da. 20 E DS.0
0 L, 10 E D
2n4
log (1 + 0² - L2 (En) B - )ks
121 SESt aE
Σ 2 2b T
-244
Σ
log det + 02 + B² En) + B2 X1 En )m(oo)
8,
121 BESS a
Eg E 4 2 E0
=2c1 E Σ
[logdet(22 det
log (2i,
02 02 B² (20) B (Z))
121 NES, aEA.,
L/ L Σ
[log deu (E(+)) - log det (2,
121
-2c4 T. [ieaT[log det (mm++
log (eg
=2n [log de +
Σ
Egg (Eo Gzmm++) -
xE(m)
Tr(I + E.Elm]
Eg (Eu + G (1)m -1
<2c log
d
22cgLdlog(1 + m Tr( d
where the second inequality holds due to Eq. (6).
Lemma D.1 If a Gaussian random variable X (N, 0²), then E[X1 2 0} = M[1
(-(--)) a exp( 2², / further p S 0, then E[X1(X 2 0J| ン2n expl زي
V2n
Theorem D.1 (Theorem 5.4 in the main text, Regret Bound of HierTS in the
Setting).
Let |8t] 1 for any? 2 1. Let c
2
(2KBB)(Eo) C1 o² + (2o), C4 o²
v2x
+32 (x))))()))))) then in the multi-task Gaussian semi-bandit setting, the Bayes regret bound of combinatorial HierTS is:
B (Eo) B2
BR(m,n) n) S m ev m/ 20 mo (1 2 + 2c, Ld + m TT(2 Enn
nL
d
Proof. Note that w. Db.... then define ((A,0) EaEa (oa, 0) for brevity, have the following result:
BR(m,n)
=E =E> Σ Σ wa(a)= [w((
12 sES;
aEA,,.
aEAst
=R
a, Oun) Σ Os,))
t>1 #ES.
deA...
BEAr
=E
Σ
[9(A 0z,e) - ((As,e:(a.n))
12
SES;
Define upper confidence bound (A) EnEs ( (Par (o.e) + toy 4J E Pa), where ei constant
to be specified. Notice that A.. He iid Ass H, and (-) is deterministic function, thus
24

---

(l,,, |H =
Then we can decompose Bayes regret BR(m, n) as follows
3R(m.n)=33 =E Σ
(A,,)) - [a(A ((,,),,0,..) -Ur,)))) + EE
0o,,) -.t) Ut,,(
121 sES;
=F EBΣ
Σ
(Una(An)) (s.s)
1E1
(1) Bounding 1E Exes, [s(A,..: 0z,,) - U,,s(
For any 1 2 1,8 E St, a E A, define random variable Xt,5,a = (D Os. - (s,,)) CV $ S.,,, Ba.
then we have Xt,s,al Hr ~ (N-ov Do D.n D3 D. since El0..- Na,1 Ht] = 0. Then
E
0o,e) (n,(A
121 SES.
E
Σ
Σ X1,90
121 sES, aEA,,,
Σ
Σ
X1, Ris,a(XXrrl 1(tts, 2 0}
eES, aeA,,.
<B
Σ
Σ
Xe. (Xi,s 2 0}
121 SES K]
E Σ
Σ
E
[[X 1(X 2 0}]
SE RE(K]
T D
62
expt
2
12 SE KE(K]
BA1 (See)
2
E
exp(
22TT
2
21 sES aE(K]
Snik (20
expl-
2tT
If let nmk (Eo) 22n
expl --1 2
S m, then /2
nk BA:
/2*
(2) Bounding E E1>1 Exes, (Uee(Ast) (AA,):0s))))
Σ
(Lne(Am))) - 9(As,1,0,,.)
121 SES.
a Po.t - O2,m) + ev TT D
121 SES, eEA.,
EE> Σ
E LLEA. H. B ( Ao,t H, + cE
ΣΣ Σ 12 I #ES, A
V
SES, [[|K]
F ΣΣ Σ
121 SE A
SovmaL
E
ΣΣ
Σ
SES aEA.,
where the second equality holds because of the mutual independence between As, H, and 0s.- Hr, and Bl 0. H,]]
O; the last incquality holds due to the Jensen inequality. Then applying
25

---

Proposition
D.1 to bound E E121 EsEs, Edeldned D. we can obtain
E (A,,(A,,)) - 9(A,,,, I evmmly 20rmlog (1 nI, 121 SES
m Tr(Eo
E
2ca Ldlog(1
d
Combining the above results finishes the whole proof.
Theorem D.2 (Theorem) 5.5 the main text, Regret Bound of HierBayesUCB in the Semi-Bandir
Setting). Let |St] = for all rounds t > 1. Let o² + X1 (Eo), C4 o² + L
(2,)n(o)) Then for any e 0, (0, E 1), the multi-task Gaussian semi-bandit setting, the Bayes regret upper bound of combinatorial IiirrBayeSUCB is as follow:
8T log
220m log (1 + nL
+ Ld Log(11 Tr(En 'E1)
BR(m,, n)) SIE
d
)]
mnn
Ac min
d
ALB X1 + (pp /dd I
g+ + I| )
Theorem 5.5 in the main text, we replace y /Bd in the right hand side of the above
inequality with v d for ease of exposition.
Proof. Define the event E,,t P4a A: (0., (a.eil $ v 2 log @1 lls. and the upper confidence bound (A) = EeEa Pa: (a,)) + / /2 log $1 Illl,,.. Let A,,t = A(A,, 0s,n)
g(A,,r, 0,,-), then decompose the Bayes regret into three parts follow:
A., E
Σ
sES,
Σ
Σ
E 1(A,, Es,)
ΣΣ
E[A,, E, + Σ 1[A,,,((,,.]]]
121 sES,
121 sES.
121 sES,
(1) Bounding Σis1 Exes, B[A 2 Extt]
ΣΣ E E[A., 2 EasH
121 sES.
(9(A,,v 0z,r) g(A (x,))) 11D,, 2c,,
Σ Σ
D.L
12 HES,
(9(Ma.n) - (As,)) -te ((aaa, 1sDes e, Eaa)
Σ
Σ
E
Ds,t
121 S,S,
(A,,) - -(Ao,,, 11 2 c, Es.tl
Σ
E
Do.
21 =ES,
(Ba EmEA,,
02,e) + v 2 log (1 )²
E
11Aa. 2 e, Eacl]
A
121 sES.
EaEA,, 2/210g 2all (e..).)
E
1fAet Eechl
A
121 sES;
EaEA,, 8 8og (EEEA, ( 11
Σ
E
11D,,t Esccl
121 sES.
26

---

8L log
SEl
ΣE Σ |
min
EEI oEA.,t
where the first and the second inequality hold due to the definition of the upper confidence bound (A,a(As)) the fourth inequality holds due to the Cauchy-Schwartz Schwartz inequality. Utilizing the upper in Proposition D.1 completes the proof for the first part.
bound on Σ1>1 EeEs, ExEA,.!
(2) Bounding E121 Exes. B[A e 1 <,, Eec)). We trivially have E121 Eees,
EE A 1( < Eash & mne.
(3) Bounding E121 E E s,t F.,
Note that 0, - 44 ~ ~N(0, 1. and E 110 Me Molls,; $ VEEE (0e,. - 14)1BB = Vd. Then
according to 35 Exp 2.11]. we have with probability S. 110,,- Malls, S Vd+ / {
Therefore, with probability - over draw of [oo.))e[[]] we have
D =g(Ae. 02.0) g(A,,,, 0,.-)
Σ
Paa S,1,) )
Σ (a. 02,m)
aEA.,,
oEAr,
Σ
||all |10,
Σ
| 110
ae
a.
1 S - 2LBB A1 + 2g) ( v Id ? + I!lalls
I
where the first inequality holds due the Schwartz inequality. Then we have with probability
ΣΣ E[A., ((E,,))
sE.
Σ Σ (21 SES,
E(E
s 2LBB
A1
1
/dd1 + ||
ΣΣ 121
E E[1(E..](ui]
2LB \1 + Ed) /Bdl1 1 + ||
P H.)
121 SES.
< < A1 / (1)
d+ /8d1n Ç [1laalls, )
Combining the results in (1) (2) and (3) finishes the whole proof.
E Technical Overview and Limitations of this Work
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
be found in Table 4):
(1) The Technical Overview for Deriving Near-Optimal Regret Bound in Theorem 5.1 The biggest novelty lies in bounding each term E [(.,.. (a..) A,, H.] in Bayes regret BR n). inequality to directly bound (0.,- - (o.c) A < ||0,,. Aa. !ls A.. Ils..' used UCB technique to bound 1|0., M (which caused an
Existing work [17 chose
additional multiplicative factor log 4), leveraged the fact that A H, iid. A.d He to transform
27

---

Ex.ell4s, lls.. into Vm.n. and obtained an intermediate regret upper bound v /nnm... m.n log (1/6). Instead of using UCB technique, Theorem 5. applies novel
type incquality (i.e. Lemma A.2 to bound E(O... - Ps.t)) A.,. S V dE(((,,. - AA,,) VallAa,
and finally achieves the regret bound / m/nnmm.. removing the /log (1/5) factor. Besides, when bounding the posterior variance Vm.n, we use different matrix analysis to prevent variance terms (e.g. >² (En)) solely appearing in the denominator of regret bound. Moreover, we employ a matrix decomposition technique (in our Lemma A.1 l to reduce the multiplicative factor x² (Ee) in
[17 Theorems 3-4] to <(Zo)) in our bounds (see more details in Table 4h.
(2) The Technical Overview for Deriving Logarithmic Regret Bound in Theorem 5.2 To obtain
sharper sequential regret bound than the near-optimal regret bound in Theorem 5.1 our Theorem 5.2
chooses the Bayes regret decomposition strategy shown above Theorem 5.2 uses UCB technique
to bound the first term in the regret decomposition as Σr. EA,,;1fA,, s,t 2 E I Vm,n log 1
and finally combines the upper bound on posterior variance Vn., in Eq. (4) to achieve a logarithmic Bayes regret upper bound of (log 1 md log 7.
Nevertheless, we also need to point out the limitations of our Bayes regret bounds:
The Limitations of the Multi-Tass 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. Omm 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] 17)). (ii) Unable to shed more light on the advantages of multi-task bandit optimization. The existing regret bound ((mVnk) for multi-task representation which demonstrated that multi-task regret bound can be smaller for learning a low-dimensional representation (i.e. k << d) than the regret bound of O(mv nd) for learning each task independently, and the existing regret bound O(myn /n log (1 + nV)) for multi-task adversarial linear bandit which proved that the regret bound decreases with more similarity (i.e. smaller V/ among bandit tasks. Our hierarchical Bayesian bandit model has assumed that different bandit instances are sampled the same meta- distribution, and hence fails to reveal the influence of task similarity to the multi-task Bayes regret.
Remark E.1 (The Underlying Causes for the Limitation of Multi- Bayes Regret Bound.) The underlying causes the shortcoming the the multi-task Bayes regret bound is that the upper bound on the posterior variance Vm, = E Eiz1 Aless,1As,:11
may be not tight enough. Detailed
explanations lie in the following three aspects:
(I) Recall that in the proof for our Theorem 5.1 we can upper bound the multi-task Bayes regret as (R(m,, n) S. wnddd /Vm,.. Then in Proposition A. I we use a purely algebraic technique to bound the posterior-variance Vn.. S (m logn), resulting in the final Bayes regret bound of
Vmndd / O(Vmmd m logn) O n logn),
which is almost the same the summation of the regret bounds for learning bandit tasks indepen- denuly. Therefore, if we can upper bound the posterior-variance Vm.a with a bound that is sublinear with respect to m and logarithmic w.r.t. n (e.g. bound of (mm log,)), then the final Bayes regret bound will be much sharper. The upper bounds on the posterior-variance Vmn. in existing works (e.g. see [25 7 17] in our Table 7 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 via purely algebraic technique (thus leading to a worst-case upper bound on the posterior variance E Ei21
A.
only give the worst-case upper bound
E,E,,
Such worst-case upper bound is obtained via purely algebraic techniques, ignoring the expectation over the randomness of Aut and E.,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-variance Vm. E Eiz1 Eoes, A Ill we need to consider other bounding technique like concentration in- equality, or more technical matrix analysis, to achieve upper bound that is sublinear w.r.t. the
28

---

mumber m of tasks and sublinear W.T.t the number of iterations per task. Only in this way can we obtain a multi-tar task regret bound mmn) that is sublinear w.r.s m and sublinear w.E. n.
(4) On the other hand, we also consider finding the lower bound of cesterior-varinne Vm. to show that our upper bound V. is tight, 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.
F Additional Experiments and Computer Resources
Linear Bancit
1-1)
Linear Bardit (m e,
Linear Bandk
10, 5-
150
150
x-130
Hagnos
Regret
Ragnt
100
30
50
Number Concanmnt
(a) Regrets w.r.t. different m
(b) Regrets w.r.t. different L
(c) Regrets w.r.t different dg
Linerr Bandit (d 4, ie 10. (a
Lineor Bandit (d 10, X=s)
Linear Bandit (ff c, = 0.5
300
mmm05
1000
10
OruckTS
TS
Regret
300
750
HarBegalcC
HiNTs
500
200
100
.00
Round
Round
Round
(d) Regrets w.r.t. different (e) Regrets w.r.t. different
(f) Regrets of different algorithms
Figure 2: Regrets of HierBayesUCB algorithm with respect to (w.r.t)) different apperrparameter....
Experimental Results. From Figure 2 we have the similar observations as that in Figure | (1) In plot (a), the multi-task regret of Hic becomes larger with the increase of and which consistent with our regret upper bound in Theorems 5.2 (2) In plot (b), the regret increases with higher dimension d, and increases with larger number L of the concurrent tasks. (3) In plots (c)-(e), the regret decreases with a smaller variance (e.g. ag. Op and σ) in hierarchical Bayesian model, validating the provable benefits of variance-reducciion 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 o, (when compared with og 1.0 in Figure (f)).
Computer Resources. Our implementations are based on Python. We run all bandit algorithms on platform with 8 NVIDIA RTX 6000 GPUs and 2 AMD EPYC 7543 Processors. Each GPU has 48G memory, and each CPU has 64 cores. The CUDA version is 12.1, the Python version 3.7.16, the matplotlib version 3.5.3, and the tensorflow version 1.15. The source code for reproducing all experimental results of HierTS and Hie provided in the supplementary material.
29

---

Table 4: The technical novelties for deriving our improved sequential regret bound when compared with the latest regret bound in [17] Thm 3]. m is the number of bandit tasks, n the number of iterations per task. and d the dimension of action .4.
(1) Our regret bounds the /log (mm)) factor.
(2) To minimize our bound, it suffices to decrease the variances of A (Ea), A (2
(3) Our regret bounds also show that
we should decrease the condition number Au (. Ka
Our Improvements
the variance matrix Ee minimize the Bayes regret.
Be AaAiA (32,))
x + BPA (Ma))
d m/mmmlog (1 + on Thi Sy.
Our Theorem 5.1
dm dmyalog n (1+ 5)
(Eo) (PA)E
X0 BPM
Improvement Motivations
(1) Use a Shwartz-ly piz-ype inequality in Lemmal A.2 instead of UCB strategy, to bound per-task regret to avoid udditional term log (where 8 = mm))
(2) Define new matrix Xat s.t. the denominaton in the regret is
B² (Eo). not only a2. Avoid the case that the variance serves alone as the denominator.
(3) Give more technical ana in Lemma A.1 to improve AfpX..
to
3855g
ArtSo
Act
(1) There exists an additional factor /log (mn).
There also exists an additional factor llg (mmn).
(2) There exists a paradox this bound, i.c. variance exists in both the denoninator and numerator Then whether we should increase decrease 2 to minimize the regret bound?
Existing Problems
dmn / log (1m)) log (1 + ndg (ay (Zn) do
mid mAA Cla) An(3))
A3 (X,, (1+ M1
22 Doo [1+ X Ra0ie
V Ing 04 24030
dv man log (men) log (1+
(1
17 Thmn
X
Regret Bound
Bound III
Bound
30

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: see Section 5
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: see Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
31

---

Justification:
see assumptions in Section and see proof sketch in Section
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: Yes]
Justification: see implementation details in Section and Section F and see the source code in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
32

---

Answer: [Yes]
Justification:
see the source code our supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/
httppp//iiiicuiiceoo/ooeeeaaaaia CoodeSubeeiieeeeeeeeee ssi asionnolle onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Ye]]
Justification: see the implementation details in Section G
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: see our Figures 12
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
33

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: see details in Section H
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httppsss//ourrppp.cc////ll//////
Answer: [Yes]
Justification: this paper is purely theoretical paper and has no negative social impact. Be- sides, we release the source code to implement our proposed algorithms in the supplementary material.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: there is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
34

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: the paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses for existing assets
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?
Question:
Answer: [NA]
Justification: the paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not 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 URL.
The name the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
35

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
36


Reviews:
[{"review_id": "YrVZWH8IMe", "reviewer": "Reviewer_wPds", "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.\n\nIn the introduction section, the description\n “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. \n\nQuestions:\n\nI 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?\n\n\n\nIn Line 53, there is a typo. I guess it should be “latest” instead of “latext”.\n\nCan you rotate Table 4? It is hard for readers who use a desktop.", "questions": "see the first box", "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.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "see the first box", "weaknesses": "see the first box", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1. 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. Instead, we care about the action with the highest mean given a problem instance.**\\\nA1: Thanks for pointing this out. It is true that in Problem Setting we care about the action with the highest mean reward (not the highest reward and hence seems not aligned with the pseudo regret definition in Introduction), and we define the action with the highest mean reward as the optimal action. We will make a more rigorous statement of our introduction in the revised version.\n\n**Q2. When using the notion of Bayesian regret, why is there an instance-dependent gap?**\\\nA2: Thanks. There are two reasons for the existence of instance-dependent gap:\\\n$\\mathbf{(1)}$ The first reason is that we use a new bounding technique to upper bound $\\mathbb{E}\\Delta _{s,t}$ (e.g. see Lines 549-550) as follows (informal form): $$ \\mathbb{E}\\Delta _{s,t} \\mathbf{1}\\lbrace\\Delta _{s,t} \\geq \\epsilon\\rbrace=\\mathbb{E}\\frac{\\Delta _{s,t}^{2}}{\\Delta _{s,t}} \\mathbf{1}\\lbrace\\Delta _{s,t} \\geq \\epsilon\\rbrace \\leq \\mathbb{E}\\frac{C _{t,s, A _{s,t}}^{2}}{\\Delta _{\\min}^{\\epsilon}}.$$ Therefore, there exists $\\Delta _{\\min}^{\\epsilon}$ in the denominator in our bound.\\\n$\\mathbf{(2)}$ The second reason is that the instance-dependent gap is actually a random variable, and our bound needs to take the expectation of this random variable. Note that the instance $\\theta _{s, \\star}$ is random, and the gap $\\Delta _{s,t} = \\theta _{s,\\star}^{\\top}A _{s, \\star}-  \\theta _{s,\\star}^{\\top}A _{s, t}$ is a random variable. Finally, the term $\\mathbb{E}{\\frac{1}{\\Delta _{\\min}^{\\epsilon}}}$ in our regret bound (e.g. see Lines 549-550) takes the expectation over the randomness of $\\Delta _{s,t}$. Similar instance-dependent gap based regret bound can also be found in the latest work [3, Thm5].\n\n**Q3. 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?**\\\nA3: Thanks for your suggestions, our explanations are two-fold:\\\n$\\mathbf{(1)}$ Using frequentist regret bound to derive Bayes regret bound (either instance-dependent or instance-independent) is also one of our future research directions, because the techniques for deriving frequentist regret bounds are more fruitful and more general. But in the current work, we focus on applying improved Bayes regret analysis (like improved matrix analysis in Lemma B.1 and novel regret decomposition strategy in Theorem C.1) to derive sharper Bayes regret bounds.\\\n$\\mathbf{(2)}$ It seems difficult to apply existing gap-dependent frequentist regret bound for UCB-type algorithm to derive instance-gap-dependent Bayes regret bound for multi-task hierarchical Bayesian bandit problems. To the best of our knowledge, the existing instance-dependent frequentist regret bound for UCB-type algorithm is in [1, Theorem 5], and is not suitable to be applied in our setting due to the following two reasons: $\\mathbf{(i)}$ [1, Theorem 5] assumes the boundedness of the instance parameter $\\theta _{s,\\star}$, which hence could not be applied to analyze Gaussian bandit instance where the instance parameter $\\theta _{s,\\star}$ is not uniformly bounded. $\\mathbf{(ii)}$ The frequentist regret bound in [1, Theorem 5] is more lengthy than the single-task Bayes regret bound for UCB in [3, Theorem 5], and hence could not lead to a concise multi-task Bayed bound as in our Theorem 5.2.\n\n**Q4. In Line 53, there is a typo. I guess it should be “latest” instead of “latext”.**\\\nA4: Thanks for pointing this out. We will correct it in the final version.\n\n**Q5. Can you rotate Table 4? It is hard for readers who use a desktop.**\\\nA5: Sorry for the inconvenience. Because Table 4 is much wider than it is tall, we choose Table 4 with horizontal layout.\n\n**References**\\\n[1] Improved Algorithms for Linear Stochastic Bandits. NeurIPS 2011.\\\n[3] Finite-Time Logarithmic Bayes Regret Upper Bounds. NeurIPS 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QwSEjKENRd", "reviewer": "Reviewer_yLZF", "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.", "questions": "No questions.", "limitations": "Yes.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Contribution: The paper improves upon prior works in several directions; it proposes tighter regret bounds for HierTS, extends multi-task bandit algorithms to combinatorial semi-bandit setting. \n\nPresentation: the paper is very well-organized, it clearly defines the problem, pseudo-code of the algorithms are clearly presented, and the experimental results are extensive.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1. The paper improves upon prior works in several directions; it proposes tighter regret bounds for HierTS, extends multi-task bandit algorithms to combinatorial semi-bandit setting.**\\\nA1: Thanks for your positive comments. we will continue to improve the quality of this paper.\n\n**Q2. 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.**\\\nA2: Thanks for your comments. It is true that in the current work we only conduct synthetic experiments to validate the effectiveness of our theoretical results and our proposed algorithms. Conducting real-world dataset experiments is also one of our future directions and we will try to add it in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pTKX6d836Y", "reviewer": "Reviewer_diEN", "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.", "questions": "Here are a few questions regarding the paper:\n1. 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. \n2. 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)\n3. 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. \n4. The term $\\mathcal{V}_{m,n}$ is the posterior variance of which distribution?\n5. 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).\n6. 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?\n7. 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?\n8. 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. \n9. 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.\n10. 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.\n\nOther 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": "See the questions.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper deals with an interesting hierarchical bandit/semi-bandit setting, where the agent needs to optimize its policy for several tasks simultaneously based on semi-bandit feedback. For the Gaussian setting, the paper provides Bayesian regret bounds that either improve upon previous results, or provide new results (e.g., HierBayesUCB in the combinatorial setting).", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to the Review by Reviewer diEN (Part 1/4)\n\n**Q1. The Gaussian distribution assumption for each layer of the hierarchy is highly restrictive since in many cases, the noise is not Gaussian (assuming sub-Gaussian would be better). 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.**\\\nA1: Thank you for the suggestion, we will mention the Gaussian linear bandit setting in the abstract and introduction in the revised version to make the statement more rigorous. For the Gaussian assumption, our explanations are two-fold:\\\n$\\mathbf{(1)}$ It is true that the Gaussian distribution assumption for each layer of the hierarchy (especially the Gaussian noise) is restrictive. On the other hand, we also need to point out that the existing Bayes regret bounds [7,17,25] for hierarchical Bayesian bandit algorithms all adopt the Gaussian distribution for each layer of the hierarchy.\\\n$\\mathbf{(2)}$ Extending our results to the more general settings (e.g. sub-Gaussian noise) is also one of our future directions. However, the generalization is not easy, mainly because the non-Gaussian assumption could not lead to the closed-form posteriors and hence could not apply our proposed algebraic analysis (e.g. Lemma B.1, Propositions B.1, D.1 and E.1). Instead, we may need to choose other tools like information-theoretic analysis in [32] to derive Bayes regret bounds for hierarchical Bayesian bandit algorithms.\n\n**Q2. What is the benefit of assuming a hierarchical structure rather than dealing with each task independently? The overall regret is linear in $m$, which seems to be similar to that of dealing with the tasks independently.**\\\nA2: Thanks. Our explanations are two-fold:\\\n$\\mathbf{(1)}$ It is true that, from the theoretical perspective, the current Bayes regret bound for multi-task hierarchical Bayesian bandit is similar to that of dealing with the tasks independently. This is not very surprising because the regret bound $O(\\sqrt{n\\log{n}})$ in [21] for single-task Bayesian bandit is also near-optimal. Besides, deriving more insightful regret bounds (e.g. the bound revealing the impact of task-similarity to the generalization) to illustrate the benefits of multi-task Bayes regret bound over the single-task regret bound for hierarchical Bayesian bandit is also one of our ongoing research directions.\\\n$\\mathbf{(2 )}$ From the algorithm perspective, in the hierarchical Bayesian bandit problem, using specifically-designed hierarchical Bayesian bandit algorithms can access more information of $\\mu _{\\star}$ via interacting with different tasks, than using traditional single-task Bayesian bandit algorithms. Such benefit can also be found in the lower regrets of HierTS/HierBayesUCB than that of vanilla TS in our Figures 1(f) and 2(f).\n\n**Q3. Is it possible to use this result to derive frequentist regret bounds (either high probability bounds or in expectation?**\\\nA3: Probably not. Detailed explanations are two-fold:\\\n$\\mathbf{(1)}$ Notice that frequentist regret bound (for any fixed task instance) is the upper bound on the Bayesian regret. Besides, as shown in [31, Sect 3.1], only in some cases can Bayes regret bound be converted to frequentist regret bounds. Therefore it is not easy to use our Bayes regret bound to derive frequentist regret bounds. \\\n$\\mathbf{(2)}$ Obtaining frequentist regret bound may require more advanced techniques. To the best of our knowledge, deriving frequentist regret bounds always need to use advanced analysis tools such as anti-concentration inequality or martingale method (see [1,15]), while deriving Bayes regret bounds in our work just uses less technical algebraic bounding analysis.\n\n**Q4. In the Gaussian case, is the lower bound $\\Omega(d\\sqrt{n})$ tight in this hierarchical setting (note that this lower bound is for a linear bandit learning a single task, but it is not immediately obvious whether or not the shared structure across the tasks could help in the regret bound).**\\\nA4:Thanks for pointing this out, we believe that the lower bound $\\Omega(d\\sqrt{n})$ is tight in the hierarchical Gaussian setting, due to the following reason. For any fixed hyper-parameter $\\mu _{\\star}$ (drawn from the hyper-posterior $Q$), [30, Theorem 2.1] shows that the lower Bayes regret bound for Gaussian bandit instance $\\theta _{s,\\star} \\sim \\mathbb{P}(\\cdot | \\mu _{\\star})$ (for any policy) is $$ \\mathbb{E} _{\\theta _{s,\\star} \\sim  \\mathbb{P}(\\cdot | \\mu _{\\star})} \\sum _{t=1}^{n}(A _{s,\\star}^{\\top}\\theta _{s,\\star} – A _{s,t}^{\\top} \\theta _{s,\\star}) \\geq 0.006d\\sqrt{n}.$$ Taking expectation over $\\mu _{\\star} \\sim Q$, we can obtain the lower Bayes regret bound for hierarchical Gaussian linear bandit: $$ \\mathbb{E} _{\\mu _{\\star} \\sim Q} \\mathbb{E} _{\\theta _{s,\\star} \\sim  \\mathbb{P}(\\cdot | \\mu _{\\star})} \\sum _{t=1}^{n}(A _{s,\\star}^{\\top}\\theta _{s,\\star} – A _{s,t}^{\\top} \\theta _{s,\\star}) \\geq 0.006d\\sqrt{n}.$$\n\n**Q5. While the distributions for $Q$ and $\\theta _{s,\\star}|\\mu _{*}$ are fine to assume Gaussian, the issue is with the Gaussian noise, which is restrictive to apply the method to broader range of problems.**\\\nA5: Thanks for pointing this out. It is true that the Gaussian noise makes our theoretical results restrictive to be applied to a broader range of problems. Extending our results to the more general setting (e.g. sub-Gaussian noise setting) is also one of future directions, and may require more advanced analysis tools rather than the algebraic bounding technique in the current work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "68UMUKKiDt", "reviewer": "Reviewer_rxXv", "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:\n1. 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. \n2. 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. \n\nMoreover, 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)).", "questions": "1. L228-229: Please elaborate more on how you have achieved this.\n\nMinor:\n\n- 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.\n\n- L53: Latest\n\n- L143:  Fix  ‘=‘\n\n- L159: insert ‘and’", "limitations": "The nature of the work is theoretical.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper's contribution is important and novel because:\n1. It improves upon the existing regret bound for HeirTS in the infinite action setting\n2. Proposes a new algorithm to solve the finite action case. \n3. They also extend these algorithms to semi-bandit settings with SOTA regret bounds, which is novel.", "weaknesses": "Many parts of the paper can be significantly improved: \n\t\n1. [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].\n\n2. 140-141: Why do we need this assumption of at least n-round interaction, and how is it ensured in the algorithm?\n\n3. 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.\n\n\n4. 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).\n\n5. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to the Review by Reviewer rxXv (Part 1/2)\n\n**Q1. Please broadly discuss the novelties summarized in the appendix in the main paper, as this is your main contribution that led to improved bounds.**\\\nA1: Thank you for this suggestion, we will broadly discuss the novelties summarized in the appendix in the main paper in the final version.\n\n**Q2. Also, discuss the novelty in the techniques beyond using the improved inequality from [21].**\\\nA2: Thanks. Besides using the improved inequality from [21], our technical novelties lie in the following three aspects and we will clarify them in the revised version: \\\n$\\mathbf{(1)}$ For the improved regret bound for HierTS in Theorem 5.1 in the sequential bandit setting: our proof has two novelties: $\\mathbf{(i)}$ We use a more technical positive semi-definite matrix decomposition analysis (i.e. our Lemma B.1) to reduce the multiplicative factor $\\kappa^{2}(\\Sigma _{0})$ to $\\kappa(\\Sigma _{0})$. $\\mathbf{(ii)}$ Define a new matrix $\\tilde{X} _{s,t}$ such that the denominator in the regret is $\\sigma^{2}+B^{2}\\lambda _{1}(\\Sigma _{0})$, not just $\\sigma^{2}$. Avoid the case that the variance serves alone as the denominator. Such technical novelties are also listed in our Table 4.\\\n$\\mathbf{(2)}$ For the improved regret bound for HierBayesUCB in Theorem 5.2 in the sequential bandit setting: our technical novelty lies in decomposing the Bayes regret $\\mathcal{BR}(m,n)=\\mathbb{E}\\sum _{t\\geq1}\\sum _{s \\in \\mathcal{S} _{t}}\\Delta _{s,t}$ into three terms:\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 bounding the first term with a new method as well as the specific property of BayesUCB algorithm 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}},$$ resulting in the final improved gap-dependent regret bound for HierBayesUCB as follows $$ \\big(\\sum _{t\\geq1,s\\in \\mathcal{S} _{t}}\\lVert A _{s,t}\\rVert _{\\hat{\\Sigma} _{s,t}}^{2}\\log{\\frac{1}{\\delta}}\\big)/\\min _{s,t}\\lvert\\Delta _{s,t}\\rvert \\leq O\\big(md\\log{(n)}\\log{\\frac{1}{\\delta}} \\big),$$ which is of order $ O\\big(md\\log{(n)}\\log{(mn)} \\big)$ if we set $\\delta = \\frac{1}{mn}$.\\\n$\\mathbf{(3)}$ For the improved regret bounds for HierTS and HierBayesUCB in the concurrent setting and in the sequential semi-bandit setting: besides the aforementioned technical novelties in $\\mathbf{(1)}$ and $\\mathbf{(2)}$, the additional technical novelty lies in leveraging more refined analysis (e.g. using Woodbury matrix identity repeatedly) to bound the gap between the matrices $\\bar{\\Sigma} _{t+1}^{-1}$ and $\\bar{\\Sigma} _{t}^{-1}$ (more details can be found in Lemma D.1 and Equation (6) in Page 22).\n\n**Q3. L140-141: Why do we need this assumption of at least $n$-round interaction, and how is it ensured in the algorithm?**\\\nA3: Thanks. Actually in L140-141 the assumption is at $\\mathbf{MOST}$ $n$-round interactions. We adopt such assumption just for convenient comparison with exiting regret upper bounds (e.g. the bounds in Tables 1 and 2) for multi-task bandit/semi-bandit problem which directly assumes $m$ tasks and $n$ iterations per task. Such assumption is without loss generality and hence can be easily ensured in the algorithm (more implementation details can be confirmed in the code in our submitted zip file). \n\n**Q4. 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.**\\\nA4: Thanks. The task set $\\mathcal{S} _t$ is chosen randomly at each iteration $t$.\n\n**Q5. What is $\\hat{\\mu}$ and $\\hat{\\sigma}$ in Alg 1 (HierBayesUCB)? It is not defined yet. I found it to be defined later in (3).**\\\nA5: Sorry for the confusion. $\\hat{\\mu}$ and $\\hat{\\sigma}$ in Alg 1 (HierBayesUCB) are actually the expectation and covariance of the conditional distribution (given the history $H$) of the true task parameter $\\theta _{*}$ (including the form of hierarchical Gaussian bandit in Eq.(3)). We will clarify them when introducing HierBayesUCB algorithm in the revised version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
# Response to All Reviewers

We sincerely thank all reviewers for their detailed reading and constructive comments. We address below one concern that is common among reviewers and then we address the concerns of each reviewer individually:

**Common Question 1. Discuss the novelty in the techniques beyond using the improved inequality from [21]**\
A1: Besides the application of the improved inequality from [21], our technical novelties lie in the following three aspects and we will clarify them in the revised version: \
$\mathbf{(1)}$ For the improved regret bound for HierTS in Theorem 5.1 in the sequential bandit setting: our proof has two novelties: $\mathbf{(i)}$ We use a more technical positive semi-definite matrix decomposition analysis (i.e. our Lemma B.1) to reduce the multiplicative factor $\kappa^{2}(\Sigma _{0})$ to $\kappa(\Sigma _{0})$. $\mathbf{(ii)}$ Define a new matrix $\tilde{X} _{s,t}$ such that the denominator in the regret is $\sigma^{2}+B^{2}\lambda _{1}(\Sigma _{0})$, not just $\sigma^{2}$, avoiding the case that the variance serves alone as the denominator. Such technical novelties are also listed in our Table 4.\
$\mathbf{(2)}$ For the improved regret bound for HierBayesUCB in Theorem 5.2 in the sequential bandit setting: our technical novelty lies in decomposing 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 bounding the first term with a new method as well as the specific property of BayesUCB algorithm 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}},$$ resulting in the final improved gap-dependent regret bound for HierBayesUCB as follows $$ \big(\sum _{t\geq1,s\in \mathcal{S} _{t}}\lVert A _{s,t}\rVert _{\hat{\Sigma} _{s,t}}^{2}\log{\frac{1}{\delta}}\big)/\Delta _{\min}^{\epsilon} \leq O\big(m\log{(n)}\log{\frac{1}{\delta}} \big),$$ which is of order $ O\big(m\log{(n)}\log{(mn)} \big)$ if we set $\delta = \frac{1}{mn}$.\
$\mathbf{(3)}$ For the improved regret bounds for HierTS and HierBayesUCB in the concurrent setting and in the sequential semi-bandit setting: besides the aforementioned technical novelties in $\mathbf{(1)}$ and $\mathbf{(2)}$, the additional technical novelty lies in leveraging more refined analysis (e.g. using Woodbury matrix identity cleverly) to bound the gap between the matrices $\bar{\Sigma} _{t+1}^{-1}$ and $\bar{\Sigma} _{t}^{-1}$ (more details can be found in Lemma D.1 and Equation (6) in Page 22).

Besides the concerns, we also thank gratefully reviewers for pointing out minor typos and we will fix them in the revised version.

Meta-review: 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.
Decision: Accept (poster)