Generalized Kernelized Bandits: A Novel Self-Normalized Bernstein-Like Dimension-Free Inequality and Regret Bounds

2025/08/03 by Alberto Maria Metelli, Metelli, Alberto Maria, Simone Drago +3 · 2 citations
Decision Sciences · Computer Science · #Advanced Bandit Algorithms Research #Stochastic Gradient Optimization Techniques #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2508.01681

Abstract

We study the regret minimization problem in the novel setting of generalized kernelized bandits (GKBs), where we optimize an unknown function f^* belonging to a reproducing kernel Hilbert space (RKHS) having access to samples generated by an exponential family (EF) reward model whose mean is a non-linear function μ(f^*). This setting extends both kernelized bandits (KBs) and generalized linear bandits (GLBs), providing a unified view of both settings. We propose an optimistic regret minimization algorithm, GKB-UCB, and we explain why existing self-normalized concentration inequalities used for KBs and GLBs do not allow to provide tight regret guarantees. For this reason, we devise a novel self-normalized Bernstein-like dimension-free inequality that applies to a Hilbert space of functions with bounded norm, representing a contribution of independent interest. Based on it, we analyze GKB-UCB, deriving a regret bound of order \widetildeO( γ_T √(T/κ_*)), being T the learning horizon, γ_T the maximal information gain, and κ_* a term characterizing the magnitude of the expected reward non-linearity. Our result is tight in its dependence on T, γ_T, and κ_* for both KBs and GLBs. Finally, we present a tractable version GKB-UCB, Trac-GKB-UCB, which attains similar regret guarantees, and we discuss its time and space complexity.

Citations

• Bernstein-type dimension-free concentration for self-normalised martingales
• Neural Logistic Bandits
• A Vector Bernstein Inequality for Self-Normalized Martingales
• A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits
• Open Problem: Tight Bounds for Kernelized Multi-Armed Bandits with Bernoulli Rewards
• Generalized Linear Bandits with Limited Adaptivity
• On the Sublinear Regret of GP-UCB
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency
• Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domains by Adaptive Discretization
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits
• Neural Thompson Sampling
• On Information Gain and Regret Bounds in Gaussian Process Bandits
• Bandit Algorithms
• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
• Improved Optimistic Algorithms for Logistic Bandits
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Time-uniform, nonparametric, nonasymptotic confidence sequences
• Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
• On Kernelized Multi-armed Bandits
• A Second-order Bound with Excess Losses
• Finite-Time Analysis of Kernelised Contextual Bandits
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• X-Armed Bandits
• Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws

Cited by

• Vector-valued self-normalized concentration inequalities beyond sub-Gaussianity
• A variational approach to dimension-free self-normalized concentration

Related

• Regret Bounds for Noise-Free Kernel-Based Bandits
• On the Sublinear Regret of GP-UCB
• On Information Gain and Regret Bounds in Gaussian Process Bandits
• On Kernelized Multi-Armed Bandits with Constraints
• Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization