Efficient Linear Bandits through Matrix Sketching

Abstract

We prove that two popular linear contextual bandit algorithms, OFUL and Thompson Sampling, can be made efficient using Frequent Directions, a deterministic online sketching technique. More precisely, we show that a sketch of size $m$ allows a $\mathcal{O}(md)$ update time for both algorithms, as opposed to $\Omega (d^2)$ required by their non-sketched versions in general (where $d$ is the dimension of context vectors). This computational speedup is accompanied by regret bounds of order $(1+{\epsilon }_m{)}^{3/2}d\sqrt{T}$ for OFUL and of order $((1+{\epsilon }_m)d{)}^{3/2}\sqrt{T}$ for Thompson Sampling, where ${\epsilon }_m$ is bounded by the sum of the tail eigenvalues not covered by the sketch. In particular, when the selected contexts span a subspace of dimension at most $m$, our algorithms have a regret bound matching that of their slower, non-sketched counterparts. Experiments on real-world datasets corroborate our theoretical results.

Cited by in corpus (5)

• Gaussian Process Optimization with Adaptive Sketching: Scalable and No Regret
• A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance
• Meta-learning with Stochastic Linear Bandits
• Revisiting Co-Occurring Directions: Sharper Analysis and Efficient Algorithm for Sparse Matrices
• Online Model Selection: a Rested Bandit Formulation