# Non-Stationary Representation Learning in Sequential Linear Bandits

Yuzhen Qin
<EMAIL_ADDRESS>&Tommaso Menara
<EMAIL_ADDRESS>&Samet Oymak
<EMAIL_ADDRESS>&ShiNung Ching
<EMAIL_ADDRESS>&Fabio Pasqualetti∗
<EMAIL_ADDRESS>Department of Mechanical Engineering, University of
California, Riverside, CA 92521, USADepartment of Mechanical and Aerospace
Engineering, University of California, San Diego, La Jolla, CA 92093,
USADepartment of Electrical and Computer Engineering, University of
California, Riverside, CA 92521, USADepartment of Electrical and Systems
Engineering and Biomedical Engineering, Washington University in St. Louis,
St. Louis, MO 63130, USA

###### Abstract

In this paper, we study representation learning for multi-task decision-making
in non-stationary environments. We consider the framework of sequential linear
bandits, where the agent performs a series of tasks drawn from different
environments. The embeddings of tasks in each set share a low-dimensional
feature extractor called representation, and representations are different
across sets. We propose an online algorithm that facilitates efficient
decision-making by learning and transferring non-stationary representations in
an adaptive fashion. We prove that our algorithm significantly outperforms the
existing ones that treat tasks independently. We also conduct experiments
using both synthetic and real data to validate our theoretical insights and
demonstrate the efficacy of our algorithm.

##  1 INTRODUCTION

Humans are naturally endowed with the ability to learn and transfer experience
to later unseen tasks. The key mechanism enabling such versatility is the
abstraction of past experience into a ‘basis set’ of simpler representations
that can be used to construct new strategies much more efficiently in future
complex environments [1, 2].

Inspired by this observation, recent years have witnessed an increasing
interest in the study of representation learning [3]. Representation learning
is an important tool to perform transfer learning, wherein common low-
dimensional features shared by tasks are inferred and generalized. It
underlies major advances in a variety of fields including language processing
[4], drug discovery [5], and reinforcement learning [6]. Due to its promising
seminal impact, there are many recent theoretical studies on representation
learning (e.g., see [7, 8, 9, 10, 11]). Yet, existing literature focuses on
representation learning for batch tasks and is restricted to static
representations, thus relying on the working assumption that _one
representation fits all tasks_.

Most realistic decision-making scenarios feature two challenges: (i) the
learning agent faces tasks that appear in sequence, and (ii) the agent may
encounter distinct environments sequentially (see Fig. 1 (a)), where learning
a single representation is no longer sufficient. Humans can perform
extraordinarily well in such scenarios because of their flexibility to adapt
to new environments. For instance, in the Wisconsin Card Sorting Task (WCST,
see Fig. 1 (b)), participants are asked to match a sequence of stimulus cards
to one of the four cards on the table according to some sorting rule — number,
shape, or color. The sorting rule changes every now and then without informing
the participants. Earlier studies have shown that, in general, humans perform
very well on this task (e.g., [12]). By contrast, some classical learning
algorithms, such as the tabular-Q learning and the deep-Q learning, struggle
in WCST (as we show in Section 6). Unlike humans, these algorithms can neither
abstract succinct information from experience nor adapt to new environments.
This observation reveals the need to develop more human-like reasoning and a
more fluid approach in representation learning.

This paper takes an important step towards a deeper theoretical understanding
of representation learning in non-stationary environments. As a prototypical
sequential decision-making scenario, we consider a series of linear bandit
models, where each bandit represents a different task, and the objective is to
maximize the cumulative reward by interacting with these tasks. Moreover,
sequential tasks are drawn from different environments. Importantly, tasks in
the same environment share a low-dimensional linear representation, and
different environments have their own representations. Our modeling choice can
be used in a wide range of applications. For instance, consider an adaptive
system that recommends music to users of a streaming platform. This system
naturally fits our model: non-stationary environments arise due to the fact
that distinct groups of active users can have different preferences at
different times of the day (see Fig. 1 (c)). The goal of this paper is to
analytically study representation learning in dynamical environments akin to
the above recommendation system.

Figure 1: Scenarios with non-stationary environments. (a) Changing
environments that the agent enters to perform tasks in sequence. (b) The
Wisconsin Card Sorting Task, a classical test to assess cognitive capabilities
that features a changing sorting rule; (c) A recommendation system that
recommends music to distinct users at different times of the day based on the
users’ tastes.

Related Work.  As a well-known model to capture the exploration-exploitation
dilemma in decision-making, multi-armed bandits have attracted extensive
attention (see [13] for a survey). A variety of generalized bandit problems
have been investigated, where the situations with non-stationary reward
functions [14], restless arms [15], satisficing reward objectives [16], heavy-
tailed reward distributions [17], risk-averse decision-makers [18], and
multiple players [19] are considered. Distributed algorithms have also been
proposed to tackle bandit problems (e.g., see [20, 21, 22, 23, 24, 25, 26,
27]).Recently, some studies take into account the nature that sequentially
collected data is adaptive and propose novel algorithms to further improve the
performance [28, 29].

Besides the above work that focuses on single-task bandits, some efforts have
also been made to study multi-task problems. The core of multi-task bandits is
to learn and transfer interrelationships across multiple tasks, aiming to
improve decision-making efficiency compared to treating tasks independently.
Various types of interrelationships can be leveraged to boost the learning
agent’s performance, including the mean of tasks drawn from a stationary
distribution [30, 31], similarity of task coefficients in linear bandits [32],
and resemblance in contexts of arms in contextual bandits [33]. Recently,
learning low-dimensional subspaces shared by task coefficients has also been
proven to improve performance in simultaneous linear bandits [34, 35, 36].

Contribution.  This paper seeks to develop methods to learn and transfer non-
stationary representations across sequential bandits. In contrast to recent
studies that play bandits simultaneously [34, 35], the sequential setting is
more realistic, and representation learning in this context is much more
challenging. First, there does not exist a low-dimensional representation that
fits all bandits. The agent needs to adapt to dynamical environments. Second,
the agent does not know when environment changes happen, thus has no knowledge
of the number of tasks drawn from an environment. It is therefore challenging
to strike the balance between learning and transferring the representation.

We propose an adaptive algorithm to overcome these challenges. Within each
environment, this algorithm alternates between representation exploration and
exploitation, making it flexible to different durations of the environments.
Meanwhile, we incorporate a change-detection strategy into our algorithm to
adapt to non-stationary environments. We further obtain an upper bound for our
algorithm $\tilde{O}(dr\sqrt{mSN}+Sr\sqrt{N})$, with $d$ being the task
dimension, $r$ the representation dimension, $m$ the number of environments,
$S$ the number of tasks, and $N$ the number of rounds for each task. Our
regret significantly outperforms the baseline $\Theta(Sd\sqrt{N})$ of
algorithms treating tasks independently. To demonstrate our theoretical
results, we perform some experiments using synthetic data and LastFM data.
Simulation results also show that our algorithm considerably outperforms
classical reinforcement learning algorithms in WCST.

Our preliminary work [37] presents limited theoretical findings on
representation learning in the sequential setting, but we go well beyond that
in this paper by considering non-stationary environments and providing a
comprehensive account of the results. Further, we demonstrate the broad
applications of our results by presenting more experiments.

Organization.  The problem setup is in Section 2. In Section 3, we present an
algorithm that performs representation learning in a single environment. An
environment-change-detection algorithm is provided in Section 4. In Section 5,
the main algorithm is presented by putting together Sections 3 and 4.
Illustrative experiments are reported in Section 6. Concluding remarks appear
in Section 7.

Notation.  Given a matrix $A\in\mathbb{R}^{d\times r}$, $r<d$, $\rm Span(A)$
denotes its column space, $A_{\perp}\in\mathbb{R}^{d\times(d-r)}$ the
orthonormal basis of the complement of $\rm Span(A)$, $[A]_{i}$ its $i$th
column, $\sigma_{i}(A)$ its $i$th largest singular value, and $\|A\|_{F}$ its
Frobenius norm. We use $\|x\|$ to denote the $L_{2}$ norm if $x$ is a vector
and the spectral norm if $x$ is a matrix. Let $A$ and $B$ be two orthonormal
basis of two subspaces $\mathcal{A},\mathcal{B}\subset\mathbb{R}^{d\times r}$.
Define $\sin\bm{\theta}_{1}(A,B):=\sin(\bm{\theta}_{1})$ and
$\sin\bm{\theta}_{r}(A,B):=\sin(\bm{\theta}_{r})$, where $\bm{\theta}_{1}$ and
$\bm{\theta}_{r}$ are computed by the singular value decomposition
$A^{\top}B=UDV^{\top}$ with $D={\rm
diag}(\cos\bm{\theta}_{1},\dots,\cos\bm{\theta}_{r})$ satisfying
$0\leq\bm{\theta}_{r}\leq\dots\leq\bm{\theta}_{1}\leq\frac{\pi}{2}$. Following
[38], the distance between $\mathcal{A}$ and $\mathcal{B}$ is defined as ${\rm
dist}(\mathcal{A},\mathcal{B})=\|{\rm
diag}(\sin\bm{\theta}_{1},\dots,\sin\bm{\theta}_{r})\|_{F}=\|A^{\top}B_{\perp}\|_{F}$.
Given a positive number $x$, $\lceil x\rceil$ denotes the smallest integer
that is greater than or equal to $x$. Given two functions
$f,g:\mathbb{R}^{+}\to\mathbb{R}^{+}$, we write $f(x)=O(g(x))$ if there is
$M_{o}>0$ and $x_{0}>0$ such that $f(x)\leq M_{o}g(x)$ for all $x\geq x_{0}$,
and $f(x)=\tilde{O}(g(x))$ if $f(x)=O(g(x)\log^{k}(x))$. Also, we denote
$f(x)=\Omega(g(x))$ if there is $M_{\Omega}>0$ and $x_{0}>0$ such that
$f(x)\geq M_{\Omega}g(x)$ for all $x\geq x_{0}$, and $f(x)=\Theta(g(x))$ if
$f(x)=O(g(x))$ and $f(x)=\Omega(g(x))$.

##  2 Problem Setup

In this paper, we consider the following multi-task sequential linear bandits
model:

$\displaystyle y_{t}=x_{t}^{\top}\theta_{q(t)}+\eta_{t},$ (1)

where $x_{t}\in\mathcal{A}\subseteq\mathbb{R}^{d}$ is the action taken by the
agent at round $t$, $\theta{\in\mathbb{R}^{d}}$ is the bandit coefficient, and
$\eta_{t}$ is the additive noise that is assumed to be zero mean $1$-sub-
Gaussian, i.e.,
$\mathbb{E}[e^{\lambda\eta_{t}}]\leq\exp({\frac{\lambda^{2}}{2}})$ for any
$\lambda>0$.

Notice that the coefficient vector $\theta_{q(t)}$ is time-varying. We assume
that $q(t)=\lceil\frac{t}{N}\rceil$, where $t=1,2,\dots,SN$. That is, the
agent plays $S$ bandits in sequence and interacts with each bandit for $N$
rounds111We make this assumption for simplicity. Our results can be readily
generalized to the case where bandits are played for different rounds.. Then,
the task sequence can be denoted as
$\mathcal{S}:=\\{\theta_{1},\theta_{2},\dots,\theta_{S}\\}$.

We further assume that these tasks are drawn from $m$ different environments,
$\mathcal{E}_{1},\mathcal{E}_{2},\dots,\mathcal{E}_{m}$ (each
$\mathcal{E}_{k}$ is a set of tasks). Specifically, the task sequence
$\mathcal{S}$ can be divided into $m$ consecutive subsequences (see Fig. 2),
i.e.,

$\displaystyle\mathcal{S}=\\{\mathcal{S}_{1},\mathcal{S}_{2},\dots,\mathcal{S}_{m}\\},$

such that $\mathcal{S}_{k}\subseteq\mathcal{E}_{k}$ for $k=1,2,\dots,m$.
Denote $\tau_{k}$ as the number of tasks in $\mathcal{S}_{k}$; it satisfies
$\sum_{i=k}^{m}\tau_{k}=S$. We assume that, for each environment
$\mathcal{E}_{k}$, there exists a matrix $B_{k}\in\mathbb{R}^{d\times r_{k}}$
with orthonormal columns such that

$\displaystyle\exists\alpha_{i}\in\mathbb{R}^{r_{k}}:\theta_{i}=B_{k}\alpha_{i}$

for any $\theta_{i}\in\mathcal{E}_{k}$. This assumption is motivated by the
fact that real-world tasks often share low-dimensional structures, called
representations [3]. As for the examples in Fig. 1, the representation can
describe the common preferences of a user group on a music streaming platform
or a certain sorting rule of the Wisconsin sorting task. With a slight abuse
of terminology, we refer to $B_{k}$ as the representation of the $k$th
environment, $k=1,\dots,m$. For simplicity, we assume that the representations
have the same dimension222Our results can be applied to the situation with
heterogeneous $r_{k}$ by simply letting $r=\max_{k}r_{k}$., i.e., $r_{k}=r$
for all $k=1,\dots,m$.

The goal is to maximize the cumulative reward $\sum_{t=1}^{SN}y_{t}$ by
interacting with the sequential bandits in the non-stationary environments.
The agent knows $\sigma(t),N,d$, and $r$, but has no knowledge of
$\theta_{i}$, $B_{k}$, and $\tau_{k}$ for any $i=1,\dots,S$ and $k=1,\dots,m$.
To measure the agent’s performance in the $T:=SN$ rounds, we introduce the
(pseudo-)regret

$\displaystyle R_{T}=\sum_{t=1}^{T}(x_{t}^{*}-x_{t})^{\top}\theta_{{q(t)}},$
(2)

where $x^{*}_{t}=\arg\max_{x\in\mathcal{A}}x^{\top}\theta_{{q(t)}}$ is the
optimal action that maximizes the reward at round $t$. Maximizing the
cumulative reward is then equivalent to minimizing the regret $R_{T}$.

Following existing studies (e.g., see [39, 40]), we assume that the following
assumptions on the action set $\mathcal{A}$ and the task coefficients
$\theta_{i}$ hold throughout this paper.

######  Assumption 1 (Linear bandits).

