acceptodds
Under review as a conference paper at ICLR 2027

Achieving Sublinear Regret in Fixed-Size Sketching Linear Bandits: A Clustering Approach

Abstract

We study the problem of computational efficiency for linear bandits in high-dimensional settings with a finite arm set. In linear bandits, the increase in the dimension of the feature vectors leads to growing computational costs of at each round of update. Traditional sketching-based methods such as SOFUL reduce computation via fixed-size matrix sketching, yet run the risk of incurring vacuous linear regret when the spectral tail of the data is heavy and the sketch size is inadequately selected. To guarantee regret convergence and effectively reduce computational costs, we introduce a clustering mechanism and propose the Cluster Sketch Linear Bandit (CS-LB) algorithm. Our method preserves the full covariance information in each cluster to guarantee robust sublinear regret without spectral-tail vulnerabilities, performs cluster switching by assigning a sentinel for each cluster, and reduces per-round update computation to via a tunable sketch size . Experiments on synthetic datasets demonstrate that our method consistently maintains a favorable trade-off between efficiency and regret.

Primary area:
reinforcement learning
Keywords:
Linear bandits, Computational efficiency, Sketching, Clustering

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_hqgZOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies computationally efficient linear bandits in high-dimensional settings with a fixed, finite arm set. The proposed method, Cluster Sketch Linear Bandit (CS-LB), partitions the arms into clusters whose feature vectors span subspaces of dimension at most the sketch size ℓ\ell. It maintains a separate model for each cluster and uses a sentinel-based mechanism to select a cluster before choosing an arm within it. The reported model-update complexity is O(ℓ2d)O(\ell^2d), which can offer computational savings over O(d2)O(d^2) updates when ℓ<d\ell<\sqrt{d}. Numerical experiments compare the method’s regret and runtime with those of existing baselines.

Critical strengths

Clear motivation and discussion of prior work. The discussion of existing methods makes the motivation easy to follow. In particular, the explanation of sketching error helps clarify why the paper adopts a cluster-based approach and what limitation it aims to address. Potential computational benefits from cluster-specific updates. Updating only the selected cluster’s model and its sentinel offers a promising way to reduce repeated confidence-score computations across the entire arm set. This design could provide computational savings when the arm set has a suitable cluster structure.

Critical weaknesses
  1. The stated sketch update appears inconsistent with the covariance-preservation identity used in the proof.

Algorithm 1 defines Σ\Sigma through an SVD of MM, but line 4 takes the square root of the truncated Σ\Sigma to construct S′S'. Under the stated SVD convention, it is unclear how this update satisfies S′⊤S′=M⊤M,S'^\top S'=M^\top M, even when the rank of MM is at most ℓ\ell. This appears inconsistent with the covariance-preservation identity in equation (18) of Appendix B.3. Because the regret analysis relies on this identity, the discrepancy raises a substantive concern about whether the algorithm as written supports the theoretical guarantee.

  1. The added value over exact low-dimensional regression under the same information assumptions is unclear.

The complete arm set is available before learning, allowing each cluster’s span to be computed during preprocessing. This is a legitimate problem setting; the concern is whether CS-LB provides a meaningful advantage over alternatives that exploit the same information. In particular, one could precompute a basis for each cluster and maintain exact low-dimensional regression in the resulting coordinates, while retaining the same cluster partition and sentinel strategy. The paper does not sufficiently establish what additional statistical or computational benefit the proposed sketch-based updates provide over this alternative.

  1. The implementation and overall computational accounting require further clarification.

The paper provides the factorized expression V~−1=λ−1(I−S⊤HS),\widetilde V^{-1}=\lambda^{-1}(I-S^\top HS), and Section 5.2 discusses warm-up and model-update costs. Thus, a low-rank representation is already available. However, it remains unclear whether the implementation consistently uses this representation without explicitly constructing a d×dd\times d matrix. Furthermore, the reported O(ℓ2d)O(\ell^2d) complexity appears to describe model updates rather than the complete per-round computation. The costs of cluster selection, within-cluster arm selection, and sentinel recomputation should be specified separately. These distinctions are necessary to assess the overall computational advantage and interpret the reported runtime comparisons.

  1. The appendix comparison with UCB1 may primarily reflect the benefits of sharing observations across duplicate features.

In Appendix A.1, positive scaling followed by normalization appears to make all arms within the same group have identical feature vectors. Consequently, the comparison with UCB1 may primarily demonstrate the benefit of pooling observations across duplicate-feature arms, rather than the broader benefit of exploiting linear relationships among distinct arms. This concern is specific to appendix datasets (3) and (4) in the paper. It remains unclear whether the reported regret advantage persists when identical-feature arms are merged or their observations are shared by the baseline.

Questions for authors
  1. How is the sketch update in Algorithm 1 consistent with equation (18)? Algorithm 1 defines Σ\Sigma through an SVD of MM, but line 4 takes the square root of the truncated Σ\Sigma. Under this definition, how does the update preserve S′⊤S′=M⊤MS'^\top S'=M^\top M? Please clarify whether this is a notation or pseudocode error and specify which update is used in the experimental implementation.

  2. What advantage does CS-LB provide over exact regression in precomputed cluster coordinates? Since the entire arm set is available before learning, how does the proposed method compare with precomputing a basis for each cluster and maintaining exact low-dimensional regression? Please clarify the additional benefit when this alternative uses the same cluster partition and sentinel strategy.

  3. How is the factorized inverse implemented, and what costs are included in the runtime evaluation? Does the implementation use V~−1=λ−1(I−S⊤HS)\widetilde V^{-1}=\lambda^{-1}(I-S^\top HS) implicitly, without constructing a d×dd\times d matrix? Beyond the warm-up and model-update costs discussed in Section 5.2, please specify the costs of cluster selection, arm selection, and sentinel recomputation. Is warm-up time included in the reported runtime?

  4. How many distinct feature vectors remain in appendix datasets (3) and (4) after normalization? Do all arms within each group become identical? If so, does the regret advantage over UCB1 persist when identical-feature arms are merged or their observations are shared?

