Matrix Sketching in Bandits: Current Pitfalls and New Framework

## Abstract

Abstract The utilization of sketching techniques has progressively emerged as a pivotal method for enhancing the efficiency of online learning.
In linear bandit settings, current sketch-based approaches leverage matrix sketching to reduce the per-round time complexity from Ω ⁢ ( d 2 ) Ω superscript 𝑑 2 \Omega\left(d^{2}\right) roman_Ω ( italic_d start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ) to O ⁢ ( d ) 𝑂 𝑑 O(d) italic_O ( italic_d ) , where d 𝑑 d italic_d is the input dimension. Despite this improved efficiency, these approaches encounter critical pitfalls: if the spectral tail of the covariance matrix does not decrease rapidly, it can lead to linear regret .
In this paper, we revisit the regret analysis and algorithm design concerning approximating the covariance matrix using matrix sketching in linear bandits.
We illustrate how inappropriate sketch sizes can result in unbounded spectral loss, thereby causing linear regret.
To prevent this issue, we propose Dyadic Block Sketching, an innovative streaming matrix sketching approach that adaptively manages sketch size to constrain global spectral loss.
This approach effectively tracks the best rank- k 𝑘 k italic_k approximation in an online manner, ensuring efficiency when the geometry of the covariance matrix is favorable.
Then, we apply the proposed Dyadic Block Sketching to linear bandits and demonstrate that the resulting bandit algorithm can achieve sublinear regret without prior knowledge of the covariance matrix, even under the worst case.
Our method is a general framework for efficient sketch-based linear bandits, applicable to all existing sketch-based approaches, and offers improved regret bounds accordingly.
Additionally, we conduct comprehensive empirical studies using both synthetic and real-world data to validate the accuracy of our theoretical findings and to highlight the effectiveness of our algorithm.

## 1 Introduction

The Multi-Armed Bandits (MAB) model represents a framework for sequential decision-making under conditions of partial information (Robbins, ).
In each round, the player selects one of the $K$ arms to maximize cumulative rewards. The player’s strategy, which guides action choices based on previous observations, is referred to as a policy.
The player’s objective is to develop a policy that minimizes regret, which is defined as the difference between the total reward of the optimal policy and that of the chosen policy.

We consider the Stochastic Linear Bandit (SLB) model, a variant of the MAB model under a linear assumption (Abbasi-Yadkori et al., ; Auer, ; Chu et al., ; Dani et al., ).
In SLB, at round $t$, the player selects a arm $\bm{x}_{t}$ from an alternate set $\mathcal{X}$, and then observes the reward $r_{t}$. The expected reward $E[r_{t}|\bm{x}_{t}]=\bm{x}_{t}^{\top}\bm{\theta}_{\star}$, where $\bm{\theta}_{\star}$ represents unknown coefficients. The player’s objective is to minimize the regret over the total $T$ rounds, defined as:

$$ $\text{Regret}_{T}=\sum_{t=1}^{T}\max_{\bm{x}\in\mathcal{X}}\bm{x}^{\top}\bm{ \theta}_{\star}-\sum_{t=1}^{T}\bm{x}_{t}^{\top}\bm{\theta}_{\star}.$ (1) $$

Utilizing upper confidence bounds and the regularized least squares estimator, Abbasi-Yadkori et al. () introduced the well-known OFUL algorithm, which achieves a regret of $\tilde{O}(d\sqrt{T})$ and exhibits a computational complexity of $\Omega(d^{2})$, where $d$ represents the dimension of the data.
However, in real-world decision-making problems, the data dimension $d$ often increases rapidly, making traditional bandit algorithms excessively time-consuming (Calandriello et al., ; Xu et al., ; Deshpande & Montanari, ; Zhang et al., ).
To address this issue and eliminate the quadratic dependence on $d$, various approaches have adopted streaming sketching methods to enhance efficiency.
Yu et al. () employ random projection to map high-dimensional arms to a low-dimensional subspace.
Another line of these works is based on a well-known deterministic sketching algorithm—Frequent Directions (FD), which has been proven to offer better theoretical guarantees than random projection under the streaming setting (Liberty, ; Woodruff et al., ; Ghashami et al., ).
Kuzborskij et al. () directly use FD to sketch covariance matrices of linear bandits, successfully reducing time complexity from $\Omega(d^{2})$ to $O(dl+l^{2})$ while achieving an upper regret bound of $\tilde{O}\left((1+\Delta_{T})^{\frac{3}{2}}(l+d\log(1+\Delta_{T}))\sqrt{T}\right)$, where $l<d$ is the sketch size and $\Delta_{T}$ represents the spectral error caused by the shrinking of FD.
Building on this foundation,  Chen et al. () introduce Robust Frequent Directions (RFD) to reduce the order of $\Delta_{T}$ and decouple $d$ and $\Delta_{T}$, achieving an improved regret bound of $\tilde{O}\left((\sqrt{l+d\log(1+\Delta_{T})}+\sqrt{\Delta_{T}})\sqrt{lT}\right)$.

Despite recent advancements, matrix sketching in linear bandits still faces several pitfalls in practical applications (Kuzborskij et al., ; Chen et al., ; Calandriello et al., ).
Upon careful examination of the previous regret bounds, the $\sqrt{T}$ term is associated with a spectral error $\Delta_{T}$, which arises from the discrepancy between the sketched and non-sketched regularized least squares estimators.
The magnitude of the spectral error $\Delta_{T}$ relates to the fixed sketch size $l$ and the spectral tail of the covariance matrix, implying that a slow decrease in this tail can contribute to linear regret.
In practice, this is evident as an inappropriate sketch size can significantly hinder the performance of online learning algorithms.
Since the spectral information of the covariance matrix is unknown prior to online learning, selecting an optimal pre-set, fixed sketch size is challenging.
This raises a natural question: Can we adaptively adjust the sketch size in an online manner to avoid the pitfall of linear regret in current methods?

In this paper, we demonstrate that the answer is "yes" by developing a novel framework for efficient sketch-based linear bandit algorithms.
Specifically, this work makes three key contributions:
$\bullet$
We revisit the fundamental problem of approximating the covariance matrix through matrix sketching.
We analyze the critical condition for linear regret in sketch-based methods, which depends on unpredictable properties of the streaming matrix.
From both theoretical and experimental perspectives, we demonstrate that the inability of previous methods to avoid the pitfall of linear regret stems from the difficulty of pre-setting an appropriate fixed sketch size.
$\bullet$
We propose Dyadic Block Sketching, a multi-scale matrix sketching method that imposes a constraint on the global spectral error by managing the error bound within each block.
We prove that the cumulative spectral error upper bound from Dyadic Block Sketching conforms to a specified error $\epsilon$.
This approach allows the sketch size to be dynamically adjusted to accommodate the given error, even without prior knowledge of the matrix structure.
Additionally, we demonstrate that Dyadic Block Sketching effectively tracks the best rank-$k$ approximation in the streaming setting, aligning with the performance of a single deterministic sketch.
$\bullet$
We introduce an efficient framework for sketch-based linear bandits using Dyadic Block Sketching, effectively addressing the pitfall of linear regret in previous works.
Our framework is robust, scalable, and capable of achieving various regret bounds through different sketching techniques.
By tracking the best rank-$k$ approximation, our method can significantly reduce the computational cost of linear bandits when the covariance matrix has favorable properties.

#### Related Work.

Two classes of prior work are particularly relevant to our study: matrix sketching algorithms in the unbounded streaming model and sketch-based online learning algorithms.
Streaming matrix sketching methods can be broadly categorized into three groups:
The first approach is sampling a small subset of matrix rows or columns that approximates the entire matrix (Deshpande & Rademacher, ; Frieze et al., ).
The second approach is randomly combining matrix rows via random projection.
Several results are available in the literature, including random projections and hashing (Sarlos, ; Achlioptas, ).
The third approach employs a deterministic matrix sketching technique proposed by Liberty (), which adapts the well-known MG algorithm from Misra & Gries () (originally used for approximating item frequencies) to sketch a streaming matrix by tracking its frequent directions.
For further details, we refer readers to the survey by Woodruff et al. ().
In sketch-based online learning algorithms, most existing work aims to enhance efficiency through sketching.
Beyond linear bandits setting, matrix sketching is also employed to accelerate second-order online gradient descent (Luo et al., ), online kernel learning (Calandriello et al., ; Luo et al., ), stochastic optimization (Gonen et al., ), and contextual batched bandits (Zhang et al., ).

#### Organization.

The remainder of this paper is structured as follows: Section 2 revisits matrix sketching methods in linear bandits and highlights the current pitfalls.
Section 3 presents a novel multi-scale sketching method for achieving a constrained global error bound.
Section 4 introduces a new framework for efficient sketch-based linear bandits.
Section 5 provides a detailed report of the experimental results. Finally, Section 6 concludes the paper and offers a discussion.
All proofs and additional algorithmic details are provided in the appendices.

## 2 Revisiting Matrix Sketching in Linear Bandits

#### Notations.

Let $[n]=\{1,2,\ldots,n\}$, upper-case bold letters (e.g., $\bm{A}$) represent matrix and lower-case bold letters (e.g., $\bm{a}$) represent vectors.
We denote by $\bm{\|A\|}_{2}$ and $\bm{\|A\|}_{F}$ the spectral and Frobenius norms of $\bm{A}$.
We define $\left|\bm{A}\right|$ and $\text{Tr}(\bm{A})$ as the determinant and trace of matrix $\bm{A}$.
For a positive semi-definite matrix $\bm{A}$, the matrix norm of vector $\bm{x}$ is defined by $\|\bm{x}\|_{\bm{A}}=\sqrt{\bm{x}^{\top}\bm{A}\bm{x}}$.
For two positive semi-definite matrices $\bm{A}$ and $\bm{B}$, we use $\bm{A}\succeq\bm{B}$ to represent the fact that $\bm{A}-\bm{B}$ is positive semi-definite.
We use $\bm{A=U\Sigma{V^{\top}}}$ to represent the SVD of $\bm{A}$, where $\bm{U},\bm{V}$ denote the left and right matrices of singular vectors and $\bm{\Sigma}=\text{diag}[\sigma_{1},...,\sigma_{n}]$ is the diagonal matrix of singular values in the descending order.
We define $\bm{A}_{[k]}=\bm{U}_{k}\bm{\Sigma}_{k}\bm{V}_{k}^{\top}$ for $k\leq\text{rank}(\bm{A})$ as the best rank-$k$ approximation to $\bm{A}$, where $\bm{U}_{k}\in\mathbb{R}^{n\times k}$ and $\bm{V}_{k}\in\mathbb{R}^{d\times k}$ are the first $k$ columns of $\bm{U}$ and $\bm{V}$.

### 2.1 Linear Bandits through Matrix Sketching

Within the linear bandit setting, the reward for choosing action $\bm{x}_{t}$ is defined as $r_{t}=\bm{x}_{t}^{\top}\bm{\theta}_{\star}+z_{t}$, where $\bm{\theta}_{\star}$ is a fixed, unknown vector of real coefficients, and $z_{t}$ denotes a zero-mean random variable. Traditional linear bandit algorithms utilize regularized least squares (RLS) to estimate the unknown weight $\bm{\theta}_{\star}$ as

$$ $\bm{A}^{(t)}=\lambda\bm{I}_{d}+\left(\bm{X}^{(t)}\right)^{\top}\bm{X}^{(t)} \quad and\quad\hat{\bm{\theta}}_{t}=\left({\bm{A}}^{(t)}\right)^{-1}\sum_{s=1} ^{t}r_{s}\bm{x}_{s},$ (2) $$

where $\left(\bm{X}^{(t)}\right)^{\top}=\left[\bm{x}_{1}^{\top},...,\bm{x}_{t}^{\top}\right]$ is the $d\times t$ matrix containing all the arms selected up to round $t$ and $\lambda$ is the regularization parameter.

Sketch-based linear bandit methods create a smaller matrix (termed sketch matrix) $\bm{S}^{(t)}\in\mathbb{R}^{l\times d}$ as an approximation to $\bm{X}^{(t)}$, where $l$ is the sketch size.
Take FD as an example, and we can formulate this sketching operation as

$$ $\bm{S}^{(t)}=\sqrt{\left(\bm{\Sigma}^{(t-1)}_{l}\right)^{2}-\left(\sigma_{l}^{ (t-1)}\right)^{2}\bm{I}_{l}}\cdot\left(\bm{V}_{l}^{(t-1)}\right)^{\top},\quad \bm{M}^{(t)}=\left(\bm{S}^{(t)}\left(\bm{S}^{(t)}\right)^{\top}+\lambda\bm{I}_ {l}\right)^{-1},$ (3) $$

where $\bm{\Sigma}^{(t-1)}_{l}$, $\bm{V}_{l}^{(t-1)}$ are the result of rank-$l$ SVD on round $t-1$ and $\bm{M}^{(t)}$ is a diagonal matrix which can be stored efficiently.
According to Woodbury’s identity, we can rewrite the inverse of the sketched covariance matrix as

$$ $\left(\hat{\bm{A}}^{(t)}\right)^{-1}=\left(\lambda\bm{I}_{d}+\left(\bm{S}^{(t) }\right)^{\top}\bm{S}^{(t)}\right)^{-1}=\frac{1}{\lambda}\left(\bm{I}_{d}- \left(\bm{S}^{(t)}\right)^{\top}\bm{M}^{(t)}\bm{S}^{(t)}\right).$ (4) $$

The computation in equation 2 requires $\Omega\left(d^{2}\right)$ time. To improve efficiency, sketch-based methods replace $\left({\bm{A}}^{(t)}\right)^{-1}$ with $\left(\hat{\bm{A}}^{(t)}\right)^{-1}$. Notably, $\left(\hat{\bm{A}}^{(t)}\right)^{-1}$ can be updated implicitly using the sketch matrix $\bm{S}^{(t)}$ and $\bm{M}^{(t)}$ in equation 4.
Since matrix-vector multiplications with $\bm{S}^{(t)}$ take $O(ld)$ time and matrix-matrix multiplications with $\bm{M}^{(t)}$ take $O\left(l^{2}\right)$ time, the computation involving the inverse of the sketched covariance matrix is accelerated from $\Omega\left(d^{2}\right)$ to $O\left(ld+l^{2}\right)$.

### 2.2 The Motivation of Revisiting

Without loss of generality, our analysis below is based on the original FD.
To better illustrate our motivation, we first present the complete regret bound for the linear bandit using FD (Kuzborskij et al., ).

Let $\overline{\sigma}=\sum_{t=1}^{T}\left(\sigma_{l}^{(t)}\right)^{2}$ denote the sum of singular values reduced by FD up to the $T$-th round, where $l$ is the sketch size and $\left(\sigma_{l}^{(t)}\right)^{2}$ is the shrinking value at round $t$.
According to Liberty (), it can be bounded by the *spectral error* $\Delta_{T}$, i.e., $\overline{\sigma}\leq\Delta_{T}$, where

$$ $\Delta_{T}:=\min_{k<l}\frac{\left\|\bm{X}^{(T)}-\bm{X}^{(T)}_{[k]}\right\|_{F} ^{2}}{l-k}.$ (5) $$

Consequently, the regret of the sketch-based linear bandit can be formulated as

$$ $\text{Regret}_{T}=\tilde{O}\left((1+\Delta_{T})^{\frac{3}{2}}(l+d\log(1+\Delta _{T}))\sqrt{T}\right).$ (6) $$

Denote $k_{\star}$ as the minimizer of equation 5.
Ignoring logarithmic terms, we assume $\Delta_{T}=T^{\gamma}$.
When $\gamma>\frac{1}{3}$, the regret will exceed $O(T)$.
More precisely, when the spectral tail $\left\|\bm{X}^{(T)}-\bm{X}^{(T)}_{[k_{\star}]}\right\|_{F}^{2}=\Omega\left((l-
k_{\star})^{\frac{2}{3}}T^{\frac{1}{3}}\right)$, the invalid linear regret will emerge.

The above analysis highlights a key pitfall of sketch-based linear bandits: the pre-set sketch size is crucial.
Next, we will explain, from both theoretical and experimental perspectives, why this pitfall is widespread and difficult to avoid in current methods.
We present the following theorem to show that the spectral tail of the covariance matrix does not decrease rapidly, even in a non-adversarial setting.

###### Theorem 1 .

Suppose the chosen arm $\bm{x}_{t}\in\mathbb{R}^{d}$ at round $t$ is a random vector drawn iid from any distribution over $r\leq d$ orthonormal vectors $\bm{A}$.
For any sketch size $l\leq r$, the bound on the expected regret of linear bandits using FD is $\Omega\left(T^{2}\right)$.