We assume that: (a) the action set $\mathcal{A}$ is the ellipsoid of the form
$\\{x\in\mathbb{R}^{d}:x^{\top}M^{-1}x\leq 1\\}$, where $M$ is a symmetric
positive definite matrix, and (b) there are positive constants $\theta_{\min}$
and $\theta_{\max}$ so that $\theta_{\min}\leq\|\theta_{s}\|\leq\theta_{\max}$
for all $s\in\\{1,2,\dots,S\\}$.

Figure 2: Sequential tasks in non-stationary environments. The tasks are taken
from different environments $\mathcal{E}_{1},\dots,\mathcal{E}_{m}$, forming
subsequences $\mathcal{S}_{1},\dots,\mathcal{S}_{m}$. The tasks in each
environment share a low-dimensional representation (descried by
$B_{k},k=1,\dots,m$). In each subsequence $\mathcal{S}_{k}$, there are
$\tau_{k}$ tasks, but $\tau_{k}$’s are not known a priori.

Limitation of Independent Strategies. Under the stated assumptions, previous
work (e.g., see [41, 39, 40]) shows that the regret of single-task bandits is
lower bounded by $\Omega(d\sqrt{d})$. Intuitively, if the sequential bandits
$\mathcal{S}=\\{\theta_{1},\theta_{2},\dots,\theta_{S}\\}$ are independently
played by those standards algorithms, the best performance is optimally
$\Theta(Sd\sqrt{N})$.

Potential Benefits of Representation Learning. In the case of an oracle where
the representations $B_{1},\dots,B_{m}$ are known, it holds that
$\theta_{i}=B_{k}\alpha_{i}$ for any $\theta_{i}\in\mathcal{S}$. Letting
$z_{t}=B_{k}^{\top}x_{t}$, the $d$-dimensional bandit
$y_{t}=x_{t}^{\top}\theta_{i}+\eta_{t}$ becomes a $r$-dimensional one
$y_{t}=z_{t}^{\top}\alpha_{i}+\eta_{t}$ with $\alpha_{i}\in\mathbb{R}^{r}$.
Following [41, 39, 40], one can show that the best performance of an algorithm
can be optimally $\Theta(Sr\sqrt{N})$, which indicates a significant
performance improvement compared to the standard algorithms if $r\ll d$. The
reason is that learning to make decisions is accomplished in much lower-
dimensional subspaces. The above observation implies potential benefits of
representation learning, that is, exploring and exploiting the underlying low-
dimensional structure between bandit tasks can facilitate more efficient
decision-making.

In our setting, representation learning has two main challenges. First, how
can the agent explore and exploit representation in the sequential setting?
Particularly, striking the balance between exploration and exploitation
becomes more challenging than the situation where bandits are played
concurrently [34, 35]. There is a trade-off between the need to explore more
sequential tasks (more data samples) to obtain a more accurate representation
estimate and the incentive to exploit the learned representation for more
efficient learning and higher immediate rewards. Second, how can the agent
deal with environment changes? The remainder of this paper aims to address
these challenges.

##  3 Representation Learning in Sequential Bandits: Within-environment Policy

In this section, we show how the agent can improve its performance by using
representation learning in the sequential setting. The main result is the
sequential representation learning algorithm (SeqRepL, see Algorithm 3), a
within-environment policy that deals with individual segments of tasks drawn
from the same environment.

###  3.1 Sequential Representation Learning Algorithm

The key feature of SeqRepL is to balance representation exploration and
exploitation without knowing the duration of each environment. To show how
SeqRepL works, we first restrict our attention to a series of bandit tasks in
this section:

$\displaystyle\mathcal{T}=\\{\theta_{1},\dots,\theta_{\tau}\\},$ (3)

where the number of tasks $\tau$ is unknown, and the representation shared by
the tasks is $B\in\mathbb{R}^{d\times r}$.

Algorithm 1 Representation Exploration (RepE)

1:Input: $N$, $N_{1}$, {$a_{1},\dots,a_{d}$}.

2:for $t=1:N_{1}$ do

3: Take the action $x_{t}=a_{i}$, $i=({t-1\mod d})+1$

4:end for

5:Compute $\hat{\theta}=(X_{\rm E}X_{\rm E}^{\top})^{-1}X_{\rm E}Y_{\rm E}$

6:for $t=N_{1}+1:N$ do

7: Take the action $x_{t}=\arg\max_{x\in\mathcal{A}}x^{\top}\hat{\theta}$

8:end for

Algorithm 2 Representation Transfer (RepT($\hat{B}$))

1:Input: $N$, $N_{2}$, $\hat{B}\in\mathbb{R}^{d\times r}$,
$\\{a_{1}^{\prime},\dots,a_{r}^{\prime}\\}$

2:for $t=1:N_{2}$ do

3: Take the action $x_{i}=a^{\prime}_{i}$, $i=({t-1\mod r})+1$

4:end for

5:Compute $\hat{\alpha}=(\hat{B}^{\top}X_{\rm T}X_{\rm
T}^{\top}\hat{B})^{-1}\hat{B}^{\top}X_{\rm T}Y_{\rm T}$ and
$\hat{\theta}=\hat{B}\hat{\alpha}$

6:for $t=N_{2}+1:N$ do

7: Take the action $x_{t}=\arg\max_{x\in\mathcal{A}}x^{\top}\hat{\theta}$

8:end for

Algorithm 3 SeqRepL

1:Input: $L$, $N_{1}$, $N_{2}$, $n$. Initialize: $\hat{P}=0_{d\times d}$.

2:for cycle $n=1,2,\dots$ do

3: Rep Exploration: play $L$ tasks in $\mathcal{T}$ using RepE,

4: $\hat{P}=\hat{P}+\hat{\theta}_{i}\hat{\theta}_{i}^{\top}$ $\triangleright$
fixed duration: $L$

5: $\hat{B}\leftarrow$ the left-singular vectors associated with the largest
$r$ singular values of $\hat{W}=\frac{1}{nL}\hat{P}$

6: Rep Transfer: play $nL$ tasks in $\mathcal{S}_{\tau}$ using RepT($\hat{B}$)
$\triangleright$ increasing duration: $nL$

7:end for

SeqRepL operates in a cyclic manner, which is inspired by the PEGE algorithm
[39]. It alternates between two sub-algorithms—representation exploration
(RepE, see Algorithm 1) and representation transfer (RepT, see Algorithm 2).
Both RepE and RepT are explore-then-commit (ETC) algorithms, consisting of two
stages, i.e., exploration and commitment.

RepE. At the exploration stage of $N_{1}$ rounds, $d$ actions,
$a_{1},\dots,a_{d}$, are repeatedly taken in sequence. These actions can be
arbitrarily chosen but need to be linearly independent such that they span the
action space defined by $\mathcal{A}$. In this paper, we simply let
$a_{i}=\lambda_{0}e_{i}$, where $e_{i}$ is the $i$th canonical vector of
$\mathbb{R}^{d}$ and $\lambda_{0}>0$ is such that $a_{i}\in\mathcal{A}$ for
all $i$. Then, the coefficient $\theta$ is estimated by the least-squares
regression

$\displaystyle\hat{\theta}=(X_{\rm E}X_{\rm E}^{\top})^{-1}X_{\rm E}Y_{\rm
E},$

where $X_{\rm E}=[x_{1},\dots,x_{N_{1}}]$ and $Y_{\rm
E}=[y_{1},\dots,y_{N_{1}}]^{\top}$ respectively collect the actions and
rewards at this stage. At the commitment stage, the greedy action
$x_{t}=\arg\max_{x\in\mathcal{A}}x^{\top}\hat{\theta}$ is taken for $N-N_{1}$
times.

RepT. Different from RepE, RepT utilizes $\hat{B}\in\mathbb{R}^{d\times r}$ as
a plug-in surrogate for the unknown representation $B$ to learn the
coefficient $\theta$. The exploration stage is accomplished in the
$r$-dimensional space $\rm Span(\hat{B})$. Specifically, $r$ actions
$a^{\prime}_{1},\dots,a^{\prime}_{r}$, are repeatedly taken for $N_{2}$
rounds. These actions can be arbitrarily chosen in $\rm Span(\hat{B})$ such
that they are linearly independent. In this paper, we let
$a_{i}^{\prime}=\lambda_{0}[\hat{B}]_{i}$, where $\lambda_{0}>0$ is such that
$a_{i}^{\prime}\in\mathcal{A}$. To estimate $\theta$, RepT computes $\alpha$
first. Observe that
$y_{t}=x_{t}^{\top}\theta+\eta_{t}=x_{t}^{\top}B\alpha+\eta_{t}$. Then,
$\alpha$ is estimated with $\hat{B}$ by the least-squares regression

$\displaystyle\hat{\alpha}=(\hat{B}^{\top}X_{\rm T}X_{\rm
T}^{\top}\hat{B})^{-1}\hat{B}^{\top}X_{\rm T}Y_{\rm T},$

where $X_{\rm T}=[x_{1},x_{2},\dots,x_{N_{2}}]$ and $Y_{\rm
T}=[y_{1},y_{2},\dots,y_{N_{2}}]^{\top}$. Subsequently, $\theta$ is estimated
by $\hat{\theta}=\hat{B}\hat{\alpha}$. Similar to RepE,
$x_{t}=\arg\max_{x\in\mathcal{A}}x^{\top}\hat{\theta}$ is taken at the
commitment stage.

SeqRepL. As shown in Algorithm 3, there are two phases in each cycle of
SeqRepL. Specifically, for each cycle $n\in\\{1,2,\dots\\}$, these phases are:

1) Representation Exploration phase: $L$ tasks ($L$ is to be designed) are
played using RepE. Let
$\hat{W}=\frac{1}{nL}\sum_{i}\hat{\theta}_{i}\hat{\theta}_{i}^{\top}$ where
$\hat{\theta}_{i}$’s are all the estimated coefficients obtained by RepE in
all the previous $n$ cycles. Then, the representation $B$ is estimated by
performing the singular value decomposition (SVD) to $\hat{W}$. Specifically,
$\hat{B}$ takes the singular vectors associated with the $r$ largest singular
values of $\hat{W}$, i.e., $\hat{B}=\hat{U}_{1}$ with
$\hat{U}_{1}\in\mathbb{R}^{d\times r}$ taken from the SVD:
$\hat{W}=[\hat{U}_{1},\hat{U}_{2}]\hat{\Sigma}\hat{V}^{\top}$.

2) Representation Transfer phase: the latest representation estimate $\hat{B}$
is transferred. Specifically, $nL$ sequential tasks are played using
RepT($\hat{B}$).

Notice that for any cycle $n$, $L$ more tasks are played using RepT than the
previous $(n-1)$th cycle. We next show that this alternating scheme balances
representation exploration and exploitation excellently.

######  Assumption 2 (Task diversity).

Suppose that there exist an integer $\ell$ and a constant $\nu>0$ such that
any subsequence of length $\ell$ in the sequence in Eq. (3) satisfies
$\sigma_{r}(W_{s}W_{s}^{\top}/\ell)\geq\frac{\nu}{r}>0$ for any $s$, where
$W_{s}=[\theta_{s+1},\dots,\theta_{s+\ell}]$.

This assumption states that the sequential tasks well spread the entire
$r$-dimensional subspace. It ensures that this subspace can be reconstructed
before all the bandit tasks are played, which is crucial to allow for transfer
learning in the sequential setting. A similar assumption is found in [34],
wherein bandits are played concurrently. Representation learning in the
sequential setting is more challenging, thus our assumption is slightly
stronger.

######  Theorem 1 (Upper bound of SeqRepL).

Let the agent play the series of bandits in Eq. (3) using SeqRepL in Algorithm
3. Select an $L$ such that333Here, the exact knowledge of $\ell$ is not
required; instead, knowing the order of $\ell$ is sufficient. In practice, the
assumption can be further relaxed. In Fig. 5, we will show that a wide range
of $L$ can be chosen without knowing $\ell$, while still guaranteeing the
performance of our algorithms. $L=\Theta(\ell)$, and let
$N_{1}=dr\sqrt{{N}/{L}}$ and $N_{2}=r\sqrt{N}$. Then, the regret $R_{\tau N}$
of SepRepL satisfies

$\displaystyle\mathbb{E}[R_{\tau N}]={\tilde{O}\Big{(}{dr\sqrt{\tau
N}}+{\frac{dr}{\lambda_{0}^{2}\nu^{2}}\sqrt{\tau N}}+\frac{d\ell}{r}\sqrt{\tau
N}+\tau r\sqrt{N}\Big{)}}.$ (4)

The third term in (4) is the regret incurred when transferring the oracle
representation, and the first three terms include the regret that results from
representation exploration and transferring the estimated representation with
errors.

######  Remark 1 (Performance comparison).

Recall that if the same series of bandits are played using standard algorithms
that play bandits independently, e.g., UCB [41], PEGE [39], and ETC [42], the
best regret is optimally $\Theta(\tau d\sqrt{N})$. Compared to these
algorithms, SeqRepL can have better or worse performance (i.e., “positive” or
“negative” transfer), depending on the properties of the bandit tasks in (3):

  * •

If
$\tau\gg\max\\{r^{2},\frac{r^{2}}{\lambda_{0}^{4}\nu^{4}},\frac{\ell^{2}}{r^{2}}\\}$
and $d\gg r$, using SeqRepL can significantly improve the performance444We
note that positive transfer can still occur in practice without satisfying
this inequality. In Figs. 4 and 5, we let $\tau=400$ for
$\lambda_{0}=1,\ell=r=3$, and $\nu\approx 0.01$, much smaller than $9\times
10^{8}$ required by the inequality here. Nevertheless, our algorithms still
outperform the standard ones significantly.;

  * •

If
$\tau\ll\max\\{r^{2},\frac{r^{2}}{\lambda_{0}^{4}\nu^{4}},\frac{\ell^{2}}{r^{2}}\\}$,
the bound in (4) implies that the cost of learning the representation can
overwhelm the possible benefits of transfer learning. Then, using SeqRepL may
result in a situation of negative transfer.

Our algorithm is particularly advantageous over the standard ones when there
are a large number of tasks in the sequence. Also, in sharp contrast to
existing bandit algorithms using representation learning, e.g., ([34, 35]) our
algorithm requires no knowledge of $\tau$.

