Efficient Linear Bandits through Matrix Sketching

Ilja Kuzborskij, Leonardo Cella, Nicolò Cesa-Bianchi

We prove that two popular linear contextual bandit algorithms, OFUL and Thompson Sampling, can be made efficient using Frequent Directions, a deterministic online sketching techniq…