# Thresholded LASSO Bandit

Kaito Ariu
KTH
<EMAIL_ADDRESS>Kenshi Abe
CyberAgent, Inc.
<EMAIL_ADDRESS>Alexandre Proutière
KTH
<EMAIL_ADDRESS>
###### Abstract

In this paper, we revisit sparse stochastic contextual linear bandits. In
these problems, feature vectors may be of large dimension $d$, but the reward
function depends on a few, say $s_{0}$, of these features only. We present
Thresholded LASSO bandit, an algorithm that (i) estimates the vector defining
the reward function as well as its sparse support using the LASSO framework
with thresholding, and (ii) selects an arm greedily according to this estimate
projected on its support. The algorithm does not require prior knowledge of
the sparsity index $s_{0}$. For this simple algorithm, we establish non-
asymptotic regret upper bounds scaling as $\mathcal{O}(\log d+\sqrt{T\log T})$
in general, and as $\mathcal{O}(\log d+\log T)$ under the so-called margin
condition (a setting where arms are well separated). The regret of previous
algorithms scales as $\mathcal{O}(\sqrt{T}\log(dT))$ and $\mathcal{O}(\log
T\log d)$ in the two settings, respectively. Through numerical experiments, we
confirm that our algorithm outperforms existing methods.

##  1 Introduction

The linear contextual bandit Abe and Long (1999); Li et al. (2010) is a
sequential decision-making problem that generalizes the classical stochastic
Multi-Armed Bandit (MAB) problem Robbins (1952); Lai and Robbins (1985), where
(i) in each round, the decision maker is provided with a context in the form
of a feature vector for each arm and where (ii) the expected reward is a
linear function of these vectors. More precisely, at the beginning of round
$t\geq 1$, the decision-maker receives for each arm $k$, a feature vector
$A_{t,k}\in\mathbb{R}^{d}$. She then selects an arm, say $k$, and observes a
sample of a random reward with mean $\langle A_{t,k},\theta\rangle$. The
parameter vector $\theta\in\mathbb{R}^{d}$ is fixed but initially unknown.
Linear contextual bandits have been extensively applied in online services
such as online advertisement and recommendation systems Li et al. (2010,
2016); Zeng et al. (2016), and constitute arguably the most relevant
structured bandit model in practice.

The major challenge in the design of efficient algorithms for contextual
linear bandits stems from the high dimensionality of the feature space. For
example, for display ad systems as studied in Weinberger et al. (2009);
Chapelle and Li (2011), the joint information about a user, an ad and its
publisher is encoded in a feature vector of dimension $d=2^{24}$. Fortunately,
typically only a few features significantly impact the expected reward. This
observation has motivated the analysis of problems where the unknown parameter
vector $\theta$ is sparse Bastani and Bayati (2015); Wang et al. (2018); Kim
and Paik (2019); Oh et al. (2020). In this paper, we also investigate sparse
contextual linear bandits, and assume that $\theta$ only has at most $s_{0}\ll
d$ non-zero components. The set of these components and its cardinality
$s_{0}$ are unknown to the decision-maker. Sparse contextual linear bandits
have attracted a lot of attention recently. State-of-the-art algorithms
developed to exploit the sparse structure achieve regrets scaling as
$\mathcal{O}(\sqrt{T\log(dT)})$ and $\mathcal{O}(\log d\log T)$ under the co-
called margin condition (a setting where arms are well separated); refer to
Section 2 for details.

In this paper, we develop a novel algorithm, referred to as Thresholded LASSO
bandit, with improved regret guarantees. Our algorithm first uses the LASSO
framework with thresholding to maintain and update in each round estimates of
the parameter vector $\theta$ and of its support. It then greedily picks an
arm based on these estimates (the thresholded estimate of $\theta$). The
regret of the algorithm strongly depends on the accuracy of the estimator of
$\theta$. We derive strong guarantees on this accuracy. More precisely, our
contributions are as follows.

(i) Thresholded LASSO estimation performance. The performance of estimation
procedure based on the LASSO framework is now fairly well understood, see
e.g., Tibshirani (1996); Zhou (2010); Bühlmann and Van De Geer (2011). For
example, Zhou (2010) provides an analysis of the estimation of the support of
$\theta$, and specifically, gives upper bounds on the number of false
positives (components that are not in the support, but estimated as part of
it) and false negatives (components that are in the support, but not estimated
as part of it). These analyses, however, critically rely on the assumption
that the observed data is i.i.d.. This assumption does not hold for the bandit
problem, as the algorithm adapts its arm selection strategy depending on the
past observations. Despite the non i.i.d. nature of the data, we manage to
derive performance guarantees of the estimator of $\theta$. In particular, we
establish high probability guarantees that are independent of the dimension
$d$ (see Lemma 3).

(ii) Regret guarantees. Based on the analysis of the Thresholded LASSO
estimation procedure, we provide a finite-time analysis of the regret of our
algorithm. The regret scales at most as ${\mathcal{O}}(\log d+\sqrt{T\log T})$
in general and ${\mathcal{O}}(\log d+\log T)$ under the margin condition. More
precisely, the estimation error of $\theta$ induces a regret scaling as
$\mathcal{O}(\sqrt{s_{0}T\log T})$ (or $\mathcal{O}(s_{0}(\log
s_{0})^{\frac{3}{2}}\log T$ under the margin condition). The additional term
$\mathcal{O}(\log d)$ in our regret upper bound comes from the errors made
when estimating the support of $\theta$. It is worth noting that when using
the plain LASSO estimator (without thresholding), one would obtain weaker
performance guarantees for the estimation of $\theta$, typically depending on
$d$, see e.g., Bastani and Bayati (2015). This dependence causes an additional
multiplicative term $\log d$ in the regret.

(iii) Numerical experiments. We present extensive numerical experiments to
illustrate the performance of the Thresholded LASSO bandit algorithm. We
compare the estimation accuracy for $\theta$ and the regret of our algorithm
to those of the Doubly-Robust LASSO bandit and Sparsity-Agnostic LASSO bandit
algorithms Kim and Paik (2019); Oh et al. (2020). These experiments confirm
the benefit of the use of the LASSO procedure with thresholding.

##  2 Related Work

Stochastic linear bandit problems have attracted a lot of attention over the
last decade. Carpentier and Munos (2012) addresses sparse linear bandits where
$\|\theta\|_{0}\leq s_{0}$ and where the set of arms is restricted to the
$\ell_{2}$ unit ball. For regimes where the time horizon is much smaller than
the dimension $d$, i.e., $T\ll d$, the authors propose an algorithm whose
regret scales at most as ${\mathcal{O}}(s_{0}\sqrt{T}\log(dT))$. This work,
however, does not consider problems with contextual information.

Recently, high-dimensional contextual linear bandits have been investigated
again under the sparsity assumption $\|\theta\|_{0}\leq s_{0}$. In this line
of research, the decision-maker is provided in each round with a set of arms
defined by a finite set of feature vectors. This set is generated in an i.i.d.
manner across rounds according to an unknown distribution. In this setting,
the authors of Abbasi-Yadkori et al. (2012) devise an algorithm with both a
minimax (problem independent) regret upper bound
$\widetilde{\mathcal{O}}(\sqrt{s_{0}dT})$ and problem dependent upper bound
${\mathcal{O}}(ds_{0}(\log{T})^{2})$ (the notation $\widetilde{\mathcal{O}}$
hides the polylogarithmic terms).

In Bastani and Bayati (2020) (initially published in 2015 as Bastani and
Bayati (2015)), the authors address a high-dimensional contextual linear
bandit problem where the unknown parameter defining the reward function is
arm-specific ($\theta$ is different for the various arms). In the proposed
algorithm, arms are explored uniformly at random for
$\mathcal{O}(s_{0}^{2}\log d\log T)$ prespecified rounds. Under the margin
condition, similar to our Assumption 4, the algorithm achieves a regret of
$\mathcal{O}(s_{0}^{2}(\log d+\log T)^{2})$. For the same problem, Wang et al.
(2018) develops the so-called MCP-Bandit algorithm. The latter also uses the
uniform exploration for $\mathcal{O}(s_{0}^{2}\log d\log T)$ prespecified
rounds, and has improved regret guarantees: the regret scales as
$\mathcal{O}(s_{0}^{2}(\log d+s_{0})\log T)$.

High-dimensional contextual linear bandits have been also studied without the
margin condition, but with a unique parameter $\theta$ defining the reward
function. Kim and Paik (2019) designs an algorithm with uniform exploration
phases of $\mathcal{O}(\sqrt{T\log(dT)\log T})$ rounds, and with regret
$\mathcal{O}(s_{0}\sqrt{T}\log(dT))$. All the aforementioned algorithms
require the knowledge of the sparsity index $s_{0}$. In Oh et al. (2020), the
authors propose an algorithm, referred to as SA LASSO bandit, that does not
require this knowledge, and with regret $\mathcal{O}(s_{0}^{2}\log
d+s_{0}\sqrt{T\log(dT)})$. In addition, SA LASSO bandit does not include any
uniform exploration phase. Its regret guarantees are derived under a specific
assumption on the context distribution, the so-called relaxed symmetry
assumption. The authors also establish a $\mathcal{O}(\sqrt{s_{0}T\log(dT)})$
regret upper bound under the additional restricted eigenvalue condition.

In this paper, we develop an algorithm with improved regret guarantees with
and without the margin condition. The algorithm does not rely on the knowledge
of $s_{0}$.

##  3 Model and Assumptions

###  3.1 Model and notation

We consider a contextual linear stochastic bandit problem in a high-
dimensional space. In each round $t\in[T]:=\\{1,\ldots,T\\}$, the algorithm is
given a set of context vectors
$\mathcal{A}_{t}=\\{A_{t,k}\in\mathbb{R}^{d}:k\in[K]\\}$. The successive sets
$(\mathcal{A}_{t})_{t\geq 1}$ form an i.i.d. sequence with distribution
$p_{{A}}$ on $\mathbb{R}^{K\times d}$. In round $t$, the algorithm selects an
arm $A_{t}\in\mathcal{A}_{t}$ based on past observations, and collects a
random reward $r_{t}$. Formally, if $\mathcal{F}_{t}$ is the $\sigma$-algebra
generated by random variables
$(\mathcal{A}_{1},A_{1},r_{1},\ldots,\mathcal{A}_{t-1},A_{t-1},r_{t-1},\mathcal{A}_{t})$,
$A_{t}$ is $\mathcal{F}_{t}$-measurable. We assume that $r_{t}=\langle
A_{t},\theta\rangle+\varepsilon_{t}$, where $\varepsilon_{t}$ is a sub-
Gaussian random variable with variance proxy $\sigma^{2}$ given
$\mathcal{F}_{t}$ and $A_{t}$. Our objective is to devise an algorithm with
minimal regret, defined as:

$\displaystyle R(T)$
$\displaystyle\coloneqq\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\max_{A\in\mathcal{A}_{t}}\langle
A,\theta\rangle-r_{t}\right]$
$\displaystyle=\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\max_{A\in\mathcal{A}_{t}}\langle
A-A_{t},\theta\rangle\right].$

Notation. The $\ell_{0}$-norm of a vector $\theta\in\mathbb{R}^{d}$ is
$\|\theta\|_{0}=\sum_{i=1}^{d}\mathds{1}\left\\{\theta_{i}\neq 0\right\\}$. We
denote $\hat{\Sigma}_{t}=\frac{1}{t}\sum_{s=1}^{t}A_{s}A_{s}^{\top}$ as the
empirical gram matrix generated by the arms selected under a specific
algorithm. For any $B\subset[d]$, we define
$\theta_{B}\coloneqq(\theta_{1,B},\ldots,\theta_{d,B})^{\top}$ where for all
$i\in[d]$, $\theta_{i,B}\coloneqq\theta_{i}\mathds{1}\\{i\in B\\}$. For each
$B\subset[d]$, we define the submatrix $A(B)\in\mathbb{R}^{n\times|B|}$ of
$A\in\mathbb{R}^{n\times d}$ where for $A(B)$, we extract the rows and columns
that are in $B$. We denote $\textnormal{supp}(x)$ as the set of the non-zero
element indices of $x$. We also define $\theta_{\min}$ as the minimal value of
$|\theta_{i}|$ on the support: $\theta_{\min}\coloneqq\min_{i\in
S}|\theta_{i}|$.

###  3.2 Assumptions

We present a set of assumptions made throughout the paper. We also discuss and
compare these assumptions to those made in the related literature.

######  Assumption 1 (Sparsity and parameter constraints).

The parameter $\theta$ defining the reward function is sparse, i.e.,
$\|\theta\|_{0}\leq s_{0}$ for some fixed but unknown integer $s_{0}$ ($s_{0}$
does not depend on $d$). We denote by $S=\\{i\in[d]:\theta_{i}\neq 0\\}$ the
support of $\theta$. We further assume that $\|\theta\|_{2}\leq s_{2}$ for
some unknown constant $s_{2}$. Finally, we assume that the $\ell_{2}$-norm of
the context vector is bounded, i.e., for all $t$ and for all
$A\in\mathcal{A}_{t}$, $\|A\|_{2}\leq s_{A}$, where $s_{A}>0$ is a positive
constant.

######  Assumption 2 (Compatibility condition).

For a matrix $M\in\mathbb{R}^{d\times d}$ and a set $S_{0}\subset[d]$, we
define the compatibility constant $\phi(M,S_{0})$ as:

$\displaystyle\phi^{2}(M,S_{0})\\!\coloneqq\\!\min_{x:\|x_{S_{0}}\|_{1}\neq
0}\left\\{\\!\frac{s_{0}x^{\top}Mx}{\|x_{S_{0}}\|_{1}^{2}}\\!:\\!\|x_{S_{0}^{c}}\|_{1}\\!\leq\\!3\|x_{S_{0}}\|_{1}\\!\right\\}\\!.$

For each $\theta^{\prime}\in\mathbb{R}^{d}$, we assume that for the matrix
$\Sigma\coloneqq\operatorname{\mathbb{E}}_{A\sim
p_{A}}[\sum_{k=1}^{K}A_{k}A_{k}^{\top}\mathds{1}\\{k=\mathop{\rm
argmax}\limits_{k^{\prime}}\langle A_{k^{\prime}},\theta^{\prime}\rangle\\}]$
satisfies $\phi^{2}(\Sigma,S)\geq\phi^{2}_{0}$, where $\phi_{0}>0$ is some
positive constant.

The compatibility condition was introduced in the high-dimensional statistics
literature Bühlmann and Van De Geer (2011). It ensures that the LASSO
Tibshirani (1996) estimate of the parameter $\theta$ approaches to its true
value as the number of samples grows large. Note that it is easy to check that
the compatibility condition is strictly weaker than assuming the positive
definiteness of $\Sigma$. It allows us to consider feature vectors with
statistically correlated components.