The following corollary provide an upper bound of SeqRepL if $\ell$ in
Assumption 2 is of the order of $r^{2}$.

######  Corollary 1.

Assume that $\ell$ in Assumption 2 is of the order of $r$, i.e.,
$\ell=\Theta(r^{2})$. Let $N_{1}=d\sqrt{rN}$ and $N_{2}=r\sqrt{N}$. Then, the
regret of SepRepL for the sequential bandits in Eq. (3) satisfies
$\mathbb{E}[R_{\tau N}]=\tilde{O}\left(dr\sqrt{\tau
N}+{\frac{dr}{\lambda_{0}^{2}\nu^{2}}\sqrt{\tau N}}+\tau r\sqrt{N}\right)$.

If $\frac{1}{\lambda_{0}^{2}\nu^{2}}=\Theta(1)$, the regret bound becomes
$\mathbb{E}[R_{\tau N}]=\tilde{O}\left(dr\sqrt{\tau N}+\tau r\sqrt{N}\right)$.
For the series of bandits in Eq. (3), it follows from [34] that the lower
bound is $\Omega(d\sqrt{r\tau N}+\tau r\sqrt{N})$. Note that there is just a
gap of $\tilde{O}(\sqrt{r})$ between our upper bound and this lower bound.

###  3.2 Analysis of Theorem 1

We first provide some instrumental results, and we refer the readers to
Appendix A-C for their proofs.

######  Lemma 1 (Regret of RepE).

Given a bandit task $\theta\in\mathcal{T}$, let the agent play it using RepE
in Algorithm 1 for $N$ rounds. Then, the regret $R_{N}$ of RepE satisfies
$\mathbb{E}[R_{N}]=O(N_{1}+\frac{N}{N_{1}}d^{2})$.

######  Lemma 2 (Regret of RepT).

Given a bandit task $\theta\in\mathcal{T}$, assume that there exists
$B\in\mathbb{R}^{d\times r}$ with orthonormal columns such that
$\theta=B\alpha$ for some $\alpha\in\mathbb{R}^{r}$. Assume that an estimate
$\hat{B}$ is known and satisfies
$\|\hat{B}^{\top}B_{\perp}\|_{F}\leq\varepsilon$. Let the agent play this task
for $N$ rounds using RepT($\hat{B}$) in Algorithm 2, then the regret satisfies
$\mathbb{E}[R_{N}]=O(N_{2}+\frac{N}{N_{2}}r^{2}+N\varepsilon^{2}).$

######  Theorem 2 (Accuracy of learned representation).

Let the agent play the series of bandits in Eq. (3) using SeqRepL in Algorithm
3. Then, for any cycle $n$, the estimate $\hat{B}$ at the end of the
representation exploration phase satisfies

$\displaystyle\|\hat{B}^{\top}B_{\perp}\|_{F}\leq\tilde{O}\left(\frac{dr}{\lambda_{0}\nu}{\sqrt{\frac{1}{nLN_{1}}}}\right),$
(5)

with probability at least $1-\frac{1}{kN_{1}}$.

Recall that $\|\hat{B}^{\top}B_{\perp}\|_{F}$ measures the distance between
$\hat{B}$ and the true representation $B$. This distance decreases with $n$,
implying that $\hat{B}$ becomes progressively more accurate as more tasks are
explored by the RepE algorithm.

Proof of Theorem 1: In the $n$th cycle of SepRepL, $L$ tasks are played in the
representation exploration phase. Then, it follows from Lemma 1 that the
regret in this phase, denoted as $R_{\rm RepE}(n)$, satisfies
$\mathbb{E}R_{\rm RepE}(n)=O\big{(}LN_{1}+L\frac{N}{N_{1}}d^{2}\big{)}.$ From
Theorem 2, we have

$\displaystyle\|\hat{B}^{\top}B_{\perp}\|_{F}\leq\tilde{O}\Big{(}\frac{dr}{\lambda_{0}\nu}{\sqrt{\frac{1}{nLN_{1}}}}\Big{)}.$

Then, $nL$ bandit tasks are played utilizing the RepT($\hat{B}$) algorithm. It
follows from Lemma 2 that the regret in the RepT phase, denoted as $R_{\rm
RepT}(n)$, satisfies

$\displaystyle\mathbb{E}[R_{\rm RepT}(n)]$
$\displaystyle=\tilde{O}\big{(}{nL}N_{2}+nL\frac{N}{N_{2}}r^{2}+{nL}N\frac{d^{2}r^{2}}{\lambda_{0}^{2}\nu^{2}}{\frac{1}{nLN_{1}}}\big{)}$
$\displaystyle=\tilde{O}\big{(}{nL}N_{2}+nL\frac{N}{N_{2}}r^{2}+{\frac{d^{2}r^{2}}{\lambda_{0}^{2}\nu^{2}}}\frac{N}{N_{1}}\big{)}.$

Observe that there are at most $\bar{L}=\lceil\sqrt{{2\tau}/{L}}\rceil$ cycles
in the series (3) since $L\bar{L}+L\bar{L}(\bar{L}+1)/2\geq\tau$. Summing up
the regret in the representation exploration and exploitation phases in all
the cycles, we obtain

$\displaystyle\mathbb{E}[R_{\tau N}]$
$\displaystyle={\sum_{n=1}^{\bar{L}}\big{(}R_{\rm RepL}(n)+R_{\rm
RepT}(n)\big{)}}$
$\displaystyle\leq{\tilde{O}\Big{(}\bar{L}\big{(}LN_{1}+L\frac{N}{N_{1}}d^{2}\big{)}+\sum_{n=1}^{\bar{L}}\big{(}{nL}N_{2}+nL\frac{N}{N_{2}}r^{2}+{\frac{d^{2}r^{2}}{\lambda_{0}^{2}\nu^{2}}}\frac{N}{N_{1}}\big{)}\Big{)}}.$

Since $N_{1}={dr\sqrt{N/L}}$, $N_{2}=r\sqrt{N}$ and
$\bar{L}=\lceil\sqrt{{2\tau}/{L}}\rceil$, we have $\mathbb{E}[R_{\tau
N}]=\tilde{O}\big{(}{dr\sqrt{\tau
N}}+{\frac{dr}{\lambda_{0}^{2}\nu^{2}}\sqrt{\tau
N}}+\frac{dL}{r}\sqrt{N\tau}+\tau r\sqrt{N}\big{)}.$ Then, (4) follows from
$L=\Theta(r^{2})$. $\blacksquare$

##  4 Environment Change Detection

To handle environment changes, we propose the representation change detection
algorithm (RepCD, see Algorithm 4). It is the key to endow the agent with
adaptability.

###  4.1 Representation change detection algorithm

To show how RepCD works, we consider the environment change where the
representation switches from $B\in\mathbb{R}^{d\times r}$ to
$\bar{B}\in\mathbb{R}^{d\times r}$ (see Fig. 3 (a)). To detect this
environment change, we seek for the tasks that do not belong to the subspace
$\rm Span(B)$. To infer whether a task is an outlier to $\rm Span(B)$, RepCD
takes some probing actions and monitors the rewards. The probing actions need
to ensure: (1) when a task is not in $\rm Span(B)$, it can be detected as an
outlier with high probability; and (2) when a task is in $\rm Span(B)$, it can
be falsely detected as an outlier with low probability.

The key idea is to select probing actions in the orthogonal complement $\rm
Span(B_{\perp})$, which is illustrated in Fig. 3 (b). A task $\theta$ is in
the subspace $\rm Span(B)$ if and only if $B^{\top}_{\perp}\theta=0$. To
generate an accurate test, all the directions defined by the columns of
$B_{\perp}$ need to be covered by the probing actions. A naive strategy is to
choose $d-r$ actions by simply exhausting the columns of $B_{\perp}$, i.e.,
let $x_{i}=\lambda_{0}[B_{\perp}]_{i}^{\top},i=1,\dots,d-r$, where
$\lambda_{0}>0$ is such that $\lambda_{0}[B_{\perp}]_{i}\in\mathcal{A}$.
Taking these actions, the agent is expected to receive rewards satisfying
$y_{i}=\lambda_{0}[B_{\perp}]_{i}^{\top}\theta+\eta_{i}=\eta_{i}$ if
$\theta\in\rm Span(B)$. If the agent receives some rewards that exceed the
noise level, the task $\theta$ is likely an outlier of the current
representation.

However, one may not need as many as $d-r$ probing actions if the environment
change happens between two very different representations. It is also possible
that more than $d-r$ probing actions are required to detect a more subtle
environment change. Next, we show how to choose probing actions by taking both
of these situations into account.

First, let $n_{\rm det}$ be the number of probing actions (we will show how to
select $n_{\rm det}$ soon). Observe that any $n_{\rm det}$ can be rewritten
into $n_{\rm det}=k(d-r)+\bar{n}$, where $k$ can be $0,1,2\dots$. The first
$k(d-r)$ probing actions simply take the actions
$\\{x_{i}=\lambda_{0}[B_{\perp}]_{i},i=1,\dots,d-r\\}$ for $k$ times. How to
choose the remainder of $\bar{n}$ actions is more interesting.

We require all the $d-r$ directions in $\rm Span(B_{\perp})$ to be covered,
which ensures that informed decisions are made for representation change
detection, especially when $k=0$. To do that, we use the idea of random
projection [43]. First, we generate a projection matrix $P$ that projects from
$\mathbb{R}^{d-r}$ onto a random $\bar{n}$-dimensional subspace uniformly
distributed in the Grassmann manifold $G_{(d-r),\bar{n}}$ (which consists of
all $\bar{n}$-dimensional subspaces in $\mathbb{R}^{d-r}$). One can obtain a
matrix $Q\in\mathbb{R}^{(d-r)\times\bar{n}}$ with orthonormal columns that
satisfies $P=QQ^{\top}$. Then, the $\bar{n}$ remaining actions are generated
by taking the columns out from the matrix $M=B_{\perp}Q$.

Figure 3: Illustration of environment change detection. (a) Along with the
environment change, the representation switches from $B$ to $\bar{B}$. (b)
Probing actions are randomly generated in the orthogonal complement of the
current representation.

Finally, we have completed selecting all the $n_{\rm det}$ probing actions,
which are included in the set

$\displaystyle\mathcal{A}_{\rm
det}:=\\{\underbrace{\hat{\mathcal{A}},\dots\hat{\mathcal{A}}}_{k},\lambda_{0}[M]_{1},\dots,\lambda_{0}[M]_{\bar{n}}\\},$
(6)

where
$\hat{\mathcal{A}}:=\\{\lambda_{0}[B_{\perp}]_{1},\dots,\lambda_{0}[B_{\perp}]_{(d-r)}\\}$,
and $\lambda_{0}$ is a scalar such that all the actions in $\mathcal{A}_{\rm
det}$ is in $\mathcal{A}$.

Let $Y_{\rm det}=[y_{1},\dots,y_{n_{\rm det}}]^{\top}$ collect the rewards. We
build a confidence interval for $Y_{\rm det}$, which is

$\displaystyle\mathcal{C}_{\rm det}=\left\\{Y\in\mathbb{R}^{n_{\rm
det}}:\left|\frac{1}{\sqrt{n_{\rm det}}}\|Y\|_{2}-1\right|\leq\xi_{\rm
det}\right\\},$

where $\xi_{\rm det}$ is the detection threshold. For the task $\theta$, if
$Y_{\rm det}\in\mathcal{C}_{n_{\rm det}}$ is observed, we say $\theta$ is not
an outlier; if $Y_{\rm det}\notin\mathcal{C}_{\rm det}$ is observed, we say
$\theta$ is an outlier and, subsequently, there is an environment change.

Algorithm 4 Rep Change Detection (RepCD($B$))

1:Input: $B\in\mathbb{R}^{d\times r}$, $n_{\rm det}$.

2:take $n_{\rm det}$ probing actions in $\mathcal{A}_{\rm det}$, $Y_{\rm
det}=[y_{1},\dots,y_{n_{\rm det}}]^{\top}$

3:if $Y_{\rm det}\notin\mathcal{C}_{n_{\rm det}}$ then

4: Rep Change indicator $\mathbb{I}_{\rm det}=1$

5:end if

The next lemma shows how to select the detection threshold $\xi_{\rm det}$ and
the number of probing actions $n_{\rm det}$ such that an outlier can be
detected with high probability.

######  Lemma 3 (Outlier detection: oracle representation).

Consider two representations $B$ and $\bar{B}$ and any task $\theta$
satisfying $\theta=\bar{B}\alpha$ for some $\alpha$. Assume that
$\sin\bm{\theta}_{r}(B,\bar{B})=\kappa_{1}$. Let

$\displaystyle n_{\rm
det}={\Bigl{\lceil}\frac{9(d-r)\log(2S^{2}N)}{\theta_{\min}^{2}\lambda_{0}^{2}\kappa_{1}^{2}}}\Bigr{\rceil},\xi_{\rm
det}={\sqrt{\frac{\log(2S^{2}N)}{4n_{\rm det}}}}.$ (7)

Then, the task $\theta$ can be detected as an outlier to $B$ by RepCD($B$) in
Algorithm 4 with probability at least $1-O(\frac{1}{S^{2}N}).$

Note that the distance of the two subspaces $B$ and $\bar{B}$ is measured by
the smallest angle $\sin\bm{\theta}_{r}(B,\bar{B})$. From Lemma 3, it can be
seen that fewer probing actions (smaller $n_{\rm det}$) are needed to detect a
change between two representations with a larger distance. Notice that, in
Lemma 3, we have used the oracle $B$ in RepCD to detect outliers. However, the
agent usually has just access to an estimate $\hat{B}$. The following lemma
states that if $\hat{B}$ is sufficiently accurate, an outlier can still be
detected with high probability.

######  Lemma 4 (Outlier detection: estimated representation).

Consider the representation change in Lemma 3. Assume that $\hat{B}$, which
satisfies
$\|\hat{B}^{\top}B_{\perp}\|_{F}\leq\varepsilon\leq\frac{1}{3}\kappa_{1}$, is
known. Let $n_{\rm det}$ and $\xi_{\rm det}$ be as in Eq. (7). Then, the task
$\theta$ can be detected as an outlier to $B$ by RepCD($\hat{B}$) in Algorithm
4 with probability at least $1-O(\frac{1}{S^{2}N}).$

