Beyond task diversity: provable representation transfer for sequential multitask linear bandits

Authors: thang  duong
zhi  wang
chicheng  zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 08:37:14

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.

Main paper: 
 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 as 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 a 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 to 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 a problem where the learner sequentially faces N d-dimensional linear bandit tasks, each with horizon τ , with a key assumption that the reward predictors of the N tasks, θ 1 , . . . , θ N , lie in an m-dimensional linear subspace of R d . The goal of the learner is 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.One naive approach is to solve each task independently using a base algorithm (such as Lin-UCB [Abbasi-Yadkori et al., 2011] 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 d √ τ ). 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 Õ(N m √ τ ). 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 meta-exploration: 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 near-optimal regret through a reduction to low-rank linear bandits [Hu et 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 Õ N m √ τ + dm √ τ N . However, it relies on an additional key assumption that the tasks are "diverse" in the m-dimensional subspace: more formally, for any subsequence of tasks S, the m-th eigenvalue of the task parameters' covariance matrix Our algorithm, BOSS, is based on a reduction to a bandit online subspace selection problem. Specifically, for each new task n, our algorithm chooses a subspace, represented by its canonical orthonormal basis Bn , to approximate the ground-truth subspace B and guide exploration. To address the challenge of meta-exploration, as choosing different Bn 's leads to learning the projections of θ n onto 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 a simulated adversarial environment where the task diversity assumption does not hold.Parallel representation transfer for multi-task linear bandit. The parallel 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 √ mτ + √ mdτ N and an algorithm that matches this up to logarithmic factors. For the infinite action setting, they provide a lower bound for the problem of Ω N m √ τ + d √ mτ N , which holds even under the task diversity assumption. Under the same task diversity assumption and in the infinite action set setting2 , Yang et al. [2022] For general action spaces, Hu et al. [2021] provide a regret guarantee of Õ N √ mdτ + d √ τ N m , 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 to know the subspace rank m and the need for the task diversity assumption. Assuming that the action sets are finite and drawn from a specific distribution, by using trace-norm regularization for estimating task parameters and taking actions in a greedy fashion, they provide a regret upper bound of Õ N √ mτ + √ dmτ N 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 one task at a 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 a task diversity assumption, i.e., any large enough subset of tasks span the underlying m-dimensional subspace in a well-conditioned manner. With this, they provide a meta-regret guaranteeÕ N m √ τ + dm √ τ Nwhich nearly matches a lower bound of Ω N m √ τ + d √ mτ N . They also extend their analysis to a 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 ∥θ n ∥ = 1 for all tasks; however, it appears that there may be a non-trivial oversight in the analysis. 3 Bilaj et al. [2024] study a related setting where the task parameters are i.i.d. sampled from a distribution with high variances from a m-dimensional subspace and with low variances in the orthogonal directions. They provide a meta-regret guarantee of at leastÕ N √ τ (d -m) log 1 + m λ A min (d-m), where λ A min 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; λ A min may be constant when the action space is fixed. Thus, this bound can be as large as Õ(N d √ τ ). For a quick reference, see Table 1 for a comparison between our work and most related works. See also Appendix A for further discussions on related work. 
problem setup: 
 We consider a sequence of linear bandit tasks of the same length τ , described by the task parameters θ 1 , • • • , θ N ∈ R d chosen by an environment such that they satisfy Assumption 1. The learner solves N tasks sequentially. In task n, for each time step t = 1, . . . , τ , the learner chooses an action A n,t from the action set A that satisfies Assumption 2 and receives a reward r n,t = A ⊤ n,t θ n + η n,t , where η n,t is independent, mean-zero 1-sub-Gaussian noise. The learner then moves on to task n + 1 and repeats the same learning process.Algorithm 1 Meta-Exploration procedure 1: Input: Task index n, exploration length τ 1 (a multiple of d) 2: for i ∈ [d] do 3: Let A n,t = λ 0 e i for t = u(i -1) + 1, • • • ,, . . . , w N ∈ R m , such that θ i = Bw i for all i ∈ [N ].Given a semi-orthonormal matrix U ∈ R d×m (i.e., U ⊤ U = I m ), denote by U ⊥ ∈ R d×(d-m) a matrix whose columns constitute an orthonormal basis of the orthogonal complement of span(U ), where we break ties in dictionary order4 . We also denote the i-th column vector of U by U (i).Following Rusmevichientong and Tsitsiklis [2010] and [Qin et al., 2022] , we also assume that the action set A is an ellipsoid and the task parameters have bounded ℓ 2 norms: Assumption 2 (Linear bandits with ellipsoid action sets). The action set A :=x ∈ R d : x ⊤ M -1 x ≤ 1 is an ellipsoid, where M is a symmetric, positive definite matrix. In addition, there exist constants θ min and θ max such that for all tasks n ∈[N ], θ min ≤ ∥θ n ∥ 2 ≤ θ max .We define the expected pseudo-regret for task n asR n τ := max a∈A E τ t=1 a ⊤ θ n - τ t=1 A ⊤ n,tθ n , and the meta-regret for all N tasks asEQUATIONThe learner's goal is to sequentially interact with each task in a way that minimizes its meta-regret.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: The limitations are discussed in Section 4 and Section 6 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 in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
algorithm: 
 Unlike in 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 a 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 fulldimensional linear bandit algorithm (PEGE [Rusmevichientong and Tsitsiklis, 2010] , Algorithm 1); the other tries to incorporate a learned subspace B as prior knowledge to get reduced regret (Algorithm 2). Algorithm 1 and 2 can be viewed as performing meta-exploration and meta-exploitation respectively: Algorithm 1, while ignoring the low-dimension property of the tasks, produces unbiased estimators of θ n that helps learn the task subspace B; Algorithm 2 allows the learner to achieve a much lower regret when the subspace B approximately contains θ n ; however, using it may slow down the learning of B. Take action A n,t ← arg max a∈A a, θn 12: end for• At the upper level, the learner has two decisions to make for each task n: (1) choosing between meta-exploration and meta-exploitation;(2) choosing a subspace Bn to use if performing metaexploitation. To this end, we propose Algorithm 3, which aims at making these decisions in a feedback-driven way to ensure low meta-regret.We now elaborate on each level in more detail.The lower level. As mentioned above, Algorithm 1 is for meta-exploration. When invoked in task n, it can achieve two goals simultaneously: obtaining an unbiased estimate of θ n , while maintaining a reasonable regret guarantee for task n. For the first τ 1 steps (line 3 to 6), the learner takes actions {λ 0 e i } d i=1 that span the action space A, where e i is the i-th canonical vector of R d and λ 0 = λ min (M ) is a constant factor that ensures λ 0 e i ∈ A (recall Assumption 2).Then, the learner estimates task parameter θn in line 8 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 τ 1 to be a multiple of d. Suppose Algorithm 1 is run on task n with the exploration length τ 1 . Then, there exists some constant c 1 , c 2 > 0 (that depends on λ 0 , θ max , θ min , and M ) such that:1. The regret on task n is bounded asR n τ ≤ c 1 • τ 1 + τ • d 2 τ1 =: C info ; 2. With probability 1 -δ, it returns θn such that ∥ θn -θ n ∥ ≤ c 2 • d ln d δ τ1 =: α.We defer the proof of this lemma to Appendix E. Lemma 3 reveals a tradeoff between meta-exploration and regret minimization for task n: if τ 1 is larger (say, closer to τ ), θn estimates θ n more accurately; however, this may yield a worse bound on R n τ . On the other hand, Algorithm 2 is for meta-exploitation. It takes a subspace (represented by its orthonormal basis B) as input, and when invoked in task n, it can achieve a lower regret guarantee than Algorithm 1 when the subspace contains vectors that closely approximate θ n . Instead of exploring R d , the learner only explores the subspace induced by Bn (lines 3 and 6). Then, the learner estimates the low-dimensional task parameter ŵn in line 9 and acts greedily for the rest of the task (line 11). We summarize its guarantee (originally due to Yang et al. [2020] ) as follows: Lemma 4. Fixed τ 2 to be a multiple of m. Suppose Algorithm 2 is run on task n with input subspace Bn and the exploration length τ 2 . Then, there exists some constant c > 0 (that depends on λ 0 , θ max , θ min , and M ), such that the regret on task n is bounded as:R n τ ≤ c • τ 2 + τ • m 2 τ 2 + ∥ B⊤ n,⊥ θ n ∥ 2 2 .Algorithm 3 BOSS: Bandit Online Subspace Selection for Sequential Multitask Linear Bandits. The full algorithm 4 is in Appendix A.1: Input: Task length τ , number of task N , task dimension d, subspace dimension m, and exploration rate p. end if 12: end forSpecifically, if ∥ B⊤ n,⊥ θ n ∥ 2 ≤ 2α, then R n τ ≤ c τ 2 + τ • m 2 τ2 + α 2 .Lemma 4 reveals the opportunistic nature of Algorithm 2: if θ n is perfectly contained in the subspace spanned by B, ∥ B⊤ ⊥ θ n ∥ = 0 and the regret bound isR n τ ≤ O τ 2 + τ • m 2 τ2, which can be as low as O(m √ τ ); on the other extreme, ∥ B⊤ ⊥ θ n ∥ can be as large as ∥θ n ∥ in the worst case, which yields a trivial linear regret bound. Thus, its regret guarantee hinges on good choices of subspace B as input.The upper level. For the upper level, we propose Algorithm 3 that decides (1) when to perform meta-exploration and (2) the subspace to 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 Bn (line 12).For (2), we propose to choose Bn N n=1 that can optimize the following cost function online5 :C n (B) := C hit := τ 2 + τ • m 2 τ2 + α 2 ∥B ⊤ ⊥ θ n ∥ 2 ≤ 2α C miss := τ otherwise (2)The motivation behind this definition of C n is as follows: according to Lemma 4, C n ( Bn ) is (up to constant) an upper bound of the regret of the learner at task n, were the learner to invoke Algorithm 2 using Bn for this task. Therefore, if we can guarantee N n=1 C n ( Bn ) to be small, then using Algorithm 2 for all tasks yields a small meta-regret.An immediate challenge in directly optimizing C n defined in Eq. ( 2) is its dependence on unobserved quantity θ n . This challenge is further complicated by the following: (i) at best, we observe θn 's that are α-approximations of θ n (e.g. in those meta-exploration tasks, see Lemma 3); (ii) in metaexploitation tasks, we do not have guarantees on how close θn is to θ n .To address the challenge (i), we propose to optimize the following surrogate cost function for C n :Cn (B) := C hit ∥B ⊤ ⊥ θn ∥ ≤ α C miss otherwise (3)In Lemma 11, we show that, with high probability, Cn is an upper bound of C n .With this modification of the optimization objective, challenge (ii) persists: Cn is not a valid upper bound of C n for all rounds n; to ensure this upper bound property, we propose to optimize the cost:EQUATIONwhere we introduce the importance weighting multiplier Zn p . Our key observation is that, although Cn (B) is no longer an upper bound of C n (B), the upper bound property holds in-expectation; to see this, observe that for any fixed B,E Zn Cn (B) = E Zn Cn (B) • Z n p ≳ E Zn C n (B) • Z n p = C n (B),here, the first equality is from the definition of Cn (B); the inequality (here, ≳ indicates greater than up to a negligible constant) uses the property that when Z n = 1, with high probability, Cn (B) ≥ C n (B); the second equality is from the fact that Z n ∼ Ber(p).Following the online learning literature, we propose to use the Exponential Weight Algorithm (EWA) Freund and Schapire [1997] to optimize Cn (B) online. Ideally, we would like to run EWA with the B = B : B ∈ R d×m s.t. B ⊤ B = I m , the set of all m-dimensional subspaces; however, this is impossible because |B| is infinite. So instead, we propose to run EWA with the expert set defined as an ε-cover of B: Definition 5. E ε is said to be a ε-cover over the set of B in the principal angle sense , if:∀ B ∈ B, ∃B ′ ∈ E ε such that ∥B ⊤ ⊥ B ′ ∥ F ≤ ε.Definition 5 is motivated by the well-known fact that ∥B ⊤ ⊥ B ′ ∥ F is the Frobenius norm of the sine of the principal angle matrix between subspaces spanned by B and B ′ . In Appendix C we show that there is a construction of E ε of size O ( √ dm/ε) dm . In subsequent discussions, we will assume that BOSS uses such a E ε . Define a constant shift and scaling of Cn , ℓ n (B) := p Cmiss Cn (B) -C hit Zn p ; we note that any regret guarantee over sequence {ℓ n } immediately translates to a regret guarantee over sequence Cn . By the construction of the expert set E ε , sequence {ℓ n } is realizable with high probability:there exists someB ε ∈ E ε such that N n=1 ℓ n (B ε ) = 0;this allows EWA to achieve a constant regret guarantee, summarized as follows:Lemma 6. Let ε = α = c 2 d ln d δ τ1 (with c 2 defined in Lemma 3) and δ ∈ [0, 1] be a constant such that N 2 cdm δ + 1 2 ln ln d δ ≤ ln m √ τ 1, where c is a constant in Lemma 13.Then, Algorithm 3 chooses a sequence of subspaces Bn over the expert set E ε , defined in Definition 5, such that:N n=1 E C n ( Bn ) ≤ O N C hit + C miss log |E ε | p = Õ N τ 2 + τ • m 2 τ 2 + α 2 + τ dm p .Note that the cumulative cost bound of Bn has two terms: the benchmark term N C hit and theregret bound term C miss log |E ε | p. The benchmark term represents the best-case regret bound one can achieve if, for all task n, the chosen subspace Bn can well approximate θ n (i.e. ∥( Bn ) ⊤ ⊥ θn ∥ ≤ α) On the other hand, the regret-bound term depends on a few important factors: first, the cost decreases when the meta-exploration probability p increases -this matches our intuition that a larger p gives more frequent feedback to learn about θ n , allowing the learned Bn to adapt faster to θ n ; second, the cost depends logarithmically on the size of the expert set ln |E ε |, which is standard in the online learning from expert advice literature; third, the cumulative cost depends on the range of the instantaneous costs C miss . 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 θn , and the cost C n (B) depends on the chosen subspace B and θ n . 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 a stochastic fashion, unlike a deterministic dependence in the original partial monitoring setting.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: The code for our paper can be found at https://github.com/ duongnhatthang/BOSS.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
performance guarantees: 
 We bound the meta-regret of Algorithm 3 in Theorem 7:EQUATIONIn 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, N m √ τ is the cumulative regret bound of the oracle baseline, i.e. the idealized algorithm that takes advantage of the extra knowledge of B to achieve a O(m √ τ ) regret for every task. The second term, N 2 3 τ 2 3 dm 1 3 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 ≫ d 3 √ τ m 2 ). Compared with multi-task regret bounds in the parallel setting [Yang et al., 2020 , Hu et al., 2021] , our dependence on N is admittedly weaker; nevertheless, to our 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] .For the burn-in terms, the N d 2 term can be interpreted as a constant d 2 regret overhead per task; the τ md term can be interpreted as the learner sacrificing a constant number of tasks (md tasks) to learn a good representation B. Observe that, in the less favourable situation where N < md or τ < d 2 , the burn-in terms would lead to regret bounds worse than the trivial N τ .Comparison with the individual single task baseline. Recall that the individual single-task baseline has a meta-regret of O(N d √ τ ); our meta-regret guarantee improves over this baseline when τ ≫ d 2 and N ≫ m √ τ . 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:Ω N m √ τ + d √ mτ N .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 is 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 n as Rn τ := τ max a∈A ⟨θ n , a⟩ -τ t=1 ⟨θ n , A n,t ⟩.We decompose R τ as follows:R τ = N n=1 E Rn τ = N n=1 E Rn τ Z n + Rn τ (1 -Z n ) = N n=1 E Rn τ | Z n = 1 • p + N n=1 E Rn τ | Z n = 0 • (1 -p) ≤C info • N p + N n=1 E C n ( Bn ) = Õ τ 1 + τ • d 2 τ 1 N p + N τ 2 + τ • m 2 τ 2 + d 2 τ 1 + τ dm p = Õ N pτ 1 + N τ d 2 τ 1 + τ dm p + N τ 2 + N τ m 2 τ 2 ,where the first two equalities are by the definition of R τ 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 is due to the definition of C info and Lemma 6; the last equality is by algebra.The meta-regret of Algorithm 3 follows from the choices of τ 1 , τ 2 , and p -specifically, τ 2 balances the last two terms, whereas τ 1 and p aims at balancing the first three terms subject to the constraint that τ 1 ≤ τ and p ≤ 1 -see Appendix H 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, we show that knowledge of N can be 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 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.For m, the requirement 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(N d √ τ ) as discussed in section 1.1. 