Assumption 2 is essential for the LASSO estimate to be consistent. What is
important is that property similar to the compatibility condition holds for
$\hat{\Sigma}_{t}$ for $t$ large enough and with high probability. To get this
property, the authors of Bastani and Bayati (2020); Wang et al. (2018); Kim
and Paik (2019) make a slightly weaker assumption than Assumption 2; however,
they need to include in their algorithm a uniform exploration phase. Oh et al.
(2020) makes two assumptions (one similar to our Assumption 2 and the so-
called relaxed symmetry assumption) that together imply that Assumption 2
holds.

######  Assumption 3 (Sparse covariate diversity).

There exists a positive constant $\alpha>0$ such that for any
$\theta^{\prime}\in\mathbb{R}^{d}$ with $\|\theta^{\prime}\|_{0}\leq s_{0}$
and a constant $\phi_{0}^{2}>0$ satisfying Assumption 2,

$\displaystyle\min_{v\in\mathbb{R}^{d}}\operatorname{\mathbb{E}}_{A\sim
p_{A}}\left[v^{\top}\left(\sum_{k=1}^{K}A_{k}(\textnormal{supp}(v))A_{k}(\textnormal{supp}(v))^{\top}\mathds{1}\\{k=\mathop{\rm
argmax}\limits_{k^{\prime}}\langle
A_{k^{\prime}},\theta^{\prime}\rangle\\}\right)v\right]\geq\alpha,$
$\displaystyle\quad\quad\textnormal{s.t.}\;\|v\|_{2}=1,\|v\|_{0}\leq
s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}},S\subset\textnormal{supp}(v),$

where $A_{k}(\textnormal{supp}(v))\in\mathbb{R}^{d}$ is a vector whose
component is set as $0$ when it is not in $\textnormal{supp}(v)$; otherwise,
it has the same component as $A_{k}$.

This last assumption is adapted from the covariate diversity condition in
Bastani et al. (2020), but is weaker than the assumption therein. Indeed, the
$\min$ operator is taken over a set of vectors with support just slightly
wider than the support of $\theta$. In view of Lemma 1 in Bastani et al.
(2020), Assumption 3 is satisfied as soon as the distribution $p_{A}$ has the
relaxed symmetry assumption (as in Oh et al. (2020)) and the expected gram
sub-matrix restricted to all sparse sets including the support of $\theta$ and
of support size less than $s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}$ is
positive definite. The assumption then holds for a large variety of context
distributions, including uniform, Multivariate Gaussian, etc. Refer to Section
2.2 of Bastani et al. (2020) for a complete discussion.

Assumption 3 is required to establish that under the greedy algorithm
(selecting the apparent best arm), we get a consistent estimate of $\theta$.
Informally speaking, it states that in average (w.r.t. the context
distribution), when selecting the best arm, the corresponding contexts cover a
bit more than the support of $\theta$. Without this assumption, one needs to
include a uniform exploration phase in the algorithm, as in Bastani and Bayati
(2020); Wang et al. (2018); Kim and Paik (2019). This exploration yields an
additional regret of $\Omega(\log d\log T)$. In Oh et al. (2020), the relaxed
symmetry assumption together with the positive definiteness of the expected
gram matrix imply the covariate diversity condition of Bastani et al. (2020)).
The algorithm in Oh et al. (2020) does not need a uniform exploration phase,
but has looser regret guarantees than ours (illustrating the benefit of the
thresholded LASSO method).

##  4 Algorithm

We present Thresholded (TH) LASSO bandit, an algorithm that applies, to the
online bandit setting, the idea of LASSO with thresholding proposed in Zhou
(2010) for simple estimation problems over i.i.d. data. We show that in the
online setting, estimating $\theta$ and its support separately yields better
regret guarantees.

Algorithm 1 TH LASSO Bandit

1:$\lambda_{0}$

2:for $t=1,\cdots,T$ do

3: Receive a context set $\mathcal{A}_{t}:=\\{A_{t,k}:k\in[K]\\}$

4: Pull arm $A_{t}=\mathop{\rm argmax}\limits_{A\in\mathcal{A}_{t}}\langle
A,\hat{\theta}_{t}\rangle$ (ties are broken uniformly at random) and observe
$r_{t}$

5: $\lambda_{t}\leftarrow\lambda_{0}\sqrt{\frac{2\log t\log d}{t}}$

6: $A\leftarrow(A_{1},A_{2},\ldots,A_{t})^{\top}$

7: $R\leftarrow(r_{1},r_{2},\ldots,r_{t})^{\top}$

8: $\hat{\theta}_{0}^{(t)}\leftarrow\mathop{\rm
argmin}\limits_{\theta}\frac{1}{t}\|R-A\theta\|_{2}^{2}+\lambda_{t}\|\theta\|_{1}$

9:
$\hat{S}_{0}^{(t)}\leftarrow\\{j\in[d]:\;|(\hat{\theta}^{(t)}_{0})_{j}|>4\lambda_{t}\\}$

10:
$\hat{S}_{1}^{(t)}\leftarrow\\{j\in\hat{S}_{0}^{(t)}:\;|(\hat{\theta}^{(t)}_{0})_{j}|\geq
4\lambda_{t}\sqrt{|\hat{S}_{0}^{(t)}|}\\}$

11:
$\hat{\theta}_{1}^{(t)}\leftarrow(A({\hat{S}_{1}^{(t)}})^{\top}A({\hat{S}_{1}^{(t)}}))^{-1}A({\hat{S}_{1}^{(t)}})^{\top}R$

12:
$\hat{\theta}_{t+1,j}\leftarrow\begin{cases}(\hat{\theta}_{1}^{(t)})_{j}&j\in\hat{S}_{1}^{(t)}\\\
0&\text{otherwise}\end{cases}$

13:end for

The pseudo-code of our algorithm is presented in Algorithm 1. In each round,
the algorithm pulls the arm in a greedy way using the estimated value of
$\theta$, $\hat{\theta}_{t}$. From the past selected arms and rewards, we get
a first estimate $\hat{\theta}_{0}^{(t)}$ of $\theta$. This estimate will be
used to estimate the support of $\theta$. The regularizer
$\lambda_{t}\coloneqq\lambda_{0}\sqrt{(2\log t\log d)/t}$ is set at a much
larger value than that in previous work (they typically have the order of
$\sqrt{(\log d+\log t)/t}$), as we are only focusing on the support recovery
here. Applying a thresholding procedure twice to $\hat{\theta}_{0}^{(t)}$, a
support estimate $\hat{S}_{1}^{(t)}$ is obtained. Then, the final estimate
$\hat{\theta}_{t+1}$ is obtained as the Least-Squares estimator of $\theta$,
when restricted to $\hat{S}_{1}^{(t)}$.

##  5 Performance Guarantees

We analyze the regret of the Thresholded LASSO bandit algorithm both when the
margin condition holds and when it does not.

###  5.1 With the margin condition

We first present the margin condition.

######  Assumption 4 (Margin Condition).

There exists a constant $C_{\textnormal{m}}>0$ such that for all $\kappa>0$,

$\displaystyle\forall k\neq k^{\prime},\quad\mathbb{P}_{A\sim
p_{A}}(0<|\langle A_{k}-A_{k^{\prime}},\theta\rangle|\leq\kappa)\leq
C_{\textnormal{m}}\kappa.$

This assumption controls the probability under $p_{A}$ that two arms yield
very similar rewards (and hence are hard to separate). It was first introduced
in Goldenshluger and Zeevi (2013) in the (low-dimensional) linear bandit
literature. The margin condition holds for the most usual context
distributions (including the uniform distribution and Multivariate Gaussian
distributions).

The following theorem provides a non-asymptotic regret upper bound of TH LASSO
bandit under the margin condition. To simplify the presentation of our regret
upper bound, we use the following quantities, functions of the parameters
involved in Assumptions 1, 2, and 3. Define
$h_{0}=\lfloor\sqrt{\log(4(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}))}+1\rfloor$
and
$\tau=\max\left(\lfloor\frac{2\log(2d^{2})}{C_{0}^{2}}\rfloor,\lfloor(\log\log
d)\log d\rfloor\right)$, where
$C_{0}=\min\left\\{\frac{1}{2},\frac{\phi_{0}^{2}}{256s_{0}s_{A}^{2}}\right\\}$.

######  Theorem 1.

Suppose that Assumptions 1, 2, 3, and 4 hold. The regret of TH LASSO bandit
with $\lambda_{0}={1}/{(\log\log d)^{\frac{1}{4}}}$ satisfies: if $d$ is large
enough so that (i) $\log\tau\geq 64\sigma^{2}s_{A}^{2}(\log\log
d)^{\frac{1}{2}}$, (ii):

$\frac{4\left(\frac{2s_{0}}{\phi_{0}^{2}}+\sqrt{\left(1+\frac{2}{\phi_{0}^{2}}\right)s_{0}}\right)}{\theta_{\min}(\log\log
d)^{\frac{1}{4}}}\sqrt{\frac{2\log\tau\log d}{\tau}}\leq 1,$

and (iii) $d\geq 100$, then, for all $T\geq 2$,

$\displaystyle R(T)$ $\displaystyle\leq
2s_{A}s_{2}\tau+\frac{352\sigma^{2}s_{A}^{4}C_{\textnormal{m}}(K-1)h_{0}^{3}\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)}{\alpha^{2}}(\log
T+1)$ $\displaystyle\ \ \
+2(K-1)s_{A}s_{2}\left(\frac{\pi^{2}}{3}+\frac{2}{C_{0}^{2}}+\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)\frac{10s_{A}^{2}}{\alpha}\right).$

In particular, we have, as $d$ grows large,

$\displaystyle R(T)=\mathcal{O}(s_{0}^{2}\log
d+s_{0}(\log(s_{0}))^{\frac{3}{2}}\log T+s_{0}^{2}),$

where the $\mathcal{O}(\cdot)$ notation hides all the multiplicative and
additive constants that do not depend on $s_{0}$, $d$, and $T$ and hides a
$\log\log d$ multiplicative factor for the first term.

In the above theorem, note that $h_{0}$ is a constant scaling as $\sqrt{\log
s_{0}}$ and $\tau$ can be regarded as cold start time for the algorithm,
scaling as $(\log\log d)\log d$. Note that $\sqrt{\frac{2\log\tau\log
d}{\tau}}=\Theta(1)$. It is also worth mentioning that if the system
parameters $s_{0},s_{A},\theta_{\min},\phi_{0}^{2}$, and $\sigma^{2}$ were
known, we could tune $\lambda_{0}$ in the algorithm so as to obtain similar
performance guarantees under much milder conditions on $d$.

###  5.2 Without the margin condition

We also establish a regret guarantee without the margin condition.

######  Theorem 2.

Suppose that Assumptions 1, 2, and 3 hold. The regret of TH LASSO bandit with
$\lambda_{0}={1}/{(\log\log d)^{\frac{1}{4}}}$ satisfies: for $d$ satisfying
the conditions (i), (ii), and (iii) of Theorem 1, for all $T\geq 1$,

$\displaystyle R(T)\leq 2s_{A}s_{2}\tau$ $\displaystyle\ \ \
+16s_{A}^{2}(K-1)\frac{\sigma\sqrt{s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}}}{\alpha}\sqrt{T\log
T}+2(K-1)s_{A}s_{2}\left(\left(\frac{\pi^{2}}{3}+\frac{10s_{A}^{2}}{\alpha}\right)\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)+\frac{\pi^{2}}{3}+\frac{2}{C_{0}^{2}}\right).$

In particular, we have, as $d$ grows large,

$R(T)=\mathcal{O}\left(s_{0}^{2}\log d+\sqrt{s_{0}T\log T}+s_{0}^{2}\right),$

where the $\mathcal{O}(\cdot)$ notation hides all the multiplicative and
additive constants that do not depend on $s_{0}$, $d$, and $T$ and hides a
$\log\log d$ multiplicative factor for the first term.

Theorems 1 and 2 state that TH LASSO bandit achieves a much lower regret than
existing algorithms. Indeed, upper regret bounds of existing algorithms had a
term scaling as $\log d\log T$ (resp. $\log d\sqrt{T}$) with (resp. without)
the margin condition. TH LASSO bandit removes the $\log d$ multiplicative
factor. In most applications of the sparse linear contextual bandit, both $T$
and $d$ are typically very large, and the regret improvement obtained by TH
LASSO bandit is significant.

###  5.3 Sketch of the proof of Theorem 1

We sketch below the proof of Theorem 1. A complete proof is presented in
appendix.

(1) Estimation of the support of $\theta$. First, we prove that the estimated
support contains the true support $S$ with high probability.

######  Lemma 1.

Under Assumptions 1 and 2, for any $t\geq\frac{2\log(2d^{2})}{C_{0}^{2}}$ such
that
$4\left(\frac{2s_{0}}{\phi_{0}^{2}}+\sqrt{\left(1+\frac{2}{\phi_{0}^{2}}\right)s_{0}}\right)\lambda_{t}\leq\theta_{\min}$,

$\displaystyle\mathbb{P}\left(S\subset\hat{S}_{1}^{(t)}\text{ and
}|\hat{S}_{1}^{(t)}\setminus S|\leq\frac{2\sqrt{s_{0}}}{\phi^{2}_{0}}\right)$
$\displaystyle\geq
1-2\exp\left(-\frac{t\lambda_{t}^{2}}{32\sigma^{2}s_{A}^{2}}+\log
d\right)-\exp\left(-\frac{tC_{0}^{2}}{2}\right).$

Lemma 1 extends the support recovery result of the Thresholded LASSO (Zhou,
2010) to the case of the non-i.i.d data (generated by the bandit algorithm).

Proof sketch of Lemma 1. We first study the performance of the initial LASSO
estimate. Let $\phi_{t}^{2}\coloneqq\phi^{2}(\hat{\Sigma}_{t},S)$ be the
compatibility constant for the empirical gram matrix
$\hat{\Sigma}_{t}=\frac{\sum_{s=1}^{t}A_{s}A_{s}^{\top}}{t}$. We prove that

$\displaystyle\|\hat{\theta}_{0}^{(t)}-\theta\|_{1}\leq\frac{4s_{0}\lambda_{t}}{\phi_{t}^{2}},$

holds with (exponentially) high probability. Next, we establish a relationship
between the estimated support $\hat{S}_{0}^{(t)}$, $\hat{S}_{1}^{(t)}$ and
$\|\hat{\theta}_{0}^{(t)}-\theta\|_{1}$. We get:

$\displaystyle S\subset$
$\displaystyle\hat{S}_{1}^{(t)}\subset\hat{S}_{0}^{(t)},$ $\displaystyle
4|\hat{S}_{0}^{(t)}\setminus S|\lambda_{t}$
$\displaystyle\leq\|\hat{\theta}_{0}^{(t)}-\theta\|_{1},$ $\displaystyle
4|\hat{S}_{1}^{(t)}\setminus S|\lambda_{t}\sqrt{|\hat{S}_{0}^{(t)}|}$
$\displaystyle\leq\|\hat{\theta}_{0}^{(t)}-\theta\|_{1}.$