Figure: Figure 1: Regret of SOFUL, OFUL, and our method on synthetic data (details in section 5.2) The regret of SOFUL is nearly linear when sketch size $l=300$.
Refer to caption: x1.png

The detailed proof is provided in Appendix A.
Theorem 1 shows that when the sketch size is insufficient to capture most of the spectral information, sketch-based linear bandit methods will suffer from linear regret.
Furthermore, as illustrated in Figure 1, we observe that an incorrect selection of the pre-set sketch size can significantly degrade performance.

Current methods use the single-scale sketching technique to approximate the covariance matrix.
However, since the covariance matrix is determined in an online manner, its spectral information is unknown beforehand.
Even if poor performance is detected during learning, adjusting the sketch size is not possible because the shrinking process in single-scale sketching is irreversible.
Consequently, the pitfall of linear regret is difficult to avoid in previous works.

###### Theorem 1 .

## 3 Dyadic Block Sketching for Constrained Global Error Bound

In this section, we propose a multi-scale sketching method called Dyadic Block Sketching, which provides a constrained global error bound for matrix sketching.
This scalable method converts any streaming sketch into a matrix sketch with a constrained global error bound.
It can adaptively adjust the sketch size in a streaming environment, tracking the best rank-$k$ approximation of the target matrix at a minimal cost.
We employ the Frequent Directions sketch to illustrate this method.

### 3.1 Decomposability

Dyadic Block Sketching leverages the decomposability of streaming matrix sketches.
Intuitively, decomposability means that if the rows of a matrix are divided into submatrices, sketches can be constructed for each submatrix, and these sketches can then be combined to form a sketch of the original matrix.
In this process, the error of approximating the original matrix is the sum of the errors of approximating each submatrix.
The following lemma demonstrates that all matrix sketches offering a covariance error guarantee exhibit decomposability.

###### Lemma 1 (Decomposability) .

Given a matrix $\bm{X}\in\mathbb{R}^{n\times d}$, we decompose $\bm{X}$ into $p$ submatrices, i.e., $\bm{X}^{\top}=\left[\bm{X}_{1}^{\top},\bm{X}_{2}^{\top},...,\bm{X}_{p}^{\top}\right]$.
For any $i\in[p]$, if we construct a matrix sketch with covariance error guarantee $\epsilon_{i}$ for each sub-matrix $\bm{X}_{i}$, denoted as $\bm{S}_{i}$, such that $\left\|\bm{X}_{i}^{\top}\bm{X}_{i}-\bm{S}_{i}^{\top}\bm{S}_{i}\right\|_{2}\leq
\epsilon_{i}\cdot\left\|\bm{X}_{i}-{\bm{X}_{i}}_{[k]}\right\|_{F}^{2}$.
Then $\bm{S}^{\top}=\left[\bm{S}_{1}^{\top},\bm{S}_{2}^{\top},...,\bm{S}_{p}^{\top}\right]$ is an approximation of $\bm{X}^{\top}$ and the error bound is

$$ $\left\|\bm{X}^{\top}\bm{X}-\bm{S}^{\top}\bm{S}\right\|_{2}\leq\sum_{i=1}^{p} \epsilon_{i}\cdot\left\|\bm{X}_{i}-{\bm{X}_{i}}_{[k]}\right\|_{F}^{2}.$ $$

###### Proof.

Since we have $\bm{X}^{\top}\bm{X}=\sum_{i=1}^{p}\bm{X}_{i}^{\top}\bm{X}_{i}$ and $\bm{S}^{\top}\bm{S}=\sum_{i=1}^{p}\bm{S}_{i}^{\top}\bm{S}_{i}$.
Therefore

$$ $\left\|\bm{X}^{\top}\bm{X}-\bm{S}^{\top}\bm{S}\right\|_{2}\leq\sum_{i=1}^{p} \left\|\bm{X}_{i}^{\top}\bm{X}_{i}-\bm{S}_{i}^{\top}\bm{S}_{i}\right\|_{2}\leq \sum_{i=1}^{p}\epsilon_{i}\cdot\left\|\bm{X}_{i}-{\bm{X}_{i}}_{[k]}\right\|_{F }^{2},$ $$

and the Lemma follows.
∎

###### Lemma 1 (Decomposability) .

###### Proof.

### 3.2 Algorithm Descriptions

#### High-Level Ideas.

The high-level idea is illustrated in Figure 2.
We establish a logarithmic number of sketch sizes, each partitioning the stream into blocks.
The sketch size of each subsequent block is double that of the previous one, thereby halving the maximum error caused by sketching.
By maintaining a streaming sketch for each block, we can concatenate all the sketches to approximate the streaming matrix, with the error bounded by the decomposability property.

Figure: Figure 2: An illustration for Dyadic Block Sketching. For inactive Block $i\in[B-1]$, the matrix sketch covers the data from $t_{i-1}$ to $t_{i}$. For the active Block $B$, matrix sketching updates are performed on the new rows. We then merge the multi-scale matrix sketches to approximate the entire stream.
Refer to caption: x2.png

#### Algorithm.

We start by defining the data structure for our algorithm.
The matrix rows in the stream are divided into blocks, each covering a segment of consecutive, non-overlapping rows.
The list of blocks is denoted as $\bm{\mathcal{B}}$.
For $i=1,2,\ldots$, each block $\bm{\mathcal{B}}[i]$ is associated with a streaming sketch of size $l$ (length) and block size (size).
The size of block $\bm{\mathcal{B}}[i]$ is defined as the sum of the squared norms of the rows covered by $\bm{\mathcal{B}}[i]$, specifically, $\bm{\mathcal{B}}[i].size=\sum_{\bm{x}\in\bm{\mathcal{B}}[i]}\|\bm{x}\|_{2}^{2}$.

We further define two states for the blocks: active and inactive.
An active block receives updates, while an inactive block remains entirely fixed.
As illustrated in Figure 2, there is always exactly one active block in the stream. Additionally, three key invariants must be maintained:

- 1.
For each inactive block, the length must be greater than the rank of the rows it contains.
- 2.
The sum of sketch rows stored in blocks should be less than $d$.
- 3.
The size of block $\bm{\mathcal{B}}[i]$ should less than $l_{0}\epsilon$, where $l_{0}$ represents the initial sketch size and $\epsilon$ is the error parameter.

Algorithm 1 presents the pseudo-code of Dyadic Block Sketching.
When a new row $\bm{x}_{t}$ is received, we first verify the maintenance of Invariant 2 (see Line 1). If the block count reaches its upper limit, the error from the streaming sketch becomes intolerable, necessitating the full preservation of the streaming rows’ information. Therefore, we execute a complete rank-1 update on the sketch matrix.

Figure: Algorithm 1 Dyadic Block Sketching

In Lines 1 – 1, we control the errors to ensure the maintenance of Invariant 3. If the size of the active block exceeds the specified limit, we store the current block’s information and create a new block with double the previous length to prevent further errors.

In Lines 1 – 1, we update the active block’s information with $\bm{x}_{t}$.
During this process, we can query the sketch matrices $\bm{S}_{B}$ and $\bm{M}_{B}$ in the active block (details in Appendix D).
Additionally, the shrinkage of the deterministic sketch provides us with the block’s current rank if the sketch size exceeds the block’s rank.
We use the variable $rank$ to track this value.
If the shrinking value is non-zero, we set $rank$ to $\bm{\mathcal{B}}[B].{length}$; otherwise, we assign $rank$ to the block’s rank.

In Lines 1 – 1, we query the sketch of the entire stream.
To retrieve the sketch matrix $\bm{S}^{(t)}$ and $\bm{M}^{(t)}$, we combine them with the previous matrices as follows

$$ $\bm{S}^{(t)}=\begin{pmatrix}\bm{S}^{(t)}\\ \bm{S}_{i}\end{pmatrix}\quad,\quad\bm{M}^{(t)}=\left(\begin{pmatrix}\bm{M}^{(t )}&\bm{S}^{(t)}{(\bm{S}_{i})}^{\top}\\ \bm{S}_{i}(\bm{S}^{(t)})^{\top}&\bm{M}_{i}\end{pmatrix}+\lambda\bm{I}\right)^{ -1}.$ (7) $$

Since the inactive blocks remain fixed, we can store the combined result of the sketch matrix in the inactive blocks. In practice, we can avoid the looped calculation of equation 7 and perform the combination only with the active block.

### 3.3 Analysis

We explore the error guarantees along with the space and time complexities of the Dyadic Block Sketching method.
Initially, we prove a general theorem that establishes the relationship between the complexities of the Dyadic Block Sketching algorithm and the streaming sketch utilized in each block.
Subsequently, we examine how a specific deterministic streaming sketch can be integrated into the Dyadic Block Sketching framework.
We present a theorem detailing the space usage and update costs associated with Dyadic Block Sketching.
The detailed proof is provided in Appendix B.

###### Theorem 2 .

Suppose a streaming matrix sketch, denoted as $\kappa$, achieves a covariance error $\left\|\bm{X}^{\top}\bm{X}-\bm{S}^{\top}\bm{S}\right\|_{2}\leq\eta\cdot\left\|
\bm{X}\right\|_{F}^{2}$ with $\ell_{\eta}$ rows and $\mu_{\eta}$ update time.
Applying $\kappa$ as the sketching method for each block in the Dyadic Block Sketching and $l_{0}$ is the initial sketch size, we generate a matrix sketch $\bm{S}$ for the entire streaming matrix $\bm{X}$ with an error guarantee $\left\|\bm{X}^{\top}\bm{X}-\bm{S}^{\top}\bm{S}\right\|_{2}\leq 2\epsilon$.
Assuming $\mathrm{rank}(\bm{X})=k$ and that the rows are normalized, the space cost for Dyadic Block Sketching is $O\left(d\cdot\sum_{i=0}^{B}\ell_{\frac{1}{2^{i}l_{0}}}\right)$, and the update cost is $O\left(\mu_{\frac{1}{2^{B}l_{0}}}\right)$, where $B=\left\lceil\min\left\{\log\frac{k}{l_{0}},\frac{T}{\epsilon l_{0}}\right\}
\right\rceil+1$.

Note that different streaming sketches will result in varying costs.
To illustrate this, we provide a corollary using the well-known deterministic sketching method Frequent Directions (FD).

###### Theorem 2 .

#### Dyadic Block Sketching for FD.

This algorithm employs the FD sketch for each block in the Dyadic Block Sketching framework.
Recall that with a given error parameter $\eta$, the FD sketch requires a space of $\ell_{\eta}=O(1/\eta)$ and processes updates at an amortized cost of $\mu_{\eta}=O(d/\eta)$.
As outlined in Theorem 2, we derive the following corollary:

###### Corollary 1 .

The Dyadic Block Sketching algorithm for FD uses $O\left(2dk-dl_{0}\right)$ space and processes an update with $O(dk)$ amortized cost.

###### Remark 1 (Efficient Implementation) .

The primary computational costs of the algorithm include calculating the SVD to obtain $\bm{S}^{(t)}$ and performing matrix multiplication to compute $\bm{M}^{(t)}$, both of which cost $O(dl^{2})$, where $l$ is the current sketch size.
However, the amortized update cost can be effectively reduced from $O(dl^{2})$ to $O(dl)$ either by doubling the space, as detailed in Algorithm 3 in Appendix C, or by employing the Gu-Eisenstat procedure (Gu & Eisenstat, ).

###### Remark 2 (Worst-Case Analysis) .

Compared to the single streaming sketch algorithm, our method effectively controls the global error of matrix approximation by limiting error sizes within each block, thus enabling dynamic adjustment of the sketch size.
Particularly when dealing with a full-rank matrix with a heavy spectral tail, sketching methods should be avoided to prevent the pitfall of linear regret.
However, this control is impossible with a single sketch due to the irreversible nature of the shrinking process in sketching.
In the worst-case scenario, our method ensures that the streaming matrix problem can be dynamically adjusted to revert to a non-sketch situation.

###### Corollary 1 .

###### Remark 1 (Efficient Implementation) .

###### Remark 2 (Worst-Case Analysis) .

## 4 Linear Bandits through Dyadic Block Sketching

In this section, we introduce a novel framework for efficient sketch-based linear bandits, termed DBSLinUCB, which leverages Dyadic Block Sketching.
As outlined in Section 2.2, a key limitation of previous methods stems from their reliance on single-scale matrix sketching, resulting in a space-bounded linear bandit approach.
The use of a fixed sketch size leads to uncontrollable spectral loss, $\Delta_{T}$, ultimately causing linear regret.

In contrast, Dyadic Block Sketching employs a multi-scale matrix sketching strategy, where the sketch size is adaptively adjusted based on the pre-set parameter $\epsilon$.
Consequently, DBSLinUCB is an error-bounded linear bandit method that effectively addresses and overcomes the pitfalls of linear regret present in existing approaches.

Figure: Algorithm 2 DBSLinUCB

The procedure, detailed in Algorithm 2, builds on prior sketch-based algorithms but incorporates the Dyadic Block Sketching method to effectively manage the error in approximating the covariance matrix.
At each round $t$, we employ the sketch matrix $\bm{S}^{(t)}$ to approximate the covariance matrix, from which we derive the sketched regularized least squares estimator as follows

$$ $\hat{\bm{A}}^{(t)}={\bm{S}^{(t)}}^{\top}\bm{S}^{(t)}+\lambda\bm{I}\quad,\quad \hat{\bm{\theta}}_{t}=\left(\hat{\bm{A}}^{(t)}\right)^{-1}\sum_{s=1}^{t}r_{s} \bm{x}_{s}.$ (8) $$

Denote $\mathcal{X}_{t}$ as the set of arms available at round $t$ and $\hat{\beta}_{t-1}(\delta)$ as the confidence ellipsoid, $l_{B_{t}}$ as the sketch size in the active block.
The arms selected by DBSLinUCB are determined by solving the following constrained optimization problem:

$$ $\bm{x}_{t}=\underset{\bm{x}\in\mathcal{X}_{t}}{\arg\max}\max_{\bm{\theta}\in \mathbb{R}^{d}}\bm{x}^{\top}\bm{\theta}\quad\text{such that}\quad\left\|\bm{ \theta}-\hat{\bm{\theta}}\right\|_{\hat{\bm{A}}^{(t-1)}}\leq\hat{\beta}_{t-1}( \delta).$ (9) $$

The updates to the sketched regularized least squares estimator and the calculations for the confidence ellipsoid can be efficiently completed in $O\left(dl_{B_{t}}+l_{B_{t}}^{2}\right)$ time using the Woodbury identity as stated in equation 4.
This makes DBSLinUCB significantly more efficient than traditional linear bandit algorithms, which require $\Omega\left(d^{2}\right)$ in both time and space.

DBSLinUCB represents a scalable framework for efficient sketch-based linear bandits that are capable of incorporating various streaming sketching techniques.
We now explore two deterministic sketching techniques that provide different regret bounds of linear bandits.

#### DBSLinUCB using FD.

We explore the Frequent Directions (FD) (see Algorithm 4), a deterministic sketching method (Liberty, ; Ghashami et al., ).
FD uniquely maintains the invariant that the last row of the sketch matrix, $\bm{S}$, is always zero.
In each round, a new row $\bm{a}_{t}$ is inserted into this last row of $\bm{S}$, and the matrix undergoes singular value decomposition into $\bm{U\Sigma V^{\top}}$.
Subsequently, $\bm{S}$ is updated to $\sqrt{\bm{\Sigma}_{l}^{2}-\sigma\bm{I}}\cdot\bm{V}_{l}^{\top}$, where $\sigma$ represents the square of the $l$-th singular value.
Given that the rows of $\bm{S}$ are orthogonal, $\bm{M}=(\bm{S}\bm{S}^{\top}+\lambda\bm{I})^{-1}$ remains a diagonal matrix, facilitating efficient maintenance.
We integrate FD into DBSLinUCB and established the following regret bound:

###### Theorem 3 .

Assume that $\|\bm{\theta}_{\star}\|_{2}\leq H$, $\|\bm{x}\|_{2}\leq L$, and $L\geq\sqrt{\lambda}$.
Suppose that the noise is conditionally $R$-subgaussian, where $R$ is a fixed constant.
The sketch size in the active block at round $t$ is denoted as $l_{B_{t}}$.
Given the error parameter $\epsilon$, then with a probability of $1-\frac{1}{T}$, the regret of Algorithm 2 utilizing $\textup{Sk}=\textup{FD}$ is

