Beyond task diversity: provable representation transfer for sequential multitask linear bandits
Authors: Thang Duong
Zhi Wang
Chicheng Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: Bandits
multi-task
meta-learning
representation learning
online learning
task diversity
Primary area: bandits
TL;DR: We study lifelong learning in linear bandits, where a learner interacts with a sequence of linear bandit tasks that share a low-rank representation without requiring the Task Diversity assumption.

Abstract: We study lifelong learning in linear bandits, where a learner interacts with a sequence of linear bandit tasks whose parameters lie in an $m$-dimensional subspace of $\mathbb{R}^d$, thereby sharing a low-rank representation. Current literature typically assumes that the tasks are diverse, i.e., their parameters uniformly span the $m$-dimensional subspace. This assumption allows the low-rank representation to be learned before all tasks are revealed, which can be unrealistic in real-world applications. In this work, we present the first nontrivial result for sequential multi-task linear bandits without the task diversity assumption. We develop an algorithm that efficiently learns and transfers low-rank representations. When facing $N$ tasks, each played over $\tau$ rounds, our algorithm achieves a regret guarantee of $\tilde{O}\big (Nm \sqrt{\tau} + N^{\frac{2}{3}} \tau^{\frac{2}{3}} d m^{\frac13} + Nd^2 + \tau m d \big)$ under the ellipsoid action set assumption.
This result can significantly improve upon the baseline of $\tilde{O} \left (Nd \sqrt{\tau}\right)$ that does not leverage the low-rank structure when the number of tasks $N$ is sufficiently large and $m \ll d$. We also demonstrate empirically on synthetic data that our algorithm outperforms baseline algorithms, which rely on the task diversity assumption.

Beyond Task Diversity: Provable Representation Transfer for Sequential Multi-Task Linear Bandits
Thang Duong
Zhi Wang
University of Arizona thangduong@arrzznn..ee
University of zhi wang@wisc. edu
Chicheng Zhang
University of Arizona
chi chichengecss. arizona.edu
Abstract
We study lifelong learning in linear bandits, where learner interacts with a sequence of linear bandit tasks whose parameters lie in an m-dimensional subspace of TRd, thereby sharing low-rank representation. Current literature typically assumes that the tasks are diverse, i.e., their parameters uniformly span the m-- dimensional subspace. This assumption allows the low-rank representation be learned before all tasks are revealed, which be unrealistic in real-world applications. this work, we present the first nontrivial result for sequential multi- task linear bandits without the task diversity assumption. We develop an algorithm that efficiently learns and transfers low-rank representations. When facing N tasks, each played over rounds, our algorithm achieves regret guarantee of ÖNNm/F+ N dm No + rmd) under the ellipsoid action set assumption.
This result can significantly improve upon the baseline of Ô (N that does not leverage the low-rank structure when the number of tasks N is sufficiently large and m < We also demonstrate empirically on synthetic data that our algorithm outperforms baseline algorithms, which rely the task diversity assumption.
Introduction
Recommendation systems that interact with customers to promote the best items for each user have been widely adopted around the world. These interactions are often sequential and can be modelled linear bandit problems [Abe and Long, 1999, Dani et al., 2008, Rusmevichientong and Tsitsiklis, 2010, Abbasi- Yadkori et al., 2011] where the characteristics of items can be represented as context vectors, and user's preference for an item (i.e., reward) can be modelled using a linear combination of the context of the item. Even though the problem is typically high-dimensional, different users may exhibit similar preferences, leading a low-dimensional underlying reward structure.
Motivated by this observation, there has been growing interest in representation learning within the context of linear bandits. For instance. in the item recommendation example, each session of interaction with a user can be seen as a linear bandit task, and similarity across tasks can be captured by the existence of a global feature extractor that applies to all problem instances.
Formally, we consider problem where the learner sequentially faces N d-dimensional linear bandit tasks, each with horizon т, with key assumption that the reward predictors of the N tasks, 01...., ON. lie an mn-dimensional linear subspace of ı The goal the learner to minimize their meta (pseudo-)regret, which is the sum of regret across all tasks (see Equation (1) below), by exploiting the shared subspace structure.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

One naive approach is to solve each task independently using base algorithm (such as Lin- UCB [Abbasi- Yadkori et al., 201 I] or PEGE [Rusmevichientong and Tsitsiklis, 2010]); this approach. which we will henceforth refer to as the individual single-task baseline), would yield an upper bound on the meta-regret of (N) On the other hand, had the shared m-dimensional subspace been known beforehand, one would only need to estimate each reward predictor's projection onto the subspace; this leads to a meta-regret of Ó(NTYT). In this work, we focus on the setting where N and are large and m < d, the regime in which representation transfer learning would be beneficial.
Despite rich results for multi-task linear bandits in the parallel setting [e.g. Yang et al., 2020, Hu et al., 2021, Yang et al., 2022, Cella et al., 2023], progresses on multi-task bandits in the sequential setting have been relatively sparse. This can be attributed to the additional challenge of metaaexplooation: in addition to exploration in each bandit learning task, one also needs to determine when (in which tasks) to acquire more information on the shared m--dimensional subspace representation. This is in contrast to the parallel setting, where algorithms that treat all tasks equally can achieve a mear-optimal regret through a reduction to low-rank linear bandits [Hu al., 2021, Jang et al., 2021a].
Under the assumption that the action sets are well-conditioned ellipsoids, Qin et al. [2022] design an efficient algorithm with a meta-regret of Ô [NmyF- + dmv/TN). However, relies on an additional key assumption that the tasks are "diverse" in the m-dimmensoonll subspace: more formally, for any subsequence of tasks S, the m-th eigenvalue of the task parameters' covariance matrix Enes 0, is bounded away from zero (see Tripuraneni et al. [2021] for related assumption in the supervised regression setting). However, this task diversity assumption is hard to verify and may not even hold in practice. Therefore, we raise the question:
Can we design sequential multi-tast task bandit algorithms with provable low meta-regret without strong assumptions on task parameters, especially on task diversity?
In this paper, answer this question positively. Under mild assumptions that the action sets well- conditioned ellipsoids and all task parameters have norms upper and lower bounded by constants, we design an algorithm with a meta-regret of Ô (Nm/F++ + , dm Nd + rmd) providing the first nontrivial result for sequential multi-task linear bandit without the task diversity assumption. To the best of our knowledge, prior to our work, no regret bounds better than that of the individual single-task baseline (i.e., o(Nd/T)) were known for this setting.
Our algorithm, BOSS, is based on reduction to a bandit online subspace selection problem. Specifi- cally, for each new task n. our algorithm chooses a subspace, represented by its canonical orthonormal basis B,,, to approximate the ground-truth subspace B and guide exploration. To address the chal- lenge of meta-exploration, different subspaces/directions,, our algorithm is designed to randomly meta-explore in some tasks and use them to learn B. Empirically, we demonstrate the effectiveness of our algorithm in simulated adversarial environment where the task diversity assumption does not hold.
choosing different B,, 's leads to learning the projections of O,, onto
1.1 Related work
Parallel representation transfer for multi-task linear bandit. The paraliel setting where the learner interacts with N tasks simultaneously in each round was initially studied by Yang et al. [2020]. For the finite action setting, under some distributional assumptions on the action set in each round, they provide a total regret lower bound of Ω N Wmm + vmdrN) and an algorithm that matches this up to logarithmic factors. For the infinite action setting, they provide a lower bound for the problem of Ω [Nm/F++ + d d/ which holds even under the task diversity assumption. Under the same task diversity assumption and in the infinite action set setting". Yang et al. [2022] present an algorithm with a regret guarantee of Ô (Nm + dv dVmrN).
'Ô hides polylog(T, N, d') factor
2 AAthoughh not mentioned explicitly, a careful examination of Yang et al. [2022] shows that its Lemma 4.2 N uses the assumption that am ((O).... 0x))) v m. which is task diversity assumption.

---