6 comments
AuthorsOpenReview ↗

Response to Reviewer hqgZ (Part 1)

We thank the reviewer for their suggestion.

W1 & Q1. We thank the reviewer for pointing out this writing error. It is a notation error. In the pseudocode of [1], the SVD is performed on St⊤St+xx⊤S^{\top} _t S_t + x x^{\top}, whereas here we perform the SVD on [St;xt⊤][S _t;x _t^{\top}]. We now correct the writing error in Algorithm 1:

S′=Σ^V⊤S'=\hat{\Sigma}V^{\top}

and

H=([Σ^]l×l2+λI)−1.H=([\hat{\Sigma}] _{l\times l}^2+\lambda I)^{-1}.

We have checked the experimental code and the subsequent proofs, which confirm that this is merely a writing error; the experimental codes and the proofs are correct. Compared with the update process in [1], the only difference is that the square root is taken of the singular values; after matrix multiplication, the results are exactly the same. SC,N⊤SC,N=XC,N⊤XC,NS _{\mathcal{C},N}^{\top} S _{\mathcal{C},N} = X _{\mathcal{C},N}^{\top} X _{\mathcal{C},N} can be obtained directly from Property 3 in [1]. In Section 4.2, we explain that the construction of our clusters is lossless: their rank always remains less than ll, so no truncation occurs; thus, it essentially yields a decomposition of Xt⊤XtX^{\top} _t X _t. In fact, the FD update form in [1] and [2] can achieve computational optimization in practice only when implemented as the SVD decomposition of [St;xt⊤][S _t;x _t^{\top}], as we have written it. We have also made this correction in the updated version of the paper.

For W2 & Q2. Compared with methods that compute a basis for each cluster, our CS-LB has the following advantages:

  1. CS-LB supports online learning over the dataset. The CSW algorithm in our warm-up phase can actually be integrated into the learning process: whenever a new arm arrives, it first passes through CSW to determine which cluster it belongs to, and then the CS-LB algorithm performs arm selection. In this mode, our method no longer needs to scan the entire dataset in advance; instead, it gradually constructs the cluster set Call\mathcal{C}^{\mathrm{all}} during the learning process.

  2. Our method incurs lower update overhead when the dataset changes only modestly. When an arm is added (e.g., in movie recommendation, where the set of movies to recommend grows over time), our sketch-based update requires only O(l2d)O(l^2 d) overhead to insert an arm into a cluster. In contrast, basis-computation methods must recompute the basis whenever the dataset changes, at a cost of O(∣C∣dmin⁡{∣C∣,d})O(|\mathcal{C}|d\min\{|\mathcal{C}|,d\}); even if the rank rr is known in advance, the cost is O(∣C∣rd)O(|\mathcal{C}|rd). Thus, the basis-update cost scales with the number of arms ∣C∣|\mathcal{C}| in the cluster, whereas our method’s cost is completely independent of ∣C∣|\mathcal{C}|. When a cluster covers a large number of arms, basis-computation methods incur substantially higher overhead.

  3. Thanks to the nature of sketch updates, our method can avoid explicitly computing the inverse matrix, thereby achieving lower computational overhead. In contrast, basis-based methods, even when representing each arm by multiplying a coefficient matrix with the basis, still require explicit matrix inversion, which incurs greater computational overhead and prevents computational optimization.

AuthorsOpenReview ↗

Response to Reviewer hqgZ (Part 2)

For W3 & Q3. We do not need to explicitly compute Vˉt−1\bar{V}^{-1} _t. The wording in our paper may have caused a misunderstanding; what we meant is that our treatment of Vˉt−1\bar{V}^{-1} _t is consistent with that of [1]. When Vˉt−1\bar{V}^{-1} _t is needed for computation, we simply substitute its expression Vˉt−1=1λ(I−St⊤HtSt)\bar{V} _{t}^{-1}=\frac{1}{\lambda}(I-S^{\top} _t H _t S _t) into the formula to be evaluated. For example, when θ^t\hat{\theta} _t needs to be updated, θ^t=Vˉt−1βt=1λ(βt−St⊤HtStβt)\hat{\theta} _t=\bar{V} _{t}^{-1} \beta _t=\frac{1}{\lambda}(\beta _t-S^{\top} _t H _t S _t \beta _t). Updating Vt−1V _{t}^{-1} usually incurs O(d2)O(d^2) computational overhead, whereas computing βt−St⊤HtStβt\beta _t-S^{\top}_t H _t S _t \beta _t incurs only O(l2+ld)O(l^2+ld) (l≪dl\ll d), thereby achieving acceleration. We have improved the presentation of this part in the updated version of the paper. In our response to Reviewer iBj6 regarding the weakness, we compared the computational overhead of each component in detail; we have also added experimental results for the computational overhead of each part separately in supplementary experiments.

For W4 and Q4. Datasets (3) and (4) were constructed to intuitively demonstrate the low-rank structure of the dataset through linear correlation; the number of linearly independent vectors after linear combination equals the quantity value mlm^l defined in the paper. We assume that, initially, no algorithm has prior knowledge of the dataset; therefore, traditional MAB strategies can only try arms one by one, whereas our method, like OFUL, can effectively exploit the linear structure to find the optimal choice faster. We intend to use these datasets to show that CS-LB can achieve better regret performance, in addition to computational speedup, on datasets with local low-rank or local linear structure. In supplementary experiments, we reconstructed a locally low-rank dataset and used a larger-scale arm setting to compare with UCB1; the results are consistent with those in Appendix A.

