Multi-task Representation Learning with Stochastic Linear Bandits

Leonardo Cella CSML, Italian Institute of Technology Karim Lounici CMAP, Ecole
Polytechnique

Grégoire Pacreau CMAP, Ecole Polytechnique Massimiliano Pontil CSML, Italian
Institute of Technology & Dept of Computer Science, UCL

###### Abstract

We study the problem of transfer-learning in the setting of stochastic linear
contextual bandit tasks. We consider that a low dimensional linear
representation is shared across the tasks, and study the benefit of learning
the tasks jointly. Following recent results to design Lasso stochastic bandit
policies, we propose an efficient greedy policy based on trace norm
regularization. It implicitly learns a low dimensional representation by
encouraging the matrix formed by the task regression vectors to be of low
rank. Unlike previous work in the literature, our policy does not need to know
the rank of the underlying matrix, nor does it requires the covariance of the
arms distribution to be invertible. We derive an upper bound on the multi-task
regret of our policy, which is, up to logarithmic factors, of order
$T\sqrt{rN}+\sqrt{rNTd}$, where $T$ is the number of tasks, $r$ the rank, $d$
the number of variables and $N$ the number of rounds per task. We show the
benefit of our strategy over an independent task learning baseline, which has
a worse regret of order $T\sqrt{dN}$. We also argue that our policy is minimax
optimal and, when $T\geq d$, has a multi-task regret which is comparable to
the regret of an oracle policy which knows the true underlying representation.

##  1 INTRODUCTION

Contextual bandits (Abbasi-Yadkori et al., 2011; Li et al., 2010; Auer, 2002)
are a prominent learning framework to study sequential decision problems with
partial feedback. They find applications in numerous fields, ranging from
recommender systems (Li et al., 2010), to finance (Shen et al., 2015) and to
adaptive routing (Awerbuch and Kleinberg, 2008), among others. This
methodology was originally motivated by applications in clinical trials
(Woodroofe, 1979), whereby a doctor has to decide which among available
treatments is best suited for a patient, through a sequence of trials. A
fundamental aspect in bandit problems is to control the trade-off between
exploration and exploitation, namely, the balance between the need of
acquiring more information and the temptation to act optimally according to
the already available knowledge.

In this paper we study multi-task learning with stochastic linear contextual
bandit tasks (Lu et al., 2021; Li et al., 2017; Filippi et al., 2010). Within
this setting, each task is associated with a regression vector and proceeds
sequentially. At each trial an agent observes a set of different alternatives
(arms) linked to a feature (context) vector. The agent then selects one
context vector and subsequently observes a stochastic reward generated by a
noisy linear regression associated to the chosen vector. The goal is to design
an algorithm (policy) that learns, interacting with the tasks, how to select
contexts that are most aligned with the underlying task (regression vector),
hence maximizing the cumulative rewards across all the tasks.

A central idea of multi-task learning is to leverage similarities between
tasks in order to facilitate learning. In this paper, we consider that the
tasks share a low dimensional representation, that is, the task regression
vectors span a low dimensional subspace. The benefit of learning such
representation has been widely investigated in both the standard supervised
learning and in the reinforcement learning settings (see Lounici et al., 2011;
Koltchinskii et al., 2011; Negahban and Wainwright, 2011; Calandriello et al.,
2014, and references therein). In the bandit setting, this problem presents
additional difficulties, since contexts vectors are no longer independently
distributed. Indeed, they are collected sequentially depending on past
observations and on the adopted bandit policy. This entails two main
challenges. On the one hand, we would like the collected contexts to span the
whole feature space, as this would facilitate the estimation of the unknown
regression vectors. On the other hand, collecting contexts which are
misaligned with respect to the regression vector results in poor performance
for the bandit strategy.

Contributions. In this work we present an efficient policy based on the trace
norm regularization estimator (see Koltchinskii et al., 2011; Negahban and
Wainwright, 2011; Maurer and Pontil, 2013, and references therein) which
leverages the tasks common representation to improve learning. We provide
oracle inequalities for this policy under the restricted strong convexity
condition with correct and explicit dependencies (Lemma 1 and Proposition 1)
that are based based on a novel martingale concentration argument. Next, we
provide an upper bound for the proposed policy (Theorem 1) which is valid
without boundedness assumption on the arms and is minimax optimal (up to a
logarithmic factor). We noticed that when the number of tasks is larger than
the ambient dimension our policy is comparable to the oracle policy which
knows the true underlying representation a-priori. A key novelty of the
proposed policy over the state-of-the-art (Yang et al., 2020) is that it does
not need to know the rank of the representation matrix, it does not require
the arms covariance distribution to be invertible and its regret bound is non-
trivial already when the time horizon is $O(d)$ in the worse case and
potentially $O(\log d)$ in favorable scenarios.

Notation. For a real vector $\mathbf{x}\in\mathbb{R}^{d}$, we use
$\left\lVert\mathbf{x}\right\rVert$ to denote its Euclidean norm. Given a pair
of symmetric matrices $\mathbf{A},\mathbf{B}\in\mathbb{R}^{d\times d}$, the
expression $\mathbf{A}\succeq\mathbf{B}$ means that $\mathbf{A}-\mathbf{B}$ is
positive semi-definite. We respectively use $\lambda_{\min}(\mathbf{A})$ and
$\lambda_{\max}(\mathbf{A})$ to refer to the minimum and maximum eigenvalues
of a square symmetric matrix $\mathbf{A}$. Similarly, we respectively use
$\sigma_{\min}(\mathbf{A})$ and $\sigma_{\max}(\mathbf{A})$ for the smallest
and the largest singular values of a generic matrix $\mathbf{A}$. Given a
positive definite matrix $\mathbf{A}\succ\mathbf{0}$, we indicate with
$\left\lVert\mathbf{x}\right\rVert_{\mathbf{A}}=\sqrt{\mathbf{x}^{\top}\mathbf{A}\mathbf{x}}$
the corresponding weighted Euclidean norm. For any matrix
$\mathbf{A}\in\mathbb{R}^{d\times T}$, we let
$\left\lVert\mathbf{A}\right\rVert_{\ast}=\sum_{i=1}^{d}\sigma_{i}(\mathbf{A})$
be the trace norm (sum of its singular values),
$\left\lVert\mathbf{A}\right\rVert_{\rm F}$ the Frobenius norm and
$\left\lVert\mathbf{A}\right\rVert_{\rm op}=\sigma_{\max}(\mathbf{A})$ the
operator norm (largest singular value). We denote with $[\mathbf{A}]^{i}$ its
$i$-th row and with $[\mathbf{A}]_{j}$ its $j$-th column. Finally, we use
$\text{diag}(\lambda_{1},\dots,\lambda_{d})$ for the $d\times d$ diagonal
matrix with values $\lambda_{1},\dots,\lambda_{d}$ on the diagonal. Given a
random event $\Upsilon$, we denote with $\Upsilon^{c}$ its complement.
Finally, given a scalar $\epsilon\in\mathbb{R}$ we denote with
$\mathbf{\epsilon}_{d}$ the $d$-dimensional vector having value $\epsilon$ in
each component. Additional notation is introduced on the way; a table
summarizing the notation used throughout the paper is reported in the
appendix.

##  2 RELATED WORKS

In the last two decades many efforts have been devoted to designing contextual
bandit policies (Abbasi-Yadkori et al., 2011, 2012; Ariu et al., 2020; Auer,
2002; Bastani and Bayati, 2020; Chu et al., 2011; Kim and Paik, 2019; Li et
al., 2017; Oh et al., 2021; Wang et al., 2018; Kuzborskij et al., 2019; Foster
and Rakhlin, 2020). When restricting to the high-dimensional setting an
appealing approach is based on sparse linear models, i.e. the number $s$ of
non-zero components of the regression vector is assumed to be much smaller
than the input dimension $d$. Many different strategies have been investigated
(Kim and Paik, 2019; Ariu et al., 2020; Bastani and Bayati, 2020). Among the
proposed approaches, one of the most recent and valuable works is (Oh et al.,
2021), where they design a greedy policy based on the Lasso estimator.
Interestingly, their approach does not require knowledge of $s$ and it does
not perform random pulls in order to have i.i.d. data. Inspired by this work,
we propose a greedy algorithm which does not need to know the rank index $r$
(dimensionality of the underlying representation). A technical challenge that
we are facing is how to obtain an accurate estimator relying on non i.i.d.
samples, while considering a more complex matrix estimator. We observe that
their regret bound argument is not accurate as there might be a hidden
dependency in the number of features (the same inaccuracy can be found in
(Cella and Pontil, 2021; Kim and Paik, 2019; Calandriello et al., 2014).

Multi-task and meta-learning frameworks have been studied primarily in the
supervised-learning setting (Tripuraneni et al., 2021; Denevi et al., 2018,
2019; Lounici et al., 2011; Argyriou et al., 2008; Baxter, 2000).
Specifically, the impact of representation learning with trace-norm
regularization has been widely investigated when considering i.i.d. data
(Koltchinskii et al., 2011; Negahban and Wainwright, 2011; Maurer and Pontil,
2013). More recently different authors have investigated the combination of
multi-task and meta-learning with interactive learning settings (e.g. bandits
and reinforcement learning) (Hu et al., 2021; Basu et al., 2021; Cella and
Pontil, 2021; Kveton et al., 2021; Simchowitz et al., 2021; Calandriello et
al., 2014; D’Eramo et al., 2019; Cella et al., 2020; Yang et al., 2020). Among
the latter category, the most relevant works are (Yang et al., 2020; Hu et
al., 2021; Cella and Pontil, 2021). Cella and Pontil (2021) considered both
the multi-task and the meta-learning frameworks but assuming the task vector
parameters to be jointly sparse, which is more restrictive than the low rank
assumption considered here. Differently, (Yang et al., 2020) considers a
similar multi-task problem both in the finite and infinite action settings,
whereas (Hu et al., 2021) considers only the latter setting. Note that these
two references impose stronger conditions and assumptions. Indeed, the
policies considered in those papers require knowledge of the low-rank
parameter $r$ and are not sample efficient. In this work, we develop a
different and more general analysis for the finite action setting. Notably,
our algorithm is computationally efficient and does not requires knowledge of
low-rank parameter $r$. Our idea is similar to the last approach investigated
in (Calandriello et al., 2014), but their work considers the simpler case
where samples are independently distributed. At last we mention that (Kveton
et al., 2017) studied low-rank stochastic bandits. However they consider a
completely different protocol, regret and arms definitions. Thus it is not
possible to draw a quantitative comparison to this work.

##  3 PROBLEM SETTING

In this section we recall the stochastic linear contextual bandit problem and
then introduce the multi-task learning framework.

###  3.1 Stochastic Linear Contextual Bandits

The contextual linear bandit problem consists of a sequence of $N$
interactions between a learning policy $\pi$ and the environment. At each
round $n\in[N]$, the agent is given a set
$\mathcal{D}_{n}\subseteq\mathbb{R}^{d}$ formed of $K$ arms (context vectors)
from which it has to select one arm $\mathbf{x}_{n}\in\mathcal{D}_{n}$ among
the available ones. Then, the agent observes the corresponding reward $Y_{n}$
via a noisy linear regression,

$Y_{n}=\mathbf{x}_{n}^{\top}\mathbf{w}+\eta_{n},$ (1)

where $\eta_{n}$ is a random variable whose statistical distribution will be
specified later. By knowing the true regression vector $\mathbf{w}$, at each
round $n\in[N]$ the optimal policy $\pi^{*}$ selects
$\mathbf{x}^{*}_{n}=\arg\max_{\mathbf{x}\in\mathcal{D}_{n}}\mathbf{x}^{\top}\mathbf{w}$,
maximizing the instantaneous expected reward. The learning objective is then
to maximize the cumulative reward, or equivalently, to minimize the pseudo-
regret

$R(N,\mathbf{w})=\sum_{n=1}^{N}r_{n}=\sum_{n=1}^{N}(\mathbf{x}^{*}_{n}-\mathbf{x}_{n})^{\top}\mathbf{w}.$

We make the following additional assumptions on the arms, the regression
vector and the noise variables.

######  Assumption 1 (Contexts Distribution ).

At each round $n\in[N]$, the decision set
$\mathcal{D}_{n}\subset\mathbb{R}^{d}$ consists of $K$ $d$-dimensional vectors
$\mathbf{x}_{k}$ admitting representation
$\mathbf{x}_{k}=\Sigma_{k}^{1/2}\mathbf{z}_{k}$ where $\Sigma_{k}$ is the
covariance operator of $\mathbf{x}_{k}$ and $\mathbf{z}_{k}$ is a
$d$-dimensional vector with independent sub-Gaussian entries with zero mean
and variance $1$. We assume the tuples $\mathcal{D}_{1},\dots,\mathcal{D}_{N}$
to be drawn i.i.d. from a fixed unknown zero mean sub-Gaussian joint
distribution $p$ on $\mathbb{R}^{Kd}$.

Let $C_{\mathbf{z}}$ be a positive constant satisfying

$\max_{1\leq k\leq K}\|\mathbf{z}_{k}\|_{\psi_{2}}\,{<}\,C_{\mathbf{z}}.$

We denote by $C_{\mathbf{x}}$ the sub-Gaussian Orlicz norm of the $K$ marginal
distributions of $p$ corresponding to the $K$ arms, that is
$C_{\mathbf{x}}:=\max_{1\leq k\leq K}\|\mathbf{x}_{k}\|_{\psi_{2}}.$ An
obvious computation gives

$C_{\mathbf{x}}\leq C_{\mathbf{z}}\max_{1\leq k\leq
K}\left\\{\left\lVert\Sigma_{k}\right\rVert_{\rm op}^{1/2}\right\\}<\infty.$

The above assumption is quite standard when considering high-dimensional
linear bandits (Bastani and Bayati, 2020; Hao et al., 2020; Kim and Paik,
2019; Rusmevichientong and Tsitsiklis, 2010). Note that vectors associated to
different arms are allowed to be correlated between each other. Moreover,
Assumption 1 implies that each arm $k$ admits zero mean, square-integrable
marginal distribution with $d\times d$ covariance $\Sigma_{k}$.

Finally, similarly to (Bastani et al., 2021; Oh et al., 2021), we introduce
the following assumption on the arms distribution. This mild condition is
necessary for our analysis in order to control the fulfillment of a specific
regularity property (the RSC condition, see Definition 1 below) by the
empirical covariance matrix. Specifically, it will allow the designed policy
to avoid interleaving its arm selection strategy with random plays.

######  Assumption 2 (Arms distribution).

There exists a constant $\nu\,{<}\,\infty$ such that
$p(-\overline{\mathbf{x}})/p(\overline{\mathbf{x}})\,{\leq}\,\nu\;\forall\overline{\mathbf{x}}\in\mathbb{R}^{Kd}$.
Moreover, there exists a constant $\omega_{\mathcal{X}}<\infty$ such that, for
any permutation $(a_{1},\dots,a_{K})$ of $[K]$, any integer
$i\in\\{2,\dots,K{-}1\\}$ and any fixed vector $\mathbf{w}\in\mathbb{R}^{d}$,
it holds that

$\displaystyle\mathbb{E}$
$\displaystyle\left[\mathbf{x}_{a_{i}}\mathbf{x}_{a_{i}}^{\top}\mathbb{I}\left\\{\mathbf{x}_{a_{1}}^{\top}\mathbf{w}<{\cdots}<\mathbf{x}_{a_{K}}^{\top}\mathbf{w}\right\\}\right]\preceq$
$\displaystyle\preceq\omega_{\mathcal{X}}\mathbb{E}\left[\left(\mathbf{x}_{a_{1}}\mathbf{x}_{a_{1}}^{\top}{+}\mathbf{x}_{a_{K}}\mathbf{x}_{a_{K}}^{\top}\right)\mathbb{I}\left\\{\mathbf{x}_{a_{1}}^{\top}\mathbf{w}<\cdots<\mathbf{x}_{a_{K}}^{\top}\mathbf{w}\right\\}\right].$

Parameter $\nu$ characterizes the skewness of the arms distribution $p$; for
symmetrical distributions $\nu=1$. Notice that Assumption 2 is satisfied for a
large class of distributions both discrete and continuous (e.g. Gaussian,
multi-dimensional uniform and Rademacher). The value $\omega_{\mathcal{X}}$
captures dependencies between arms: the more positively correlated they are,
the smaller $\omega_{\mathcal{X}}$ will be. The extreme scenario is given by
perfectly correlated arms, in which case we have $\omega_{\mathcal{X}}$
independent of any problem parameters. Finally, when arms are generated i.i.d.
from a multivariate Gaussian or a multivariate uniform distribution over the
sphere we have $\omega_{\mathcal{X}}=O(1)$.

###  3.2 Low-Rank Linear Contextual Bandits

In this paper, we address the problem of simultaneously solving $T$ linear
contextual bandit tasks. Each task $t\in[T]$ lasts for $N$ rounds and is
associated with a regression vector $\mathbf{w}_{t}\in\mathbb{R}^{d}$. We
denote with

$\mathbf{W}=[\mathbf{w}_{1},\dots,\mathbf{w}_{T}]$

the $d\times T$ matrix, whose columns are formed by the $T$ regression
vectors, which are unknown to the learner. The bandit tasks are explored in
parallel. At each round $n\in[N]$ each task simultaneously receives a decision
set $\mathcal{D}_{t,n}$ from the environment, upon which the learner (policy
$\pi$) picks an arm $\mathbf{x}_{t,n}$, and the associated feedback $y_{t,n}$
is observed via the linear regression

$y_{t,n}=\mathbf{x}_{t,n}^{\top}\mathbf{w}_{t}+\eta_{t,n}$ (2)

where $\eta_{t,n}$ is a noise random variable which we specify below.

We make the following assumption on the task regression vectors.

######  Assumption 3 (Low-Rank Assumption).

The matrix $\mathbf{W}\in\mathbb{R}^{d\times T}$ has rank
$\rho(\mathbf{W})=r$, with $r\ll\min(d,T)$.

The above assumption implies that there exists a low dimensional
representation $\mathbf{B}\in\mathbb{R}^{d\times{r}}$ with orthonormal columns
and a matrix $\mathbf{C}\in\mathbb{R}^{r\times T}$ such that
$\mathbf{W}=\mathbf{B}\mathbf{C}$. This is in-line with the standard high-
dimensional setting where many features are redundant.

Our principal objective is to minimize the multi-task pseudo-regret,

$\displaystyle\overline{R}({T},{N})$ $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}R({N},{\mathbf{w}_{t}})$ (3) $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\sum_{n=1}^{N}(\mathbf{x}_{t,n}^{*}{-}\mathbf{x}_{t,n})^{\top}{\mathbf{w}_{t}},$

where
$\mathbf{x}_{t,n}^{*}=\arg\max_{\mathbf{x}\in\mathcal{D}_{t,n}}\mathbf{x}^{\top}{\mathbf{w}_{t}}$.

##  4 LOW-RANK MATRIX ESTIMATION

