Sharper Guarantees for Misspecified Kernelized Bandit Optimization: Breaking the Complexity Barrier

TL;DR

In both offline and online optimization, "misspecification"—the gap between our model's assumptions and reality—is usually a performance killer. Modern theoretical bounds suggest that this error is amplified by the complexity of the kernel itself (often $\sqrt{d_{eff}}$). This paper by Maran and Szepesvári (NeurIPS 2026/preview) proves that for a large class of kernels (like Matérn or Fourier-diagonal products), this amplification is much weaker—only logarithmic. By "localizing" the problem spectrally and spatially, they achieve a regret bound for kernel bandits that effectively removes the complexity penalty from the misspecified term.

The Hidden Cost of Model Complexity

In supervised learning, we often care about average error. In bandits and RL, we care about pointwise error because one bad estimate can lead the agent to ignore the optimal arm forever.

The prevailing wisdom has been pessimistic: if your function $f$ is $\epsilon$-close to your kernel space $\mathcal{H}$, your regret will still be hit by $\sqrt{{\gamma }_n}\cdot n\epsilon$. As the kernel becomes more complex (higher information gain ${\gamma }_n$), the penalty for being slightly wrong grows. This creates a paradox where a "better" (more expressive) model can actually lead to worse performance because it amplifies the misspecification more aggressively.

Methodology: The Localization Principle

The authors propose a "unifying principle of localization" to solve this.

1. Spectral Localization (Offline Setting)

For offline KRR, the authors identify the Lebesgue constant $\Lambda ({\mathsf{P}}_{au})$ as the true culprit. While generic bounds suggest $\Lambda ({\mathsf{P}}_{au})\le \sqrt{d_{eff}}$, the authors prove that for kernels with "spectral smoothness" (monotone eigenvalue decay), the constant is actually logarithmic: $\Lambda ({\mathsf{P}}_{au})\lesssim \log (e+\kappa /au)$

2. Spatial Localization (Online Setting)

In the bandit setting, you can't rely on a fixed spectral basis because the data distribution is adaptive. Instead, the authors use Domain Splitting.

Note: The algorithm (π-MISSPEC-GP-UCB) uses a dyadic partition of the input space. When a region gets too many samples, it splits. This keeps the "information gain" per region low and prevents a local misspecification from infecting the global model.

The key innovation is the Exploration Bonus: ${\beta }_t^A:=\frac{R}{\sqrt{\lambda }}\sqrt{\cdots +{\gamma }_N}+B+\epsilon \sqrt{\frac{N_{t-1}^A}{\lambda }}$ This bonus explicitly accounts for the local sample count $N$ and the misspecification $\epsilon$, ensuring the UCB stays valid even when the model is wrong.

Experimental Insight: The Persistent Regret Floor

While the paper is primarily theoretical, it addresses a fascinating "Paradox of Nested Classes." Even if you have a sequence of models where the error ${\epsilon }_{m}o0$, your regret might never vanish if the complexity $m$ grows too fast.

Note: Figure summary from Table 1 - This work improves the misspecification term from $O(\sqrt{{\gamma }_n}n\epsilon )$ to $O(n\epsilon )$, a significant reduction for kernels like Matérn where ${\gamma }_n$ grows with $n$.

Critical Analysis & Takeaways

The brilliance of this work lies in moving away from "worst-case" feature maps (which justify the $\sqrt{d}$ penalty) to "structured" kernels (which justify the $\log$ penalty).

Key Takeaways:

1. Structure overExpressivity: It's not just about how well your kernel can fit a function, but how its eigenvalues decay. Monotone decay is a powerful shield against misspecification.
2. Localize to Stabilize: If you suspect your model is misspecified, don't fit a global GP. Use domain-splitting or local KRR to "contain" the bias.

Limitations: The result relies on "Subdomain Eigendecay" (D2+) and "Bounded Eigenfunctions" (D3). While these hold for Matérn kernels, they might be harder to verify for arbitrary or learned kernels in Deep RL.

Future Outlook

This paves the way for "Robust Bayesian Optimization" where we can finally stop worrying about the exact smoothness of our target function, as long as we use localized estimation techniques.