We further prove that $\phi_{t}^{2}\geq\phi_{0}^{2}/2$ with exponentially high
probability. Combining the results, we get the statement of Lemma 1. $\Box$

Define the event $\mathcal{E}_{t}$ as:

$\displaystyle\mathcal{E}_{t}\coloneqq\left\\{S\subset\hat{S}_{1}^{(t)}\text{
and }|\hat{S}_{1}^{(t)}\setminus
S|\leq\frac{2\sqrt{s_{0}}}{\phi^{2}_{0}}\right\\}.$ (1)

In the remaining of the proof, in view of Lemma 1, we can assume that the
event $\mathcal{E}_{t}$ holds.

(2) Minimal eigenvalue of the empirical gram matrix. We write
$\hat{S}_{1}^{(t)}=\hat{S}$ for the simplicity. Let
$\hat{\Sigma}_{\hat{S}}\coloneqq\frac{1}{t}\sum_{s=1}^{t}A_{s}(\hat{S})A_{s}(\hat{S})^{\top}$
be the empirical gram matrix on the estimated support.

######  Lemma 2.

Let $t\in[T]$. Under Assumptions 1 and 3, we have:

$\displaystyle\mathbb{P}\left(\lambda_{\min}(\hat{\Sigma}_{\hat{S}})\geq\frac{\alpha}{2}\
\big{|}\ \mathcal{E}_{t}\right)\geq
1-\exp\left(\log\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)-\frac{t\alpha}{10s_{A}^{2}}\right).$

The proof of Lemma 2 is a straightforward consequence of the matrix Chernoff
inequality for adaptive data Tropp (2011).

(3) Estimation of $\theta$ after thresholding. Next, we study the accuracy of
$\hat{\theta}_{t}$.

######  Lemma 3.

Let $t\in[T]$. We have for all $x,\lambda>0$:

$\displaystyle\mathbb{P}\left(\|\hat{\theta}_{t+1}-\theta\|_{2}\geq
x\;\text{and}\;\lambda_{\min}(\hat{\Sigma}_{\hat{S}})\geq\lambda\ \big{|}\
\mathcal{E}_{t}\right)\leq
2\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)\exp\left(-\frac{\lambda^{2}tx^{2}}{2\sigma^{2}s_{A}^{2}\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)}\right).$

Proof sketch of Lemma 3. When
$\lambda_{\min}(\hat{\Sigma}_{\hat{S}})\geq\lambda>0$, we have:

$\displaystyle\|\hat{\theta}_{t+1}-\theta\|_{2}\leq\frac{1}{\lambda
t}\|A(\hat{S})^{\top}(\varepsilon_{1},\ldots,\varepsilon_{t})^{\top}\|_{2}.$

Using a concentration result, see Theorem 2.19 in Wainwright (2019), for each
$i\in\hat{S}$, for any $x>0$, we get:

$\displaystyle\mathbb{P}\left(\left|\sum_{s=1}^{t}\varepsilon_{s}(A_{s})_{i}\right|\geq\frac{\lambda
tx}{\sqrt{s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}}}\ \big{|}\
\mathcal{E}_{t}\right)\leq
2\exp\left(-\frac{\lambda^{2}tx^{2}}{2\sigma^{2}s_{A}^{2}\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)}\right).$

Combining the results, we conclude the proof. $\Box$

From the above lemma, we conclude that $\theta$ is well estimated with high
probability.

(4) Instantaneous regret upper bound. For the previous lemmas, we can derive
an upper bound on the instantaneous regret.

######  Lemma 4.

Define
$\mathcal{G}_{t}^{\frac{\alpha}{2}}\coloneqq\left\\{\lambda_{\min}(\hat{\Sigma}_{\hat{S}})\geq\frac{\alpha}{2}\right\\}$.
Let $t\geq 2$. Under Assumptions 1, 2, 3, and 4, the expected instantaneous
regret satisfies:

$\displaystyle\operatorname{\mathbb{E}}[\max_{A\in\mathcal{A}_{t}}\langle
A-A_{t},\theta\rangle]\leq\frac{352\sigma^{2}s_{A}^{4}C_{\text{m}}(K-1)h_{0}^{3}\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)}{\alpha^{2}}\frac{1}{t-1}+2(K-1)s_{A}s_{2}\left(\mathbb{P}(\mathcal{E}_{t}^{c})+\mathbb{P}\left(\left(\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)^{c}\middle|\mathcal{E}_{t}\right)\right).$

Proof sketch of Lemma 4. We derive an upper bound of the instantaneous regret
in round $t$ given that the best arm is $k$ is round. To this aim, we
discretize the possible values of the regret using the discretization step
size $\delta\coloneqq\frac{\sigma
s_{A}}{\alpha}\sqrt{\frac{8(s_{0}+2s_{0}/\phi_{0}^{2})}{t-1}}$. The
discretization allows us to simply connect the regret to the $\ell_{2}$-norm
error of the estimated value of $\theta$, $\|\hat{\theta}_{t}-\theta\|_{2}$.
Applying Lemma 3 together with the margin condition (Assumption 4), and
summing up all the cases, we get the instantaneous regret bound. $\Box$

Figure 1: (Left) Number of false positives $|\hat{S}_{1}^{(t)}\setminus S|$,
(center) false negatives $|S\setminus\hat{S}_{1}^{(t)}|$, (right)
$\ell_{2}$-norm error $\|\hat{\theta}_{t}-\theta\|_{2}$ of the three
algorithms with $\rho^{2}=0.7$, $s_{A}=10$, $K=2$, and (top line)
$(s_{0},d)=(5,1000)$, (bottom line) $(s_{0},d)=(20,2000)$. The shaded area
represents the standard errors.

Figure 2: Cumulative regret of the three algorithms with $\rho^{2}=0.7$,
$s_{A}=10$ in six scenarios selected using $K\in\\{2,50\\}$,
$d\in\\{1000,2000\\}$, and $s_{0}\in\\{5,20\\}$. The shaded area represents
the standard errors.

Figure 3: Cumulative regret at round $t=1000$ of TH LASSO bandit and SA LASSO
bandit with $\rho^{2}=0.7$, $K=2$, $d=1000$, $s_{0}=5$, and varying
$s_{A}\in\\{2.5,5,10,20,40,\infty\\}$. The error bars represent the standard
errors.

Figure 4: Cumulative regret at round $t=1000$ of TH LASSO bandit and SA LASSO
bandit with $\rho^{2}=0.7$, $s_{A}=10$, $K=2$, $d=1000$, $s_{0}=5$, and
varying $\lambda_{0}/\lambda^{\ast}\in[0.1,2.5]$. The error bars represent the
standard errors.

##  6 Experiments

In this section, we empirically evaluate the TH LASSO bandit algorithm. We
compare its performance to those of the Doubly-Robust (DR) LASSO bandit Kim
and Paik (2019) and SA LASSO bandit Oh et al. (2020) algorithms. Note that we
do not compare the proposed algorithm to the LASSO bandit algorithm Bastani
and Bayati (2020), because this algorithm is designed for a problem different
than ours ($\theta$ varies across arms).

Reward parameter and contexts. We consider problems where
$\theta\in\mathbb{R}^{d}$ is sparse, i.e., $\|\theta\|_{0}=s_{0}$. We generate
each non-zero components of $\theta$ in an i.i.d. manner using the uniform
distribution on $[1,2]$. In each round $t$, for each component $i\in[d]$, we
sample $((A_{t,1})_{i},\cdots,(A_{t,K})_{i})$ from a Gaussian distribution
$\mathcal{N}(\mathbf{0}_{K},V)$ where $V_{i,i}=1$ for all $i\in[K]$ and
$V_{i,k}=\rho^{2}=0.7$ for all $i\neq k\in[K]$. We then normalize each
$A_{t,k}=((A_{t,k})_{1},\ldots,(A_{t,k})_{d})$ so that its $\ell_{2}$-norm is
at most $s_{A}$ for all $k\in[K]$. Note that the components of the feature
vectors are correlated over $[d]$ and over $[K]$. The noise process is
Gaussian, i.i.d. over rounds: $\varepsilon_{t}\sim\mathcal{N}(0,1)$. We test
the algorithms for different values of $K,d,s_{0}$, and $s_{A}$. For each
experimental setting, we averaged the results for $20$ instances.

Algorithms. For DR LASSO bandit, we use the implementation given by
https://github.com/gisoo1989/Doubly-Robust-Lasso-Bandit. For the SA LASSO
bandit and TH LASSO bandit algorithms, we tune the hyperparameter
$\lambda_{0}$ in $[0.01,0.5]$ to roughly optimize the algorithm performance
when $K=2,d=1000,s_{A}=10$, and $s_{0}=5$. As a result, we set
$\lambda_{0}=0.16$ for SA LASSO bandit, and set $\lambda_{0}=0.03$ for TH
LASSO bandit.

Results. We first compare the estimation accuracy for $\theta$ under the three
algorithms in two scenarios: $K=2,d=1000,s_{A}=10,s_{0}=5$; and
$K=2,d=2000,s_{A}=10,s_{0}=20$. Figure 1 shows the number of false positives
$|\hat{S}_{1}^{(t)}\setminus S|$, the number of false negatives
$|S\setminus\hat{S}_{1}^{(t)}|$, and $\ell_{2}$-norm error
$\|\hat{\theta}_{t}-\theta\|_{2}$. Note that, for DR LASSO bandit and SA LASSO
bandit, we define the estimated support as
$\hat{S}_{1}^{(t)}=\\{i\in[d]:\hat{\theta}_{t,i}\neq 0\\}$. We can observe
that the number of false positives of our algorithm converge to zero faster
than those of DR LASSO bandit and SA LASSO bandit. Furthermore, our algorithm
yields a smaller estimation error $\|\hat{\theta}_{t}-\theta\|_{2}$ than the
two other algorithms, as is shown in right column of Figure 1.

Next, we compare the regret of each algorithm with $s_{A}=10$,
$K\in\\{2,50\\}$, $d=\\{1000,2000\\}$, and $s_{0}\in\\{5,20\\}$. Figure 2
shows the average cumulative regret for each algorithm. We find that TH LASSO
bandit outperforms the other algorithms in all scenarios. We provide
additional experimental results, including experiments with different
correlation levels $\rho^{2}\in\\{0,0.3\\}$, in the appendix.

We also conduct experiments varying $s_{A}\in\\{2.5,5,10,20,40,\infty\\}$. As
in previous experiments, for each $s_{A}$, we normalize each feature vector
$A_{t,k}$ so that its $\ell_{2}$-norm is at most $s_{A}$ for all $k\in[K]$. We
set $K=2,d=1000$, and $s_{0}=5$. Figure 4 shows the average cumulative regret
at $t=1000$ of TH LASSO bandit and SA LASSO bandit for each $s_{A}$. This
experiment confirms that TH LASSO exhibits lower regret than SA LASSO bandit.

Finally, we examine the robustness of TH LASSO bandit and SA LASSO bandit with
respect to the hyperparameter $\lambda_{0}$. We vary
$\lambda_{0}\in[0.1\lambda^{\ast},2.5\lambda^{\ast}]$ where
$\lambda^{\ast}=0.03$ for TH LASSO bandit and $\lambda^{\ast}=0.16$ for SA
LASSO bandit. We set $K=2,d=1000,s_{0}=5$, and $s_{A}=10$. Figure 4 shows the
average cumulative regret at $t=1000$ for TH LASSO bandit and SA LASSO bandit
for different ratios $\lambda_{0}/\lambda^{\ast}$. Observe that the regret of
TH LASSO bandit is lower than that of SA LASSO bandit for various ratios.
Moreover, note the performance of TH LASSO bandit is not very sensitive to the
choice of $\lambda_{0}$: it is robust. This contrasts with the SA LASSO bandit
algorithm, for which a careful tuning of $\lambda_{0}$ is needed to get good
performance.

##  7 Conclusion

In this paper, we studied the high-dimensional contextual linear bandit
problem with sparsity. We devised TH LASSO bandit, a simple algorithm that
applies a LASSO procedure with thresholding to estimate the support of the
unknown parameter. We established finite-time regret upper bounds under
various assumptions, and in particular with and without the margin condition.
These bounds exhibit a better regret scaling than those derived for previous
algorithms. We also numerically compared TH LASSO bandit to previous
algorithms in a variety of settings, and showed that it outperformed other
algorithms in these settings.

In future work, it would be interesting to consider scenarios where the
assumptions made in this paper may not hold. In particular, it is worth
investigating the case where the sparse covariate diversity condition
(Assumption 3) is not satisfied. In this case, being greedy in the successive
arm selections may not work. It is intriguing to know whether devising an
algorithm without forced uniform exploration and with reasonable regret
guarantees is possible.

## References

  * 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.
  * Abe and Long (1999) Naoki Abe and Philip M. Long.  Associative reinforcement learning using linear probabilistic concepts.  In _International Conference on Machine Learning_ , page 3–11, 1999\.
  * Bastani and Bayati (2015) Hamsa Bastani and Mohsen Bayati.  Online decision-making with high-dimensional covariates.  _Available at SSRN 2661896_ , 2015.
  * 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. (2020) Hamsa Bastani, Mohsen Bayati, and Khashayar Khosravi.  Mostly exploration-free algorithms for contextual bandits.  _Management Science, Articles in Advance_ , 2020.
  * 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.
  * Carpentier and Munos (2012) Alexandra Carpentier and Rémi Munos.  Bandit theory meets compressed sensing for high dimensional stochastic linear bandit.  In _Artificial Intelligence and Statistics_ , pages 190–198, 2012\.
  * Chapelle and Li (2011) Olivier Chapelle and Lihong Li.  An empirical evaluation of thompson sampling.  In _Advances in neural information processing systems_ , pages 2249–2257, 2011.
  * Goldenshluger and Zeevi (2013) Alexander Goldenshluger and Assaf Zeevi.  A linear response bandit problem.  _Stochastic Systems_ , 3(1):230–261, 2013.
  * Kim and Paik (2019) Gi-Soo Kim and Myunghee Cho Paik.  Doubly-robust lasso bandit.  In _Advances in Neural Information Processing Systems_ , pages 5877–5887, 2019.
  * Lai and Robbins (1985) Tze Leung Lai and Herbert Robbins.  Asymptotically efficient adaptive allocation rules.  _Advances in applied mathematics_ , 6(1):4–22, 1985.
  * Li et al. (2010) Lihong Li, Wei Chu, John Langford, and Robert E Schapire.  A contextual-bandit approach to personalized news article recommendation.  In _International conference on World wide web_ , pages 661–670, 2010\.
  * Li et al. (2016) Shuai Li, Alexandros Karatzoglou, and Claudio Gentile.  Collaborative filtering bandits.  In _International ACM SIGIR conference on Research and Development in Information Retrieval_ , pages 539–548, 2016.
  * Oh et al. (2020) Min-hwan Oh, Garud Iyengar, and Assaf Zeevi.  Sparsity-agnostic lasso bandit.  _arXiv preprint arXiv:2007.08477_ , 2020.
  * Robbins (1952) Herbert Robbins.  Some aspects of the sequential design of experiments.  _Bulletin of the American Mathematical Society_ , 58(5):527–535, 1952.
  * Tibshirani (1996) Robert Tibshirani.  Regression shrinkage and selection via the lasso.  _Journal of the Royal Statistical Society: Series B (Methodological)_ , 58(1):267–288, 1996.
  * Tropp (2011) Joel A Tropp.  User-friendly tail bounds for matrix martingales.  Technical report, 2011.
  * Wainwright (2019) Martin J Wainwright.  _High-dimensional statistics: A non-asymptotic viewpoint_ , volume 48.  Cambridge University Press, 2019.
  * 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.
  * Weinberger et al. (2009) Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg.  Feature hashing for large scale multitask learning.  In _International Conference on Machine Learning_ , page 1113–1120, 2009.
  * Zeng et al. (2016) Chunqiu Zeng, Qing Wang, Shekoofeh Mokhtari, and Tao Li.  Online context-aware recommendation with time varying multi-armed bandit.  In _International conference on Knowledge discovery and data mining_ , pages 2025–2034, 2016.
  * Zhou (2010) Shuheng Zhou.  Thresholded lasso for high dimensional variable selection and statistical estimation.  _arXiv preprint arXiv:1002.1583_ , 2010.

