Efficient Kernel UCB for Contextual Bandits

Houssam Zenati (1, 2) , Alberto Bietti (3) , Eustache Diemert (1) , Julien Mairal (2) , Matthieu Martin (1) , Pierre Gaillard (2)

1 Criteo AI Lab
2 Thoth - Apprentissage de modèles à partir de données massives
3 NYU - New York University [New York]

In this paper, we tackle the computational efficiency of kernelized UCB algorithms in contextual bandits. While standard methods require a $O(CT^3)$ 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 Nyström approximations of the joint kernel embedding of contexts and actions. This allows us to achieve a complexity of $O(CT m^2)$ where $m$ is the number of Nyström 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(\sqrt{T})$ and nearly constant in some cases.

Mots clés: Contextual bandits; Kernel methods

Domaines: Informatique [cs]; Mathématiques [math]

Houssam Zenati, Alberto Bietti, Eustache Diemert, Julien Mairal, Matthieu Martin, et al.. Efficient Kernel UCB for Contextual Bandits. International Conference on Artificial Intelligence and Statistics, Mar 2022, Valencia, Spain. pp.5689-5720. ⟨hal-03575953⟩