[1] Ilja Kuzborskij, Leonardo Cella, and Nicolo Cesa-Bianchi. Efficient linear bandits through matrix sketching. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. 177–185. PMLR, 16–18 Apr 2019.

[2] Cheng Chen, Luo Luo, Weinan Zhang, Yong Yu, and Yijiang Lian. Efficient and robust highdimensional linear contextual bandits. IJCAI’20, 2021. ISBN 9780999241165.

Thank you for the detailed response and additional experiments. The corrected sketch update resolves my original covariance-preservation concern, and the implicit inverse explanation and runtime breakdown address my computational-accounting concern. I also appreciate the experiments beyond the duplicated-feature setting.

My main remaining concern is the added value over exact regression in precomputed cluster coordinates. For the fixed, known arm set studied here, an orthonormal basis and arm coordinates can be computed once per cluster. Using the same partition, regularization, confidence parameters, and sentinel strategy, this alternative preserves the predictions and confidence widths while supporting O(rC2)O(r_C^2) rank-one model updates after preprocessing, where rC≤ℓr_C\leq\ell is the cluster rank. It does not require repeatedly computing a matrix inverse from scratch. Thus, the response’s claimed computational disadvantage of basis-based methods is not established.

The arguments about newly arriving arms do not resolve this comparison. The revised paper still treats varying arm sets as future work. Moreover, basis methods need not recompute the entire basis for every arrival: in-span additions require no basis change, and new directions can be incorporated incrementally.

The clustering and sentinel design remains potentially useful, but the additional experiments do not establish the benefit over this coordinate-based alternative using the same design. A direct analytical or empirical comparison is therefore important for assessing the claimed efficiency contribution. I maintain my rating of 2 (weak rejection), primarily because this contribution remains insufficiently established, rather than because of the corrected covariance-preservation issue.

Reviewer_iBj6OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the computational efficiency of high-dimensional linear bandits under a fixed finite action set, with a focus on the limitation that existing fixed-size matrix sketch methods may not guarantee sub-linear regret when the spectral tail is heavy. The authors propose CS-LB, which maintains an independent sketch for each cluster by rank-constrained clustering, and uses the largest confidence upper bound within each cluster as a sentinel to achieve inter-cluster selection. The paper provides a sublinear regret bound without the spectral error term, and analyzes the cost of each round of update outside the warm-up phase as O(l2d)O(l^2d), where l is the pre-set sketch size. Synthetic data experiments show that CS-LB has lower cumulative regret compared to SOFUL and CBSCFD, and lower running time than OFUL.

Critical strengths
  • The paper focuses on the problem of balancing update efficiency and regret convergence for high-dimensional linear bandits under limited computational budgets, with a clear research motivation and a close connection to real-time computational requirements in online decision-making scenarios.
  • The paper explicitly describes the relationship between the regret boundary and the number of clusters, as well as the sketch size, and separately analyzes the computational costs in the preheating phase and the online update phase, which helps to understand the trade-off between the statistical efficiency and computational cost of the method.
Critical weaknesses

The verification of computational advantage in the paper is mainly focused on local update complexity and runtime for a small number of instances, and has not fully characterized the overall statistical-computational trade-off. The method requires maintaining multiple local sketches and incurs preprocessing costs dependent on the number of actions and clusters, while the measured rate advantage partly comes from the reduction in the search range of candidate actions. Although these designs can contribute to reasonable efficiency gains, existing results are still insufficient to clearly identify their main sources, as well as the scale and time domain in which a favorable overall trade-off can be formed.

Questions for authors

What are the main benefits of the method: low-dimensional statistical estimation, reducing the search space for actions, or trading more states and preprocessing for cheaper online operations? Under what conditions does the advantage hold when these factors are combined?

2 comments
AuthorsOpenReview ↗

Response to Reviewer iBj6 (Part 1)

We sincerely thank the reviewer for their valuable comments.

For the weakness:

For linear bandits, the computational overhead (excluding initialization, identical I/O operations, and waiting for environment feedback) mainly consists of the following: (C1) update overhead: the per-round cost of (C1a) updating Xt⊤XtX^{\top}_t X_t or St⊤StS^{\top}_t S_t, (C1b) forming Vt−1=(λI+Xt⊤Xt)−1V_t^{-1}=(\lambda I+X^{\top}_t X_t)^{-1} or Vˉt−1=(λI+St⊤St)−1\bar{V}_t^{-1}=(\lambda I+S^{\top}_t S_t)^{-1}, (C1c) updating reward vector βt\beta_t, and (C1d) estimate θ^t\hat{\theta}_t; (C2) search overhead: including the cost of computing the matrix norm $ || x || _{V _t^{-1}}$ or $ || x|| _{\bar{V} _t^{-1}}$ for each arm xx required for the current estimate. Our method incurs additional overhead: (C3) clustering overhead: the total cost of the CSW algorithm during the warm-up phase; (C4) cluster search overhead: the cost of comparing cluster sentinels to select the current cluster; (C5) cluster update overhead: the cost of updating each cluster sentinel.

We summarize the order of computational overhead for each component across the algorithms in the following tables.

