Research map / Bandits and online learning / Online convex optimization and games

Sharper Guarantees for Misspecified Kernelized Bandit Optimization

NeurIPS 2026 · Bandits and online learning › Online convex optimization and games · approach: Best-of-both-worlds bandit algorithms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that spectral localization of kernel ridge regression keeps the Lebesgue-constant misspecification amplification logarithmic (1D monotone spectra) or polylogarithmic (multivariate Fourier-diagonal product kernels) offline, and that a domain-splitting UCB (π-Misspec-GPUCB) achieves regret Õ(sqrt(γ_n n)+nε) online.

Problem

Misspecified kernelized bandit optimization: existing guarantees amplify the misspecification level ε by sqrt(d_eff) offline and by sqrt(γ_n) n ε online, which is harmful for kernels with large information gain.

Approach

Localization: spectral localization bounds the Lebesgue constant of the KRR population operator via discrete spectral smoothness (ℓ1 norm of finite differences of eigenvalue ratios), and domain splitting with a misspecification-inflated UCB bonus localizes online misspecification errors region by region.

Key results

• Offline: for 1D monotone spectra the Lebesgue constant satisfies Λ(P_τ) ≲ log(e+κ/τ), versus the generic sqrt(d_eff) bound.
• Online: π-Misspec-GPUCB achieves regret Õ(sqrt(γ_n n) + nε) under polysub and bounded eigenfunction assumptions, removing the extra sqrt(γ_n) factor from the misspecification term of EC-GP-UCB.
• Lower bound: for every s>1 there is a Fourier-diagonal kernel with polynomial effective dimension where Λ(P_τ) is of order sqrt(d_eff) along a subsequence of τ, so polynomial effective dimension alone does not give logarithmic amplification.

Surprising findings

• Polynomial effective dimension alone does not guarantee sub-sqrt(d_eff) Lebesgue constant; a constructed Fourier-diagonal kernel attains the worst-case sqrt(d_eff) behavior.

Limitations

• Offline bounds require Fourier-diagonal or monotone-spectrum kernels; standard non-periodic kernels like squared-exponential do not satisfy the spectral Lebesgue growth assumption by stationarity alone.
• Online result requires subdomain polynomial eigendecay and bounded eigenfunctions assumptions and a finite competitor set.
• Theoretical paper with no experiments.

Experimental setup

Metrics: simple regret cumulative regret Lebesgue constant

Baselines: EC-GP-UCB generic sqrt(d_eff) offline bound

Builds on: GP-UCB pi-GP-UCB EC-GP-UCB Mercer decomposition kernel ridge regression

Closest papers by meaning

• Misspecified Gaussian Process Bandit Optimization (NeurIPS 2021 · similarity 0.92)
• On Kernelized Multi-Armed Bandits with Constraints (NeurIPS 2022 · similarity 0.89)
• Near-Optimal Regret in Adversarial Kernel Bandits (NeurIPS 2026 · similarity 0.88)
• Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting (AAAI 2025 · similarity 0.87)
• Misspecified $Q$-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error (ICLR 2025 · similarity 0.87)
• Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance (ICML 2025 · similarity 0.87)