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

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

$=>$ 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.

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

• ``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.''

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.

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

Indeed, 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

of the specific choice of $\hat{B}_{n, \perp}$, as long as its columns form a orthonormal basis of $\text{span}(\hat{B}_n)^\perp$:

For any two choices of $\hat{B}_{n, \perp}$

(denoted by $\hat{B}_{\perp, 1}$,

$\hat{B}_{\perp, 2}$, respectively)

there exists orthonormal $V \in \mathbb{R}^{{(d-m) \times (d-m)}}$ such that

$\hat{B}_{\perp, 1}$

$= \hat{B}_{\perp, 2} V$.

Therefore,

$\|\hat{B}_{\perp, 1}^{\top} \theta_n\|_2$

$= \|V^{\top}\hat{B}_{\perp, 2}^{\top} \theta_n\|_2$

$= \|\hat{B}_{\perp, 2}^{\top} \theta_n\|_2$

To show that all valid choices of $\hat{B}_{n, \perp}$ are equivalent up to a $(d-m) \times (d-m)$ orthogonal transformation, we have:

Let $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$.

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.

• ``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.''

$=>$ 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

$\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.

• ``What does the EWA algorithm do in Algorithm 3? Which part of the results is directly from the EWA algorithm?''

$=>$ 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.

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

• ``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''

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

• ``The definition of the expert set $\mathcal{E}^{\varepsilon}$ is in the Appendix, which makes the paper not self-contained''

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.

• ``... the code is not released during the submission. And I am curious how Figure 1B is generated.''

Correct. We want to add some additional experiment results. The code is in https://anonymous.4open.science/r/Serena-C5F1.

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

• ``The Assumption 2 is stated as linear bandits. I didn’t get the reason for this title.''

$=>$ We will change it to ``linear bandits with ellipsoid action sets'' in the final version.

• ``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?''

Yes. Indeed, our regret bound has an implicit dependence on $|| \hat{B}_{n, \perp}^T \theta_n ||$ - see Eq. (2).

This is a key quantity like the $||B_{\perp} -\hat{B}_{n+1,\perp}||$ you mentioned.

• ``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?''

$=>$ 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 most task $n$, in an average sense.

• ``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?''

$=>$ 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.

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

• ``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''

$=>$ Thank you for your suggestion. We will include the full EWA algorithm in the appendix in the final version.

• ``There is a gap to the known lower bound, which is suggested to be due to the task diversity assumption not being met.''

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.

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

• ``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?''

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.

The reason why we need large $N$ is explained in the global answer above.

• ``It would be nice to demonstrate the impact of the task diversity assumption''

$=>$ 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.

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

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!