##  5 The Main Algorithm: CD-RepL

In this section, we provide the main results in this paper.

###  5.1 CD-RepL

We present the main algorithm, i.e., the change-detection representation
learning algorithm (CD-RepL). CD-RepL uses the strategies that we have
presented in the previous two sections to perform representation learning and
to adapt to changing environments.

CD-RepL proceeds as follows. If a new environment is detected by RepCD (the
first environment is also regarded as a new one), the agent first performs
initial representation exploration. In this period, $bL$ sequential tasks are
played and an initial representation estimate $\hat{B}$ is constructed. Then,
using this $\hat{B}$, the agent starts to test every task to infer whether
there is an environment change using RepCD. If there is no representation
change, the agent plays the sequential bandits using SeqRepL in Algorithm 3.
Note that SeqRepL starts from the $(b+1)$th cycle instead of the first one.
Meanwhile, $\hat{B}$ is constantly updated. Once detecting a new environment,
the agent restarts the above processes.

Notice that the initial representation exploration plays an important role in
CD-RepL. It provides the agent with a rough but acceptable estimate of the
underlying representation such that the agent can avoid false detection with
high probability (see Lemma 5). Moreover, after the initial exploration
SeqRepL does not need to start from the first cycle because of the initial
estimate $\hat{B}$. By starting from $(b+1)$th cycle, it avoids the
unnecessary exploration phases in the first $b$ cycles. Let us explain how to
select $b$.

First, we choose the number of probing actions $n_{\rm det}$ and the detection
threshold $\xi_{\rm det}$ since the choice of $b$ depends on them. In the
previous section, they are chosen in the case of two representations. For the
case of $m$ representations, we use the same idea. Let
$\kappa:=\min\\{\sin\bm{\theta}_{r}(B_{i},B_{i+1}),i=1,\dots,m-1\\}$. Then, we
let

$\displaystyle n_{\rm
det}={\Bigl{\lceil}\frac{9(d-r)\log(2S^{2}N)}{\theta_{\min}^{2}\lambda_{0}^{2}\kappa^{2}}\Bigr{\rceil}},{\xi_{\rm
det}=2\sqrt{\frac{\log(2S^{2}N)}{n_{\rm det}}}}.$ (8)

Subsequently, we let

$\displaystyle b={\Bigl{\lceil}\frac{9dr\theta_{\max}^{2}n_{\rm
det}}{4\nu^{2}\sqrt{\ell N}(d-r)\log(2S^{2}N)}\Bigr{\rceil}}.$ (9)

The expressions in Eqs. (8) and (9) are guided by the following underlying
ideas:

(1) Fewer probing actions ($n_{\rm det}$) and a larger detection threshold
($\xi_{\rm det}$) are sufficient to detect representation changes if the
distance between representations are larger.

(2) The choice of $b$ needs to balance between the need to explore more tasks
such that the initial estimate of $\hat{B}$ is sufficiently accurate to avoid
false detection and the incentive to explore fewer tasks to incur less regret.

Algorithm 5 CD-RepL

1:Input: $b$, $L$ Initialize: $\hat{B}=I_{d}$, $\hat{P}=\bm{0}$, the new Rep
indicator $\mathbb{I}_{\rm det}=1$

2:if $\mathbb{I}_{\rm NewRep}=1$ (i.e., a new environment detected) then

3: reset $\hat{P}=\bm{0}$;

4: play $bL$ tasks using RepE with $N_{1}=dr\sqrt{\frac{N}{\ell}}$,
$\hat{P}=\hat{P}+\hat{\theta}_{i}\theta_{i}^{\top}$;

5: $\hat{B}\leftarrow$ top $r$ singular value decomposition of
$\hat{W}=\frac{1}{bL}\hat{P}$;

6: set $n_{\rm st}=b+1$.

7:else

8: invoke RepCD, update $\mathbb{I}_{\rm det}$

9:end if

10:if $\mathbb{I}_{\rm det}=0$ then

11: invoke SeqRepL that starts from the $n_{\rm st}$th cycle.

12:end if

The following theorem provides an upper bound for CD-RepL, which also
justifies our choice of $n_{\rm det}$, $\xi_{\rm det}$, and $b$.

######  Theorem 3 (Upper bound of CD-RepL).

Let the agent play the sequential bandits in $\mathcal{S}$ using the CD-RepL
in Algorithm 5. Let $L=\Theta(\ell)$, $n_{\rm det}$ and $\xi_{\rm det}$ be as
in Eq. (8), and $b$ be as in Eq. (9). Then, the regret of the CD-RepL
satisfies

$\displaystyle\mathbb{E}[R_{T}]=\tilde{O}\Big{(}$
$\displaystyle{\underbrace{\sum_{i=1}^{m}\big{(}{dr\sqrt{\tau_{i}N}}+{\frac{dr}{\lambda_{0}^{2}\nu^{2}}\sqrt{\tau_{i}N}}+\frac{d\ell}{r}\sqrt{\tau_{i}N}\big{)}+Sr\sqrt{N}}_{(a)}}$
$\displaystyle\hskip 51.21504pt{+\underbrace{Sn_{\rm
det}+mbdr\sqrt{N\ell}}_{(b)}+\underbrace{2m}_{(c)}}\Big{)}.$ (10)

The regret incurred by CD-RepL can be decomposed into three parts. Term (a)
follows from Theorem 1, which is the regret incurred by the SepRepL for each
environment. Term (b) is the regret incurred by the probing actions for each
task and the initial representation exploration for each environment. Term (c)
is due to unsuccessful detection and false detection. Similar to Remark 1,
whether CD-SepL outperforms the existing algorithms that treat bandits
independently depends on the relationship between the parameters
$d,r,\ell,\lambda_{0},\nu,\kappa,\tau,S$ and $m$. To make the dependence more
clear, we provide the following corollary.

######  Corollary 2.

Assume that $\ell=\Theta(r)$, $1/(\lambda_{0}^{2}\nu^{2})=\Theta(1)$, and
$\kappa$ satisfies

$\displaystyle\kappa\geq\max\big{\\{}\min\\{p_{1},p_{2}\\},\min\\{p_{3},p_{4}\\}\big{\\}},$
(11)

where

$\displaystyle
p_{1}=\frac{3S^{\frac{1}{4}}(d-r)^{\frac{1}{2}}\sqrt{\log(2S^{2}N)}}{2d^{\frac{1}{2}}r^{\frac{1}{2}}N^{\frac{1}{4}}\theta_{\min}\lambda_{0}},$
$\displaystyle
p_{2}=\frac{3(d-r)^{\frac{1}{2}}\sqrt{\log(2S^{2}N)}}{2r^{\frac{1}{2}}N^{\frac{1}{4}}\theta_{\min}\lambda_{0}}$
$\displaystyle
p_{3}=\frac{3(d-r)^{\frac{1}{2}}q^{\frac{1}{2}}m^{\frac{1}{2}}}{4r^{\frac{1}{2}}N^{\frac{1}{4}}S^{\frac{1}{4}}\nu\theta_{\min}\lambda_{0}},\hskip
12.0ptp_{4}=\frac{3d^{\frac{1}{2}}(d-r)^{\frac{1}{2}}q^{\frac{1}{2}}m^{\frac{1}{2}}}{4r^{\frac{1}{2}}N^{\frac{1}{4}}S^{\frac{1}{2}}\nu\theta_{\min}\lambda_{0}}.$

Then, the regret of CD-RepL for the sequential tasks in $\mathcal{S}$
satisfies

$\displaystyle\mathbb{E}[R_{SN}]=\tilde{O}\Big{(}\sum\nolimits_{i=1}^{m}{dr\sqrt{\tau_{i}N}}+Sr\sqrt{N}\Big{)}.$
(12)

The reason that the upper bound in Theorem 3 reduces to the one in Eq. (12) is
because Terms (b) and (c) in Eq. (3) are dominated by Term (a) if $\kappa$ is
lower bounded as in Eq. (11). Further, observing that
$\sum\nolimits_{i=1}^{m}{dr\sqrt{\tau_{i}N}}\leq dr\sqrt{SmN}$, the upper
bound of the regret in Eq. (12) can be rewritten into
$\tilde{O}\Big{(}dr\sqrt{mSN}+Sr\sqrt{N}\Big{)}.$ Recall that algorithms like
UCB, ETC, and PEGE (e.g., see [41, 39, 40]) that play the sequential bandits
independently have a regret bound $\Theta(Sd\sqrt{N})$. Under the assumption
$r\ll d$, CD-RepL outperforms these algorithms considerably if $S/m>r^{2}$. In
other words, our algorithm is advantageous over the existing ones if: (a) the
dimension of linear representation is much smaller than the task dimension;
(b) the underlying representation does not change too fast. Notice that if the
agent plays the $S$ tasks simultaneously, the regret upper bound can be up to
$O(Sd\sqrt{N})$ even if the idea of representation learning is used. This is
because the entire set of the $S$ tasks may not share a common representation,
although some of its subsets do (this point will be demonstrated in Fig. 4 in
Section 6).

######  Remark 2.

We remark that the assumption of $\kappa$ in Eq. (11) is mild. The right-hand
side of Eq. (11) becomes very small if $d\ll N$.

###  5.2 Analysis of Theorem 3

Let us provide an instrumental result first, whose proof is in Appendix E.

######  Lemma 5 (Probability of a false detection).

Consider the case where there is only one environment (i.e, $m=1$) in the task
sequence $\\{\theta_{1},\theta_{2},\dots,\theta_{S}\\}$, and the underlying
representation is $B\in\mathbb{R}^{d\times r}$. Let the agent play this
sequence of tasks using CD-RepL. Let $\hat{B}$ be the estimated representation
after the initial sample phase of $bL$ tasks, the probability that a task
$\theta$ is detected by RepCD($\hat{B}$) as an outlier, denoted by $\Pr[Y_{\rm
det}\notin\mathcal{C}_{\rm det}|\theta=B\alpha]$, is less than
$O(\frac{1}{S^{2}N})$.

Proof of Theorem 3: Recall that $\tau_{i}$ sequential tasks are taken from
each set $\mathcal{S}_{i}$. Therefore, the representations change after the
$(\sum_{i=1}^{p-1}\tau_{i})$-th task is played, where $p=2,\dots,m$. For the
simplicity of nation, denote $v_{i}=(\sum_{j=1}^{i}\tau_{j}+1),i=1,\dots,m-1$
as the instants when the environment switches happen. Let $\mu_{i}$ be the
detection time of the $i$th switch (i.e., the $\mu_{i}$th task is detected as
an outlier to the $i$th representation). Therefore, the event
$D_{i}=\\{\mu_{i}=v_{i}\\}$ is a good event, which describes the situations
that the $i$th representation switch is detected immediately after it happens.
The event $G_{i}=\\{\mu_{i}>v_{i}\\}$ denotes a late or an unsuccessful
detection. The event $F_{i}=\\{\mu_{i}<v_{i}\\}$ denotes a false detection,
which describes the situation that an alarm is triggered when there is no
representation switch.

First, we consider the case with two representations (i.e., 1 representation
switch), and the sequential tasks
$\underbrace{\\{\theta_{1},\dots,\theta_{\tau_{1}}}_{B_{1}},\underbrace{\theta_{\tau_{1}+1},\dots,\theta_{\tau_{1}+\tau_{2}}}_{B_{2}}\\}$
are played using CD-RepL in Algorithm 5. The regret of CD-RepL given $D_{1}$
satisfies

$\displaystyle{\mathbb{E}[R_{(\tau_{1}+\tau_{2})N}|D_{1}]\lesssim}$
$\displaystyle{\underbrace{\sum_{i=1}^{2}{dr\sqrt{\tau_{i}N}}+{\frac{dr}{\lambda_{0}^{2}\nu^{2}}\sqrt{\tau_{i}N}}+\frac{d\ell}{r}\sqrt{N\tau_{i}}+\tau_{i}r\sqrt{N}}_{(a)}}$
$\displaystyle{+\underbrace{(\tau_{1}+\tau_{2})n_{\rm
det}}_{(b)}+\underbrace{2bdr\sqrt{N\ell}}_{(c)}}.$ (13)

Note that term (a) is the regret incurred by SeqRepL in individual
subsequence, which follows from Theorem 1; term (b) is incurred by the probing
actions for each task; and term (c) results from the initial representation
exploration.

If the event $G_{1}$ happens, the regret of CD-RepL satisfies

$\displaystyle{\mathbb{E}[R_{(\tau_{1}+\tau_{2})N}|G_{1}]\lesssim}$
$\displaystyle{\underbrace{({dr\sqrt{\tau_{1}N}}+{\frac{dr}{\lambda_{0}^{2}\nu^{2}}\sqrt{\tau_{1}N}}+\frac{d\ell}{r}\sqrt{N\tau_{1}}+\tau_{1}r\sqrt{N})}_{(i)}}$
$\displaystyle{\underbrace{(\tau_{1}+\tau_{2})n_{\rm
det}+bdr\sqrt{N\ell}}_{(ii)}+\underbrace{\tau_{2}N}_{(iii)}}.$ (14)

Here, the terms (i) and (ii) are the regret in the first subsequence, which
follows from Eq. (5.2). If the representation switch is detected after $v_{i}$
or not detected at all, the regret for the second subsequence would be bounded
by $O(\tau_{2}N$), which results in the term (iii). This is intuitive since
there are $\tau_{2}$ tasks in the second subsequence and the regret of each
task is bounded by $O(N)$.

If the event $F_{1}$ happens, the regret of CD-RepL satisfies

$\displaystyle\mathbb{E}[R_{(\tau_{1}+\tau_{2})N}|F_{1}]\lesssim(\tau_{1}+\tau_{2})N.$
(15)

From Lemma 3, it can be derived that $\Pr[D_{1}]\geq 1-O(\frac{1}{S^{2}N})$.
The event $G_{1}$ means that $D_{1}$ does not happen. It can be calculated
that $\Pr[G_{1}]\leq O(\frac{1}{S^{2}N})$. The event $F_{1}$ means that there
is at least $1$ false detection in the first subsequence. From Lemma 5, we
know that the probability that a task is detected as an outlier falsely is
less than $O(\frac{1}{S^{2}N})$. Then, the probability of $F_{1}$ can be
calculated as