Algorithm(C1a)(C1b)(C1c)(C1d)(C2)(C3)(C4)(C5)Total cost per round
OFULO(d2)O(d^2)O(d2)O(d^2)O(d)O(d)O(d2)O(d^2)O(Nd2)O(Nd^2)NoneNoneNoneO(d2+Nd2)O(d^2+Nd^2)
SOFUL/CBSCFDO(ld)O(ld)NoneO(d)O(d)O(ld+l2)O(ld+l^2)O(N(ld+l2))O(N(ld+l^2))NoneNoneNoneO(ld+N(ld+l2))O(ld+N(ld+l^2))
CS-LB (Ours)O(l2d)O(l^2d)NoneO(d)O(d)O(ld+l2)O(ld+l^2)O(Cmax⁡(ld+l2))O(C_{\max}(ld+l^2))O(NNAll2d)O(NN_{\mathcal{A}}^ll^2d)O(d)O(d)O(Cmax⁡(ld+l2))O(C_{\max}(ld+l^2))O(l2d+Cmax⁡(ld+l2))O(l^2d+C_{\max}(ld+l^2))

Table: computation cost for (C1)–(C5)

Our matrix update is based on the sketch strategy. According to [1], we do not need to explicitly compute Vˉt−1\bar{V} _t^{-1}; instead, we use the formula Vˉt−1=1λ(I−St⊤HtSt)\bar{V} _{t}^{-1}=\frac{1}{\lambda}(I-S^{\top} _t H _t S _t), and substitute it into the computations of θ^t\hat{\theta} _t and ∥∣x∥∣Vˉt−1\|| x \|| _{\bar{V} _t^{-1}}, thereby reducing the computational overhead from O(d2)O(d^2) to O(l2+ld)O(l^2+ld). Meanwhile, for the search overhead, both traditional linear bandit methods and traditional sketch strategies must compute ∥∣x∥∣Vˉt−1\|| x \|| _{\bar{V} _t^{-1}} for NN arms, yielding a per-round search overhead of O(Nd2)O(Nd^2) and O(N(l2+ld))O(N(l^2+ld)), respectively. In contrast, our CS-LB algorithm does not need to search the entire arm set; it only needs to search the arms in the current cluster Wt\mathcal{W} _t, yielding a search overhead of O(∥Wt∥(ld+l2))O(\|\mathcal{W} _t\|(ld+l^2)). With Cmax⁡=max⁡C∈Call{∣C∣}C _{\max}=\max _{\mathcal{C}\in \mathcal{C}^{all}}\{|\mathcal{C}|\}, the search overhead of the CS-LB algorithm is O(Cmax⁡(ld+l2))O(C _{\max}(ld+l^2)), which provides a huge speedup for large-scale arm settings.

The update of the sketch matrix St⊤StS^{\top} _t S _t mainly comes from the SVD computation of the sketch matrix, and is therefore O(l2d)O(l^2d). SOFUL and CBSCFD can use an acceleration method that updates once every 2l2l rounds [1,2], reducing the average sketch update overhead to O(ld)O(ld). Our method cannot be accelerated in the same way because it needs to maintain lossless updates; this is also the main source of computational overhead in our algorithm. However, our optimization of the search overhead compensates well for this (see the supplementary experiments). Regarding the additional overhead of CS-LB: (C3) does not occur in every round; since it is constant with respect to time, it is negligible when averaged over time (see the supplementary experiments); (C4) only involves comparing NAlN _{\mathcal{A}}^l tensors; and for (C5), since only the currently selected cluster needs sentinel updates, (C5) is equivalent to performing the search overhead once more. We have added timing measurements for these computational components in supplementary experiments to quantify the computational overhead, thereby supporting the above analysis.

AuthorsOpenReview ↗

Response to Reviewer iBj6 (Part 2)

For the question:

The main benefit of our method lies in guaranteeing regret convergence while optimizing computational efficiency for linear bandits with finite arms (with a limited number of additions and removals). Compared with previous sketch-based computational optimization strategies, we achieve a better regret order; on top of this, our method further improves search efficiency. CS-LB has two advantages. In terms of computational optimization, computational acceleration can be achieved when the sketch size satisfies l2<dl^2<d; in this case, we achieve lower regret than the conventional SOFUL and CBSCFD methods. In terms of regret, on datasets with local linear correlation or local low-rankness, our method uses clustering to obtain lNA<min⁡d,Nl\sqrt{N_A}<\min\\{d,\sqrt{N}\\}, which allows CS-LB to achieve better regret than UCB1 and OFUL. The forms of datasets with local linear correlation or local low-rankness can be found respectively in our simulated dataset settings in Appendix A and supplementary experiments.

[1] Ilja Kuzborskij, Leonardo Cella, and Nicolo Cesa-Bianchi. Efficient linear bandits through matrix sketching. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. 177–185. PMLR, 16–18 Apr 2019.

[2] Cheng Chen, Luo Luo, Weinan Zhang, Yong Yu, and Yijiang Lian. Efficient and robust high-dimensional linear contextual bandits. IJCAI’20, 2021. ISBN 9780999241165.

Reviewer_e2WCOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper addresses a longstanding computational challenge in high-dimensional linear bandits: the O(d2)O(d^2) per-round update cost. Existing fixed-size sketching methods reduce this cost but do not guarantee sublinear regret in general, whereas adaptive sketching methods provide regret guarantees but may exceed a prescribed computational budget. The paper aims to combine a small, fixed sketch size with a sublinear regret guarantee. The work addresses this challenge by fixing the sketch size in advance while retaining a T\sqrt{T} dependence in the regret bound, up to logarithmic factors.

Critical strengths

A strength of the work is that it addresses this challenge by fixing the sketch size in advance while retaining a T\sqrt{T} dependence in the regret bound, up to logarithmic factors. Moreover, the presentation is clean and easy to follow and the justification of the paper is powerful.

Critical weaknesses

