mlsanityData to 14 Oct 2026

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

arXiv 2508.01681 ↗First posted 3 Aug 2025cs.LG stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

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/kappa_*), being T the learning horizon, γT the maximal information gain, and kappa_* a term characterizing the magnitude of the expected reward non-linearity. Our result is tight in its dependence on T, γT, and kappa_* 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.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 22 of its 56 references that are in the map. First posted on arXiv 3 Aug 2025.

Builds on

22 of 56 references.

References · 22

  1. 2014Convex Optimization: Algorithms and Complexitycited by 575
  2. 2017On Kernelized Multi-armed Banditscited by 352
  3. 2018Time-uniform, nonparametric, nonasymptotic confidence sequencescited by 229
  4. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  5. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  6. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  7. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  8. 2020Neural Thompson Samplingcited by 128
  9. 2020Improved Optimistic Algorithms for Logistic Banditscited by 118
  10. 2014A Second-order Bound with Excess Lossescited by 95
  11. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  12. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 78
10 more
  1. 2020Instance-Wise Minimax-Optimal Algorithms for Logistic Banditscited by 57
  2. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 51
  3. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 40
  4. 2020Self-Concordant Analysis of Generalized Linear Bandits with Forgettingcited by 29
  5. 2024A Unified Confidence Sequence for Generalized Linear Models, with Applications to Banditscited by 29
  6. 2023On the Sublinear Regret of GP-UCBcited by 26
  7. 2024Generalized Linear Bandits with Limited Adaptivitycited by 22
  8. 2021Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domains by Adaptive Discretizationcited by 7
  9. 2025Neural Logistic Banditscited by 6
  10. 2024Open Problem: Tight Bounds for Kernelized Multi-Armed Bandits with Bernoulli Rewardscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 2.

4 papers.

  1. 2025Vector-valued self-normalized concentration inequalities beyond sub-Gaussianitycited by 4
  2. 2025A variational approach to dimension-free self-normalized concentrationcited by 2
  3. 2026Logistic Bandits with tildeO(√dT) Regret without Context Diversity Assumptionscited by 1
  4. 2026Learning Kernel-Based MDPs from Episodic Preferential Feedbackcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences
  2. 2026Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent
  3. 2024Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm
  4. 2023Reward Learning as Doubly Nonparametric Bandits: Optimal Design and Scaling Laws
  5. 2025Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits
  6. 2026Near-Optimal Regret for KL-Regularized Multi-Armed Bandits
  7. 2026On the Complexity of Preference-Based Bandits
  8. 2026Dynamic Minimax Regret Optimization for Robust LLM Post-Training