$\displaystyle\Pr[F_{1}]\leq 1-(1-O(\frac{1}{S^{2}N}))^{\tau_{1}}\leq
O(\frac{\tau_{1}}{S^{2}N}).$

Putting together Eqs. (5.2)–(15) and using the law of total expectation, it
can be computed that the regret of CD-RepL satisfies

$\displaystyle{\mathbb{E}[R_{(\tau_{1}+\tau_{2})N}]}$
$\displaystyle{\lesssim\sum_{i=1}^{2}({dr\sqrt{\tau_{i}N}}+{\frac{dr}{\lambda_{0}^{2}\nu^{2}}\sqrt{\tau_{i}N}}+\frac{d\ell}{r}\sqrt{N\tau_{i}}+\tau_{i}r\sqrt{N})}$
$\displaystyle+(\tau_{1}+\tau_{2})n_{\rm det}+2bdr\sqrt{N\ell}+2,$ (16)

where the last term on the right-hand side follows from $\tau_{2}N\cdot
O(\frac{1}{S^{2}n})+(\tau_{1}+\tau_{2})N\cdot O(\frac{\tau_{1}}{S^{2}N})\leq
O(2)$.

The upper bound in Eq. (5.2) can be generalized to the case where there are
$m-1$ representation switches. In this case, the upper bound of the regret of
CD-RepL becomes

$\displaystyle{\mathbb{E}[R_{SN}]\lesssim}$
$\displaystyle{\sum_{i=1}^{m}({dr\sqrt{\tau_{i}N}}+{\frac{dr}{\lambda_{0}^{2}\nu^{2}}\sqrt{\tau_{i}N}}+\frac{d\ell}{r}\sqrt{N\tau_{i}}+\tau_{i}r\sqrt{N})}$
$\displaystyle{+\sum_{i=1}^{m}\tau_{i}n_{\rm det}+mbdr\sqrt{N\ell}+2(m-1)}$
$\displaystyle\leq$
$\displaystyle{\sum_{i=1}^{m}\big{(}{dr\sqrt{\tau_{i}N}}+{\frac{dr}{\lambda_{0}^{2}\nu^{2}}\sqrt{\tau_{i}N}}+\frac{d\ell}{r}\sqrt{\tau_{i}N}\big{)}+Sr\sqrt{N}}$
$\displaystyle{+Sn_{\rm det}+mbdr\sqrt{N\ell}+2m}.$

which completes the proof. $\blacksquare$

##  6 Illustrative Examples

We perform some experiments to validate our theoretical results and
demonstrate the efficacy of our algorithm.

Synthetic Data. We first synthesize a set of data to demonstrate our
algorithm. Specifically, we consider a series of $1600$ bandit tasks of
dimension 20. There are four segments in this sequence, and each has 400
tasks. In each segment, there is a representation
$B_{i}\in\mathbb{R}^{20\times 3}$. The parameters in Assumption 2 are $\ell=3$
and $\nu=0.01$. The action set is the unit ball defined by
$\mathcal{A}=\\{x\in\mathbb{R}^{20}:\|x\|\leq 1\\}$. The noise in the reward-
generating function is assumed to be Gaussian $\mathcal{N}(0,0.3)$. Each task
is played for $2000$ rounds.

Table 1: Baselines Algorithms | Description
---|---
| play bandits independently
Standard | (e.g., ETC [42], PEGE [39] and UCB [41, 40])
| the single representation for all bandits is known
Semi-oracle | (i.e., $B$ such that satisfies $\theta_{i}=B\alpha_{i}$ for all $i$ is known555Such $B$ always has no smaller dimension that those of within-environment representations, and it may not exist if $\theta_{i}$’s span the entire $\mathbb{R}^{d}$. Note that existing algorithms (e.g., [34, 35]) that play bandits simultaneously and exploit representation learning cannot outperform the semi-oracle algorithm since they need to estimate the representation. )
Non-adaptive | disabled environment change detection
Oracle | representations and change times are known
Figure 4: Performance comparison between different algorithms using synthetic
data. Upper panels: regret; lower panels: distance between $\hat{B}$ to the
changing true representation $B$. In (a), (b), and (c), environment changes
involving different representation distances are considered. Shaded areas
contain 10 random realizations of trials. Figure 5: Performance of CD-SepL
when $L$ is set to different values. The parameters are the same as in Fig. 4
(b).

We compare our algorithm (CD-RepL) with four other algorithms in Table 1. We
consider several situations where environment changes involve different
representation distances (which is measured by
$\sin\bm{\theta}_{r}(B_{i},B_{i+1}),i=1,2,3$).

The Oracle outperforms CD-RepL as expected since the latter needs to pay the
cost of learning the representations and detecting the environment changes.

From the upper panels in Fig. 4, CD-RepL always outperforms Standard,
consistent with our theoretical results. Compared with Semi-oracle, CD-SeqL
outperforms the existing algorithms that learn the single representation
shared by all the bandits. The reason is that this representation may not
exist or have a high dimension even if the subsets of tasks have low-
dimensional representations.

Further, we disable the environment change detection of our algorithm (i.e.,
Non-adaptive) and compare it with CD-RepL. CD-RepL is particularly
advantageous over Non-adaptive when representations change drastically (see
Fig. 4 (a)); the advantage decreases when it comes to more subtle changes (see
Fig. 4 (b)). For sufficiently small changes, Non-adaptive can even perform
better (see Fig. 4 (c)). This is because the price of detecting the changes
and re-learning each representation may overwhelm the potential benefits of
transferring the learned representations. However, CD-RepL have a much more
stable performance in all situations. The lower panels in Fig. 4 illustrate
that CD-SepL can detect environment changes in different situations involving
drastic or subtle representation changes, which is the key to endow CD-SepL
with the adaptability. By contrast, Non-adaptive can no longer learn the true
representations accurately after the first environment change.

Recall that our theoretical results rely on fact that the order of $\ell$ in
Assumption 2 is known since the number of tasks in each representation cycle
is set to be $L=\Theta(\ell)$. Yet, this assumption is not required in
practice. As shown in Fig. 5, CD-RepL has similar performance for a wide range
of $L$. This implies that, even if $\ell$ is unknown, one can always choose an
$L$ that is likely larger than $\ell$ without compromising the performance
much compared to the case of letting $L=\ell$.

LastFM. We use this dataset to demonstrate that our algorithm can be used to
design an adaptive recommendation system as depicted in Fig. 1 (b). This
dataset is extracted from the music streaming service Last.fm. It contains
1892 users, 17632 artists, and a listening count of user-artist pairs. We
first remove the artists that have fewer than 40 listeners and the users who
listened fewer than 10 artists, and obtain a matrix $M=[m_{ij}]$ of size
$411\times 1565$ with each row representing an artists and each column a user.
To generate arms and users, we use the non-negative matrix factorization for
$M$ and keep the first $20$ latent features. In other words, $M\approx AU$,
where $A\in\mathbb{R}^{411\times 20}$ and $U\in\mathbb{R}^{20\times 1565}$ are
non-negative and describe the features of the artists and users, respectively.
From $U$, we select 3 groups of users that approximately lie in distinct
subspaces, consisting $11$, $6$, and $6$ users, respectively. These users form
a series of bandits $\theta_{1},\dots,\theta_{23}$ that have different
2-dimensional representations. We then recommend music items to these users
for 200 times from the action set $\mathcal{A}$ that is composed of the row
vectors of $A$. The reward is generated by
$y_{t}=x_{t}^{\top}\theta_{i}+\eta_{t}$, where $x_{t}\in\mathcal{A}$ and
$\eta_{t}$ is Gaussian noise $\mathcal{N}(0,0.2)$. In Fig. 6 it can be
observed that, by learning and exploiting the representation shared by users
and detecting environment changes our algorithm outperforms the existing ones
that treat bandits independently.

Figure 6: Performance comparison between different algorithms as
recommendation systems using LastFM data. Shaded areas contain 10 random
realizations of trials.

Wisconsin Card Sorting Task (WCST). WCST, see Fig. 1 (b), is typically
utilized to assess human abstraction and shift of contexts [44]. Participants
need to match a series of stimulus cards to one of the four cards on the table
based on a sorting rule. For the stimulus card in Fig. 1 (b), if the rule is
color, the correct sorting action is the third card. The participants only
receive feedback about whether their actions are correct. For convenience, we
assume that they receive reward 1 for a correct action, and 0 otherwise.
Participants do not know the current sorting rule, thus need to infer it by
trial and error. The sorting rule changes every now and then, which makes the
task challenging.

WCST can actually be described by a bandit problem with environment changes,
where representations define the sorting rules. Specifically, we use a matrix
of size $4\times 3$, $A=[a_{1},a_{2},a_{3}]$, to describe each card. Here, the
vectors $a_{1},a_{2}$ and $a_{3}$ define the number, color, and shape,
respectively, and they take value from the $4$-dimensional standard basis
$\\{e_{1},e_{2},e_{3},e_{4}\\}$. The matrix $A=[e_{i},e_{j},e_{m}]$ describes
a card that has the $i$th number, the $j$th color, and the $m$th shape of the
4 cards on the table. For instance, the stimulus card in Fig. 1 (b) can be
described by the matrix $A=[e_{2},e_{3},e_{1}]$. Further, we use a vector $B$
to describe the sorting rule, which takes value from the basis
$\\{b_{1},b_{2},b_{3}\\}$ of $\mathbb{R}^{3}$, representing the sorting rule
is number, color, and shape, respectively.

Figure 7: Performance comparison for different algorithms in WCST, where the
sorting rule changes after ever 20 rounds. Shaded areas contain 10
realizations.

As a consequence, the reward of WCST is generated by
$y_{t}=x^{\top}_{t}\theta_{t}$ with $\theta_{t}=A_{t}B_{\sigma(t)}$, where
$x_{t}$ is the action that takes value from the $4$-dimensional standard basis
$\\{e_{1},e_{2},e_{3},e_{4}\\}$, $A_{t}$ is the card at round $t$. Notice that
$B_{\sigma(t)}$ that describes the sorting rule can be regarded as the time-
varying representation in the reward function.

For standard reinforcement learning algorithms, such as tabular-Q-learning and
deep-Q-learning, WCST is challenging. There are in total $4^{3}$ possible
stimulus cards (4 colors, 4 numbers, 4 shapes), and for each stimulus card,
there are 4 possible categories. To find the best policy, the standard
tabular-Q-learning needs many samples to construct the Q table for a single
sorting rule. It is then impossible for the standard Q learning algorithm to
find the optimal policy if the sorting rule changes in a few trials (in Fig. 7
it changes every 20 rounds). Being unaware of rule changes results in an even
worse performance. The deep-Q-learning algorithm666Here, we formalize each
input state by a 3-dimensional vector (shape, number,
color)${}^{\top}\in\\{1,2,3,4\\}^{3}$. The result in Fig. 7 considers a three
layer neural network with 3, 12, and 4 nodes in the input, hidden, and output
layers, respectively. Deeper or wider structures were also considered, but
similar performances were obtained. does not perform better since, similarly,
it always needs a large number of samples to train the weights in the neural
network to find the optimal policy. It can be seen from Fig. 7 that these two
algorithms perform barely better than the one that takes a random action at
each round.

However, by describing the WCST as a linear bandit model, we find that the
problem can reduce to learning the representation $B_{\sigma(t)}$, as the
correct action can be computed as $x^{*}_{t}=A_{t}B_{t}$. The problem then
reduces to learn the underlying representation $B_{\sigma}$, a task that is
much easier than constructing the Q table or training the weights in a Deep-Q
network. Remarkably, one does not even need to learn individual $\theta_{t}$
to construct $B_{\sigma}$. Instead, $B_{\sigma}$ can be recovered as
$B_{\sigma}=(\sum\nolimits_{t=1}^{k}A_{t}^{\top}x_{t}x_{t}^{\top}A_{t})^{-1}\sum\nolimits_{t=1}^{k}A_{t}^{\top}x_{t}y_{t}$
immediately after $\sum_{t=1}^{k}A_{t}^{\top}x_{t}x_{t}^{\top}A_{t}$ becomes
invertible. This indicates that our idea in this paper can apply to more
general situations. As shown in Fig. 7, our algorithm significantly
outperforms the other two, approaching the oracle that makes correct choice at
every round. This experiment suggests that the ability to learn
representations and shift attention [2, 45] to adapt to environment changes
facilitates efficient learning.

##  7 Concluding Remarks

In this paper, we exploit representation learning for decision-making in non-
stationary environments using the framework of multi-task sequential linear
bandits. We propose an efficient decision-making algorithm that learns and
transfers representations online. Employing a representation-change-detection
strategy, our algorithm also has the flexibility to adapt to new environments.
We further obtain an upper bound for the algorithm, analytically showing that
it significantly outperforms the existing ones that treat tasks independently.
Moreover, we perform some experiments using synthetic data to demonstrate our
theoretical results. Using the LastFM data, we show that our algorithm can be
applied to designing adaptive recommendation systems. In the Wisconsin Card
Sorting Task, experimental results show that our algorithm considerably
outperforms some classic reinforcement learning algorithms.

Directions of future work include nonlinear representation learning,
representation-based clustering, and task-tailored representation generation
from experience in bandit and reinforcement learning problems.

## Appendix

####  A Proof of Lemma 1

###### Proof.

Without loss of generality, we assume that $N_{1}$ is a multiple of $d$.
Following similar steps as those in Lemma 3.4 of [39], we can obtain that
after $N_{1}$ steps of exploration

$\displaystyle\mathbb{E}[\|\hat{\theta}-\theta\|^{2}]\leq\frac{d^{2}}{N_{1}}.$

From [39], it holds that
$\max_{x\in\mathcal{A}}x^{\top}\theta-\max_{x\in\mathcal{A}}x^{\top}\hat{\theta}\leq
J{\|\theta-\hat{\theta}\|^{2}}/{\|\theta\|}$, where $J$ is a constant that
exists since the action set $\mathcal{A}$ is an ellipsoid. Since
$\|\theta\|\geq\theta_{\min}$, it follows that