In the standard supervised learning setting a natural estimator suited to
Assumption 3 is given by the trace (nuclear) norm regularized estimator (see
Argyriou et al., 2008; Bühlmann and Van De Geer, 2011; Lounici et al., 2011;
Negahban and Wainwright, 2011, and references therein). In particular a large
body of works have shown that bounds on the estimation error is controlled by
the rank of the underlying regression matrix. Here we adapt this methodology
to the bandit setting. At each round $n\in[N]$, we estimate matrix
$\mathbf{W}$ via $\widehat{\mathbf{W}}_{n+1}$ as the solution of the following
trace norm regularization problem

$\arg\min_{\mathbf{A}\in\mathbb{R}^{d\times
T}}\frac{1}{n}\sum_{t=1}^{T}\left\lVert\mathbf{y}_{t,n}-\mathbf{X}_{t,n}[\mathbf{A}]_{t}\right\rVert_{2}^{2}+\lambda_{n}\left\lVert\mathbf{A}\right\rVert_{\ast}$
(4)

where the design matrix $\mathbf{X}_{t,n}\in\mathbb{R}^{n\times d}$ contains
the context vectors $\mathbf{x}_{t,i}\in\mathbb{R}^{d}$, $i\in[n]$ as its
rows, the vector $\mathbf{y}_{t,n}\in\mathbb{R}^{n}$ is formed by the rewards
for task $t$ after $n$ interactions, sampled from (2), and
$\left\lVert\mathbf{A}\right\rVert_{\ast}$ is the trace norm of the matrix
$\mathbf{A}$, that is the sum of its singular values. If compared to the Lasso
estimator, the objective function (4) encourages low-rank matrices instead of
sparse vectors. Before presenting the technical results we need to introduce
the following additional notation.

Covariance matrices. We indicate the theoretical averaged $d\times d$
covariance matrix as

$\mathbf{\Sigma}=\frac{1}{K}\mathbb{E}\left[\sum_{k=1}^{K}\mathbf{x}_{k}\mathbf{x}_{k}^{\top}\right]=\frac{1}{K}\sum_{k=1}^{K}\Sigma_{k},$
(5)

where the expectation is over the decision set sampling distribution
$p_{\mathcal{X}}$ which is assumed to be shared between the tasks.

For every $t\in[T]$, we denote the empirical covariance matrix for task $t$ as

$\widehat{\mathbf{\Sigma}}_{t,n}=\frac{1}{n}\sum_{i=1}^{n}\mathbf{x}_{t,i}\mathbf{x}_{t,i}^{\top}.$
(6)

Moreover, we use the notation $\overline{\mathbf{\Sigma}}$ and
$\widehat{\overline{\mathbf{\Sigma}}}_{n}\in\mathbb{R}^{dT\times dT}$ for the
theoretical and the empirical multi-task matrices respectively. They are both
block diagonal and composed by the corresponding $T$ single task $d\times d$
matrices on the diagonal, that is

$\overline{\mathbf{\Sigma}}={\rm diag}(\mathbf{\Sigma},\dots,\mathbf{\Sigma})$

and

$\widehat{\overline{\mathbf{\Sigma}}}_{n}={\rm
diag}(\widehat{\mathbf{\Sigma}}_{1,n},\dots,\widehat{\mathbf{\Sigma}}_{T,n}).$

We introduce now the restricted strong convexity (RSC) condition on covariance
$\overline{\mathbf{\Sigma}}$. To this end, we denote by
$\rm{Vec}(\mathbf{\Delta})$, the vector in $\mathbb{R}^{dT}$ obtained by
stacking together the columns of $\mathbf{\Delta}\in\mathbb{R}^{d\times T}$.
Let

$\mathbf{W}={\bf U}{\bf D}{\bf V}^{\top}$

be the singular value decomposition of matrix $\mathbf{W}$ of rank $r$ where
${\bf U}\in\mathbb{R}^{d\times r}$, ${\bf V}\in\mathbb{R}^{T\times r}$ are the
matrices formed by the left and right singular vectors, respectively and ${\bf
D}$ is the $r\times r$ diagonal matrix of singular values.

######  Definition 1 (RSC Condition).

We say that the restricted strong convexity (RSC) condition is met for the
theoretical multi-task matrix
$\overline{\mathbf{\Sigma}}\in\mathbb{R}^{dT\times dT}$, with positive
constant $\kappa(\overline{\mathbf{\Sigma}})$ if

$\displaystyle\min\left\\{\frac{\left\lVert\rm{Vec}(\mathbf{\Delta})\right\rVert_{\overline{\mathbf{\Sigma}}}^{2}}{2\left\lVert\rm{Vec}(\mathbf{\Delta})\right\rVert_{2}^{2}}:\mathbf{\Delta}\in\mathcal{C}(r)\right\\}\geq\kappa(\overline{\mathbf{\Sigma}}),$
(7)

where

$\mathcal{C}(r){=}\Big{\\{}\mathbf{\Delta}\in\mathbb{R}^{d\times
T}:\left\lVert\Pi(\mathbf{\Delta})\right\rVert_{\ast}\leq{3}\left\lVert\mathbf{\Delta}{-}\Pi(\mathbf{\Delta})\right\rVert_{\ast}\Big{\\}}$
(8)

and $\Pi(\mathbf{\Delta})$ is the projection onto set

$\Big{\\{}\mathbf{\Delta}\in\mathbb{R}^{d\times
T}:{\rm{Col}}(\mathbf{\Delta})\perp{\bf
U},{\rm{Row}}(\mathbf{\Delta})\perp{\bf V}\Big{\\}}.$

The RSC condition allows us to control the error
$\mathbf{\Delta}_{n}=\widehat{\mathbf{W}}_{n}-\mathbf{W}$ as it guarantees
that the considered empirical loss is strictly convex on a restricted subset
of approximately low rank matrices defined by the cone $\mathcal{C}(r)$.

######  Remark 1 (Value of $\kappa(\Sigma)$).

As discussed in (Calandriello et al., 2014) Definition 1 can be compared with
the restricted eigenvalue and the compatibility conditions that have been
investigated for the group Lasso (Bühlmann and Van De Geer, 2011; Lounici et
al., 2011) and Lasso (Oh et al., 2021; Kim and Paik, 2019; Calandriello et
al., 2014) estimators. It is standard in high-dimensional statistics or in
compressed sensing to assume the existence of an absolute constant $\kappa>0$
such that $\kappa(\overline{\mathbf{\Sigma}})>\kappa>0$. Such conditions are
satisfied w.h.p. for instance by context vectors with i.i.d. zero mean,
variance 1, sub-Gaussian entries.

###  4.1 Oracle Inequality with non i.i.d. Data

We can now state our first result which controls the Forbeniou-norm estimation
error

$\Big{\|}\widehat{\mathbf{W}}_{n+1}-\mathbf{W}\Big{\|}_{\rm F}$

assuming the RSC condition to hold for the empirical multi-task matrix
$\widehat{\overline{\mathbf{\Sigma}}}_{n}$. In Proposition 2 we will show that
such condition is satisfied with high probability under our Assumptions 1, 2
and the RSC condition on $\overline{\mathbf{\Sigma}}$.

We denote by $\\{\mathbf{e}_{1},\ldots,\mathbf{e}_{T}\\}$ the standard
canonical basis of $\mathbb{R}^{T}$. We have then to upper bound the operator
norm of the following matrix

$\mathbf{D}_{n}=\sum_{t=1}^{T}\sum_{i=1}^{n}\eta_{t,i}\,\mathbf{x}_{t,i}\mathbf{e}_{t}^{\top}$

in order to set the regularization parameter at round $n$ so that the
estimation bound in the following lemma holds with high probability.

######  Lemma 1.

Let $\\{\mathbf{x}_{t,i}:t\in[T],i\in[N]\\}$ be the sequence generated by
Algorithm (1) Suppose the RSC condition holds for the empirical multi-task
matrix $\widehat{\overline{\mathbf{\Sigma}}}_{n}$ with constant
$\kappa\big{(}\widehat{\overline{\mathbf{\Sigma}}}_{n}\big{)}$. For
$\delta\in(0,1)$, define the regularization parameter
$\lambda_{n}=\lambda_{n}(\delta)$ such that with probability at least
$1-\delta$

$\frac{1}{n}\left\lVert\mathbf{D}_{n}\right\rVert_{\rm op}\leq\lambda_{n}.$
(9)

Then with probability at least $1-\delta$ the trace-norm regularized estimate
$\widehat{\mathbf{W}}_{n}$ defined in (4) satisfies

$\left\lVert\widehat{\mathbf{W}}_{n+1}-\mathbf{W}\right\rVert_{\rm
F}\leq\frac{32\lambda_{n}\sqrt{r}}{\kappa\big{(}\widehat{\overline{\mathbf{\Sigma}}}_{n}\big{)}}.$
(10)

The proof, which is presented in the appendix, follows along the lines of
(Negahban and Wainwright, 2011, Theorem 1).

######  Remark 2.

We note that a similar result can be also be found in Koltchinskii et al.
(2011). In addition, as pointed out in these references, it is possible to
extend this result to the case of approximately low rank matrices $\mathbf{W}$
by introducing an additional mispecification error in (10).

###  4.2 Controlling the Noise Term

The result in Lemma 1 requires us to set the regularization parameter at round
$n$ as in (9). To this end we exploit deviation bounds for martingales. Let us
define the filtration $(\overline{\mathcal{F}}_{n})_{n\geq 0}$ on a
probability space $(\Omega,\mathcal{A},\mathbb{P})$ as follows:
$\overline{\mathcal{F}}_{0}$ is the trivial $\sigma$-field
$\\{\emptyset,\Omega\\}$, and for any $n\geq 1$,

$\overline{\mathcal{F}}_{n}=\sigma\big{(}\mathbf{X}_{1,i},\eta_{1,i},\dots,\mathbf{X}_{T,i},\eta_{T,i},\,i\in[n]\big{)}.$

We consider the standard noise assumption (Abbasi-Yadkori et al., 2011;
Bastani and Bayati, 2020; Cella et al., 2020).

######  Assumption 4 (subGaussian noise).

The noise variables $(\eta_{t,n})_{t,n}$ are a sequence of sub-Gaussian random
variables adapted to the filtration $\\{\overline{\mathcal{F}}_{n}\\}_{n\geq
0}$ and such that for any $1\leq t\leq T$ and $n\geq 1$,

$\mathbb{E}[\eta_{t,n}|\overline{\mathcal{F}}_{n-1}]=0,\quad\text{and}\quad\mathbb{E}[\eta_{t,n}^{2}|\overline{\mathcal{F}}_{n-1}]\leq\sigma^{2},$

and $\eta_{1,n},\ldots,\eta_{T,n}$ are mutually independent conditionally on
$\overline{\mathcal{F}}_{n-1}$. We denote by $c_{\eta}$ the sub-Gaussian norm
of the $\eta_{t,n}$’s, that is, $\max_{t,n}\\{\|\eta_{t,n}\|_{\psi_{2}}\\}\leq
c_{\eta}$.

######  Proposition 1 (SubGaussian noise).

Let Assumptions 1 and 4 be satisfied. Then, with probability at least
$1-\delta$

$\frac{1}{n}\left\lVert\mathbf{D}_{n}\right\rVert_{\rm op}\leq\lambda_{n}$

where

$\displaystyle\lambda_{n}=\max_{k\in[K]}\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}^{1/2}\left[\sigma\sqrt{\frac{(d+T)\,\log\frac{2N(d+T)}{\delta}}{n}}\right.$
$\displaystyle\hskip
2.84544pt\bigvee\left.\frac{C\sqrt{\left(T+d+\log\frac{4N}{\delta}\right)\log^{3}\frac{8N(d+T)}{\delta}}}{n}\,\right]$
(11)

where $C>0$ can depend only on $c_{\eta},C_{\mathbf{z}}$.

###### Proof Sketch.

The complete proof is given in Appendix B. The proof relies on Freedman’s
inequality for martingale (Tropp, 2011, Corollary 1.3) combined with a
stopping time argument to handle unbounded arms.

∎

##  5 MULTI-TASK BANDITS VIA TRACE NORM REGULARIZATION

Algorithm 1 Trace-Norm Bandit

0: Confidence parameter $\delta$, noise variance $\sigma^{2}$

1: At round $n=1$ arms are picked randomly

2: Observe $Y_{1,1},\dots,Y_{T,1}$

3: for $n\in 2,\dots,N$ do

4: update $\widehat{\mathbf{W}}_{n}$ and $\lambda_{n}$ according to (4) and
(1)

5: for $t\in 1,\dots,T$ do

6: observe $\mathcal{D}_{t,n}$

7: pick
$\mathbf{x}_{t,n}\in\arg\max_{\mathbf{x}\in\mathcal{D}_{t,n}}\mathbf{x}^{\top}[\widehat{\mathbf{W}}_{n}]_{t}$

8: observe reward $Y_{t,n}$

9: end for

10: end for

