- 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 . 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 , which can offer computational savings over updates when . 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
- The stated sketch update appears inconsistent with the covariance-preservation identity used in the proof.
Algorithm 1 defines through an SVD of , but line 4 takes the square root of the truncated to construct . Under the stated SVD convention, it is unclear how this update satisfies even when the rank of is at most . 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.
- 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.
- The implementation and overall computational accounting require further clarification.
The paper provides the factorized expression 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 matrix. Furthermore, the reported 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.
- 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
-
How is the sketch update in Algorithm 1 consistent with equation (18)? Algorithm 1 defines through an SVD of , but line 4 takes the square root of the truncated . Under this definition, how does the update preserve ? Please clarify whether this is a notation or pseudocode error and specify which update is used in the experimental implementation.
-
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.
-
How is the factorized inverse implemented, and what costs are included in the runtime evaluation? Does the implementation use implicitly, without constructing a 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?
-
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
Response to Reviewer hqgZ (Part 2)
For W3 & Q3. We do not need to explicitly compute . The wording in our paper may have caused a misunderstanding; what we meant is that our treatment of is consistent with that of [1]. When is needed for computation, we simply substitute its expression into the formula to be evaluated. For example, when needs to be updated, . Updating usually incurs computational overhead, whereas computing incurs only (), 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 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 rank-one model updates after preprocessing, where 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.
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⊤, whereas here we perform the SVD on [St;xt⊤]. We now correct the writing error in Algorithm 1:
S′=Σ^V⊤
and
H=([Σ^]l×l2+λ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,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 l, so no truncation occurs; thus, it essentially yields a decomposition of Xt⊤Xt. 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⊤], 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:
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 during the learning process.
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) 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}); even if the rank r is known in advance, the cost is O(∣C∣rd). Thus, the basis-update cost scales with the number of arms ∣C∣ in the cluster, whereas our method’s cost is completely independent of ∣C∣. When a cluster covers a large number of arms, basis-computation methods incur substantially higher overhead.
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.