$\displaystyle\mathbb{E}\big{[}\max_{x\in\mathcal{A}}x^{\top}\theta-\max_{x\in\mathcal{A}}x^{\top}\hat{\theta}\big{]}\leq
J\frac{\mathbb{E}\|\theta-\hat{\theta}\|^{2}}{\theta_{\min}}\leq
J\frac{d^{2}}{N_{1}\theta_{\min}}.$ (17)

Further, at the exploration phase it holds with
$g(\theta):=\arg\max_{x\in\mathcal{A}}x^{\top}\theta$ that

$\displaystyle g^{\top}(\theta)\theta-x_{t}^{\top}\theta$
$\displaystyle\leq\max_{x\in\mathcal{A}}x^{\top}\theta-\max_{x\in\mathcal{A}}x^{\top}(-\theta)\leq
2J\theta_{\max}.$

Therefore, the total regret in $N$ steps satisfies

$\displaystyle\mathbb{E}[R_{N}]$ $\displaystyle\leq
2J\theta_{\max}N_{1}+(N-N_{1})J\frac{d^{2}}{N_{1}\theta_{\min}}$
$\displaystyle=O(N_{1}+\frac{N}{N_{1}}d^{2}),$

which completes the proof. ∎

####  B Proof of Lemma 2

###### Proof.

Without loss of generality, we assume that $N_{2}$ is a multiple of $r$.
Recall that, at the end of the exploration phase, $\hat{\alpha}$ is computed
by
$\hat{\alpha}=(\hat{B}^{\top}X_{T}X_{T}^{\top}\hat{B})^{-1}\hat{B}^{\top}X_{T}Y_{T}$.
Since $x_{t}$ repeatedly takes actions from
$a^{\prime}_{1},\dots,a^{\prime}_{r}$, it holds that
$X_{T}X_{T}^{\top}={N_{2}}AA^{\top}/r$ with
$A=[a^{\prime}_{1},\dots,a^{\prime}_{r}]$. Therefore, we have
$\hat{\alpha}=\big{(}{N_{2}}\hat{B}^{\top}AA^{\top}\hat{B}/r\big{)}^{-1}\hat{B}^{\top}X_{T}Y_{T}.$
Since $a_{i}^{\prime}=\lambda_{0}[\hat{B}]_{i}$, it holds that
$A=\lambda_{0}\hat{B}$, which implies that
$\big{(}{N_{2}}\hat{B}^{\top}AA^{\top}\hat{B}/r\big{)}^{-1}=\frac{r}{\lambda_{0}^{2}N_{2}}I_{r}$.
Consequently,

$\displaystyle\hat{\alpha}=\frac{r}{\lambda_{0}^{2}N_{2}}\hat{B}^{\top}X_{T}Y_{T}.$

As $Y_{T}=X_{T}^{\top}B\alpha+\eta$ with
$\eta=[\eta_{1},\dots,\eta_{N_{2}}]^{\top}$, we have

$\displaystyle\hat{\alpha}$
$\displaystyle=\frac{r}{\lambda_{0}^{2}N_{2}}\hat{B}^{\top}X_{T}(X_{T}^{\top}B\alpha+\eta)$
$\displaystyle=\frac{r}{\lambda_{0}^{2}N_{2}}\frac{N_{2}}{r}\hat{B}^{\top}AA^{\top}B\alpha+\frac{r}{\lambda_{0}^{2}N_{2}}\hat{B}^{\top}X_{T}\eta$
$\displaystyle=\hat{B}^{\top}B\alpha+\frac{r}{\lambda_{0}^{2}N_{2}}\hat{B}^{\top}X_{T}\eta.$

As $\hat{\theta}=\hat{B}\hat{\alpha}$ and $\theta=B\alpha$, it follows that

$\displaystyle\hat{\theta}-\theta=\hat{B}\hat{\alpha}-B\alpha=\underbrace{\hat{B}\hat{B}^{\top}B\alpha-B\alpha}_{s_{1}}+\underbrace{\frac{r}{\lambda_{0}^{2}N_{2}}\hat{B}\hat{B}^{\top}X_{T}\eta}_{s_{2}}.$

Next, we evaluate $\mathbb{E}\|\hat{\theta}-\theta\|^{2}$. Since
$\mathbb{E}s_{1}^{\top}s_{2}=0$, it holds that
$\mathbb{E}\|\hat{\theta}-\theta\|^{2}\leq\mathbb{E}\|s_{1}\|^{2}+\mathbb{E}\|s_{2}\|^{2}$.

Observe that
$I_{d}=\hat{B}\hat{B}^{\top}+\hat{B}_{\perp}\hat{B}^{\top}_{\perp}$. Thus, we
have

$\displaystyle\mathbb{E}\|s_{1}\|^{2}=\|(I_{d}-\hat{B}_{\perp}\hat{B}^{\top}_{\perp})B\alpha-B\alpha\|^{2}=\|\hat{B}_{\perp}\hat{B}^{\top}_{\perp}B\alpha\|^{2}.$

Because $\|\hat{B}^{\top}_{\perp}B\|_{F}\leq\varepsilon$, we have

$\displaystyle\mathbb{E}\|s_{1}\|^{2}\leq\|\hat{B}_{\perp}\|^{2}\cdot\|\hat{B}^{\top}_{\perp}B\|^{2}_{F}\cdot\|\alpha\|^{2}\leq\mu\varepsilon^{2},$
(18)

where $\mu>0$, which is such that $\|\alpha\|^{2}\leq\mu$, exists since
$\theta=B\alpha$ satisfies $\theta_{\min}\leq\theta\leq\theta_{\max}$.

Now, we evaluate $\mathbb{E}\|s_{2}\|^{2}$, which satisfies

$\displaystyle\mathbb{E}\|s_{2}\|^{2}$
$\displaystyle=\frac{r^{2}}{\lambda_{0}^{4}N_{2}^{2}}\mathbb{E}(\hat{B}\hat{B}^{\top}X_{T}\eta)^{\top}\hat{B}\hat{B}^{\top}X_{T}\eta$
$\displaystyle=\frac{r^{2}}{\lambda_{0}^{4}N_{2}^{2}}\sum_{t=1}^{N_{2}}x_{t}^{\top}\hat{B}\hat{B}^{\top}x_{t}\mathbb{E}\eta_{t}^{2}.$

Since $\eta_{t}$ is sub-Gaussian with variance proxy variable $1$, we have

$\displaystyle\mathbb{E}\|s_{2}\|^{2}\leq\frac{r^{2}}{\lambda_{0}^{4}N_{2}^{2}}\sum_{t=1}^{N_{2}}x_{t}^{\top}\hat{B}\hat{B}^{\top}x_{t}=\frac{r^{2}}{\lambda_{0}^{2}N_{2}}.$
(19)

Putting Eqs. (18) and (19) together, we have
$\mathbb{E}[\|\hat{\theta}-\theta\|^{2}]\leq\frac{r^{2}}{\lambda_{0}^{2}N_{2}}+\mu\varepsilon^{2}$.
Similar to (17), one can derive that

$\displaystyle\mathbb{E}[\max_{x\in\mathcal{A}}x^{\top}\theta-\max_{x\in\mathcal{A}}x^{\top}\hat{\theta}]\leq
J\frac{r^{2}}{\theta_{\min}\lambda_{0}^{2}N_{2}}+J\frac{1}{\theta_{\min}}\mu\varepsilon^{2}.$
(20)

For the commitment phase, there are $N-N_{2}$ steps. Thus, the overall regret
satisfies

$\displaystyle\mathbb{E}[R_{N}]\leq
2J\theta_{\max}N_{2}+(N-N_{2})\mathbb{E}\big{(}\max_{x\in\mathcal{A}}x^{\top}\theta-\max_{x\in\mathcal{A}}x^{\top}\hat{\theta}\big{)}.$

Substituting (20) into the right side yields
$\mathbb{E}[R_{N}]=O(N_{2}+\frac{N}{N_{2}}r^{2}+N\varepsilon^{2})$, which
completes the proof. ∎

####  C Proof of Theorem 2

######  Lemma 6 (Matrix Bernstein’s inequality [43]).

Let $X_{1},X_{2},\dots,X_{k}$ be independent zero-mean $d\times d$ symmetric
random matrices so that there exists $M>0$ such that $\|X_{i}\|\leq M$ almost
surely for all $i=1,2,\dots,k$. Then, for any $t\geq 0$, it holds that
$\Pr\left[\left\|\sum_{i=1}^{k}X_{i}\right\|\geq t\right]\leq
2d\exp\left(\frac{-2t^{2}}{\sigma^{2}+Mt/3}\right),$ where
$\sigma^{2}=\left\|\sum_{i=1}^{k}\mathbb{E}X_{i}\right\|$.

###### Proof.

Denote the $nL$ tasks that are played using RepE as
$\theta_{1},\theta_{2},\dots,\theta_{nL}$, and let $k:=nL$. Then, $\hat{W}$
becomes $\frac{1}{k}\sum_{i=1}^{k}\hat{\theta}_{i}\hat{\theta}_{i}^{\top}$.
Let $W=\frac{1}{k}\sum_{i=1}^{k}\theta_{i}\theta_{i}^{\top}$ be the true
counterpart of $\hat{W}$. The proof is constructed in two steps. In Step 1, we
use Lemma 6 to estimate $\|\hat{W}-(W+D)\|$ with $D$ being a scaled identity
matrix; in Step 2, we use the Davis-Kahan $\sin\bm{\theta}$ Theorem [46] to
evaluate the distance between the top-$r$ singular values of $\hat{W}$ and
$W+D$, which is the distance between $\hat{B}$ and the true $B$ (notice that
$W+D$ and $W$ share the same singular vectors).

Step 1. Let $\eta:=[\eta_{1},\eta_{2},\dots,\eta_{N_{1}}]^{\top}$, and it
holds that $Y_{E}=X_{E}^{\top}\theta_{i}+\eta$. It follows that

$\displaystyle\hat{\theta}_{i}=(X_{E}X_{E}^{\top})^{-1}X_{E}(X_{E}^{\top}\theta_{i}+\eta)=\theta_{i}+(X_{E}X_{E}^{\top})^{-1}X_{E}\eta.$

Some algebraic computations yield

$\displaystyle\hat{\theta}_{i}\hat{\theta}_{i}^{\top}=$
$\displaystyle\theta_{i}\theta_{i}^{\top}+\theta_{i}\eta^{\top}X_{E}^{\top}(X_{E}X_{E}^{\top})^{-1}+(X_{E}X_{E}^{\top})^{-1}X_{E}\eta\theta_{i}^{\top}$
$\displaystyle+(X_{E}X_{E}^{\top})^{-1}X_{E}\eta\eta^{\top}X_{E}^{\top}(X_{E}X_{E}^{\top})^{-1}.$

Since $\eta_{i}$ are independent zero mean 1-sub-Gaussian random variables,
the expectation of $\hat{\theta}_{i}\hat{\theta}_{i}^{\top}$ can be computed
as

$\displaystyle\mathbb{E}\hat{\theta}_{i}\hat{\theta}_{i}^{\top}$
$\displaystyle=\theta_{i}\theta_{i}^{\top}+(X_{E}X_{E}^{\top})^{-1}X_{E}\mathbb{E}\eta\eta^{\top}X_{E}^{\top}(X_{E}X_{E}^{\top})^{-1}$
$\displaystyle=\theta_{i}\theta_{i}^{\top}+(X_{E}X_{E}^{\top})^{-1}.$

Since $[a_{1},a_{2},\dots,a_{d}]$ be the standard basis of $\mathbb{R}^{d}$,
it holds that $\sum_{i=1}^{d}a_{i}a_{i}^{\top}=I_{d}$. Without loss of
generality, we consider $N_{1}$ as a multiple of $d$, then it follows that
$X_{E}X_{E}^{\top}=\frac{N_{1}}{d}\lambda_{0}^{2}I_{d}$. Therefore, we have
$(X_{E}X_{E}^{\top})^{-1}=\frac{d}{\lambda_{0}^{2}N_{1}}I_{d}$. Denote
$D:=\frac{d}{\lambda_{0}^{2}N_{1}}I_{d}$, then it follows that

$\displaystyle\mathbb{E}\hat{\theta}_{i}\hat{\theta}_{i}^{\top}=\theta_{i}\theta_{i}^{\top}+D,$

and

$\displaystyle{\hat{\theta}_{i}\hat{\theta}_{i}^{\top}=\theta_{i}\theta_{i}^{\top}+D\underbrace{\left(\theta_{i}\eta^{\top}X_{E}^{\top}+X_{E}\eta\theta_{i}^{\top}\right)}_{A}+D^{2}\underbrace{\left(X_{E}\eta\eta^{\top}X_{E}^{\top}\right)}_{C}}.$
(21)

Define a set of new variables
$z_{i}=\frac{1}{k}\hat{\theta}_{i}\hat{\theta}_{i}^{\top}-\frac{1}{k}\left(\theta_{i}\theta_{i}^{\top}+D\right)$.
From (21), we have $z_{i}=\frac{1}{k}(DA+D^{2}C-D).$ Then, the expectation of
$z_{i}^{2}$ satisfies

$\displaystyle\mathbb{E}z_{i}^{2}=\frac{1}{k^{2}}\mathbb{E}\big{[}$
$\displaystyle D^{2}A^{2}+D^{4}C^{2}+D^{2}+D^{3}(AC+CA)$
$\displaystyle-2D^{2}A-2D^{3}C\big{]},$ (22)

where the fact that $D$ commutes with any matrix has been used. Since $D$ is
deterministic, to compute $\mathbb{E}z_{i}^{2}$, it suffices to calculate
$\mathbb{E}A^{2},\mathbb{E}C^{2},\mathbb{E}(AC+CA),\mathbb{E}A,$ and
$\mathbb{E}C$.

For $\mathbb{E}A^{2}$, it holds that

$\displaystyle\mathbb{E}A^{2}=$
$\displaystyle\mathbb{E}(\theta_{i}\eta^{\top}X_{E}^{\top})^{2}+\mathbb{E}(X_{E}\eta\theta_{i}^{\top})^{2}+\mathbb{E}(\theta_{i}\eta^{\top}X_{E}^{\top}X_{E}\eta\theta_{i}^{\top})$
$\displaystyle+\mathbb{E}(X_{E}\eta\theta_{i}^{\top}\theta_{i}\eta^{\top}X_{E}^{\top})$
$\displaystyle=$ $\displaystyle
2\frac{\lambda_{0}^{2}N_{1}}{d}\theta_{i}\theta_{i}^{\top}+N_{1}\lambda_{0}^{2}\theta_{i}\theta_{i}^{\top}+\theta_{i}^{\top}\theta_{i}\frac{\lambda_{0}^{2}N_{1}}{d}I_{d}.$