$$ $\displaystyle\text{Regret}_{T}$ $\displaystyle\overset{\tilde{O}}{=}\frac{L(R+H\sqrt{\lambda})}{\sqrt{\lambda}} \cdot\left(d\ln\left(1+\frac{\epsilon}{\lambda}\right)+2l_{B_{T}}\cdot\ln\left (1+\frac{TL^{2}}{2l_{B_{T}}\lambda}\right)\right)\cdot\left({1+\frac{\epsilon} {\lambda}}\right)^{\frac{3}{2}}\sqrt{T}.$ $$

###### Remark 3 .

Compared to linear bandits that use a single FD sketch, our approach relies on a predetermined error parameter $\epsilon$ rather than fixed sketch size $l$.
This ensures a sublinear regret bound of order $\tilde{O}(\sqrt{T})$ without requiring prior knowledge of the streaming matrix.
The sketch size in DBSLinUCB can be dynamically adjusted to match the desired order of regret.
In practice, if the goal is to significantly enhance efficiency at the expense of a higher order of regret, $\epsilon$ can be set as a function of $T$.
Another advantage of DBSLinUCB is that the initial sketch size is independent of the error term $\epsilon$; it only affects the total computational and space cost.

###### Theorem 3 .

###### Remark 3 .

#### DBSLinUCB using RFD.

We employ the Robust Frequent Directions (RFD) sketch (see Algorithm 5), a sketching strategy designed to address the rank deficiency issue inherent in FD (Luo et al., ).
RFD reduces the approximation error of FD by maintaining a counter $\alpha$, which quantifies the spectral error.
More precisely, RFD employs $\bm{S}^{\top}\bm{S}+\alpha\bm{I}$ to approximate $\bm{A}^{\top}\bm{A}$.
We integrate RFD into DBSLinUCB and established the following regret bound:

###### Theorem 4 .

Assume that $\|\bm{\theta}_{\star}\|_{2}\leq H$, $\|\bm{x}\|_{2}\leq L$, and $L\geq\sqrt{\lambda}$.
Suppose that the noise is conditionally R-subgaussian, where $R$ is a fixed constant.
The sketch size in the active block at round $t$ is denoted as $l_{B_{t}}$.
Given the error parameter $\epsilon$, then with a probability of $1-\frac{1}{T}$, the regret of Algorithm 2 utilizing $\textup{Sk}=\textup{RFD}$ is

$$ $\displaystyle\text{Regret}_{T}$ $\displaystyle\overset{\tilde{O}}{=}\frac{L}{\sqrt{\lambda}}\cdot\sqrt{\ln\left (1+\frac{TL^{2}}{2l_{B_{T}}\lambda}+\left(1-\frac{2-B_{T}}{2^{B_{T}+1}}\right) \cdot\frac{\epsilon}{\lambda}\right)}\cdot\Bigg{(}H\cdot\sqrt{\lambda+\epsilon}+$ $\displaystyle\hphantom{{}={}}R\cdot\sqrt{d\ln\left(1+\frac{\epsilon}{\lambda} \right)+2l_{B_{T}}\cdot\ln\left(1+\frac{TL^{2}}{2l_{B_{T}}\lambda}+\left(1- \frac{2-B_{T}}{2^{B_{T}+1}}\right)\cdot\frac{\epsilon}{\lambda}\right)}\Bigg{)}.$ $$

###### Remark 4 .

Compared to DBSLinUCB using FD, the order of the error term $\epsilon$ is reduced from $3/2$ to $1/2$.
Apart from logarithmic terms, decoupling the dimensions $d$ and $\epsilon$ further reduces the impact of the error.
These properties indicate that Dyadic Block Sketching maintains the excellent characteristics of RFD.
In fact, despite having the same error bound as DBSLinUCB using FD, DBSLinUCB using RFD satisfies both positive definite monotonicity and well-conditioned properties.
We present details and proof in Appendix G.

###### Theorem 4 .

###### Remark 4 .

## 5 Experiments

In this section, we empirically verify the efficiency and effectiveness of our algorithms. We conduct experiments on both synthetic and real-world datasets. Each experiment is performed over 20 different random permutations of the datasets.
All experiments are performed on a machine with 24-core Intel(R) Xeon(R) Gold 6240R 2.40GHz CPU and 256 GB memory.

### 5.1 Matrix Approximation

Figure: Figure 3: Comparison among FD and our DBS-FD w.r.t. the error and its upper bound
Refer to caption: x3.png

We evaluate the performance of the proposed Dyadic Block Sketching in terms of matrix approximation.
We compare it with FD (Liberty, ).
We generated a synthetic dataset with $n=1250$ rows and $d=100$ columns.
Specifically, each row $\bm{a}_{t}\in\mathbb{R}^{100}$ is independently drawn from a multivariate Gaussian distribution $\bm{a}_{t}\sim\mathcal{N}(\bm{0},\bm{I}_{d})$.
We set the sketch size $l_{0}=50$ for FD.
We set the initial sketch size $l_{0}=16$ and the error parameter $\epsilon=2000$ for Dyadic Block Sketching.

Figure 3 shows the spectral norm error $\|\bm{A}_{t}^{\top}\bm{A}_{t}-\bm{S}_{t}^{\top}\bm{S}_{t}\|_{2}$ and its upper bound for matrix sketching, where $\bm{A}_{t}$ is the steaming matrix at round $t$ and $\bm{S}_{t}$ is the skech matrix at round $t$.
We observe that Dyadic Block Sketching provides a constrained global error bound for matrix sketching.
Compared with FD, the rate of error growth in Dyadic Block Sketching decreases over time, effectively limiting the linear growth of the spectral tail.

### 5.2 Online Regression in Synthetic Data

In this section, we evaluate our DBSLinUCB on synthetic datasets.
The baselines include the non-sketched method OFUL (Abbasi-Yadkori et al., ) and the sketch-based methods SOFUL (Kuzborskij et al., ), CBSCFD (Chen et al., ).
Inspired by the experimental settings in Chen et al. (), we build synthetic datasets using multivariate Gaussian distributions $\mathcal{N}(0,\bm{I}_{d})$ with $100$ arms and $d=500$ features per context.
The true parameter $\theta_{\star}$ is drawn from $\mathcal{N}(0,\bm{I}_{d})$ and is normalized.
The confidence ellipsoid $\beta$ of all algorithms is searched in $\{10^{-4},10^{-3},\ldots,1\}$ and $\lambda$ is searched in $\{2\times 10^{-4},2\times 10^{-3},\ldots,2\times 10^{4}\}$.
We set the sketch size $l=300,450$ for SOFUL and CBSCFD and the initial sketch size $l_{0}=64$ for DBSLinUCB.
Additionally, we set the error parameter $\epsilon=2000$ for DBSLinUCB.

Experimental results in Figure 1 (in Section 2.2), 4(a) show that DBSLinUCB using FD and RFD consistently outperforms the other sketch-based algorithms in terms of the regret of online learning. We observe that when $l=300$, SOFUL and CBSCFD perform significantly worse than DBSLinUCB, with SOFUL exhibiting nearly linear regret.
Moreover, DBSLinUCB achieves sublinear regret similar to OFUL by providing a constrained global error bound.
Our experimental results confirm our analysis in Section 2.2, indicating that for all existing sketch-based linear bandit algorithms, inappropriate sketch size selection can lead to the pitfall of linear regret.

Figure: (a) Regret on synthetic data
Refer to caption: x4.png

### 5.3 Online Classification in Real-world Data

We perform online classification on the real-world dataset MNIST to evaluate the performance of our methods.
The dataset contains $60,000$ samples, each with $d=784$ features, and there are $M=10$ possible labels for each sample.
We follow the experimental setup in Kuzborskij et al. ().
Specifically, we construct the online classification problem within the contextual bandit setting as follows: given a dataset with data in $M$ labels, we first choose one cluster as the target label.
In each round, we randomly draw one sample from each label and compose an arm set of $M$ samples in $M$ contexts.
The algorithms choose one sample from the arm set and observe the reward based on whether the selected sample belongs to the target label.
The reward is $1$ if the selected sample comes from the target label and 0 0 otherwise.
We set sketch size $l=20,100,200$ for SOFUL and $l_{0}=2$ for DBSLinUCB.
We set the error parameter $\epsilon=1000$ for DBSLinUCB.
The choice of confidence ellipsoid and regularization parameter follows the previous section.

Figures 4(b) and 4(c) compare the online mistakes and running times of different algorithms.
Our findings indicate that, for a given dataset, there exists an optimal sketch size (e.g., $l=200$) that captures most of the spectral information of the original matrix, thereby accelerating the algorithm without significantly compromising performance.
However, selecting this optimal sketch size for SOFUL is challenging due to the lack of prior knowledge about the data.
When $l=20$ or $l=100$, the regret of SOFUL is significantly worse than that of the non-sketched method, OFUL.
In contrast, DBSLinUCB matches the performance of OFUL by adaptively adjusting the sketch size to the near-optimal value of $l=200$ while being significantly faster than OFUL.

## 6 Conclusion

This paper addresses the current pitfall of linear regret in sketch-based linear bandits for the first time.
We propose Dyadic Block Sketching with a constrained global error bound and provide formal theoretical guarantees.
By leveraging Dyadic Block Sketching, we present a framework for efficient sketch-based linear bandits.
Even in the worst-case scenario, our method can achieve sublinear regret without prior knowledge of the covariance matrix.
Extensive experimental evaluations on real and synthetic datasets demonstrate the excellent performance and efficiency of our methods.

## Appendix A Proof of Theorem 1

For linear bandits using FD, at round $t$, the sketch matrix $\bm{S}^{(t-1)}\in\mathbb{R}^{l\times d}$ is utilized, and a new row $\bm{x}_{t}$ is received, where $l$ denotes the sketch size.
Let $\bm{\Sigma}=\mathbb{E}[\bm{x}_{t}\bm{x}_{t}^{\top}]$ be the covariance matrix of the arms, and let $\lambda_{i}$ be the $i$-th eigenvalue of $\bm{\Sigma}$. By definition, $\bm{x}_{t}$ follows the distribution $\bm{x}_{t}=\bm{a}_{i}$ with probability $\lambda_{i}$, where $\bm{a}_{i}$ is the $i$-th vector of $\bm{A}$.

We first consider the expected value of the shrinking factor when the sketch is full-rank.
If $\text{rank}\left(\bm{S}^{(t-1)}\right)=l-1$.
Let $\bm{S}^{(t-1)}=\bm{U}\bm{\Sigma}\bm{V}$ be the SVD of $\bm{S}^{(t-1)}$, and $\bm{v}_{i}$ be the $i$-th row of $\bm{V}$.
Denote the set of basis vectors not in the row space of $\bm{S}^{(t-1)}$ as $W_{t-1}=\bm{A}\backslash\{\bm{v}_{1},...,\bm{v}_{l-1}\}$, we have $|W_{t-1}|=r-l+1$.
If $\bm{x}_{t}\in\text{span}(\bm{v}_{1},...,\bm{v}_{l-1})$, we have the shrinking value $\left(\sigma_{l}^{(t)}\right)^{2}=0$; otherwise $\left(\sigma_{l}^{(t)}\right)^{2}=1$, with probability $\sum_{a_{i}\in W_{t-1}}\lambda_{i}\geq\sum_{i=l}^{r}\lambda_{i}$.
Therefore, If $\text{rank}(\bm{S}^{(t-1)})=l-1$, we have

$$ $\mathbb{E}\left[\left(\sigma_{l}^{(t)}\right)^{2}\mid\bm{S}^{(t-1)}\right]\geq \sum_{i=l}^{r}\lambda_{i}.$ $$

If $\text{rank}\left(\bm{S}^{(t-1)}\right)<l-1$, this means that $\bm{S}^{(t-1)}$ contains fewer than $l-1$ distinct vectors drawn from $\bm{A}$.
Let $I_{i}$ be the indicator variable for drawing $a_{i}$ in the first $t-1$ rounds.
Then we have the expected number of distinct vectors at round $t-1$

$$ $\mathbb{E}\left[\sum_{i=1}^{r}I_{i}\right]=\sum_{i=1}^{r}\left(1-(1-\lambda_{i })^{t-1}\right).$ $$

Using Markov’s inequality, we have

$$ $\text{Prob}\left[r-\sum_{i=1}^{r}I_{i}\geq r-l+2\right]\leq\frac{\sum_{i=1}^{r }1-(1-\lambda_{i})^{t-1}}{r-l+2}\leq\frac{r(1-\lambda_{r})^{t-1}}{2}.$ $$

Note that this is precisely the probability of having fewer than $l-1$ distinct vectors in the first $t-1$ rounds.
We conclude that for $t\geq\log\left(\frac{r}{\lambda_{r}}\right)+1$, $\text{Prob}\left[\text{rank}(\bm{S}_{t-1})=l-1\right]\geq\frac{1}{2}$.
This implies that $\mathbb{E}[\rho_{t}]\geq\frac{1}{2}\sum_{i=l}^{r}\lambda_{i}$ after an initial logarithmic number of rounds.

Therefore, assuming $T\geq 2\log\left(\frac{r}{\lambda_{r}}\right)$, the expected accumulated shrinking value is at least:

$$ $\mathbb{E}\left[\sum_{t=1}^{T}\left(\sigma_{l}^{(t)}\right)^{2}\right]\geq \frac{T}{4}\sum_{i=l}^{r}\lambda_{i}.$ $$

Note that the accumulated shrinking value is upper-bounded by the spectral loss.
According to the regret in equation 6, we conclude that the regret upper bound is $\Omega\left(T^{2}\right)$ in expectation.

## Appendix B Proof of Theorem 2

We begin our proof by considering the number of blocks. Let the entire data stream be denoted as $\bm{X}^{\top}=\left[\bm{X}_{0}^{\top},\bm{X}_{1}^{\top},\dots,\bm{X}_{B}^{\top
}\right]$. Block $i$ covers the submatrix $\bm{X}_{i}$ and stores the corresponding matrix sketch $\bm{S}_{i}$.

According to Invariant 3, each submatrix $\bm{X}_{i}$ in block $i$ contains at least $\lfloor\epsilon l_{0}\rfloor$ rows. Since there are $T$ rows available for allocation in the entire matrix, the maximum number of blocks is $\left\lceil\frac{T}{\epsilon l_{0}}\right\rceil$.

When $\epsilon$ is small, the block length grows exponentially. By Invariant 1, the length of the last active block will be exactly greater than $k$, i.e., $2^{B-1}l_{0}\leq k\leq 2^{B}l_{0}$.

Thus, we take the minimum of the two scenarios to determine the number of blocks, resulting in $B=\left\lceil\min\left\{\log\frac{k}{l_{0}},\frac{T}{\epsilon l_{0}}\right\}
\right\rceil+1$.

For the error guarantee, recall that the error comprises two components: the error from the active block and the error from merging $B$ inactive blocks.
Given that the streaming sketch can detect the best rank-$k$ approximation as long as the sketch size exceeds $k$, the approximation error in the $B$-th active block is effectively zero.

By maintaining Invariant 3, the size of the $i$-th inactive block is bounded by $l_{0}\epsilon$.
Additionally, the $i$-th block employs a streaming matrix sketch with an error parameter of $\frac{1}{2^{i}l_{0}}$, thereby ensuring that the maximum error introduced by a sketch at the $i$-th block is at most $\frac{\epsilon}{2^{i}}$.

Combining all $B+1$ sketches, we use $\bm{S}^{\top}=\left[\bm{S}_{0}^{\top},\bm{S}_{1}^{\top},\dots,\bm{S}_{B}^{\top
}\right]$ to approximate $\bm{X}$.
By Lemma 1, this provides the following error guarantee for the entire streaming matrix:

$$ $\displaystyle\left\|\bm{X}^{\top}\bm{X}-\bm{S}^{\top}\bm{S}\right\|_{2}$ $\displaystyle\leq\sum_{i=0}^{B}\left\|\bm{X}_{i}^{\top}\bm{X}_{i}-\bm{S}_{i}^{ \top}\bm{S}_{i}\right\|_{2}$ $\displaystyle=\sum_{i=0}^{B-1}\left\|\bm{X}_{i}^{\top}\bm{X}_{i}-\bm{S}_{i}^{ \top}\bm{S}_{i}\right\|_{2}+\left\|\bm{X}_{B}^{\top}\bm{X}_{B}-\bm{S}_{B}^{ \top}\bm{S}_{B}\right\|_{2}$ $\displaystyle\leq\sum_{i=0}^{B-1}\frac{\epsilon}{2^{i}}+0$ $\displaystyle\leq 2\epsilon.$ $$

