# Efficient Linear Bandits through Matrix Sketching

arXiv: https://arxiv.org/abs/1809.11033 · HTML: https://mlsanity.com/paper/1809.11033/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Sep 2018.

## Built on by (most cited first, 12 of 12)

- [Multi-task Representation Learning with Stochastic Linear Bandits](https://mlsanity.com/paper/2202.10066/) (2022)
- [Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2211.05964/) (2022)
- [Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketching](https://mlsanity.com/paper/2410.10258/) (2024)
- [Efficient Kernel UCB for Contextual Bandits](https://mlsanity.com/paper/2202.05638/) (2022)
- [Scalable LinUCB: Low-Rank Design Matrix Updates for Recommenders with Large Action Spaces](https://mlsanity.com/paper/2510.19349/) (2025)
- [Effective Streaming Low-tubal-rank Tensor Approximation via Frequent Directions](https://mlsanity.com/paper/2108.10129/) (2021)
- [Scaling Federated Linear Contextual Bandits via Sketching](https://mlsanity.com/paper/2605.00500/) (2026)
- [Efficient Multinomial Logistic Bandit via Frequent Directions](https://mlsanity.com/paper/2606.11968/) (2026)
- [Set Membership Estimation for Stochastic Linear Contextual Bandits](https://mlsanity.com/paper/2606.20022/) (2026)
- [Efficient Hypergradient Descent for Inverse Reinforcement Learning](https://mlsanity.com/paper/2608.11052/) (2026)
- [Efficient Linear Bandits via Cluster-Aware Sketching](https://mlsanity.com/paper/2609.27594/) (2026)
- [Accelerating Linear Bandits with Persistent Candidate Sets](https://mlsanity.com/paper/2610.13407/) (2026)

## Abstract (arXiv)

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 O(md) update time for both algorithms, as opposed to Omega(d2) 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+varepsilonm)3/2d√T for OFUL and of order big((1+varepsilonm)dbig)3/2√T for Thompson Sampling, where varepsilonm 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.