In this section we present our proposed algorithm for multitask learning with
linear stochastic bandits. The algorithm relies on the trace-norm regularized
estimator in (4) and is displayed in Algorithm 1. It does not require to know
any input parameter besides an upper bound on the noise variance $\sigma^{2}$
and the confidence value $\delta$, which are necessary to specify the
regularization parameter111Using a regularization is quite common in the
bandit literature (e.g. Abbasi-Yadkori et al. (2011); Bastani and Bayati
(2020).  $\lambda_{n}$. Indeed this is the only parameter required by our
policy and it should be chosen large enough (in theory) as prescribed by
Proposition 1; see also equation (11).

Algorithm 1 updates the task parameters via a trace-norm regularized
estimation using all the already observed data. Similarly to (Oh et al.,
2021), our policy is completely greedy and does not need any forced-sampling
strategy. This phenomenon was recently highlighted by (Bastani et al., 2021)
which proved that greedy policies do not need an explicit exploration and can
even be rate-optimal if there is sufficient randomness in the observed
contexts (relying on i.i.d. arms assumption). This is unlike the UCB-like
policies (like OFUL) or forced-exploration policies Bastani and Bayati (2020).
Our trace-norm bandit policy (Alg. 1) belongs to the former class of
“exploration-free” greedy policies. More precisely, our policy performs a
natural initial exploration thanks to the arms randomness condition
(Assumptions 1 and 2) until the empirical covariance matrix satisfies the
(RSC) condition. In the regret analysis below this can be seen in the
definition of the first $N_{0}$ rounds in (12).

###  5.1 Multi-Task Learning

In this subsection we present our main result which is a high-probability
upper bound on the multi-task regret incurred by the trace-norm bandit policy.

For any $\delta\in(0,1)$, let $N_{0}(\delta)$ be the smallest integer such
that

$\displaystyle N$ $\displaystyle\geq
C\max_{k\in[K]}\left\lVert\Sigma_{k}\right\rVert_{\rm
op}^{2}\left(\big{(}r\log d\big{)}\log\frac{4TN}{\delta}\right)^{2},$ (12)

where $C>0$ is some large enough numerical constant that may depend only on
the distribution of the arms, in particular $\nu,\omega_{\mathcal{X}}$ and
$C_{\mathbf{z}}$.

Note that (12) is a sufficient condition on the minimum number of rounds for
our regret bound to be valid. Interestingly it depends on the ambient
dimension $d$ only logarithmically. This means that for our greedy policy, we
can guarantee that the duration of the implicit exploration phase is at most
$r^{2}$ (up to logarithmic factors). In situation where the $\mathbf{W}^{*}$
matrix is low-rank with $r\ll\sqrt{d}$, this represents another benefit of our
trace norm policy procedure over (Yang et al., 2020) which requires a much
longer exploration phase of at least $d^{2}$ rounds for their regret bound to
be valid.

We now state the main result.

######  Theorem 1.

Let Assumptions 1, 2, 3, 4 be satisfied. Assume that
$\max_{t\in[T]}\left\lVert\mathbf{w}_{t}\right\rVert_{2}{\leq}L$, for some
constant $L>0$ and that $N\geq N_{0}(\delta)$ for some $\delta\in(0,1)$. Then,
with probability at least $1-\delta$, the multi-task regret of Algorithm 1 is
upper bounded (up to logarithmic factors) by

$\displaystyle\mathcal{O}$
$\displaystyle\bigg{(}(T\sqrt{rN}+\sqrt{rdTN})\bigg{)}.$

Our proof is inspired by the one proposed in (Oh et al., 2021) for the single
task lasso bandit approach. We present here a sketch summarizing the key
steps. Full technical details are provided in Appendix D.

###### Proof Sketch of Theorem 1..

We consider the instantaneous multi-task regret at round $n$

$\displaystyle\overline{R}_{n}$
$\displaystyle=\sum_{t=1}^{T}R_{t,n}=\sum_{t=1}^{T}\langle\mathbf{x}_{t,n}^{*},\mathbf{w}_{t}\rangle-\langle\mathbf{x}_{t,n},\mathbf{w}_{t}\rangle.$

During the first $N_{0}(\delta)$ rounds, the RSC condition may not be
satisfied. During this phase, using a simple conditioning argument, we obtain
the following bound. We have with probability at least $1-\delta$, for any
$n\in[N_{0}]$

$\displaystyle\sum_{n=1}^{N_{0}}\overline{R}_{n}$ $\displaystyle\lesssim
T\,L\,N_{0}\,\sqrt{\log(eTN_{0}K\delta^{-1})}.$

Starting from the $N_{0}+1$ round, we bound the instantaneous regret as
follows:

$\displaystyle\overline{R}_{n}$
$\displaystyle\leq\sum_{n=N_{0}+1}^{N}\sum_{t=1}^{T}\langle\mathbf{x}_{t,n}^{*}-\mathbf{x}_{t,n},\mathbf{w}_{t}-\mathbf{\widehat{w}}_{t,n}\rangle.$

Using another conditioning, we get with probability at least $1-\delta$, for
any $t\in[T]$, $n\in[N]$,

$\displaystyle\overline{R}_{n}$
$\displaystyle\lesssim\sqrt{T}\left\lVert\mathbf{W}-\widehat{\mathbf{W}}_{n}\right\rVert_{F}\sqrt{\log(eTNK\delta^{-1})}.$

This bound is of interest if we can guarantee that $\widehat{\mathbf{W}}_{n}$
is an accurate estimate of $\mathbf{W}$, meaning that
$\left\lVert\mathbf{W}-\widehat{\mathbf{W}}_{n}\right\rVert_{F}$ is small.

To this end, we first prove that $\widehat{\overline{\mathbf{\Sigma}}}_{n}$
satisfies the RSC condition whp starting from round $N_{0}$. The argument is
based on concentration bounds for martingales combined with a novel geometric
analysis of the cone of matrix $\mathcal{C}_{r}$; see Lemma 2.

######  Proposition 2.

Let Assumptions 1 and 2 be satisfied. Assume in addition that
$\overline{\mathbf{\Sigma}}$ satisfies the RSC condition. Then, for any
$\delta\in(0,1)$ and any $n\geq N_{0}(\delta)$, with probability at least
$1-\delta$, the multi-task empirical matrix
$\widehat{\overline{\mathbf{\Sigma}}}_{n}$ satisfies the RSC condition with
constant

$\kappa\big{(}\widehat{\overline{\mathbf{\Sigma}}}_{n}\big{)}\geq\frac{\kappa\big{(}\overline{\mathbf{\Sigma}}\big{)}}{4\nu\omega_{\mathcal{X}}}>0.$

Consequently, this means that we can now use Lemma 1 and Proposition 1 which
guarantee with probability at least $1-\delta$, simultaneously for any
$n\in[N_{0},N]$

$\displaystyle\left\lVert\widehat{\mathbf{W}}_{n}-\mathbf{W}\right\rVert_{\rm
F}\lesssim\sqrt{\frac{r}{n}}\biggl{(}\sqrt{T+d+\log\left(\frac{4N(d+T)}{\delta}\right)}$
$\displaystyle\hskip
85.35826pt\cdot\log^{3/2}\left(\frac{8N(d+T)}{\delta}\right)\biggr{)}.$

Summing over $n$, we obtain with probability at least $1-\delta$ up to
logarithmic factors

$\displaystyle\sum_{n=N_{0}+1}^{N}\overline{R}_{s}$ $\displaystyle\leq
C\sqrt{rT(T+d)N},$

where
$C=C\left(L,\eta,\sigma,C_{\mathbf{z}},\kappa(\overline{\mathbf{\Sigma}}),\max_{1\leq
k\leq K}\left\\{\left\lVert\Sigma_{k}\right\rVert_{\rm
op}^{1/2}\right\\}\right)$ is a finite constant under our assumptions.

An union bound summing the regrets for the first phase $n\leq N_{0}$ and the
second phase $n>N_{0}$ gives the result (up to a rescaling of the constants).

∎

###  5.2 Result Discussion

We now discuss the implication of Theorem 1 and compare it to previous
approaches to multi-task representation learning in the bandit setting.

Advantage over ITL. Notice that running any $T$ independent policies (ITL)
with the linear contextual bandit setting defined in Section 3.1 would yield
at best a regret bound of order $T\sqrt{dN}$, up to logs; see e.g. (Lattimore
and Szepesvári, 2020, Chapter 19.4, comment 5). Since this regret bound is
always larger than the upper bound in Theorem 1 for the proposed MTL strategy,
there is a gain in using our method. In particular, if $T>d$, discarding
logarithmic factors, the bound for our method is smaller by a factor of order
$O(\sqrt{d/r})$, while for $d>T$ the gain is of order $O(\sqrt{T/r})$.

Minimax Optimality. Theorem 2 in (Yang et al., 2020) provides a matching
minimax lower bound to our Theorem 1 (up to logarithmic terms). In particular
this implies that in the regime $T\geq d$, our policy achieves the minimax
regret $T\sqrt{rN}$ (up to logs). This corresponds to the performance of the
oracle policy which knows the true underlying representation a-priori.

Comparison to SOTA Approaches. Our upper bound compares favorably to Theorem 1
in (Yang et al., 2020) for the finitely many arms setting. Their result
assumes Gaussian arms with non singular covariance matrices. They also assume
that $\mathrm{rank}(\mathbf{W})=r$ with known $r$ and
$K,T\leq\mathrm{poly}(d)$, $N\geq d^{2}$. Then Theorem 1 in (Yang et al.,
2020) guarantees for their MLinGreedy policy that

$\displaystyle\mathbb{E}[\overline{R}(T,N)]=$ $\displaystyle
O\Big{(}\left(T\sqrt{rN}+\sqrt{rdTN}\right)\cdot$
$\displaystyle\cdot\sqrt{\log(NKT)\log(NTdr)}\log\log N\Big{)}.$

We stress out that their policy requires the knowledge of the rank $r$ whereas
our policy does not. Notably, their regret bound requires $N\geq d^{2}$ rounds
to be valid whereas our regret bound is valid as soon as $N\gtrsim r^{2}$ (up
to logs). Moreover, their analysis requires the invertibility of the arms
covariance, whereas we only need the less restrictive RSC condition. Finally
we also extend the result to sub-Gaussian arm distributions. With our
notation, Hu et al. (2021) obtained a regret bound of order
$O(T\sqrt{drN}+d\sqrt{rTN})$ up to logs for their MTLR-OFUL policy in the
infinitely many arms setting, provided the rank $r$ is known to their policy.

##  6 EXPERIMENTS

In this section we validate the policy proposed in Section 5. The experiments
displayed in Figures 1 and 2 compare 3 different policies: the Trace-Norm
Bandit approach of Algorithm 1 for different choices of the regularization
parameter, the Oracle Policy which knows the low dimensional representation
$\mathbf{B}\in\mathbb{R}^{d\times r}$ to select the arm to play at each round
and the ITL policy which solves each $d$-dimensional task separately. In order
to compute the trace-norm estimator (Eq. 4) we adopt the accelerated gradient
method proposed in (Ji and Ye, 2009). In all the experiments, we report
results averaged over $5$ repetitions.

Figure 1: Averaged cumulative reward over all tasks for $T=10$ (top) and
$T=30$ (bottom). Each task lasts for $N=40$ rounds, has $K=10$ arms with
$d=20$ features, noise variance $\sigma^{2}=1$.

Figure 2: Averaged cumulative reward over all tasks. Each task lasts for
$N=40$ rounds, has $K=10$ arms with $d=50$ features and noise variance
$\sigma^{2}=1$ (top), $\sigma^{2}=9$ (bottom).

Data Processing. We conduct numerical experiments on different configurations.
Specifically, we analyze the impact of the number of tasks $T$, the dimension
$d$, noise variance $\sigma^{2}$ and the choice of the regularization
parameter. As metric we consider the cumulative reward averaged on all the
tasks $\overline{R}(T,N)/T$ as a function of the number of rounds $N$. The arm
set is generated randomly from a standard Gaussian distribution . The task
matrix $\mathbf{W}$ has been chosen to be of rank $r\ll d$ with randomly
generated gaussian entries.

Result Discussion. Figures 1 and 2 indicate that the proposed multi-task
approach performs favorably over independent task learning. Figure 1
highlights that our trace-norm policy performs well and significantly better
than ITL policy as long as the regularization parameter used in Eq. (4) is
taken large enough according to theory:

$\lambda_{n}=l\Bigg{[}\left(\frac{T+d}{n}+\frac{\log\frac{2}{\delta}}{n}\right)\bigvee\Bigg{(}\sqrt{\frac{T{+}d}{n}}+\sqrt{\frac{\log\frac{2}{\delta}}{n}}\Bigg{)}\Bigg{]}.$

In addition, we also observe that the performance of the trace norm bandit
improves and tends to that of the oracle policy as the number of tasks
increases. In Figure 2, we investigate the impact of noise variance on the
performance of the different policies. We used a higher value of dimension
$d=50$ as it is well-known that the impact of the noise becomes more
problematic in high-dimension. We observe that the trace-norm policy is
significantly less impacted by increased noise variance than the ITL policy.
Indeed the performance of the ITL policy degrades by $48\%$ as the noise
variance increases from $1$ to $9$. Comparatively, the oracle policy and the
trace-norm policy only incur a degradation of about $25\%$ as the noise
variance increases. This may be due to the fact that the oracle works in a
subspace of dimension $r$, and that the trace-norm policy is able to perform
dimensionality reduction through the nuclear norm regularization whereas the
ITL policy works in the whole $d$-dimensional space.

##  7 LIMITATIONS AND FUTURE WORK

We have studied the benefit of multi-task representation learning in the
setting of linear contextual bandit tasks. We proposed a novel bandit policy
based on trace-norm regularization which is computationally efficient and does
not need knowledge of the rank of the underlying task matrix. We derived an
upper bound for the multi-task regret of the proposed policy, showing that it
is effective in comparison to learning the tasks independently. Additionally,
this regret bound is minimax optimal and, in the regime $T\geq d$, our
policy’s regret matches the one of the oracle policy which knows the low-rank
common representation.

In this work we have restricted our analysis to the case of linear feature
learning. Additionally, we still require the designed policy to know one
problem parameter which is the variance associated to the noisy term. Relying
on (Maurer et al., 2016), in the future an interesting extension would be to
go beyond the linearity of the shared representation. Secondly, inspired by
(Belloni et al., 2011) a challenge one may try to solve is to design a fully
parameter free policy. Namely, a policy which does not require to know the
noise variance $\sigma^{2}$. Finally an important future direction is to
consider the meta-learning setting, in which the tasks are observed
sequentially and the goal is to minimize the regret on future yet-unseen
tasks.

#### Acknowledgements

This work was supported in part by the Chaire Business Analytic for Future
Banking, PNRR MUR project PE0000013-FAIR, and the European Union (Project
101070617).

## main

  * Abbasi-Yadkori et al. (2011) Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  In _NIPS_ , volume 11, pages 2312–2320, 2011.
  * Abbasi-Yadkori et al. (2012) Yasin Abbasi-Yadkori, David Pal, and Csaba Szepesvari.  Online-to-confidence-set conversions and application to sparse stochastic bandits.  In _Artificial Intelligence and Statistics_ , pages 1–9, 2012.
  * Argyriou et al. (2008) Andreas Argyriou, Theodoros Evgeniou, and Massimiliano Pontil.  Convex multi-task feature learning.  _Machine learning_ , 73(3):243–272, 2008.
  * Ariu et al. (2020) Kaito Ariu, Kenshi Abe, and Alexandre Proutière.  Thresholded lasso bandit.  _arXiv preprint arXiv:2010.11994_ , 2020.
  * Auer (2002) Peter Auer.  Using confidence bounds for exploitation-exploration trade-offs.  _Journal of Machine Learning Research_ , 3(Nov):397–422, 2002.
  * Awerbuch and Kleinberg (2008) Baruch Awerbuch and Robert Kleinberg.  Online linear optimization and adaptive routing.  _Journal of Computer and System Sciences_ , 74(1):97–114, 2008.
  * Bastani and Bayati (2020) Hamsa Bastani and Mohsen Bayati.  Online decision making with high-dimensional covariates.  _Operations Research_ , 68(1):276–294, 2020.
  * Bastani et al. (2021) Hamsa Bastani, Mohsen Bayati, and Khashayar Khosravi.  Mostly exploration-free algorithms for contextual bandits.  _Management Science_ , 67(3):1329–1349, 2021\.
  * Basu et al. (2021) Soumya Basu, Branislav Kveton, Manzil Zaheer, and Csaba Szepesvári.  No regrets for learning the prior in bandits.  _arXiv preprint arXiv:2107.06196_ , 2021.
  * Baxter (2000) Jonathan Baxter.  A model of inductive bias learning.  _Journal of artificial intelligence research_ , 12:149–198, 2000.
  * Belloni et al. (2011) Alexandre Belloni, Victor Chernozhukov, and Lie Wang.  Square-root lasso: pivotal recovery of sparse signals via conic programming.  _Biometrika_ , 98(4):791–806, 2011.
  * Bühlmann and Van De Geer (2011) Peter Bühlmann and Sara Van De Geer.  _Statistics for high-dimensional data: methods, theory and applications_.  Springer Science & Business Media, 2011.
  * Calandriello et al. (2014) Daniele Calandriello, Alessandro Lazaric, and Marcello Restelli.  Sparse multi-task reinforcement learning.  In _NIPS_ , 2014.
  * Cella and Pontil (2021) Leonardo Cella and Massimiliano Pontil.  Multi-task and meta-learning with sparse linear bandits.  In _The Conference on Uncertainty in Artificial Intelligence_ , 2021\.
  * Cella et al. (2020) Leonardo Cella, Alessandro Lazaric, and Massimiliano Pontil.  Meta-learning with stochastic linear bandits.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 1360–1370. PMLR, 13–18 Jul 2020.
  * Chu et al. (2011) Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire.  Contextual bandits with linear payoff functions.  In _International Conference on Artificial Intelligence and Statistics_ , pages 208–214, 2011.
  * Denevi et al. (2018) Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil.  Incremental learning-to-learn with statistical guarantees.  In _Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence_ , pages 457–466, 2018.
  * Denevi et al. (2019) Giulia Denevi, Dimitris Stamos, Carlo Ciliberto, and Massimiliano Pontil.  Online-within-online meta-learning.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * D’Eramo et al. (2019) Carlo D’Eramo, Davide Tateo, Andrea Bonarini, Marcello Restelli, and Jan Peters.  Sharing knowledge in multi-task deep reinforcement learning.  In _International Conference on Learning Representations_ , 2019.
  * Filippi et al. (2010) Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári.  Parametric bandits: The generalized linear case.  In _NIPS_ , volume 23, pages 586–594, 2010.
  * Foster and Rakhlin (2020) Dylan Foster and Alexander Rakhlin.  Beyond ucb: Optimal and efficient contextual bandits with regression oracles.  In _International Conference on Machine Learning_ , pages 3199–3210. PMLR, 2020.
  * Hao et al. (2020) Botao Hao, Tor Lattimore, and Mengdi Wang.  High-dimensional sparse linear bandits.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 10753–10763. Curran Associates, Inc., 2020.
  * Hu et al. (2021) 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.
  * Ji and Ye (2009) Shuiwang Ji and Jieping Ye.  An accelerated gradient method for trace norm minimization.  In _International Conference on Machine Learning_ , pages 457–464, 2009.
  * Kim and Paik (2019) Gi-Soo Kim and Myunghee Cho Paik.  Doubly-robust lasso bandit.  _Advances in Neural Information Processing Systems_ , 32:5877–5887, 2019.
  * Koltchinskii (2011) V. Koltchinskii.  _Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems: École D’Été de Probabilités de Saint-Flour XXXVIII-2008_.  Lecture Notes in Mathematics. Springer, 2011.  ISBN 9783642221460.  URL https://books.google.fr/books?id=D5Jxen3_xkAC.
  * Koltchinskii et al. (2011) Vladimir Koltchinskii, Karim Lounici, and Alexandre B Tsybakov.  Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion.  _The Annals of Statistics_ , 39(5):2302–2329, 2011.
  * Kuzborskij et al. (2019) Ilja Kuzborskij, Leonardo Cella, and Nicolò Cesa-Bianchi.  Efficient linear bandits through matrix sketching.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 177–185. PMLR, 2019.
  * Kveton et al. (2017) Branislav Kveton, Csaba Szepesvári, Anup Rao, Zheng Wen, Yasin Abbasi-Yadkori, and S Muthukrishnan.  Stochastic low-rank bandits.  _arXiv preprint arXiv:1712.04644_ , 2017.
  * Kveton et al. (2021) Branislav Kveton, Mikhail Konobeev, Manzil Zaheer, Chih-wei Hsu, Martin Mladenov, Craig Boutilier, and Csaba Szepesvari.  Meta-thompson sampling.  _arXiv preprint arXiv:2102.06129_ , 2021.
  * Lattimore and Szepesvári (2020) Tor Lattimore and Csaba Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Li et al. (2010) Lihong Li, Wei Chu, John Langford, and Robert E Schapire.  A contextual-bandit approach to personalized news article recommendation.  In _Proceedings of the 19th international conference on World wide web_ , pages 661–670, 2010.
  * Li et al. (2017) Lihong Li, Yu Lu, and Dengyong Zhou.  Provably optimal algorithms for generalized linear contextual bandits.  In _International Conference on Machine Learning_ , pages 2071–2080, 2017.
  * Lounici et al. (2011) Karim Lounici, Massimiliano Pontil, Sara Van De Geer, and Alexandre B Tsybakov.  Oracle inequalities and optimal inference under group sparsity.  _The annals of statistics_ , 39(4):2164–2204, 2011.
  * Lu et al. (2021) Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari.  Low-rank generalized linear bandit problems.  In Arindam Banerjee and Kenji Fukumizu, editors, _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ , volume 130 of _Proceedings of Machine Learning Research_ , pages 460–468. PMLR, 13–15 Apr 2021.
  * Maurer and Pontil (2013) Andreas Maurer and Massimiliano Pontil.  Excess risk bounds for multitask learning with trace norm regularization.  In _Conference on Learning Theory_ , pages 55–76. PMLR, 2013.
  * Maurer et al. (2016) Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes.  The benefit of multitask representation learning.  _Journal of Machine Learning Research_ , 17(81):1–32, 2016.
  * Negahban and Wainwright (2011) Sahand Negahban and Martin J. Wainwright.  Estimation of (near) low-rank matrices with noise and high-dimensional scaling.  _The Annals of Statistics_ , 39(2):1069–1097, 2011.
  * Oh et al. (2021) Min-hwan Oh, Garud Iyengar, and Assaf Zeevi.  Sparsity-agnostic lasso bandit.  In _Proceedings of the 38-th International Conference on Machine Learning_ , volume 139, pages 8271–8280, 2021.
  * Rusmevichientong and Tsitsiklis (2010) Paat Rusmevichientong and John N. Tsitsiklis.  Linearly parameterized bandits.  _Mathematics of Operations Research_ , page 395–411, 2010.
  * Shen et al. (2015) Weiwei Shen, Jun Wang, Yu-Gang Jiang, and Hongyuan Zha.  Portfolio choices with orthogonal bandit learning.  In _Twenty-fourth international joint conference on artificial intelligence_ , 2015.
  * Simchowitz et al. (2021) Max Simchowitz, Christopher Tosh, Akshay Krishnamurthy, Daniel Hsu, Thodoris Lykouris, Miroslav Dudík, and Robert E Schapire.  Bayesian decision-making under misspecified priors with applications to meta-learning.  _arXiv preprint arXiv:2107.01509_ , 2021.
  * Tripuraneni et al. (2021) Nilesh Tripuraneni, Chi Jin, and Michael Jordan.  Provable meta-learning of linear representations.  In _International Conference on Machine Learning_ , pages 10434–10443. PMLR, 2021.
  * Tropp (2011) Joel Tropp.  Freedman’s inequality for matrix martingales.  _Electronic Communications in Probability_ , 16(none):262 – 270, 2011.  doi: 10.1214/ECP.v16-1624.  URL https://doi.org/10.1214/ECP.v16-1624.
  * Vershynin (2018) Roman Vershynin.  _High-Dimensional Probability: An Introduction with Applications in Data Science_.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.  doi: 10.1017/9781108231596.
  * Wang et al. (2018) Xue Wang, Mingcheng Wei, and Tao Yao.  Minimax concave penalized multi-armed bandit model with high-dimensional covariates.  In _International Conference on Machine Learning_ , pages 5200–5208, 2018.
  * Woodroofe (1979) Michael Woodroofe.  A one-armed bandit problem with a concomitant variable.  _Journal of the American Statistical Association_ , 74(368):799–806, 1979.
  * Yang et al. (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.

APPENDIX

This appendix provides full proofs of the results stated in the main body of
the paper. It is organized as follows:

  * •

Appendix A contains the proof of Lemma 1, which is the oracle inequality
associated to the error $\Delta_{n+1}=\widehat{\mathbf{W}}_{n+1}-\mathbf{W}$
considering non i.i.d. data.

  * •

Appendix B presents the proof of Proposition 1 on the control to the operator
norm of matrix
$\mathbf{D}_{n}=\sum_{t=1}^{T}\sum_{i=1}^{n}\eta_{t,i}\,\mathbf{x}_{t,i}\otimes\mathbf{e}_{t}$.

  * •

Appendix C contains the proof of Proposition 2. It relies on a matrix
perturbation argument and a novel analysis of the uniform deviation of the
empirical arms covariance on the cone $\mathcal{C}_{r}$ of approximately low-
rank matrices (Lemmas 2 and 3). These results are then combined to relate the
RSC constant $\kappa(\overline{\mathbf{\Sigma}})$ of
$\overline{\mathbf{\Sigma}}$ to that of its empirical counterpart
$\kappa(\widehat{\overline{\mathbf{\Sigma}}}_{n})$.

  * •

Appendix D contains the proof for the regret upper bound associated to the
policy of Alg. 1.

  * •

In Appendix E, we provide additional numerical experiments.

Symbol | Description
---|---
$[n]$ | The set $\\{1,\dots,n\\}$, given a positive integer $n$
$T$ | Number of tasks
$N$ | Time horizon associated to each single task
$d$ | Dimension of context vectors
$a\vee b$ | The maximum between $a$ and $b$ ($\max(a,b)$)
$\|\cdot\|_{\psi_{2}}$ | The sub-Gaussian norm with $\psi_{2}(s)=e^{s^{2}}-1$
| (See e.g. page 215 in Koltchinskii (2011))
$\mathbf{e}_{1},\dots,e_{T}\in\mathbb{R}^{T}$ | The standard basis indicator vectors, i.e. $\mathbf{e}_{t,j}=1$, if $j=t$
| and $0$ otherwise, for all $t,j\in[T]$
$\mathbf{W}=[\mathbf{w}_{1},\dots,\mathbf{w}_{T}]\in\mathbb{R}^{d\times T}$ | Matrix of $T$ regression tasks
| (we also use the notation $[\mathbf{W}]_{t}\equiv w_{t},~{}t\in[T]$)
$r$ | Rank of the task matrix $\mathbf{W}$
$K$ | Number of arms
$p$ | Joint distribution on $\mathbb{R}^{dK}$ (from which $K$ arm vectors are sample)
$\mathcal{D}_{t,n}$, $t\in[T]$, $n\in[N]$ | Decision sets (each containing $K$ arm vectors) sampled i.i.d. from $p$
$\mathbf{x}_{t,n}\in\mathcal{D}_{t,n}$ | Arm vector chosen in task $t\in[T]$ at round $n\in[N]$
$\mathbf{x}^{*}_{t,n}\in\mathcal{D}_{t,n}$ | Optimal arm vector in task $t\in[T]$ during round $n\in[N]$
$\mathbf{\Sigma}\in\mathbb{R}^{d\times d}$ | Theoretical covariance matrix - see eq. (5)
$\mathbf{\Sigma}_{t,n}\in\mathbb{R}^{d\times d}$ | Adapted covariance matrix for task $t$ at round $n$; see eq. (32)
$\widehat{\mathbf{\Sigma}}_{t,n}\in\mathbb{R}^{d\times d}$ | Empirical covariance matrix for task $t$ at round $n$; see eq. (6)
$\overline{\mathbf{\Sigma}}\in\mathbb{R}^{dT\times dT}$ |  $T$-block diagonal matrix ${\rm diag}(\mathbf{\Sigma},\dots,\mathbf{\Sigma})$
$\overline{\mathbf{\Sigma}}_{n}\in\mathbb{R}^{dT\times dT}$ |  $T$-block diagonal matrix ${\rm diag}(\mathbf{\Sigma}_{1,n},\dots,\mathbf{\Sigma}_{T,n})$
$\widehat{\overline{\mathbf{\Sigma}}}_{n}\in\mathbb{R}^{dT\times dT}$ |  $T$-block diagonal matrix ${\rm diag}(\widehat{\mathbf{\Sigma}}_{1,n},\dots,\widehat{\mathbf{\Sigma}}_{T,n})$
$\left\lVert\mathbf{x}\right\rVert,~{}\left\lVert\mathbf{x}\right\rVert_{1},~{}\left\lVert\mathbf{x}\right\rVert_{\infty}$ | Euclidean, $\ell_{1}$ and maximum norm associated to a vector $\mathbf{x}$
$[\mathbf{A}]_{t}$ | The $t$-th column of matrix $\mathbf{A}\in\mathbb{R}^{d\times T}$
$\lambda_{\min}(\mathbf{A}),\lambda_{\max}(\mathbf{A})$ | Minimum and maximum eigenvalues of a square symmetric matrix $\mathbf{A}$
$\sigma_{\min}(\mathbf{A}),\sigma_{\max}(\mathbf{A})$ | Minimum and maximum singular values of matrix $\mathbf{A}$
$\left\lVert\mathbf{A}\right\rVert_{\ast}$ | Trace norm of matrix $\mathbf{A}$ (sum of its singular values)
$\left\lVert\mathbf{A}\right\rVert_{\rm F}$ | Frobenius norm of matrix $\mathbf{A}$ ($\ell_{2}$ norm o matrix elements / singular values)
$\left\lVert\mathbf{A}\right\rVert_{\rm op}$ | Operator norm of matrix $\mathbf{A}$ (maximum singular value)

##  Appendix A PROOF OF LEMMA 1

By definition of $\widehat{\mathbf{W}}_{n}$, we have for any
$\mathbf{W}\in\mathbb{R}^{d\times T}$,

$\frac{1}{n}\sum_{t=1}^{T}\left\lVert\mathbf{y}_{t,n}-\mathbf{X}_{t,n}[\widehat{\mathbf{W}}_{n+1}]_{t}\right\rVert_{2}^{2}+\lambda_{n}\left\lVert\widehat{\mathbf{W}}_{n+1}\right\rVert_{\ast}\leq\frac{1}{n}\sum_{t=1}^{T}\left\lVert\mathbf{y}_{t,n}-\mathbf{X}_{t,n}[\mathbf{W}]_{t}\right\rVert_{2}^{2}+\lambda_{n}\left\lVert\mathbf{W}\right\rVert_{\ast}.$

We define the error matrix
$\Delta_{n+1}=\widehat{\mathbf{W}}_{n+1}-\mathbf{W}$ and introduce the
following operator ${\cal A}:\mathbb{R}^{d\times
T}\rightarrow\mathbb{R}^{n\times T}$ and its adjoint ${\cal
A}^{*}:\mathbb{R}^{n\times T}\rightarrow\mathbb{R}^{d\times T}$ as

$\displaystyle[{\cal A}(\mathbf{W})]^{t}_{n}$
$\displaystyle=\langle\mathbf{x}_{t,n}\mathbf{e}^{\top}_{t},\mathbf{W}\rangle=\text{Tr}(\mathbf{W}\mathbf{e}_{t}\mathbf{x}_{t,n})=\mathbf{x}_{t,n}^{\top}\mathbf{w}_{t}$
$\displaystyle{\cal A}^{*}(\mathbf{H}_{n})$
$\displaystyle=\sum_{t=1}^{T}\sum_{i=1}^{n}\mathbf{x}_{t,i}\mathbf{e}^{\top}_{t}\eta_{t,i}=\mathbf{D}_{n}\hskip
10.00002pt\in\mathbb{R}^{d\times T},$

where
$\boldsymbol{\eta}_{t,n}=(\eta_{t,1},\ldots,\eta_{t,n})^{\top}\in\mathbb{R}^{n}$
and
$\mathbf{H}_{n}:=\left(\boldsymbol{\eta}_{1,n},\ldots,\boldsymbol{\eta}_{T,n}\right)\in\mathbb{R}^{n\times
T}.$

Using this notation the following hold

$\displaystyle\frac{1}{n}\left\lVert{\cal A}(\Delta_{n+1})\right\rVert_{\rm
F}^{2}$ $\displaystyle=\frac{1}{n}\sum_{t=1}^{T}\left\lVert\left[{\cal
A}(\Delta_{n+1})\right]^{t}\right\rVert_{2}^{2}\leq\frac{1}{n}\langle\mathbf{H}_{n},{\cal
A}(\Delta_{n+1})\rangle+\lambda_{n}\left(\left\lVert\mathbf{W}\right\rVert_{\ast}-\left\lVert\widehat{\mathbf{W}}_{n+1}\right\rVert_{\ast}\right)$
$\displaystyle\leq\frac{1}{n}\langle\mathbf{H}_{n},{\cal
A}(\Delta_{n+1})\rangle+\lambda_{n}\left(\left\lVert\widehat{\mathbf{W}}_{n+1}+\Delta_{n+1}\right\rVert_{\ast}-\left\lVert\widehat{\mathbf{W}}_{n+1}\right\rVert_{\ast}\right)$
$\displaystyle\leq\frac{1}{n}\langle\mathbf{H}_{n},{\cal
A}(\Delta_{n+1})\rangle+\lambda_{n}\left(\left\lVert\Delta_{n+1}\right\rVert_{\ast}\right).$

Considering now the first term on the RHS and applying Holder’s inequality we
have

$\frac{1}{n}\lvert\langle\mathbf{H}_{n},{\cal
A}(\Delta_{n+1})\rangle\rvert=\frac{1}{n}\lvert\langle{\cal
A}^{*}(\mathbf{H}_{n}),\Delta_{n+1}\rangle\rvert\leq\frac{1}{n}\left\lVert{\cal
A}^{*}(\mathbf{H}_{n})\right\rVert_{\rm
op}\left\lVert\Delta_{n+1}\right\rVert_{\ast}.$

Now, considering $\lambda_{n}\geq\frac{1}{n}\left\lVert{\cal
A}^{*}(\mathbf{H}_{n})\right\rVert_{\rm op}$ the following holds:

$\frac{1}{n}\left\lVert{\cal A}(\Delta_{n+1})\right\rVert_{\rm F}^{2}\leq
2\lambda_{n}\left\lVert\Delta_{n+1}\right\rVert_{\ast}.$ (13)

Relying on (Negahban and Wainwright, 2011, Lemma 1) we can decompose the error
matrix $\Delta_{n+1}$ as $\Delta_{n+1}^{\prime}+\Delta_{n+1}^{\prime\prime}$
such that $\Delta_{n+1}^{\prime}$ is of rank at most $2r$ and

$\left\lVert\Delta_{n+1}\right\rVert_{\ast}\leq
4\left\lVert\Delta_{n+1}^{\prime}\right\rVert_{\ast}.$ (14)

Assuming the RSC condition to be met with constant
$\kappa\left(\widehat{\overline{\mathbf{\Sigma}}}_{n}\right)$, starting from
equation (13) we get

$\left\lVert\Delta_{n+1}\right\rVert_{\rm F}^{2}\leq=\frac{\left\lVert{\cal
A}(\Delta_{n+1})\right\rVert_{\rm
F}^{2}}{2n\kappa\big{(}\widehat{\overline{\mathbf{\Sigma}}}_{n}\big{)}}\leq\frac{\lambda_{n}\
\left\lVert\Delta_{n+1}\right\rVert_{\ast}}{\kappa\left(\widehat{\overline{\mathbf{\Sigma}}}_{n}\right)}.$

These last two results combined with (Negahban and Wainwright, 2011, Lemma 1)
give that
$\left\lVert\Delta^{\prime}_{n+1}\right\rVert_{\ast}\leq\sqrt{2r}\left\lVert\Delta^{\prime}_{n+1}\right\rVert_{\rm
F}$, from which we conclude that

$\left\lVert\Delta_{n+1}\right\rVert_{\rm
F}\leq\frac{32\lambda_{n}\sqrt{r}}{\kappa\left(\widehat{\overline{\mathbf{\Sigma}}}_{n}\right)}.$

##  Appendix B PROOF OF PROPOSITION 1

###  B.1 Preliminary results

We consider the stochastic process $\\{\mathbf{M}_{n}\\}_{n\geq 0}$ defined as
$\mathbf{M}_{0}=0$ a.s. and for any $n\geq 1$

$\mathbf{M}_{n}=\sum_{t=1}^{T}\mathbf{x}_{t,n}\otimes\mathbf{x}_{t,n}-\mathbb{E}\left[\mathbf{x}_{t,n}\otimes\mathbf{x}_{t,n}|\overline{\mathcal{F}}_{n-1}\right].$

By definition of the Trace-Norm bandit (Algorithm 1), $\\{M_{n}\\}_{n\geq 0}$
is a $\overline{\mathcal{F}}_{n-1}$-martingale. Furthermore, given the past
history $\overline{\mathcal{F}}_{n-1}$, we select at round $n$ for each task
$t$ the arm $\mathbf{x}_{t,n}\in\mathcal{D}_{t,n}$ where the sets
$\mathcal{D}_{t,n}$, $t\in[T]$, are mutually independent. This means that the
arms $\mathbf{x}_{t,n}$, $t\in[T]$, are mutually independent given the past
history $\overline{\mathcal{F}}_{n-1}$.

Next, we use a standard argument to control the operator norm of
$\mathbb{M}_{n}$. Fix $\epsilon\in(0,1/2)$. An $\epsilon$-net
$\mathcal{N}_{\epsilon}$ of $\mathbb{S}^{d}$ is a subset of $\mathbb{S}^{d}$
such that for any $\mathbf{u}\in\mathbb{S}^{d}$, there exists
$\mathbf{v}\in\mathcal{N}_{\epsilon}$ such that
$\|\mathbf{u}-\mathbf{v}\|\leq\epsilon$. Corollary 4.2.13 in Vershynin (2018)
guarantees the existence of an $\epsilon$-net $\mathcal{N}_{\epsilon}$ of
$\mathbb{S}^{d}$ such that

$\displaystyle|\mathcal{N}_{\epsilon}|\leq\left(1+\frac{2}{\epsilon}\right)^{d}.$
(15)

Similarly to the first step of the proof of Theorem 4.4.5 in Vershynin (2018),
we get

$\displaystyle\left\lVert\mathbf{M}_{n}\right\rVert_{\rm
op}\leq\frac{1}{1-2\epsilon}\max_{\mathbf{u}\in\mathcal{N}_{\epsilon}}\left\\{\langle\mathbf{M}_{n}\mathbf{u},\mathbf{u}\rangle\right\\}\leq\frac{1}{1-2\epsilon}\max_{\mathbf{u}\in\mathcal{N}_{\epsilon}}\left\\{\sum_{t=1}^{T}\langle\mathbf{x}_{t,n},u\rangle^{2}-\mathbb{E}[\langle\mathbf{x}_{t,n},u\rangle^{2}|\overline{\mathcal{F}}_{n-1}]\right\\}.$
(16)

In view of Assumption 1, we have
$\langle\mathbf{x}_{t,n},u\rangle=\langle\mathbf{z}_{t,n},\mathbf{\Sigma}_{k}^{1/2}\mathbf{u}\rangle$
and
$\mathbb{E}[\langle\mathbf{x}_{t,n},\mathbf{u}\rangle^{2}|\overline{\mathcal{F}}_{n-1}]=\langle\mathbf{\Sigma}_{k(t)}\mathbf{u},\mathbf{u}\rangle$
for some $k(t)\in[K]$. We apply now the Hanson-Wright’s inequality
conditionally on $\overline{\mathcal{F}}_{n-1}$ to get for any $x>0$

$\displaystyle\mathbb{P}\left(\sum_{t=1}^{T}\langle\mathbf{z}_{t,n},\mathbf{\Sigma}_{k(t)}^{1/2}\mathbf{u}\rangle^{2}-\langle\mathbf{\Sigma}_{k(t)}\mathbf{u},\mathbf{u}\rangle\geq
C\left(\sqrt{T\,\max_{k\in[K]}\\{\left\lVert\mathbf{\Sigma}_{k}^{1/2}\mathbf{u}\otimes\mathbf{u}\mathbf{\Sigma}_{k}^{1/2}\right\rVert_{F}^{2}\\}\,x}+\max_{k\in[K]}\\{\left\lVert\mathbf{\Sigma}_{k}\mathbf{u}\otimes\mathbf{u}\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\\}\,x\right)|\overline{\mathcal{F}}_{n-1}\right)\leq e^{-x},$

where $C>0$ is a numerical constant which can depend only on $C_{\mathbf{z}}$.
Note that
$\left\lVert\mathbf{\Sigma}_{k}^{1/2}\mathbf{u}\otimes\mathbf{u}\mathbf{\Sigma}_{k}^{1/2}\right\rVert_{F}=\left\lVert\mathbf{\Sigma}_{k}^{1/2}\mathbf{u}\otimes\mathbf{u}\mathbf{\Sigma}_{k}^{1/2}\right\rVert_{\rm
op}\left\lVert\mathbf{u}\right\rVert^{2}\leq\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}$. Hence we get for any $x>0$

$\displaystyle\mathbb{P}\left(\sum_{t=1}^{T}\langle\mathbf{z}_{t,n},\mathbf{\Sigma}_{k(t)}\mathbf{u}\rangle^{2}-\langle\mathbf{\Sigma}_{k(t)}\mathbf{u},\mathbf{u}\rangle\geq
C\max_{k\in[K]}\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\\}\left(\sqrt{T\,x}+x\right)|\overline{\mathcal{F}}_{n-1}\right)\leq
e^{-x}.$