stream countersstream stream stream

##  Appendix A Proof of Theorems

###  A.1 Proof of Theorem 1

We first upper bound the instantaneous regret in round $t\geq 1$. We have:

$\displaystyle\operatorname{\mathbb{E}}[\max_{A\in\mathcal{A}_{t}}\langle
A-A_{t},\theta\rangle]$
$\displaystyle\leq\operatorname{\mathbb{E}}[|\max_{A\in\mathcal{A}_{t}}\langle
A,\theta\rangle|]+\operatorname{\mathbb{E}}[|\langle A_{t},\theta\rangle|]$
$\displaystyle\leq s_{A}s_{2}+s_{A}s_{2}$ $\displaystyle=2s_{A}s_{2},$ (2)

where for the second inequality stems from Cauchy–Schwarz inequality. We
deduce the following upper bound on the expected regret up to round $T$:

$\displaystyle R(T)$
$\displaystyle=\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\max_{A\in\mathcal{A}_{t}}\langle
A-A_{t},\theta\rangle\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}2s_{A}s_{2}\tau+\sum_{t=\tau+1}^{T}\operatorname{\mathbb{E}}\left[\max_{A\in\mathcal{A}_{t}}\langle
A-A_{t},\theta\rangle\right]$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}2s_{A}s_{2}\tau+\sum_{t=\tau+1}^{T}\left(\frac{352\sigma^{2}s_{A}^{4}C_{\text{m}}(K-1)h_{0}^{3}\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)}{\alpha^{2}}\frac{1}{t-1}+2(K-1)s_{A}s_{2}\left(\mathbb{P}(\mathcal{E}_{t}^{c})+\mathbb{P}\left(\left(\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)^{c}\middle|\mathcal{E}_{t}\right)\right)\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}2s_{A}s_{2}\tau+\sum_{t=\tau+1}^{T}\bigg{(}\frac{352\sigma^{2}s_{A}^{4}C_{\text{m}}(K-1)h_{0}^{3}\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)}{\alpha^{2}}\frac{1}{t-1}$
$\displaystyle\ \ \
+2(K-1)s_{A}s_{2}\left(2\exp\left(-\frac{t\lambda_{t}^{2}}{32\sigma^{2}s_{A}^{2}}+\log
d\right)+\exp\left(-\frac{tC_{0}^{2}}{2}\right)+\exp\left(\log\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)-\frac{t\alpha}{10s_{A}^{2}}\right)\right)\bigg{)},$

where for $(a)$, we used equation (2) for $1\leq t\leq\tau$; for $(b)$, we
used Lemma 4; for $(c)$, we used Lemma 1 (for $\mathcal{E}_{t}$) and Lemma 2
(for $\mathcal{G}_{t}^{\frac{\alpha}{2}}$).

Now we have:

$\displaystyle\sum_{t=\tau+1}^{T}\frac{352\sigma^{2}s_{A}^{4}C_{\text{m}}(K-1)h_{0}^{3}\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)}{\alpha^{2}}\frac{1}{t-1}$
$\displaystyle=\sum_{t=\tau}^{T-1}\frac{352\sigma^{2}s_{A}^{4}C_{\text{m}}(K-1)h_{0}^{3}\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)}{\alpha^{2}}\frac{1}{t}$
$\displaystyle\leq\frac{352\sigma^{2}s_{A}^{4}C_{\text{m}}(K-1)h_{0}^{3}\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)}{\alpha^{2}}(1+\int_{1}^{T}\frac{1}{t}dt)$
$\displaystyle=\frac{352\sigma^{2}s_{A}^{4}C_{\text{m}}(K-1)h_{0}^{3}\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)}{\alpha^{2}}(1+\log
T),$

and

$\displaystyle\sum_{t=\tau+1}^{T}\exp\left(-\frac{t\lambda_{t}^{2}}{32\sigma^{2}s_{A}^{2}}+\log
d\right)$ $\displaystyle=\sum_{t=\tau+1}^{T}\exp\left(-\left(\frac{\log
t}{16\sigma^{2}s_{A}^{2}(\log\log d)^{\frac{1}{2}}}-1\right)\log d\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{t=\tau+1}^{T}\exp\left(-\frac{\log
t\log d}{32\sigma^{2}s_{A}^{2}(\log\log d)^{\frac{1}{2}}}\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\sum_{t=\tau+1}^{T}\exp\left(-\frac{\log
t\log\tau}{32\sigma^{2}s_{A}^{2}(\log\log d)^{\frac{1}{2}}}\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\sum_{t=\tau+1}^{T}\exp\left(-2\log
t\right)$ $\displaystyle=\sum_{t=\tau+1}^{T}\frac{1}{t^{2}}$
$\displaystyle\leq\sum_{t=1}^{\infty}\frac{1}{t^{2}}$
$\displaystyle=\frac{\pi^{2}}{6},$

where for $(a)$, we used the fact that $\log\tau\geq
64\sigma^{2}s_{A}^{2}(\log\log d)^{\frac{1}{2}}$; for $(b)$, we used the fact
that $\log\tau\leq\log d$ from $d\geq 100$; for $(c)$, we used again
$\log\tau\geq 64\sigma^{2}s_{A}^{2}(\log\log d)^{\frac{1}{2}}$. In addition,

$\displaystyle\sum_{t=\tau+1}^{T}\left(\exp\left(-\frac{tC_{0}^{2}}{2}\right)+\exp\left(\log\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)-\frac{t\alpha}{10s_{A}^{2}}\right)\right)$
$\displaystyle\leq\int_{0}^{\infty}\left(\exp\left(-\frac{tC_{0}^{2}}{2}\right)+\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)\exp\left(-\frac{t\alpha}{10s_{A}^{2}}\right)\right)dt$
$\displaystyle=\frac{2}{C_{0}^{2}}+\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)\frac{10s_{A}^{2}}{\alpha}.$

In summary, we obtain that:

$\displaystyle R(T)$ $\displaystyle\leq
2s_{A}s_{2}\tau+\frac{352\sigma^{2}s_{A}^{4}C_{\text{m}}(K-1)h_{0}^{3}\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)}{\alpha^{2}}(\log
T+1)$ $\displaystyle\ \ \
+2(K-1)s_{A}s_{2}\left(\frac{\pi^{2}}{3}+\frac{2}{C_{0}^{2}}+\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)\frac{10s_{A}^{2}}{\alpha}\right).$

This concludes the proof of the regret upper bound. Regarding the scaling in
$d$, $T$, and $s_{0}$, note that $1/C_{0}^{2}=\mathcal{O}(s_{0}^{2})$ and
$h_{0}^{3}=\mathcal{O}((\log(s_{0}))^{\frac{3}{2}})$. Therefore, we have:

$\displaystyle R(T)=\mathcal{O}(s_{0}^{2}\log
d+s_{0}(\log(s_{0}))^{\frac{3}{2}}\log T+s_{0}^{2}).$

This concludes the proof. $\Box$

###  A.2 Proof of Theorem 2

The following lemma provides an upper bound of the instantaneous regret.

######  Lemma 5.

Under Assumptions 1, 2, and 3, for any $t\in[T]$, we have:

$\displaystyle\operatorname{\mathbb{E}}[\max_{A\in\mathcal{A}_{t}}\langle
A-A_{t},\theta\rangle]$ $\displaystyle\leq
8s_{A}^{2}(K-1)\frac{\sigma\sqrt{s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}}}{\alpha}\sqrt{\frac{\log
t}{t}}$ $\displaystyle\ \ \
+4(K-1)s_{A}s_{2}\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)\frac{1}{t^{2}}+2(K-1)s_{A}s_{2}\left(\mathbb{P}(\mathcal{E}_{t}^{c})+\mathbb{P}\left(\left(\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)^{c}\middle|\mathcal{E}_{t}\right)\right).$

Using Lemma 5, we proceed as in the proof of Theorem 1, and deduce that:

$\displaystyle R(T)$
$\displaystyle=\operatorname{\mathbb{E}}\left[\sum_{t=1}^{T}\max_{A\in\mathcal{A}_{t}}\langle
A-A_{t},\theta\rangle\right]$ $\displaystyle\leq
2s_{A}s_{2}\tau+\sum_{t=\tau+1}^{T}\operatorname{\mathbb{E}}\left[\max_{A\in\mathcal{A}_{t}}\langle
A-A_{t},\theta\rangle\right]$ $\displaystyle\leq
2s_{A}s_{2}\tau+\sum_{t=\tau+1}^{T}\left(8s_{A}^{2}(K-1)\frac{\sigma\sqrt{s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}}}{\alpha}\sqrt{\frac{\log
t}{t}}\right.$ $\displaystyle\ \ \
\left.+4(K-1)s_{A}s_{2}\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)\frac{1}{t^{2}}+2(K-1)s_{A}s_{2}\left(\mathbb{P}(\mathcal{E}_{t}^{c})+\mathbb{P}\left(\left(\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)^{c}\middle|\mathcal{E}_{t}\right)\right)\right)$

We also show that:

$\displaystyle\sum_{t=\tau+1}^{T}2(K-1)s_{A}s_{2}\left(\mathbb{P}(\mathcal{E}_{t}^{c})+\mathbb{P}\left(\left(\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)^{c}\middle|\mathcal{E}_{t}\right)\right)\leq
2(K-1)s_{A}s_{2}\left(\frac{\pi^{2}}{3}+\frac{2}{C_{0}^{2}}+\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)\frac{10s_{A}^{2}}{\alpha}\right)$

and

$\displaystyle\sum_{t=\tau+1}^{T}4(K-1)s_{A}s_{2}\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)\frac{1}{t^{2}}\leq\frac{2\pi^{2}}{3}(K-1)s_{A}s_{2}\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right).$

Regarding the series involving $\sqrt{\log t/t}$, we have:

$\displaystyle\sum_{t=\tau+1}^{T}8s_{A}^{2}(K-1)\frac{\sigma\sqrt{s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}}}{\alpha}\sqrt{\frac{\log
t}{t}}$ $\displaystyle\leq 8\sqrt{\log
T}s_{A}^{2}(K-1)\frac{\sigma\sqrt{s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}}}{\alpha}\sum_{t=\tau+1}^{T}\sqrt{\frac{1}{t}}$
$\displaystyle\leq 8\sqrt{\log
T}s_{A}^{2}(K-1)\frac{\sigma\sqrt{s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}}}{\alpha}\sum_{t=1}^{T}\sqrt{\frac{1}{t}}$
$\displaystyle\leq 8\sqrt{\log
T}s_{A}^{2}(K-1)\frac{\sigma\sqrt{s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}}}{\alpha}\int_{0}^{T}\sqrt{\frac{1}{t}}dt$
$\displaystyle=16s_{A}^{2}(K-1)\frac{\sigma\sqrt{s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}}}{\alpha}\sqrt{T\log
T}.$

In summary, we get:

$\displaystyle R(T)$ $\displaystyle\leq
2s_{A}s_{2}\tau+16s_{A}^{2}(K-1)\frac{\sigma\sqrt{s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}}}{\alpha}\sqrt{T\log
T}$ $\displaystyle\ \ \
+2(K-1)s_{A}s_{2}\left(\left(\frac{\pi^{2}}{3}+\frac{10s_{A}^{2}}{\alpha}\right)\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)+\frac{\pi^{2}}{3}+\frac{2}{C_{0}^{2}}\right).$

This concludes the proof of the regret upper bound. Regarding the scaling,
note that $1/C_{0}^{2}=\mathcal{O}(s_{0}^{2})$. Therefore, we have:

$\displaystyle R(T)=\mathcal{O}\left(s_{0}^{2}\log d+\sqrt{s_{0}T\log
T}+s_{0}^{2}\right).$

This concludes the proof. $\Box$

##  Appendix B Proof of Lemmas

###  B.1 Proof of Lemma 1

We define $v\coloneqq\hat{\theta}_{0}^{(t)}-\theta$. We first analyze the
performance of the initial LASSO estimate.

######  Lemma 6.

Let $\hat{\Sigma}_{t}\coloneqq\frac{\sum_{s=1}^{t}A_{s}A_{s}^{\top}}{t}$ be
the empirical covariance matrix of the selected context vectors. Suppose
$\hat{\Sigma}_{t}$ satisfies the compatibility condition with the support $S$
with the compatibility constant $\phi_{t}$. Then, we have:

$\displaystyle\mathbb{P}\left(\|v\|_{1}\leq\frac{4s_{0}\lambda_{t}}{\phi_{t}^{2}}\right)\geq
1-2\exp\left(-\frac{t\lambda_{t}^{2}}{32\sigma^{2}s_{A}^{2}}+\log d\right).$

The next lemma then states that the compatibility constant of
$\hat{\Sigma}_{t}$ does not deviate much from the compatibility constant of
$\Sigma$.

######  Lemma 7.

Let
$C_{0}\coloneqq\min\left\\{\frac{1}{2},\frac{\phi_{0}^{2}}{256s_{0}s_{A}^{2}}\right\\}$.
For all $t\geq\frac{2\log(2d^{2})}{C_{0}^{2}}$, we have:

$\displaystyle\mathbb{P}\left(\phi^{2}(\hat{\Sigma}_{t},S)\geq\frac{\phi^{2}_{0}}{2}\right)\geq
1-\exp\left(-\frac{tC_{0}^{2}}{2}\right).$

Then, we follow the steps of the proof given by Zhou (2010). Let us define the
event $\mathcal{G}_{t}$ as:

$\displaystyle\mathcal{G}_{t}\coloneqq\left\\{\|v\|_{1}\leq\frac{4s_{0}\lambda_{t}}{\phi_{t}^{2}}\right\\}.$

For the rest of this section, we assume that the event $\mathcal{G}_{t}$
holds. Note that:

$\displaystyle\|v\|_{1}$ $\displaystyle\geq\|v_{S^{c}}\|_{1}$
$\displaystyle=\sum_{j\in S^{c}}|(\hat{\theta}_{0}^{(t)})_{j}|$
$\displaystyle\geq\sum_{j\in
S^{c}\cap\hat{S}_{0}^{(t)}}|(\hat{\theta}_{0}^{(t)})_{j}|$
$\displaystyle=\sum_{j\in\hat{S}_{0}^{(t)}\setminus
S}|(\hat{\theta}_{0}^{(t)})_{j}|$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}|\hat{S}_{0}^{(t)}\setminus
S|4\lambda_{t},$

where for $(a)$, we used the construction of $\hat{S}_{0}^{(t)}$ in the
algorithm. We get:

$\displaystyle|\hat{S}_{0}^{(t)}\setminus S|$
$\displaystyle\leq\frac{\|v\|_{1}}{4\lambda_{t}}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{s_{0}}{\phi_{t}^{2}},$

where for $(a)$, we used the definition of $\mathcal{G}_{t}$.

We have: $\forall j\in S$,

$\displaystyle|(\hat{\theta}_{0}^{(t)})_{j}|$
$\displaystyle\geq\theta_{\min}-\|v_{S}\|_{\infty}$
$\displaystyle\geq\theta_{\min}-\|v_{S}\|_{1}$
$\displaystyle\geq\theta_{\min}-\frac{4s_{0}\lambda_{t}}{\phi_{t}^{2}}.$

Therefore, when $t$ is large enough so that
$4\lambda_{t}\leq\theta_{\min}-\frac{4s_{0}\lambda_{t}}{\phi_{t}^{2}}$, we
have: $S\subset\hat{S}_{0}^{(t)}$. Using a similar argument, when $t$ is large
enough so that
$4\lambda_{t}\sqrt{\left(1+\frac{1}{\phi_{t}^{2}}\right)s_{0}}\leq\theta_{\min}-\frac{4s_{0}\lambda_{t}}{\phi_{t}^{2}}$,
it holds that $S\subset\hat{S}_{1}^{(t)}$. From the construction of
$\hat{S}_{1}^{(t)}$ in the algorithm, it also holds that:
$\hat{S}_{1}^{(t)}\subset\hat{S}_{0}^{(t)}$. Therefore,

$\displaystyle\|v\|_{1}$
$\displaystyle\geq\sum_{i\in\hat{S}_{0}^{(t)}\setminus
S}|(\hat{\theta}_{0}^{(t)})_{i}|$
$\displaystyle\geq\sum_{i\in\hat{S}_{1}^{(t)}\setminus
S}|(\hat{\theta}_{0}^{(t)})_{i}|$
$\displaystyle\geq|\hat{S}_{1}^{(t)}\setminus
S|4\lambda_{t}\sqrt{|\hat{S}_{0}^{(t)}|},$

and

$\displaystyle|\hat{S}_{1}^{(t)}\setminus S|$
$\displaystyle\leq\frac{\|v\|_{1}}{4\lambda_{t}\sqrt{|\hat{S}_{0}^{(t)}|}}$
$\displaystyle\leq\frac{1}{4\lambda_{t}\sqrt{|\hat{S}_{0}^{(t)}|}}\cdot\frac{4s_{0}\lambda_{t}}{\phi_{t}^{2}}$
$\displaystyle\leq\frac{\sqrt{s_{0}}}{\phi_{t}^{2}}.$

Note that the condition
$4\lambda_{t}\sqrt{\left(1+\frac{1}{\phi_{t}^{2}}\right)s_{0}}\leq\theta_{\min}-\frac{4s_{0}\lambda_{t}}{\phi_{t}^{2}}$
is equivalent to
$4\lambda_{t}\left(\sqrt{\left(1+\frac{1}{\phi_{t}^{2}}\right)s_{0}}+\frac{s_{0}}{\phi_{t}^{2}}\right)\leq\theta_{\min}$.
This concludes the proof of Lemma 1 by substituting
$\phi_{t}^{2}=\phi_{0}^{2}/2$. $\Box$

###  B.2 Proof of Lemmas used for the proof of Lemma 1

####  B.2.1 Proof of Lemma 6

the proof is similar to that given by Oh et al. (2020). Let us define the loss
function:

$\displaystyle\ell_{t}(\theta)\coloneqq\frac{1}{t}\sum_{s=1}^{t}(r_{t}-\langle\theta,A_{t}\rangle)^{2}.$

The initial LASSO estimate is given by:

$\displaystyle\hat{\theta}_{t}\coloneqq\arg\min_{\theta^{\prime}}\left\\{\ell_{t}(\theta^{\prime})+\lambda_{t}\|\theta^{\prime}\|_{1}\right\\}.$

From this definition, we get:

$\displaystyle\ell_{t}(\hat{\theta}_{t})+\lambda_{t}\|\hat{\theta}_{t}\|_{1}\leq\ell_{t}(\theta)+\lambda_{t}\|\theta\|_{1}.$

Let us denote $\operatorname{\mathbb{E}}[\cdot]$ as the expectation over
$r_{t}$ in this section. Note that in view of the previous inequality, we
have:

$\displaystyle\ell_{t}(\hat{\theta}_{t})-\operatorname{\mathbb{E}}[\ell_{t}(\hat{\theta}_{t})]+\operatorname{\mathbb{E}}[\ell_{t}(\hat{\theta}_{t})]-\operatorname{\mathbb{E}}[\ell_{t}(\theta)]+\lambda_{t}\|\hat{\theta}_{t}\|_{1}\leq\ell_{t}(\theta)-\operatorname{\mathbb{E}}[\ell_{t}(\theta)]+\lambda_{t}\|\theta\|_{1}.$

Denoting
$v_{t}(\theta)\coloneqq\ell_{t}(\theta)-\operatorname{\mathbb{E}}[\ell_{t}(\theta)]$
and
$\mathcal{E}(\theta^{\prime})\coloneqq\operatorname{\mathbb{E}}[\ell_{t}(\theta^{\prime})]-\operatorname{\mathbb{E}}[\ell_{t}(\theta)]$,

$\displaystyle
v_{t}(\hat{\theta}_{t})+\mathcal{E}(\hat{\theta}_{t})+\lambda_{t}\|\hat{\theta}_{t}\|_{1}\leq
v_{t}({\theta})+\lambda_{t}\|\theta\|_{1}.$

Let us define the event $\mathcal{T}_{t}$:

$\displaystyle\mathcal{T}_{t}\coloneqq\\{|v_{t}(\hat{\theta}_{t})-v_{t}({\theta})|\leq\frac{1}{2}\lambda_{t}\|\hat{\theta}_{t}-{\theta}\|_{1}\\}.$

We can condition on this event in the rest of the proof:

######  Lemma 8.

Assume that $A_{t}$ satisfies $\|A_{t}\|_{2}\leq s_{A}$ for all $t\in[T]$. We
have:

$\displaystyle\mathbb{P}\left(|v_{t}(\hat{\theta}_{t})-v_{t}({\theta})|\leq\frac{1}{2}\lambda_{t}\|\hat{\theta}_{t}-{\theta}\|_{1}\right)\geq
1-2\exp\left(-\frac{t\lambda_{t}^{2}}{32\sigma^{2}s_{A}^{2}}+\log d\right).$

Given the event $\mathcal{T}_{t}$, we have:

$\displaystyle 2\mathcal{E}(\hat{\theta}_{t})\leq
2\lambda_{t}(\|\theta\|_{1}-\|\hat{\theta}_{t}\|_{1})+\lambda_{t}\|\hat{\theta}_{t}-\theta\|_{1}.$

By the triangle inequality,

$\displaystyle\|\hat{\theta}_{t}\|_{1}$
$\displaystyle=\|\hat{\theta}_{t,S}\|_{1}+\|\hat{\theta}_{t,S^{c}}\|_{1}$
$\displaystyle\geq\|{\theta}_{S}\|_{1}-\|\hat{\theta}_{t,S}-{\theta}_{S}\|+\|\hat{\theta}_{t,S^{c}}\|_{1}.$

We also have:

$\displaystyle\|\hat{\theta}_{t}-\theta\|_{1}$
$\displaystyle=\|(\hat{\theta}_{t}-\theta)_{S}\|_{1}+\|(\hat{\theta}_{t}-\theta)_{S^{c}}\|_{1}$
$\displaystyle=\|\hat{\theta}_{t,S}-\theta_{S}\|_{1}+\|\hat{\theta}_{t,S^{c}}\|_{1}.$

Therefore, we get:

$\displaystyle 2\mathcal{E}(\hat{\theta}_{t})$ $\displaystyle\leq
2\lambda_{t}\|\theta\|_{1}-2\lambda_{t}(\|\theta_{S}\|_{1}-\|\hat{\theta}_{t,S}-\theta_{S}\|_{1}+\|\hat{\theta}_{t,S^{c}}\|_{1})+\lambda_{t}(\|\hat{\theta}_{t,S}-\theta_{S}\|_{1}+\|\hat{\theta}_{t,S^{c}}\|_{1})$
$\displaystyle=3\lambda_{t}\|\hat{\theta}_{t,S}-\theta_{S}\|_{1}-\lambda_{t}\|\hat{\theta}_{t,S^{c}}\|_{1}.$
(3)

From the compatibility condition, we get:

$\displaystyle\|\hat{\theta}_{t,S}-\theta_{S}\|_{1}^{2}\leq\frac{s_{0}(\hat{\theta}_{t}-\theta)^{\top}\hat{\Sigma}_{t}(\hat{\theta}_{t}-\theta)}{\phi_{t}^{2}}$
(4)

Using inequality (3), we get:

$\displaystyle
2\mathcal{E}(\hat{\theta}_{t})+\lambda_{t}\|\hat{\theta}_{t}-{\theta}\|_{1}$
$\displaystyle=2\mathcal{E}(\hat{\theta}_{t})+\lambda_{t}\|\hat{\theta}_{t,S^{c}}\|_{1}+\lambda_{t}\|\hat{\theta}_{t,S}-{\theta}_{S}\|_{1}$
$\displaystyle\leq
3\lambda_{t}\|\hat{\theta}_{t,S}-\theta_{S}\|_{1}+\lambda_{t}\|\hat{\theta}_{t,S}-{\theta}_{S}\|_{1}$
$\displaystyle=4\lambda_{t}\|\hat{\theta}_{t,S}-{\theta}_{S}\|_{1}$
$\displaystyle\leq\frac{4\lambda_{t}}{{\phi_{t}^{2}}}\sqrt{{s_{0}(\hat{\theta}_{t}-\theta)^{\top}\hat{\Sigma}_{t}(\hat{\theta}_{t}-\theta)}}$
$\displaystyle\leq{(\hat{\theta}_{t}-\theta)^{\top}\hat{\Sigma}_{t}(\hat{\theta}_{t}-\theta)}+\frac{4\lambda_{t}^{2}s_{0}}{\phi_{t}^{2}}$
$\displaystyle\leq
2\mathcal{E}(\hat{\theta}_{t})+\frac{4\lambda_{t}^{2}s_{0}}{\phi_{t}^{2}},$

where for the third inequality, we used $4uv\leq u^{2}+4v^{2}$ with
$u=\sqrt{{(\hat{\theta}_{t}-\theta)^{\top}\hat{\Sigma}_{t}(\hat{\theta}_{t}-\theta)}}$
and $v=\frac{\lambda_{t}\sqrt{s_{0}}}{\phi_{t}}$. The last inequality is due
to Lemma 9:

######  Lemma 9.

We have:

$\displaystyle\mathcal{E}(\hat{\theta}_{t})\geq\frac{1}{2}{(\hat{\theta}_{t}-\theta)^{\top}\hat{\Sigma}_{t}(\hat{\theta}_{t}-\theta)}\;.$

Thus, we get:

$\displaystyle\|\hat{\theta}_{t}-{\theta}\|_{1}\leq\frac{4\lambda_{t}s_{0}}{\phi_{t}^{2}}.$

This concludes the proof. $\Box$

####  B.2.2 Proof of Lemma 7

First we define the adapted Gram matrix
$\Sigma_{t}\coloneqq\frac{1}{t}\sum_{s=1}^{t}\operatorname{\mathbb{E}}[A_{s}A_{s}^{\top}|\mathcal{F}_{s-1}]$.
From the construction of the algorithm,
$\operatorname{\mathbb{E}}[A_{s}A_{s}^{\top}|\mathcal{F}_{s-1}]=\operatorname{\mathbb{E}}[\sum_{k=1}^{K}A_{s,k}A_{s,k}^{\top}\mathds{1}\\{k=\mathop{\rm
argmax}\limits_{k^{\prime}}\langle
A_{s,k},\hat{\theta}_{s}\rangle\\}|\;\hat{\theta}_{s}]$ satisfies the
compatibility condition with the compatibility constant
$\phi(\Sigma_{t},S)=\phi(\Sigma,S)\geq\phi_{0}^{2}$ by Assumption 2.
Furthermore, we have a following adaptive matrix concentration results for
$\hat{\Sigma}_{t}$:

######  Lemma 10.

Let
$C_{0}\coloneqq\min\left\\{\frac{1}{2},\frac{\phi_{0}^{2}}{256s_{0}s_{A}^{2}}\right\\}$.
We have, for all $t\geq\frac{2\log(2d^{2})}{C_{0}^{2}}$,

$\displaystyle\mathbb{P}\left(\frac{1}{2s_{A}^{2}}\|\hat{\Sigma}_{t}-\Sigma_{t}\|_{\infty}\geq\frac{\phi(\Sigma_{t},S)}{64s_{0}s_{A}^{2}}\right)\leq\exp\left(-\frac{tC_{0}^{2}}{2}\right).$

We use a following result from Bühlmann and Van De Geer (2011):

######  Lemma 11 (Corollary 6.8. in Bühlmann and Van De Geer (2011)).

