# Efficient Kernel UCB for Contextual Bandits

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 22 references that are in the map.
- First posted on arXiv 11 Feb 2022.

## Builds on (most cited first, 11 of 11)

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits](https://mlsanity.com/paper/2010.12247/) (2020)
- [Bayesian experimental design using regularized determinantal point processes](https://mlsanity.com/paper/1906.04133/) (2019)
- [Second-Order Kernel Online Convex Optimization with Adaptive Sketching](https://mlsanity.com/paper/1706.04892/) (2017)
- [Near-linear Time Gaussian Process Optimization with Adaptive Batching and Resparsification](https://mlsanity.com/paper/2002.09954/) (2020)
- [Efficient Linear Bandits through Matrix Sketching](https://mlsanity.com/paper/1809.11033/) (2018)
- [Efficient online learning with kernels for adversarial large scale problems](https://mlsanity.com/paper/1902.09917/) (2019)

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

- [Communication Efficient Distributed Learning for Kernelized Contextual Bandits](https://mlsanity.com/paper/2206.04835/) (2022)
- [Stochastic Graph Bandit Learning with Side-Observations](https://mlsanity.com/paper/2308.15107/) (2023)
- [Dual Instrumental Method for Confounded Kernelized Bandits](https://mlsanity.com/paper/2209.03224/) (2022)

## Abstract (arXiv)

In this paper, we tackle the computational efficiency of kernelized UCB algorithms in contextual bandits. While standard methods require a O(CT3) complexity where T is the horizon and the constant C is related to optimizing the UCB rule, we propose an efficient contextual algorithm for large-scale problems. Specifically, our method relies on incremental Nystrom approximations of the joint kernel embedding of contexts and actions. This allows us to achieve a complexity of O(CTm2) where m is the number of Nystrom points. To recover the same regret as the standard kernelized UCB algorithm, m needs to be of order of the effective dimension of the problem, which is at most O(√(T)) and nearly constant in some cases.