Nearly Optimal Algorithms for Adversarial Kernelized Bandits

Abstract

This paper studies kernelized bandits (also known as Gaussian process bandits) in an adversarial environment, where the reward functions in a known reproducing kernel Hilbert space (RKHS) may be adversarially chosen at each round. We show that the exponential-weight algorithm achieves $\tilde{O}(\sqrt{T{\gamma }_T})$ adversarial regret, where $T$ and ${\gamma }_T$ denote the number of total rounds and the maximum information gain, respectively. For squared exponential (SE) and $\nu$-Matérn kernels, we also show algorithm-independent lower bounds that guarantee the optimality of our algorithm up to polylogarithmic factors. Furthermore, we present a computationally efficient variant of our algorithm using Nyström approximation while maintaining nearly optimal regret guarantees.

arXiv comment47 pages. Accepted at NeurIPS 2026. This version corrects minor errors and typographical mistakes in v1