Efficient Linear Bandits via Cluster-Aware Sketching
This work introduces a clustering mechanism and proposes the Cluster Sketch Linear Bandit algorithm, which 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 reduce...