experiments: 
 In this section6 , 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 on the true subspace B, for all tasks • SeqRepL: our implementation of [Qin et al., 2022] , in which Bn is estimated with SVD and the tasks for meta-exploration are chosen deterministically at round n = i(i+1)2 for i = 1, 2, • • • . • BOSS-no-oracle: Algorithm 3 with E ε setof 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 a better approximation of the original BOSS (Algorithm 3) since there existsB ε ∈ E ε such that ∥(B ε ) ⊤ ⊥ B∥ F ≤ ε.The setting is (N, τ, d, m) = (4000, 500, 10, 3). The environment reveals a new subspace dimension at tasks 1, 2501, and 3501. In this experiment, we assume A is a unit sphere, i.e., M = I d . At each task n, denote by B n ∈ R d×mn the subspace basis that the environment used to generate θ n , where m n is incremented when n = 1, 2501, 3501. θ n is chosen in the following way: θ n = λ 1 B n w n for some w n ∼ Unif(S mn-1 ) and λ 1 ∼ Unif([0.8, 1]) is a random scaling factor to ensures Assumption 2, where θ min = 0.8, θ max = 1.The hyper-parameters p, τ 1 , τ 2 , and α of all algorithms, where it applies, are tuned. The error bands in the figures indicate ±1 standard deviation computed over 5 independent runs. 6 Discussion and Future WorkWe 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Õ N m √ τ + N 2 3 τ 2 3 dm 1 3 + N d 2 +τ md without using the task diversity assumption as in previous works.In this work, we present the first nontrivial result for sequential multi-task representation transfer in linear bandits without the task diversity assumption. This paper 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 performance in all parameter regimes. In addition, BOSS utilizes the special structure of fixed, ellipsoid-shaped action spaces to obtain useful information for metaexploration, extending the algorithm and guarantees to general and time-varying action spaces is an important direction. Practically, it would also be nice to design parameter-free variants of BOSS that do not require knowing m ahead of time. Furthermore, BOSS requires maintaining an exponentially large number of experts in B ε ; in the future, we would like to develop more computationally efficient algorithms. Lastly, it would be interesting to study relaxations of Assumption 1 (all task parameters lie exactly in a m-dimensional linear subspace), similar to Bilaj et al. [2024] or the changing subspace setting of Qin et al. [2022] .Meta learning bandit problems. Balcan et al. [2022] analyzed a 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 an online mirror decent base algorithm, they provided a guarantee of Õ min 1τ ≤ϵ≤ 1 √ τ N d Vϵ √ τ + ϵτ + N 3 4 τ 2 d, where Vϵ measures the proximity of the optimal parameters of all N tasks. Balcan et al. [2022] 's results also applies to the sequential meta-learning with adversarial K-arms bandit, which is further investigated by Azizi et al. [2024] . Their bandit meta-learning with a small set of optimal arms setting is analogous to the sequential multi-task representation transfer in linear bandit. The task diversity assumption is equivalent to the Azizi et al. [2024] 's Efficient Identification assumption; both require a gap to 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. It can take a left action x L and a right action x R and receive reward r = x ⊤ L Θx R + η. This reduces to our setting when the action set of the left action is the task descriptor {e i } i=1,••• ,N and the task's parameters have a low-rank structure. When applying their approach to our setting, their guarantee isÕ N d √ τ + N 3 2√ dτ , which is worse than independently using a classical algorithm, such as PEGE, for each task. This is due to the fact that Jang et al. [2021b] 's solution does not exploit the low-rank and the left action structures.In Table 2 , we comprehensively compare the settings and assumptions of the previous works for the multi-task bandit representation transfer problem.Setting Prior knowledge Task Diversity Regret guarantee For all B ∈ E ε , observe the costIndependent PEGE for each task Both None No Õ (N d √ τ ) Hu et al. [2021] Parallel N, m No Õ N √ mdτ + d √ τ N m Yang et al. [2020] Parallel N, m, τ Yes O N m √ τ + d 3 2 m √ τ N Ω N m √ τ + d √ mτ N Yang et al. [2022] Parallel N, m, τ Yes Õ N m √ τ + d √ mτ N Cella et al. [2023] Parallel A t : |A t | = K No Õ N √ mdτ + d √ τ N m Ω √ N τ dm Jang et al. [2021b] Sequential None No Õ N d √ τ + N 3 2 √ dτ Qin et al. [2022] Sequential m, τ Yes Õ N m √ τ + dm √ τ N Ω N m √ τ + d √ mτ N Bilaj et al. [2024] Sequential None Yes At least O N √ τ (d -m) log 1 + m λ A min (d-m) BOSS Sequential N, m, τ No Õ(N m √ τ + N 2 3 τ 2 3 dm 1 3 + N d 2 + τ md)Cn (B) = I(∥B ⊤ ⊥ θn ∥ 2 ≤ α)C hit + I(∥B ⊤ ⊥ θn ∥ 2 > α)C miss 10:The shifted and scaled loss:ℓ n (B) = p C miss Cn (B) Z n p -C hit Z n p = 1 C miss Cn (B) -C hit 11: Update: D n+1 (B) = Dn(B) exp(-ηℓn(B)) B ′ ∈E ε Dn(B ′ ) exp(-ηℓn(B ′ ))12:else 13:Exploitation procedure in Algorithm 2 with Bn 14:Update:D n+1 = D n 15:end if 16: end forIn this section, we provide more details about the construction of the expert set used in Section 3.Since it is difficult to directly construct E ε , an ε-cover in the principal angle sense (Definition 5) , we define the surrogate set E ε F : an ε-cover in the Frobenius norm sense over the set B S ⊇ B in Definition 8. We will then show that E ε F is also an ε-cover of B in the principal angle sense. Specifically, Lemma 13 shows that for any B ∈ B, there existsA ∈ E ε F such that ∥A ⊤ ⊥ B∥ F ≤ ε. Definition 8. E εF is said to be an ε-cover over the set of B S = {B :∥B∥ F = √ m} in the Frobenius norm sense, if: ∀ B ∈ B S , ∃A ∈ E ε F such that ∥vec(A) -vec(B)∥ 2 ≤ εAfter defining the expert set, to use the EWA algorithm, we need to use a surrogate expert's cost Cn defined in Equation ( 3), which is a high probability upper-bound of the true cost C n (B) following Lemma 11. To construct Cn , we need to introduce the definition of α-covering in Definition 9. Definition 9. A subspace (represented by its orthonormal basis) B ∈ R d×m is said to αapproximately cover vector ϕ ∈ R d , if ∥B ⊤ ⊥ ϕ∥ 2 ≤ α. Note: the specific choice of B ⊥ does not affect the validity of this definition -e.g., ∥B ⊥ ϕ∥ 2 are always the same regardless of the specific choice of B ⊥ , as long as its columns form a orthonormal basis of span(B ⊥ ): for any two choices of B ⊥ (denoted by B ⊥,1 , B ⊥,2 , respectively) there exists orthonormalV ∈ R (d-m)×(d-m) such that B ⊥,1 = B ⊥,2 V . Therefore, ∥B ⊤ ⊥,1 θ n ∥ 2 = ∥V ⊤ B ⊤ ⊥,2 θ n ∥ 2 = ∥B ⊤ ⊥,2 θ n ∥ 2The following lemma justifies that all valid choices of B ⊥ are equivalent up to a (d -m) × (d -m) orthogonal transformation: Lemma 10. Let W be a k-dimensional subspace of R d . Let B, B ∈ R d×k be matrices whose columns form an orthonormal basis of W . Then, there exists an orthogonal matrix V ∈ R k×k such that B = BV .Proof. Since B is a basis of W , there exists some V such that B = BV . SinceV ⊤ V = V ⊤ (B ⊤ B)V = (BV ) ⊤ (BV ) = B⊤ B = I, V is an orthogonal matrix.Next, we justify the use of Cn as a surrogate cost for the true cost C n in Lemma 11, which requires Remark 2. Remark 2. By the observation that∥B ⊤ ⊥ ϕ∥ 2 = ∥B ⊥ B ⊤ ⊥ ϕ∥ 2 = ∥ϕ -BB ⊤ ϕ∥ 2 = min θ∈span(B)∥ϕ -θ∥, B α-approximately cover ϕ if and only if there exists some θ in span(B) that is α-close to ϕ. As a result:• If θ n ∈ span(B) and ∥θ n -θn ∥ ≤ α, B also α-covers θn ;• If B α-covers θn and ∥θ n -θn ∥ ≤ α, B also 2α-covers θ n .Lemma 11. With high probability, Cn is an upper bound of C n .Proof. We have:C n (B) = I(∥B ⊤ ⊥ θ n ∥ 2 ≤ 2α)C hit + I(∥B ⊤ ⊥ θ n ∥ 2 > 2α)C miss ≲ I(∥B ⊤ ⊥ θn ∥ 2 ≤ α)C hit + I(∥B ⊤ ⊥ θn ∥ 2 > α)C miss (With high probability) = Cn (B).Here, the first equality comes from Equation (2). Since, for all meta-exploration rounds n (where Z n = 1), ∥ θn -θ n ∥ ≤ α with high probability, the inequality is true following Remark 2To ensure that there exists some B ∈ E ε that can α-cover all θn , we need to choose ε by following Lemma 12. Lemma 12. By choosing ε ≤ α, there exists some B ε ∈ E ε such that, for all n, B ε α-approximately covers θ n .Proof. For any n ∈ [N ], θ n ∈ span(B). Hence, θ n = P B θ n .Thus:min U ∈E ε ∥θ n -U U ⊤ θ n ∥ 2 = min U ∈E ε ∥U ⊥ U ⊤ ⊥ θ n ∥ 2 = min U ∈E ε ∥U ⊥ U ⊤ ⊥ BB ⊤ θ n ∥ 2 ≤ min U ∈E ε ∥U ⊥ ∥ op ∥U ⊤ ⊥ B∥ F ∥B ⊤ ∥ 2 op ∥θ n ∥ 2 ≤ min U ∈E ε ∥U ⊤ ⊥ B∥ F ≤ εHence, by setting ε ≤ α, we ensure that min U ∈E ε ∥ϕ -U U ⊤ ϕ∥ 2 ≤ α.Lemma 13.• For any B ∈ B, there existsA ∈ E ε F such that ∥A ⊤ ⊥ B∥ F ≤ ε • The size of the set E ε defined in Definition 5 is |E ε | ≤ |E ε F | ≤ c • dm ε dmFollowing Vu [2020] , we relate ∥A ⊤ ⊥ B∥ F to the Orthogonal Procrustes problem in Gower and Dijksterhuis [2004] : minR∈R m×m :R ⊤ R=Im ∥AR -B∥ 2 F With the solution R * = A ⊤ B B ⊤ AA ⊤ B -12 , at the optimum:∥A ⊤ ⊥ B∥ 2 F = m i=1 sin 2 (θ i ) (θ is the canonical angle) = m - m i=1 cos 2 (θ i ) ≤ m - m i=1 (2 cos(θ i ) -1) (cos(θ i ) 2 ≥ 2 cos(θ i ) -1) = 2m -2 m i=1 cos(θ i ) = ∥AR * -B∥ 2 F We have ∥A ⊤ ⊥ B∥ 2 F ≤ ∥AR * -B∥ 2 F ≤ ∥A -B∥ 2 F . Thus, ∀A, B ∈ [-1, 1] d×m , if ∥A -B∥ F ≤ ε, then ∥A ⊤ ⊥ B∥ F ≤ ε. Since ∥B∥ F = ∥vec(B)∥ 2 =√ m, by vectorizing B, we can further describe B ⊂ B S as the surface of the sphere in R dm with radius √ m.Since B ⊂ B S and the inequality above, by Definition 8:∀ B ∈ B, ∃A ∈ E ε F such that ∥A ⊤ ⊥ B∥ F ≤ ∥vec(A) -vec(B)∥ 2 ≤ εSince this is the same as the Definition 5, we can conclude that E ε F is a "denser" net than E ε over B. In other word, since E ε F ε-cover B S , then it also ε-cover B Then, following Erdogdu and Vural [2024], if we discretize the hyper-cube that contains this sphere (not just the surface), then|E ε | ≤ |E ε F | ≤ 2m √ d ε dm = c • dm ε dm .We first restate Lemma 3. Lemma 3. Fix τ 1 to be a multiple of d. Suppose Algorithm 1 is run on task n with the exploration length τ 1 . Then, there exists some constant c 1 , c 2 > 0 (that depends on λ 0 , θ max , θ min , and M ) such that:1. The regret on task n is bounded asR n τ ≤ c 1 • τ 1 + τ • d 2 τ1 =: C info ; 2. With probability 1 -δ, it returns θn such that ∥ θn -θ n ∥ ≤ c 2 • d ln d δ τ1 =: α.Proof. For the first item, following Rusmevichientong and Tsitsiklis [2010] 's Lemma 3.4, we have:E ∥ θ -θ∥ 2 ≤ c 0 d 2 τ 1 ,where c 0 is a constant that depends on λ 0 and M . From Yang et al. [2020] 's Lemma 17, we have:max a∈A ⟨a -A n,t , θ n ⟩ ≤ J∥θ n -θn ∥ 2 /∥θ n ∥, where A n,t = argmax a∈A a, θn , J = λmax(M ) √ λmin(M ) = λmax(M ) λ0. Thus:E [R n τ ] = E τ max a∈A ⟨θ n , a⟩ - τ t=1 ⟨θ n , A n,t ⟩ = E τ 1 max a∈A ⟨θ n , a⟩ - τ1 t=1 ⟨θ n , A n,t ⟩ + (τ -τ 1 ) max a∈A ⟨θ n , a⟩ - τ t=τ1+1 ⟨θ n , A n,t ⟩ ≤ λ 0 θ max τ 1 + (τ -τ 1 )J E∥ θn -θ n ∥ 2 θ min ≤ λ 0 θ max τ 1 + J θ min • τ c 0 d 2 τ 1The proof of the first item is concluded by taking c 1 = max(λ 0 θ max , Jc0 θmin ). For the second item, recall that u = τ1 d , and A n,1 , . . . , A n,τ1 are constructed as follows: for eachi ∈ [d] and t ∈ {u(i -1) + 1, • • • , ui}, A n,t = λ 0 e i . Since θn := argmin θ 1 τ1 τ1 t=1 (⟨A n,t , θ⟩ -r n,t )2 , by the closed-form solution of ordinary least squares, we haveθn = (A ⊤ n A n ) -1 A ⊤ n r n ,whereA n :=   A ⊤ n,1 • • • A ⊤ n,τ1   ∈ R τ1×d ,andEQUATIONLet η n := (η n,1 , . . . , η n,τ1 ). We haveθn = (A ⊤ n A n ) -1 A ⊤ n r n (a) = 1 uλ 2 0 A ⊤ n r n = 1 uλ 2 0 A ⊤ n (A n θ n + η n ) (b) = θ n + 1 uλ 2 0 A ⊤ n η n ,where both (a) and (b) follow from Eq. ( 6).It now suffices to show that θn -θ n 2 = 1 uλ 2 0 A ⊤ n η n 2 ≤ O d log(d/δ)τ1 with probability at least 1 -δ. To this end, observe that by the construction of A n ,A ⊤ n η n =   λ 0 u t=1 η n,t • • • λ 0 τ1 t=τ1-u+1 η n,t   .Since for each n and t, η n,t is zero-mean and 1-sub-Gaussian, by [Lattimore and Szepesvári, 2020, Corollary 5.5] , for any i ∈ [d], we have:Pr   ui t=u(i-1)+1 η n,t ≥ 2u log(2/δ ′ )   ≤ δ ′ . Let δ = dδ ′ and G := ∀i ∈ [d], (A ⊤ n η n ) i ≤ λ 0 2u log(2d/δ) .Then, by the union bound, G happens with probability at least 1 -δ. Since under the event G,∥ θn -θ n ∥ 2 = 1 uλ 2 0 A ⊤ n η n 2 = 1 uλ 2 0 d i=1 (A ⊤ n η n ) 2 i ≤ 1 uλ 0 d • 2u log(2d/δ) ≤ O   d log(d/δ) τ 1   ,the proof of the second item is complete.We first restate Lemma 4. Lemma 4. Fixed τ 2 to be a multiple of m. Suppose Algorithm 2 is run on task n with input subspace Bn and the exploration length τ 2 . Then, there exists some constant c > 0 (that depends on λ 0 , θ max , θ min , and M ), such that the regret on task n is bounded as:R n τ ≤ c • τ 2 + τ • m 2 τ 2 + ∥ B⊤ n,⊥ θ n ∥ 2 2 . Specifically, if ∥ B⊤ n,⊥ θ n ∥ 2 ≤ 2α, then R n τ ≤ c τ 2 + τ • m 2 τ2 + α 2 .Proof. Similar to Rusmevichientong and Tsitsiklis [2010] , define J = λmax(M ) √ λmin(M )= λmax(M ) λ0 .From Yang et al. [2020] 's Lemma 17, we have:max a∈A ⟨a -A n,t , θ n ⟩ ≤ J∥θ n -θn ∥ 2 /∥θ n ∥,where A n,t = argmax a∈A a, θn .Thus:E [R n τ ] = E τ max a∈A ⟨θ n , a⟩ - τ t=1 ⟨θ n , A n,t ⟩ = E τ 2 max a∈A ⟨θ n , a⟩ - τ2 t=1 ⟨θ n , A n,t ⟩ + (τ -τ 2 ) max a∈A ⟨θ n , a⟩ - τ t=τ2+1 ⟨θ n , A n,t ⟩ ≤ λ 0 θ max τ 2 + (τ -τ 2 )J E∥θ n -Bn ŵn ∥ 2 θ minFor the second term, by the Subspace informed estimation Theorem 14, we have:E Bn ŵn -θ n 2 ≤ m 2 λ 2 0 τ 2 + ∥ B⊤ n,⊥ θ n ∥ 2Thus:R n τ ≤ c • τ 2 + τ • m 2 τ 2 + ∥ B⊤ n,⊥ θ n ∥ 2 2 When ∥ B⊤ n,⊥ θ n ∥ 2 ≤ 2α, then: E [R n τ ] ≤ λ 0 θ max τ 2 + (τ -τ 2 ) J θ min m 2 λ 2 0 τ 2 + 4α 2 ≤ c τ 2 + τ • m 2 τ 2 + α 2 ,where c = max λ 0 θ max , J λ 2 0 θmin , 4J θmin .In the proof above, we use the Subspace informed estimation theorem. Similar to Qin et al. [2022] 's lemma 2 and Yang et al. [2020] 's lemma 18, we have:Theorem 14 (Subspace informed estimation). Suppose Algorithm 2 is run on task n with the exploration length τ 2 , then:E∥ θn -θ n ∥ 2 ≤ m 2 λ 2 0 τ2 + ∥ B⊤ n,⊥ θ n ∥ 2 . Proof. Since A n,t = λ 0 Bn (i), i ∈ [m],and each action repeats ⌊τ 2 /m⌋ times, we haveτ2 t=1 A n,t A ⊤ n,t = τ2λ 2 0 m Bn B⊤ n . Thus: τ2 t=1 B⊤ n A n,t A ⊤ n,t Bn = τ 2 λ 2 0 m B⊤ n Bn B⊤ n Bn = τ 2 λ 2 0 m I mThen, the OLS estimator is given by:ŵn = τ2 t=1 B⊤ n A n,t A ⊤ n,t Bn -1 τ2 t=1 B⊤ n A n,t r n,t = τ2 t=1 B⊤ n A n,t A ⊤ n,t Bn -1 τ2 t=1 B⊤ n A n,t A ⊤ n,t Bw n + η n,t = m τ 2 λ 2 0 τ2 t=1 B⊤ n A n,t A ⊤ n,t Bw n + η n,t = m τ 2 λ 2 0 τ2 t=1 B⊤ n A n,t A ⊤ n,t Bn B⊤ n + Bn,⊥ B⊤ n,⊥ Bw n + m τ 2 λ 2 0 τ2 t=1 B⊤ n A n,t η n,t ( Bn B⊤ n + Bn,⊥ B⊤ n,⊥ = I) = B⊤ n Bw n + m τ 2 λ 2 0 τ2 t=1 B⊤ n A n,t A ⊤ n,t Bn,⊥ B⊤ n,⊥ Bw n + m τ 2 λ 2 0 τ2 t=1 B⊤ n A n,t η n,t = B⊤ n Bw n + m τ 2 λ 2 0 τ2 t=1 B⊤ n A n,t η n,t (A ⊤ n,t Bn,⊥ = 0)where the first equality is the closed-form solution of OLS; the second equality is by the definition of r n,t . The other equalities are algebraic manipulations. Now, we have:θn -θ n = Bn ŵn -Bw n = Bn B⊤ n Bw n + m τ 2 λ 2 0 τ2 t=1 B⊤ n A n,t η n,t -Bw n = B B⊤ n Bw n -Bw =:s1 + m τ 2 λ 2 0 τ2 t=1 Bn B⊤ n A n,t η n,t =:s2For s 1 :∥s 1 ∥ 2 = ∥ Bn B⊤ n Bw n -Bw n ∥ 2 = ∥(I -Bn,⊥ B⊤ n,⊥ )Bw n -Bw n ∥ 2 = ∥ Bn,⊥ B⊤ n,⊥ Bw n ∥ 2 ≤ ∥ Bn,⊥ ∥ 2 op ∥ B⊤ n,⊥ θ n ∥ 2 ≤ ∥ B⊤ n,⊥ θ n ∥ 2For s 2 :E∥s 2 ∥ 2 = E m τ 2 λ 2 0 τ2 t=1 Bn B⊤ n A n,t η n,t 2 = m 2 τ 2 2 λ 4 0 E τ2 t=1 Bn B⊤ n A n,t η n,t ⊤ Bn B⊤ n A n,t η n,t = m 2 τ 2 2 λ 4 0 E∥η n,t ∥ 2 τ2 t=1 A ⊤ n,t Bn B⊤ n A n,t = m 2 τ 2 2 λ 4 0 E∥η n,t ∥ 2 τ2 t=1 A ⊤ n,t I d -Bn,⊥ B⊤ n,⊥ A n,t ( Bn B⊤ n + Bn,⊥ B⊤ n,⊥ = I) = m 2 τ 2 2 λ 4 0 E∥η n,t ∥ 2 τ2 t=1 A ⊤ n,t A n,t (A ⊤ n,t Bn,⊥ = 0) = m 2 τ 2 2 λ 4 0 E∥η n,t ∥ 2 τ 2 λ 2 0 = m 2 τ 2 λ 2 0 E∥η n,t ∥ 2 ≤ m 2 τ 2 λ 2 0 (η n,t is 1-sub-Gaussian noise assumption)Hence:E∥ θn -θ n ∥ 2 ≤ E∥s 1 ∥ 2 + E∥s 2 ∥ 2 (Triangle inequality) ≤ m 2 τ 2 λ 2 0 + ∥ B⊤ n,⊥ θ n ∥ 2 G Proof of lemma 6: Regret of the subspace selection game Lemma 6. Let ε = α = c 2 d ln d δ τ1 (with c 2 defined in Lemma 3) and δ ∈ [0, 1] be a constant such that N 2 cdm δ + 1 2 ln ln d δ ≤ ln m √ τ 1, where c is a constant in Lemma 13.Then, Algorithm 3 chooses a sequence of subspaces Bn over the expert set E ε , defined in Definition 5, such that:N n=1 E C n ( Bn ) ≤ O N C hit + C miss log |E ε | p = Õ N τ 2 + τ • m 2 τ 2 + α 2 + τ dm p .Proof. First, we want to show that, by choosing δ such thatN 2 cdm δ + 1 2 ln ln d δ ≤ ln m √ τ 1 , we would have δ ≤ ln |E ε | N 2 .We have:δ ≤ ln |E ε | N 2 ≤ c dm ln dm ε N 2 (Lemma 13) = c dm(ln dm -ln ε) N 2 = c   dm(ln dm -ln d ln d δ τ1 ) N 2   = c   dm(ln dm -ln d ln d δ + ln √ τ 1 ) N 2   = c   dm(ln dm + ln √ τ 1 -ln d -ln ln d δ ) N 2   = c dm(ln dm + ln √ τ 1 -ln d -1 2 ln ln d δ ) N 2 =⇒ N 2 cdm δ + 1 2 ln ln d δ ≤ ln dm + ln √ τ 1 -ln d = ln dm √ τ 1 d = ln m √ τ 1 .Hence, by choosing δ such thatN 2 cdm δ + 1 2 ln ln d δ ≤ ln m √ τ 1 , we would have δ ≤ ln |E ε | N 2Next, recall the guarantee of Hedge from Freund and Schapire [1997] :Theorem 15 (Freund and Schapire [1997] ). For any sequence of loss vectors ℓ 1 , • • • , ℓ T and the initial weights of the experts are w i 1 = 1/n for all i ∈ [n] and γ ∈ (0, 1), the Hedge algorithm generates {p t } T t=1 such that its expected loss is bounded byT t=1 ⟨ℓ t , p t ⟩ ≤ -log(1 -γ) γ ℓ t (i) + ln n γ , ∀i = 1, . . . , n specifically, if at each round we choose i t ∼ p t , E T t=1 ℓ t (i t ) ≤ - ln(1 -γ) γ • E T t=1 ℓ t (i) + ln n γ , ∀i = 1, . . . , nApplying Theorem 15 with T = N , expert set E ε , i t = Bn , and the baseline expert i = B ε , we get:E N n=1 ℓ n ( Bn ) ≤ - ln(1 -γ) γ • E N n=1 ℓ t (B ε ) + ln |E ε | γBy using Taylor expansion, we have:ln(1 -x) = -x -x 2 2 + • • • , then: -γ - γ 2 2 ≤ ln(1 -γ) =⇒ 1 + γ 2 ≥ ln(1 -γ) -γHence:E N n=1 ℓ n ( Bn ) ≤ (1 + γ/2)E N n=1 ℓ n (B ε ) + log |E ε | γ Define E n as the event where ∥ θn -θ n ∥ ≤ α and E = ∩ N n=1 E n .Then, when all of our estimations θn are accurate, we have:I (E) N n=1 ℓ n (B ε ) = 0 for ℓ n (B) = p Cmiss Cn (B) -C hit Zn p and B ε ∈ E ε . Since P (E c n ) = δ, we have: P (E) ≥ 1 - N n=1 P (E c n ) = 1 -N δ.Thus. the event E happens with high probability 1 -N δ. Hence:E N n=1 ℓ n ( Bn ) - N n=1 ℓ n (B ε ) ≤ E γ N n=1 ℓ n (B ε ) + log |E ε | γ = E I(E)γ N n=1 ℓ n (B ε ) + I(E c )γ N n=1 ℓ n (B ε ) + log |E ε | γ = E 0 + I(E c )γ N n=1 ℓ n (B ε ) + log |E ε | γ ≤ E I(E c )γN + log |E ε | γ ≤ N 2 γδ + |E ε | γ ≤ O (log |E ε |) . (δ ≤ log |E ε | N 2and choose γ = 1/2)Since γ = 1 -exp(-η), the learning rate η of the algorithm is η = -log(0.5) = 0.301.Then,E N n=1 ℓ n ( Bn ) - N n=1 ℓ n (B ε ) ≤ O(log |E ε |) =⇒ E N n=1 ℓ n ( Bn ) -E I(E) N n=1 ℓ n (B ε ) + I(E c ) N n=1 ℓ n (B ε ) ≤ O(log |E ε |) =⇒ E N n=1 ℓ n ( Bn ) -E I(E c ) N n=1 ℓ n (B ε ) ≤ O(log |E ε |) =⇒ E N n=1 ℓ n ( Bn ) ≤ O(log |E ε |) + N 2 δ =⇒ N n=1 p C miss E Cn ( Bn ) -C hit Z n p ≤ O(log |E ε |) =⇒ N n=1 E Cn ( Bn ) -N C hit ≤ O C miss log |E ε | p =⇒ N n=1 E Cn ( Bn ) ≤ O N C hit + C miss log |E ε | p Thus, E Cn ( Bn ) = E Cn ( Bn ) • Z n p ≥ E Cn ( Bn ) • I(E n ) • Z n p ≥ E C n ( Bn ) • (1 -I(E C n )) • Z n p ( Cn (B)I(E n ) ≥ C n (B)I(E n )) = C n ( Bn ) -E C n ( Bn ) • I(E C n ) • E Z n p | Bn ≥ C n ( Bn ) -C miss δ (C n ( Bn ) ≤ C miss , P (E C n ) = δ) Hence, N n=1 E Cn ( Bn ) ≤ O N C hit + C miss log |E ε | p =⇒ N n=1 E C n ( Bn ) ≤ O N C hit + C miss log |E ε | p + N δC miss = O N C hit + C miss log |E ε | p (N 2 δ = log |E ε | and 1 N ≤ 1 ≤ 1 p )Substituting C hit and C miss in Equation (2) to complete the proof.H Theorem 7: meta-regret guarantee Theorem 7. With exploration probability p = minEQUATIONRemainder of the Proof of Theorem 7. Recall that in the proof sketch of Theorem 7 (Section 4), we have proved thatR τ ≤ Õ N pτ 1 + N τ d 2 τ 1 + τ dm p + N τ 2 + N τ m 2 τ 2 . Now, by the choice of τ 2 = m • ⌊ √ τ ⌋, R τ ≤ Õ N m √ τ + N τ d 2 τ 1 + N pτ 1 + τ dm pWe want to tune the parameters p, τ 1 to minimize the meta-regret subjected to the constraint:p ∈ [0, 1] and τ 1 ∈ [0, τ ].The meta-regret is: 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:R τ ≤ Õ N m √ τ + N τ d 2 τ 1 + N pτ 1 + τ dm p = Õ N m √ τ + N d √ τ p + τ dm p + N d 2 (Choose τ 1 = d • min d τ p , τ /d ) = Õ N m √ τ + N• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not 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. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: The experiment information is provided in Section 5 and the code with all the parameters can be found at https://github.com/duongnhatthang/BOSS.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
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 a 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 error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, 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. Guidelines:• The answer NA means that there is no societal impact of the work performed.• 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks. Our dataset is synthetic.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [NA] Justification: We don't provide any new 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 is used. 38th Conference on Neural Information Processing Systems (NeurIPS 2024).Õ hides polylog(τ, N, d) factorAlthough not mentioned explicitly, a careful examination ofYang et al. [2022] shows that its Lemma 4.2 uses the assumption that σm ((θ1, . . . , θN )) ≥ N m , which is a task diversity assumption.In the proof of Theorem 5.1 therein, a key inequality, ∥θn -θn∥2 ≤ ∥θn∥2 -∥ θn∥2, was used (see Equation (21)); however, this inequality does not hold in general.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.In the case split of the definition of Cn(B), the value of ∥B ⊤ ⊥ θn∥2 is independent of the choice of B ⊥ . See Definition 9 and the discussion below in Appendix C for more details.The code for our paper can be found at https://github.com/duongnhatthang/BOSS 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: * 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.
* 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).
* 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?
* There is a gap to the known lower bound, which is suggested to be due to the task diversity assumption not being met.
questions: 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: limitations: NA
paper_summary: paper_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.
The authors provide a meta regret bound for their algorithms and synthetic data results.
strength_weakness: strength_weakness: 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)

