SOURCE-LINKED INTELLIGENCE

Efficient Linear Bandits via Cluster-Aware Sketching

arXiv · AI, language, vision and robotics · article · Sep 23, 2026 · UTC

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 $d$ of the feature vectors leads to growing computational costs of $O(d^2)$ 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 introdu

Read original source ↗ Open in workspace

recordType

paper

region

Global