Efficient kernelized bandit algorithms via exploration distributions

2025/06/11 by Bingshan Hu, Hu, Bingshan, Zheng He +3
Decision Sciences · Computer Science · #Advanced Bandit Algorithms Research #Stochastic Gradient Optimization Techniques #Complexity and Algorithms in Graphs

paper · pdf · doi:10.48550/arxiv.2506.10091

Abstract

We consider a kernelized bandit problem with a compact arm set X ⊂ ℝ^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 O(γ_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.

Related

• On Kernelized Multi-Armed Bandits with Constraints
• On Kernelized Multi-armed Bandits
• Open Problem: Tight Bounds for Kernelized Multi-Armed Bandits with Bernoulli Rewards
• Kernel ε-Greedy for Multi-Armed Bandits with Covariates
• Pure Exploration Bandit Problem with General Reward Functions Depending on Full Distributions