I believe several important questions remain insufficiently addressed. First, the tradeoff between computational cost and statistical accuracy discussed in Section 3.3 is not clearly characterized by the theoretical results. The paper gives a per-round update cost of O(l2d)O(l^2d) and a regret bound of O~(lNAlT)\widetilde O\left(l\sqrt{N_{\mathcal A}^{l}T}\right). Intuitively, a larger computational budget permits a larger ll, which could allow fewer clusters and thus a smaller NAlN_{\mathcal A}^{l}, potentially improving statistical accuracy and regret. However, the paper does not establish whether NAlN_{\mathcal A}^{l} decreases monotonically with ll. Consequently, this remains an intuition rather than a tradeoff substantiated by the analysis.

Although NAl≤N/l+1N_{\mathcal A}^{l}\le N/l+1 provides an upper bound that decreases with ll, this bound appears too loose to establish the intended benefit. Substituting it into the regret bound yields O~(lNT)\widetilde O(\sqrt{lNT}), as also noted around line 384. I find this dependence on NN problematic because linear bandit problems are often motivated by large action sets. When NN is small, standard MAB algorithms already achieve O~(NT)\widetilde O(\sqrt{NT}) regret, which may not differ substantially from the O~(dT)\widetilde O(\sqrt{dT}) guarantees available for linear bandits.

My second concern is closely related to the first. A favorable comparison with the standard linear bandit regret bound requires l2NAl≤d2l^2N_{\mathcal A}^{l}\le d^2. However, the paper provides neither a sufficiently strong guarantee nor a concrete characterization on NAlN_{\mathcal A}^{l} (the example in experiment is also not significant since the action set N is too small). As a result, it is hard to say the requirement is easy to satisfied. Consequently, I am not convinced that the theoretical results establish a substantial advantage or sufficiently demonstrate the significance of the proposed algorithm.

Questions for authors

1.Could author give either a sufficiently strong guarantee or a concrete characterization on NAlN_{\mathcal A}^{l} to obtain a more informative regret bound to show the benefit of your algorithm design and a better tradeoff between cost and accuracy?

2.Could author give some concrete examples when l2NAl≤d2l^2N_{\mathcal A}^{l}\le d^2 with large N is satisfied commonly in the real world application scene?

3.the action set N for the experiment is not large enough. N and d is so close that we can just use MAB model to gain a close regret bound (O~(NT)\widetilde O(\sqrt{NT}) and O~(dT)\widetilde O(\sqrt{dT})).

  1. I am less familiar with research on improving computational efficiency, so I reserve judgment on this aspect for now. I would welcome input from other reviewers and hope to gain a better understanding through the discussion.
4 comments
AuthorsOpenReview ↗

Response to Reviewer e2WC (Part 1)

We sincerely thank the reviewer for their valuable comments.

Regarding Weakness:

Regarding the expression for NAlN_{\mathcal{A}}^l. The reason we did not provide an explicit expression for NAlN_{\mathcal{A}}^l is that it is currently difficult to obtain a specific mathematical formula for NAlN_{\mathcal{A}}^l, because NAlN_{\mathcal{A}}^l depends on the structure of the dataset. For two datasets of the same size NN and the same sketch size ll, NAlN_{\mathcal{A}}^l can still differ. For example, suppose there are two datasets A1\mathcal{A}_1 and A2\mathcal{A}_2, both with N=6N = 6 arms in dimension d=3d = 3 and of rank 3, where

A1=(1,0,0),(0,1,0),(0,0,1),(1,1,0),(0,1,1),(1,0,1)\mathcal{A}_1=\\{(1,0,0),(0,1,0),(0,0,1),(1,1,0),(0,1,1),(1,0,1)\\}

and

A2=(1,0,0),(0,1,0),(0,0,1),(2,0,0),(0,2,0),(0,0,2)\mathcal{A}_2=\\{(1,0,0),(0,1,0),(0,0,1),(2,0,0),(0,2,0),(0,0,2)\\}

Now suppose we take the sketch size l=2l=2. Then, executing CSW on the two datasets in data order will yield NA12=3N _{\mathcal{A} _1}^2=3 and NA22=2N _{\mathcal{A} _2}^2=2, respectively. For A1\mathcal{A}_1, we obtain 3 clusters:

(1,0,0),(0,1,0),(1,1,0),(0,0,1),(0,1,1),(1,0,1);\\{(1,0,0),(0,1,0),(1,1,0)\\}, \\{(0,0,1),(0,1,1)\\}, \\{(1,0,1)\\};

for A2\mathcal{A}_2, we obtain 2 clusters:

(1,0,0),(2,0,0),(0,1,0),(0,2,0),(0,0,1),(0,0,2).\\{(1,0,0),(2,0,0),(0,1,0),(0,2,0)\\},\\{(0,0,1),(0,0,2)\\}.

As can be seen, without knowing the specific form of the dataset, even if the two datasets have the same overall mathematical information (number of arms, dimension, and rank of the dataset), they can still produce different NAlN_{\mathcal{A}}^l under the same ll. This shows that NAlN_{\mathcal{A}}^l can only be obtained by traversing every data point in dataset A\mathcal{A}.

Therefore, NAlN_{\mathcal{A}}^l cannot be obtained by direct mathematical derivation. To our knowledge, NAlN_{\mathcal{A}}^l can only be obtained from the final output of the algorithm. This is also why the notation for NAlN_{\mathcal{A}}^l is tied to both the dataset AA and the sketch size ll. We can get the upper bound of NAlN_{\mathcal{A}}^l, because at most one cluster can have fewer than ll arms. The proof is as follows:

Proof by contradiction: suppose there are two clusters that contain fewer than ll arms. Then the number of linearly independent vectors contained in each of these two clusters is also less than ll, so the rank of each is also less than ll. According to the CSW algorithm, an arm will preferentially be assigned to a cluster whose rank is less than ll, and only when the ranks of all existing clusters have reached ll will it be assigned to a new cluster. This yields a contradiction.