For space usage, the $i$-th block employs a streaming matrix sketch with an error parameter of $\frac{1}{2^{i}l_{0}}$, resulting in a sketch of size $\ell_{\frac{1}{2^{i}l_{0}}}$. Therefore, the total number of sketched rows is $\sum_{i=0}^{B}\ell_{\frac{1}{2^{i}l_{0}}}$. Consequently, the total space requirement is $O\left(d\cdot\sum_{i=0}^{B}\ell_{\frac{1}{2^{i}l_{0}}}\right)$.

For the update cost, since only the active sketch requires updating, the cost is $O\left(\mu_{\frac{1}{2^{B}l_{0}}}\right)$.

## Appendix C Fast Algorithm of Dyadic Block Sketching

The computational cost of FD and RFD, as detailed in Algorithm 4 and 5, is primarily driven by the singular value decomposition (SVD) operations.
At round $t$, with $B_{t}+1$ blocks, we denote $l_{i}$ as the sketch size for the $i$-th block.
It incurs an amortized time of $O\left(dl_{B_{t}}^{2}\right)$ due to standard SVD processes in the active block.
Additionally, the operation to compute $\bm{M}^{(t)}$ via matrix multiplication and matrix inversion also requires $O\left(\sum_{i=0}^{B_{t}-1}l_{i}\cdot l_{B_{t}}\cdot d+\left(\sum_{i=0}^{B_{t}
}l_{i}\right)^{3}\right)=O\left(dl_{B_{t}}^{2}\right)$.
We can enhance the efficiency of our Dyadic Block Sketching by doubling the sketch size, as detailed in Algorithm 3.

Figure: Algorithm 3 Fast Dyadic Block Sketching

Notice that within each epoch, the update of $\bm{M}^{(t)}$ can be formulate as

$$ $\bm{M}^{(t)}=\begin{pmatrix}\bm{M}^{(t-1)}+\frac{\bm{\phi}\bm{\phi}^{\top}}{ \xi}&\frac{-\bm{\phi}}{\xi}\\ \frac{-\bm{\phi}^{\top}}{\xi}&\frac{1}{\xi}\end{pmatrix},$ (10) $$

where $\bm{\phi}=\bm{M}^{(t-1)}\bm{S}^{(t-1)}\bm{x}_{t}^{\top}$ and $\xi=\bm{x}_{t}\bm{x}_{t}^{\top}-\bm{x}_{t}\left(\bm{S}^{(t-1)}\right)^{\top}
\bm{\phi}+\alpha+\lambda$.

When the method $\text{Sk}=\text{FD}$, $\alpha$ is set to 0; conversely, when the method $\text{Sk}=\text{RFD}$, $\alpha$ serves as the counter maintained in the RFD sketch.

Given that the length of $\bm{M}^{(t)}$ is at most twice the length of $\bm{\mathcal{B}}[B].{length}$, the amortized computation time required for $\bm{M}^{(t)}$ is limited to $O\left(dl_{B_{t}}\right)$.
Additionally, we perform the SVD only after every addition of $\bm{\mathcal{B}}[B].{length}$ rows, reducing the amortized update time complexity to $O\left(dl_{B_{t}}\right)$.

## Appendix D Pseudo-code of Deterministic Matrix Sketching

Figure: Algorithm 4 FD sketch

The pseudo-code for deterministic matrix sketching methods is displayed in Algorithm 4 and Algorithm 5.
Note that these deterministic matrix sketching methods can be accelerated by doubling the sketch size.
More details can be found in Appendix C.

## Appendix E Proof of Theorem 3

Following Abbasi-Yadkori et al. (), we structure the proof in two parts: first, we establish bounds for the approximate confidence ellipsoid, and second, we delineate the bounds for regret.
Denote $B_{t}$ as the number of blocks at round $t$, and $\overline{\sigma}_{i}$ as the sum of shrinking singular values in the sketch of block $i$.
Let $l_{B_{t}}$ be the sketch size in the active block at round $t$.
We start by establishing an intermediate result concerning the confidence ellipsoid.

###### Theorem 5 .

Let $\hat{\bm{\theta}}_{t}$ be the RLS estimate constructed by an arbitrary policy for linear bandits after $t$ rounds of play.
For any $\delta\in(0,1)$, the optimal unknown weight $\bm{\theta}_{\star}$ belongs to the set $\Theta_{t}\equiv\left\{\bm{\theta}\in\mathbb{R}^{d}:\left\|\bm{\theta}-\hat{
\bm{\theta}}_{t}\right\|_{\hat{\bm{A}}^{(t)}}\leq\hat{\beta}_{t}(\delta)\right\}$ with probability at least $1-\delta$, where

$$ $\displaystyle\hat{\beta}_{t}(\delta)$ $\displaystyle=R\cdot\sqrt{1+\frac{\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}}{ \lambda}}\cdot\sqrt{2\ln\left(\frac{1}{\delta}\right)+d\ln\left(1+\frac{\sum_{ i=1}^{B_{t}}\overline{\sigma}_{i}}{\lambda}\right)+2l_{B_{t}}\cdot\ln\left(1+ \frac{tL^{2}}{2l_{B_{t}}\lambda}\right)}$ $\displaystyle\hphantom{{}={}}+H\cdot\frac{\lambda+\sum_{i=1}^{B_{t}}\overline{ \sigma}_{i}}{\sqrt{\lambda}}.$ $$

###### Proof.

According to Algorithm 2, the approximate covariance matrix is

$$ $\hat{\bm{A}}^{(t)}=\lambda\bm{I}+\sum_{i=1}^{B_{t}}\left(\bm{S}_{i}^{(t)} \right)^{\top}\bm{S}_{i}^{(t)},$ $$

where $\bm{S}_{i}^{(t)}$ is the sketch matrix in block $i$ at round $t$.
Define $\bm{z}_{1}^{\top},...,\bm{z}_{t}^{\top}\in\mathbb{R}^{d}$ is the noise sequence conditionally R-subgaussian for a fixed constant $R$ and $\bm{r}_{t}^{\top}=(r_{1},r_{2},...r_{t})\in\mathbb{R}^{d}$ is the reward vector.
We begin by noticing that

$$ $\displaystyle\hat{\bm{\theta}}_{t}=\left(\hat{\bm{A}}^{(t)}\right)^{-1}\bm{X}_ {t}^{\top}\bm{r}_{t}=\left(\hat{\bm{A}}^{(t)}\right)^{-1}\bm{X}_{t}^{\top} \left(\bm{X}_{t}\bm{\theta}_{\star}+\bm{z}_{t}\right).$ $$

Therefore, we can decompose $\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{\hat{\bm{A}}^{(t)}}^
{2}$ into two parts as follows

$$ $\displaystyle\hphantom{{}={}}\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star} \right\|_{\hat{\bm{A}}^{(t)}}^{2}$ (11) $\displaystyle=\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right)^{\top} \hat{\bm{A}}^{(t)}\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right)$ $\displaystyle=\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right)^{\top} \hat{\bm{A}}^{(t)}\left(\left(\hat{\bm{A}}^{(t)}\right)^{-1}\bm{X}_{t}^{\top} \left(\bm{X}_{t}\bm{\theta}_{\star}+\bm{z}_{t}\right)-\bm{\theta}_{\star}\right)$ $\displaystyle=\underbrace{\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star} \right)^{\top}\hat{\bm{A}}^{(t)}\left(\left(\hat{\bm{A}}^{(t)}\right)^{-1}\bm{ X}_{t}^{\top}\bm{X}_{t}\bm{\theta}_{\star}-\bm{\theta}_{\star}\right)}_{\text{ Term 1: Bias Error}}+\underbrace{\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{ \star}\right)^{\top}\bm{X}_{t}^{\top}\bm{z}_{t}}_{\text{Term 2: Variance Error }}.$ $$

###### Theorem 5 .

###### Proof.

#### Bounding the bias error.

We first focus on bounding the first term.
We have that

$$ $\displaystyle\hphantom{{}={}}\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star} \right)^{\top}\hat{\bm{A}}^{(t)}\left(\left(\hat{\bm{A}}^{(t)}\right)^{-1}\bm{ X}_{t}^{\top}\bm{X}_{t}\bm{\theta}_{\star}-\bm{\theta}_{\star}\right)$ (12) $\displaystyle=\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right)^{\top} \left(\hat{\bm{A}}^{(t)}\right)^{\frac{1}{2}}\left(\hat{\bm{A}}^{(t)}\right)^{ -\frac{1}{2}}\left(\bm{X}_{t}^{\top}\bm{X}_{t}\bm{\theta}_{\star}-\hat{\bm{A}} ^{(t)}\bm{\theta}_{\star}\right)$ $\displaystyle=\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right)^{\top} \left(\hat{\bm{A}}^{(t)}\right)^{\frac{1}{2}}\left(\hat{\bm{A}}^{(t)}\right)^{ -\frac{1}{2}}\left[\left(\bm{A}^{(t)}-\hat{\bm{A}}^{(t)}\right)\bm{\theta}_{ \star}-\lambda\bm{\theta}_{\star}\right].$ $$

In accordance with the decomposability of matrix sketches, as detailed in Lemma 1, we have

$$ $\left\|\bm{X}_{t}^{\top}\bm{X}_{t}-\sum_{i=1}^{B_{t}}\left(\bm{S}_{i}^{(t)} \right)^{\top}\bm{S}_{i}^{(t)}\right\|_{2}\leq\sum_{i=1}^{B_{t}}\overline{ \sigma}_{i}$ (13) $$

By Cauchy-Schwartz inequality and the triangle inequality, we have

$$ $\displaystyle\hphantom{{}={}}\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star} \right)^{\top}\left(\hat{\bm{A}}^{(t)}\right)^{\frac{1}{2}}\left(\hat{\bm{A}}^ {(t)}\right)^{-\frac{1}{2}}\left[\left(\bm{A}^{(t)}-\hat{\bm{A}}^{(t)}\right) \bm{\theta}_{\star}-\lambda\bm{\theta}_{\star}\right]$ (14) $\displaystyle\leq\left|\lambda+\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}\right| \cdot\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{\hat{\bm{A}}^{( t)}}\cdot\left\|\bm{\theta}_{\star}\right\|_{\left(\hat{\bm{A}}^{(t)}\right)^{ -1}}$ $\displaystyle\leq H\cdot\frac{\lambda+\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}} {\sqrt{\lambda}}\cdot\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_ {\hat{\bm{A}}^{(t)}},$ $$

where the last inequality holds beacause $\hat{\bm{A}}^{(t)}\succeq\lambda\bm{I}$ and $\|\bm{\theta}_{\star}\|_{2}\leq H$.

#### Bounding the variance error.

Then, we aim to bound the second term.
We use the following self-normalized martingale concentration inequality by Abbasi-Yadkori et al. ().

###### Proposition 1 .

Assume that $\bm{z}_{1},...,\bm{z}_{t}$ is a conditionally R-subgaussian real-valued stochastic process and $\bm{X}_{t}^{\top}=\left[\bm{x}_{1}^{\top},...,\bm{x}_{t}^{\top}\right]$ is any stochastic process such that $\bm{x}_{i}$ is measurable with respect to the $\sigma$-algebra generated by $\bm{z}_{1},...,\bm{z}_{t}$.
Then, for any $\delta>0$, with probability at least $1-\delta$, for all $t\geq 0$,

$$ $\left\|\bm{X}_{t}^{\top}\bm{z}_{t}\right\|_{\left({\bm{A}}^{(t)}\right)^{-1}}^ {2}\leq 2R^{2}\ln\left(\frac{1}{\delta}\left|\bm{A}^{(t)}\right|^{\frac{1}{2}} \left|\lambda\bm{I}\right|^{-\frac{1}{2}}\right).$ $$

Notice that the variance error can be reformulated as

$$ $\displaystyle\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right)^{\top}\bm{ X}_{t}^{\top}\bm{z}_{t}$ $\displaystyle=\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right)^{\top} \left({\bm{A}}^{(t)}\right)^{-\frac{1}{2}}\left({\bm{A}}^{(t)}\right)^{\frac{1 }{2}}\bm{X}_{t}^{\top}\bm{z}_{t}$ (15) $\displaystyle\leq\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{ \hat{\bm{A}}^{(t)}}\cdot\frac{\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star} \right\|_{{\bm{A}}^{(t)}}}{\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star} \right\|_{\hat{\bm{A}}^{(t)}}}\cdot\left\|\bm{X}_{t}^{\top}\bm{z}_{t}\right\|_ {\left({\bm{A}}^{(t)}\right)^{-1}},$ $$

where the last inequality uses Cauchy-Schwartz inequality.

For any vector $\bm{a}$, we have

$$ $\displaystyle\|\bm{a}\|_{{\bm{A}}^{(t)}}^{2}-\|\bm{a}\|_{\hat{\bm{A}}^{(t)}}^{2}$ $\displaystyle=\bm{a}^{\top}\left({\bm{A}}^{(t)}-\hat{\bm{A}}^{(t)}\right)\bm{a}$ (16) $\displaystyle=\bm{a}^{\top}\left(\bm{X}^{\top}\bm{X}-\sum_{i=1}^{B_{t}}\left( \bm{S}_{i}^{(t)}\right)^{\top}\bm{S}_{i}^{(t)}\right)\bm{a}$ $\displaystyle\leq\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}\cdot\|\bm{a}\|_{2}^{2}.$ $$

Therefore, the ratios of norms on the right-hand side of equation 15 can be bounded as

$$ $\displaystyle\frac{\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{{ \bm{A}}^{(t)}}}{\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{\hat {\bm{A}}^{(t)}}}$ $\displaystyle=\sqrt{\frac{\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star} \right\|_{{\bm{A}}^{(t)}}^{2}}{\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star }\right\|_{\hat{\bm{A}}^{(t)}}^{2}}}$ (17) $\displaystyle\leq\sqrt{\frac{\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star} \right\|_{{\hat{\bm{A}}}^{(t)}}^{2}+\sum_{i=1}^{B_{t}}\overline{\sigma}_{i} \left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|^{2}}{\left\|\hat{\bm{ \theta}}_{t}-\bm{\theta}_{\star}\right\|_{\hat{\bm{A}}^{(t)}}^{2}}}$ $\displaystyle\leq\sqrt{1+\frac{\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}}{ \lambda}}.$ $$

Substituting equation 17 and Proposition 1 into equation 15 gives

$$ $\displaystyle\hphantom{{}={}}\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star} \right\|_{\hat{\bm{A}}^{(t)}}\cdot\frac{\left\|\hat{\bm{\theta}}_{t}-\bm{ \theta}_{\star}\right\|_{{\bm{A}}^{(t)}}}{\left\|\hat{\bm{\theta}}_{t}-\bm{ \theta}_{\star}\right\|_{\hat{\bm{A}}^{(t)}}}\cdot\left\|\bm{X}_{t}^{\top}\bm{ z}_{t}\right\|_{\left({\bm{A}}^{(t)}\right)^{-1}}$ (18) $\displaystyle\leq\sqrt{1+\frac{\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}}{ \lambda}}\cdot\sqrt{2R^{2}\ln\left(\frac{1}{\delta}\left|\bm{A}^{(t)}\right|^{ \frac{1}{2}}\left|\lambda\bm{I}\right|^{-\frac{1}{2}}\right)}\cdot\left\|\hat{ \bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{\hat{\bm{A}}^{(t)}}.$ $$

Motivated by Abbasi-Yadkori et al. (); Kuzborskij et al. (), we apply the multi-scale sketch-based determinant-trace inequality.
Compared to the non-sketched version, this inequality depends on the approximate covariance matrix $\hat{\bm{A}}$, reflecting the costs associated with the shrinkage due to multi-scale sketching.

###### Lemma 2 .

For any $t\geq 1$, define $\bm{A}^{(t)}=\lambda\bm{I}+\bm{X}_{t}^{\top}\bm{X}_{t}$, and assume $\|\bm{x}_{t}\|_{2}\leq L$, we have

$$ $\ln\left(\frac{\left|\bm{A}^{(t)}\right|}{\left|\lambda\bm{I}\right|}\right) \leq d\ln\left(1+\frac{\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}}{\lambda}\right )+2l_{B_{t}}\cdot\ln\left(1+\frac{tL^{2}}{2l_{B_{t}}\lambda}\right).$ $$

###### Proof.

$\sum_{i=1}^{B_{t}}\left(\bm{S}_{i}^{(t)}\right)^{\top}\bm{S}_{i}^{(t)}$ has rank at most $2l_{B_{t}}$ due to the Dyadic Block Sketching.
Since $\hat{\bm{A}}^{(t)}=\lambda\bm{I}+\sum_{i=1}^{B_{t}}\left(\bm{S}_{i}^{(t)}
\right)^{\top}\bm{S}_{i}^{(t)}$ and $\bm{A}^{(t)}\preceq\hat{\bm{A}}^{(t)}+\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}
\cdot\bm{I}$, we have

