# Bayesian Optimization under Heavy-tailed Payoffs

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Sep 2019.

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

- [Design-Bench: Benchmarks for Data-Driven Offline Model-Based Optimization](https://mlsanity.com/paper/2202.08450/) (2022)
- [Weighted Gaussian Process Bandits for Non-stationary Environments](https://mlsanity.com/paper/2107.02371/) (2021)
- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [No-Regret Algorithms for Time-Varying Bayesian Optimization](https://mlsanity.com/paper/2102.06296/) (2021)
- [Risk-averse Heteroscedastic Bayesian Optimization](https://mlsanity.com/paper/2111.03637/) (2021)
- [No-Regret Reinforcement Learning with Heavy-Tailed Rewards](https://mlsanity.com/paper/2102.12769/) (2021)
- [A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits](https://mlsanity.com/paper/2202.01850/) (2022)
- [Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards](https://mlsanity.com/paper/2310.18701/) (2023)
- [Quantum Heavy-tailed Bandits](https://mlsanity.com/paper/2301.09680/) (2023)
- [Enhancing Gaussian Process Surrogates for Optimization and Posterior Approximation via Random Exploration](https://mlsanity.com/paper/2401.17037/) (2024)
- [Lower Bounds on the Worst-Case Complexity of Efficient Global Optimization](https://mlsanity.com/paper/2209.09655/) (2022)
- [Lower Bounds for Time-Varying Kernelized Bandits](https://mlsanity.com/paper/2410.16692/) (2024)
- [Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards](https://mlsanity.com/paper/2506.04775/) (2025)
- [Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere](https://mlsanity.com/paper/2602.17940/) (2026)
- [(Private) Kernelized Bandits with Distributed Biased Feedback](https://mlsanity.com/paper/2301.12061/) (2023)
- [On solutions of the distributional Bellman equation](https://mlsanity.com/paper/2202.00081/) (2022)
- [Trigonometric Quadrature Fourier Features for Scalable Gaussian Process Regression](https://mlsanity.com/paper/2310.14544/) (2023)
- [Safe Bayesian optimization across noise models via scenario programming](https://mlsanity.com/paper/2512.11580/) (2025)
- [Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processes](https://mlsanity.com/paper/2602.01295/) (2026)
- [On Uniform Error Bounds for Kernel Regression under Non-Gaussian Noise](https://mlsanity.com/paper/2605.09757/) (2026)
- [Robust Bayesian Optimization with Q-Exponential Surrogates](https://mlsanity.com/paper/2609.32775/) (2026)

## Abstract (arXiv)

We consider black box optimization of an unknown function in the nonparametric Gaussian process setting when the noise in the observed function values can be heavy tailed. This is in contrast to existing literature that typically assumes sub-Gaussian noise distributions for queries. Under the assumption that the unknown function belongs to the Reproducing Kernel Hilbert Space (RKHS) induced by a kernel, we first show that an adaptation of the well-known GP-UCB algorithm with reward truncation enjoys sublinear tildeO(T^frac2 + α2(1+α)) regret even with only the (1+α)-th moments, α ∈ (0,1], of the reward distribution being bounded (tildeO hides logarithmic factors). However, for the common squared exponential (SE) and Mat'ern kernels, this is seen to be significantly larger than a fundamental Omega(T^frac11+α) lower bound on regret. We resolve this gap by developing novel Bayesian optimization algorithms, based on kernel approximation techniques, with regret bounds matching the lower bound in order for the SE kernel. We numerically benchmark the algorithms on environments based on both synthetic models and real-world data sets.