Thus, in the worst case (i.e., the case that maximizes the number of clusters), every cluster except the last contains exactly ll data points. This yields an upper bound of ⌈N/l⌉\lceil N/l \rceil, and only from this upper bound can we infer the relationship between the maximum value of NAlN_{\mathcal{A}}^l and ll. On the other hand, if an appropriate sketch size is chosen such that l=dl=d or l≥rank(XT)l\geq rank(X_T), then a single cluster can cover the entire dataset, yielding NAl=1N_{\mathcal{A}}^l=1. It should be noted that the quantity NAlN_{\mathcal{A}}^l is not necessary for the subsequent algorithm CS-LB (the algorithm does not need to know NAlN_{\mathcal{A}}^l); it is only used to show that NAlN_{\mathcal{A}}^l is a constant independent of TT that can be fixed in advance. Its role in the regret expression is to show that we can achieve regret convergence with respect to TT. Therefore, we did not further explore an explicit mathematical expression for NAlN_{\mathcal{A}}^l. However, the reviewer’s point is very inspiring to us, and we may investigate this direction in future work.

AuthorsOpenReview ↗

Response to Reviewer e2WC (Part 2)

Regarding the regret bound: Our goal is not a tighter regret bound, but to reduce the computational overhead of linear bandit updates while guaranteeing regret convergence. Sketch-based singular-value truncation (e.g., SOFUL) lowers inverse-matrix update cost, but introduces errors that worsen regret [1, 2] and, in the worst case, can prevent convergence [3].

a) For linear bandits, our focus is on optimizing the computational overhead while ensuring regret convergence; optimizing computational overhead inevitably incurs some loss of accuracy. In [1,2], the regret degrades to linear order in TT in the worst case. Our regret formulation proves that convergence is still guaranteed even in the worst case, yielding better regret than previous computationally optimized strategies. It should be noted that, if only regret is considered, our algorithm achieves better regret only on datasets that are linearly dependent or low-rank. According to Lemma 8 in [1], if the dataset is low-rank—that is, the rank rAr_{\mathcal{A}} of the decision sequence matrix X⊤XX^{\top}X formed by the vectors in the dataset satisfies rA<dr_{\mathcal{A}}<d—then the OFUL algorithm can exploit this low-rank structure to reduce the regret from O~(dT)\widetilde{O}(d\sqrt{T}) to O~(rAT)\widetilde{O}(r_{\mathcal{A}}\sqrt{T}), since the effective dimension drops from dd to rAr_{\mathcal{A}}. Correspondingly, for our algorithm, if we choose an appropriate sketch size l≥rAl\geq r_{\mathcal{A}}, then our regret becomes O~(lT)\widetilde{O}(l\sqrt{T}), depending on ll; when rA2≤l2<dr_{\mathcal{A}}^2\leq l^2<d, this will be better than the optimal regret O~(dT)\widetilde{O}(\sqrt{dT}) for linear bandits on general datasets with finite arms. Although OFUL can also achieve O~(rAT)\widetilde{O}(r_{\mathcal{A}}\sqrt{T}) regret, it requires greater computational overhead to compute the determinant of the covariance matrix maintained at each round, whereas our method can exploit the low-rank structure of the dataset with lower computational overhead.

b) As for the comparison with MAB regret: our algorithm is better suited to datasets with local linear correlation and local low-rankness. NAlN_{\mathcal{A}}^l exploits the information transfer among the vectors in the dataset that is induced by the linear structure of the dataset, which is also the advantage of linear bandits over traditional MAB. Some datasets may be dense but may exhibit local linear correlation and local low-rankness. The clusters formed by our method can effectively exploit such local optimization to obtain a lower NAlN_{\mathcal{A}}^l, thereby accelerating the convergence of the algorithm; exploiting this local optimization can make lNAl<Nl\sqrt{N_{\mathcal{A}}^l}<\sqrt{N}. On the other hand, even in the worst case our regret is O~(lNT)\widetilde{O}(\sqrt{lNT}); since ll can be set arbitrarily in advance, it can be regarded as a constant term; therefore, even in the worst case, the regret is of the same order as that of MAB. In Appendix A, we ran comparative experiments against UCB1. We constructed simulated datasets with local linear correlation, and the experimental results show that our CS-LB can aggregate locally linearly correlated arms to achieve better regret than UCB1 for large-scale NN. We have also added simulation experiments on locally low-rank datasets in supplementary experiments and constructed larger-scale datasets for comparison with UCB1.

Regarding Questions:

Q1. Please refer to our response regarding the weakness.

Q2. We have added experiments on real datasets in supplementary experiments; please refer to supplementary experiments.

Q3. We have added experiments with a larger number of arms in supplementary experiments; please refer to supplementary experiments.

[1] Ilja Kuzborskij, Leonardo Cella, and Nicolo Cesa-Bianchi. Efficient linear bandits through matrix sketching. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. 177–185. PMLR, 16–18 Apr 2019.

[2] Cheng Chen, Luo Luo, Weinan Zhang, Yong Yu, and Yijiang Lian. Efficient and robust highdimensional linear contextual bandits. IJCAI’20, 2021. ISBN 9780999241165.

[3] Dongxie Wen, Hanyan Yin, Xiao Zhang, Peng Zhao, Lijun Zhang, and Zhewei Wei. Revisiting matrix sketching in linear bandits: Achieving sublinear regret via dyadic block sketching. In International Conference on Learning Representations, volume 2026, pp. 86907–86942, 2026.

My main concern remains that the regret guarantee depends on an insufficiently characterized quantity, NAlN_{\mathcal A}^{l}, and the current analysis does not adequately establish the claimed trade-off between computational efficiency and regret.

