Efficient Linear Bandits through Matrix Sketching

2018/09/28 by Kuzborskij, Ilja, Cella, Leonardo, Cesa-Bianchi, Nicolò · 1 citation
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1809.11033

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 O(md) update time for both algorithms, as opposed to Ω(d²) 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+ε_m)^3/2d√(T) for OFUL and of order ((1+ε_m)d)^3/2√(T) for Thompson Sampling, where ε_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

• Scalable LinUCB: Low-Rank Design Matrix Updates for Recommenders with Large Action Spaces

Related

• Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketching
• Frequent Directions : Simple and Deterministic Matrix Sketching
• Simple and Deterministic Matrix Sketching
• Matrix Product Sketching via Coordinated Sampling
• Improved Practical Matrix Sketching with Guarantees