Suppose $\Sigma_{0}$ satisfies the compatibility condition for the set $S$
with $|S|=s_{0}$, with the compatibility constant $\phi^{2}(\Sigma_{0},S)>0$,
and that $\|\Sigma_{0}-\Sigma_{1}\|_{\infty}\leq\lambda$, where
$\frac{32\lambda s_{0}}{\phi^{2}(\Sigma_{0},S)}\leq 1$. Then, the
compatibility condition also holds for $\Sigma_{1}$ with the compatibility
constant $\frac{\phi^{2}(\Sigma_{0},S)}{2}$, i.e.,
$\phi^{2}(\Sigma_{1},S)\geq\frac{\phi^{2}(\Sigma_{0},S)}{2}.$

Combining the above results, we get, for all
$t\geq\frac{2\log(2d^{2})}{C_{0}^{2}}$:

$\displaystyle\phi^{2}(\hat{\Sigma}_{t},S)$
$\displaystyle\geq\frac{\phi^{2}({\Sigma}_{t},S)}{2}$
$\displaystyle\geq\frac{\phi^{2}_{0}}{2},$

with probability at least $1-\exp\left(-\frac{tC_{0}^{2}}{2}\right)$. This
concludes the proof. $\Box$

####  B.2.3 Proof of Lemma 8

Let us denote $\hat{\theta}=\hat{\theta}_{t}$ for simplicity. We compute
$v_{t}(\hat{\theta})$ as:

$\displaystyle v_{t}(\hat{\theta})$
$\displaystyle=\ell_{t}(\hat{\theta})-\operatorname{\mathbb{E}}[\ell_{t}(\hat{\theta})]$
$\displaystyle=\frac{1}{t}\sum_{s=1}^{t}(r_{s}-\langle\hat{\theta},A_{s}\rangle)^{2}-\frac{1}{t}\sum_{s=1}^{t}\operatorname{\mathbb{E}}\left[(r_{s}-\langle\hat{\theta},A_{s}\rangle)^{2}\right]$
$\displaystyle=\frac{1}{t}\sum_{s=1}^{t}(\langle{\theta},A_{s}\rangle+\varepsilon_{s}-\langle\hat{\theta},A_{s}\rangle)^{2}-\frac{1}{t}\sum_{s=1}^{t}\operatorname{\mathbb{E}}\left[(\langle{\theta},A_{s}\rangle+\varepsilon_{s}-\langle\hat{\theta},A_{s}\rangle)^{2}\right]$
$\displaystyle=\frac{1}{t}\sum_{s=1}^{t}(2\varepsilon_{s}\langle\theta-\hat{\theta},A_{s}\rangle+\varepsilon_{s}^{2}-\operatorname{\mathbb{E}}[\varepsilon_{s}^{2}]).$

We also have that:

$\displaystyle v_{t}({\theta})$
$\displaystyle=\frac{1}{t}\sum_{s=1}^{t}(\varepsilon_{s}^{2}-\operatorname{\mathbb{E}}[\varepsilon_{s}^{2}]).$

Therefore, we can compute:

$\displaystyle v_{t}(\hat{\theta})-v_{t}({\theta})$
$\displaystyle=\frac{1}{t}\sum_{s=1}^{t}2\varepsilon_{s}\langle\theta-\hat{\theta},A_{s}\rangle$
$\displaystyle\leq\frac{2}{t}\left\|\sum_{s=1}^{t}\varepsilon_{s}A_{s}\right\|_{\infty}\|\theta-\hat{\theta}\|_{1},$

where we used the Hölder’s inequality in the above inequality. We have that:

$\displaystyle\mathbb{P}\left(\frac{2}{t}\left\|\sum_{s=1}^{t}\varepsilon_{s}A_{s}\right\|_{\infty}\leq\lambda\right)\geq
1-\sum_{i=1}^{d}\mathbb{P}\left(\frac{2}{t}\left|\sum_{s=1}^{t}\varepsilon_{s}(A_{s})_{i}\right|>\lambda\right),$

where $(A_{s})_{i}$ is the $i$-th element of $A_{s}$. Define
$\widetilde{\mathcal{F}}_{t}$ as a $\sigma$-algebra generated by the random
variables
$(A_{1},\mathcal{A}_{1},\varepsilon_{1},\ldots,A_{t},\mathcal{A}_{t},\varepsilon_{t},\mathcal{A}_{t+1})$.
For each $i\in[d]$, we get
$\operatorname{\mathbb{E}}[\varepsilon_{s}(A_{s})_{i}|\widetilde{\mathcal{F}}_{s-1}]=(A_{s})_{i}\operatorname{\mathbb{E}}[\varepsilon_{s}|\widetilde{\mathcal{F}}_{s-1}]=0$.
Thus, for each $i\in[d]$, $\\{\varepsilon_{s}(A_{s})_{i}\\}_{s=1}^{t}$ is a
martingale difference sequence adapted to the filtration
$\widetilde{\mathcal{F}}_{1}\subset\ldots\subset\widetilde{\mathcal{F}}_{t-1}$.
By the assumption, we have $|(A_{s})_{i}|\leq\|A_{s}\|_{2}\leq s_{A}$. We
compute, for each $\alpha\in\mathbb{R}$,

$\displaystyle\operatorname{\mathbb{E}}[\exp(\alpha\varepsilon_{s}(A_{s})_{i})|\widetilde{\mathcal{F}}_{s-1}]$
$\displaystyle\leq\operatorname{\mathbb{E}}[\exp(\alpha\varepsilon_{s}s_{A})|\widetilde{\mathcal{F}}_{s-1}]$
$\displaystyle\leq\exp\left(\frac{\alpha^{2}s_{A}^{2}\sigma^{2}}{2}\right).$

Therefore $\varepsilon_{s}(A_{s})_{i}$ is also a sub-Gaussian random variable
with the variance proxy $(s_{A}\sigma)^{2}$. Next, we use the concentration
results by Wainwright (2019), Theorem 2.19:

######  Theorem 3.

Let $(Z_{t},\widetilde{\mathcal{F}}_{t})_{t=1}^{\infty}$ be a martingale
difference sequence, and assume that for all $\alpha\in\mathbb{R}$,
$\operatorname{\mathbb{E}}[\exp(\alpha
Z_{s})|\widetilde{\mathcal{F}}_{s-1}]\leq\exp(\frac{\alpha^{2}\sigma^{2}}{2})$
with probability one. Then, for all $x\geq 0$, we get:

$\displaystyle\mathbb{P}\left(\left|\sum_{s=1}^{t}Z_{s}\right|\geq
x\right)\leq 2\exp\left(-\frac{x^{2}}{2t\sigma^{2}}\right).$

From these results, we get:

$\displaystyle\mathbb{P}\left(\left|\sum_{s=1}^{t}\varepsilon_{s}(A_{s})_{i}\right|>\frac{t\lambda}{2}\right)$
$\displaystyle\leq
2\exp\left(-\frac{t\lambda^{2}}{8\sigma^{2}s_{A}^{2}}\right).$

Taking $\lambda=\frac{1}{2}\lambda_{t}$,

$\displaystyle\mathbb{P}\left(\frac{2}{t}\left\|\sum_{s=1}^{t}\varepsilon_{s}A_{s}\right\|_{\infty}\leq\frac{\lambda_{t}}{2}\right)$
$\displaystyle\geq
1-2d\exp\left(-\frac{t\lambda_{t}^{2}}{32\sigma^{2}s_{A}^{2}}\right)$
$\displaystyle=1-2\exp\left(-\frac{t\lambda_{t}^{2}}{32\sigma^{2}s_{A}^{2}}+\log
d\right).$

$\Box$

####  B.2.4 Proof of Lemma 9

We denote $\hat{\theta}_{t}=\hat{\theta}$ for brevity. From the definitions of
$\mathcal{E}(\theta^{\prime})$ and $\ell_{t}(\theta^{\prime})$,

$\displaystyle\mathcal{E}(\hat{\theta})$
$\displaystyle=\operatorname{\mathbb{E}}[\ell_{t}(\hat{\theta})]-\operatorname{\mathbb{E}}[\ell_{t}(\theta)]$
$\displaystyle=\frac{1}{t}\operatorname{\mathbb{E}}\left[\sum_{s=1}^{t}(\langle\hat{\theta}-\theta,A_{s}\rangle+\varepsilon_{s})^{2}-\sum_{s=1}^{t}\varepsilon_{s}^{2}\right]$
$\displaystyle=\frac{1}{t}\sum_{s=1}^{t}\langle\hat{\theta}-\theta,A_{s}\rangle^{2}$
$\displaystyle=\frac{1}{t}\sum_{s=1}^{t}(\hat{\theta}-\theta)^{\top}A_{s}A_{s}^{\top}(\hat{\theta}-\theta)$
$\displaystyle=(\hat{\theta}-\theta)^{\top}\hat{\Sigma}_{t}(\hat{\theta}-\theta)$
$\displaystyle\geq\frac{1}{2}(\hat{\theta}-\theta)^{\top}\hat{\Sigma}_{t}(\hat{\theta}-\theta),$

where for the inequality, we used the positive semi-definiteness of
$\hat{\Sigma}_{t}$. $\Box$

####  B.2.5 Proof of Lemma 10

Let us define $\gamma^{ij}_{t}(A_{t})$ as:

$\displaystyle\gamma^{ij}_{t}(A_{t})\coloneqq\frac{1}{2C^{2}_{A}}\left((A_{t})_{i}(A_{t})_{j}-\operatorname{\mathbb{E}}[(A_{t})_{i}(A_{t})_{j}\;|\;\mathcal{F}_{t-1}]\right),$

where $(A_{t})_{i}$ is the $i$-th element of $A_{t}$. We have a following a
Bernstein-like inequality for the adapted data:

######  Lemma 12 (Bernstein-like inequality for the adapted data Oh et al.
(2020)).

Suppose for all $t\geq 1$, for all $1\leq i\leq j\leq d$,
$\operatorname{\mathbb{E}}[\gamma^{ij}_{t}(A_{t})|\mathcal{F}_{t-1}]=0$ and
$\operatorname{\mathbb{E}}[|\gamma^{ij}_{t}(A_{t})|^{m}\;|\;\mathcal{F}_{t-1}]\leq
m!$ for all integer $m\geq 2$. Then, for all $x>0$, and for all integer $t\geq
1$, we have:

$\displaystyle\mathbb{P}\left(\max_{1\leq i\leq j\leq
d}\left|\frac{1}{t}\sum_{s=1}^{t}\gamma^{ij}_{s}(A_{s})\right|\geq
x+\sqrt{2x}+\sqrt{\frac{4\log(2d^{2})}{t}}+\frac{2\log(2d^{2})}{t}\right)\leq\exp\left(-\frac{tx}{2}\right).$

Note that
$\frac{1}{2s_{A}^{2}}\|\hat{\Sigma}_{t}-{\Sigma}_{t}\|_{\infty}=\max_{1\leq
i\leq j\leq d}\left|\frac{1}{t}\sum_{s=1}^{t}\gamma^{ij}_{s}(A_{s})\right|$,
$\operatorname{\mathbb{E}}[\gamma^{ij}_{t}(A_{t})|\mathcal{F}_{t-1}]=0$, and
$\operatorname{\mathbb{E}}[|\gamma^{ij}_{t}(A_{t})|^{m}\;|\;\mathcal{F}_{t-1}]\leq
1$ for all integer $m\geq 2$. Therefore, we can apply Lemma 12:

$\displaystyle\mathbb{P}\left(\frac{1}{2s_{A}^{2}}\|\hat{\Sigma}_{t}-{\Sigma}_{t}\|_{\infty}\geq
x+\sqrt{2x}+\sqrt{\frac{4\log(2d^{2})}{t}}+\frac{2\log(2d^{2})}{t}\right)\leq\exp\left(-\frac{tx}{2}\right).$

For all $t\geq\frac{2\log(2d^{2})}{C_{0}^{2}}$ with
$C_{0}\coloneqq\min\left\\{\frac{1}{2},\frac{\phi_{0}^{2}}{256s_{0}s_{A}^{2}}\right\\}$,
taking $x=C_{0}^{2}$,

$\displaystyle
x+\sqrt{2x}+\sqrt{\frac{4\log(2d^{2})}{t}}+\frac{2\log(2d^{2})}{t}$
$\displaystyle\leq 2C_{0}^{2}+2\sqrt{2}C_{0}$ $\displaystyle\leq 4C_{0}$
$\displaystyle\leq\frac{\phi_{0}^{2}}{64s_{0}s_{A}^{2}}$
$\displaystyle\leq\frac{\phi^{2}(\Sigma_{t},S)}{64s_{0}s_{A}^{2}}\;.$

In summary, for all $t\geq\frac{2\log(2d^{2})}{C_{0}^{2}}$, we get:

$\displaystyle\mathbb{P}\left(\frac{1}{2s_{A}^{2}}\|\hat{\Sigma}_{t}-{\Sigma}_{t}\|_{\infty}\geq\frac{\phi^{2}(\Sigma_{t},S)}{64s_{0}s_{A}^{2}}\right)$
$\displaystyle\leq\mathbb{P}\left(\frac{1}{2s_{A}^{2}}\|\hat{\Sigma}_{t}-{\Sigma}_{t}\|_{\infty}\geq
C_{0}^{2}+\sqrt{2}C_{0}+\sqrt{\frac{4\log(2d^{2})}{t}}+\frac{2\log(2d^{2})}{t}\right)$
$\displaystyle\leq\exp\left(-\frac{tC_{0}^{2}}{2}\right).$

This concludes the proof. $\Box$

###  B.3 Proof of Lemma 2

First, we prove the lower bound on the smallest eigenvalue of the expected
covariance matrices. Let
$\Sigma_{\hat{S}}\coloneqq\frac{1}{t}\sum_{s=1}^{t}\operatorname{\mathbb{E}}[A_{s}(\hat{S})A_{s}(\hat{S})^{\top}\mid\mathcal{F}_{t-1}]$.
By Assumption 3 and the construction of the algorithm, under the event
$\mathcal{E}_{t}$, we get:

$\displaystyle\lambda_{\min}(\Sigma_{\hat{S}})$
$\displaystyle=\lambda_{\min}\left(\frac{1}{t}\sum_{s=1}^{t}\operatorname{\mathbb{E}}\left[\sum_{k=1}^{K}A_{s,k,\hat{S}}A_{s,k,\hat{S}}\mathds{1}\\{k=\mathop{\rm
argmax}\limits_{k^{\prime}}\langle
A_{k^{\prime}},\hat{\theta}_{s}\rangle\\}\mid\hat{\theta}_{s}\right]\right)$
$\displaystyle\geq\sum_{s=1}^{t}\lambda_{\min}\left(\frac{1}{t}\operatorname{\mathbb{E}}\left[\sum_{k=1}^{K}A_{s,k,\hat{S}}A_{s,k,\hat{S}}\mathds{1}\\{k=\mathop{\rm
argmax}\limits_{k^{\prime}}\langle
A_{k^{\prime}},\hat{\theta}_{s}\rangle\\}\mid\hat{\theta}_{s}\right]\right)$
$\displaystyle=\alpha,$

