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

• URL: http://arxiv.org/abs/2508.01681v1
• Date: Sun, 03 Aug 2025 09:23:19 GMT
• Title: Generalized Kernelized Bandits: Self-Normalized Bernstein-Like Dimension-Free Inequality and Regret Bounds
• Authors: Alberto Maria Metelli, Simone Drago, Marco Mussi,
• Abstract summary: We study the regret problem in the novel setting of generalized kernelized bandits (GKBs)<n>We propose an optimistic algorithm, GKB-UCB, and we explain why existing self-normalized concentration inequalities do not allow to provide tight regret guarantees.
• Score: 18.662468634576218
• License: http://creativecommons.org/licenses/by/4.0/
• 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) noise model whose mean is a non-linear function $\mu(f^*)$. This model extends both kernelized bandits (KBs) and generalized linear bandits (GLBs). We propose an optimistic algorithm, GKB-UCB, and we explain why existing self-normalized concentration inequalities do not allow to provide tight regret guarantees. For this reason, we devise a novel self-normalized Bernstein-like dimension-free inequality resorting to Freedman's inequality and a stitching argument, which represents a contribution of independent interest. Based on it, we conduct a regret analysis of GKB-UCB, deriving a regret bound of order $\widetilde{O}( \gamma_T \sqrt{T/\kappa_*})$, being $T$ the learning horizon, ${\gamma}_T$ the maximal information gain, and $\kappa_*$ a term characterizing the magnitude the reward nonlinearity. Our result matches, up to multiplicative constants and logarithmic terms, the state-of-the-art bounds for both KBs and GLBs and provides a unified view of both settings.

Related papers

• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Harmful Overfitting in Sobolev Spaces [49.47221415754556]
  We study the generalization behavior of functions in Sobolev spaces $Wk, p(mathbbRd)$ that perfectly fit a noisy training data set.<n>We show that approximately norm-minimizing interpolators, which are canonical solutions selected by smoothness bias, exhibit harmful overfitting.<n>Our proof uses a geometric argument which identifies harmful neighborhoods of the training data using Sobolev inequalities.
  arXiv  Detail & Related papers  (2026-01-31T17:40:56Z)
• Differential Privacy in Kernelized Contextual Bandits via Random Projections [8.658538065693206]
  We consider the problem of contextual kernel bandits with contexts.<n>The underlying reward function belongs to a known Reproducing Kernel Hilbert Space.<n>We propose a novel algorithm that achieves the state-of-the-art cumulative regret of $widetildemathcalO(sqrtgamma_TT+fracgamma_Tvarepsilon_mathrmDP)$
  arXiv  Detail & Related papers  (2025-07-18T03:54:49Z)
• Variance-Optimal Arm Selection: Regret Minimization and Best Arm Identification [3.5502600490147196]
  We develop an online algorithm called textttUCB-VV for the regret setting and show that its upper bound on regret for bounded rewards evolves as $mathcalOleft(lognright)$.<n>We extend the framework from bounded distributions to sub-Gaussian distributions using a novel concentration inequality on the sample variance.
  arXiv  Detail & Related papers  (2025-05-17T12:38:23Z)
• Differentially Private Kernelized Contextual Bandits [8.658538065693206]
  We consider the problem of contextual kernel bandits with contexts, where the underlying reward function belongs to a known Reproducing Kernel Hilbert Space (RKHS)<n>We propose a novel algorithm that improves upon the state of the art and achieves an error rate of $mathcalOleft(sqrtfracgamma_TT + fracgamma_TT varepsilonright)$ after $T$ queries.
  arXiv  Detail & Related papers  (2025-01-13T04:05:19Z)
• Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees [56.80920351680438]
  We study high-probability convergence in online learning, in the presence of heavy-tailed noise.<n>We provide guarantees for a broad class of nonlinearities, without any assumptions on noise moments.
  arXiv  Detail & Related papers  (2024-10-17T18:25:28Z)
• Achieving Constant Regret in Linear Markov Decision Processes [57.34287648914407]
  We introduce an algorithm, Cert-LSVI-UCB, for misspecified linear Markov decision processes (MDPs)<n>We show that Cert-LSVI-UCB has a cumulative regret of $tildemathcalO(d3H5/Delta)$ with high probability, provided that the misspecification level $zeta$ is below $tildemathcalO(Delta / (sqrtdH2))$.
  arXiv  Detail & Related papers  (2024-04-16T17:23:19Z)
• Generalized Linear Bandits with Limited Adaptivity [12.112051468737596]
  We study the generalized linear contextual bandit problem within the constraints of limited adaptivity.<n>We present two algorithms, $textttB-GLinCB$ and $textttRS-GLinCB$, that address, respectively, two prevalent limited adaptivity settings.
  arXiv  Detail & Related papers  (2024-04-10T08:47:57Z)
• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  We show that wetailed high-prob convergence guarantees of learning on streaming data in the presence of heavy-tailed noise. We demonstrate analytically and that $ta$ can be used to the preferred choice of setting for a given problem.
  arXiv  Detail & Related papers  (2023-10-28T18:53:41Z)
• Adversarial Contextual Bandits Go Kernelized [21.007410990554522]
  We study a generalization of the problem of online learning in adversarial linear contextual bandits by incorporating loss functions that belong to a Hilbert kernel space. We propose a new optimistically biased estimator for the loss functions and reproducing near-optimal regret guarantees.
  arXiv  Detail & Related papers  (2023-10-02T19:59:39Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  We present the first computationally efficient algorithm for linear bandits with heteroscedastic noise. Our algorithm is adaptive to the unknown variance of noise and achieves an $tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regret. We also propose a variance-adaptive algorithm for linear mixture Markov decision processes (MDPs) in reinforcement learning.
  arXiv  Detail & Related papers  (2023-02-21T00:17:24Z)
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
  We study the regret of Thompson sampling (TS) algorithms for exponential family bandits, where the reward distribution is from a one-dimensional exponential family. We propose a Thompson sampling, termed Expulli, which uses a novel sampling distribution to avoid the under-estimation of the optimal arm.
  arXiv  Detail & Related papers  (2022-06-07T18:08:21Z)
• On Kernelized Multi-Armed Bandits with Constraints [16.102401271318012]
  We study a bandit problem with a general unknown reward function and a general unknown constraint function. We propose a general framework for both algorithm performance analysis. We demonstrate the superior performance of our proposed algorithms via numerical experiments.
  arXiv  Detail & Related papers  (2022-03-29T14:02:03Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  Kernelized bandit algorithms have shown strong empirical and theoretical performance for this problem. We introduce a emphmisspecified kernelized bandit setting where the unknown function can be $epsilon$--uniformly approximated by a function with a bounded norm in some Reproducing Kernel Hilbert Space (RKHS) We show that our algorithm achieves optimal dependence on $epsilon$ with no prior knowledge of misspecification.
  arXiv  Detail & Related papers  (2021-11-09T09:00:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.