$$ $\displaystyle\left|\bm{A}^{(t)}\right|$ $\displaystyle\leq\left|\hat{\bm{A}}^{(t)}+\sum_{i=1}^{B_{t}}\overline{\sigma}_ {i}\cdot\bm{I}\right|$ $\displaystyle\leq\left(\lambda+\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}\right)^ {d-2l_{B_{t}}}\cdot\left(\frac{\sum_{i=1}^{2l_{B_{t}}}\left(\lambda_{i}\left( \hat{\bm{A}}^{(t)}\right)+\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}\right)}{2l_{ B_{t}}}\right)^{2l_{B_{t}}}$ $\displaystyle\leq\left(\lambda+\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}\right)^ {d-2l_{B_{t}}}\cdot\left(\lambda+\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}+\frac {\text{Tr}\left(\sum_{i=1}^{B_{t}}\left(\bm{S}_{i}^{(t)}\right)^{\top}\bm{S}_{ i}^{(t)}\right)}{2l_{B_{t}}}\right)^{2l_{B_{t}}}$ $\displaystyle\leq\left(\lambda+\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}\right)^ {d-2l_{B_{t}}}\cdot\left(\lambda+\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}+\frac {tL^{2}}{2l_{B_{t}}}\right)^{2l_{B_{t}}},$ $$

where the last inequality holds because

$$ $\displaystyle\hphantom{{}={}}\text{Tr}\left(\sum_{i=1}^{B_{t}}\left(\bm{S}_{i} ^{(t)}\right)^{\top}\bm{S}_{i}^{(t)}\right)$ $\displaystyle\leq\text{Tr}\left(\bm{X}_{t}^{\top}\bm{X}_{t}\right)$ $\displaystyle=\sum_{s=1}^{t}{\bm{x}_{s}^{\top}\bm{x}_{s}}$ $\displaystyle\leq tL^{2}$ $$

Therefore, we have

$$ $\displaystyle\ln\left(\frac{\left|\bm{A}^{(t)}\right|}{\left|\lambda\bm{I} \right|}\right)$ $\displaystyle\leq\ln\left\{\left(\frac{\lambda+\sum_{i=1}^{B_{t}}\overline{ \sigma}_{i}}{\lambda}\right)^{d-2l_{B_{t}}}\cdot\left(\frac{\lambda+\sum_{i=1} ^{B_{t}}\overline{\sigma}_{i}+\frac{tL^{2}}{2l_{B_{t}}}}{\lambda}\right)^{2l_{ B_{t}}}\right\}$ $\displaystyle=(d-2l_{B_{t}})\ln\left(1+\frac{\sum_{i=1}^{B_{t}}\overline{ \sigma}_{i}}{\lambda}\right)+2l_{B_{t}}\ln\left(1+\frac{\sum_{i=1}^{B_{t}} \overline{\sigma}_{i}}{\lambda}+\frac{tL^{2}}{2l_{B_{t}}\lambda}\right)$ $\displaystyle\leq d\ln\left(1+\frac{\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}}{ \lambda}\right)+2l_{B_{t}}\cdot\ln\left(1+\frac{tL^{2}}{2l_{B_{t}}\lambda} \right).$ $$

∎

According to Lemma 2, we finally bound the variance error term as follows

$$ $\displaystyle\hphantom{{}={}}\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star} \right\|_{\hat{\bm{A}}^{(t)}}\cdot\frac{\left\|\hat{\bm{\theta}}_{t}-\bm{ \theta}_{\star}\right\|_{{\bm{A}}^{(t)}}}{\left\|\hat{\bm{\theta}}_{t}-\bm{ \theta}_{\star}\right\|_{\hat{\bm{A}}^{(t)}}}\cdot\left\|\bm{X}_{t}^{\top}\bm{ z}_{t}\right\|_{\left({\bm{A}}^{(t)}\right)^{-1}}$ $\displaystyle\leq\sqrt{1+\frac{\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}}{ \lambda}}\cdot\sqrt{2R^{2}\ln\left(\frac{1}{\delta}\left|\bm{A}^{(t)}\right|^{ \frac{1}{2}}\left|\lambda\bm{I}\right|^{-\frac{1}{2}}\right)}\cdot\left\|\hat{ \bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{\hat{\bm{A}}^{(t)}}$ $\displaystyle\leq R\cdot\sqrt{1+\frac{\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}} {\lambda}}\cdot\sqrt{2\ln\left(\frac{1}{\delta}\right)+d\ln\left(1+\frac{\sum_ {i=1}^{B_{t}}\overline{\sigma}_{i}}{\lambda}\right)+2l_{B_{t}}\cdot\ln\left(1+ \frac{tL^{2}}{2l_{B_{t}}\lambda}\right)}\cdot\left\|\hat{\bm{\theta}}_{t}-\bm{ \theta}_{\star}\right\|_{\hat{\bm{A}}^{(t)}}.$ $$

Sum up the bias error and the variance error and divide both sides of equation 11 by $\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{\hat{\bm{A}}^{(t)}}$ simultaneously, we have

$$ $\displaystyle\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{\hat{ \bm{A}}^{(t)}}$ $\displaystyle\leq R\cdot\sqrt{1+\frac{\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}} {\lambda}}\cdot\sqrt{2\ln\left(\frac{1}{\delta}\right)+d\ln\left(1+\frac{\sum_ {i=1}^{B_{t}}\overline{\sigma}_{i}}{\lambda}\right)+2l_{B_{t}}\cdot\ln\left(1+ \frac{tL^{2}}{2l_{B_{t}}\lambda}\right)}$ $\displaystyle\hphantom{{}={}}+H\cdot\frac{\lambda+\sum_{i=1}^{B_{t}}\overline{ \sigma}_{i}}{\sqrt{\lambda}},$ $$

which concludes the proof.
∎
Having established the confidence ellipsoid, we now focus on analyzing the regret.
We begin with an analysis of the instantaneous regret.

Recall that the optimal arm at round $t$ is defined as $\bm{x}_{t}^{\star}=\underset{\bm{x}\in\mathcal{X}_{t}}{\arg\max}(\bm{x}^{\top}
\bm{\theta}_{\star})$.
On the other hand, the principle of optimism in the face of uncertainty ensures that $\left(\bm{x}_{t},\hat{\bm{\theta}}_{t-1}\right)=\underset{(\bm{x},\bm{\theta})
\in\mathcal{X}_{t}\times\Theta_{t-1}}{\arg\max}\bm{x}^{\top}\bm{\theta}$.
By denoting $\tilde{\bm{\theta}}_{t}$ as the RLS estimator, we utilize these facts to establish the bound on the instantaneous regret as follows

$$ $\displaystyle\hphantom{{}={}}\left(\bm{x}_{t}^{\star}-\bm{x}_{t}\right)^{\top} \bm{\theta}_{\star}$ (19) $\displaystyle\leq\bm{x}_{t}^{\top}\hat{\bm{\theta}}_{t-1}-\bm{x}_{t}^{\top}\bm {\theta}_{\star}$ $\displaystyle=\bm{x}_{t}^{\top}\left(\hat{\bm{\theta}}_{t-1}-\tilde{\bm{\theta }}_{t-1}\right)+\bm{x}_{t}^{\top}\left(\tilde{\bm{\theta}}_{t-1}-\bm{\theta}_{ \star}\right)$ $\displaystyle\leq\|\bm{x}_{t}\|_{\left(\hat{\bm{A}}^{(t-1)}\right)^{-1}}\cdot \left(\left\|\hat{\bm{\theta}}_{t-1}-\tilde{\bm{\theta}}_{t-1}\right\|_{\hat{ \bm{A}}^{(t-1)}}+\left\|\tilde{\bm{\theta}}_{t-1}-\bm{\theta}_{\star}\right\|_ {\hat{\bm{A}}^{(t-1)}}\right)$ $\displaystyle\leq 2\hat{\beta}_{t-1}(\delta)\cdot\|\bm{x}_{t}\|_{\left(\hat{ \bm{A}}^{(t-1)}\right)^{-1}}.$ $$

Now, we are prepared to establish the upper bound of regret.
Utilizing equation 19 and Cauchy-Schwartz inequality, we derive the following bound

$$ $\displaystyle\text{Regret}_{T}$ $\displaystyle=\sum_{t=1}^{T}\max_{\bm{x}\in\mathcal{X}}\bm{x}^{\top}\bm{\theta }_{\star}-\sum_{t=1}^{T}\bm{x}_{t}^{\top}\bm{\theta}_{\star}$ (20) $\displaystyle\leq 2\sum_{t=1}^{T}\min\left\{HL,\hat{\beta}_{t-1}(\delta)\cdot \|\bm{x}_{t}\|_{\left(\hat{\bm{A}}^{(t-1)}\right)^{-1}}\right\}$ $\displaystyle\leq 2\sum_{t=1}^{T}\hat{\beta}_{t-1}(\delta)\min\left\{\frac{L}{ \sqrt{\lambda}},\|\bm{x}_{t}\|_{\left(\hat{\bm{A}}^{(t-1)}\right)^{-1}}\right\}$ $\displaystyle\leq 2\cdot\max\left\{1,\frac{L}{\sqrt{\lambda}}\right\}\cdot\hat {\beta}_{T}(\delta)\cdot\sum_{t=1}^{T}\min\left\{1,\|\bm{x}_{t}\|_{\left(\hat{ \bm{A}}^{(t-1)}\right)^{-1}}\right\}$ $\displaystyle\leq 2\cdot\max\left\{1,\frac{L}{\sqrt{\lambda}}\right\}\cdot\hat {\beta}_{T}(\delta)\cdot\sqrt{T\sum_{t=1}^{T}\min\left\{1,\|\bm{x}_{t}\|_{ \left(\hat{\bm{A}}^{(t-1)}\right)^{-1}}^{2}\right\}}.$ $$

We further bound the terms in the above.
In particular, we formulate $\hat{\beta}_{T}(\delta)$ by Theorem 5 as follows

$$ $\displaystyle\hat{\beta}_{T}(\delta)$ $\displaystyle=R\sqrt{1+\frac{\sum_{i=1}^{B_{T}}\overline{\sigma}_{i}}{\lambda} }\cdot\sqrt{2\ln\frac{1}{\delta}+d\ln\left(1+\frac{\sum_{i=1}^{B_{T}}\overline {\sigma}_{i}}{\lambda}\right)+2l_{B_{T}}\cdot\ln\left(1+\frac{TL^{2}}{2l_{B_{T }}\lambda}\right)}$ (21) $\displaystyle\hphantom{{}={}}+H\sqrt{\lambda}\left({1+\frac{\sum_{i=1}^{B_{T}} \overline{\sigma}_{i}}{\lambda}}\right).$ $$

Besides, we adopt the Sketched leverage scores established by Kuzborskij et al. () as follows

###### Proposition 2 (Lemma 6 of Kuzborskij et al. ( 2019 ) ) .

The sketched leverage scores through sketching at round $T$ can be upper bounded as

$$ $\displaystyle\hphantom{{}={}}\sum_{t=1}^{T}\min\left\{1,\|\bm{x}_{t}\|^{2}_{ \left(\hat{\bm{A}}^{(t)}\right)^{-1}}\right\}$ $\displaystyle\leq 2\left(1+\frac{\sum_{i=1}^{B_{T}}\overline{\sigma}_{i}}{ \lambda}\right)\cdot\ln\left(\frac{\left|\bm{A}^{(T)}\right|}{\left|\lambda\bm {I}\right|}\right)$ $\displaystyle\leq 2\left(1+\frac{\sum_{i=1}^{B_{T}}\overline{\sigma}_{i}}{ \lambda}\right)\cdot\left(d\ln\left(\frac{1+\sum_{i=1}^{B_{T}}\overline{\sigma }_{i}}{\lambda}\right)+2l_{B_{t}}\cdot\ln\left(1+\frac{TL^{2}}{2l_{B_{T}} \lambda}\right)\right).$ $$

Combining equation 21, equation 20 and Proposition 2, assume $L\geq\sqrt{\lambda}$, we have

$$ $\displaystyle\text{Regret}_{T}$ $\displaystyle\leq 2\cdot\max\left\{1,\frac{L}{\sqrt{\lambda}}\right\}\cdot\hat {\beta}_{T}(\delta)\cdot\sqrt{T\sum_{t=1}^{T}\min\left\{1,\|\bm{x}_{t}\|_{ \left(\hat{\bm{A}}^{(t-1)}\right)^{-1}}^{2}\right\}}$ $\displaystyle\overset{\tilde{O}}{=}\frac{L}{\sqrt{\lambda}}\cdot\sqrt{T}\cdot \left(1+\frac{\sum_{i=1}^{B_{T}}\overline{\sigma}_{i}}{\lambda}\right)\cdot \left(d\ln\left(\frac{1+\sum_{i=1}^{B_{T}}\overline{\sigma}_{i}}{\lambda} \right)+2l_{B_{t}}\cdot\ln\left(1+\frac{TL^{2}}{2l_{B_{T}}\lambda}\right)\right)$ $\displaystyle\hphantom{{}={}}\cdot\Bigg{(}R\sqrt{1+\frac{\sum_{i=1}^{B_{T}} \overline{\sigma}_{i}}{\lambda}}\cdot\sqrt{2\ln\frac{1}{\delta}+d\ln\left(1+ \frac{\sum_{i=1}^{B_{T}}\overline{\sigma}_{i}}{\lambda}\right)+2l_{B_{T}}\cdot \ln\left(1+\frac{TL^{2}}{2l_{B_{T}}\lambda}\right)}$ $\displaystyle\hphantom{{}={}}+H\sqrt{\lambda}\left({1+\frac{\sum_{i=1}^{B_{T}} \overline{\sigma}_{i}}{\lambda}}\right)\Bigg{)}$ $\displaystyle\overset{\tilde{O}}{=}\frac{L(R+H\sqrt{\lambda})}{\sqrt{\lambda}} \cdot\left(d\ln\left(1+\frac{\sum_{i=1}^{B_{T}}\overline{\sigma}_{i}}{\lambda} \right)+2l_{B_{T}}\cdot\ln\left(1+\frac{TL^{2}}{2l_{B_{T}}\lambda}\right)\right)$ $\displaystyle\hphantom{{}={}}\cdot\left({1+\frac{\sum_{i=1}^{B_{T}}\overline{ \sigma}_{i}}{\lambda}}\right)^{\frac{3}{2}}\sqrt{T}.$ $$

According to Theorem 2, we can bound the spectral error by error $\epsilon$, which is

$$ $\displaystyle\text{Regret}_{T}$ $\displaystyle\overset{\tilde{O}}{=}\frac{L(R+H\sqrt{\lambda})}{\sqrt{\lambda}} \cdot\left(d\ln\left(1+\frac{\epsilon}{\lambda}\right)+2l_{B_{T}}\cdot\ln\left (1+\frac{TL^{2}}{2l_{B_{T}}\lambda}\right)\right)\cdot\left({1+\frac{\epsilon} {\lambda}}\right)^{\frac{3}{2}}\sqrt{T}.$ $$

###### Proposition 1 .

###### Lemma 2 .

###### Proof.

###### Proposition 2 (Lemma 6 of Kuzborskij et al. ( 2019 ) ) .

## Appendix F Proof of Theorem 4

We denote $B_{t}$ as the number of blocks at round $t$, and $\overline{\sigma}_{i}$ as the cumulative shrinking singular values in the sketch of block $i$.
Let $l_{B_{t}}$ be the sketch size in the active block at round $t$.
Similarly, our analysis establishes an intermediate result regarding the confidence ellipsoid.

###### Theorem 6 .

Let $\hat{\bm{\theta}}_{t}$ be the RLS estimate constructed by an arbitrary policy for linear bandits after $t$ rounds of play.
For any $\delta\in(0,1)$, the optimal unknown weight $\bm{\theta}_{\star}$ belongs to the set $\Theta_{t}\equiv\left\{\bm{\theta}\in\mathbb{R}^{d}:\left\|\bm{\theta}-\hat{
\bm{\theta}}_{t}\right\|_{\hat{\bm{A}}^{(t)}}\leq\hat{\beta}_{t}(\delta)\right\}$ with probability at least $1-\delta$, where

$$ $\displaystyle\hat{\beta}_{t}(\delta)$ $\displaystyle=R\cdot\sqrt{2\ln\left(\frac{1}{\delta}\right)+d\ln\left(1+\frac{ \sum_{i=1}^{B_{t}}\overline{\sigma}_{i}}{\lambda}\right)+2l_{B_{t}}\cdot\ln \left(1+\frac{tL^{2}}{2l_{B_{t}}\lambda}+\frac{h_{t}}{\lambda}\right)}$ $\displaystyle\hphantom{{}={}}+H\cdot\sqrt{\lambda+\sum_{i=1}^{B_{t}}\overline{ \sigma}_{i}}$ $$