where for the inequality, we used the concavity of $\lambda_{\min}(\cdot)$
over the positive semi-definite matrices. Next, we prove the upper bound on
the largest eigenvalue of $A_{s}(\hat{S})A_{s}(\hat{S})^{\top}$:

$\displaystyle\lambda_{\max}(A_{s}(\hat{S})A_{s}(\hat{S})^{\top})$
$\displaystyle\leq\lambda_{\max}(A_{s}A_{s}^{\top})$
$\displaystyle=\max_{\|v\|=1}v^{\top}A_{s}A_{s}^{\top}v$
$\displaystyle\leq\max_{\|v\|=1}\|v\|_{2}^{2}\|A_{s}\|_{2}^{2}$
$\displaystyle\leq s_{A}^{2},$

where for the second inequality, we used the Cauchy-Schwarz inequality. Now
recall the matrix Chernoff inequality by Tropp (2011):

######  Theorem 4 (Matrix Chernoff, Theorem 3.1 of Tropp (2011)).

Let $\mathcal{F}_{1}\subset\mathcal{F}_{2}\subset\ldots\subset\mathcal{F}_{t}$
be a filtration and a consider a finite sequence $\\{X_{s}\\}$ of positive
semi-definite matrices with dimension $d$, adapted to the filtration. Suppose
$\lambda_{\max}(X_{k})\leq R$ almost surely. Define the finite series:
$Y\coloneqq\sum_{s=1}^{t}X_{s}$ and
$W\coloneqq\sum_{s=1}^{t}\operatorname{\mathbb{E}}[X_{s}\mid\mathcal{F}_{s-1}]$.
Then, for all $\mu\geq 0$, for all $\delta\in[0,1)$, we have:

$\displaystyle\mathbb{P}\left(\lambda_{\min}(Y)\leq(1-\delta)\mu\text{ and
}\lambda_{\min}(W)\geq\mu\right)\leq
d\left(\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\right)^{\frac{\mu}{R}}.$

Taking $R=s_{A}^{2}$, $X_{s}=A_{s,\hat{S}}A_{s,\hat{S}}^{\top}$,
$Y=t\hat{\Sigma}_{\hat{S}}$, $W=t{\Sigma}_{\hat{S}}$, $\delta=1/2$,
$\mu=t\alpha$:

$\displaystyle\mathbb{P}\left(\lambda_{\min}(t\hat{\Sigma}_{\hat{S}})\leq\frac{1}{2}t\alpha\text{
and }\lambda_{\min}(t{\Sigma}_{\hat{S}})\geq t\alpha\right)$
$\displaystyle\leq\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)\left(\frac{e^{-0.5}}{0.5^{0.5}}\right)^{\frac{t\alpha}{s_{A}^{2}}}$
$\displaystyle\leq\exp\left(\log\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)-\frac{t\alpha}{10s_{A}^{2}}\right),$

where for the last inequality, we used $-0.5-0.5\log(0.5)<-\frac{1}{10}$. This
concludes the proof. $\Box$

###  B.4 Proof of Lemma 3

In this proof, we denote $\hat{S}=\hat{S}_{1}^{(t)}$ and
$\varepsilon=(\varepsilon_{1},\ldots,\varepsilon_{t})^{\top}$. Assume
$\lambda_{\min}(\hat{\Sigma}_{\hat{S}})\geq\lambda$. We have:

$\displaystyle\|\hat{\theta}_{t+1}-\theta\|_{2}$
$\displaystyle=\|(A(\hat{S})^{\top}A(\hat{S}))^{-1}A(\hat{S})^{\top}R-\theta\|_{2}$
$\displaystyle=\|(A(\hat{S})^{\top}A(\hat{S}))^{-1}A(\hat{S})^{\top}(A\theta+\varepsilon)-\theta\|_{2}$
$\displaystyle=\|(A(\hat{S})^{\top}A(\hat{S}))^{-1}A(\hat{S})^{\top}(A(\hat{S})\theta({\hat{S}})+\varepsilon)-\theta\|_{2}$
$\displaystyle=\|(A(\hat{S})^{\top}A(\hat{S}))^{-1}A(\hat{S})^{\top}\varepsilon\|_{2}$
$\displaystyle\leq\|(A(\hat{S})^{\top}A(\hat{S}))^{-1}\|_{2}\|A(\hat{S})^{\top}\varepsilon\|_{2}$
$\displaystyle\leq\frac{1}{\lambda t}\|A(\hat{S})^{\top}\varepsilon\|_{2}.$

We get (note that we are conditioning on a fixed $\hat{S}$ during the proof):

$\displaystyle\mathbb{P}\left(\|\hat{\theta}_{t+1}-\theta\|_{2}\geq
x\;\text{and}\;\lambda_{\min}(\hat{\Sigma}_{\hat{S}})\geq\lambda\right)$
$\displaystyle=\mathbb{P}\left(\|\hat{\theta}_{t+1}-\theta\|_{2}\geq
x\;\middle|\;\lambda_{\min}(\hat{\Sigma}_{\hat{S}})\geq\lambda\right)\mathbb{P}(\lambda_{\min}(\hat{\Sigma}_{\hat{S}})\geq\lambda)$
$\displaystyle\leq\mathbb{P}\left(\|A(\hat{S})^{\top}\varepsilon\|_{2}\geq\lambda
tx\;\middle|\;\lambda_{\min}(\hat{\Sigma}_{\hat{S}})\geq\lambda\right)\mathbb{P}(\lambda_{\min}(\hat{\Sigma}_{\hat{S}})\geq\lambda)$
$\displaystyle\leq\mathbb{P}\left(\|A(\hat{S})^{\top}\varepsilon\|_{2}\geq\lambda
tx\right)$
$\displaystyle\leq\sum_{i=1}^{d}\mathbb{P}\left(\left|\sum_{s=1}^{t}\varepsilon_{s}(A_{s})_{i}\mathds{1}\left\\{i\in\hat{S}\right\\}\right|\geq\frac{\lambda
tx}{\sqrt{s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}}}\right)$
$\displaystyle=\sum_{i\in\hat{S}}\mathbb{P}\left(\left|\sum_{s=1}^{t}\varepsilon_{s}(A_{s})_{i}\right|\geq\frac{\lambda
tx}{\sqrt{s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}}}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}2\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)\exp\left(-\frac{\lambda^{2}tx^{2}}{2\sigma^{2}s_{A}^{2}\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)}\right),$

where for $(a)$, we used Theorem 3. This concludes the proof. $\Box$

###  B.5 Proof of Lemma 4

We follow the proof strategy of Lemma 6 in Bastani et al. (2020). Let
$r_{t}^{\pi}$ be the instantaneous expected regret of algorithm $\pi$ at round
$t$ defined as:

$\displaystyle
r_{t}^{\pi}\coloneqq\operatorname{\mathbb{E}}\left[\max_{A\in\mathcal{A}_{t}}\langle
A-A_{t},\theta\rangle\right].$

Let us define the events
$\mathcal{R}_{k}\coloneqq\\{\mathcal{A}_{t}\in\mathbb{R}^{K\times
d}:k\in\mathop{\rm argmax}\limits_{k^{\prime}}\langle
A_{t,k^{\prime}},\theta\rangle\\}$ and
$\mathcal{G}_{t}^{\lambda}\coloneqq\left\\{\lambda_{\min}(\hat{\Sigma}_{\hat{S}})\geq\lambda\right\\}$.
We have:

$\displaystyle r_{t}^{\pi}$
$\displaystyle\leq\sum_{k=1}^{K}\operatorname{\mathbb{E}}\left[r_{t}^{\pi}\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\right]\mathbb{P}\left(\mathcal{A}_{t}\in\mathcal{R}_{k}\right).$

The term
$\operatorname{\mathbb{E}}\left[r_{t}^{\pi}\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\right]$
can be further computed as:

$\displaystyle\operatorname{\mathbb{E}}\left[r_{t}^{\pi}\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\right]$
$\displaystyle=\operatorname{\mathbb{E}}\left[\langle
A_{t,k}-A_{t},\theta\rangle\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}\left[\mathds{1}\left\\{\langle
A_{t},\hat{\theta}_{t}\rangle\geq\langle
A_{t,k},\hat{\theta}_{t}\rangle\right\\}\langle
A_{t,k}-A_{t},\theta\rangle\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\right]$
$\displaystyle\leq\sum_{\ell\neq
k}\operatorname{\mathbb{E}}\left[\mathds{1}\left\\{\langle
A_{t,\ell},\hat{\theta}_{t}\rangle\geq\langle
A_{t,k},\hat{\theta}_{t}\rangle\right\\}\langle
A_{t,k}-A_{t,\ell},\theta\rangle\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\right]$
$\displaystyle\leq\sum_{\ell\neq
k}\operatorname{\mathbb{E}}\left[\mathds{1}\left\\{\langle
A_{t,\ell},\hat{\theta}_{t}\rangle\geq\langle
A_{t,k},\hat{\theta}_{t}\rangle\right\\}\langle
A_{t,k}-A_{t,\ell},\theta\rangle\mid\mathcal{A}_{t}\in\mathcal{R}_{k},\
\mathcal{E}_{t},\ \mathcal{G}_{t}^{\frac{\alpha}{2}}\right]$ $\displaystyle\ \
\
+2(K-1)s_{A}s_{2}\left(\mathbb{P}(\mathcal{E}_{t}^{c})+\mathbb{P}\left(\left(\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)^{c}\middle|\mathcal{E}_{t}\right)\right).$

Let us denote the event
$I_{h}\coloneqq\\{\mathcal{A}_{t}\in\mathbb{R}^{K\times d}:\langle
A_{t,k}-A_{t,\ell},\theta\rangle\in(2\delta s_{A}h,2\delta s_{A}(h+1)]\\}$
where

$\displaystyle\delta=\frac{\sigma
s_{A}}{\alpha}\sqrt{\frac{8\left(s_{0}+\frac{2s_{0}}{\phi_{0}^{2}}\right)}{t-1}}.$

By conditioning on $I_{h}$, we get:

$\displaystyle\operatorname{\mathbb{E}}\left[\mathds{1}\left\\{\langle
A_{t,\ell},\hat{\theta}_{t}\rangle\geq\langle
A_{t,k},\hat{\theta}_{t}\rangle\right\\}\langle
A_{t,k}-A_{t,\ell},\theta\rangle\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\cap
I_{h},\ \mathcal{E}_{t},\ \mathcal{G}_{t}^{\frac{\alpha}{2}}\right]$
$\displaystyle\leq\sum_{h=0}^{\lceil
s_{2}/\delta\rceil}\operatorname{\mathbb{E}}\left[\mathds{1}\left\\{\langle
A_{t,\ell},\hat{\theta}_{t}\rangle\geq\langle
A_{t,k},\hat{\theta}_{t}\rangle\right\\}\langle
A_{t,k}-A_{t,\ell},\theta\rangle\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\cap
I_{h},\ \mathcal{E}_{t},\
\mathcal{G}_{t}^{\frac{\alpha}{2}}\right]\mathbb{P}(\mathcal{A}_{t}\in I_{h})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{h=0}^{\lceil
s_{2}/\delta\rceil}2\delta
s_{A}(h+1)\operatorname{\mathbb{E}}\left[\mathds{1}\left\\{\langle
A_{t,\ell},\hat{\theta}_{t}\rangle\geq\langle
A_{t,k},\hat{\theta}_{t}\rangle\right\\}\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\cap
I_{h},\ \mathcal{E}_{t},\
\mathcal{G}_{t}^{\frac{\alpha}{2}}\right]\mathbb{P}\left(\mathcal{A}_{t}\in(0,2\delta
s_{A}(h+1)]\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\sum_{h=0}^{\lceil
s_{2}/\delta\rceil}4\delta^{2}s_{A}^{2}(h+1)^{2}C_{\text{m}}\mathbb{P}\left(\langle
A_{t,\ell},\hat{\theta}_{t}\rangle\geq\langle
A_{t,k},\hat{\theta}_{t}\rangle\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\cap
I_{h},\ \mathcal{E}_{t},\ \mathcal{G}_{t}^{\frac{\alpha}{2}}\right),$

where for $(a)$, we used the definition of $I_{h}$ and for $(b)$, we used
Assumption 4. Under the event $\mathcal{A}_{t}\in I_{h}$, the event $\langle
A_{t,\ell},\hat{\theta}_{t}\rangle\geq\langle A_{t,k},\hat{\theta}_{t}\rangle$
happens only when at least one of the events $\langle
A_{t,k},\theta-\hat{\theta}\rangle\geq\delta s_{A}h$ or $\langle
A_{t,\ell},\hat{\theta}-\theta\rangle\geq\delta s_{A}h$ holds. Therefore,

$\displaystyle\mathbb{P}\left(\langle
A_{t,\ell},\hat{\theta}_{t}\rangle\geq\langle
A_{t,k},\hat{\theta}_{t}\rangle\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\cap
I_{h},\ \mathcal{E}_{t},\ \mathcal{G}_{t}^{\frac{\alpha}{2}}\right)$
$\displaystyle\leq\mathbb{P}\left(\langle
A_{t,k},\theta-\hat{\theta}\rangle\geq\delta
s_{A}h\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\cap I_{h},\ \mathcal{E}_{t},\
\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)+\mathbb{P}\left(\langle
A_{t,\ell},\hat{\theta}-\theta\rangle\geq\delta
s_{A}h\mathcal{A}_{t}\in\mathcal{R}_{k}\cap I_{h},\ \mathcal{E}_{t},\
\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\mathbb{P}\left(\|\theta-\hat{\theta}\|_{2}\geq\delta
h\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\cap I_{h},\ \mathcal{E}_{t},\
\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)+\mathbb{P}\left(\|\theta-\hat{\theta}\|_{2}\geq\delta
h\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\cap I_{h},\ \mathcal{E}_{t},\
\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)$
$\displaystyle=2\mathbb{P}\left(\|\theta-\hat{\theta}\|_{2}\geq\delta
h\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\cap I_{h},\ \mathcal{E}_{t},\
\mathcal{G}_{t}^{\frac{\alpha}{2}}\right),$

where for $(a)$, we used the Cauchy–Schwarz inequality. Let us denote
$s^{\prime}=s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}$. Then, using Lemma 3, we
get:

$\displaystyle\mathbb{P}\left(\|\theta-\hat{\theta}\|_{2}\geq\delta
h\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\cap I_{h},\ \mathcal{E}_{t},\
\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)$ $\displaystyle\leq
2s^{\prime}\exp\left(-\frac{\alpha^{2}t\delta^{2}h^{2}}{8\sigma^{2}s_{A}^{2}s^{\prime}}\right)$
$\displaystyle=2s^{\prime}\exp\left(-h^{2}\right).$

We also trivially have that:

$\displaystyle\mathbb{P}\left(\|\theta-\hat{\theta}\|_{2}\geq\delta
h\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\cap I_{h},\ \mathcal{E}_{t},\
\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)$ $\displaystyle\leq 1.$

Therefore, we can upper bound the expected instantaneous regret as:

$\displaystyle r_{t}^{\pi}$
$\displaystyle\leq\sum_{k=1}^{K}\operatorname{\mathbb{E}}\left[r_{t}^{\pi}\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\right]\mathbb{P}\left(\mathcal{A}_{t}\in\mathcal{R}_{k}\right)$
$\displaystyle\leq\sum_{k=1}^{K}\left(\sum_{\ell\neq
k}\left(\sum_{h=0}^{\lceil
s_{2}/\delta\rceil}\left(4\delta^{2}s_{A}^{2}(h+1)^{2}C_{\text{m}}\min\left\\{1,4s^{\prime}\exp\left(-h^{2}\right)\right\\}\right)\right)\right.$
$\displaystyle\ \ \
\left.+2(K-1)s_{A}s_{2}\left(\mathbb{P}(\mathcal{E}_{t}^{c})+\mathbb{P}\left(\left(\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)^{c}\right)\right)\right)\cdot\mathbb{P}\left(\mathcal{A}_{t}\in\mathcal{R}_{k}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}4\delta^{2}s_{A}^{2}C_{\text{m}}(K-1)\sum_{h=0}^{\lceil
s_{2}/\delta\rceil}(h+1)^{2}\min\left\\{1,4s^{\prime}\exp\left(-h^{2}\right)\right\\}+2(K-1)s_{A}s_{2}\left(\mathbb{P}(\mathcal{E}_{t}^{c})+\mathbb{P}\left(\left(\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)^{c}\middle|\mathcal{E}_{t}\right)\right)$
$\displaystyle\leq
4\delta^{2}s_{A}^{2}C_{\text{m}}(K-1)\left(\sum_{h=0}^{h_{0}}(h+1)^{2}+\sum_{h=h_{0}+1}^{h_{\max}}4s^{\prime}(h+1)^{2}\exp\left(-h^{2}\right)\right)+2(K-1)s_{A}s_{2}\left(\mathbb{P}(\mathcal{E}_{t}^{c})+\mathbb{P}\left(\left(\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)^{c}\middle|\mathcal{E}_{t}\right)\right)$

where for $(a)$, we used
$\sum_{k=1}^{K}\mathbb{P}\left(\mathcal{A}_{t}\in\mathcal{R}_{k}\right)=1$
from Assumption 4 and we set $h_{0}\coloneqq\lfloor\sqrt{\log
4s^{\prime}}+1\rfloor$. We have:

$\displaystyle\sum_{h=h_{0}+1}^{h_{\max}}(h+1)^{2}\exp(-h^{2})$
$\displaystyle=\sum_{h=h_{0}+1}^{h_{\max}}h^{2}\exp(-h^{2})+2\sum_{h=h_{0}+1}^{h_{\max}}h\exp(-h^{2})+\sum_{h=h_{0}+1}^{h_{\max}}\exp(-h^{2})$
$\displaystyle\leq\int_{h_{0}}^{\infty}h^{2}\exp(-h^{2})dh+2\int_{h_{0}}^{\infty}h\exp(-h^{2})dh+\int_{h_{0}}^{\infty}\exp(-h^{2})dh.$

Using an integration by parts, the inequality
$\int_{h_{0}}^{\infty}\exp(-h_{0}^{2})dh\leq\exp(-h_{0}^{2})/(h_{0}+\sqrt{h_{0}^{2}+4/\pi})\leq\exp(-h_{0}^{2})$,
and $h_{0}\geq 1$ from $s_{0}\geq 1$, we get:

$\displaystyle\int_{h_{0}}^{\infty}h^{2}\exp(-h^{2})dh$
$\displaystyle\leq\frac{1}{2}h_{0}\exp(-h_{0}^{2})+\frac{1}{2}\exp(-h_{0}^{2})$
$\displaystyle 2\int_{h_{0}}^{\infty}h\exp(-h^{2})dh$
$\displaystyle=\exp(-h_{0}^{2})$
$\displaystyle\int_{h_{0}}^{\infty}\exp(-h^{2})dh$
$\displaystyle\leq\exp(-h_{0}^{2}).$

Therefore,

$\displaystyle\sum_{h=h_{0}+1}^{h_{\max}}(h+1)^{2}\exp(-h^{2})$
$\displaystyle\leq\frac{1}{2}h_{0}\exp(-h_{0}^{2})+\frac{5}{2}\exp(-h_{0}^{2})$
$\displaystyle\leq h_{0}\exp(-h_{0}^{2})+5\exp(-h_{0}^{2}).$

We get:

$\displaystyle\sum_{h=0}^{h_{0}}(h+1)^{2}+\sum_{h=h_{0}+1}^{h_{\max}}4s^{\prime}(h+1)^{2}\exp\left(-h^{2}\right)$
$\displaystyle\leq\frac{(h_{0}+1)(h_{0}+2)(2h_{0}+3)}{6}+4s^{\prime}(h_{0}+5)\exp(-h_{0}^{2})$
$\displaystyle\leq\frac{2h_{0}^{3}+9h_{0}^{2}+13h_{0}+6}{6}+4s^{\prime}(h_{0}+5)\frac{1}{4s^{\prime}}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}11h_{0}^{3},$

where for $(a)$, we used $h_{0}\geq 1$. Finally, we get:

$\displaystyle r_{t}^{\pi}$ $\displaystyle\leq
44\delta^{2}s_{A}^{2}C_{\text{m}}(K-1)h_{0}^{3}+2(K-1)s_{A}s_{2}\left(\mathbb{P}(\mathcal{E}_{t}^{c})+\mathbb{P}\left(\left(\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)^{c}\middle|\mathcal{E}_{t}\right)\right)$
$\displaystyle\leq\frac{352\sigma^{2}s_{A}^{4}C_{\text{m}}(K-1)h_{0}^{3}\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)}{\alpha^{2}}\frac{1}{t-1}+2(K-1)s_{A}s_{2}\left(\mathbb{P}(\mathcal{E}_{t}^{c})+\mathbb{P}\left(\left(\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)^{c}\middle|\mathcal{E}_{t}\right)\right).$

This concludes the proof. $\Box$

###  B.6 Proof of Lemma 5

Let $r_{t}^{\pi}$ be the instantaneous expected regret of algorithm $\pi$ in
round $t$ defined as:

$\displaystyle
r_{t}^{\pi}\coloneqq\operatorname{\mathbb{E}}\left[\max_{A\in\mathcal{A}_{t}}\langle
A-A_{t},\theta\rangle\right].$

Let us define the events
$\mathcal{R}_{k}\coloneqq\\{\mathcal{A}_{t}\in\mathbb{R}^{K\times
d}:k\in\mathop{\rm argmax}\limits_{k^{\prime}}\langle
A_{t,k^{\prime}},\theta\rangle\\}$ and
$\mathcal{G}_{t}^{\lambda}\coloneqq\left\\{\lambda_{\min}(\hat{\Sigma}_{\hat{S}})\geq\lambda\right\\}$.
As in the proof of Lemma 4, we get:

$\displaystyle r_{t}^{\pi}$
$\displaystyle\leq\sum_{k=1}^{K}\operatorname{\mathbb{E}}\left[r_{t}^{\pi}\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\right]\mathbb{P}\left(\mathcal{A}_{t}\in\mathcal{R}_{k}\right),$

and

$\displaystyle\operatorname{\mathbb{E}}\left[r_{t}^{\pi}\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\right]$
$\displaystyle=\operatorname{\mathbb{E}}\left[\langle
A_{t,k}-A_{t},\theta\rangle\mid\mathcal{A}_{t}\in\mathcal{R}_{k}\right]$
$\displaystyle\leq\sum_{\ell\neq
k}\operatorname{\mathbb{E}}\left[\mathds{1}\left\\{\langle
A_{t,\ell},\hat{\theta}_{t}\rangle\geq\langle
A_{t,k},\hat{\theta}_{t}\rangle\right\\}\langle
A_{t,k}-A_{t,\ell},\theta\rangle\mid\mathcal{A}_{t}\in\mathcal{R}_{k},\
\mathcal{E}_{t},\ \mathcal{G}_{t}^{\frac{\alpha}{2}}\right]$ $\displaystyle\ \
\
+2(K-1)s_{A}s_{2}\left(\mathbb{P}(\mathcal{E}_{t}^{c})+\mathbb{P}\left(\left(\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)^{c}\middle|\mathcal{E}_{t}\right)\right).$

Let us denote $r_{k,\ell}\coloneqq\langle A_{t,k}-A_{t,\ell},\theta\rangle$.
For each $x>0$, we get:

$\displaystyle\operatorname{\mathbb{E}}\left[\mathds{1}\left\\{\langle
A_{t,\ell},\hat{\theta}_{t}\rangle\geq\langle
A_{t,k},\hat{\theta}_{t}\rangle\right\\}\langle
A_{t,k}-A_{t,\ell},\theta\rangle\mid\mathcal{A}_{t}\in\mathcal{R}_{k},\
\mathcal{E}_{t},\ \mathcal{G}_{t}^{\frac{\alpha}{2}}\right]$
$\displaystyle=\operatorname{\mathbb{E}}\left[\mathds{1}\left\\{\langle
A_{t,k},\theta-\hat{\theta}\rangle-\langle
A_{t,\ell},\theta-\hat{\theta}\rangle\geq
r_{k,\ell}\right\\}r_{k,\ell}\mid\mathcal{A}_{t}\in\mathcal{R}_{k},\
\mathcal{E}_{t},\ \mathcal{G}_{t}^{\frac{\alpha}{2}}\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}\left[\mathds{1}\left\\{\|A_{t,k}\|_{2}\|\theta-\hat{\theta}\|_{2}+\|A_{t,\ell}\|_{2}\|\theta-\hat{\theta}\|_{2}\geq
r_{k,\ell}\right\\}r_{k,\ell}\mid\mathcal{A}_{t}\in\mathcal{R}_{k},\
\mathcal{E}_{t},\ \mathcal{G}_{t}^{\frac{\alpha}{2}}\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}\left[\mathds{1}\left\\{2s_{A}\|\theta-\hat{\theta}\|_{2}\geq
r_{k,\ell}\right\\}r_{k,\ell}\mid\mathcal{A}_{t}\in\mathcal{R}_{k},\
\mathcal{E}_{t},\ \mathcal{G}_{t}^{\frac{\alpha}{2}}\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}\left[\mathds{1}\left\\{2s_{A}\|\theta-\hat{\theta}\|_{2}\geq
r_{k,\ell}\right\\}r_{k,\ell}\mid\mathcal{A}_{t}\in\mathcal{R}_{k},\
\mathcal{E}_{t},\
\mathcal{G}_{t}^{\frac{\alpha}{2}},\|\theta-\hat{\theta}\|_{2}\leq
x\right]+2s_{A}s_{2}\mathbb{P}\left(\|\theta-\hat{\theta}\|_{2}\geq
x\mid\mathcal{A}_{t}\in\mathcal{R}_{k},\ \mathcal{E}_{t},\
\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)$ $\displaystyle\leq
2s_{A}x+2s_{A}s_{2}\mathbb{P}\left(\|\theta-\hat{\theta}\|_{2}\geq
x\mid\mathcal{A}_{t}\in\mathcal{R}_{k},\ \mathcal{E}_{t},\
\mathcal{G}_{t}^{\frac{\alpha}{2}}\right).$

Using Lemma 3, we get:

$\displaystyle\mathbb{P}\left(\|\theta-\hat{\theta}\|_{2}\geq\frac{4\sigma
s_{A}\sqrt{s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}}}{\alpha}\sqrt{\frac{\log
t}{t}}\mid\mathcal{A}_{t}\in\mathcal{R}_{k},\ \mathcal{E}_{t},\
\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)\leq
2\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)\frac{1}{t^{2}}.$

Therefore, we have:

$\displaystyle r_{t}^{\pi}$ $\displaystyle\leq
8s_{A}^{2}(K-1)\frac{\sigma\sqrt{s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}}}{\alpha}\sqrt{\frac{\log
t}{t}}$ $\displaystyle\ \ \
+4(K-1)s_{A}s_{2}\left(s_{0}+\frac{2\sqrt{s_{0}}}{\phi_{0}^{2}}\right)\frac{1}{t^{2}}+2(K-1)s_{A}s_{2}\left(\mathbb{P}(\mathcal{E}_{t}^{c})+\mathbb{P}\left(\left(\mathcal{G}_{t}^{\frac{\alpha}{2}}\right)^{c}\middle|\mathcal{E}_{t}\right)\right).$

This concludes the proof. $\Box$

##  Appendix C Additional Experimental Results

###  C.1 Additional Results for Two-Armed Bandits

Figures 5, 6, and 7 show the numerical results with correlation levels between
two arms $\rho^{2}\in\\{0.0,0.3,0.7\\}$, respectively. We find that the TH
LASSO bandit exhibits lower regret than SA LASSO bandit and DR LASSO bandit in
all scenarios.

Figure 5: Cumulative regret of the three algorithms with $\rho^{2}=0.0$,
$s_{A}=10$, $K\in\\{2,50\\}$, $d\in\\{1000,2000\\}$, and $s_{0}\in\\{5,20\\}$.
The shaded area represents the standard errors.

Figure 6: Cumulative regret of the three algorithms with $\rho^{2}=0.3$,
$s_{A}=10$, $K\in\\{2,50\\}$, $d\in\\{1000,2000\\}$, and $s_{0}\in\\{5,20\\}$.
The shaded area represents the standard errors.

Figure 7: Cumulative regret of the three algorithms with $\rho^{2}=0.7$,
$s_{A}=10$, $K\in\\{2,50\\}$, $d\in\\{1000,2000\\}$, and $s_{0}\in\\{5,20\\}$.
The shaded area represents the standard errors.

###  C.2 Additional Results for K-Armed Bandits

We also present the experimental results with varying
$s_{A}\in\\{2.5,5,10,20,40,\infty\\}$ and a different parameter setting. We
set $K=50,d=1000$, and $s_{0}=20$. Figure 8 shows the average cumulative
regret at $t=1000$ of TH LASSO bandit and SA LASSO bandit for each $s_{A}$. We
observe that TH LASSO bandit outperforms SA LASSO bandit for all $s_{A}$.

Figure 8: Cumulative regret at round $t=1000$ of TH LASSO bandit and SA LASSO
bandit with $\rho^{2}=0.7$, $K=50$, $d=1000$, $s_{0}=20$, and varying
$s_{A}\in\\{2.5,5,10,20,40,\infty\\}$. The error bars represent the standard
errors.