Efficient Linear Bandits via Cluster-Aware Sketching

1 Introduction

• Classical LinUCB and linear Thompson Sampling incur O(d2) per-round updates, while global-sketch methods such as SOFUL [7] and CBSCFD can suffer linear regret under heavy-tailed spectra.DBSLinUCB [10] guarantees sublinear regret using adaptive sketch-size growth, but its guarantees do not extend to fixed sketch size and its efficiency relies on low-rank data.Source: §1 · pp. 1–2
• CS-LB is presented as a sketching-based bandit strategy designed to deliver regret convergence in computation-constrained settings.The authors describe it as the first such strategy to combine convergence guarantees with a fixed sketch size.Source: §1 · p. 2
• The algorithm partitions arms into clusters and maintains a dedicated sketch for each, preserving each cluster’s information integrity as the basis for regret convergence.Each cluster’s sentinel is its arms’ maximum upper confidence bound, enforcing global optimism in the spirit of OFUL.Source: §1 · p. 2
• CS-LB has a regret bound of eO(lAT) and per-round cost O(l2d), excluding warm-up overhead, when l2 < d; its bound omits the spectral error term and applies to fixed sketches and full-rank data.The one-time warm-up overhead becomes a constant term when the horizon is sufficiently large.Source: §1 · p. 2
• Synthetic experiments show CS-LB consistently beats SOFUL and CBSCFD in cumulative regret, with the largest gains on naturally clustered action sets, and runs faster than OFUL.The reported results are on synthetic data.Source: §1 · p. 2

2 Related Work

• Early linear-bandit work introduced confidence-bound techniques, with LinRel improving the stated regret bound from eO(T3/4) to eO(T).The passage also notes extensions to more general compact action sets.Source: §2 · p. 2
• LinUCB [1] uses upper confidence bounds and was applied to personalized recommendation, while OFUL uses a tighter confidence set and linear Thompson Sampling [6] samples a parameter from its posterior.The passage reports linear Thompson Sampling’s performance as comparable to OFUL up to logarithmic factors.Source: §2 · p. 2
• Frequent Directions [8] supports online sketching; SOFUL [7] combined it with OFUL to reduce update costs, and CBSCFD developed a variant with a tighter regret bound.DBSLinUCB [10] uses multi-scale adaptive sketching to guarantee sublinear regret without prior knowledge of the data spectrum; this paper instead focuses on fixed sketch size.Source: §2 · p. 2

3.1 Notation and Definition

• The paper defines its matrix and vector notation, including SVD, singular values, finite-set cardinality, and eO bounds that omit logarithmic factors.Every d-dimensional vector is represented as a column vector.Source: §3.1 · p. 3

3.2 Stochastic Linear Bandits

• The learner selects from a finite arm set, observes a noisy linear reward, and seeks to minimize cumulative regret relative to the arm maximizing expected reward.The model assumes conditionally R-sub-Gaussian noise and bounded parameter and action norms.Source: §3.2 · p. 3

3.3 Computation efficiency

• High-dimensional linear-bandit updates remain costly in real-time settings, motivating methods that trade computational cost against statistical accuracy.The passage notes that computation beyond the per-round budget can degrade service or revenue.Source: §3.3 · p. 3

3.4 Sketch

• Frequent Directions truncates the smallest singular value after an SVD update, reducing per-round computation from O(d^2) to O(ld) at the cost of doubling space.Sketching maintains an l × d matrix in place of the selected-action matrix.Source: §3.4 · p. 3
• Sketching replaces the full action-history matrix with an l × d approximation for policy updates, reducing update cost but risking information loss and non-convergence.Frequent Directions truncates singular values; spectral compensation accumulates truncated mass as a diagonal correction, but heavy spectral tails can still prevent convergence.Source: §3.4 · pp. 3–4
• Spectral compensation accumulates discarded spectral mass as a diagonal correction, improving conditioning while retaining the heavy-tail non-convergence issue.The compensated covariance sequence is monotone, but the error bound remains the same as for Frequent Directions.Source: §3.4 · p. 4

4 Algorithm

• CS-LB is designed to improve computational efficiency while ensuring regret convergence with a fixed sketch size.The section introduces the algorithm as a response to limitations in computationally efficient linear-bandit methods.Source: §4 · p. 4

4.1 Limitations of Existing Approaches

• OFUL has rigorous regret guarantees, but its per-round update cost is prohibitive in high-dimensional, computation-constrained settings.The section identifies this cost as a deployment difficulty for OFUL.Source: §4.1 · p. 4
• SOFUL and CBSCFD remain vulnerable to linear regret when heavy spectral tails make the spectral-error term grow with T.CBSCFD reduces SOFUL’s error term but still carries a risk of linear regret; FD sketching can also discard information on full-rank data.Source: §4.1 · p. 4, §4.2 · p. 5
• DSBLinUCB uses adaptively growing sketch sizes and assumes low-rank data, limiting its fit for fixed-size settings and full-rank heavy-tailed data.In the latter setting, its time complexity increases to O(d^2).Source: §4.1 · p. 4

4.2 Cluster Sketch Linear Bandits