Prior
Task
Algorithm
Regret guarantee(s)
info.
diversity
Indep. PEGE for each task
None
No
Ō (NNd/F
Ô ÖNNVVT + (Mm/T + dvmrN
Qin et al. [2022]
m,
Yes
Bilaj et al. [2024]
None
Yes
at least O (NVF(d - mm) log (1
m mmin (d-m)
BOSS (our work)
N, m,
No
ONNW/++ N + Nd + rmdd
Table Comparisons of the settings, assumptions, and regret guarantees in this paper and previous works. A more comprehensive comparison is available in Table 2 of Appendix A.
For general action spaces, Hu et al. [2021] provide a regret guarantee of Ô (N /Nvdrr + dVTNM) albeit using a computationally inefficient algorithm. They also provide an extension for multi-task linear reinforcement learning under the assumption of low inherent Bellman error.
Unlike previous approaches, Cella et al. [2023] relaxes the requirement know the subspace rank m and the need for the task diversity assumption. Assuming that the action sets are finite and drawn from specific distribution, by using trace-norm regularization for estimating task parameters and taking actions in greedy fashion, they provide regret upper bound of Ô [N /mF + d that matches the lower bound from Yang et al. [2020] up to logarithmic factors.
Sequential representation transfer for multi-task linear bandit. Compared with the parallel setting, the sequential setting is more challenging, where the learner only interacts with task time; hence, even after many tasks, the reward predictors of the seen tasks may not span the underlying m-dimensional subspace. Qin et al. [2022] avoid this challenge by assuming task diversity assumption, i.c., any large enough subset of tasks span the underlying m-dimensional subspace in
well-conditioned manner. With this, they provide a meta-regret guarantee Ô (Nm/F dmvTNW
which nearly matches lower bound of (Nm./r + dVmrN). They also extend their analysis to
nonstationary representation setting where the global feature extractor can change over segments of tasks. Yang et al. [2022] study the sequential setting with an additional assumption that ||0,/| = for all tasks; however, appears that there may non-trivial oversight in the analysis."
Bilaj et al. [2024] study a related setting where the task parameters are i..d. sampled from a distribu- tion with high variances from m-dimensional subspace and with low variances in the orthogonal di- rections. They provide meta-regret guarantee of at least Ô N VFld- - m) log (1+
X (d-m)
where X is the smallest eigenvalue of the empirical covariance matrix of the actions taken. Since a linear bandit algorithm is expected to converge to pull the optimal arm at the end; X may be constant when the action space is fixed. Thus, this bound can be as large as Ö(Nd/T)). For quick reference, see Table for a comparison between our work and most related works. See also Appendix A for further discussions on related work.
2 Problem setup
We consider sequence of linear bandit tasks of the same length described by the task parameters 01.-.. Ox E Rd chosen by an environment such that they satisfy Assumption 1. The learner solves N tasks sequentially. In task n, for each time step l,..., .....,77 7, the learner chooses an action An, from the action set A that satisfies Assumption and receives a reward rn,t AT Uha where
In the proof of Theorem 5.1 therein, key inequality, |10,- - - 1..122 S [10, 1|2 110.l1.. was used (see Equation (21)); however, this inequality does not hold in general.
3

---

Algorithm 1 Meta-Exploration procedure
1: Input: Task index n, exploration length Ti (a multiple of d)
2: for E [d] do
3: Let An. = Age; for t = u(i 1 1) +
1, ui, where u d
4: end for
5: for time step t +- 1, ................................ Ti do
6: Take action A,, and receive the reward Tn.t
7: end for
8: Compute i == argmingeRR ti Eim ((Ane; rn,))²
9: for time step +- 71 1,, ,T do
10: Take action An, t- arg max.Ea ( (x)
11:
end for
Na, is independent, mean-zero I-sub-Gaussian noise. The learner then moves on to task + 1 and repeats the same learning process.
Assumption 1 (Low-rank representation). Let m d. For task parameters o,.... SN. there exist (i) a global feature extractor B E [Rdx with orthogonal columns and (ii) vectors wi,..., WN E R such that 02 Bw;for all i [N].
Given a semi- orthonormal matrix U E d.d (i.e., U Im), denote by U1 E (d)x(dm)) matrix whose columns constitute an orthonormal basis of the orthogonal complement of span(U),, where we break ties in dictionary order*. We also denote the i-th column vector of by (i).
Following Rusmevichientong and Tsitsiklis [2010] and [Qin et al., 2022], we also assume that the action set A is ellipsoid and the task parameters have bounded E2 norms:
Assumption 2 (Linear bandits with ellipsoid action sets). The action set A {I E Rd T 7-M S 1 is an ellipsoid, where M is a symmetric, positive definite matrix. In addi- tion, there exist constants Ounn and m S such that for all tasks n E [N], Omni S 110,1l2 S 0max
We define the expected pseudo-regret for task as R == T max.E a 00 and the meta-regret for all N tasks as
E EE On].
R
R
max a TO, E
Σ AT, On
(1)
aeA
The learner's goal is to sequentially interact with each task in a way that minimizes its meta-regret.
3
Algorithm
Unlike the parallel setting or the sequential setting with a task diversity assumption, here, the learner cannot directly learn the global feature extractor B. Instead, it needs to reason with the uncertainty about B learned from the seen tasks.
High-level idea of our approach. To simultaneously learn B online and utilize our (imperfect) knowledge of it, we solve the sequential multi-task bandit problem using bi-level approach:
At the lower level, for each task n, the learner has the option of invoking two base algorithms: one performs naive exploration that does not incorporate our knowledge on B, using a variant of full- dimensional linear bandit algorithm (PEGE (Rusmevichientong and Tsitsiklis, 2010], Algorithm I); the other tries incorporate learned subspace B as prior knowledge get reduced regret (Algorithm 2).
Algorithm and 2 can be viewed as performing meta exstoarxploottion and meta-cxploitation respectively: Algorithm 1, while ignoring the low-dimension property of the tasks, produces unbiased estimators
As we will see, other tie- breaking mechanisms would not change our algorithm and analysis; see Definition 9 and the discussion below in Appendix C for more details.

---

Algorithm 2 Meta-Exploitation procedure
1: Input: Task index n, exploration length (a multiple of m)), and the subspace orthonormal basis Bn E Rdxm
2: for i E [m] do
3: Let An, - do (i) for = uli 1) + ., wi, where I
4: end for
5: for time step t f- 1, 72 do
6: Take action An, and receive the reward In.1
7:
end for
8: Compute Wn == argmin Ei= ((An,t Brw) rn.e)
9: Let 0n == Br in
for time stept t- 72 + 1,.., , do
11: Take action An, arg max.EA (n,0n)
12:
end for
of On that helps learn the task subspace B; Algorithm 2 allows the learner to achieve a much lower regret when the subspace B approximately contains 0,; however, using it may slow down the learning of B.
At the upper level, the learner has two decisions to make each task n: (1) choosing between meta-cxploration and meta-explottation (2) choosing a subspace B, to use if performing meta- exploitation. To this end, propose Algorithm 3, which aims making these decisions in feedback-driven way to ensure low meta-regret.
We now elaborate on each level in more detail.
The lower level. As mentioned above, Algorithm is for meta-exploration. When invoked in task n, it achieve two goals simultaneously: obtaining an unbiased estimate of On, while maintaining reasonable regret guarantee for task n. For the first steps (line 3 to 6), the learner takes {A that span the action space A, where is the i-th canonical vector of IRd and V (M) a constant factor that ensures λay
actions
Ao
(recall Assumption 2).
Then, the learner estimates task parameter Ó, in line and acts greedily for the rest of the task (line 10). We summarize its guarantee (originally due to Rusmevichientong and Tsitsiklis [2010]) as follows:
Lemma 3. Fix Tı to be a multiple of Suppose Algorithm is run on task with the exploration length T1. Then, there exists some constants C2, > 0 (that depend on No Omax 6 minn and M) such that:
T The regret on task n is bounded as R. I 61 (T
d² 71
Csnfoi
2. With probability 2 1 6, 1|0,, 0n S dy
In
We defer the proof of this lemma to Appendix Lemma reveals tradeoff between meta- exploration and regret minimization for task n: if T1 larger (say, closer to 7), 6, estimates O,, more accurately; however, this may yield worse bound on R"
the other hand, Algorithm 2 is for meta-exploitation. takes a subspace (represented by its orthonormal basis В) as input, and when invoked in task n, can achieve a lower regret guarantee than Algorithm when the subspace contains vectors that closely approximate O,- Instead of exploring Rd. the learner only explores the subspace induced by B,, (lines 3 and 6). Then, the learner estimates the low- www-imennsionl task parameter t., in line 9 and acts greedily for the rest of the task (line 11). We summarize its guarantee (originally due Yang et al. [2020]) as follows:
Lemma Fix Ta to be a multiple of m. Suppose Algorithm 2 run on task n with imput subspace B., and the exploration length T2. Then, there exists some constant O (that depends on Xo, Omaxs O m
5

---

Algorithm 3 BOSS: Bandit Online Subspace Selection for Sequential Multitask Linear Bandits. The full algorithm 4 in Appendix A.
Input: Task length r, number of task N, task dimension subspace dimension m, and explo- ration rate p.
2: Initialize: An uniform distribution Do over the experts & in Definition
3: for E [M]: do
4: Randomly draw B, from Dn
5: With probability p. Zn 1, otherwise Zn = 0
6: if Z, = then
7:
Exploration procedure Algorithm
8:
Update the distribution Dn+1 with the EWA algorithm [Freund and Schapire, 1997], with learning rate = 1n2
9: else
10:
Exploitation procedure in Algorithm with B,
end if
12:
end for
and M), such that the regret on task n bounded as:
(m²
R S c.
T2 +
+
+1 0ul12
T2
m² + +a²)) where a is defined in Specifically, if II,,, On S 20, then R. < 4c + Lemma 3.
Lemma 4 reveals the opportunistic nature of Algorithm 2: if f, is perfectly contained in the subspace spanned by B,, [| 0. = O and the regret bound is R. s 0 + un² which can be as low as /F) on the other extreme, [1 0, can be as large as ||0,, || in the worst case, which yields trivial linear regret bound. Thus, its regret guarantee hinges good choices of subspace Bn as input. See Appendix E for the proof of Lemma 4.
The upper level. For the upper level, we propose Algorithm 3 that decides (1) when to perform meta-exploration and (2) the subspace use if performing meta-exploitation.
For (1), for each task, the learner chooses to explore the subspace with probability p (line 6) or exploit with the online subspace estimate Вn (line 9).
[B,) A n=
For (2), we propose to choose
that can optimize the following cost function online
Chit T2 + m= + +a²)
20; otherwise.
B 0x112
C,(
Cnise :
The motivation behind this definition of C, follows: according Lemma 4, C, (B.) is (up to constant) an upper bound of the regret of the learner at task n. were the learner to invoke Algorithm using B, for this task. Therefore, if we can guarantee Σ. Cn to be small, then using Algorithm for all tasks yields a small meta-regret.
An immediate challenge in directly optimizing Cn defined in Eq. (2) is its dependence on unobserved quantity 8,, This challenge is further complicated by the following: (i) at best, we observe d, 's that are a-approximations of 0, (e.g. in those meta-exploration tasks, see Lemma 3); (ii) in meta- exploitation tasks, we do not have guarantees on how close Ó,, is to 0,; note the difference in the definitions of f in meta-exploration and meta-exploitation tasks, respectively.
'I the case split of the definition of CB,B),, the value of || B e., 2| is independent of the choice of B1. See Definition 9 and the discussion below in Appendix C for more details.

---

To address the challenge (i), we propose to optimize the following surrogate cost function for Cn:
Chit
|B S a;
(B)
Caiss
otherwise.
In Lemma 11 Appendix C, we show that, with high probability, C₂ is an upper bound of Cn (when 8, close to 8, as guaranteed by Lemma 3 in meta-exploration rounds).
With this modification of the optimization objective, challenge (ii) persists: C₂ is only a valid high-probability upper bound of C, for all meta-exploration rounds n; to ensure this upper bound property, we propose to optimize the cost:
Zn p
where we introduce the importance weighting multiplier Ze. Our key observation that, although (B) is no longer upper bound of C., (B), the upper bound property holds in-expectation; this, observe that for any fixed B,
Ez, [Bn = Ez, (B.
Zn
Zm = (B), 2 Ez. CB)
here, the first equality is from the definition of (B)); the inequality (here, Z indicates greater than up to a negligible constant) uses the mentioned property that when Z, 1, with high probability, (B)( 2 (B) (see Lemma 3 and Lemma 11); the second equality is from the fact that Zn Bpr(p).
Following the online learning literature, we propose to use the exponential weight algorithm (EWA, aka Hedge) [Freund and Schapire, 1997] to optimize [B)} online. Ideally, we would like to EWA with the B = B B E R s.t. B B = Im the set of all m-dimensional subspaces; however, this is impossible because [8] is infinite. So instead, we propose to run EWA with the expert set defined as an E-cover of B:
Definition 5. & is said be a E-cover over the set of B in the principal angle sense, if:
BB E B, 3B' E E such that B'IlE S.
Definition 5 is motivated by the well well-known fact that | B'll is the Frobenius norm of the sine of the principal angle matrix between subspaces spanned by B and B'. In Appendix C.1 we show how to construct E and its size | < (Vdm/s))oddn In subsequent discussions, will assume that BOSS uses such an 8
Define a constant shift and scaling of C, (B) == C.ses [C,( Cass 2a we note that any regret guarantee over sequence
p_
regret guarantee over sequence { immediately translates {C,). By the construction of the expert set E sequence (6, } is realizable with high probability: there exists some B& E 8 such that DA (B. = 0: this allows EWA to achieve constant regret guarantee, summarized follows:
Lemma 6. Let = = In
(with e2 defined in Lemma 3) and 8 = Ne, where e is a constant in Lemma 13. Then, assuming that t > d,, Algorithm 3 chooses a sequence of subspaces (Bn)
over the expert set & defined in Definition 5, such that:
Σ E (Bm)) 5o (NCast Casos log [3
N
(
=0 (N
(m² + a² ad)) Jdm
P
T2
p
n=1
Note that the cumulative cost bound of { [B,]] has two terms: the benchmark term N Cass and the [ The benchmark term represents the best-case regret bound one can
regret bound term Coies P
7

---

achieve if, for all task n. the chosen subspace Bn can well approximate 6n (i.e. _ fn S a) On the other hand, the regret-hound term depends on a few important factors: first, the cost decreases when the meta-exploration probability p increases- this matches our intuition that larger p gives more frequent feedback to learn about 8, allowing the learned B,, adapt faster 8,: second, the cost depends logarithmically on the size of the expert set in 1E which is standard in the online learning from expert advice literature; third, the cumulative cost depends on the range of the instantaneous costs Caisa.
Remark 1. The subspace selection game in the upper level resembles the partial monitoring problem [see Lattimore and Szepesvári, 2020, Chapter 37]. where the learner does not directly observe the loss for its actions but receives signals from an environment according to an observation matrix. Here, in our subspace selection problem, the learner does not directly observe the chosen subspace's cost for most tasks, except when they choose to explore the subspace B. Unlike the traditional partial monitoring problem, here, the observation would be On, and the cost C, (B) depends on the chosen subspace B and O₂ This means that the cost matrix has an infinite number of columns (one for each B) and the observation depends on the actions of the learner and the environment in stochastic fashion, unlike a deterministic dependence in the original partial monitoring setting.
4 Performance Guarantees
We bound the meta-regret of Algorithm 3 in Theorem
Theorem 7. With exploration probability p = min ((
( ((2mg N
3 .1). by choosing & = =a
c2d
In g (with 02 defined in Lemma 3) where 8 N TI
mmi 7 /d]
m [VT], the meta-regret of the BOSS algorithm is bounded by:
72
Rr S 2 ONNNNV 3 + Nod +rmd)
(5)
In the meta-regret bound (5), we view the first two terms as the main terms and the last two as "burn-in" terms. The first term, Nm the cumulative regret bound of the oracle baseline, i.c. the idealized algorithm that takes ad advantage of the extra knowledge of B to achieve a ((mv/) regret for every task. The second term, N 7 dm is the main overhead for learning the representation B; it grows sublinearly in N, and as a consequence, is dominated by the first term when the number of tasks N is very large (specifically, N >> parallel setting [Yang et al., 2020, Hu et al., 2021], our dependence on is admittedly weaker; nevertheless, to knowledge, Theorem 7 is the first nontrivial result in the sequential setting without task diversity assumptions, which has not been studied before in [e.g., Qin et al., 2022].
d' m2 Compared with multi-task regret bounds in the
For the burn-in terms, the Na term can be interpreted rmdd term can be interpreted as the learner sacrificing a constant number of tasks (md tasks) to learn good representation B. Observe that, in the less favourable situation where N < md or < df, the burn-in terms would lead to regret bounds worse than the trivial NT.
constant d2 regret overhead per task; the
Comparison with the individual single task baseline. Recall that the individual single-task baseline has a meta-regret of ((Nd/F); our meta-regret guarantee improves over this baseline when > d² and N >> my/T. We leave broadening the parameter regimes when our guarantee outperforms the individual single-task baseline as an important open problem.
Comparison with lower bounds. Qin et al. [2022] showed a lower bound for the problem: Q [Nm/F++ + dv W/mrN). We can see that there still exists a gap between our upper bound in Theorem 7 with this, and the gap is bigger than other solutions with task diversity assumption such as Qin et al. [2022]; we speculate that this a price we pay due to not making any assumptions on task diversity.
We now sketch the proof of Theorem 7 below.
Proof sketch. Denote the pseudo-regret for task as R := max.EA a),,a) - -T= Ant))
8

---

We decompose R,, as follows:
N
R2
IE
E
Pe En - R1 - Zno
n=1
N
N
Σ
EI
R4
Zn
+
Σ
18 Rr Zn =0] (1 (1-p)
n=1
n=l
<Cinto
Np +
E
Cn (Bm)
n=1
d²
Np N
12 77
m²
T1 )
de
rdm
57
T2
p
d²
Tdm NNg + NT m
-
Npt + NT
p
where the first two equalities are by the definition of R2 and algebra; the third equality uses the law of total expectation; the inequality uses Lemmas 3 and 4 to bound the first and second terms, respectively; the fourth equality due to the definition of Cinto and Lemma 6; the last equality by algebra.
The meta-regret of Algorithm follows from the choices of TI, T2, and p - specifically, 72 balances the last two terms, whereas Ti and aims at balancing the first three terms subject to the constraint that Ti S T and p < 1 see Appendix for the remaining details.
Adaptivity to problem parameters. Algorithm 3 requires the knowledge of N and m, the total number of tasks and the dimensionality of the subspace underlying the task parameters. Below, show that knowledge of N can relaxed.
We can relax the need to know N by using the doubling trick on BOSS. Specifically, in phase i, we can run our algorithm with the assumption that there are 2 total tasks in this phase. The modified algorithm has meta-regret guarantee that is within constant of the algorithm that knows N. This implicitly gives an adaptive setting meta-cxploration probability p that decaying over time.
For m, the requirement can be relaxed to knowing an upper bound of m. Removing this knowledge requires a change of approach, such low-rank matrix optimization, as in Cella et al. [2023] or additional assumption, as in Bilaj et al. [2024]. Cella et al. [2023] is in the parallel setting, which is not applicable here, and Bilaj al. [2024]'s 's guarantee can be large as (NNd/T) discussed in section 1.1.
Experiments
In this section we compare the performance of our BOSS algorithm with the baselines on synthetic environments. The algorithms we evaluate include:
PEGE: independently solves each task using the PEGE algorithm (Rusmevichientong and Tsitsiklis, 2010]
PEGE-oracle: The "oracle baseline" that only uses PEGE the true subspace B, for all tasks
SeqRepL: our implementation of [Qin et al., 2022], in which B,, is estimated with SVD and the tasks for meta-exploration are chosen deterministically at round n i(++1) for i 1,2,
BoSs-no-oracle: Algorithm 3 with 8 set of 100,000 experts drawn uniformly at random from B.
BOSS: Algorithm 3 with E set as 100,000 experts drawn uniformly at random from B, plus the ground truth expert B. This algorithm is better approximation of the original BOSS (Algorithm 3) since there exists B, E 8 such that [[ B S e.
'The code for our paper can be found https: http//ggtttttttttteeeeeeeee comm/btoongggaataaaggBBSS

---

The setting is (N, T. d, m) = (4000, 500, 3). The environment reveals new subspace dimension tasks 1, 2501, and 3501. In this experiment, we assume A is a unit sphere, i.e., M La- At each task n, denote by B, E IR mgdxm, the subspace basis that the environment used to generate O,. where mn is incremented when some W., ~ Unif(Smm=]] and A1 ~ (0.88 1J) 2, where min 0.8, max 1.
1. 2501, 2501, On is chosen in the following way: 6n X B, W/ for is a random scaling factor to ensures Assumption
The hyper-parametert in the figures indicate #1 standard deviation computed over 5 independent runs.
T1, and a of all algorithms, where it applies, are tuned. The error bands
Figure la clearly shows the linear dependency of the cumulative regret on N. Observe that BOSS and its variants outperform both the independent PEGE and the SeqRepL baselines. It is also clear that the gap between BOSS-no- moo-lracle and BOSS exists because the expert set 3 used in this experiment does not cover the true B, since even with d 0.5, the theoretical size the expert set is Yम.
[ = (vdm/s)dm x 30 in this experiment setting which is much larger than the expert set size used in Boss-no-oracle.
In Figure lb, we plot [ BallF, which measures the closeness of Ba, to B,, When the environ- ment reveals new subspace dimension at tasks 1, 2501, and 3501, all algorithms' estimation B,, require updates and converge after a while. Even though BOSS-no- ww-oooooeee oracle has a worse estimation of Bn compared to SeqRepL, it achieves better regret due to having better estimation of 6, as shown in Figure Ic.
76003
5005
00.00
04
00
30
2008
1368
2008
1306
2002
580
1006
2010
2503
1030
1306
2008 2508
1000
4000
(a)
(b)
(c)
Figure 1: Comparing the cumulative regret of BOSS and other baselines. The setting (N, T, d, m) (4000, 500, 10, 3) and |00lll2 E [0.8, 1] Vn e [N] chosen uniformly at random from this interval. The environment only reveals a new subspace dimension at tasks 1, 2501, and 3501, so there's no task diversity assumption.
Discussion and Future Work
We study the problem of sequential representation transfer in multi-task linear bandit, where the task parameters are allowed to be chosen adversarially online. Our BOSS algorithm achieves the regret guarantee of Ô [Nm// + 3 + Nd + +rmd without using the task diversity assumption as in previous works. This opens up many promising avenues for future work. Statistically, it would be good to design an algorithm that performs no worse than the individual single-task baseline's 's performance all parameter regimes. In addition, BOSS utilizes the special structure of fixed, ellipsoid-shape action spaces to obtain useful information for meta-exploration, extending the algo- rithm and guarantees to general and tirevnarying action spaces an important direction. Practically, it would also be nice to design parameter-free free variants of BOSS that do not require knowing m ahead of time. Furthermore, BOSS requires maintaining an exponentially large number of experts B in the future, we would like to develop more computationally-efiin -efficcce algorithms. Lastly, it would be interesting to study relaxations of Assumption (all task parameters lie exactly a m-dimensional linear subspace), similar to Bilaj et al. [2024] or the changing subspace setting of Qin et al. [2022].
10

---

References
Yasin Yadkor,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Naoki Abe and Philip M Long. Associative reinforcement learning using linear probabillistic concepts. In ICML, pages 3-11. Citeseer, 1999.
Javad Azizi, Thang Duong, Yasin Abbasi- Yadkori, András György, Claire Vernade, and Moham- mad Ghavamzadeh. Non-stationary bandits and meta-learning with a small set of optimal arms. Reinforcement Learning Journal, 5:2461-2499 2024.
Maria-Florina Balcan, Keegan Harris, Mikhail Khodak, and Zhiwei Steven Wu. Meta-learning adversarial bandits. arXiv preprint arXiv:2205. 14128, 2022.
Steven Bilaj, Sofien Dhouib, and Setareh Maghsudi. Meta learning in bandits within shared affine subspaces, 2024.
Leonardo Cella, Karim Lounici, Grégoire Pacreau, and Massimiliano Pontil. Multi-task representation learning with stochastic linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 4822-48477 PMLR, 2023.
Varsha Dani, Thomas Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In COLT, volume 2, page 3, 2008.
Murat A Erdogdu and Mert Vural. Csc 2532 winter 2024: Statistical learning theory, lecture 5. pdf, 2024.
htttps://et //rdoodu//
Yoav Freund and Robert E Schapire. A pecision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-13) 1997.
John Gower and Garmt B Dijksterhuis. Procrustes problems, volume 30. OUP Oxford, 2004.
Jiachen Hu, Xiaoyu Chen, Chi Jin, Lihong Li, and Liwei Wang. Near-optimal representation learning for linear bandits and linear rl. In International Conference on Machine Learning, pages 4349 4358..
PMLR, 2021.
Kyoungseok Jang, Kwang-Sung Jun, Se- Young Yun, and Wanmo Kang. Improved regret bounds of bilinear bandits using action space analysis. International Conference on Machine Learning. PMLR, 2021a.
pages
Kyoungseok Jang, Kwang-Sune Jun, Se- Young Yun, and Wanmo Kang. Improved regret bounds of bilinear bandits using action space analysis. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 4744-4754. PMLR, 18-24 Jul 2021b. https: h/tp:///////ocoossss/..o mlr.press// /vt/s///vv///////// satssss/vv9/jaaggs/ee jang21a. a..1ml..mm..
Tor Lattimore and Csaba Szepesvári. Bandil algorithms. Cambridge University Press, 2020.
Yuzhen Qin, Tommaso Menara, Samet Oymak, ShiNung Ching, and Fabio Pasqualetti. Non-stationary representation learning in sequential linear bandits. IEEE Open Journal of Control Systems, 41-56, 2022.
Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 351 2010.
Matus Telgarsky. Deep learning theory lecture notes. https://njt.cn cs. http:tt...s.llnniiieeee illinois.edu/lle 2021. Version: 2021-10-27 v0.0-e715012d (alpha).
Nilesh Tripuraneni, Chi Jin, and Michael Jordan. Provable meta-learning of linear representations. In
International Conference on Machine Learning, pages 10434-10443, PMLR, 2021.
Trung Vu. Matrix perturbation and davis-kahan theorem. https://trungvietten hww.ingvviitttgghhhheee github. io/
notes/22020/Daviskahha 2020.

---

Jiaqi Yang, Wei Hu, Jason D Lee, and Simon Shaolei Du. Impact of representation learning in linear bandits. In International Conference on Learning Representations. 2020.
Jiaqi Yang, Qi Lei, Jason D Lee, and Simon Du. Nearly minimax algorithms for linear bandits with shared representation. arXiv preprini 2rXiv:2203.15666 2022.
12

---

Prior knowledge
Task
Algorithm
Setting
Regret bound(s)
diversity
Indep. PEGE
Both
None
No
((NdFF)
[Hu et al., 2021]
Parallel
N, m
No
NV + d..ddv.Nnn TNm)
0
NmwF +d dàmN/TN)
[Yang et al., 2020]
Parallel
N, m,
Yes
Ω Nmm/T + dv M
[Yang et al., 2022]
Parallel
N,,,T
Nm + dv M
Ô
Nv + dv dvTNN)
[Cella et al., 2023]
Parallel
A =
No
Ω
VNrdm
[Jang et al., 2021b]
Sequential
None
No
Ô (d + N VdT
Ô NmwF= dmv
[Qin et al., 2022]
Sequential
m, 7
Yes
Ω Nmm + dv dVmTN
at least O (NVT(d mm)
[Bilaj et al., 2024]
Sequential
None
Yes
log
1 X (d-m)
Ö(NmVF+N N dm
BOSS (ours)
Sequential
N, m,
No
+Nd + rmd)
Table A comparison of the settings, assumptions, and regret guarantees between our results and prior works.
A Further discussion on related work
Meta learning bandit problems. Balcan et al. [2022] analyzed harder problem in the Sequential setting by dealing with tasks generated by an adversary, and each task is an adversarial linear bandit problem. By using online mirror decent base algorithm, they provided a guarantee of
Ô (mingses N (dVeFF+e)) + - where V. measures the proximity of the optimal vT parameters of all N tasks. Balcan et al. [2022]'s results also applies the sequential meta-learning with adversarial K-arms bandit, which is further investigated by Azizi et al. [2024]. Their bandit meta-learning with small of optimal arms setting analogous the sequential multi-task representation transfer in linear bandit. The task diversity assumption is equivalent to the Azizi al. [2024]'s Efficient Identification assumption; both require a gap separate the noise from the problem's parameters. Our BOSS algorithm also has some high-level similarities with their E-BASS algorithm.
Bilinear bandits. The bilinear bandit problem described by Jang et al. [2021b] studies a setting where the learner has (potentially time-varying) sets of left actions and right actions available. can take a left action æ and right action R and receive reward r = - R + v/. This reduces our setting when the action set of the left action is the task descriptor { parameters have low-rank structure. When applying their approach is Ô NddF + ~ Vdr) which is worse than independently using a classical algorithm, such as PEGE, for each task. This due to the fact that Jang et [2021b]'s solution does not exploit the low-rank and the left action structures.
and the task's setting, their guarantee
13

---

In Table 2, we comprchensively compare the settings and assumptions of the previous works for the multi-task bandit representation transfer problem.
B
Additional information on Algorithm 3
Algorithm 4 BOSS: Bandit Online Subspace Selection for Sequential Multitask Linear Bandits
1: Input: Task length т, number of task N, task dimension d, subspace dimension m, learning rate
7,, and exploration
p.
2: Initialize: An uniform distribution Dj over the set of experts & in Definition 5
3: for [M]] do
4: Randomly draw B, from D,
5: With probability p: Zn 1, otherwise Zn = 0
6: if Zn = then
7:
Exploration procedure in Algorithm Update the distribution Dn+1 with the EWA algorithm
8:
9:
For all B E E,, observe the cost (B) = T[[] 0, I a) + I[[IB] >
Cnias
10:
The shifted and scaled loss:
(n( Zn p
Zn
(B( Cnias
Chit
CB Cast
p
Cniza
7,
Update: Dn+1 (B+) EBeeer (x,(B')xx(( expl n (B))
DB, expí pexp(-nf.. (...
12:
else
Exploitation procedure in Algorithm with B,, Update: D D,
14:
p > In this case, (B) = Caiu
(B) 2n
Chit 2n
=
2,=0
15:
end
16:
end for
C Additional details related to Section 3
We first provide more details on the construction of the expert set used in Section 3. To construct 8 an e-cover of B in the principal angle sense (Definition 5), we do the following:
Construct E proper f-cover over (Bs, || ||,), where Bg defined in Definition (see below). Since B C Bs, E an also improper & -cover over (B, || Ile).
2. Construct E from & and show that it is proper s-cover over (B, !|r)
3. Show that 8 is proper E-cover over (B, || -I -.l)).
We provide the details in Subsection C.1.
Definition 8. E said be an --cover over the set of Bg {B: ||B|| & /m) in the Frobenius norm sense, if:
MBEss ]A & such that [[ve(()) vec(B)]12
We follow the convention in Telgarsky [2021] that proper cover has to be subset of the ground set, while improper may not satisfy such property.
14

---

After defnnngg the expert set, to use the EWA algorithm, we need to use surrogate expert's cost CN. defined in Equation (3), which is high probability upper-bound of the true cost C, (B) following Lemma 11. To construct Cn. we need to introduce the definition a-covering in Definition 9. Definition 9. A subspace (represented by its orthonormal basis) E Rdxm is said to a- approximately cover vector Φ E IR. | Σ a.
the specific choice of 11 does not affect the validity of this definition e.g.. |B1ي always the same regardless the specific choice of BL, as long as its columns form a orthonormal basis of span (B for any two choices of B1 (denoted by B1,1, B1,2, respectively) there exists orthonormal V (dd-m) (d-m) such that B 1,, B .. Therefore.
Note:
[ [B V B 21.20 2|
The following lemma justifies that all valid choices of B are equivalent up to (d - (d) x (d - m) orthogonal transformation:
Lemma 10. Let W be a k-dimensional subspace of TRd. Let B, B E Rdxk be matrices whose columns form orthonormal basis of W. Then, there exists an orthogonal matrix V E Baxk such that B = BV.
Proof. Since B is a basis of W, there exists some such that B BV. Since VTV ( (BBBVV = (BV) (BV) = BT 1, V is an orthogonal matrix.
Next, we justify the use of Ün as a surrogate cost for the true cost C, in Lemma 11, which requires Remark 2.
Remark 2. By the observation that
0l = BB BI 16 BB 2112
min | O||, 8gspant B))
B a-approximately covers if and only if there exists some 0 in span B) that is a-close to c. As result:
If 0n E span(B) and ||0, - 0. S a. B also a-covers o,.
* If B a-covers 0, and ||0, - 0..ll s B also 2a-covers 0n. Lemma 11. 10,00 - 0n S a, O. is an upper bound of Cn. Equivalently; u(110, - 0,1 s (B) S 1(110, - 0nl S (B)
Proof. Recall that
Cait:
|B 0 < 2a
Cait. Cuise
|| 0x1 S 2a | 0,l > 2a
CB(
(B)
Crise
|B 0,l 2a
First, observe that (B) 2 Case for any Then, we conduct case analysis:
Case 1: || 1 < 2a. In this case, (B) Cait S (B).
Case 2: |B 0,112 2a. In this case, C, (BB Caiss We now show that (B. Caise Indeed,
|B < [B] 03 ||2 [I -0.)l12
< | 0, +
2a < [B] 0. 1|2 +
[| 2a)
a < |
where the first inequality is by triangle inequality; the second inequality is by the definition
of this case and that ||B] (0, 0n) < 110, 0m. <
15

---

In summary, in both cases, (B) S (B).
To ensure that there exists some B E & that can a-cover all 0,, we need to choose by following Lemma 12.
Lemma 12. By choosing S a, there exists some Bg Ed such that, for all a, Be a-approximately covers On.
Proof. For any [N], On E span(B). Hence, 0, PBBn. Thus,
||0n - UU 0n112 UeE
min
[ULU]0l12 min UEE*
min UEEr
| U BB 0nl12
$ min UeE*
||U 1l | BllE| B 1 11
x min UEE
|U] B F
S =0max.
Hence, assuming that 0max S 1, by setting e S a, we have that minrees || - UUT S a.
C.1 The expert set 8 construction and size
First, we construct the surrogate set E proper _ c-vverr over (Bs, || |Ie). Following Erdogdu and Vural [2024], we construct by discretizing the hyper-cube that contains ball & Then |
dm
(dm)) O(dm)) Note that for any B B, ||[p p ||vec( B)]l2 /m; therefore, B C Bs. and thus E is improper --oover of B.
4m
Then, follow a procedure similar to [Telgarsky, 2021, Remark 15.3] to construct as follows:
g = U(b): be :bE
where (b)) == BeB |B - b. In words, Ed is the collections of "nearest neighbors" of E
in B. By the definition of & 8 c B and |8 < E < (m O(dm))
For the rest of the subsection, we will show that our construction of E satisfies Definition 5. Lemma 13.
1. 8 is proper c-cover of (B, (4, () + ||A B).e).
2. E is proper e-cover of (B, (A, B) ||A]] B).
Proof. For the first item, we consider any B B. We would like to show that there exists some element C' in Ee such that ||C B < E.
We find element as follows: first, by definition of E,, there exists element b E & such that
| - bll < 2. We define C = (b). Therefore, ||C - bll < B blи S 2. Thus:
BB Cl S | bllF + ||C b|] S E
Se.
2
Hence, E6 a proper c-cover over (B, ||| llf).
We now prove the second item. suffices to show that, for B B, ||_ BI < ||
Following [Vu, 2020], for semi-orthogonal matrices A, B B, we relate ||AT B||= to the orthogonal
Procrustes problem in [Gower and Dijksterhuis, 2004],
min
||R 2
RE mER R-I.
16

---

With the solution Rº B (B AA AA at the optimum,
| B
sin (o:)
(6 is the canonical angle)
t=1
cos 2 (1hs)
m
S
(2 cos co,) 1)
(cos(d:)2 2cos(1;) - 1)
2m
(b:))
i=1
||R B B|
(See [Vu, 2020])
We have B| S ARR
B S ||- B
D Proof of Lemma 3: Regret of Meta-exploration Tasks
We first restate Lemma 3.
Lemma 3. Fix to be multiple of d. Suppose Algorithm 1 is run on task with the exploration length Ty. Then, there exists some constants C12 C2 (that depend on No, Omaxs Omins and M) such that:
1. The regret on task n is bounded RTT S 61 (1 +
L 77
Confoi
With probability 2 1 - 6, |10, - 0nl 1 C2 dv In
=: a
Proof. For the first item, following (Rusmevichientong and Tsitsiklis, 2010, Lemma 3.4), we have
E [10 - 1/ < co d 77
where co is constant that depends do and M. By [Yang et al., 2020, Lemma 17]. have that max (a- An,z, On) S r - 0z 112 / /I. where An = argmax ( 0,, and =
(M) (M). Thus,
Amen (M) Aa
R
T max (On, a)
Σ (On Ani))
aEA
Σ (On, An.i) + (T - TI) max (fn, a) - Σ (0n, And) aed
Ti max (0n, a) aEA
1=1+1
0 0m 11
S d0 + (T (T- TT)
Omin
J
d²
S Ap0maxTi +
TCU
Omin
TI
The proof of the first item concluded by taking 01 = max(A1 Jcn ) For the second item, recall that u and
and An,,,..., Anm are constructed follows: for each
i [d] and t {u(i - 1) + 1...., .ui. An,t doe
17

---

Since 8, == argming 1 ΣE ((An,,,), 0) -rn,)) by the closed-form solution of ordinary least
squares, we have
On = An) A
where
AT,
A, :=
E R
AT
and In = (fa,1''' " (n,n) Observe that
A An u. 2 ejey uuild.
(6)
Let Th. 10..1...... M...)) We have
0n
(4 An)
1044=~100 -1
(n)
1
Am
1
A (n 7m))
u\
(b)
On
+
with probability at A An.
ux
where both (a) and (b) follow from Eq. (6).
It now suffices to show that |8.
A, 7m
S 2o =0(a)
log(d/8)
least 1 - 5. To this end, observe that by the construction of Ans
Ao Et Bn.t
A Th
Ao EE -441
u+1 77.
Since for each and I, T/,,t is zero-mean and i-sub-Gaussian, by [Lattimore and Szepesvári, 2020, Corollary 5.5], for any i E [d]. we have
Mi Σ
Pr
nutt 2 2u log(2/8)
8
1=
Let = dō' and
Fn = Vi [d].
[(A). S do (2g(2/8))
Then, by the union bound, F, happens with probability at least 1 - 8. Under the event F,.
|| 0xl12 =
A Tr
(AT nT))
V
d
2u log (2d())
uin
log(d/8)
0
dg
T1
and the proof of the second item is complete.
18

---

E Proof of Lemma 4: Regret of Meta-exploitation Tasks
We first restate Lemma 4.
Lemma 4. Fix to be mudtiple of m. Suppose Algorithm 2 is run on lask n with input subspace Br, and the exploration length 72. Then, there exists some constant e (that depends on Xo; Omax, Omin. and M), such that the regret on task is bounded as:
m
+ I n, 8al12 )
R S
T2 T2
Specifically, if [I Onl12 & 2a, then R
I 4c
T2 +
m + +a))) where a is defined in
Lemma 3.
Proof. Similar to the approach in [Rusmevichientong and Tsitsiklis, 2010], define J = Amaua (M)
Vmman (M)
(m) By aYang et al., 2020, Lemma 17], we have maxae (a An,t; S J100, - 1 /110pl1-
Ao
where An, argmax a, 6. Thus,
R
max (0n, a) aEA
Σ (On An,t)
T2
T2 max (O.z a)
Σ
(Bn. An,i) + (5- T2)
max (fn, aEA
Σ
(9n, And))
aEA
1=
B 2m
S T2 + (T-
Omin
To bound the second term, use Lemma 14 (subspace informmd estimation). We have
E Br - 0a1²
m²
+ 1| 1m
1372
It follows that
(m²
R Se T2 TT
+
1 n. 0m113
72
In addition, when || 0,l12 v 2a,
R S Ao0max (T T2)
J m²
+ 4a² 402)
< 4c
mm² T2
(m²²
+ +a² +a²)
Omin
T2
J where max A000max X70min
Benan
We now present Lemma 14 used in the proof above for subspace-informed estimation; see also [Qin
et al., 2022, Lemma 2] and [Yang et al., 2020, Lemma 18].
Lemma 14 (Subspace-informed estimation). Suppose Algorithm 2 is run on task n with the exploration length then EllØ, 0 < m"
x + +I 2.
Proof. Without loss of generality, we assume that 72 multiple of m. Since An,t Br, (i), i e [m], and each action repeats [T2/m] times for t S T2, we have Ee AT, 52 B, BT m
Thus,
Σ B An,AA,,, = T2 B BTB.BBBBB B, 1=1
A2 Im..
19

---

Then, the OLS estimator is given by
1
T2
T2
in
Σ
B An An An
BR An,trn.
72
BR An, A An
BR An, (An, + mm,))
m
Bi An,t (Ap, Bwon + ma,1)
T
12
m
Bi Am. (BrBy + Br BTnL) Bwn +
B An,
T2
t=1
(B, B
Br, B = I)
B Bwn +
m
B An, A n.t Br, B Bwn +
m
B An,t
T2
T2
t=1
BT Bwn +
m
B An
(AT, = 0)
T2
where the first equality uses the flosed-form solution of OLS; the second equality is by the definition of rn,ti and the other equalities follow from algebraic manipulations.
Now, we have
00,
Briin
Bun
T2
Bnn
Bn
B Bwn +
B An,
Bwn
T2
-BBT Bwn Bw
+
Ba BT An,
T2
m:81
For $1, we have
|1 2 = =1 BJ Bwn Bwa.
=I((1 Bn. 1
Bwn Bwn 112
= -BBr, BT Bwn
< || BB,, 112p11 11,,11000 0n.1
< 1 1n11
20

---

For we have
B||s2|1
E
1s2 =
E
m
Bn B An.e
T
m72
E
BB BTT Ams
72 0
m²
Blmmm.111 11
An, B,, BTT An,t
m²
72
Σ
Anie (Id Br..BB..) Ani
(BrBa Br.L I)
T2 A
t=1
m
Bl|mm,ell 112
72
A An.e
(A, = 0)
72 0
t=1
m²
Bl| 11 312
T 1
m?
E |1mm.ll?
T2
m²
(no I-sub-Gaussian noise assumption)
T2
Hence,
0n.12 s [2|[s] [1]
++H |2|1
(Triangle inequality)
m²
<
+ 11 0.11
T2
Proof of lemma 6: Regret of the subspace selection game
Lemma 6. Let = =add= In 7 (with 02 defined in Lemma 3) and n2, where c a constant
in Lemma 13. Then, assuming that t d,, Algorithm 3 chooses a sequence of subspaces (Bn over the expert set E5, defined in Definition 5, such that:
Σ E Cn(,.)] so (NCRs+ Cases log [39 1 (N 12 t
N
(
mm2 + a²) 2 rdm
P
p
Proof. Recall the guarantee of EWA from Freund and Schapire [1997]:
Theorem 15 (Freund and Schapire [1997]). For any sequence of loss vectors ...... lr and the initial weights of the experts are w 1/n for all i E [ni] and y E (0, 1), the EWA algorithm with learning rate rj In(1 7) generates {pr such that its expected loss is bounded by
- -log(1 - 7) (,(i) + Inn
Σ (l..)))
Vi 1...., m.
7
specifically, if at each round we choose is ~ pr.
Σ ((6i)) < In(1 - 7)
T
In
Σ (i)
Vi 1,..,,n.
21

---

Applying Theorem 15 with T N, expert set E", BRs loss functions (B
Ca Le Cast Zu
n E [N], B E & and the baseline expert Be, we get:
Cziza
N
In(1 7)
In |
E
nn Br))
7 E
& (Bx)
7
Using the basic fact that -l((1_2) I + x for x E (0, [ we have that, for E (0, 1..
N
N
log 1891
E
L (Bm)
s (1++))
Σ (B,)
+
?
Define F, = { 0v (Z, = 1A 116, - 0x1 S { and F = = Fn. Then, when all of our es-
timations 0, are accurate, we have: (FF) ",m (B,) = f (B) - Cn) and Bg E 8
Zn Cnat
p
By the definition of Fn, we have: F Z, = 1 - 8,11l > a). Thus, by Lemma 3, P(F() =
P( - f, || > 7, P(,, = 1) S pỘ, and therefore P(F) 2 1- --- P(P.) Np6. Since Algorithm 3 chooses the learning rate for EWA as log(2), thus, 7 = - exp( -1)) = 0.5. we have
ln (Bs) + log |
E
ln (Bn) Σ n=1
En (Ba)
EE
7
1=11
==
log |
E
I(F) Y
(x,) + +I(FF)
(,,
7
log g
I(F)) Σ (n. +
n=1
I(F + log |
<
log log|er
< SN278
(p<D) 1)
< 0logg1/87 (11g.
(8 < 4log |gs N2
and 1/2)
22

---

Then.
en (Bn)
(Be)
s O (89))
N
N en + [((F
n
Ba))
- E
fn (Be)
O |
n=1
n=1
N
R
en (Bx)
- E. [((F))
en (Ba)
s Ollog |
n=1
E
en (Bm)
Ollog +
(p S 1)
Σ
P
Cn((n)
Cast
Zn p
< Ollog |
Cnisa
(N26 s Ollo |E$
Caiss log |
Cn (Bm))
-CCist 50
N
Ca(BB) 50 <0(M0 ONNCstt + Cnisa log _
Thus,
2m
E
Cn (Bn)
E
(Bn)
p
Zn
2 E
(B.) .(F,).
p
Zm
2 E
(n( . ((FI))
(C,(B)I(F.) 2 (,)(((((F)) in Lemma 11)
p
7n
(Br)) - E CB.) I[FF))
Caisa
2 CBBn)) N2
where, for the last inequality, we use the observation that E (Bm [(F.) Cam ( Cum P(FR) & Caissd & Guv, since P(F.) S pd Rz.
Za p
<
Hence,
(n(Bn) 50 NCrit + Caies log E
R=1
N
(Bm)) 0 NCaat + Caise log [
Caise N2
+
x=1
=0 -O(NCat [C + Caise log [
(1 S Ollog ( and 1/ S15
Substituting Caie and Cuise in Equation (2) to complete the proof.
23

---

G Theorem 7: meta-regret guarantee
With exploration probability p min (( (22m//) $ .1). by choosing
Theorem 7.
c In (with defined in Lemma 3), where 8 Nr. TI d min (z) /d]
m LVF the mela-regret of the BOSS algorithm is bounded by:
R, =ONNNT++ND 7 = Ndd + +Tmd)
(5)
Remainder of the Proof of Theorem 7. Recall that in the proof sketch of Theorem 7 (Section 4), we have proved that
R2 s Ō Npri +NT-+ d
rdm + Nr2 + NT m²
TI p
T2
Now, by the choice of 72 m. LVF],
R2 < ò NmvF+ N de
7dm
NNr +
p
We want to tune the parameters p; Ti to minimize the meta-regret subjected to the constraint; p E [0, and Ti E r].
The meta-regret is:
NmvF+ + N & + Npr + Tdm
Rr 5
=
Wmm/+NNd/7D)
Tdm
P + Nd
(Choose = d min
(d / /d
(Choose min (( (2mm/²)
- NOOON N dm + N + rmd)
11
H
Additional experiment result
H.1 Adversarial environment for SeqRepL's 's deterministic exploration schedule
Boo
Figure 2: Comparing the cumulative regret of BOSS and other baselines. The setting is (N, T, d, m) (6000, 2000, 10,3) 3) and ||0,1l2 E [0.8, Yn E [N] chosen uniformly at random from this interval. SeqRepL, BOSS, and coss-no-oracio uses the same hyperparameters environment only reveals new subspace dimension at tasks 501, and 1001, and only reveals the same dimension at Qin et al. [2022]'s deterministic exploration schedule.
400, 72 = 50. The

---

H.2 When the Task Diversity assumption is satisfied
12
Figure 3: Comparing the cumulative regret of BOSS and other baselines. The setting is (N, T, d, m)
(6000, 2000, 10,3) 3) and |00, E [0.8. 1] vn E N SeqRepL, BOSS, and Aoss-no-oracho uses the same hyperparameters Ti 1000, 72 300. The task diversity assumption is satisfied: each 0, is generated by a linear combinations of the columns in B, the subspace spanning 0,, ,00.."00p11 performance of SeqRepL and BOSS is almost identical in the left figure.
20-1. The
25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: See the abstract, the end of Section 1 (and Section 4 and 5 for elaboration) on a summary of the contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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 be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are discussed in Section 4 and Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section 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 on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not 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 to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
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]
26

---

All the necessary assumptions and proof are shown in the main paper and Appendix.
Justification:
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 in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
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)?
Question:
Answer: [Yes]
Justification: We will publish the code in the future, including all the hyper-parameters to reproduce the results in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 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 a specific model and empirical evaluation, it may be necessary either make it 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 appropriate to the research performed.
While NeurlPS 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) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) 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 instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
27

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The code for paper be found https://github... com/
duongnhatthang/Bee BOSS..
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
cetrbbmmsssoooolliiii onPolicy icy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /nips. cc/public//eeecccccccccccccc wtwp/////////eeeeeeeeeeeeseeeeee /toeeS//o/m ietimmsssionn ssionPolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. 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 as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is 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: [Yes]
Justification: The experiment information is provided in Section and the code with all the parameters can be found at https: //gi github..... com/ comm/ddoonhaattt thang/BOSS.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core 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, appendix, 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: This is shown in Section 5, where we provide standard deviation error over five randomized experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
28

---

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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: The experiment is relatively small and simple, and the paper's main focus is the theoretical analysis.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the 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 NeurIPS Code of Ethics https: : //terrip////////.eee/e cc
Answer: [Yes]
Justification:
We have read the NeurIPS Code of Ethics and found violation.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws 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: Our work focus on the theoretical analysis and poses no significant societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
29

---

If the authors answer NA or No, they should explain why their work has no societal impact or 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.
The conference expects that many papers will be foundational research and not tied to 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 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 generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
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. Our dataset synthetic.
Guidelines:
The answer NA means that the paper poses no 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 to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All authors and citations are mentioned, to the best of our knowledge.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
30

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. cww/coo//aaoo/oo datasttss 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. If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We don't provide any assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create 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 as details about compensation (if any)?
Answer: [NA]
Justification: Our work does not involve 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 Ethics, 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: Our work does require IRB Approvals or Equivalent for Research with Human Subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending 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.
31

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS 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.
32


Reviews:
[{"review_id": "5fZVJ0Wxuf", "reviewer": "Reviewer_LLug", "summary": "This paper addresses the problem of representation transfer in a sequential multi-task linear bandit problem. The main objective in the paper is to remove the task diversity assumption made in Qin et al (2022), which places a constraint on any subsequence of tasks observed. The paper proposes an algorithm that for each task performs exploration with a constant probability, and uses the exponential weighted average algorithm to choose the exploration probability over a large set of arm vectors. The paper proves an upper bound on the cumulative regret without making the task diversity assumption and demonstrate the performance in an experiment.", "questions": "* If possible, it would be nice to demonstrate the impact of the task diversity assumption. Specifically, could we construct a simulated environment where the assumption is not met by a significantly large fraction of subsequences, and the performance of BOSS is better than SeqRepL Qin et al (2022) ? Maybe your experiment already demonstrates that but I missed it. Could you clarify?", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* The paper presents the results in an engaging and clear manner and the algorithms proposed are intuitive.\n* Removal of the task diversity assumption appears to be significant advance.", "weaknesses": "* The problem setting emphasizes the sequential nature of the tasks. Specifically, the algorithm needs to collect all samples from $\\theta_1$ task before moving on to $\\theta_2$, i.e., the tasks cannot be interleaved. It would be helpful to outline some situations where this aspect of the problem setup is important.\n* The algorithm needs to know the value of $m, N, \\tau$ to choose the exploration probability. The proposed algorithm performs better than the \"individual task baseline\" only under a specific parameter regimes (see line 242).\n* The theoretically valid size of the set of experts is extremely large for reasonable parameter values (lines 408 and 284). Is that one of the reasons why BOSS only performs better when we have very large number of tasks?\n* There is a gap to the known lower bound, which is suggested to be due to the task diversity assumption not being met.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- ``There is a gap to the known lower bound, which is suggested to be due to the task diversity assumption not being met.''\n\n**Before our work, no regret bounds that are $o(N d \\sqrt{\\tau})$ were known for Sequential representation transfer multi-task linear bandits without Task Diversity assumption**.\n\nIn addition, we don't know if our upper bound can be improved. Even with task diversity, the upper and lower bounds of Qin et al. do not exactly match (see Table 1)\n        \n- ``The theoretically valid size of the set of experts is extremely large for reasonable parameter values, is that one of the reasons why BOSS only performs better when we have very large number of tasks?''\n\n**Yes.** $|\\mathcal{E}^\\epsilon|$ directly affects the $\\frac{\\tau \\ln|\\mathcal{E}^\\epsilon|}{p} = \\tilde{O}( \\frac{\\tau d m } p )$ term in the regret bound, and will subsequently affect the $N^{2/3} \\tau^{2/3} d m^{1/3}$ term in the regret bound.  If we can make this term smaller, we can broaden the parameter regimes when our regret bound is better than the $N d \\sqrt{\\tau}$ baseline. We are also working on a method that is more computationally efficient in the future.\n        \nThe reason why we need large $N$ is explained in the global answer above.\n\n- ``It would be nice to demonstrate the impact of the task diversity assumption''\n        \n$=>$ Our experiments in the submission are designed without the Task Diversity assumption, as shown in the caption of Fig 1 (a new dimension of the underlying subspace $B$ is revealed at tasks 1, 2500, and 3500). We also add some extra experiment results to highlight how BOSS outperforms SeqRepL when the parameters length is larger ($0.8 \\leq \\|\\theta_n\\|_2 \\leq 1$) in the attached PDF file of the global answer. Furthermore, we also add another set of experiments when the Task Diversity assumption is satisfied, where SeqRepL outperforms BOSS as expected. \n        \nThe first figure is the experiment results without the Task Diversity assumption and the second is with Task Diversity. Different from the main paper, we ensure that $0.8 \\leq \\|\\theta_n\\|_2 \\leq 1$ highlights how badly SeqRepL performs when the Task Diversity assumption is violated. We also made some small changes to the hyper-parameters, as shown in the figures' captions.", "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": "aTkCyUfzfP", "reviewer": "Reviewer_9RaC", "summary": "The paper proposes a strategy for the multi task linear bandit problem, where the tasks are assumed to share a low rank representation, which is ought to be learnt via a new meta learning strategy, where meta exploration and exploitation needs to be balanced. The low rank representation is learnt via optimizing a newly constructed loss function over an epsilon-net. The tasks appear sequentially to the learner and the authors explicitly do not make any assumption on the task diversity of their setting.\nThe authors provide a meta regret bound for their algorithms and synthetic data results.", "questions": "In Figure 1a) it looks like the Boss algorithm performs worse after a new dimension for the subspace is incremented at n= 2501, does that mean that the dimension of the subspace was falsely estimated?\n\nat n=1 the the low rank should be estimated as m=1 as well, which makes it hard to minimize $B^T_{n+1,\\perp}\\theta_{n+1}$, (Since the n+1th task parameter might be outside the subspace selected for the first n tasks), Intuitively, the algorithm should work best if at least m task parameters are already bias-less estimated for a m-dimensional low rank structure. Could you explain how you mitigate this issue?\n\nShouldn't a bound on the term $||B_{\\perp}-\\hat{B}_{n+1,\\perp}||$ or a term that showcases the estimation error on the representation,  appear in the final regret?\n\nDoes p need to be constant? after enough tasks explored, p could gradually vanish. I see in the final bound that $p \\sim 1/\\sqrt[3]{N^2}$, which is still constant.", "limitations": "Aside from the assumptions on their setting made, I did not see any limitations explicitly addressed.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is well written and easy to follow\n\nOriginal idea for solving the multi-task/meta learning setting with low rank representation\n\nThe assumption on the action set is weaker than in comparable works (constant action set vs iid action set)", "weaknesses": "The EWA algorithm for the meta learning procedure should not just be referenced but actually appear in the paper (or at least in the supplementary)\n\nThe presentation of the actual meta learning could be made clearer. For that matter, definition 7 and 8 should be moved to the main paper so it becomes clearer what the uniform distributions D_n are supposed to be.\n\nThe experiments would benefit if there were another baseline to compare to (Cella et al or Bilaj et al as they appear in the related work section)\n\nThe plot labels of figure 1 b) and c) should have latex style writing", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- ``Shouldn’t a bound on the term $||B_{\\perp} -\\hat{B}_{n+1,\\perp}||$ or a term that showcases the estimation error on the representation, appear in the final regret?''\n\n**Yes.** Indeed, our regret bound has an implicit dependence on $|| \\hat{B}_{n, \\perp}^T \\theta_n ||$ - see Eq. (2). \n\nThis is a key quantity like the $||B_{\\perp} -\\hat{B}_{n+1,\\perp}||$ you mentioned. \n        \n- ``At n=1 the the low rank should be estimated as m=1 as well, which makes it hard to minimize $||B^T_{n+1,\\perp} \\theta_{n+1}||$ , (Since the n+1th task parameter might be outside the subspace selected for the first n tasks), Intuitively, the algorithm should work best if at least m task parameters are already bias-less estimated for a m-dimensional low rank structure. Could you explain how you mitigate this issue?''\n\n$=>$ If we understand correctly, the reviewer was referring to that the algorithm needs to overcome additional challenges without the task diversity assumption. Without task diversity, we cannot hope to obtain estimate $\\hat{B}_n$'s that converge to the underlying $B$. Instead, we use online learning with randomized meta-exploration (using the learned $\\hat{\\theta}_n$'s to estimate the underlying representation $B$) to ensure that our learned $\\hat{B}_n$'s can capture $\\theta_n$'s for \\emph{most} task $n$, in an average sense.\n\n- ``In Figure 1a) it looks like the Boss algorithm performs worse after a new dimension for the subspace is incremented at n= 2501, does that mean that the dimension of the subspace was falsely estimated?''\n\n$=>$ Our estimator $\\hat{B}_n$ is always in $\\mathbb{R}^{d \\times m}$, so the subspace dimension estimate is always $m$. If the reviewer meant ``the newly revealed direction of the subspace was falsely estimated'', we agree. \n        \nBOSS uses the estimated $\\hat{B}$ to efficiently estimate $\\hat{\\theta}_n$. When a new dimension is revealed at n=2501, it takes a while for BOSS to have an accurate estimation $\\hat{B}_n$ with respect to $B_n$, the subspace spanned by all $\\{\\theta_i: i=1,..,n\\}$ shown so far. Fig 1b and 1c show that if the expert set covers the underlying $B$ (green plot), BOSS can adapt and learn very fast.\n\n- ``The presentation of the actual meta learning could be made clearer. The EWA algorithm for the meta learning procedure should not just be referenced but actually appear in the paper''\n        \n$=>$ Thank you for your suggestion. We will include the full EWA algorithm in the appendix 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": "Hkc4nq2AEO", "reviewer": "Reviewer_vp1F", "summary": "The paper studies lifelong learning in linear bandits and designs a two-level algorithm with provable low regret without task diversity assumptions. The paper assumes the tasks share a low-rank representation and provides a regret upper bound.", "questions": "1) In line 109, for a matrix $U$, isn't $U_{\\perp}$ not unique? This should be defined as a set or stated as one of the matrices.\n2) The Assumption 2 is stated as linear bandits. I didn't get the reason for this title.\n3) In line 3 in Algorithm 1, it should be $\\mu=\\frac{\\tau_1}{d}$\n4) The statement in Lemma 4 seems problematic. As stated in 1), the matrix $\\hat B_{n,\\perp}$ is not unique, hence the RHS is a matrix-dependent bound. Thus, the condition $||\\hat B_{n,\\perp} \\theta_{n}||_2\\leq 2\\alpha$ is also dependent on the choice of the matrix. This discussion is missing in the paper. This will also affect the definitions in (2) and (3), and the following results.\n5) In line 173, the definition of the expert set $\\mathcal{E}^{\\epsilon}$ is in the Appendix, which makes the paper not self-contained.\n6) What does the EWA algorithm do in Algorithm 3? Which part of the results is directly from the EWA algorithm?\n7) Overall, the paper provides the regret bounds of order  $\\tilde{\\mathcal{O}} (N m\\sqrt{\\tau} + N^{\\frac{3}{2}} \\tau^{\\frac{2}{3}} d m^{\\frac{1}{3}} + \\tau m d)$ in equation (5),  times of interactions. Compared to the baseline, which is $\\tilde{\\mathcal{O}} (N d \\sqrt{\\tau})$, I didn't see a clear improvement in the regret/ Firstly, the regret scales linear with $\\tau$ when fix $N$, which is known to be suboptimal in linear bandit. At least some truncation can be done in the first $md$ tasks to get rid of the linear term. This term cannot be hidden from the abstract from my point of view. Secondly, to achieve similar upper bounds, one needs $N\\geq md$ and $d^2\\leq\\tau\\leq (\\frac{N}{m})^2$, which means the algorithm can only learn for a finite time and the tightness discussion is missing the paragraph Comparison with lower bounds with only a conjecture.\n7) The author answer Yes to the Question about Open access to data and code in the Checklist, but the code is not released during the submission. And I am curious how Figure 1B is generated.\n9) The labels on the y-axis in the figures need to be fixed.", "limitations": "The regret upper bounds has a hugh gap to the lower bound.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper uses a two-level approach to solve this problem, which is novel. A theoretical guarantee is given with numerical experiments performed.", "weaknesses": "There are some statements in the theorems that seem wrong and the upper bound provided does not seems tight. See Questions for details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- ``In line 109, for a matrix $U$ , isn’t $U_{\\perp}$ not unique? This should be defined as a set or stated as one of the matrices.''\n\n**We thank the reviewer for pointing out this impreciseness.** Indeed, the choice of $U_\\perp$ is not unique according to our writing in the submitted version. \n        \nTo make the definition well-defined, it suffices to fix any orthonormal basis $U_\\perp$; one may break ties in dictionary order. We will clarify this in the final version of the paper.\n        \nIndeed, the specific choice of $U_\\perp$ does not affect the correctness of our proof -- e.g., $ \\| \\hat{B}_{n, \\perp} \\theta_n \\|_2$ are always the same regardless \n\nof the specific choice of $\\hat{B}_{n, \\perp}$, as long as its columns form a orthonormal basis of $\\text{span}(\\hat{B}_n)^\\perp$: \n\nFor any two choices of $\\hat{B}_{n, \\perp}$ \n\n(denoted by $\\hat{B}_{\\perp, 1}$, \n\n$\\hat{B}_{\\perp, 2}$, respectively) \n\nthere exists orthonormal $V \\in \\mathbb{R}^{{(d-m) \\times (d-m)}}$ such that \n\n$\\hat{B}_{\\perp, 1}$\n\n$ = \\hat{B}_{\\perp, 2} V$. \n\nTherefore, \n\n$\\|\\hat{B}_{\\perp, 1}^{\\top} \\theta_n\\|_2$ \n\n$= \\|V^{\\top}\\hat{B}_{\\perp, 2}^{\\top} \\theta_n\\|_2$\n\n$ = \\|\\hat{B}_{\\perp, 2}^{\\top} \\theta_n\\|_2$\n\nTo show that all valid choices of $\\hat{B}_{n, \\perp}$  are equivalent up to a $(d-m) \\times (d-m)$ orthogonal transformation, we have:\n        \nLet $W$ be a $k$-dimensional subspace of $\\mathbb{R}^d$. Let $B, \\hat{B} \\in \\mathbb{R}^{d \\times k}$ be matrices whose columns form an orthonormal basis of $W$. Then, there exists an orthogonal matrix $V \\in \\mathbb{R}^{k \\times k}$ such that $\\hat{B} = B V$.\n\n**Proof:** Since $B$ is a basis of $W$, there exists some $V$ such that $\\hat{B} = BV$. Since $V^\\top V = V^\\top (B^\\top B) V = (BV)^\\top (BV) = \\hat{B}^\\top \\hat{B} = I$, $V$ is an orthogonal matrix.\n\n\n        \n- ``The statement in Lemma 4 seems problematic. As stated in 1), the matrix $\\hat{B}_{n,\\perp}$ is not unique, hence the RHS is a matrix-dependent bound. \n\nThus, the condition $||\\hat{B}_{n,\\perp} \\theta_n||_2 \\leq 2 \\alpha$ is also dependent on the choice of the matrix. This discussion is missing in the paper. This will also affect the definitions in (2) and (3), and the following results.''\n        \n        \n$=>$ As we mention in our previous item, the value of $|| \\hat{B}_{n, \\perp}^\\top \\theta_n ||$ is invariant to the specific choice of matrix \n\n$\\hat{B}_{n, \\perp}$. Still, we agree that this can be made clearer in the main paper, so we will make the necessary edits in the final version. \n        \n- ``What does the EWA algorithm do in Algorithm 3? Which part of the results is directly from the EWA algorithm?''\n\n$=>$ The algorithm uses Exponentially Weighted Algorithm (EWA) in line 8 of Algorithm 3. The intuition of using EWA is to choose subspaces $\\hat{B}_n$ online such that their linear spans capture $\\theta_n$'s over tasks $n=1,..., N$. The idea is to use the feedback from the meta-exploration tasks to update the weights of all possible experts from the expert set. Since this expert set $\\alpha$-cover the true $B$, the EWA guarantee would ensure that BOSS would efficiently learn the closest expert to the true $B$ while maintaining the correct uncertainty over all possible experts when the subspace dimensions are not fully revealed, thus, neatly dealing with the non-Task Diversity setting.\n\nSpecifically speaking, the EWA's guarantee is used in the proof of Lemma 5, line 455. We will provide a full description of the algorithm with weight updates in the Appendix in the final version.\n        \n- ``Overall, the paper provides the regret bounds of order  $\\tilde{O} (N m\\sqrt{\\tau} + N^{3/2} \\tau^{2/3} dm^{1/3} + \\tau md)$ in equation (5), times of interactions. Compared to the baseline, which is  $\\tilde{O}(N d\\sqrt{\\tau} )$, I didn’t see a clear improvement in the regret. ... the regret scales linear with when fix N, which is known to be suboptimal in linear bandit. At least some truncation can be done in the first tasks to get rid of the linear term. This term cannot be hidden from the abstract from my point of view''\n\n**We agree that the $\\tau m d$ term cannot be ignored and will add it to the abstract.** Note that we are studying the multi-task problem; thus, the interesting regime is when the number of tasks $N$ is large enough to allow useful transfer learning across tasks. The $\\tau md$ part of the regret can be understood as the learner ``sacrifices'' a small number of tasks to learn transferable knowledge. This last term is of lower order than $N^{2/3} \\tau^{2/3} d m^{1/3}$ when $\\tau \\ll (\\frac{N}{m})^2$.\n\n- ``The definition of the expert set $\\mathcal{E}^{\\varepsilon}$ is in the Appendix, which makes the paper not self-contained''\n\n**We agree.** At first, we moved these definitions to the appendix to not distract the reader. We realized that they may be required for the main paper to be self-contained, so we will make the necessary edits.\n\n- ``... the code is not released during the submission. And I am curious how Figure 1B is generated.''\n        \n**Correct**. We want to add some additional experiment results. The code is in https://anonymous.4open.science/r/Serena-C5F1.\n\nFor Fig 1b, since we use a simulated environment, we have access to the $B_n$, the subspace spanned by  $\\left ( \\theta_i \\right )_{i=1}^n$ thus far and the estimated subspace $\\hat{B}_n$ of the learners for each task. Thus, we plot this figure on this information.\n        \n- ``The Assumption 2 is stated as linear bandits. I didn’t get the reason for this title.''\n\n$=>$ We will change it to ``linear bandits with ellipsoid action sets'' 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": "DhEHZbImNH", "reviewer": "Reviewer_u72q", "summary": "This paper extends the existing work on multi-task linear bandits where the task parameters lie in a low rank subspace. Specifically, this paper assumes $N$ $d$-dimensional linear bandits with parameters lie in an $m$-dimensional subspace. For such a setting, the classical approaches yield a regret linear in $N$ and $d$. This paper then proposed a new algorithm that improves the regret with mild assumptions of well-conditioned ellipsoids of the tasks and bounded task parameters. The algorithm is based on a reduction to a bandit online subspace selection problem. The key idea of the proposed approach is bi-level. At the lower level, the algorithm performs either an meta-exploration algorithm or a meta-exploitation algorithm for each of the tasks. At the upper level, the learner either chooses exploration/exploitation or chooses a subspace to use for exploitation. The effectiveness of the proposed algorithm is verified empirically on synthetic adversarial settings.", "questions": "Please see weaknesses.\n\n\nAlso, I am curious about the following:\n\n1. This paper assumes knowledge to a few hyper-parameters. Among these, I wonder whether the assumption on the prior knowledge of the $\\tau$ parameter can be relaxed with certain adaptive design. Could the author elaborate on why knowledge is necessary for the current algorithm to work?\n\n2. Is there a corollary or simple extension that can readily extend the current result to the parallel setting?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "**Significance**: This paper proposed a new algorithm for multi-task linear bandit with provable low regret without making strong assumptions on task parameters. The sequential setting studied is more challenging than parallel settings due to the slow revelation of the underlining subspace. Compared with a few related existing works, this paper does not need assumptions such as task diversity.\n\n**Quality**: this paper is in general good quality. The algorithm is well described.\nThe theoretical part of the work is clearly formulated. Thought the experiments are synthetic, the result still verifies the effectiveness of the proposed algorithm.\n\n**Clearity**: The design of the algorithm and intuition behind the design is clearly explained.", "weaknesses": "There is no major weakness in the paper. I do have some questions regarding the following:\n\n**1**. This paper assumes knowledge of the parameters corresponding to the task number, the dimension, and the number of rounds, which is not ideal. \n\n**2**. [Originality] The algorithmic design and the guarantee is closely related to a a few works, including the PEGE by [Rusmevichientong and Tsitsiklis 2010] (related to lemma 3 in this paper), the analysis in Yang et al [2020] (related to lemma 4), EWA algorithm (related to lemma 5). Therefore, the technical novelty of the proposed algorithm and analysis is not very obvious to me.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Originality: The algorithmic design and the guarantee is closely related to a a few works, including the PEGE by [Rusmevichientong and Tsitsiklis 2010] (related to lemma 3 in this paper), the analysis in Yang et al [2020] (related to lemma 4), EWA algorithm (related to lemma 5). Therefore, the technical novelty of the proposed algorithm and analysis is not very obvious to me.\n\n$=>$ As discussed in the Introduction and Table 1, Table 2, our work fills the gap of the sequential representation transfer for linear bandit, without the Task Diversity assumption. Before our work, no algorithms could provably beat the naive individual single-task baseline. The absence of task diversity assumption makes meta-learning the task representation matrix $B$ nontrivial. \n\nOur proposal designs a bi-level approach for this problem and shows that, under mild assumptions, we can efficiently learn the underlying subspace in an online sense and maintain the correct uncertainty over possible experts when the environment acts adversarially (i.e. not revealing the full underlying subspace till the end). We believe our reduction to online subspace selection is new to sequential representation transfer and may benefit other meta-learning applications such as in RL or supervised learning.", "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:
We thank the reviewers for their insightful feedback. 
    
In this work, we introduce the first provable representation transfer algorithm for sequential linear bandits without relying on the task diversity assumption. Unlike in parallel settings or sequential settings that assume task diversity, the learner now has to address the $\textit{unique challenges}$ in meta-exploration, which involves carefully deciding when to acquire more information on the low-dimensional representation.
    
We are encouraged that the reviewers found our work clear (R1, R2, R4), intuitive (R1, R4), and novel (R2, R3). 
We are also glad that the reviewers recognized the significance of removing the task diversity assumption (R1, R2, R4) in exchange for some mild assumptions (R2) within the more challenging sequential setting (R4).

In addition, our theoretical guarantee and experiment are also appreciated (R1, R3, R4). We address some common questions below and the specific questions in each reviewer's section. 

- ``The proposed algorithm performs better than the ”individual task baseline” only under a specific parameter regimes (R1, R4), $N \geq md$ and $d^2 \leq \tau \leq (N/m)^2$, which means the algorithm can only learn for a finite time (R3). [Does] BOSS only performs better [than the individual single-task baseline] when we have very large number of tasks? (R1)''

$ \textbf{We wish to point out that our work gives the first nontrivial result towards sequential multi-task linear bandit without task diversity assumption.}$
Before our work, no regret bounds better than individual single-task baseline (i.e. $o(N d \sqrt{\tau})$) were known for this setting.

Our main motivation for this paper was to show that sequential representation transfer is indeed possible without the task diversity assumption. Proving this opens the floodgates for developing more sample-efficient algorithms.
        
We can rephrase the parameter regime where our regret bound is better than the individual single-task baseline as:
$\tau \gg d^2$ and $N \gg m \sqrt{\tau}$. So, indeed, BOSS performs better when $N$ is large. As mentioned in the paper, we think that broadening the parameter regime for improvement is an important problem.

If we interpret R3's concern correctly, $\tau$ being capped at $(N/m)^2$ is a limitation of our paper. We agree -- this is due to the existence of the burn-in term $\tau m d$ (when $\tau > (N/m)^2$, this is greater than $N d \sqrt{\tau}$). Removing this burn-in term is an interesting open problem. 
        
- ``The algorithm needs to know the value of $m, d, N, \tau$. Can this be avoided?'' (R1, R4)

$\textbf{Maybe}$. The requirement for knowledge of $m$ can be relaxed to knowing an upper bound of $m$. Removing this knowledge requires a change of approach, such as low-rank matrix optimization, as in Cella et al. 2023 or additional assumption, as in Bilaj et al. 2024. Cella et al. 2023 is in the parallel setting, which is not applicable here, and Bilaj et al. 2024's guarantee can be as large as $O(Nd\sqrt{\tau})$ as discussed in line 91.

The requirement for $\tau$ and $d$ is not too bad since the action space is given to us ahead of time, so $d$ is known, and $\tau$ can be known after finishing the first task. 

Using an adaptive design to not be dependent on $N$ is likely to be possible with the doubling-trick. The details are in the next question.
        
- ``Can we use an adaptive design (R4)? Can $p$ gradually vanishes (R2)?''

$\textbf{Yes}$. We think achieving adaptivity in $N$ can be done using a doubling trick.

Specifically, in phase $i$, run our algorithm with the assumption that there are $2^i$ total tasks in this phase. The modified algorithm has a meta-regret guarantee that is within a constant of the algorithm that knows $N$. This implicitly gives an adaptive setting of meta-exploration probability $p$ that is decaying over time. 
        
- ``Can our results translated to the interleaved (R1) or Parallel (R4) setting?'' 
        
$=>$ Our algorithm is designed to tackle the unique challenges in sequential transfer without the task diversity assumption, and so applying it to the parallel setting would result in losing the intended benefits.

We don't think that our result can be easily adapted to the parallel setting and achieve a better guarantee than Hu et al. 2021. 

The interleaved setting can be seen as a unified model for both the Sequential and Parallel settings. Since these two are fundamentally different, investigating the interleaved setting is left for future work.
        
- ``The labels on the y-axis in the figures need to be fixed (R2, R3)''
        
$\textbf{Yes.}$ We will correct it as you suggest.

Meta-review: This paper addresses the problem of representation transfer in a sequential multi-task linear bandit problem. The main objective in the paper is to remove the task diversity assumption made in Qin et al (2022), which places a constraint on any subsequence of tasks observed. The paper proposes an algorithm that for each task performs exploration with a constant probability, and uses the exponential weighted average algorithm to choose the exploration probability over a large set of arm vectors. The paper proves an upper bound on the cumulative regret without making the task diversity assumption and demonstrate the performance in an experiment.

All reviewers believe this paper is above the bar of acceptance. The AC agrees and recommends acceptance.
Decision: Accept (poster)