For $\mathbb{E}C^{2}$, we have

$\displaystyle\mathbb{E}C^{2}=\mathbb{E}\left[X_{E}\eta\eta^{\top}X_{E}^{\top}X_{E}\eta\eta^{\top}X_{E}^{\top}\right]$
$\displaystyle{=\mathbb{E}\left[\eta^{\top}X_{E}^{\top}X_{E}\eta\cdot
X_{E}\eta\eta^{\top}X_{E}^{\top}\right]=\mathbb{E}\left[\sum_{t=1}^{N_{1}}\eta_{t}^{4}x_{t}^{\top}x_{t}x_{t}x_{t}^{\top}\right]}$
$\displaystyle{=\psi_{4}\lambda_{0}^{2}\left(\sum_{t=1}^{N_{1}}x_{t}x_{t}^{\top}\right)=\psi_{4}\lambda_{0}^{2}X_{E}X_{E}^{\top}=\frac{\psi_{4}\lambda_{0}^{4}N_{1}}{d}I_{d},}$

where $\psi_{4}=\mathbb{E}\eta_{t}^{4}$ ($\psi_{4}$ always exists since
$\eta_{t}$ is a sub-Gaussian random variable). For $\mathbb{E}(AC+CA)$, it
holds that

$\displaystyle\mathbb{E}$
$\displaystyle(AC+CA)=\mathbb{E}\big{[}\big{(}\theta_{i}\eta^{\top}X_{E}^{\top}+X_{E}\eta\theta_{i}^{\top}\big{)}X_{E}\eta\eta^{\top}X_{E}^{\top}$
$\displaystyle+$ $\displaystyle
X_{E}\eta\eta^{\top}X_{E}^{\top}\left(\theta_{i}\eta^{\top}X_{E}^{\top}+X_{E}\eta\theta_{i}^{\top}\right)\big{]}$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\eta^{\top}X_{E}^{\top}X_{E}\eta\cdot\theta_{i}\eta^{\top}X_{E}^{\top}\right]+\mathbb{E}\left[\theta_{i}^{\top}X_{E}\eta\cdot
X_{E}\eta\eta^{\top}X_{E}^{\top}\right]$ $\displaystyle+$
$\displaystyle\mathbb{E}\left[\eta^{\top}X_{E}^{\top}\theta_{i}\cdot
X_{E}\eta\eta^{\top}X_{E}^{\top}\right]+\mathbb{E}\left[\eta^{\top}X_{E}^{\top}X_{E}\eta\cdot
X_{E}\eta\theta_{i}^{\top}\right]$ $\displaystyle=$
$\displaystyle{\frac{\lambda_{0}^{3}\psi_{3}N_{1}}{d}\theta_{i}\mathbf{1}_{d}^{\top}+\frac{\lambda_{0}^{3}\psi_{3}N_{1}}{d}{\rm
diag}{\theta_{i}}+\frac{\lambda_{0}^{3}\psi_{3}N_{1}}{d}{\rm
diag}{\theta_{i}}+\frac{\lambda_{0}^{3}\psi_{3}N_{1}}{d}\mathbf{1}_{d}\theta_{i}^{\top}}$
$\displaystyle=$
$\displaystyle\frac{\lambda_{0}^{3}\psi_{3}N_{1}}{d}(\theta_{i}\mathbf{1}_{d}^{\top}+\mathbf{1}_{d}\theta_{i}^{\top})+\frac{2\lambda_{0}^{3}\psi_{3}N_{1}}{d}{\rm
diag}{\theta_{i}}.$

Notice that $\mathbb{E}A=0$. For $\mathbb{E}C$, it holds that
$\mathbb{E}C=\mathbb{E}X\eta\eta^{\top}X^{\top}=\frac{\lambda_{0}^{2}N_{1}}{d}I_{d}.$

Overall, substituting all the above terms into Eq. (22) we have

$\displaystyle\mathbb{E}$ $\displaystyle
z_{i}^{2}=\frac{1}{k^{2}}\frac{d^{2}}{\lambda_{0}^{4}N_{1}^{2}}\Big{[}2\frac{\lambda_{0}^{2}N_{1}}{d}\theta_{i}\theta_{i}^{\top}+N_{1}\lambda_{0}^{2}\theta_{i}\theta_{i}^{\top}$
$\displaystyle+\theta_{i}^{\top}\theta_{i}\frac{\lambda_{0}^{2}N_{1}}{d}I_{d}+D^{2}\frac{\psi_{4}\lambda_{0}^{4}N_{1}}{d}I_{d}+I_{d}+D\Big{(}\frac{\lambda_{0}^{3}\psi_{3}N}{d}$
$\displaystyle\cdot(\theta_{i}\mathbf{1}_{d}^{\top}+\mathbf{1}_{d}\theta_{i}^{\top})+\frac{2\lambda_{0}^{3}\psi_{3}N}{d}{\rm
diag}{\theta_{i}}\Big{)}-2D\frac{\lambda_{0}^{2}N}{d}I_{d}\Big{]}$
$\displaystyle\leq\frac{d^{2}}{k^{2}\lambda_{0}^{2}N_{1}}\big{(}\frac{2}{d}+1\big{)}\theta_{i}\theta_{i}^{\top}+O\big{(}\frac{d^{2}}{k^{2}\lambda_{0}^{4}N^{2}_{1}}I_{d}\big{)}.$

Let $\sigma^{2}=\|\sum_{i=1}^{k}\mathbb{E}z_{i}^{2}\|_{F}$, and it satisfies

$\displaystyle{\sigma^{2}\lesssim\left\|\frac{d^{2}}{k\lambda_{0}^{2}N_{1}}\frac{1}{k}\sum_{i=1}^{k}\theta_{i}\theta_{i}^{\top}\right\|_{F}\leq
O\left(\frac{d^{2}}{k\lambda_{0}^{2}N_{1}}{\rm Trace}(W_{k})\right)}.$

Since for any $\theta\in\mathcal{T}$, it holds that
$\theta_{\min}\leq\|\theta\|\leq\theta_{\max}$ with $\theta_{\min}=\Theta(1)$
and $\theta_{\max}=\Theta(1)$, it follows that ${\rm Trace}(W_{k})=\Theta(1)$.
Therefore, it holds that ${\sigma^{2}\leq
O\left(\frac{d^{2}}{k\lambda_{0}^{2}N_{1}}\right)}.$

Applying Lemma 6 with
$t=2c_{1}\log(2dkN_{1})+c_{2}\sqrt{4\sigma^{2}\log(2dkN_{1})}$ for
sufficiently large $c_{1},c_{2}>0$, we have

$\displaystyle{\left\|\sum_{i=1}^{k}z_{i}\right\|_{F}\lesssim\frac{d}{\lambda_{0}}\sqrt{\frac{1}{kN_{1}}}(\sqrt{\log\left({kdN_{1}}\right)}+\log\left({kdN_{1}}\right))}.$

with probability at least $1-\frac{1}{kN_{1}}$.

Notice that $\sum_{i=1}^{k}z_{i}=\hat{W}-(W+D)$. Let $W^{\prime}=W+D$, we have

$\displaystyle{\left\|\hat{W}-W^{\prime}\right\|_{F}:=\|\Delta\|_{F}\lesssim\frac{d}{\lambda_{0}}\sqrt{\frac{1}{kN_{1}}}(\sqrt{\log\left({kdN_{1}}\right)}+\log\left({kdN_{1}}\right))}.$

Step 2. From the Davis-Kahan $\sin\bm{\theta}$ Theorem, we have

$\displaystyle{\|\hat{B}^{\top}B_{\perp}\|_{F}\leq\frac{\|\hat{B}_{\perp}^{\top}(W-W^{\prime})B\|}{\omega}\leq\frac{\|\hat{W}-W^{\prime}\|_{F}}{\omega}},$
(23)

where $\omega=\inf_{1\leq i\leq r,r<j\leq
d}|\lambda_{i}(W^{\prime})-\lambda_{j}(\hat{W})|$. From the Weyl’s Theorem,
$|\lambda_{i}(W^{\prime})-\lambda_{i}(\hat{W})|\leq\|\hat{W}-W^{\prime}\|_{F}=\left\|\sum_{j=1}^{k}z_{j}\right\|_{F}$
for any $i=1,\dots,d$. Since $\lambda_{i}(W^{\prime})=0$ for all $i\geq r+1$,
it holds that $|\lambda_{i}(\hat{W})|\leq\|\Delta\|_{F}$ for all $i\geq r+1$.
Recall that $\sigma_{r}$ is the $r$-th largest eigenvalue of $W$, therefore
$\omega\geq\sigma_{k}-\|\Delta\|_{F}$. From the Assumption 2, we know
$\sigma_{r}\geq\nu/r$, therefore we obtain

$\displaystyle{\|\hat{B}^{\top}B_{\perp}\|_{F}\lesssim\frac{\|\Delta\|_{F}}{\sigma_{r}-\|\Delta\|_{F}}\lesssim\frac{dr}{\lambda_{0}\nu}\sqrt{\frac{1}{nLN_{1}}}\Big{(}\sqrt{\log
dnLN_{1}}+\log dnLN_{1}\Big{)}},$

where $k=nL$ have been used. The proof is complete. ∎

####  D Analysis of Lemmas 3 and 4

Let us present some instrumental results first.

######  Lemma 7 (Random projection, Chap. 5, [43]).

Let $P$ be a projection from $\mathbb{R}^{n}$ onto a random $m$-dimensional
subspace uniformly distributed in the Grassmann manifold $G_{n,m}$. Let
$x\in\mathbb{R}^{n}$ be a fixed point and $\beta>0$. Then, with probability at
least $1-\exp(-c\beta^{2}m)$, we have

$\displaystyle{(1-\beta)\sqrt{\frac{m}{n}}\|x\|_{2}\leq\|Px\|_{2}\leq(1+\beta)\sqrt{\frac{m}{n}}\|x\|_{2}}.$

######  Lemma 8.

Denote $z=B_{\perp}^{\top}\theta$. Let $P$ be a projection matrix from
$\mathbb{R}^{d-r}$ onto a random $m$-dimensional subspace uniformly
distributed in the Grassmann manifold $G_{(d-r),m}$. Then, it holds with
probability at least $1-\exp(-c\beta^{2}m)$ that

$\displaystyle{\frac{1}{2}\sqrt{\frac{m}{d-r}}\|z\|_{2}\leq\|Pz\|_{2}\leq\frac{3}{2}\sqrt{\frac{m}{d-r}}\|z\|_{2}}.$

The proof of Lemma 8 directly follows from Lemma 7 by letting $\beta=1/2$.

######  Lemma 9 (Concentration of the norm, Chap. 3, [43]).

Suppose that $X=[X_{1},X_{2},\dots,X_{n}]^{\top}$ is a random vector, where
$X_{1},\dots,X_{n}$ are independent $\delta$-sub-Gaussian random variable.
Then, for any $\xi>0$ it holds that

$\displaystyle{\Pr\left[\frac{1}{\sqrt{n}}\left|\|X\|_{2}-\delta\right|\geq\xi\right]\leq
2\exp\left(-\frac{cn\xi^{2}}{K^{2}}\right)},$ (24)

where $c$ is an absolute constant and $K=\max_{i}\|X_{i}\|_{\psi_{2}}$ is
assumed $K<1$.

We are now ready to prove Lemmas 3 and 4.

Proof of Lemma 3: We construct the proof by showing that $Y_{\rm det}$ goes
beyond $\mathcal{C}_{\rm det}$ with high probability when the task $\theta$ is
played by RepCD.

Denote $\rho=\|B^{\top}_{\perp}\theta\|$, and from Lemma 8 we have
$\|Q^{\top}B^{\top}_{\perp}\theta\|=\|QQ^{\top}B^{\top}_{\perp}\theta\|\geq\frac{1}{2}\rho\sqrt{{\bar{n}}/{(d-r)}}$
with probability at least $1-\exp(-{c}\bar{n}/4)$ since
$QQ^{\top}B^{\top}_{\perp}\theta$ can be taken as projecting
$B^{\top}_{\perp}\theta$ onto the random subspace spanned by $Q$. The reward
vector $Y_{\rm det}$ satisfies $Y_{\rm
det}=\lambda_{0}G^{\top}B^{\top}_{\perp}\theta+\eta$ with
$G:=[\underbrace{I_{d-r},\dots,I_{d-r}}_{k},Q]$. It follows that

$\displaystyle\Pr\left[Y_{\rm det}\in\mathcal{C}_{\rm det}\right]$
$\displaystyle\leq{\Pr\Big{[}\big{|}\frac{1}{\sqrt{n_{\rm
det}}}\|\lambda_{0}G^{\top}B^{\top}_{\perp}\theta+\eta\|-1\big{|}\leq\xi_{\rm
det}\Big{]}}$ $\displaystyle\leq{\Pr\Big{[}\big{|}\frac{1}{\sqrt{n_{\rm
det}}}\|\eta\|-1\big{|}\geq\frac{\lambda_{0}\rho}{2\sqrt{d-r}}\sqrt{1+\frac{3k(d-r)}{n_{\rm
det}}}-\xi_{\rm det}\Big{]}}$
$\displaystyle\leq{\Pr\Big{[}\big{|}\frac{1}{\sqrt{n_{\rm
det}}}\|\eta\|-1\big{|}\geq\frac{\lambda_{0}\rho}{2\sqrt{d-r}}-\xi_{\rm
det}\Big{]}}.$

Observe that
$\|B^{\top}_{\perp}\theta\|=\|B^{\top}_{\perp}\bar{B}\alpha\|\geq\sigma_{\min}(B^{\top}_{\perp}\bar{B})\|\alpha\|$.
Since $\sigma_{\min}(B^{\top}_{\perp}\bar{B})=\sin\bm{\theta}_{r}(B,\bar{B})$
and $\theta\geq\theta_{\min}$, we have