and

$$ $h_{t}=\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}-\frac{\sum_{i=1}^{B_{t}}l_{i} \cdot\overline{\sigma}_{i}}{2l_{B_{t}}}.$ $$

###### Proof.

Notice that RFD uses the adaptive regularization term to approximate the covariance matrix, i.e., $\hat{\bm{A}}^{(t)}=\lambda\bm{I}+\sum_{i=1}^{B_{t}}\alpha_{i}^{(t)}\bm{I}+\sum
_{i=1}^{B_{t}}\left(\bm{S}_{i}^{(t)}\right)^{\top}\bm{S}_{i}^{(t)}$, where $\bm{S}_{i}^{(t)}$ is the sketch matrix in block $i$ and $\alpha_{i}^{(t)}$ is the adaptive regularization term of RFD at round $t$.

Similarily, we decompose $\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{\hat{\bm{A}}^{(t)}}^
{2}$ into two parts as follows

$$ $\displaystyle\hphantom{{}={}}\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star} \right\|_{\hat{\bm{A}}^{(t)}}^{2}$ $\displaystyle=\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right)^{\top} \hat{\bm{A}}^{(t)}\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right)$ $\displaystyle=\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right)^{\top} \hat{\bm{A}}^{(t)}\left(\left(\hat{\bm{A}}^{(t)}\right)^{-1}\bm{X}_{t}^{\top} \left(\bm{X}_{t}\bm{\theta}_{\star}+\bm{z}_{t}\right)-\bm{\theta}_{\star}\right)$ $\displaystyle=\underbrace{\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star} \right)^{\top}\hat{\bm{A}}^{(t)}\left(\left(\hat{\bm{A}}^{(t)}\right)^{-1}\bm{ X}_{t}^{\top}\bm{X}_{t}\bm{\theta}_{\star}-\bm{\theta}_{\star}\right)}_{\text{ Term 1: Bias Error}}+\underbrace{\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{ \star}\right)^{\top}\bm{X}_{t}^{\top}\bm{z}_{t}}_{\text{Term 2: Variance Error }}.$ $$

###### Theorem 6 .

###### Proof.

#### Bounding the bias error.

For the bias error term, we have

$$ $\displaystyle\hphantom{{}={}}\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star} \right)^{\top}\hat{\bm{A}}^{(t)}\left(\left(\hat{\bm{A}}^{(t)}\right)^{-1}\bm{ X}_{t}^{\top}\bm{X}_{t}\bm{\theta}_{\star}-\bm{\theta}_{\star}\right)$ (22) $\displaystyle=\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right)^{\top} \left(\hat{\bm{A}}^{(t)}\right)^{\frac{1}{2}}\left(\hat{\bm{A}}^{(t)}\right)^{ -\frac{1}{2}}\left(\bm{X}_{t}^{\top}\bm{X}_{t}\bm{\theta}_{\star}-\hat{\bm{A}} ^{(t)}\bm{\theta}_{\star}\right)$ $\displaystyle=\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right)^{\top} \left(\hat{\bm{A}}^{(t)}\right)^{\frac{1}{2}}\left(\hat{\bm{A}}^{(t)}\right)^{ -\frac{1}{2}}\left(\bm{X}_{t}^{\top}\bm{X}_{t}-\lambda\bm{I}-\sum_{i=1}^{B_{t} }\alpha_{i}^{(t)}\bm{I}-\sum_{i=1}^{B_{t}}\left(\bm{S}_{i}^{(t)}\right)^{\top} \bm{S}_{i}^{(t)}\right)\bm{\theta}_{\star}$ $\displaystyle\triangleq\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right)^ {\top}\left(\hat{\bm{A}}^{(t)}\right)^{\frac{1}{2}}\left(\hat{\bm{A}}^{(t)} \right)^{-\frac{1}{2}}\bm{D}_{t}\cdot\bm{\theta}_{\star}$ $$

Since $\bm{D}_{t}=\bm{X}_{t}^{\top}\bm{X}_{t}-\lambda\bm{I}-\sum_{i=1}^{B_{t}}\alpha_
{i}^{(t)}\bm{I}-\sum_{i=1}^{B_{t}}\left(\bm{S}_{i}^{(t)}\right)^{\top}\bm{S}_{
i}^{(t)}$, for any unit vector $\bm{a}$, we have

$$ $\displaystyle\left|\bm{a}^{\top}\bm{D}_{t}\bm{a}\right|$ $\displaystyle=\left|\bm{a}^{\top}\left(\bm{X}_{t}^{\top}\bm{X}_{t}-\lambda\bm{ I}-\sum_{i=1}^{B_{t}}\alpha_{i}^{(t)}\bm{I}-\sum_{i=1}^{B_{t}}\left(\bm{S}_{i} ^{(t)}\right)^{\top}\bm{S}_{i}^{(t)}\right)\bm{a}\right|$ (23) $\displaystyle=\left|\bm{a}^{\top}\left(\bm{X}_{t}^{\top}\bm{X}_{t}-\sum_{i=1}^ {B_{t}}\left(\bm{S}_{i}^{(t)}\right)^{\top}\bm{S}_{i}^{(t)}\right)\bm{a}- \lambda\bm{I}-\sum_{i=1}^{B_{t}}\alpha_{i}^{(t)}\bm{I}\right|.$ $$

According to Theroem 2, we can get

$$ $0\leq\bm{a}^{\top}\left(\bm{X}_{t}^{\top}\bm{X}_{t}-\sum_{i=1}^{B_{t}}\left( \bm{S}_{i}^{(t)}\right)^{\top}\bm{S}_{i}^{(t)}\right)\bm{a}\leq\sum_{i=1}^{B_{ t}}\overline{\sigma}_{i}.$ $$

Bring the above equation into equation 23, since $\sum_{i=1}^{B_{t}}\alpha_{i}^{(t)}=\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}$, we can bound the spectral norm of $\bm{D}_{t}$ as follows

$$ $\displaystyle\|\bm{D}_{t}\|_{2}\leq\lambda+\sum_{i=1}^{B_{t}}\overline{\sigma} _{i}.$ (24) $$

By Cauchy-Schwartz inequality and the triangle inequality, we can bound equation 22 by

$$ $\displaystyle\hphantom{{}={}}\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star} \right)^{\top}\left(\hat{\bm{A}}^{(t)}\right)^{\frac{1}{2}}\left(\hat{\bm{A}}^ {(t)}\right)^{-\frac{1}{2}}\bm{D}_{t}\cdot\bm{\theta}_{\star}$ (25) $\displaystyle\leq\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{ \hat{\bm{A}}^{(t)}}\cdot\|\bm{D}_{t}\|_{2}\cdot\left\|\bm{\theta}_{\star} \right\|_{\left(\hat{\bm{A}}^{(t)}\right)^{-1}}$ $\displaystyle\leq H\cdot\sqrt{\lambda+\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}} \cdot\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{\hat{\bm{A}}^{( t)}},$ $$

where the last inequality holds because

$$ $\left\|\bm{\theta}_{\star}\right\|_{\left(\hat{\bm{A}}^{(t)}\right)^{-1}}^{2} \leq\frac{\|\bm{\theta}_{\star}\|_{2}^{2}}{\lambda_{\text{min}}\left(\hat{\bm{ A}}^{(t)}\right)}\leq\frac{H^{2}}{\lambda+\sum_{i=1}^{B_{t}}\overline{\sigma}_ {i}}.$ $$

#### Bounding the variance error.

For the variance error, we have

$$ $\displaystyle\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right)^{\top}\bm{ X}_{t}^{\top}\bm{z}_{t}$ $\displaystyle=\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right)^{\top} \left({\bm{A}}^{(t)}\right)^{-\frac{1}{2}}\left({\bm{A}}^{(t)}\right)^{\frac{1 }{2}}\bm{X}_{t}^{\top}\bm{z}_{t}$ (26) $\displaystyle\leq\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{ \hat{\bm{A}}^{(t)}}\cdot\frac{\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star} \right\|_{{\bm{A}}^{(t)}}}{\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star} \right\|_{\hat{\bm{A}}^{(t)}}}\cdot\left\|\bm{X}_{t}^{\top}\bm{z}_{t}\right\|_ {\left({\bm{A}}^{(t)}\right)^{-1}}$ $\displaystyle\leq\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{ \hat{\bm{A}}^{(t)}}\cdot\left\|\bm{X}_{t}^{\top}\bm{z}_{t}\right\|_{\left({\bm {A}}^{(t)}\right)^{-1}}.$ $$

where the last inequality holds because for any vector $\bm{a}$

$$ $\displaystyle\|\bm{a}\|_{{\bm{A}}^{(t)}}^{2}-\|\bm{a}\|_{\hat{\bm{A}}^{(t)}}^{2}$ $\displaystyle=\bm{a}^{\top}\left(\bm{X}^{\top}\bm{X}-\sum_{i=1}^{B_{t}}\left( \bm{S}_{i}^{(t)}\right)^{\top}\bm{S}_{i}^{(t)}-\sum_{i=1}^{B_{t}}\overline{ \sigma}_{i}\bm{I}\right)\bm{a}$ (27) $\displaystyle=\bm{a}^{\top}\left(\bm{X}^{\top}\bm{X}-\sum_{i=1}^{B_{t}}\left( \bm{S}_{i}^{(t)}\right)^{\top}\bm{S}_{i}^{(t)}\right)\bm{a}-\sum_{i=1}^{B_{t}} \overline{\sigma}_{i}\|\bm{a}\|_{2}^{2}$ $\displaystyle\leq\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}\|\bm{a}\|_{2}^{2}- \sum_{i=1}^{B_{t}}\overline{\sigma}_{i}\|\bm{a}\|_{2}^{2}$ $\displaystyle=0$ $$

By Proposition 1, we can bound the variance error term as follows

$$ $\displaystyle\hphantom{{}={}}\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star} \right)^{\top}\bm{X}_{t}^{\top}\bm{z}_{t}$ (28) $\displaystyle=\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right)^{\top} \left({\bm{A}}^{(t)}\right)^{-\frac{1}{2}}\left({\bm{A}}^{(t)}\right)^{\frac{1 }{2}}\bm{X}_{t}^{\top}\bm{z}_{t}$ $\displaystyle\leq\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{ \hat{\bm{A}}^{(t)}}\cdot\left\|\bm{X}_{t}^{\top}\bm{z}_{t}\right\|_{\left({\bm {A}}^{(t)}\right)^{-1}}$ $\displaystyle\leq\sqrt{2R^{2}\ln\left(\frac{1}{\delta}\left|\bm{A}^{(t)}\right |^{\frac{1}{2}}\left|\lambda\bm{I}\right|^{-\frac{1}{2}}\right)}\cdot\left\| \hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{\hat{\bm{A}}^{(t)}}.$ $$

According to equation 27, we have $\left|\hat{\bm{A}}^{(t)}\right|\geq\left|\bm{A}^{(t)}\right|$.
For any $t\in[T]$, since the rank of $\hat{\bm{A}}^{(t)}$ is at most $2l_{B_{t}}$, we can bound the determinant of $\hat{\bm{A}}^{(t)}$ as follows

$$ $\displaystyle\left|\hat{\bm{A}}^{(t)}\right|$ $\displaystyle\leq\left(\sum_{i=1}^{B_{t}}\alpha_{i}^{(t)}+\lambda\right)^{d-2l _{B_{t}}}\cdot\prod_{i=1}^{2l_{B_{t}}}\lambda_{i}\left(\hat{\bm{A}}^{(t)}\right)$ (29) $\displaystyle\leq\left(\sum_{i=1}^{B_{t}}\alpha_{i}^{(t)}+\lambda\right)^{d-2l _{B_{t}}}\left(\frac{\sum_{i=1}^{2l_{B_{t}}}\lambda_{i}\left(\hat{\bm{A}}^{(t) }\right)}{2l_{B_{t}}}\right)^{2l_{B_{t}}}$ $\displaystyle=\left(\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}+\lambda\right)^{d- 2l_{B_{t}}}\left[\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}+\lambda+\frac{\text{ Tr}\left(\sum_{i=1}^{B_{t}}\left(\bm{S}_{i}^{(t)}\right)^{\top}\bm{S}_{i}^{(t) }\right)}{2l_{B_{t}}}\right]^{2l_{B_{t}}}$ $\displaystyle\leq\left(\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}+\lambda\right)^ {d-2l_{B_{t}}}\left(\left(\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}-\frac{\sum_{ i=1}^{B_{t}}l_{i}\cdot\overline{\sigma}_{i}}{2l_{B_{t}}}\right)+\lambda+\frac{ TL^{2}}{2l_{B_{t}}}\right)^{2l_{B_{t}}},$ $$

where the last inequality satisfies due to

$$ $\displaystyle\text{Tr}\left(\sum_{i=1}^{B_{t}}\left(\bm{S}_{i}^{(t)}\right)^{ \top}\bm{S}_{i}^{(t)}\right)$ $\displaystyle=\sum_{i=1}^{B_{t}}\text{Tr}\left(\left(\bm{S}_{i}^{(t)}\right)^{ \top}\bm{S}_{i}^{(t)}\right)$ $\displaystyle=\sum_{s=1}^{t}\text{Tr}(\bm{x}_{s}^{\top}\bm{x}_{s})-\sum_{i=1}^ {B_{t}}l_{i}\cdot\overline{\sigma}_{i}$ $\displaystyle\leq TL^{2}-\sum_{i=1}^{B_{t}}l_{i}\cdot\overline{\sigma}_{i}.$ $$

Therefore, the variance error term can be bounded as

$$ $\displaystyle\hphantom{{}={}}\left(\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star} \right)^{\top}\bm{X}_{t}^{\top}\bm{z}_{t}$ $\displaystyle\leq\sqrt{2R^{2}\ln\left(\frac{1}{\delta}\left|\bm{A}^{(t)}\right |^{\frac{1}{2}}\left|\lambda\bm{I}\right|^{-\frac{1}{2}}\right)}\cdot\left\| \hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{\hat{\bm{A}}^{(t)}}$ $\displaystyle\leq\sqrt{2R^{2}\ln\left(\frac{1}{\delta}\left|\hat{\bm{A}}^{(t)} \right|^{\frac{1}{2}}\left|\lambda\bm{I}\right|^{-\frac{1}{2}}\right)}\cdot \left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{\hat{\bm{A}}^{(t)}}$ $\displaystyle\leq R\cdot\sqrt{2\ln\left(\frac{1}{\delta}\right)+(d-2l_{B_{t}}) \ln\left(1+\frac{\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}}{\lambda}\right)+2l_{ B_{t}}\cdot\ln\left(1+\frac{tL^{2}}{2l_{B_{t}}\lambda}+\frac{h_{t}}{\lambda} \right)}\cdot\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{\hat{ \bm{A}}^{(t)}}$ $\displaystyle\leq R\cdot\sqrt{2\ln\left(\frac{1}{\delta}\right)+d\ln\left(1+ \frac{\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}}{\lambda}\right)+2l_{B_{t}}\cdot \ln\left(1+\frac{tL^{2}}{2l_{B_{t}}\lambda}+\frac{h_{t}}{\lambda}\right)}\cdot \left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{\hat{\bm{A}}^{(t)}},$ $$

where $h_{t}=\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}-\frac{\sum_{i=1}^{B_{t}}l_{i}
\cdot\overline{\sigma}_{i}}{2l_{B_{t}}}$.

Sum up the bias error term and the variance error term and divide both sides by $\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{\hat{\bm{A}}^{(t)}}$ simultaneously, we have

$$ $\displaystyle\left\|\hat{\bm{\theta}}_{t}-\bm{\theta}_{\star}\right\|_{\hat{ \bm{A}}^{(t)}}$ $\displaystyle\leq R\cdot\sqrt{2\ln\left(\frac{1}{\delta}\right)+d\ln\left(1+ \frac{\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}}{\lambda}\right)+2l_{B_{t}}\cdot \ln\left(1+\frac{tL^{2}}{2l_{B_{t}}\lambda}+\frac{h_{t}}{\lambda}\right)}$ $\displaystyle\hphantom{{}={}}+H\cdot\sqrt{\lambda+\sum_{i=1}^{B_{t}}\overline{ \sigma}_{i}},$ $$

which concludes the proof.
∎
Next, we start to prove the regret.
Similar to the case using FD, since the algorithm uses the principle of optimism in the face of uncertainty to select the arm, we can bound instantaneous regret by equation 19.
Utilizing equation 19 and Cauchy-Schwartz inequality, we derive the following bound