The 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.

The 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)

The plot labels of figure 1 b) and c) should have latex style writing
questions: 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?

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?

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?

Does 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: limitations: Aside from the assumptions on their setting made, I did not see any limitations explicitly addressed.
paper_summary: paper_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.
strength_weakness: strength_weakness: There are some statements in the theorems that seem wrong and the upper bound provided does not seems tight. See Questions for details.
questions: 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.
2) The Assumption 2 is stated as linear bandits. I didn't get the reason for this title.
3) In line 3 in Algorithm 1, it should be $\mu=\frac{\tau_1}{d}$
4) 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.
5) In line 173, the definition of the expert set $\mathcal{E}^{\epsilon}$ is in the Appendix, which makes the paper not self-contained.
6) What does the EWA algorithm do in Algorithm 3? Which part of the results is directly from the EWA algorithm?
7) 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.
7) 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.
9) The labels on the y-axis in the figures need to be fixed.
limitations: limitations: The regret upper bounds has a hugh gap to the lower bound.
paper_summary: paper_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.
strength_weakness: strength_weakness: There is no major weakness in the paper. I do have some questions regarding the following:

**1**. This paper assumes knowledge of the parameters corresponding to the task number, the dimension, and the number of rounds, which is not ideal. 

**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.
questions: questions: Please see weaknesses.


Also, I am curious about the following:

1. 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?

2. Is there a corollary or simple extension that can readily extend the current result to the parallel setting?
limitations: limitations: Yes.

Comments: title: Response to rebuttal
comment: Thank you for the response, I have increased my score.
As the author-reviewer discussion period is coming to a close, we kindly ask for your review of our response. This ensures that any additional questions or feedback you may have can be addressed before the discussion period ends. Thank you for your time!
Thank you for your detailed answers to my questions and concerns. I will take them into consideration for the reviewers discussion period.
Thanks for clarifying some of the points I over-interpreted. I would like to raise the score to 5 but reduce the confidence to 3. The main weakness in 
my opinion is still the linear term in $\tau$. Consider any real-world tasks (such as search systems or recommender systems like movie recommendations), there will be a large volume of queries and $\tau$ will be arbitrarily larger than poly$(N)$.
I thank you authors for their efforts in the rebuttal. I will take all the rebuttals into consideration during the discussion period between reviewers.