# Efficient kernelized bandit algorithms via exploration distributions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 1 references that are in the map.
- First posted on arXiv 11 Jun 2025.

## Abstract (arXiv)

We consider a kernelized bandit problem with a compact arm set X subset ℝd  and a fixed but unknown reward function f^* with a finite norm in some Reproducing Kernel Hilbert Space (RKHS). We propose a class of computationally efficient kernelized bandit algorithms, which we call GP-Generic, based on a novel concept: exploration distributions. This class of algorithms includes Upper Confidence Bound-based approaches as a special case, but also allows for a variety of randomized algorithms. With careful choice of exploration distribution, our proposed generic algorithm realizes a wide range of concrete algorithms that achieve tildeO(γT√T) regret bounds, where γT characterizes the RKHS complexity. This matches known results for UCB- and Thompson Sampling-based algorithms; we also show that in practice, randomization can yield better practical results.