# Online learning with kernel losses

arXiv: https://arxiv.org/abs/1802.09732 · HTML: https://mlsanity.com/paper/1802.09732/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2018.

## Built on by (most cited first, 12 of 12)

- [Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency](https://mlsanity.com/paper/2310.15351/) (2023)
- [Learning curves for Gaussian process regression with power-law priors and targets](https://mlsanity.com/paper/2110.12231/) (2021)
- [Sample Complexity of Kernel-Based Q-Learning](https://mlsanity.com/paper/2302.00727/) (2023)
- [Adversarial Contextual Bandits Go Kernelized](https://mlsanity.com/paper/2310.01609/) (2023)
- [Reward Imputation with Sketching for Contextual Batched Bandits](https://mlsanity.com/paper/2210.06719/) (2022)
- [Differentially Private Kernelized Contextual Bandits](https://mlsanity.com/paper/2501.07046/) (2025)
- [Dynamic Pricing and Demand Learning on a Large Network of Products: A PAC-Bayesian Approach](https://mlsanity.com/paper/2111.00790/) (2021)
- [Nearly-Optimal Algorithm for Adversarial Kernelized Bandits](https://mlsanity.com/paper/2605.10299/) (2026)
- [Fast Best-in-Class Regret for Contextual Bandits](https://mlsanity.com/paper/2510.15483/) (2025)
- [Sharper Guarantees for Misspecified Kernelized Bandit Optimization](https://mlsanity.com/paper/2605.05967/) (2026)
- [Near-Optimal Regret in Adversarial Kernel Bandits](https://mlsanity.com/paper/2605.26585/) (2026)
- [Instance-dependent Stochastic Lipschitz bandit](https://mlsanity.com/paper/2605.29748/) (2026)

## Abstract (arXiv)

We present a generalization of the adversarial linear bandits framework, where the underlying losses are kernel functions (with an associated reproducing kernel Hilbert space) rather than linear functions. We study a version of the exponential weights algorithm and bound its regret in this setting. Under conditions on the eigendecay of the kernel we provide a sharp characterization of the regret for this algorithm. When we have polynomial eigendecay μj ≤ O(j-β), we find that the regret is bounded by Rn ≤ O(nβ/(2(β-1))); while under the assumption of exponential eigendecay μj ≤ O(e-β j ), we get an even tighter bound on the regret Rn ≤ O(n1/2log(n)1/2). We also study the full information setting when the underlying losses are kernel functions and present an adapted exponential weights algorithm and a conditional gradient descent algorithm.