$$ $\displaystyle\text{Regret}_{T}$ $\displaystyle=\sum_{t=1}^{T}\max_{\bm{x}\in\mathcal{X}}\bm{x}^{\top}\bm{\theta }_{\star}-\sum_{t=1}^{T}\bm{x}_{t}^{\top}\bm{\theta}_{\star}$ (30) $\displaystyle\leq 2\sum_{t=1}^{T}\min\left\{HL,\hat{\beta}_{t-1}(\delta)\cdot \|\bm{x}_{t}\|_{\left(\hat{\bm{A}}^{(t-1)}\right)^{-1}}\right\}$ $\displaystyle\leq 2\sum_{t=1}^{T}\hat{\beta}_{t-1}(\delta)\min\left\{\frac{L}{ \sqrt{\lambda}},\|\bm{x}_{t}\|_{\left(\hat{\bm{A}}^{(t-1)}\right)^{-1}}\right\}$ $\displaystyle\leq 2\cdot\max\left\{1,\frac{L}{\sqrt{\lambda}}\right\}\cdot\hat {\beta}_{T}(\delta)\cdot\sum_{t=1}^{T}\min\left\{1,\|\bm{x}_{t}\|_{\left(\hat{ \bm{A}}^{(t-1)}\right)^{-1}}\right\}$ $\displaystyle\leq 2\cdot\max\left\{1,\frac{L}{\sqrt{\lambda}}\right\}\cdot\hat {\beta}_{T}(\delta)\cdot\sqrt{T\sum_{t=1}^{T}\min\left\{1,\|\bm{x}_{t}\|_{ \left(\hat{\bm{A}}^{(t-1)}\right)^{-1}}^{2}\right\}}.$ $$

We present a lemma of RFD-sketched leverage scores to conclude the proof.

###### Lemma 3 .

$$ $\displaystyle\sum_{t=1}^{T}\min\left\{1,\|\bm{x}_{t}\|_{\left(\hat{\bm{A}}^{(t -1)}\right)^{-1}}^{2}\right\}\leq 2l_{B_{T}}\cdot\ln\left(1+\frac{TL^{2}}{2l_{ B_{T}}\lambda}+\frac{h_{T}}{\lambda}\right).$ $$

###### Proof.

Denote $\bm{C}_{t}=\hat{\bm{A}}^{(t-1)}+\bm{x}_{t}^{\top}\bm{x}_{t}$.
Notice that the first ${2l_{B_{t}}}$ eigenvalues of $\bm{C}_{t}$ are the same as $\hat{\bm{A}}^{(t)}$ while the other eigenvalues of $\bm{C}_{t}$ are $\sum_{i=1}^{B_{t}}\alpha_{i}^{(t-1)}+\lambda$.
Thus we can obtain $\frac{\left|\hat{\bm{A}}^{(t)}\right|}{\left|\bm{C}_{t}\right|}=\left(\frac{
\sum_{i=1}^{B_{t}}\alpha_{i}^{(t)}+\lambda}{\sum_{i=1}^{B_{t-1}}\alpha_{i}^{(t
-1)}+\lambda}\right)^{d-{2l_{B_{t}}}}$.

For the determinant of $\hat{\bm{A}}^{(t)}$, we have

$$ $\displaystyle\left|\hat{\bm{A}}^{(t)}\right|$ $\displaystyle=\left(\frac{\sum_{i=1}^{B_{t}}\alpha_{i}^{(t)}+\lambda}{\sum_{i= 1}^{B_{t-1}}\alpha_{i}^{(t-1)}+\lambda}\right)^{d-{2l_{B_{t}}}}\cdot\left|\bm{ C}_{t}\right|$ (31) $\displaystyle=\left(\frac{\sum_{i=1}^{B_{t}}\alpha_{i}^{(t)}+\lambda}{\sum_{i= 1}^{B_{t-1}}\alpha_{i}^{(t-1)}+\lambda}\right)^{d-{2l_{B_{t}}}}\cdot\left|\hat {\bm{A}}^{(t-1)}\right|\cdot{\left|\bm{I}+\left(\hat{\bm{A}}^{(t-1)}\right)^{- 1}\bm{x}_{t}^{\top}\bm{x}_{t}\right|}$ $\displaystyle=\left(\frac{\sum_{i=1}^{B_{t}}\alpha_{i}^{(t)}+\lambda}{\sum_{i= 1}^{B_{t-1}}\alpha_{i}^{(t-1)}+\lambda}\right)^{d-{2l_{B_{t}}}}\cdot\left|\hat {\bm{A}}^{(t-1)}\right|\cdot{\left({1+\|\bm{x}_{t}\|_{\left(\hat{\bm{A}}^{(t-1 )}\right)^{-1}}^{2}}\right)}$ $\displaystyle=\left(\frac{\sum_{i=1}^{B_{t}}\overline{\sigma}_{i}+\lambda}{ \lambda}\right)^{d-{2l_{B_{t}}}}\cdot\left|\lambda\bm{I}\right|\cdot\prod_{s=1 }^{t}{\left({1+\|\bm{x}_{s}\|_{\left(\hat{\bm{A}}^{(s-1)}\right)^{-1}}^{2}} \right)}.$ $$

Since $\min{(1,x)}\leq 2\ln{(1+x)}$ for all $x\geq 0$, using equation 31, we can derive the following bound

$$ $\displaystyle\hphantom{{}={}}\sum_{t=1}^{T}\min\left\{1,\|\bm{x}_{t}\|_{\left( \hat{\bm{A}}^{(t-1)}\right)^{-1}}^{2}\right\}$ $\displaystyle\leq 2\sum_{t=1}^{T}\ln\left(1+\|\bm{x}_{t}\|_{\left(\hat{\bm{A}} ^{(t-1)}\right)^{-1}}^{2}\right)$ $\displaystyle=2\cdot\ln\left(\left(\frac{\lambda}{\sum_{i=1}^{B_{T}}\overline{ \sigma}_{i}+\lambda}\right)^{d-2l_{B_{T}}}\cdot\frac{\left|\hat{\bm{A}}^{(T)} \right|}{\left|\lambda\bm{I}\right|}\right)$ $\displaystyle\leq 2l_{B_{T}}\cdot\ln\left(1+\frac{TL^{2}}{2l_{B_{T}}\lambda}+ \frac{h_{T}}{\lambda}\right),$ $$

where the last step holds by equation 29 and $h_{T}=\sum_{i=1}^{B_{T}}\overline{\sigma}_{i}-\frac{\sum_{i=1}^{B_{T}}l_{i}
\cdot\overline{\sigma}_{i}}{2l_{B_{T}}}$.
∎

We combine equation 30, Theorem 6 and Lemma 3. Assume $L\geq\sqrt{\lambda}$, we have

$$ $\displaystyle\text{Regret}_{T}$ $\displaystyle=\sum_{t=1}^{T}\max_{\bm{x}\in\mathcal{X}}\bm{x}^{\top}\bm{\theta }_{\star}-\sum_{t=1}^{T}\bm{x}_{t}^{\top}\bm{\theta}_{\star}$ $\displaystyle\leq 2\cdot\max\left\{1,\frac{L}{\sqrt{\lambda}}\right\}\cdot\hat {\beta}_{T}(\delta)\cdot\sqrt{T\sum_{t=1}^{T}\min\left\{1,\|\bm{x}_{t}\|_{ \left(\hat{\bm{A}}^{(t-1)}\right)^{-1}}^{2}\right\}}$ $\displaystyle\overset{\tilde{O}}{=}\frac{L}{\sqrt{\lambda}}\cdot\sqrt{T}\cdot \sqrt{2l_{B_{T}}\cdot\ln\left(1+\frac{TL^{2}}{2l_{B_{T}}\lambda}+\frac{h_{T}}{ \lambda}\right)}\cdot\Bigg{(}H\cdot\sqrt{\lambda+\sum_{i=1}^{B_{T}}\overline{ \sigma}_{i}}+$ $\displaystyle\hphantom{{}={}}R\cdot\sqrt{d\ln\left(1+\frac{\sum_{i=1}^{B_{T}} \overline{\sigma}_{i}}{\lambda}\right)+2l_{B_{T}}\cdot\ln\left(1+\frac{TL^{2}} {2l_{B_{T}}\lambda}+\frac{h_{T}}{\lambda}\right)}\Bigg{)}.$ $$

According to Theorem 2, we can bound the spectral error by error $\epsilon$, which is

$$ $\displaystyle\text{Regret}_{T}$ $\displaystyle\overset{\tilde{O}}{=}\frac{L}{\sqrt{\lambda}}\cdot\sqrt{\ln\left (1+\frac{TL^{2}}{2l_{B_{T}}\lambda}+\frac{h_{T}}{\lambda}\right)}\cdot\Bigg{(} H\cdot\sqrt{\lambda+\epsilon}+$ $\displaystyle\hphantom{{}={}}R\cdot\sqrt{d\ln\left(1+\frac{\epsilon}{\lambda} \right)+2l_{B_{T}}\cdot\ln\left(1+\frac{TL^{2}}{2l_{B_{T}}\lambda}+\frac{h_{T} }{\lambda}\right)}\Bigg{)}$ $\displaystyle\overset{\tilde{O}}{=}\frac{L}{\sqrt{\lambda}}\cdot\sqrt{\ln\left (1+\frac{TL^{2}}{2l_{B_{T}}\lambda}+\left(1-\frac{2-B_{T}}{2^{B_{T}+1}}\right) \cdot\frac{\epsilon}{\lambda}\right)}\cdot\Bigg{(}H\cdot\sqrt{\lambda+\epsilon}+$ $\displaystyle\hphantom{{}={}}R\cdot\sqrt{d\ln\left(1+\frac{\epsilon}{\lambda} \right)+2l_{B_{T}}\cdot\ln\left(1+\frac{TL^{2}}{2l_{B_{T}}\lambda}+\left(1- \frac{2-B_{T}}{2^{B_{T}+1}}\right)\cdot\frac{\epsilon}{\lambda}\right)}\Bigg{)},$ $$

where the last inequality holds because

$$ $\displaystyle h_{T}$ $\displaystyle=\sum_{i=1}^{B_{T}}\overline{\sigma}_{i}-\frac{\sum_{i=1}^{B_{T}} l_{i}\cdot\overline{\sigma}_{i}}{2l_{B_{T}}}$ $\displaystyle=\sum_{i=1}^{B_{T}}\left(1-\frac{2^{i-1}}{2^{B_{T}}}\right)\cdot \overline{\sigma}_{i}$ $\displaystyle\leq\epsilon\cdot\sum_{i=1}^{B_{T}}\left(1-\frac{2^{i-1}}{2^{B_{T }}}\right)\cdot\frac{1}{2^{i}}=\left(1-\frac{2-B_{T}}{2^{B_{T}+1}}\right)\cdot\epsilon$ $$

###### Lemma 3 .

###### Proof.

## Appendix G Properties of Dyadic Block Sketching for RFD

In this section, we highlight two significant properties of Dyadic Block Sketching for RFD that elucidate why the regret bound of DBSLinUCB using RFD is improved.
Although Robust Frequent Directions for ridge regression have been studied by Luo et al. (), their theory is limited to single deterministic streaming sketches.
We demonstrate that the decomposability of multi-scale sketching does not alter the properties of RFD.

We begin with the positive definite monotonicity of Dyadic Block Sketching for RFD, which ensures that the sequence of approximation matrices is per-step optimal.

###### Theorem 7 (Positive Definite Monotonicity) .

At round $t$, denote that the Dyadic Block Sketching for RFD provides a sketch $\bm{S}^{(t)}$, we have the following equation

$$ $\left(\bm{S}^{(t)}\right)^{\top}\bm{S}^{(t)}+\alpha^{(t)}\bm{I}\succeq\left( \bm{S}^{(t-1)}\right)^{\top}\bm{S}^{(t-1)}+\alpha^{(t-1)}\bm{I}.$ $$

###### Proof.

Notice that $\alpha^{(t)}\bm{I}+\left(\bm{S}^{(t)}\right)^{\top}\bm{S}^{(t)}=\sum_{i=1}^{B_
{t}}\alpha_{i}^{(t)}\bm{I}+\sum_{i=1}^{B_{t}}\left(\bm{S}_{i}^{(t)}\right)^{
\top}\bm{S}_{i}^{(t)}$, where $\bm{S}_{i}^{(t)}$ is the sketch matrix in block $i$ and $\alpha_{i}^{(t)}$ is the adaptive regularization term of RFD at round $t$.

Let $\bm{Q}=\left[\left(\bm{S}_{B_{t}}^{(t-1)}\right)^{\top},\bm{x}_{t}^{\top}
\right]^{\top}$, $\sigma_{t}$ is the shrinking singular values of active block at round $t$, the shrinking step of RFD provides

$$ $\displaystyle\sum_{i=1}^{B_{t}}\left(\bm{S}_{i}^{(t)}\right)^{\top}\bm{S}_{i}^ {(t)}+\sigma_{t}\bm{I}\succeq\sum_{i=1}^{B_{t}-1}\left(\bm{S}_{i}^{(t)}\right) ^{\top}\bm{S}_{i}^{(t)}+\bm{Q}^{\top}\bm{Q}\succeq\sum_{i=1}^{B_{t-1}}\left( \bm{S}_{i}^{(t-1)}\right)^{\top}\bm{S}_{i}^{(t-1)}.$ (32) $$

Therefore, for any unit vector $\bm{a}$, we have

$$ $\displaystyle\hphantom{{}={}}\bm{a}^{\top}\left(\left(\bm{S}^{(t)}\right)^{ \top}\bm{S}^{(t)}+\alpha^{(t)}\bm{I}-\left(\bm{S}^{(t-1)}\right)^{\top}\bm{S}^ {(t-1)}+\alpha^{(t-1)}\bm{I}\right)\bm{a}$ $\displaystyle=\bm{a}^{\top}\left(\sum_{i=1}^{B_{t}}\alpha_{i}^{(t)}\bm{I}+\sum _{i=1}^{B_{t}}\left(\bm{S}_{i}^{(t)}\right)^{\top}\bm{S}_{i}^{(t)}-\sum_{i=1}^ {B_{t-1}}\alpha_{i}^{(t-1)}\bm{I}-\sum_{i=1}^{B_{t-1}}\left(\bm{S}_{i}^{(t-1)} \right)^{\top}\bm{S}_{i}^{(t-1)}\right)\bm{a}$ $\displaystyle=\bm{a}^{\top}\left(\sum_{i=1}^{B_{t}}\left(\bm{S}_{i}^{(t)} \right)^{\top}\bm{S}_{i}^{(t)}+\sigma_{t}\bm{I}-\sum_{i=1}^{B_{t-1}}\left(\bm{ S}_{i}^{(t-1)}\right)^{\top}\bm{S}_{i}^{(t-1)}\right)\bm{a}$ $\displaystyle\geq 0,$ $$

which concludes the proof.
∎

Next, we prove that the sketch matrix produced by Dyadic Block Sketching for RFD is better conditioned than those produced by Dyadic Block Sketching for FD and the covariance matrix.
In this context, the $\alpha$ selected by RFD is optimal, as choosing a smaller $\alpha$ would result in a worse condition number for the approximation matrices.

###### Theorem 8 (Well-Conditioned Property) .

Let $\textup{cond}(\bm{X})=\frac{\sigma_{\max}(\bm{X})}{\sigma_{\min}(\bm{X})}$ be the condition number of matrix $\bm{X}$.
At round $t$, denote that the Dyadic Block Sketching for RFD provides a sketch $\bm{S}^{(t)}$, we have

$$ $\displaystyle\textup{cond}\left(\left(\bm{S}^{(t)}\right)^{\top}\bm{S}^{(t)}+ \alpha^{(t)}\bm{I}+\lambda\bm{I}\right)$ $\displaystyle\leq\textup{cond}\left(\left(\bm{S}^{(t)}\right)^{\top}\bm{S}^{(t )}+\lambda\bm{I}\right),$ $\displaystyle\textup{cond}\left(\left(\bm{S}^{(t)}\right)^{\top}\bm{S}^{(t)}+ \alpha^{(t)}\bm{I}+\lambda\bm{I}\right)$ $\displaystyle\leq\textup{cond}\left(\bm{X}_{t}^{\top}\bm{X}_{t}+\lambda\bm{I} \right).$ $$

###### Proof.