$\displaystyle|B^{\top}_{\perp}\theta\|\geq\sin\bm{\theta}_{r}(B,\bar{B})\theta_{\min}=\kappa_{1}\theta_{\min}.$

Therefore, we have $\rho\geq\kappa_{1}\theta_{\min}$. From lemma 9, one can
derive that

$\displaystyle{\Pr\left[Y_{\rm det}\in\mathcal{C}_{n_{\rm det}}\right]\leq
2\exp\Big{(}-\frac{cn_{\rm
det}(\frac{1}{2}\kappa_{1}\lambda_{0}\theta_{\min}\sqrt{\frac{1}{d-r}}-\xi_{\rm
det})^{2}}{K^{2}}\Big{)}}.$

Let $n_{\rm
net}=\frac{9(d-r)\log(2S^{2}N)}{\kappa_{1}^{2}\theta_{\min}^{2}\lambda_{0}^{2}}$
and $\xi_{\rm det}=\sqrt{\frac{\log(2S^{2}N)}{4n_{\rm det}}}$. Then, it can be
calculated that $\Pr\left[Y_{\rm det}\in\mathcal{C}_{\rm det}\right]\leq
O(\frac{1}{S^{2}N})$, which means that the outlier $\theta$ to $B$ can be
detected with probability at least $1-O(\frac{1}{S^{2}N})$. The proof is
complete. $\blacksquare$

For Lemma 3, the only difference is that only an estimate $\hat{B}$ satisfying
$\|\hat{B}^{\top}_{\perp}B\|\leq\varepsilon$ is known. It can be derived that
$\|\hat{B}^{\top}_{\perp}\theta\|=\|B^{\top}_{\perp}\bar{B}\alpha\|\geq(\kappa_{1}-\varepsilon)\theta_{\min}$.
Then, following similar steps as those for Lemma 3, one can prove lemma 4.

####  E Proof of Lemma 5

###### Proof.

It follows from the proof of Theorem 2 that, after the initial $bL$ tasks, the
estimated representation $\hat{B}$ satisfies

$\displaystyle\|\hat{B}^{\top}B_{\perp}\|_{F}\lesssim\frac{dr}{\lambda_{0}\nu\sqrt{b\ell
N_{1}}}\big{(}\sqrt{\log(db\ell N_{1})}+\log(db\ell N_{1})\big{)}.$

For the simplicity of notation, let $q=\sqrt{\log(db\ell N_{1})}+\log(db\ell
N_{1})$. For $\theta$, there is $\alpha\in\mathbb{R}^{r}$ such that
$\theta=B\alpha$, which implies that $Y_{\rm
det}=\lambda_{0}G^{\top}\hat{B}^{\top}_{\perp}\theta+\eta=\lambda_{0}G^{\top}\hat{B}^{\top}_{\perp}B\alpha+\eta,$
where $G=[I_{d-r},\dots,I_{d-r},Q]$. Since
$\|Q^{\top}\hat{B}_{\perp}^{\top}\theta\|=\|QQ^{\top}\hat{B}_{\perp}^{\top}\theta\|$,
it follows from Lemma 8 that
$\|Q^{\top}\hat{B}^{\top}_{\perp}\theta\|\leq\frac{3}{2}\|\hat{B}_{\perp}^{\top}\theta\|\sqrt{{\bar{n}}/{(d-r)}}$
with probability at least $1-\exp(-{c}\bar{n}/4)$. Denote
$\varepsilon=\|\hat{B}_{\perp}^{\top}B\|_{F}$, and it can be observed that
$\|\hat{B}_{\perp}^{\top}\theta\|\leq\|\hat{B}_{\perp}^{\top}B\|_{F}\cdot\|\alpha\|\leq\varepsilon\theta_{\max}$.
Subsequently, since $n_{\rm det}=k(d-r)+\bar{n}$, it holds that

$\displaystyle\frac{1}{\sqrt{n_{\rm det}}}\|Y_{\rm det}\|_{2}$
$\displaystyle\leq\frac{1}{\sqrt{n_{\rm
det}}}\big{(}\frac{\lambda_{0}\varepsilon\theta_{\max}}{\sqrt{d-r}}\sqrt{k(d-r)+\frac{9}{4}\bar{n}}+\|\eta\|\big{)}$
$\displaystyle\leq{\frac{3\lambda_{0}\varepsilon\theta_{\max}}{2\sqrt{d-r}}+\frac{1}{\sqrt{n_{\rm
det}}}\|\eta\|\leq\frac{1}{\sqrt{n_{\rm
det}}}\|\eta\|+\underbrace{\frac{3dr\theta_{\max}q}{2\nu\sqrt{bLN_{1}(d-r)}}}_{s}}.$

Then, from Lemma 9, we have

$\displaystyle{\Pr[Y_{\rm det}\notin\mathcal{C}_{\rm det}|\theta=B\alpha]\leq
2\exp\left(-\frac{cn_{\rm det}(\xi_{\rm det}-s)^{2}}{K^{2}}\right)}.$

Substituting Eqs. (9) and (8) into the right-hand side yields
$\Pr[\theta\notin\rm Span(\hat{B})|\theta=B\alpha]\leq\frac{1}{S^{2}N}$ given
$N_{1}=dr\sqrt{N/\ell}$. ∎

## ACKNOWLEDGMENT

This work was supported in part by under Award ARO-78259-NS-MUR and Award
AFOSR-FA9550-20-1-0140.

## References

  * [1] Nicholas T Franklin and Michael J Frank.  Generalizing to generalize: humans flexibly switch between compositional and conjunctive structures during reinforcement learning.  PLoS computational biology, 16(4):e1007720, 2020.
  * [2] Angela Radulescu, Yeon Soon Shin, and Yael Niv.  Human representation learning.  Annual Review of Neuroscience, 44(1):253–273, 2021.
  * [3] Yoshua Bengio, Aaron Courville, and Pascal Vincent.  Representation learning: A review and new perspectives.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8):1798–1828, 2013.
  * [4] Jason D Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo.  Predicting what you already know helps: Provable self-supervised learning.  arXiv preprint arXiv:2008.01064, 2020.
  * [5] Bharath Ramsundar, Steven Kearnes, Patrick Riley, Dale Webster, David Konerding, and Vijay Pande.  Massively multitask networks for drug discovery.  arXiv preprint arXiv:1502.02072, 2015.
  * [6] 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.
  * [7] Maria-Florina Balcan, Mikhail Khodak, and Ameet Talwalkar.  Provable guarantees for gradient-based meta-learning.  In International Conference on Machine Learning, pages 424–433, 2019.
  * [8] Simon Shaolei Du, Wei Hu, Sham M. Kakade, Jason D. Lee, and Qi Lei.  Few-shot learning via learning the representation, provably.  In International Conference on Learning Representations, 2021.
  * [9] Nilesh Tripuraneni, Chi Jin, and Michael I Jordan.  Provable meta-learning of linear representations.  arXiv preprint arXiv:2002.11684, 2020.
  * [10] Nilesh Tripuraneni, Michael Jordan, and Chi Jin.  On the theory of transfer learning: The importance of task diversity.  In Advances in Neural Information Processing Systems, volume 33, pages 7852–7862. Curran Associates, Inc., 2020.
  * [11] Quentin Bouniot, Ievgen Redko, Romaric Audigier, Angélique Loesch, Yevhenii Zotkin, and Amaury Habrard.  Towards better understanding meta-learning methods through multi-task representation learning theory.  arXiv preprint arXiv:2010.01992, 2020.
  * [12] Alina Borkowska, Wiktor Drożdż, Piotr Jurkowski, and Janusz K Rybakowski.  The wisconsin card sorting test and the n-back test in mild cognitive impairment and elderly depression.  The World Journal of Biological Psychiatry, 10(4-3):870–876, 2009\.
  * [13] Sébastien Bubeck and Nicolo Cesa-Bianchi.  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.  Machine Learning, 5(1):1–122, 2012.
  * [14] Lai Wei and Vaibhav Srivastava.  Nonstationary stochastic multiarmed bandits: UCB policies and minimax regret.  arXiv preprint arXiv:2101.08980, 2021.
  * [15] Tomer Gafni and Kobi Cohen.  Learning in restless multiarmed bandits via adaptive arm sequencing rules.  IEEE Transactions on Automatic Control, 66(10):5029–5036, 2021\.
  * [16] Paul Reverdy, Vaibhav Srivastava, and Naomi Ehrich Leonard.  Satisficing in multi-armed bandit problems.  IEEE Transactions on Automatic Control, 62(8):3788–3803, 2016.
  * [17] Lai Wei and Vaibhav Srivastava.  Minimax policy for heavy-tailed bandits.  IEEE Control Systems Letters, 5(4):1423–1428, 2020.
  * [18] Milad Malekipirbazari and Ozlem Cavus.  Risk-averse allocation indices for multi-armed bandit problem.  IEEE Transactions on Automatic Control, 2021.  In Press.
  * [19] Manjesh Kumar Hanawal and Sumit Darak.  Multi-player bandits: A trekking approach.  IEEE Transactions on Automatic Control, 2021.  In Press.
  * [20] D. Kalathil, N. Nayyar, and R. Jain.  Decentralized learning for multiplayer multiarmed bandits.  IEEE Transactions on Information Theory, 60(4):2331–2345, 2014\.
  * [21] Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard.  Social imitation in cooperative multiarmed bandits: Partition-based algorithms with strictly local information.  In IEEE Conf. on Decision and Control, pages 5239–5244. IEEE, 2018.
  * [22] David Martínez-Rubio, Varun Kanade, and Patrick Rebeschini.  Decentralized cooperative stochastic bandits.  In Advances in Neural Information Processing Systems, 2019.
  * [23] Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard.  Distributed cooperative decision making in multi-agent multi-armed bandits.  Automatica, 125:109445, 2021.
  * [24] U. Madhushani and N. E. Leonard.  A dynamic observation strategy for multi-agent multi-armed bandit problem.  In 2020 European Control Conf., pages 1677–1682, 2020.
  * [25] Jingxuan Zhu and Ji Liu.  A distributed algorithm for multi-armed bandit with homogeneous rewards over directed graphs.  In American Control Conference, pages 3038–3043, 2021.
  * [26] Udari Madhushani and Naomi Leonard.  When to call your neighbor? strategic communication in cooperative stochastic bandits.  arXiv preprint arXiv:2110.04396, 2021.
  * [27] Udari Madhushani, Abhimanyu Dubey, Naomi Leonard, and Alex Pentland.  One more step towards reality: Cooperative bandits with imperfect communication.  In Neural Information Processing Systems, 2021.
  * [28] Maria Dimakopoulou, Zhimei Ren, and Zhengyuan Zhou.  Online multi-armed bandits with adaptive inference.  Advances in Neural Information Processing Systems, 2021.
  * [29] Ruohan Zhan, Zhimei Ren, Susan Athey, and Zhengyuan Zhou.  Policy learning with adaptively collected data.  arXiv preprint arXiv:2105.02344, 2021.
  * [30] Mohammad Gheshlaghi Azar, Alessandro Lazaric, and Emma Brunskill.  Sequential transfer in multi-armed bandit with finite set of models.  In Advances in Neural Information Processing Systems, page 2220–2228, 2013.
  * [31] Leonardo Cella, Alessandro Lazaric, and Massimiliano Pontil.  Meta-learning with stochastic linear bandits.  In International Conference on Machine Learning, pages 1360–1370, 2020.
  * [32] Marta Soare, Ouais Alsharif, Alessandro Lazaric, and Joelle Pineau.  Multi-task linear bandits.  In NIPS2014 Workshop on Transfer and Multi-task Learning: Theory meets Practice, 2014.
  * [33] Aniket Anand Deshmukh, Ürün Dogan, and Clayton Scott.  Multi-task learning for contextual bandits.  In NIPS, pages 4851–4859, 2017.
  * [34] Jiaqi Yang, Wei Hu, Jason D Lee, and Simon Shaolei Du.  Impact of representation learning in linear bandits.  In International Conference on Learning Representations, 2021.
  * [35] Jiachen Hu, Xiaoyu Chen, Chi Jin, Lihong Li, and Liwei Wang.  Near-optimal representation learning for linear bandits and linear RL.  arXiv preprint arXiv:2102.04132, 2021.
  * [36] Leonardo Cella, Karim Lounici, and Massimiliano Pontil.  Multi-task representation learning with stochastic linear bandits.  arXiv preprint arXiv:2202.10066, 2022.
  * [37] Y. Qin, T. Menara, S. Oymak, S. Ching, and F. Pasqualetti.  Representation learning for context-dependent decision-making.  In American Control Conference, Atlanta, GA, June 2022.  To appear.
  * [38] Chandler Davis and W. M. Kahan.  The rotation of eigenvectors by a perturbation. III.  SIAM Journal on Numerical Analysis, 7(1):1–46, 1970.
  * [39] Paat Rusmevichientong and John N. Tsitsiklis.  Linearly parameterized bandits.  Mathematics of Operations Research, 35(2):395–411, 2010.
  * [40] Yingkai Li, Yining Wang, Xi Chen, and Yuan Zhou.  Tight regret bounds for infinite-armed linear contextual bandits.  In International Conference on Artificial Intelligence and Statistics, pages 370–378. PMLR, 2021.
  * [41] Varsha Dani, Thomas P Hayes, and Sham M Kakade.  Stochastic linear optimization under bandit feedback.  2008\.
  * [42] Yasin Abbasi-Yadkori, András Antos, and Csaba Szepesvári.  Forced-exploration based algorithms for playing in stochastic linear bandits.  In COLT Workshop on On-line Learning with Limited Feedback, volume 92, page 236, 2009.
  * [43] Roman Vershynin.  High-Dimensional Probability: An Introduction with Applications in Data Science.  Cambridge University Press, 2018.
  * [44] David A Grant and Esta Berg.  A behavioral analysis of degree of reinforcement and ease of shifting to new responses in a weigl-type card-sorting problem.  Journal of experimental psychology, 38(4):404, 1948.
  * [45] Nikhil Mishra, Mostafa Rohaninejad, Xi Chen, and Pieter Abbeel.  A simple neural attentive meta-learner.  In International Conference on Learning Representations, 2018.
  * [46] Rajendra Bhatia.  Matrix Analysis.  Springer Science & Business Media, 2013.