Specifically, the per-round update cost is O(l2d)O(l^2d), while the regret bound is O~(lNAlT)\widetilde O\left(l\sqrt{N_{\mathcal A}^{l}T}\right). The sketch size ll affects both the explicit coefficient in the regret bound and the number of clusters NAlN_{\mathcal A}^{l}. (Also, for the parameter ll, these bounds therefore appear to favor a smaller ll on both criteria, leaving the claimed computational–statistical trade-off unclear.) However, the analysis provides only a coarse upper bound on this quantity. Consequently, the results do not sufficiently explain how changing the sketch size translates into computational savings and the associated statistical cost.

The examples in the response demonstrate that datasets with the same number of arms, dimension, and overall rank can produce different cluster counts. However, my concern does not require an exact expression for NAlN_{\mathcal A}^{l}. This observation does not preclude a more refined structural characterization or a more informative regret analysis, and therefore does not resolve the concern above. Similarly, establishing that NAlN_{\mathcal A}^{l} is independent of TT explains the sublinear dependence on the horizon, but does not substitute for an analysis of the computational–statistical trade-off.

While the response clarifies some of the meaning of this parameter, it has not resolved my concern about the depth of the theoretical analysis and whether the results sufficiently support the claimed contribution. I therefore maintain my original rating.

We thank the reviewer for the reply. NAlN_{\mathcal{A}}^l appears in the bound only to aggregate the per-cluster regret into a global one; since it is bounded independently of the horizon, the aggregate stays sublinear in TT, even in the worst case, when every cluster fills to rank ll and NAlN_{\mathcal{A}}^l is largest---convergence does not rely on any particular partition. This is what SOFUL and CBSCFD lack: their spectral tail grows with TT under heavy tails and drives the regret to grow linearly. The contribution is therefore twofold: a convergence guarantee, since capping each cluster's rank at ll discards no singular mass and leaves no spectral term in the bound; and a cheaper search, with the candidate set falling from all arms to those of the selected cluster. We acknowledge that our analysis of NAlN_{\mathcal{A}}^l is not sufficiently in-depth, but the analysis of NAlN_{\mathcal{A}}^l does not affect the main problem we address, and we have also explained and demonstrated the scenarios in which our regret advantage holds in the supplementary experiments.

Comments on the paper

3 comments
AuthorsOpenReview ↗

Supplementary Experiments (Part 1)

We thank the reviewer for the comments. This part constitutes our supplementary experiments.

We have updated the submitted version of the paper; for the legends of the following supplementary experiments, please refer to Appendix C in our updated paper. The following is a supplement to the experiments in the main text. The basic parameter settings of the supplementary experiments are consistent with those in Section 6.2, and all experimental results are averaged over 5 independent runs.

Comparison with UCB1 on Larger-scale Data

To further verify the advantages of CS-LB on large-scale locally low-rank datasets, we increased the number of arms and modified the dataset generation so that the datasets are no longer simply linearly correlated.

Our simulated dataset is constructed as follows: for a dataset with NN arms, every 30 arms form a group, and the vectors in each group are constrained to have rank 5. The dataset constructed in this way exhibits local low-rank: the rank of the entire dataset remains dd, while the rank within each group is 5. We generate dataset (5) in this manner with N=300N=300 and d=100d=100, and set the sketch size to l=5l=5. The experimental results are shown in Figures 3(a) and 3(b) in Appendix C; for the reviewer’s convenience, we list the numerical values behind these legends in the following table.

RegretRunning time
OFUL15264.415264.41824.21824.2
SOFUL57841.357841.31108.41108.4
CBSCFD12119.112119.11119.51119.5
UCB19891.59891.5425.4425.4*
CS-LB(Ours)3049.23049.2*679.7679.7

Table: dataset(5), 400K rounds

For dataset (5), the CS-LB algorithm exploits its local low-rank property to generate NA5=10N_{\mathcal{A}}^5=10 clusters such that lNA5<Nl\sqrt{N_{\mathcal{A}}^5}<\sqrt{N}, achieving better regret than UCB1; moreover, the running time of CS-LB is second only to UCB1, which does not require matrix operations.

Real-world Dataset

We choose MovieLens-25M [4] as the real-world dataset for our experiments. The arms are 500 real MovieLens-25M movies described by their Tag-Genome relevance vectors [5], projected to rank r=10r=10 by a non-negative factorization fitted without the ratings. The rewards are the movies' actual mean ratings.

We set the sketch size to l=5,10,20l=5,10,20. We selected 500 movies as arms, with each arm corresponding to a vector of dimension d=200d=200, and chose the highest-rated movie as the best arm. The experimental results are shown in Figures 3(c) and 3(d) in Appendix C; for the reviewer’s convenience, we list the numerical values behind these legends in the following table.

RegretRunning timeNAlN_{\mathcal{A}}^l
OFUL4997.54997.53410.83410.8None
UCB13609.23609.2179.2179.2*None
CS-LB(l=5l=5)6924.46924.4307.2307.2*100
CS-LB(l=10l=10)1536.21536.2*1648.31648.31
CS-LB(l=20l=20)1728.21728.27925.97925.91

Table: real dataset, 200K rounds

The cluster counts corresponding to the three sketch sizes are NA5=100N_{\mathcal{A}}^5=100 and NA10=NA20=1N_{\mathcal{A}}^{10}=N_{\mathcal{A}}^{20}=1, respectively. This is because when the sketch size ll is larger than the rank of the dataset, a single cluster can cover the entire dataset. When l=5l=5, the search time and update overhead are substantially reduced; as can be seen, l=5l=5 gives the fastest running time (second only to UCB1), but the excessive number of clusters makes its regret worse. With l=10l=10, the regret of CS-LB is exactly O~(rT)\widetilde{O}(r\sqrt{T}), and since r=10<dr=10<\sqrt{d} and r<Nr<\sqrt{N}, it achieves optimal regret and allows computational speedup. With l=20l=20, the benefit from the number of clusters no longer increases, and the regret becomes O~(lT)\widetilde{O}(l\sqrt{T}), depending on the choice of ll. l=20l=20 satisfies r<l<dr<l<d and l<Nl<\sqrt{N}, so the regret at l=20l=20 is slightly worse than that at l=10l=10 but still better than OFUL and UCB1; however, since l2=400>d=200l^2=400>d=200, computational speedup can no longer be achieved at l=20l=20.