We define now the event

$\Omega_{n}=\bigcap_{\mathbf{u}\in\mathcal{N}_{\epsilon}}\left\\{\left|\langle\mathbf{M}_{n}\mathbf{v},\mathbf{u}\rangle\right|\leq
C\max_{k\in[K]}\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\\}\left(\sqrt{T\,x}+x\right)\right\\}.$

Set $\epsilon=1/4$. A simple union bound combining (15) with the last two
displays gives

$\mathbb{P}\left(\Omega_{n}^{c}\right)\leq|\mathcal{N}_{\epsilon}|\,e^{-t^{\prime}}\leq
2e^{d\log(9)-x}.$

Now we set $x=\log(4\delta^{-1})+d\log(9)$ for some $\delta\in(0,1)$.
Consequently, we obtain that

$\mathbb{P}\left(\Omega_{n}\right)\geq 1-\delta/4.$

It follows, in view of (C.1), with probability at least $1-\delta$

$\displaystyle\left\lVert\mathbf{M}_{n}\right\rVert_{\rm op}\leq
C^{\prime}\max_{k\in[K]}\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\\}\left(\sqrt{T\,(d+\log(4\delta^{-1}))}+d+\log(4\delta^{-1})\right),$
(17)

for some numerical constant $C^{\prime}>0$ that can depend only on
$C_{\mathbf{z}}$.

We note that

$\left\lVert\sum_{t=1}^{T}\mathbb{E}\left[\mathbf{x}_{t,n}\otimes\mathbf{x}_{t,n}|\overline{\mathcal{F}}_{n-1}\right]\right\rVert_{\rm
op}\leq T\max_{k}\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm op}\\},$

since
$\sum_{t=1}^{T}\mathbb{E}\left[\mathbf{x}_{t,n}\otimes\mathbf{x}_{t,n}|\overline{\mathcal{F}}_{n-1}\right]=\sum_{t=1}^{T}\mathbf{\Sigma}_{k(t)}$,
where $k(t)\in[K]$. Combining this observation with (17), we prove that the
following event

$\displaystyle\Omega_{n}=\left\\{\left\lVert\sum_{t=1}^{T}\mathbf{x}_{t,n}\otimes\mathbf{x}_{t,n}\right\rVert_{\rm
op}\leq\max_{k\in[K]}\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\\}\left(T+C^{\prime}\left(\sqrt{T\,(d+\log(4N\delta^{-1}))}+d+\log(4N\delta^{-1})\right)\right)\right\\}$
(18)

satisfies $\mathbb{P}(\Omega_{n})\geq 1-\delta/(4N)$. Next we also introduce
the event

$\displaystyle\overline{\Omega}_{n}=\bigcap_{l=0}^{n}\Omega_{l}\in\overline{\mathcal{F}}_{n},$
(19)

with $\Omega_{0}$ being the whole sample space. The Bayes rule gives

$\displaystyle\mathbb{P}\left(\overline{\Omega}_{N}\right)=\prod_{n=1}^{N}\mathbb{P}\left({\Omega}_{n}\big{|}\bigcap_{k=0}^{n-1}{\Omega}_{k}\right)\geq\left(1-\frac{\delta}{4N}\right)^{N}.$

Bernoulli’s inequality ($(1+x)^{n}\geq 1+nx$ for any $x>-1$ and integer $n\geq
1$) gives

$\displaystyle\mathbb{P}\left(\overline{\Omega}_{N}\right)=\prod_{n=1}^{N}\mathbb{P}\left({\Omega}_{n}\big{|}\bigcap_{k=0}^{n-1}{\Omega}_{k}\right)\geq
1-\frac{\delta}{4}.$ (20)

Define for any $n\in[N]$ the events

$\displaystyle\Omega_{n}^{\prime}=\bigcap_{t=1}^{T}\left\\{|\eta_{t,n}|\leq
c_{\eta}\sqrt{\log(8TN\delta^{-1})}\right\\},$ (21)

and

$\displaystyle\overline{\Omega}_{n}^{\prime}=\bigcap_{l=0}^{n}\Omega_{l}^{\prime},$
(22)

with $\Omega^{\prime}_{0}$ being the whole sample space.

Assumption 4 guarantees that for any $\delta\in(0,1)$, with probability at
least $1-\delta$

$\displaystyle\mathbb{P}\left(\Omega_{n}^{\prime}\big{|}\overline{\mathcal{F}}_{n-1}\right)\geq
1-\frac{\delta}{4N}.$ (23)

and

$\displaystyle\mathbb{P}\left(\overline{\Omega}_{N}^{\prime}\big{|}\overline{\mathcal{F}}_{N-1}\right)\geq
1-\frac{\delta}{4}.$ (24)

###  B.2 Main proof

##### Checking the martingale structure.

Let us define the stochastic process $(\mathbf{D}_{n})_{n\geq 0}$ as
$\mathbf{D}_{0}=0$ a.s. and

$\displaystyle\mathbf{D}_{n}:=\sum_{t=1}^{T}\sum_{i=1}^{n}\eta_{t,i}\,\mathbf{x}_{t,i}\mathbf{e}^{\top}_{t}\in\mathbb{R}^{d\times
T}.$ (25)

By definition of the Trace-Norm bandit (Algorithm 1), given the past history
$\overline{\mathcal{F}}_{n-1}$, we select at round $n$ the arms for the T
tasks: $\mathbf{x}_{t,n}\in\mathcal{D}_{t,n}$ with $\mathcal{D}_{t,n}$
independent of $(\eta_{t,n})_{1\leq t\leq T}$. This means that

$(\mathbf{x}_{t,n})_{1\leq t\leq T}\perp\\!\\!\\!\perp(\eta_{t,n})_{1\leq
t\leq T}\bigg{|}\overline{\mathcal{F}}_{n-1}.$

Consequently, under Assumption 1 and 4, $(\mathbf{D}_{n})_{n\geq 0}$ is a
square-root integrable martingale adapted to the filtration
$\\{\overline{\mathcal{F}}_{n}\\}_{n\geq 0}$.

We would like to apply the Freedman inequality for matrix martingales (Tropp,
2011, Corollary 1.3 ). However this result is for bounded martingales.
Therefore it is not directly applicable to $(\mathbf{D}_{n})_{n\geq 0}$. To
remedy this difficulty. We introduce the following stopping times:

$\displaystyle\tau_{1}$ $\displaystyle=\inf\left\\{n\geq
0\,:\,\left\lVert\sum_{t=1}^{T}\mathbf{x}_{t,n}\otimes\mathbf{x}_{t,n}\right\rVert_{\rm
op}\geq\max_{k\in[K]}\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\\}\left(T+C^{\prime}\left(\sqrt{T\,(d+\log(4N\delta^{-1}))}+d+\log(4N\delta^{-1})\right)\right)\right\\},$
(26)

and

$\displaystyle\tau_{2}=\inf\left\\{n\geq
0\,:\,\min_{t\in[T]}\left\\{|\eta_{t,n}|\right\\}\geq
c_{\eta}\sigma\sqrt{\log(8TN\delta^{-1}))}\right\\}.$ (27)

Again by definition of the Trace-Norm bandit and assumptions on the noise,
$\tau_{1}$ and $\tau_{2}$ are both stopping times relative to the filtration
$\\{\overline{\mathcal{F}}_{n}\\}_{n\geq 0}$, so is
$\tau=\tau_{1}\wedge\tau_{2}$. Hence the stopped process
$\\{\mathbf{D}^{\tau}_{n}\\}_{n\geq 0}$ defined as
$\mathbf{D}^{\tau}_{n}=\mathbf{D}_{n\wedge\tau}$ is also a martingale adapted
to the filtration $\\{\overline{\mathcal{F}}_{n}\\}_{n\geq 0}$. Furthermore
$\\{\mathbf{D}^{\tau}_{n}\\}_{n\geq 0}$ is a bounded martingale. Hence we can
apply the Freedman inequality to it.

By definition of $\tau_{1}$ and (19), we have
$\\{\tau_{1}>N\\}=\overline{\Omega}_{N}$. Similarly for $\tau_{2}$ in view of
(22), we have $\\{\tau_{2}>N\\}=\overline{\Omega}^{\prime}_{N}$. Hence

$\displaystyle\mathbb{P}\left(\left\lVert\mathbf{D}_{n}\right\rVert_{\rm
op}\geq t\right)$ $\displaystyle=\mathbb{P}\left(\\{\mathbf{D}_{n}\geq
t\\}\cap\\{\tau>N\\}\right)+\mathbb{P}\left(\\{\left\lVert\mathbf{D}_{n}\right\rVert_{\rm
op}\geq t\\}\cap\\{\tau\leq N\\}\right)$
$\displaystyle\leq\mathbb{P}\left(\left\lVert\mathbf{D}^{\tau}_{n}\right\rVert_{\rm
op}\geq t\right)+\mathbb{P}\left(\\{\tau_{1}\leq N\\}\cup\\{\tau_{2}\leq
N\\}\right)$
$\displaystyle=\mathbb{P}\left(\left\lVert\mathbf{D}^{\tau}_{n}\right\rVert_{\rm
op}\geq t\right)+\mathbb{P}\left(\tau_{1}\leq
N\right)+\mathbb{P}\left(\tau_{2}\leq N\right)$
$\displaystyle\leq\mathbb{P}\left(\left\lVert\mathbf{D}^{\tau}_{n}\right\rVert_{\rm
op}\geq t\right)+\delta/2,$ (28)

where we have used (20) and (24) in the last line.

##### Application of Freedman’s inequality.

We now use (Tropp, 2011, Corollary 1.3) to control
$\\{\mathbf{D}^{\tau}_{n}\\}_{n\geq 0}$.

######  Theorem 2 (Corollary 1.3 in Tropp (2011)).

Consider a matrix martingale $\\{\bm{Y}_{n}:n=0,1,2,\dots\\}$ whose values are
matrices with dimension $d_{1}\times d_{2}$, and let
$\\{\bm{X}_{k}:n=1,2,3,\dots\\}$ be the difference sequence. Assume that the
difference sequence is uniformly bounded:

$\left\lVert\bm{X}_{n}\right\rVert_{\rm op}\leq R\quad\text{almost
surely}\quad\text{for $n=1,2,3,\dots$}.$

Define two predictable quadratic variation processes for this martingale:

$\displaystyle\bm{W}_{{\rm col},\,k}$
$\displaystyle:=\sum\nolimits_{j=1}^{n}\operatorname{\mathbb{E}}_{j-1}\big{(}\bm{X}_{j}\bm{X}_{j}^{*}\big{)}\quad\text{and}$
$\displaystyle\bm{W}_{{\rm row},\,k}$
$\displaystyle:=\sum\nolimits_{j=1}^{n}\operatorname{\mathbb{E}}_{j-1}\big{(}\bm{X}_{j}^{*}\bm{X}_{j}\big{)}\quad\text{for
$n=1,2,3,\dots$}.$

Then, for all $t\geq 0$ and $\overline{\sigma}^{2}>0$,

$\mathbb{P}\left(\exists n\geq 0:\left\lVert\bm{Y}_{n}\right\rVert\geq t\text{
and }\ \max\\{\left\lVert\bm{W}_{{\rm col},\,n}\right\rVert_{\rm
op},\left\lVert\bm{W}_{{\rm row},\,n}\right\rVert_{\rm
op}\\}\leq\overline{\sigma}^{2}\right)\leq(d_{1}+d_{2})\cdot\exp\left\\{-\frac{-t^{2}/2}{\overline{\sigma}^{2}+Rt/3}\right\\}.$

We now check the conditions of Theorem 2. In view of (18)-(19) and (21)-(22),
we have on the event $\\{\tau>N\\}=\\{\tau_{1}>N\\}\cap\\{\tau_{2}>N\\}$, for
any $n\in[N]$,

$\displaystyle\left\lVert\sum_{t=1}^{T}\eta_{t,n}\mathbf{x}_{t,n}\otimes\mathbf{e}_{t}\right\rVert_{\rm
op}$
$\displaystyle=\sqrt{\left\lVert\left(\sum_{t=1}^{T}\eta_{t,n}\mathbf{x}_{t,n}\otimes\mathbf{e}_{t}\right)\left(\sum_{t=1}^{T}\eta_{t,n}\mathbf{e}_{t}\otimes\mathbf{x}_{t,n}\right)\right\rVert_{\rm
op}}$
$\displaystyle=\sqrt{\left\lVert\sum_{t=1}^{T}\eta_{t,n}^{2}\mathbf{x}_{t,n}\otimes\mathbf{x}_{t,n}\right\rVert_{\rm
op}}\leq\max_{t\in[T]}\\{|\eta_{t,n}|\\}\sqrt{\left\lVert\sum_{t=1}^{T}\mathbf{x}_{t,n}\otimes\mathbf{x}_{t,n}\right\rVert_{\rm
op}}$ $\displaystyle\leq
c_{\eta}\sqrt{\log(8TN\delta^{-1})}\sqrt{\max_{k\in[K]}\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\\}\left(T+C^{\prime}\left(\sqrt{T\,(d+\log(4N\delta^{-1}))}+d+\log(4N\delta^{-1})\right)\right)}$
$\displaystyle\leq
c_{\eta}\sqrt{1+C^{\prime}/2}\sqrt{\log(8TN\delta^{-1})}\sqrt{\max_{k\in[K]}\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\\}\left(T+d+\log(4N\delta^{-1})\right)}.$

Next we have

$\displaystyle\bm{W}_{{\rm col}}$
$\displaystyle=\sum_{s=1}^{n}\mathbb{E}\left[\sum_{t=1}^{T}\sum_{s=1}^{n}\eta_{t,s}^{2}\mathbf{x}_{t,s}\otimes\mathbf{x}_{t,s}|\overline{\mathcal{F}}_{s-1}\right]=\sigma^{2}\sum_{t=1}^{T}\sum_{s=1}^{n}\mathbf{\Sigma}_{k(t,s)},$

where $k(t,s)\in[K]$ for any $t,s$. Hence

$\left\lVert\bm{W}_{{\rm col}}\right\rVert_{\rm op}\leq
Tn\,\sigma^{2}\max_{k\in[K]}\left\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\right\\}.$

We proceed similarly for $\bm{W}_{{\rm row}}$

$\displaystyle\bm{W}_{{\rm row}}$
$\displaystyle=\sum_{s=1}^{n}\mathbb{E}\left[\sum_{t=1}^{T}\sum_{s=1}^{n}\eta_{t,s}^{2}\left\lVert\mathbf{x}_{t,s}\right\rVert^{2}\mathbf{e}_{t}\otimes\mathbf{e}_{t}|\overline{\mathcal{F}}_{s-1}\right]\leq
n\sigma^{2}\max_{k\in[K]}\left\\{\mathrm{tr}(\mathbf{\Sigma}_{k})\right\\}I_{T}.$

Hence, we get

$\displaystyle\left\lVert\bm{W}_{{\rm row}}\right\rVert_{\rm op}$
$\displaystyle\leq
n\sigma^{2}\max_{k\in[K]}\left\\{\mathrm{tr}(\Sigma_{k})\right\\}\leq
nd\,\sigma^{2}\,\max_{k\in[K]}\left\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\right\\}.$

Define the event

$\displaystyle A_{n}=\left\\{\frac{\left\lVert\mathbf{D}_{n}\right\rVert_{\rm
op}}{n}\leq\max_{k\in[K]}\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}^{1/2}\\}\left(\sigma\sqrt{\frac{(d+T)\,(\log(2\delta^{-1}N(d+T)))}{n}}\right.\right.$
$\displaystyle\left.\hskip
56.9055pt\bigvee\frac{c_{\eta}\sqrt{1+C^{\prime}/2}\sqrt{\log(8TN\delta^{-1})}\sqrt{\left(T+d+\log(4N\delta^{-1})\right)}\,(\log(2\delta^{-1}N(d+T)))}{n}\right\\}.$

Applying Theorem 2, we get for any $t>0$

$\displaystyle\mathbb{P}\left(A_{n}^{c}|\bar{\Omega}_{n}\right)\leq\frac{\delta}{2N}.$
(29)

An elementary argument combining the previous display with (C.4) gives

$\mathbb{P}\left(A_{n}^{c}\right)=\mathbb{P}\left(A_{n}^{c}\cap\bar{\Omega}_{n}\right)+\mathbb{P}\left(A_{n}^{c}\cap\bar{\Omega}_{n}^{c}\right)\leq\mathbb{P}\left(A_{n}^{c}|\bar{\Omega}_{n}\right)+\mathbb{P}\left(\bar{\Omega}_{n}^{c}\right)\leq\frac{\delta}{N}.$

From the previous display and an union bound, we immediately deduce, with
probability at least $1-\delta$,

$\displaystyle\max_{1\leq n\leq
N}\frac{\left\lVert\mathbf{D}_{n}\right\rVert_{\rm
op}}{n}\leq\max_{k\in[K]}\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}^{1/2}\\}\left(\sigma\sqrt{\frac{(d+T)\,(\log(2\delta^{-1}N(d+T)))}{n}}\right.$
$\displaystyle\left.\hskip
56.9055pt\bigvee\frac{c_{\eta}\sqrt{1+C^{\prime}/2}\sqrt{\left(T+d+\log(4N\delta^{-1})\right)}\,(\log^{3/2}(8\delta^{-1}N(d+T)))}{n}\right).$
(30)

##  Appendix C PROOF OF PROPOSITION 2

###  C.1 Concentration bounds on the arms covariance.

For every $t\in[T]$, we recall that the empirical covariance matrix for task
$t$ as

$\widehat{\mathbf{\Sigma}}_{t,n}=\frac{1}{n}\sum_{i=1}^{n}\mathbf{x}_{t,i}\mathbf{x}_{t,i}^{\top}$
(31)

and the corresponding adapted covariance matrix (w.r.t. the filtration
$(\overline{\mathcal{F}}_{n})_{n\geq 0}$) as

$\mathbf{\Sigma}_{t,n}{=}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[\mathbf{x}_{t,i}\mathbf{x}_{t,i}^{\top}\Big{|}\overline{\mathcal{F}}_{i-1}\right].$
(32)

Here adapted means that the covariance matrix $\mathbf{\Sigma}_{t,n}$ is fully
known at time $n$ since it depends only on the past history
$\overline{\mathcal{F}}_{n-1}$.

Moreover, we use the notation
$\overline{\mathbf{\Sigma}},\widehat{\overline{\mathbf{\Sigma}}}_{n},\overline{\mathbf{\Sigma}}_{n}\in\mathbb{R}^{dT\times
dT}$ for the theoretical, the empirical and the adapted multi-task matrices,
respectively. They are all block diagonal and composed by the corresponding
$T$ single task $d\times d$ matrices on the diagonal (e.g.
$\overline{\mathbf{\Sigma}}_{n}={\rm
diag}(\overline{\mathbf{\Sigma}}_{1,n},\dots,\overline{\mathbf{\Sigma}}_{T,n})$).

The following lemma gives a high probability bound on the deviation of
$\widehat{\overline{\mathbf{\Sigma}}}_{n}$ from
$\overline{\mathbf{\Sigma}}_{n}$ according to the operator norm restricted to
the cone $\mathcal{C}_{r}$ defined in (7). We define for any symmetric
$dT\times dT$ matrix $A$

$\left\lVert
A\right\rVert_{\rm{op},\mathcal{C}_{r}}=\max_{\mathbf{\Delta}\in\mathcal{C}_{r}\,:\,\left\lVert\mathbf{\Delta}\right\rVert_{F}=1}\left\\{\langle
A\rm{Vec}(\mathbf{\Delta}),\rm{Vec}(\mathbf{\Delta})\rangle\right\\}.$

######  Lemma 2 (Concentration).

Let Assumption 1 be satisfied. For any $n\geq 1$ and $\delta\in(0,1)$, with
probability at least $1-\delta$, for any $n\in[N]$

$\displaystyle\left\lVert\widehat{\overline{\mathbf{\Sigma}}}_{n}-\overline{\mathbf{\Sigma}}_{n}\right\rVert_{\rm{op},\mathcal{C}_{r}}$
$\displaystyle\leq C\max_{1\leq k\leq
K}\left\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\right\\}r\left(\frac{(1+\log(4NT\delta^{-1}))\log^{2}(d)}{\sqrt{n}}+\frac{(1+\log(4NT\delta^{-1}))^{2}\log^{2}(d)}{n}\right).$
(33)

for some constant $C=C(C_{\mathbf{z}})>0$.

###### Proof.

For any $n\in[N]$, we define the $dT\times dT$ block-diagonal matrix

$\mathbf{M}_{n}:=\mathrm{diag}(\mathbf{M}_{1,n},\ldots,\mathbf{M}_{T,n}),$

where the diagonal $d\times d$ diagonal block matrices are defined as follows:

$\displaystyle\mathbf{M}_{t,n}:=n\left(\widehat{\mathbf{\Sigma}}_{t,n}-\mathbf{\Sigma}_{t,n}\right)=\sum_{s=1}^{n}\mathbf{x}_{t,s}\mathbf{x}^{\top}_{t,s}-\mathbb{E}\left[\mathbf{x}_{t,s}\mathbf{x}^{\top}_{t,s}\Big{|}\overline{\mathcal{F}}_{s-1}\right].$
(34)