Notice that $\alpha^{(t)}\bm{I}+\left(\bm{S}^{(t)}\right)^{\top}\bm{S}^{(t)}=\sum_{i=1}^{B_
{t}}\alpha_{i}^{(t)}\bm{I}+\sum_{i=1}^{B_{t}}\left(\bm{S}_{i}^{(t)}\right)^{
\top}\bm{S}_{i}^{(t)}$, where $\bm{S}_{i}^{(t)}$ is the sketch matrix in block $i$ and $\alpha_{i}^{(t)}$ is the adaptive regularization term of RFD at round $t$.
We have

$$ $\displaystyle\textup{cond}\left(\left(\bm{S}^{(t)}\right)^{\top}\bm{S}^{(t)}+ \alpha^{(t)}\bm{I}+\lambda\bm{I}\right)$ $\displaystyle=\frac{\sigma_{\max}\left(\sum_{i=1}^{B_{t}}\left(\bm{S}_{i}^{(t) }\right)^{\top}\bm{S}_{i}^{(t)}\right)+\lambda+\sum_{i=1}^{B_{t}}\alpha_{i}^{( t)}}{\lambda+\sum_{i=1}^{B_{t}}\alpha_{i}^{(t)}}$ $\displaystyle\leq\frac{\sigma_{\max}\left(\sum_{i=1}^{B_{t}}\left(\bm{S}_{i}^{ (t)}\right)^{\top}\bm{S}_{i}^{(t)}\right)+\lambda}{\lambda}$ $\displaystyle=\textup{cond}\left(\left(\bm{S}^{(t)}\right)^{\top}\bm{S}^{(t)}+ \lambda\bm{I}\right).$ $$

Similarly, we have

$$ $\displaystyle\textup{cond}\left(\left(\bm{S}^{(t)}\right)^{\top}\bm{S}^{(t)}+ \alpha^{(t)}\bm{I}+\lambda\bm{I}\right)$ $\displaystyle=\frac{\sigma_{\max}\left(\sum_{i=1}^{B_{t}}\left(\bm{S}_{i}^{(t) }\right)^{\top}\bm{S}_{i}^{(t)}\right)+\lambda+\sum_{i=1}^{B_{t}}\alpha_{i}^{( t)}}{\lambda+\sum_{i=1}^{B_{t}}\alpha_{i}^{(t)}}$ $\displaystyle\leq\frac{\sigma_{\max}\left(\bm{X}_{t}^{\top}\bm{X}_{t}\right)+ \lambda+\sum_{i=1}^{B_{t}}\alpha_{i}^{(t)}}{\lambda+\sum_{i=1}^{B_{t}}\alpha_{ i}^{(t)}}$ $\displaystyle\leq\frac{\sigma_{\max}\left(\bm{X}_{t}^{\top}\bm{X}_{t}\right)+ \lambda}{\lambda}$ $\displaystyle\leq\textup{cond}\left(\bm{X}_{t}^{\top}\bm{X}_{t}+\lambda\bm{I} \right),$ $$

which concludes the proof.
∎

###### Theorem 7 (Positive Definite Monotonicity) .

###### Proof.

###### Theorem 8 (Well-Conditioned Property) .

###### Proof.

## Appendix H Open Access to Data

MNIST: [http://yann.lecun.com/exdb/mnist/](http://yann.lecun.com/exdb/mnist/)

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: (several questions are included as part of concerns mentioned above)
soundness: 3
strengths: - The general topic of improving trade-offs in per-round computation and regret in online learning is important. 

- The authors clearly lay out an important issue with standard stochastic linear bandit methods with the dimension is large enough that per-round computation can be a concern. 

- The proposed method is interesting, using a decomposition property to control the overall spectral norm error and then carefully designing block sizes adaptively.  It is integrated using standard matrix sketching methods (FD and RFD) to form new LinUCB variants for which the authors obtain regret bounds.  

- The presentation overall is good.  

- Experiments are included on synthetic and real-world data, showing that the method can perform competitively with non-sketching methods while reducing per-round computation significantly.
summary: The authors consider stochastic linear bandits when the dimension $d$ is high enough that per-round computational complexity is of concern to the user.  Traditional methods have high per-round computational complexity with respect to the dimension size $d$ due to covariance matrix estimators used.  Sketching based variants have been proposed to alleviate the computational complexity, but require pre-selecting the sketch size $l$ which can lead to high-regret (there is a regret bound term related to error from sketching (with size $l$) that can exhibit horizon dependence).  The authors propose a new sketching method that adaptively selects the sketch size subject to a parameter controlling the sketching error.  They derive regret bounds and show experiments demonstrating that it can empirically achieve a superior tradeoff of regret and computation.
weaknesses: ### Major 

- My biggest concern is with regards to prior works.  There is a brief related works discussion on sketching (no recent works) and no mention of similarities or differences in the methodology section.  Is this Dyadic Block Sketching technique completely new?  Three classes of matrix sketching methods are described none of which seemed (to me) to be particularly similar.   

    - However, there is at least one (slightly more recent) paper that is not cited but sounds fairly relevant: a 2016 sigmod https://dl.acm.org/doi/abs/10.1145/2882903.2915228 paper which proposes a “Dyadic Interval framework” that sounds similar—it is also based on the decomposability property, it also involves specifying an error hyper-parameter, has a logarithmic number of ‘levels’, and there is a check of a L2 norm based block size that triggers updating; they also combine it with the “Frequent Directions” method.   

    - The citations included in that section are old, with the most recent paper in that section of related work being a 2014 review paper.   

 

- Another concern I have is with the role of $\epsilon$.  I think it is quite interesting to go from fixing a sketch size and possibly incurring large regret to fixing an error bound in part of the estimation scheme.  Given there is a different hyperparameter,  it would have been better to have more discussion and also some experiments showing how the choice of $\epsilon$ impacts the spectral norm errors, the regret, and the computation.  In the experiments a seemingly large constant $\epsilon=2000$ is used for two sets of experiments, $\epsilon = 1000$ in another, but I do not have a sense where those came from.  For sketch size, by contrast, the user knows $d$ and at least for a target computational budget could probably fairly easily select a sketch size that would fit well within that (with the caveat being of course it might incur large error).          

    - 5.1 Matrix approximation experiment – only one value of $\epsilon$ is used (also computation time and sketch sizes method used are not reported for that $\epsilon$); 

    - 5.3 experiment on MNIST, “In contrast, DBSLinUCB matches the performance of OFUL by adaptively adjusting the sketch size to the near-optimal value of l = 200 while being significantly faster than OFUL.” empirical regret is shown so clearly is close to OFUL and time is shown for this experiment so is clear is close to SOFUL(l=200), which is suggestive sketch sizes would be similar (around 200) but did  you actually check that?  Or are you basing that on the total run-time? 

    - in experiment 5.3, the $\epsilon$ was changed compared to previous experiments? Why?  How was this value chosen? 

 

 

### Minor 

- the computational complexity (and relatedly realized sketch sizes) are not reported.  In the first experiment the spectral norm error is shown (so tradeoff FD makes is clear) but no mention of the extent to which computation time is traded off.   

- in section 5.1, is there a reason FD does better for small number of rows than DBS-FD?   

- theorem 1’s statement is poorly written for a formal theorem.  It also contains a notable typo “$\Omega(T^2)$” for regret bound

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 2
questions: See weaknesses.
soundness: 3
strengths: The authors demonstrate that Frequent Directions (FD), a previously utilized matrix sketching method, could lead to linear regret. They introduce a dyadic block sketching method where the sketch size is adaptively adjusted based on the parameter $\epsilon$. The main theorem asserts that the proposed algorithm achieves favorable regret bounds, and experimental results highlight its effectiveness and efficiency.
summary: This paper studies matrix sketching within the context of linear bandits, aiming to reduce time complexity.

The authors demonstrate that Frequent Directions (FD), a previously utilized matrix sketching method, could lead to linear regret. They introduce a dyadic block sketching method where the sketch size is adaptively adjusted based on the parameter $\epsilon$. The main theorem asserts that the proposed algorithm achieves favorable regret bounds, and experimental results highlight its effectiveness and efficiency.
weaknesses: However, there are several weaknesses:

1. The comparison with previous work is overly simplistic and lacks sufficient detail. In previous work, $l$ represents a trade-off between time complexity and regret. This work uses $\epsilon$. The authors should provide a comprehensive analysis of the trade-off (including time complexity at each step, memory costs, assumptions, and regret) to elucidate the advantages of the new method.
2. Although a regret lower bound is established for the previous algorithm, it is unclear how the proposed algorithm performs under the worst-case scenario constructed.
3. The algorithm searches for parameters in the experiments. However, the main theorems do not hold for these parameters. It would be beneficial if the authors could also present experimental results that consider scaling the parameters.

Additionally, in Theorem 1, the stated regret is $T^2$, which is unusual since the worst-case scenario typically scales linearly with $T$. Could the authors clarify this discrepancy?

---

confidence: 2
contribution: 2
initial_rating: 6
presentation: 2
questions: - Did you run any additional experiments on more diverse real-world datasets to better investigate the method's adaptability to varying spectral properties? If so, what did you observe? 
- Given the increased complexity of managing blocks and adaptive sketch sizes, how does Dyadic Block Sketching compare in terms of computational complexity to simpler, single-scale sketching approaches in real-world applications?
- The paper suggests improved regret bounds when favorable conditions are met. Could you elaborate on how practical these improvements are in some examples of real-life scenarios?
soundness: 2
strengths: - The topic of balancing computational efficiency with accurate regret minimization in high-dimensional settings is of broad interest
- The writing is mostly clear
summary: This work explores the limitations of current sketching techniques in online learning, particularly within linear bandit settings. Existing methods using matrix sketching suffer from high spectral error, leading to potential linear regret when the covariance matrix's spectral tail does not decay rapidly. The authors propose a novel approach, Dyadic Block Sketching, which adaptively adjusts sketch size to control spectral error. This new technique aims to achieve sublinear regret without prior knowledge of the covariance matrix, presenting a potentially generalizable framework for improving efficiency and regret bounds in sketch-based linear bandits.
weaknesses: - Magnitude of the technical novelty and practical impact of the contributions

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 1
questions: 1) Several things I can't understand in Theorem 1

1-1) If I understood correctly, the arm is drawn randomly from a 'fixed' arbitrary distribution over a set of $r$ arms. Now in this case, what is the point of the sketching? The regret above (by Kuzborskij et al) is the regret of the sketch-based linear bandit. This fixed random sampling is not the algorithm by Kuzborskij et al (2019). What is the connection?

1-2) Also, no algorithm could achieve a 'square regret' $\Omega(T^2)$. It is impossible since the worst possible regret is $T$. I can barely guess that the authors want to mention the 'upper bound' of the expected regret using FD is $\Omega(T^2)$, but it is not super surprising, since it is an 'upper bound'. For example, in $K$-armed bandit, the worst case regret bound is of $\sqrt{KT}$, and if $K=T^2$, the regret 'upper bound' is $T^{3/2}$ but it is not surprising since it is just an upper bound. 

2) I failed to understand Algorithm 1. Here are the issues I found. 

**2-Major**

- If I understood correctly when the algorithm updates, the B[i].length should increase. The term 'rank' is the block's rank, actually. How could a rank be larger than the length? It feels like for $d_1 \times d_2$ dimensional rank $r$ matrix, you are saying 'when $d_1 < r$'.
- What is the second condition in line 276, 'The sum of sketch rows stored in blocks should be less than $d$'? Rows are vectors and $d$ is a scalar.  
- Similar to this question, How could a block contain the size $\epsilon l_0$ while doubling the length? In my intuition, each $x_t$ corresponds to the actions chosen by the LinUCB algorithm. Whatever your sketch is, you add $B[i].size +=\|\|x_t\|\|^2$. How can you make the length be doubled while maintaining the same B[i].size for each block?
- The authors mentioned three key invariants that should be maintained - (B[i].length>rank, $B[i].size< l_0 \epsilon$, and the strange condition above). However, in line 8 of Algorithm 1, they used 'AND' logic. Is it right?

**2-Minor**

- $l_0$ is 'sketch size' and you are using the term $B[i].size$ differently. It is very confusing. 
- Also the term 'rank' is very confusing. I know they defined rank around line 317, but it's hard to find what it is.
- What is Line 12? The authors should 'define' how each sketching algorithm works, or at least direct readers to a certain part. 
- At least use a different font or something for Sk. 
- Also, I was about the point out the computational inefficiency of lines 16-18 of Algo 1. I just found that you mentioned in lines 324-326, but it is not intuitive at all. The main point that this paper sells is the computational efficiency, and this part looks like updating all the sketch matrices for each timestep which is not efficient. 

3) Also, in Section 2.1, I think they should add some remarks about the rank-$l$ SVD. This algorithm needs rank-$l$ SVD for each time (For Eq. (3), right?) and they intentionally omitted the cost in lines 157-161. As the previous work did, they should add a remark to avoid any doubts about their honesty.

4) The result in Theorem 3 seems much more intertwined in terms of $\lambda$, much more complicated than the previous work of Kuzborskij. Can authors state whether their results are better than Kuzborskij or not in terms of $\lambda$?

5) How large is your error parameter? Is there no assumption needed on $\epsilon$? As we all know, most of the researchers use the character $\epsilon$ as a 'very small quantity smaller than 1'. However in this work, in their experiments, they used $\epsilon = 2000$, much larger than their dimension $d=100$. Are you sure that this $\epsilon$ does not hide any important terms, such as dimensionality?



Overall, I encourage the authors to further refine their paper to bring out its full potential if they believe it has significant contributions to offer.
soundness: 3
strengths: The authors proposed a novel and flexible algorithm, DBS, which optimizes its sketching size as the number of samples increases. Adding a doubling trick to the sketching will not be easy, so **if their result is true**, I want to give some points on the novelty, soundness, and significance of this algorithm. 

Not only that, they also actually improved the regret bound of the bandit algorithm from the previous work [Kuzborskij et al.., 2019] to a more flexible result. Previously, the result relied on the term called 'spectral error', which is relatively vague and depends on a fixed sketch size. According to their literature search, there was almost no improvement after [Kuzborskij et al., 2019] for 5 years, and they finally made a more flexible and tighter result than before, **if their results are true.**
summary: The authors proposed a new sketching method called dyadic block sketching. This sketching method does not need a fixed sketch size as other sketching methods do, and can adaptively adjust the sketch size based on the error. Using this Dyadic Block Sketching, the authors proposed a bandit algorithm called DBSLinUCB which modifies the traditional OFUL algorithm a bit and achieves an improved regret bound compared to the traditional method of [Kujborskij et al., 2019].
weaknesses: Overall, because of clarity issues, I cannot trust the soundness of their result now. 

1) Their presentation about the lower bound is poor. I don't understand what the authors want to say in Theorem 1. Please check the 'Questions' section below. 

2) Also, Algorithm 1 is the core of this paper, but it is very hard to understand from many perspectives and is not clearly written. Please check the 'Questions' section below. 


3) Clarity problems

3-1) Figure 1 - It is really strange that the regret is much larger than the number of timesteps. After I checked the experimental details, they set the arm set $a \sim N(0,I_d)$ and this is the reason why they had a large regret. Also, this means they reported only one experiment, not the average result of repetitions (If not, all their regret should fluctuate a lot). I know that experiments are not the main focus of bandit papers, but this is not a good tradition.

3-2) In Lemma 1, it would be great if they could add the 'size' of each $X_i \in \mathbb{R}^{n_i \times d}$ so that the readers could understand how the submatrices look like. I was a bit confused in Lemma 1 since they didn't define the concatenation $[X_1, X_2]$ before.
2-3) In Section 2.1, they should add their SVD computations, or mention their efficient way of updating parameters $S^{(t)}$ and $M^{(t)}$

4) It seems like it is an improvement from the previous work [Kuzborskij et al., 2019], but I doubt that their result has $(R+L\sqrt{\lambda})$ term in their result. The LinUCB algorithm has a regret bound of $Rd\sqrt{T}$. The form looks quite problematic if $R$ and $L$ are in different scales. I know that the previous work also had this issue, but it is still true that this kind of (variance + arm set scale) is not a good thing in practice, especially when $R<<H$. See Questions section for my doubt on $\lambda$.

Meta-review: Recognizing that existing sketching methods for speeding up linear bandit algorithms perform poorly when the rank of the problem is not small compared to the sketching dimension, this paper presents a method for adjusting the sketching dimension "on the fly" to adapt to the problem rank. While all reviewers saw merit in the paper, the overall novelty and conceptual contribution are somewhat limited compared to other submissions. While nice to have proven, the conceptual message behind the lower bounds provided by the paper is expected, and the approach of adaptively adjusting the sketch requires effort to develop, but does not represent a major new idea. That said, we appreciate the authors' engagement with the reviewers and the relative clarity of the paper, and wish the authors the best of luck submitting to another venue.

Decision: Reject