• Arms are partitioned into clusters whose ranks do not exceed l, and each cluster maintains its own sketch to preserve local covariance information.An arm joins a cluster only if its inclusion keeps the cluster rank at most l; otherwise, another cluster is sought or a new one is formed.Source: §4.2 · p. 5
• Within each cluster, the FD update incurs no information loss, which the method identifies as the basis for regret convergence.The warm-up procedure bounds each cluster’s arm-matrix rank by the sketch size l.Source: §4.2 · p. 5
• Each cluster’s sentinel is its maximum arm-level upper confidence bound; CS-LB selects the cluster with the largest sentinel before choosing an arm within it.After warm-up, the within-cluster selection behaves as a rank-l LinUCB update.Source: §4.2 · pp. 5–6
• CS-LB’s per-round complexity is O(l^2 d), stemming from SVD decomposition; traditional OFUL incurs O(d^2) cost for computing the inverse matrix, a significant reduction in computational overhead.Source: §4.2 · p. 6

5.1 Regret Analysis

• For any sketch size l > 1, CS-LB’s finite-arm regret bound eliminates the spectral-error term and guarantees regret convergence.Source: §5.1 · p. 6
• In the worst case, the regret bound depends on data scale N; strong linear correlation can reduce cluster count N_A, and N_A < d permits lower computation and better regret than OFUL.N_A is the number of clusters produced by cluster-sketch warm-up.Source: §5.1 · pp. 6–7

5.2 Computation Analysis

• Online updates cost O(l^2d), with SVD as the dominant operation within clusters of rank at most l.The sketch size l can be tuned in advance.Source: §5.2 · p. 7
• Warm-up checks each arm against existing clusters; its actual cost is below the worst-case bound and it is a one-time overhead that becomes constant for sufficiently large T.Source: §5.2 · p. 7

6.1 Baseline

• The baselines span UCB1’s low-cost, linear-structure-agnostic approach, OFUL’s tight regret guarantee with O(d^2) cost, and sketching methods’ computational savings and regret risks.SOFUL risks linear regret with an unsuitable sketch size; CBSCFD’s tighter theoretical bound does not address linear regret from a heavy spectral tail.Source: §6.1 · p. 8

6.2 Experimental Setup

• Synthetic arms use independently uniform components, random integer scaling, and normalization; the two convergence datasets use (N, d, l) = (60, 50, 5) and (100, 50, 10).The UCB1 comparison uses correlated datasets (100, 50, 10, 2) and (200, 50, 5, 10), specified as (N, d, l, m_l).Source: §6.2 · p. 8, §6.3 · p. 8, §6.4 · p. 9

6.3 Regret Convergence Verification

• On both convergence datasets, results match the analysis: SOFUL and CBSCFD fail to converge at the chosen sketch sizes, while CS-LB is expected to attain the smallest regret.The regret results are averaged over five independent runs.Source: §6.3 · p. 8, Figure 1 · p. 9
• CS-LB has slightly lower running time than SOFUL and CBSCFD on these datasets, with cluster-restricted arm search also lowering search overhead.Source: §6.3 · p. 8, Figure 2 · p. 9

6.4 Comparing with UCB1

• As the arm set expands, OFUL and CS-LB achieve superior convergence rates to UCB1, although UCB1 is computationally cheaper.The paper presents average regret and running time in Figures 3 and 4.Source: Figure 3 · p. 9, §6.4 · p. 9, Figure 4 · p. 10

• CS-LB combines clustering, lossless per-cluster sketches, and sentinel-guided optimistic cluster selection to obtain sublinear regret with guaranteed convergence.The conclusion reports per-round computation reduced from O(d^2) to O(ld), with synthetic evaluations showing reliable convergence, lower overhead, and superior regret performance.Source: §7 · p. 10
• Because warm-up reads the entire dataset, CS-LB is not yet applicable to linear contextual bandits with a varying arm set.Source: §7 · p. 10

• C_x denotes the cluster containing arm x after the cluster warm-up algorithm runs.Source: §A.1 · p. 12
• T_C,t denotes how many times cluster C has been selected up to round t.Source: §A.1 · p. 12
• The notation also refers to statistical information maintained during OFUL execution.Source: §A.1 · p. 12

A.2 Technical Lemmas

• For positive semidefinite A, the matrix Cauchy–Schwarz inequality bounds |x⊤y| by ∥x∥_A∥y∥_{A−1}.Source: §A.2 · p. 12
• With probability at least 1−δ, the confidence-set result places θ* in a specified set for all t≥0.The cited result is Theorem 2 in.Source: §A.2 · p. 12
• The sketch-size bound relates ε_l to the spectral tail of the covariance matrix, whose eigenvalues are ordered λ_1>...>λ_d.The bound is attributed to and [7].Source: §A.2 · p. 13

A.3 Proof of Lemma 4.1

• The proof combines the confidence-set and sketch-trace lemmas to obtain a high-probability statement for each cluster.The stated probability is at least 1−δ′.Source: §A.3 · pp. 13–14

A.4 Proof of Theorem 5.1

• The proof derives per-round regret from CS-LB’s arm-selection policy and uses the sentinel strategy to bound the upper confidence bound.Source: §A.4 · p. 14

A.3 Proof of Lemma 4.1

• CS-LB performs no singular-value truncation, and the sketch matrix rank is less than l; consequently, ε_l=0 within each cluster.Source: §A.3 · p. 13, §A.4 · p. 15

A.4 Proof of Theorem 5.1

• The fragment gives λ ≥ max{1, L²} and begins a regret claim at probability at least 1−δ, without specifying its bound.Source: §A.4 · p. 15