We also set $\mathbf{M}_{0}=\mathbf{0}_{dT\times dT}$ a.s. By construction
$(\mathbf{M}_{n})_{n\geq 0}$ is a
$\\{\overline{\mathcal{F}}_{n}\\}_{n}$-martingale satisfying

$\displaystyle\left\lVert\mathbf{M}_{n}\right\rVert_{\rm{op},\mathcal{C}_{r}}=\max_{\mathbf{\Delta}\in\mathcal{C}_{r}\,:\,\left\lVert\mathbf{\Delta}\right\rVert_{F}=1}\left\\{\langle\mathbf{M}_{n}\rm{Vec}(\mathbf{\Delta}),\rm{Vec}(\mathbf{\Delta})\rangle\right\\}=\max_{\mathbf{\Delta}\in\mathcal{C}_{r}\,:\,\left\lVert\mathbf{\Delta}\right\rVert_{F}=1}\left\\{\sum_{t=1}^{T}\langle\mathbf{M}_{t,n}\mathbf{\Delta}_{t},\mathbf{\Delta}_{t}\rangle\right\\}.$
(35)

We derive several geometric properties of matrices in the cone
$\mathcal{C}_{r}$. We then exploit these properties via an improved union
bound argument to derive a sharper uniform deviation bound of the martingale
$(\mathbf{M}_{n})_{n\geq 0}$ on the cone $\mathcal{C}_{r}$ as compared to the
standard operator norm bound on the whole space of $d\times T$ matrices.

##### Uniform deviation bound on
$\langle\mathbf{M}_{t,n}\mathbf{u},\mathbf{v}\rangle$ for vectors $\mathbf{u}$
$\mathbf{v}$ in lower-dimensional balls.

We consider two linear subspaces $\mathbf{U}$, $\mathbf{V}$ of
$\mathbb{R}^{d}$ of respective dimension $d_{\mathbf{U}}$ and
$d_{\mathbf{V}}$. We then introduce the ball
$B_{\mathbf{U}}(0,r_{\mathbf{U}})\in\mathbf{U}$ centered at $0$ of radius
$r_{\mathbf{U}}$. We define similarly the ball
$B_{\mathbf{V}}(0,r_{\mathbf{V}})\in\mathbf{V}$. Fix $\mathbf{u}\in
B_{\mathbf{U}}(0,r_{\mathbf{U}})$ and $\mathbf{v}\in
B_{\mathbf{V}}(0,r_{\mathbf{V}})$. We consider now the
$\\{\overline{\mathcal{F}}_{n}\\}_{n}$-martingale
$(\langle\mathbf{M}_{t,n}\mathbf{u},\mathbf{v}\rangle)_{n\geq 0}$. Note that

$\displaystyle\max_{\mathbf{u}\in
B_{\mathbf{U}}(0,r_{\mathbf{U}}),\mathbf{v}\in
B_{\mathbf{V}}(0,r_{\mathbf{V}})}{\langle\mathbf{M}_{t,n}\mathbf{u},\mathbf{v}\rangle}\leq
r_{\mathbf{U}}\,r_{\mathbf{V}}\max_{\mathbf{u}\in
B_{\mathbf{U}}(0,1),\mathbf{v}\in
B_{\mathbf{V}}(0,1)}{\langle\mathbf{M}_{t,n}\mathbf{u},\mathbf{v}\rangle}\leq
r_{\mathbf{U}}\,r_{\mathbf{V}}\left\lVert
P_{\mathbf{U}}\mathbf{M}_{t,n}P_{\mathbf{V}}\right\rVert_{\rm op}.$ (36)

Using Lemma 4 with $\delta$ replaced by $\delta/(2T)$. gives with probability
at least $1-\delta$, for any $n\in[N]$ and any $t\in[T]$

$\displaystyle\max_{\mathbf{u}\in
B_{\mathbf{U}}(0,r_{\mathbf{U}}),\mathbf{v}\in
B_{\mathbf{V}}(0,r_{\mathbf{V}})}{\left\langle\frac{\mathbf{M}_{t,n}}{n}\mathbf{u},\mathbf{v}\right\rangle}$
$\displaystyle\hskip 28.45274pt\leq
Cr_{\mathbf{U}}\,r_{\mathbf{V}}\max_{k\in[K]}\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\\}\biggl{(}\sqrt{\frac{\bigl{(}d_{\mathbf{U}}\vee
d_{\mathbf{V}}+\log(4NT\delta^{-1})\bigr{)}\log(8NT\delta^{-1}d)}{n}}$
$\displaystyle\hskip
170.71652pt+\frac{\sqrt{\left(d_{\mathbf{U}}+\log(4NT\delta^{-1})\right)\left(d_{\mathbf{V}}+\log(4NT\delta^{-1}d)\right)}\log(4NT\delta^{-1})}{n}\biggr{)}.$
(37)

##### Geometric properties of $\mathcal{C}_{r}$.

Set $\bar{r}=\mathrm{rank}(\mathbf{\Delta})$. Note that $\bar{r}\leq d\wedge
T$. Taking the SVD of $\mathbf{\Delta}$, we have

$\mathbf{\Delta}=\sum_{j=1}^{\bar{r}}\sigma_{j}(\mathbf{\Delta})\mathbf{u}_{j}(\mathbf{\Delta})\otimes\mathbf{v}_{j}(\mathbf{\Delta}),$

with singular values
$\sigma_{1}(\mathbf{\Delta})\geq\sigma_{2}(\mathbf{\Delta})\geq\cdots\geq\sigma_{\bar{r}}(\mathbf{\Delta})>0$
and orthonormal families
$\\{\mathbf{u}_{j}(\mathbf{\Delta})\\}_{j=1}^{\bar{r}}\in\mathbb{R}^{d}$,
$\\{\mathbf{v}_{j}(\mathbf{\Delta})\\}_{j=1}^{\bar{r}}\in\mathbb{R}^{T}$. For
the sake of brevity, we set $\sigma_{j}(\mathbf{\Delta})=\sigma_{j}$,
$\mathbf{u}_{j}(\mathbf{\Delta})=\mathbf{u}_{j}$ and
$\mathbf{v}_{j}(\mathbf{\Delta})=\mathbf{v}_{j}$ for any $j\in[\bar{r}]$. From
the previous displays, we immediately get the following representation for the
columns of $\mathbf{\Delta}$:

$\displaystyle\mathbf{\Delta}_{t}=\sum_{j=1}^{\bar{r}}\sigma_{j}\mathbf{v}_{j,t}\mathbf{u}_{j},\quad\forall
t\in{T},$ (38)

where $\mathbf{v}_{j}$ admits components
$\mathbf{v}_{j}=(\mathbf{v}_{j,1},\cdots,\mathbf{v}_{j,T})^{\top}$.

By definition of the cone $\mathcal{C}_{r}$ in (7), for any
$\mathbf{\Delta}\in\mathcal{C}_{r}$, we have
$\left\lVert\Pi(\mathbf{\Delta})\right\rVert_{*}\leq
3\left\lVert\mathbf{\Delta}-\Pi(\mathbf{\Delta})\right\rVert_{*}$. Note that
$\mathrm{rank}(\mathbf{\Delta}-\Pi(\mathbf{\Delta}))\leq 2r$ by definition of
$\Pi$ and the cone $\mathcal{C}_{r}$. Hence we have, for any
$\mathbf{\Delta}\in\mathcal{C}_{r}$ with
$\left\lVert\mathbf{\Delta}\right\rVert_{F}=1$,

$\displaystyle\left\lVert\mathbf{\Delta}\right\rVert_{*}\leq\left\lVert\Pi(\mathbf{\Delta})\right\rVert_{*}+\left\lVert\mathbf{\Delta}-\Pi(\mathbf{\Delta})\right\rVert_{*}\leq
4\left\lVert\mathbf{\Delta}-\Pi(\mathbf{\Delta})\right\rVert_{*}\leq
4\sqrt{2r}\left\lVert\mathbf{\Delta}-\Pi(\mathbf{\Delta})\right\rVert_{F}\leq
4\sqrt{2r}\left\lVert\mathbf{\Delta}\right\rVert_{F}=4\sqrt{2r}.$ (39)

We deduce from (39) that $\sum_{j=1}^{\bar{r}}\sigma_{j}\leq 4\sqrt{2r}$ and
consequently for any $\mathbf{\Delta}\in\mathcal{C}_{r}$

$\displaystyle\sigma_{j}(\mathbf{\Delta})\leq\frac{4\sqrt{2r}}{j},\quad\forall
j\in[\bar{r}].$ (40)

We conclude this paragraph with some elementary facts on orthonormal basis. We
complete the orthonormal family $\\{\mathbf{v}_{j}\\}_{j=1}^{\bar{r}}$ into an
orthonormal basis $\\{\mathbf{v}_{j}\\}_{j=1}^{T}$ of $\mathbb{R}^{T}$. By
properties of orthonormal basis, we have
$\langle\mathbf{v}_{j},\mathbf{v}_{j^{\prime}}\rangle=\sum_{t=1}^{T}\mathbf{v}_{j,t}\mathbf{v}_{j^{\prime},t}=\delta_{j,j^{\prime}}$
where $\delta_{j,j^{\prime}}=1$ if $j=j^{\prime}$ and $0$ otherwise.

##### Uniform bound over $\mathbf{\Delta}\in\mathcal{C}_{r}$.

Our goal is to control
$\left\lVert\mathbf{M}_{n}\right\rVert_{\rm{op},\mathcal{C}_{r}}$. To this
end, we set $m_{*}=\lceil\log_{2}(d\wedge T)\rceil$ and, for any
$m\in[m_{*}]$, define $J_{m}=\\{j\in[m_{*}]\,:\,2^{m-1}\leq j<2^{m}\\}$. Next
we propose the following decomposition of $\mathbf{\Delta}$:

$\mathbf{\Delta}_{t}=\sum_{m=1}^{m_{*}}\mathbf{\Delta}_{t,m},\quad\text{where}\quad\mathbf{\Delta}_{t,m}=\sum_{j\in
J_{m}}\sigma_{j}\mathbf{v}_{j,t}\mathbf{u}_{j},\quad\forall t\in[T].$

By construction and (40), for any $m\in[m_{*}]$, all the vectors
$\mathbf{\Delta}_{t,m}$, ${t\in[T]}$ live in the same subspace of dimension at
most $2^{m-1}$ and

$\left\lVert\mathbf{\Delta}_{t,m}\right\rVert^{2}\leq\sigma^{2}_{2^{m-1}}\sum_{j\in
J_{m}}\mathbf{v}^{2}_{j,t}\leq\sigma^{2}_{2^{m-1}}\leq\frac{32r}{2^{2(m-1)}},$

and

$\displaystyle\sum_{t=1}^{T}\left\lVert\mathbf{\Delta}_{t,m}\right\rVert^{2}\leq\sigma^{2}_{2^{m-1}}\sum_{j\in
J_{m}}\sum_{t=1}^{T}\mathbf{v}^{2}_{j,t}\leq\sigma^{2}_{2^{m-1}}|J_{m}|\leq\frac{32r}{2^{(m-1)}}.$
(41)

Combining the last two displays with (38), we get that

$\displaystyle\sum_{t=1}^{T}\langle\mathbf{M}_{t,n}\mathbf{\Delta}_{t},\mathbf{\Delta}_{t}\rangle$
$\displaystyle=\sum_{t=1}^{T}\sum_{m,m^{\prime}=1}^{m_{*}}\langle\mathbf{M}_{t,n}\mathbf{\Delta}_{t,m},\mathbf{\Delta}_{t,m^{\prime}}\rangle.$
(42)

An union bound combining the last two displays with (35) and (C.1) gives for
any $\delta\in(0,1)$ with probability at least $1-\delta$, for any $n\in[N]$

$\displaystyle\frac{1}{n}\left\lVert\mathbf{M}_{n}\right\rVert_{\rm{op},\mathcal{C}_{r}}$
$\displaystyle\leq C\max_{1\leq k\leq
K}\left\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\right\\}\sum_{m,m^{\prime}=1}^{m_{*}}\sum_{t=1}^{T}\left\lVert\mathbf{\Delta}_{t,m}\right\rVert\left\lVert\mathbf{\Delta}_{t,m^{\prime}}\right\rVert\epsilon_{m,m^{\prime}},$

where

$\displaystyle\epsilon_{m,m^{\prime}}$
$\displaystyle=\sqrt{\frac{\bigl{(}2^{m\vee
m^{\prime}-1}+\log(4NT\delta^{-1})\bigr{)}\log(4NT\delta^{-1}d)}{n}}$
$\displaystyle\hskip
85.35826pt+\frac{\sqrt{\left(2^{m-1}+\log(4NT\delta^{-1})\right)\left(2^{m^{\prime}-1}+\log(4NT\delta^{-1}d)\right)}\log(4NT\delta^{-1})}{n}.$

The Cauchy-Schwartz inequality and (41) give

$\displaystyle\left\lVert\mathbf{M}_{n}\right\rVert_{\rm{op},\mathcal{C}_{r}}$
$\displaystyle\leq C\max_{1\leq k\leq
K}\left\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\right\\}\sum_{m,m^{\prime}=1}^{m_{*}}\left(\sum_{t=1}^{T}\left\lVert\mathbf{\Delta}_{t,m}\right\rVert^{2}\right)^{1/2}\left(\sum_{t=1}^{T}\left\lVert\mathbf{\Delta}_{t,m^{\prime}}\right\rVert^{2}\right)^{1/2}\epsilon_{m,m^{\prime}}$
$\displaystyle\leq 32C\max_{1\leq k\leq
K}\left\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\right\\}r\sum_{m,m^{\prime}=1}^{m_{*}}\frac{1}{2^{\frac{m-1}{2}}}\frac{1}{2^{\frac{m^{\prime}-1}{2}}}\epsilon_{m,m^{\prime}}.$

By definition of $\epsilon_{m,m^{\prime}}$, we have for any
$m,m^{\prime}\in[m_{*}]$

$\displaystyle\frac{1}{2^{\frac{m-1}{2}}}\frac{1}{2^{\frac{m^{\prime}-1}{2}}}\epsilon_{m,m^{\prime}}$
$\displaystyle\lesssim\frac{1+\log(4NT\delta^{-1})}{\sqrt{n}}+\frac{(1+\log(4NT\delta^{-1}))^{2}}{n}.$

Combining the last two displays with the fact that $m_{*}\lesssim\log(d)$, we
get for any $\delta\in(0,1)$ with probability at least $1-\delta$, for any
$n\in[N]$

$\displaystyle\frac{1}{n}\left\lVert\mathbf{M}_{n}\right\rVert_{\rm{op},\mathcal{C}_{r}}$
$\displaystyle\leq C\max_{1\leq k\leq
K}\left\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\right\\}r\left(\frac{(1+\log(4NT\delta^{-1}))\log^{2}(d)}{\sqrt{n}}+\frac{(1+\log(4NT\delta^{-1}))^{2}\log^{2}(d)}{n}\right).$

∎

###  C.2 RSC condition and Matrix perturbation

The next lemma guarantees that if the
$\left\lVert\cdot\right\rVert_{\mathrm{op},\mathcal{C}_{r}}$ metric between
two matrices is small enough and if one of these two matrices satisfies the
RSC condition, then the other matrix also satisfied the RSC condition.
Specifically, the next lemma links the RSC constant
$\kappa\big{(}\overline{\mathbf{\Sigma}}\big{)}$ associated to the multi-task
theoretical matrix, to the adapted one
$\kappa\big{(}\overline{\mathbf{\Sigma}}_{n}\big{)}$.

######  Lemma 3 (RSC condition and Random Matrices).

Let ${\bf\Sigma}_{0}$ and ${\bf\Sigma}_{1}$ be two $dT\times dT$ block-
diagonal matrices (with blocks matrices of size $d\times d$). Suppose that the
RSC condition is met for the covariance matrix ${\bf\Sigma}_{0}$ with constant
$\kappa\big{(}{\bf\Sigma}_{0}\big{)}$ and that
$\left\lVert{\bf\Sigma}_{0}-{\bf\Sigma}_{1}\right\rVert_{\mathrm{op},\mathcal{C}_{r}}\leq\widetilde{\lambda}$,
where

$\widetilde{\lambda}\leq\kappa\big{(}{\bf\Sigma}_{0}\big{)}.$

Then, the RSC condition is also met for the covariance matrix
${\bf\Sigma}_{1}$ with constant
$\kappa\big{(}{\bf\Sigma}_{1}\big{)}\geq\kappa\big{(}{\bf\Sigma}_{0}\big{)}/2$.
Moreover, for all $\mathbf{\Delta}\in\mathbb{R}^{d\times T}$ such that
$\mathbf{\Delta}\in\mathcal{C}(r)$ (see equation 8), we have

$\left\lVert\rm{Vec}(\mathbf{\Delta})\right\rVert_{{\bf\Sigma}_{0}}^{2}\leq
2\left\lVert\rm{Vec}(\mathbf{\Delta})\right\rVert_{{\bf\Sigma}_{1}}^{2}\leq
3\left\lVert\rm{Vec}(\mathbf{\Delta})\right\rVert_{{\bf\Sigma}_{0}}^{2}.$ (43)

The proof combines Definition 1 and the
$\left\lVert\cdot\right\rVert_{\mathrm{op},\mathcal{C}_{r}}$ metric closeness
$\left\lVert{\bf\Sigma}_{0}-{\bf\Sigma}_{1}\right\rVert_{\mathrm{op},\mathcal{C}_{r}}\leq\widetilde{\lambda}$.

###### Proof.

For any $\mathbf{\Delta}\in\mathcal{C}_{r}$, we have

$\displaystyle\left|\left\lVert\text{Vec}(\mathbf{\Delta})\right\rVert_{{\bf\Sigma}_{0}}^{2}-\left\lVert\text{Vec}(\mathbf{\Delta})\right\rVert_{{\bf\Sigma}_{1}}^{2}\right|$
$\displaystyle\leq\left\lVert{\bf\Sigma}_{0}{-}{\bf\Sigma}_{1}\right\rVert_{\mathrm{op},\mathcal{C}_{r}}\left\lVert\text{Vec}(\mathbf{\Delta})\right\rVert_{2}^{2}\leq\widetilde{\lambda}\left\lVert\text{Vec}(\mathbf{\Delta})\right\rVert_{2}^{2}.$

According to Definition 1, for any
$\mathbf{\Delta}\mathbf{\Delta}\in\mathcal{C}_{r}$, the RSC condition gives

$\left\lVert\mathbf{\Delta}\right\rVert^{2}_{\rm
F}=\left\lVert\text{Vec}(\mathbf{\Delta})\right\rVert^{2}_{2}\leq\frac{\left\lVert\text{Vec}(\mathbf{\Delta})\right\rVert^{2}_{\Sigma_{0}}}{2\kappa\big{(}\mathbf{\Sigma}_{0}\big{)}}.$

Combining these two last results we have

