Efficient Linear Bandits via Cluster-Aware Sketching

Hantao Yang, Hong Xie, Defu Lian

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…