AuthorsOpenReview ↗

Supplementary Experiments (Part 2)

Breakdown of Computational Overhead

Our previous experiments on computational overhead compared only the overall running time of the algorithms. In this section, we divide the running time into update time, search time, and the additional overhead time of CS-LB for comparison. We exclude all other running time in the code that is unrelated to algorithm decisions, including I/O time for data logging and time spent waiting for feedback; these parts of the code are identical across all algorithms and thus need not be compared.

For linear bandits, the computational overhead mainly consists of the following: (C1) update overhead: the per-round cost of updating Xt⊤Xt\boldsymbol{X}^{\top}_t\boldsymbol{X}_t or St⊤St\boldsymbol{S}^{\top}_t\boldsymbol{S}_t, Vt−1=(λI+Xt⊤Xt)−1\boldsymbol{V}_t^{-1}=(\lambda\boldsymbol{I}+\boldsymbol{X}^{\top}_t\boldsymbol{X}_t)^{-1} or Vˉt−1=(λI+St⊤St)−1\bar{\boldsymbol{V}}_t^{-1}=(\lambda\boldsymbol{I}+\boldsymbol{S}^{\top}_t\boldsymbol{S}_t)^{-1}, reward vector βt\boldsymbol{\beta}_t, and estimate θ^t\hat{\theta} _t; (C2) search overhead: including the cost of computing the matrix norm ∣∣x∣∣Vt−1||\boldsymbol{x} || _{\boldsymbol{V}_t^{-1}} or ∣∣x∣∣Vˉt−1||\boldsymbol{x} || _{\bar{\boldsymbol{V}}_t^{-1}} for each arm x\boldsymbol{x} required for the current estimate. Our method incurs additional overhead: (C3) clustering overhead: the total cost of the CSW algorithm during the warm-up phase; (C4) cluster search overhead: the cost of comparing cluster sentinels to select the current cluster; (C5) cluster update overhead: the cost of updating each cluster sentinel.

We compared the separately measured computational overhead on dataset (5). The results are averaged over 5 runs with T=400KT=400K and are shown in the following table:

UpdateSearchsentinelWarm-upTotal
OFUL439.9660.6001100.3
SOFUL57.4*570.500627.9
CBSCFD60.6573.200633.2
CS-LB(Ours)73.383.7*87.20.332244.5*

Table: Computational overhead in the experiments on dataset (5)

The meanings of the entries are as follows:

-Update time: (C1)

-Search time: (C2) for baselines, and (C2)+(C4) for CS-LB

-sentinel time: (C5)

-Warm-up time: (C3)

-Total time: Total overhead excluding parts unrelated to the algorithm

The results in the table are consistent with our analysis in the paper. Thanks to the acceleration provided by the sketch strategy, SOFUL, CBSCFD, and CS-LB all have update time and search time significantly lower than those of OFUL, since they avoid explicitly computing the inverse matrix. For sketch updates, both SOFUL and CBSCFD can use the interval-update acceleration method [1,2], reducing the average sketch matrix update cost to only O(ld)O(ld). Moreover, SOFUL and CBSCFD differ only numerically and have completely identical update strategies, so their running times are almost the same. In contrast, CS-LB cannot use the acceleration strategy of SOFUL and CBSCFD, so its sketch matrix update can only be performed in O(l2d)O(l^2d), which is also why we need to set l2<dl^2<d for acceleration. Therefore, the update time of SOFUL and CBSCFD is shorter than that of CS-LB. However, CS-LB restricts the search scope to within clusters via clustering, greatly reducing the search time and thus compensating for its disadvantage in update time. On the other hand, the warm-up time for constructing clusters via CSW is negligible compared with the total running time over TT rounds, consistent with our constant-term argument. The sentinels need to be updated only for the current cluster, since the statistics of unselected clusters remain unchanged; therefore, the sentinel time is almost identical to the search time. Taken together, the above results show that CS-LB achieves lower computational overhead.

[1] Ilja Kuzborskij, Leonardo Cella, and Nicolo Cesa-Bianchi. Efficient linear bandits through matrix sketching. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. 177–185. PMLR, 16–18 Apr 2019.

[2] Cheng Chen, Luo Luo, Weinan Zhang, Yong Yu, and Yijiang Lian. Efficient and robust high-dimensional linear contextual bandits. IJCAI’20, 2021. ISBN 9780999241165.

[4] F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 5(4), December 2015. ISSN 2160-6455. doi: 10.1145/2827872.

[5] Jesse Vig, Shilad Sen, and John Riedl. The tag genome: Encoding community knowledge to support novel interaction. ACM Trans. Interact. Intell. Syst., 2(3), September 2012. ISSN 2160-6455. doi:10.1145/2362394.2362395.

Dear Reviewers,

I hope this message finds you well. As the discussion period is nearing its end, with less than two days remaining, I wanted to ensure that we have addressed all your concerns satisfactorily. If there are any additional points or feedback you would like us to consider, please let us know. Your insights are invaluable to us, and we are eager to address any remaining issues to improve our work.

We are grateful to the reviewers and the AC/PC/SAC for the time and effort devoted to our work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.