$\left|\;\left\lVert\text{Vec}(\mathbf{\Delta})\right\rVert_{\mathbf{\Sigma}_{0}}^{2}-\left\lVert\text{Vec}(\mathbf{\Delta})\right\rVert_{\mathbf{\Sigma}_{1}}^{2}\right|\leq\widetilde{\lambda}\frac{\left\lVert\text{Vec}(\mathbf{\Delta})\right\rVert^{2}_{\mathbf{\Sigma}_{0}}}{2\kappa\big{(}\mathbf{\Sigma}_{0}\big{)}}.$

Equivalently, the following result holds

$\left|\frac{\left\lVert\text{Vec}(\mathbf{\Delta})\right\rVert_{\mathbf{\Sigma}_{1}}^{2}}{\left\lVert\text{Vec}(\mathbf{\Delta})\right\rVert_{\mathbf{\Sigma}_{0}}^{2}}-1\right|\leq\frac{\widetilde{\lambda}}{2\kappa\big{(}\mathbf{\Sigma}_{0}\big{)}}.$

The statement follows directly by the selected $\widetilde{\lambda}$. ∎

###  C.3 Combining everything

We can now prove Proposition 2.

###### Proof.

In the RSC condition (see Definition 1) the considered covariance matrix
$\overline{\mathbf{\Sigma}}\in\mathbb{R}^{dT\times dT}$ is block-diagonal
consisting of $T$ blocks, one for each different task. Let us consider now the
single-task adapted matrix

$\displaystyle\mathbf{\Sigma}_{t,n}=\frac{1}{n}\sum_{s=1}^{n}\mathbb{E}\left[\mathbf{x}_{t,s}\mathbf{x}_{t,s}^{\top}\Big{|}\overline{\mathcal{F}}_{s-1}\right]$

and the multi-task one $\overline{\mathbf{\Sigma}}_{n}={\rm
diag}(\mathbf{\Sigma}_{1,n},...,\mathbf{\Sigma}_{T,n})\in\mathbb{R}^{dT\times
dT}$. Relying on (Oh et al., 2021, Lemma 10), under Assumption 2 we have

$\overline{\mathbf{\Sigma}}_{n}=\frac{1}{n}\sum_{s=1}^{n}\mathbb{E}\left[\overline{\mathbf{x}}_{s}\overline{\mathbf{x}}_{s}^{\top}\Big{|}\overline{\mathcal{F}}_{s-1}\right]\succeq{\left(2\nu\omega_{\mathcal{X}}\right)}^{-1}\overline{\mathbf{\Sigma}},$
(44)

where
$\overline{\mathbf{x}}_{s}=[\mathbf{x}_{1,s}^{\top},\cdots,\mathbf{x}_{T,s}^{\top}]^{\top}\in\mathbb{R}^{dT}$.
Now, let us denote
$\mathbf{\widetilde{w}}_{n}=\arg\min_{\mathbf{\overline{w}}\in\mathcal{C}(r)}\frac{\mathrm{Vec}(\mathbf{\overline{w}})\overline{\mathbf{\Sigma}}_{n}\mathrm{Vec}(\mathbf{\overline{w}})}{2\left\lVert\mathrm{Vec}(\mathbf{\overline{w}})\right\rVert^{2}_{2}}$.

Relying on the RSC condition and thanks to the previous display, we obtain

$\frac{\mathrm{Vec}(\mathbf{\widetilde{w}})^{\top}_{n}\overline{\mathbf{\Sigma}}_{n}\mathrm{Vec}(\mathbf{\widetilde{w}})_{n}}{\left\lVert\mathrm{Vec}(\mathbf{\widetilde{w}})_{n}\right\rVert_{2}^{2}}\geq\frac{\mathrm{Vec}(\mathbf{\widetilde{w}})^{\top}_{n}\overline{\mathbf{\Sigma}}\mathrm{Vec}(\mathbf{\widetilde{w}})_{n}}{2\nu\omega_{\mathcal{X}}\left\lVert\mathrm{Vec}(\mathbf{\widetilde{w}})_{n}\right\rVert_{2}^{2}}\geq\frac{\kappa\big{(}\overline{\mathbf{\Sigma}}\big{)}}{2\nu\omega_{\mathcal{X}}}.$

Hence, $\overline{\mathbf{\Sigma}}_{n}$ satisfies the RSC condition with
constant
$\kappa\left(\overline{\mathbf{\Sigma}}_{n}\right)=\kappa\left(\overline{\mathbf{\Sigma}}\right)/\left(2\nu\omega_{\mathcal{X}}\right)$.

Next we consider the operator norm deviation of the multi-task adapted matrix
$\mathbf{\Sigma}_{0}=\overline{\mathbf{\Sigma}}_{n}$ from the multi-task
empirical matrix
$\mathbf{\Sigma}_{1}=\widehat{\overline{\mathbf{\Sigma}}}_{n}$. In view of
(33), the quantity
$\left\lVert\widehat{\overline{\mathbf{\Sigma}}}_{n}-\overline{\mathbf{\Sigma}}_{n}\right\rVert_{\mathrm{op},\mathcal{C}_{r}}$
becomes smaller as $n$ increases. This means that if we take $n$ large enough,
then we have whp that
$\left\lVert\widehat{\overline{\mathbf{\Sigma}}}_{n}-\overline{\mathbf{\Sigma}}_{n}\right\rVert_{\mathrm{op},\mathcal{C}_{r}}\leq\kappa\left(\overline{\mathbf{\Sigma}}\right)/\left(4\nu\omega_{\mathcal{X}}\right)=\kappa(\overline{\mathbf{\Sigma}}_{n})/2$.
We formalize this argument below.

For a fixed $\delta\in(0,1)$, recall the definition of $N_{0}(\delta)$ in
(12). In view of Lemma 2, if $n\geq N_{0}(\delta)$ then with probability at
least $1-\delta$,

$\left\lVert\widehat{\overline{\mathbf{\Sigma}}}_{n}-\overline{\mathbf{\Sigma}}_{n}\right\rVert_{\mathrm{op},\mathcal{C}_{r}}\leq\frac{\kappa\big{(}\overline{\mathbf{\Sigma}}\big{)}}{4\nu\omega_{\mathcal{X}}}\leq\frac{\kappa\big{(}\overline{\mathbf{\Sigma}}_{n}\big{)}}{2}.$

Then Lemma 3 yields the result.

∎

###  C.4 Technical Lemma

Consider linear subspaces $\mathbf{U},\mathbf{V}$ of $\mathbb{R}^{d}$ of
dimension $d_{\mathbf{U}}$ and $d_{\mathbf{V}}$ respectively. Denote by
$P_{\mathbf{U}}$ and $P_{\mathbf{V}}$ the orthogonal projections onto
$\mathbf{U}$ and $\mathbf{V}$ respectively. We have for any $n\in[N]$

$\max_{\mathbf{u}\in B_{\mathbf{U}}(0,1),\mathbf{v}\in
B_{\mathbf{V}}(0,1)}{\langle\mathbf{M}_{t,n}\mathbf{u},\mathbf{v}\rangle}\leq\left\lVert
P_{\mathbf{U}}\mathbf{M}_{t,n}P_{\mathbf{V}}\right\rVert_{\rm op}.$

######  Lemma 4.

Let Assumption 1 be satisfied. For any $\delta\in(0,1)$ and any $t\in[T]$,
with probability at least $1-\delta$,

$\displaystyle\max_{n\in[N]}\left\\{\frac{1}{n}\left\lVert
P_{\mathbf{U}}\mathbf{M}_{t,n}P_{\mathbf{V}}\right\rVert_{\rm op}\right\\}$
$\displaystyle\leq
C\max_{k\in[K]}\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\\}\biggl{(}\sqrt{\frac{\bigl{(}d_{\mathbf{U}}\vee
d_{\mathbf{V}}+\log(4N\delta^{-1})\bigr{)}\log(4N\delta^{-1}d)}{n}}$
$\displaystyle\hskip
28.45274pt+\frac{\sqrt{\left(d_{\mathbf{U}}+\log(4N\delta^{-1})\right)\left(d_{\mathbf{V}}+\log(4N\delta^{-1}d)\right)}\log(4N\delta^{-1})}{n}\biggr{)},$
(45)

where $C=C(C_{\mathbf{z})})>0$ may depend only on $C_{\mathbf{z}}$.

###### Proof.

We have for any $n\geq 1$

$\displaystyle\left\lVert
P_{\mathbf{U}}(\mathbf{M}_{t,n}-\mathbf{M}_{t,n-1})P_{\mathbf{V}}\right\rVert_{\rm
op}$ $\displaystyle=\left\lVert
P_{\mathbf{U}}(\mathbf{x}_{t,n})P_{\mathbf{V}}(\mathbf{x}_{t,n})^{\top}-\mathbb{E}\left[P_{\mathbf{U}}(\mathbf{x}_{t,n})P_{\mathbf{V}}(\mathbf{x}_{t,n})^{\top}\Big{|}\overline{\mathcal{F}}_{n-1}\right]\right\rVert_{\rm
op}$ $\displaystyle\leq\left\lVert
P_{\mathbf{U}}(\mathbf{x}_{t,n})\right\rVert\left\lVert
P_{\mathbf{V}}(\mathbf{x}_{t,n})\right\rVert+\max_{k\in[K]}\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\\}.$ (46)

In view of Assumption 1, we have
$\|P_{\mathbf{U}}(\mathbf{x}_{t,n})\|_{2}^{2}=\mathbf{z}_{t,n}^{\top}P_{\mathbf{U}}\mathbf{\Sigma}_{k}P_{\mathbf{U}}\mathbf{z}_{t,n}$
for some $k\in[K]$. We apply now Hanson-Wright’s inequality conditionally on
$\overline{\mathcal{F}}_{n-1}$ to get for any $x>0$

$\displaystyle\mathbb{P}\left(\mathbf{z}_{t,n}^{\top}P_{\mathbf{U}}\mathbf{\Sigma}_{k}P_{\mathbf{U}}\mathbf{z}_{t,n}\leq\mathbb{E}\left[\mathbf{z}_{t,n}^{\top}P_{\mathbf{U}}\mathbf{\Sigma}_{k}P_{\mathbf{U}}\mathbf{z}_{t,n}\big{|}\overline{\mathcal{F}}_{n-1}\right]+C\,C_{\mathbf{z}}^{2}\left(\sqrt{\|P_{\mathbf{U}}\mathbf{\Sigma}_{k}P_{\mathbf{U}}\|_{\rm
F}^{2}x}+\left\lVert
P_{\mathbf{U}}\mathbf{\Sigma}_{k}P_{\mathbf{U}}\right\rVert_{\rm op}\
x\right)\big{|}\overline{\mathcal{F}}_{n-1}\right)\geq 1-e^{-x}.$

Note that
$\mathbb{E}\left[\mathbf{z}_{t,n}^{\top}P_{\mathbf{U}}\mathbf{\Sigma}_{k}P_{\mathbf{U}}\mathbf{z}_{t,n}\big{|}\overline{\mathcal{F}}_{n-1}\right]=\mathrm{trace}(P_{\mathbf{U}}\mathbf{\Sigma}_{k}P_{\mathbf{U}})\leq\max_{k\in[K]}\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\\}d_{\mathbf{U}}$ since $\mathbf{z}_{k}$ is a zero mean isotropic random
vector.

We define the following event in $\overline{\mathcal{F}}_{n}$

$\displaystyle\Omega_{n}(\mathbf{U})$ $\displaystyle:=\left\\{\left\lVert
P_{\mathbf{U}}(\mathbf{x}_{t,n})\right\rVert^{2}\leq\max_{k\in[K]}\left\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\right\\}\left(d_{\mathbf{U}}+C\,C_{\mathbf{z}}^{2}\left(\sqrt{d_{\mathbf{U}}\,\log(4N\delta^{-1})}+\log(4N\delta^{-1})\right)\right)\right\\},$
(47)

and

$\displaystyle\Omega_{n}(\mathbf{V})$ $\displaystyle:=\left\\{\left\lVert
P_{\mathbf{V}}(\mathbf{x}_{t,n})\right\rVert^{2}\leq\max_{k\in[K]}\left\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\right\\}\left(d_{\mathbf{V}}+C\,C_{\mathbf{z}}^{2}\left(\sqrt{d_{\mathbf{V}}\,\log(4N\delta^{-1})}+\log(4N\delta^{-1})\right)\right)\right\\}.$
(48)

Combining the last three displays and taking $x=\log(\delta^{-1})$ immediately
implies for any $n\in[N]$

$\displaystyle\mathbb{P}\left(\Omega_{n}(\mathbf{U})\big{|}\overline{\mathcal{F}}_{n-1}\right)\geq
1-\frac{\delta}{4N},\quad\mathbb{P}\left(\Omega_{n}(\mathbf{V})\big{|}\overline{\mathcal{F}}_{n-1}\right)\geq
1-\frac{\delta}{4N}$ (49)

We define, for any $n\in[N]$

$\displaystyle\bar{\Omega}_{n}=\bigcap_{l=0}^{n}\Omega_{l}(\mathbf{U})\cap\Omega_{l}(\mathbf{V})\in\overline{\mathcal{F}}_{n},$
(50)

with $\Omega_{0}(\mathbf{U})=\Omega_{0}(\mathbf{V})$ being the whole sample
space. The Bayes rule combined with (49) gives

$\displaystyle\mathbb{P}\left(\bar{\Omega}_{N}\right)=\prod_{n=1}^{N}\mathbb{P}\left(\Omega_{n}(\mathbf{U})\cap\Omega_{n}(\mathbf{V})\big{|}\bigcap_{k=0}^{n-1}\Omega_{k}(\mathbf{U})\cap\Omega_{k}(\mathbf{V})\right)\geq\left(1-\frac{\delta}{2N}\right)^{N}.$
(51)

Bernoulli’s inequality ($(1+x)^{n}\geq 1+nx$ for any $x>-1$ and integer $n\geq
1$) gives

$\displaystyle\mathbb{P}\left(\bar{\Omega}_{N}\right)=\prod_{n=1}^{N}\mathbb{P}\left(\Omega_{n}(\mathbf{U})\cap\Omega_{n}(\mathbf{V})\big{|}\bigcap_{k=0}^{n-1}\Omega_{k}(\mathbf{U})\cap\Omega_{k}(\mathbf{V})\right)\geq
1-\frac{\delta}{2}.$ (52)

Define the stopping times $\tau(\mathbf{U})$ and $\tau(\mathbf{V})$ as follows

$\displaystyle\tau(\mathbf{U})$ $\displaystyle=\inf\left\\{n\geq
0\,:\,\left\lVert
P_{\mathbf{U}}(\mathbf{x}_{t,n})\right\rVert^{2}\geq\max_{k\in[K]}\left\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\right\\}\left(d_{\mathbf{U}}+C\,C_{\mathbf{z}}^{2}\left(\sqrt{d_{\mathbf{U}}\,\log(4N\delta^{-1})}+\log(4N\delta^{-1})\right)\right)\right\\},$
(53)

and

$\displaystyle\tau(\mathbf{V})=\inf\left\\{n\geq 0\,:\,\left\lVert
P_{\mathbf{V}}(\mathbf{x}_{t,n})\right\rVert^{2}\geq\max_{k\in[K]}\left\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\right\\}\left(d_{\mathbf{V}}+C\,C_{\mathbf{z}}^{2}\left(\sqrt{d_{\mathbf{V}}\,\log(4N\delta^{-1})}+\log(4N\delta^{-1})\right)\right)\right\\},$
(54)

Again by definition of the Trace-Norm bandit, $\tau(\mathbf{U})$ and
$\tau(\mathbf{V})$ are both stopping times relative to the filtration
$\\{\overline{\mathcal{F}}_{n}\\}_{n\geq 0}$, so is
$\tau=\tau(\mathbf{U})\wedge\tau(\mathbf{V})$. Hence the stopped process
$\\{\overline{\mathbf{M}}^{\tau}_{n}\\}_{n\geq 0}$ defined as follows

$\overline{\mathbf{M}}^{\tau}_{n}:=P_{\mathbf{U}}\mathbf{M}_{t,n\wedge\tau}P_{\mathbf{V}},\quad\forall
n\geq 0,$

is also a martingale adapted to the filtration
$\\{\overline{\mathcal{F}}_{n}\\}_{n\geq 0}$. Furthermore
$\\{\overline{\mathbf{M}}^{\tau}_{n}\\}_{n\geq 0}$ is a bounded martingale.
Hence we can apply the Freedman inequality to it.

By definition of $\tau$ and (52), we have
$\\{\tau>N\\}=\overline{\Omega}_{N}$. Hence for any $x>0$

$\displaystyle\mathbb{P}\left(\left\lVert
P_{\mathbf{U}}\mathbf{M}_{t,n}P_{\mathbf{V}}\right\rVert_{\rm op}\geq
x\right)$
$\displaystyle=\mathbb{P}\left(\\{P_{\mathbf{U}}\mathbf{M}_{t,n}P_{\mathbf{V}}\geq
x\\}\cap\\{\tau>N\\}\right)+\mathbb{P}\left(\\{\left\lVert
P_{\mathbf{U}}\mathbf{M}_{t,n}P_{\mathbf{V}}\right\rVert_{\rm op}\geq
x\\}\cap\\{\tau\leq N\\}\right)$
$\displaystyle\leq\mathbb{P}\left(\left\lVert\overline{\mathbf{M}}^{\tau}_{n}\right\rVert_{\rm
op}\geq x\right)+\mathbb{P}\left(\\{\tau\leq
N\\}\right)\leq\mathbb{P}\left(\left\lVert\overline{\mathbf{M}}^{\tau}_{n}\right\rVert_{\rm
op}\geq x\right)+\delta/2,$ (55)

where we have used (52) in the last line.

##### Deviation bound for
$\left\lVert\overline{\mathbf{M}}^{\tau}_{n}\right\rVert_{\rm op}$.

We will use again (Tropp, 2011, Corollary 1.3).

In view of (C.4), (47) and (48), we have

$\displaystyle\left\lVert\overline{\mathbf{M}}^{\tau}_{n}-\overline{\mathbf{M}}^{\tau}_{n-1}\right\rVert_{\rm
op}$
$\displaystyle\leq\max_{k\in[K]}\left\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\right\\}\left(1+(1+C\,C_{\mathbf{z}}^{2}/2)\sqrt{\left(d_{\mathbf{U}}+\log(4N\delta^{-1})\right)\left(d_{\mathbf{V}}+\log(4N\delta^{-1})\right)}\right).$
(56)

Next, we set
$Y_{t,n}=\overline{\mathbf{M}}^{\tau}_{n}-\overline{\mathbf{M}}^{\tau}_{n-1}$.
Elementary computations give

$\displaystyle\bm{W}_{{\rm col}}$
$\displaystyle=\sum_{s=1}^{n}\mathbb{E}\left[Y_{t,n}Y_{t,n}^{\top}|\overline{\mathcal{F}}_{s-1}\right]\leq(1+C\,C_{\mathbf{z}}^{2}/2)^{2}n\bigl{(}d_{\mathbf{V}}+\log(4N\delta^{-1})\bigr{)}\max_{k\in[K]}\\{\left\lVert
P_{\mathbf{V}}\mathbf{\Sigma}_{k}P_{\mathbf{V}}\right\rVert_{\rm
op}\\}\max_{k\in[K]}\\{\left\lVert
P_{\mathbf{U}}\mathbf{\Sigma}_{k}P_{\mathbf{U}}\right\rVert_{\rm op}\\},$

