Efficient Linear Bandits through Matrix Sketching
This work addresses computational bottlenecks in bandit algorithms for researchers and practitioners, offering a practical speedup with theoretical guarantees, though it is incremental as it builds on existing methods.
The paper tackled the computational inefficiency of linear contextual bandit algorithms by applying matrix sketching, achieving an update time of O(md) compared to Ω(d^2) for non-sketched versions, with regret bounds scaling with sketch size and tail eigenvalues.
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 $Ω(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+\varepsilon_m)^{3/2}d\sqrt{T}$ for OFUL and of order $\big((1+\varepsilon_m)d\big)^{3/2}\sqrt{T}$ for Thompson Sampling, where $\varepsilon_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.