Sharper Guarantees for Misspecified Kernelized Bandit Optimization

• URL: http://arxiv.org/abs/2605.05967v1
• Date: Thu, 07 May 2026 10:12:56 GMT
• Title: Sharper Guarantees for Misspecified Kernelized Bandit Optimization
• Abstract summary: We show that for a large class of kernels, the misspecification amplification can be reduced to logarithmic or polylogarithmic growth.<n>In the offline setting, we first prove high-probability simple-regret bounds whose misspecification term is governed by a spectral Lebesgue constant.<n>In the online setting, we modify a domain-splitting algorithm and prove a cumulative regret bound of $widetildemathcal O(sqrt_n n+nvarepsilon)$ under mild localized eigendecay assumptions.
• Score: 34.863425530383545
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Existing guarantees for misspecified kernelized bandit optimization pay for misspecification through kernel complexity: in generic offline bounds, the misspecification level $\varepsilon$ is multiplied by $\sqrt{d_\mathrm{eff}}$, where $d_\mathrm{eff}$ is the kernel effective dimension, while in online regret bounds, the corresponding penalty is $\sqrt{γ_n}\,n\varepsilon$, where $γ_n$ is the maximum information gain after $n$ rounds of interaction. In this work, we show that, for a large class of kernels, the misspecification amplification can be reduced to logarithmic or polylogarithmic growth. In the offline setting, we first prove high-probability simple-regret bounds whose misspecification term is governed by a spectral Lebesgue constant. This yields logarithmic amplification for one-dimensional monotone spectra and polylogarithmic amplification for multivariate Fourier-diagonal product kernels. In the online setting, we modify a domain-splitting algorithm and prove a cumulative regret bound of $\widetilde{\mathcal O}(\sqrt{γ_n n}+n\varepsilon)$ under mild localized eigendecay assumptions, removing the extra $\sqrt{γ_n}$ factor from the misspecification term. The common principle is localization: spectral localization controls the Lebesgue constant of the offline approximation operator, while domain splitting implements the spatial analogue of this mechanism in the online setting, preventing local misspecification errors from being amplified globally.

Related papers

• Near-Optimal Regret in Adversarial Kernel Bandits [50.68324062892194]
  We study the adversarial kernel bandit problem, in which the loss at each round is induced by an arbitrary bounded element.<n>Our main result bounds the regret by $widetildeObig(sqrtT, d_*(),log|X|big)$, where $d_*()$ is a widely-adopted notion of effective dimension.
  arXiv  Detail & Related papers  (2026-05-26T06:10:24Z)
• Quantum Differential Equation Solver via Hybrid Oscillator-Qubit Linear Combination of Hamiltonian Simulations [7.438217717051814]
  We introduce a hybrid oscillator-qubit formulation of linear combination of Hamiltonian simulation (LCHS)<n>Instead of representing the quadrature rule with a discrete-variable (DV) ancilla register in qubit-only LCHS, the method encodes the LCHS kernel in a continuous-variable ancillary mode.<n>In the heat-equation benchmarks, the Law--Eberly protocol achieves end-to-end solution fidelity at least 99.90%.
  arXiv  Detail & Related papers  (2026-05-11T15:20:35Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• 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)
• Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy [13.264499801590583]
  We introduce new high-probability spectral-norm perturbation bounds for symmetric matrix $A in mathbbRn times n$ and an arbitrary symmetric perturbationE$.<n>Under mild eigengap and norm conditions, our bounds yield sharp estimates for $|(A + E)_p - A_p|$, with improvements of up to a factor of $sqrtn$.<n>As an application, we derive improved utility guarantees for differentially private PCA, resolving an open problem in the literature.
  arXiv  Detail & Related papers  (2025-10-29T16:36:00Z)
• 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)
• Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Bias [21.64772960240025]
  We show that as the dimension $d$ of the problem increases, the number of iterations required to ensure convergence within a desired error increases.<n>A key technical challenge we address is the lack of a one-step contraction property in the $W_2,ellinfty$ metric to measure convergence.
  arXiv  Detail & Related papers  (2024-08-20T01:24:54Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• 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)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  We introduce a batch algorithm inspired by finite-arm bandit algorithms. We show that it achieves the cumulative regret upper bound $Oast(sqrtTgamma_T)$ using $O(loglog T)$ batches within time horizon $T$. In addition, we propose a modified version of our algorithm, and characterize how the regret is impacted by the number of batches.
  arXiv  Detail & Related papers  (2021-10-15T00:54:04Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  Solving optimal transport with an entropic regularization requires computing a $ntimes n$ kernel matrix that is repeatedly applied to a vector. We propose to use instead ground costs of the form $c(x,y)=-logdotpvarphi(x)varphi(y)$ where $varphi$ is a map from the ground space onto the positive orthant $RRr_+$, with $rll n$.
  arXiv  Detail & Related papers  (2020-06-12T10:21:40Z)

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.