and

$\displaystyle\bm{W}_{{\rm row}}$
$\displaystyle=\sum_{s=1}^{n}\mathbb{E}\left[Y_{t,n}^{\top}Y_{t,n}|\overline{\mathcal{F}}_{s-1}\right]\leq(1+C\,C_{\mathbf{z}}^{2}/2)^{2}n\bigl{(}d_{\mathbf{U}}+\log(4N\delta^{-1})\bigr{)}\max_{k\in[K]}\\{\left\lVert
P_{\mathbf{V}}\mathbf{\Sigma}_{k}P_{\mathbf{V}}\right\rVert_{\rm
op}\\}\max_{k\in[K]}\\{\left\lVert
P_{\mathbf{U}}\mathbf{\Sigma}_{k}P_{\mathbf{U}}\right\rVert_{\rm op}\\}.$

Hence

$\displaystyle\bm{W}_{{\rm row}}\vee\bm{W}_{{\rm col}}$
$\displaystyle\leq(1+C\,C_{\mathbf{z}}^{2}/2)^{2}n\bigl{(}d_{\mathbf{U}}\vee
d_{\mathbf{V}}+\log(4N\delta^{-1})\bigr{)}\max_{k\in[K]}\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}^{2}\\}.$ (57)

Applying (Tropp, 2011, Corollary 1.3), we get for any $\delta\in(0,1)$ with
probability at least $1-\delta/(2N)$ that

$\displaystyle\left\lVert\overline{\mathbf{M}}^{\tau}_{n}\right\rVert_{\rm
op}$
$\displaystyle\leq(1+C\,C_{\mathbf{z}}^{2}/2)\max_{k\in[K]}\\{\left\lVert\mathbf{\Sigma}_{k}\right\rVert_{\rm
op}\\}\biggl{(}\sqrt{n\,\bigl{(}d_{\mathbf{U}}\vee
d_{\mathbf{V}}+\log(4N\delta^{-1})\bigr{)}\log(4N\delta^{-1}d)}$
$\displaystyle\hskip
142.26378pt+2\sqrt{\left(d_{\mathbf{U}}+\log(4N\delta^{-1})\right)\left(d_{\mathbf{V}}+\log(4N\delta^{-1})\right)}\log(4N\delta^{-1}d)\biggr{)}.$
(58)

Dividing by $n$ and a trivial union bound gives the result.

∎

##  Appendix D PROOF OF THEOREM 1

We recall that $\mathbf{W}=[\mathbf{w}_{1},\dots,\mathbf{w}_{T}]$ is of rank
smaller than $r$. Hence $\mathbf{W}$ admits the following singular value
decomposition

$\mathbf{W}=\sum_{j=1}^{r}\sigma_{j}(\mathbf{W})u_{j}(\mathbf{W})\otimes
v_{j}(\mathbf{W}),$

with singular values
$\sigma_{1}(\mathbf{W})\geq\cdots\geq\sigma_{r}(\mathbf{W})>0$ and
corresponding left and right orthonormal singular vectors
$u_{1}(\mathbf{W}),\ldots,u_{r}(\mathbf{W})$ of $\mathbb{R}^{d}$ and
$v_{1}(\mathbf{W}),\ldots,v_{r}(\mathbf{W})$ of $\mathbb{R}^{T}$. We denote by
$P_{U}$ the orthogonal projection onto
$U=\mathrm{l.s.}(u_{1}(\mathbf{W}),\ldots,u_{r}(\mathbf{W}))$. By definition
of the SVD, we obviously have $P_{U}(\mathbf{w}_{t})=\mathbf{w}_{t}$ for any
$1\leq t\leq T$.

We consider now the instantaneous multi-task regret

$\overline{R}_{n}=\sum_{t=1}^{T}R_{t,n}=\sum_{t=1}^{T}\langle\mathbf{x}_{t,n}^{*},\mathbf{w}_{t}\rangle-\langle\mathbf{x}_{t,n},\mathbf{w}_{t}\rangle\leq
2\sum_{t=1}^{T}\max_{\mathbf{x}\in\mathcal{D}_{t,n}}|\langle\mathbf{x},\mathbf{w}_{t}\rangle|,$

where
$\mathbf{x}_{t,n}^{*}=\arg\max_{\mathbf{x}\in\mathcal{D}_{t,n}}\langle\mathbf{x},\mathbf{w}_{t}\rangle$.

Assumption 1 guarantees that
$\frac{\langle\mathbf{x},\mathbf{w}_{t}\rangle}{\left\lVert\mathbf{w}_{t}\right\rVert}$
is $C_{\mathbf{x}}$-subgaussian and consequently, for any $\delta\in(0,1)$,
with probability at least $1-\delta$

$|\langle\mathbf{x},\mathbf{w}_{t}\rangle|\leq
C_{\mathbf{x}}\left\lVert\mathbf{w}_{t}\right\rVert\sqrt{\log(e\delta^{-1})}\leq
C_{\mathbf{z}}\max_{k\in[K]}\left\\{\left\lVert\Sigma_{k}\right\rVert_{\rm
op}^{1/2}\right\\}L\sqrt{\log(e\delta^{-1})}.$

An union bound over $t\in[T]$, $n\in[N]$, $\mathbf{x}\in\mathcal{D}_{t,n}$
gives with probability at least $1-\delta/2$

$\max_{\mathbf{x}\in\mathcal{D}_{t,n}}|\langle\mathbf{x},\mathbf{w}_{t}\rangle|\leq
C_{\mathbf{z}}\max_{k\in[K]}\left\\{\left\lVert\Sigma_{k}\right\rVert_{\rm
op}^{1/2}\right\\}L\sqrt{\log(2eTKN\delta^{-1})},\quad\forall
t\in[T],\;\forall k\in[K],\forall n\in[N].$

Hence with the same probability, $\forall n\in[N]$

$\overline{R}_{n}\leq
C_{\mathbf{z}}T\max_{k\in[K]}\left\\{\left\lVert\Sigma_{k}\right\rVert_{\rm
op}^{1/2}\right\\}L\sqrt{\log(2eTKN\delta^{-1})}$

We will now split the regret into two phases. During the first $N_{0}$
interactions the collected data will not meet the RSC condition. Hence, the
incurred regret will be of order $TN_{0}\sqrt{\log(2eTKN\delta^{-1})}$.
Conversely, from the $N_{0}+1$-th round up to the $N$-th one, the RSC
condition will be met allowing the result of Lemma 1.

We have

$\displaystyle\sum_{n=\lceil N_{0}\rceil}^{N}\overline{R}_{n}$
$\displaystyle=\sum_{n=\lceil
N_{0}\rceil}^{N}\sum_{t=1}^{T}\langle\mathbf{x}_{t,n}^{*},\mathbf{w}_{t}-\mathbf{\widehat{w}}_{t,n}\rangle+\sum_{n=\lceil
N_{0}\rceil}^{N}\sum_{t=1}^{T}\langle\mathbf{x}_{t,n}^{*}-\mathbf{x}_{t,n},\mathbf{\widehat{w}}_{t,n}\rangle+\sum_{n=\lceil
N_{0}\rceil}^{N}\sum_{t=1}^{T}\langle\mathbf{x}_{t,n},\mathbf{\widehat{w}}_{t,n}-\mathbf{w}_{t}\rangle$
$\displaystyle\leq\sum_{n=\lceil
N_{0}\rceil}^{N}\sum_{t=1}^{T}\langle\mathbf{x}_{t,n}^{*},\mathbf{w}_{t}-\mathbf{\widehat{w}}_{t,n}\rangle+\sum_{n=\lceil
N_{0}\rceil}^{N}\sum_{t=1}^{T}\langle\mathbf{x}_{t,n},\mathbf{\widehat{w}}_{t,n}-\mathbf{w}_{t}\rangle=\sum_{n=\lceil
N_{0}\rceil}^{N}\sum_{t=1}^{T}\langle\mathbf{x}_{t,n}^{*}-\mathbf{x}_{t,n},\mathbf{w}_{t}-\mathbf{\widehat{w}}_{t,n}\rangle$
(59)

where we have used that for any $1\leq n\leq N$, $1\leq t\leq T$,
$\langle\mathbf{x}_{t,n}^{*}-\mathbf{x}_{t,n},\mathbf{\widehat{w}}_{t,n}\rangle\leq
0$ a.s. by definition of our policy.

Next, we have

$\left|\sum_{t=1}^{T}\langle\mathbf{x}_{t,n}^{*}-\mathbf{x}_{t,n},\mathbf{w}_{t}-\mathbf{\widehat{w}}_{t,n}\rangle\right|\leq
2\sum_{t=1}^{T}\max_{\mathbf{x}\in\mathcal{D}_{t,n}}\left|\langle\mathbf{x},\mathbf{w}_{t}-\mathbf{\widehat{w}}_{t,n}\rangle\right|.$
(60)

In view of (4), we note that
$\widehat{\mathbf{W}}_{n}\in\overline{\mathcal{F}}_{n-1}$. Thus, conditionally
on $\overline{\mathcal{F}}_{n-1}$, Assumption 1 guarantees that
$\frac{\langle\mathbf{x},\mathbf{w}_{t}-\mathbf{\widehat{w}}_{t,n}\rangle}{\left\lVert\mathbf{w}_{t}-\mathbf{\widehat{w}}_{t,n}\right\rVert}$
is $C_{\mathbf{x}}$-subgaussian and consequently, for any $\delta\in(0,1)$,
with probability at least $1-\delta$

$|\langle\mathbf{x},\mathbf{w}_{t}-\mathbf{\widehat{w}}_{t,n}\rangle|\leq
C_{\mathbf{x}}\left\lVert\mathbf{w}_{t}-\mathbf{\widehat{w}}_{t,n}\right\rVert\sqrt{\log(e\delta^{-1})}\leq
C_{\mathbf{z}}\max_{k\in[K]}\left\\{\left\lVert\Sigma_{k}\right\rVert_{\rm
op}^{1/2}\right\\}\left\lVert\mathbf{w}_{t}-\mathbf{\widehat{w}}_{t,n}\right\rVert\sqrt{\log(e\delta^{-1})}.$

An union bound over $t,n,k$ gives with probability at least $1-\delta$

$\displaystyle\max_{t\in[T],n\in[N]}\max_{\mathbf{x}\in\mathcal{D}_{t,n}}|\langle\mathbf{x},\mathbf{w}_{t}-\mathbf{\widehat{w}}_{t,n}\rangle|\leq
C_{\mathbf{z}}\max_{k\in[K]}\left\\{\left\lVert\Sigma_{k}\right\rVert_{\rm
op}^{1/2}\right\\}\left\lVert\mathbf{w}_{t}-\mathbf{\widehat{w}}_{t,n}\right\rVert\sqrt{\log(eTKN\delta^{-1})}.$
(61)

Combining the last two displays, we get with probability at least $1-\delta$,
for any $t\in[T]$, $n\in[N]$,

$\displaystyle\left|\sum_{t=1}^{T}\langle\mathbf{x}_{t,n}^{*}-\mathbf{x}_{t,n},\mathbf{w}_{t}-\mathbf{\widehat{w}}_{t,n}\rangle\right|$
$\displaystyle\leq
2C_{\mathbf{z}}\max_{k\in[K]}\left\\{\left\lVert\Sigma_{k}\right\rVert_{\rm
op}^{1/2}\right\\}\left(\sum_{t=1}^{T}\left\lVert\mathbf{w}_{t}-\mathbf{\widehat{w}}_{t,n}\right\rVert\right)\sqrt{\log(eTKN\delta^{-1})}$
$\displaystyle\leq
2C_{\mathbf{z}}\max_{k\in[K]}\left\\{\left\lVert\Sigma_{k}\right\rVert_{\rm
op}^{1/2}\right\\}\sqrt{T}\left\lVert\mathbf{W}-\widehat{\mathbf{W}}_{n}\right\rVert_{F}\sqrt{\log(eTKN\delta^{-1})}.$

Recall that Lemmas 1 and 2 combined with Propositions 1 and 2 gives, for any
$\lceil N_{0}\rceil\leq n\leq N$ and any $\delta\in(0,1)$, with probability at
least $1-\frac{\delta}{2N}$,

$\displaystyle\left\lVert\widehat{\mathbf{W}}_{n}-\mathbf{W}\right\rVert_{\rm
F}\lesssim_{c_{\eta},\sigma,C_{\mathbf{x}},\kappa(\overline{\mathbf{\Sigma}}),\max_{1\leq
k\leq K}\left\\{\left\lVert\Sigma_{k}\right\rVert_{\rm
op}^{1/2}\right\\}}\sqrt{\frac{r}{n}}\left(\sqrt{T+d+\log\left(\frac{4N(d+T)}{\delta}\right)}\log^{3/2}\left(\frac{8N(d+T)}{\delta}\right)\right).$
(62)

Combining the last two displays, we obtain with probability at least
$1-\delta$

$\displaystyle\left|\sum_{t=1}^{T}\langle\mathbf{x}_{t,n}^{*}-\mathbf{x}_{t,n},\mathbf{w}_{t}-\mathbf{\widehat{w}}_{t,n+1}\rangle\right|$
$\displaystyle\lesssim\sqrt{\frac{rT}{n}}\left(\sqrt{T+d+\log\left(\frac{4N(d+T)}{\delta}\right)}\log^{3/2}\left(\frac{8N(d+T)}{\delta}\right)\right)\sqrt{\log(2e\delta^{-1}TKN)}.$
(63)

Summing over $n$ in the previous display along with an union bound argument
and (D) gives with probability at least $1-\delta$

$\displaystyle\sum_{n=\lceil N_{0}\rceil}^{N}\overline{R}_{s}$
$\displaystyle\leq
C\sqrt{rTN}\left(\sqrt{T+d+\log\left(\frac{4N(d+T)}{\delta}\right)}\log^{3/2}\left(\frac{8N(d+T)}{\delta}\right)\right)\sqrt{\log(2e\delta^{-1}TKN)},$
(64)

where
$C=C\left(\eta,\sigma,C_{\mathbf{z}},\kappa(\overline{\mathbf{\Sigma}}),\max_{1\leq
k\leq K}\left\\{\left\lVert\Sigma_{k}\right\rVert_{\rm
op}^{1/2}\right\\}\right)$ is a finite constant under our assumptions.

##  Appendix E NUMERICAL EXPERIMENTS

We perform here some additional experiments on the impact of the rank $r$, the
dimension $d$ and the number of tasks $T$ on the performance of our trace norm
bandit policy (Algorithm 1). We also compare its performance to the MLingreedy
policy of Yang et al. (2020).

##### Comparison to MLingreedy (Yang et al., 2020).

We compare the performance of the trace norm bandit (Alg. 1) to that of the
MLingreedy policy and independent task learning (ITL). We recall that the
MLingreedy policy use a rank parameter $\overline{r}$. This parameter is set
equal to the true rank $r$ of $\mathbf{W}$ in Yang et al. (2020) to derive the
theoretical properties of this policy.

In our experiments we will use different values for the rank parameter
$\overline{r}$, either the true rank $r$ or an overestimated rank
$\overline{r}=\min(2r,d,T)$ or an underestimated rank
$\overline{r}=\max(\lfloor r/2\rfloor,1)$. At each epoch of the the MLingreedy
policy, we used stochastic gradient descent to solve the matrix factorization
step. We perform $5$ repetitions of our experiments for several values of
dimension $d$, $T$, the parameter $\overline{r}$ of MLingreedy and the
regularization parameter $l\in\\{l_{1},l_{2},l_{3}\\}$ of the trace norm
policy.

In Figures 3 and 4, we implement MLingreedy with the true value of rank $r$
(most favorable case for this policy in theory) and compare its performance to
that of our trace norm bandit and ITL. Trace norm bandit performs consistently
above ITL and MLingreedy with true parameter for all considered configurations
of $T$ and $d$. Noticeably MLingreedy with true parameter performs
significantly worse than ITL for $d=40$ for almost all values of $N$.

In Figure 5, we explore in more details the impact of parameters $l$ and
$\overline{r}$ on the performance of the trace norm bandit and MLingreedy,
respectively.

  * •

In higher dimension $d=40$ and $T=10$, the trace norm bandit performs
significantly better than MLingreedy. Actually MLingreedy performance is
significantly worse than ITL even when using the true rank ($\overline{r}=r$)
until $N$ becomes larger than $38$ whereas the trace norm policy performs
significantly better than ITL even when $N$ is small.

  * •

For $d=40$ and $T=30$, the trace norm bandit performs better than ITL for any
$N\geq 25$ whereas MLingreedy with overestimated rank and true rank are below
ITL until $N\geq 35$ and $N\geq 38$ respectively. MLingreedy with
underestimated rank is significantly worse than ITL for all $N$.

Figure 3: Averaged cumulative reward over all tasks with $d=10$ features,
$T=10$ tasks (left) and $T=30$ (right). Each task lasts for $N=40$ rounds, has
$K=10$ arms, noise variance $\sigma^{2}=1$ and true rank $r=5$.

Figure 4: Averaged cumulative reward over all tasks with $d=40$ features,
$T=10$ tasks (left) and $T=30$ (right). Each task lasts for $N=40$ rounds, has
$K=10$ arms, noise variance $\sigma^{2}=1$ and true rank $r=5$.

Figure 5: Averaged cumulative reward over all tasks with $d=40$ features,
$T=10$ tasks (top) and $T=30$ (bottom). Each task lasts for $N=40$ rounds, has
$K=10$ arms, noise variance $\sigma^{2}=1$ and true rank $r=5$.

In summary, the trace norm bandit performs consistently better than ITL
uniformly for most values of $N$, for all values of $d$ and $T$ and for
several choices of the regularization parameter. Conversely, MLingreedy is far
more sensitive to the choice of rank parameter $\overline{r}$ and the values
of $d$ and $T$. MLingreedy with underestimated rank performs far worse than
ITL in all configurations. MLingreedy with overestimated rank performs
sometimes better than MLingreedy with true rank. Overall, its performance are
worse than those of trace norm bandit.

##### Impact of rank $r$.

In Figure 6, we note that Alg. 1 performs uniformly better than the ITL policy
uniformly over all values of rank $r\in[d]$. The performance of the oracle
tends to that of ITL as $r$ tends to $d$. This is expected as the oracle
working in a $r$-dimensional space loses the benefit of working in a small
dimensional space when $r\approx d$. Interestingly, the performance of the
trace norm bandit becomes superior to that of the oracle as $r$ gets close to
$d$. A plausible explanation is that nuclear norm regularization can still
bring some benefit even when $r\approx d$ as it can still perform dimension
reduction.

Figure 6: Averaged cumulative reward over all tasks for $d=20$, $T=20$,
$\sigma^{2}=1$ as a function of the rank $r$.