# Exploration strategies for Gaussian process bandit optimization with inference regret guarantees

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 31 of its 56 references that are in the map.
- First posted on arXiv 12 Oct 2026.

## Builds on (most cited first, 30 of 31)

- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Max-value Entropy Search for Efficient Bayesian Optimization](https://mlsanity.com/paper/1703.01968/) (2017)
- [Neural Architecture Search with Bayesian Optimisation and Optimal Transport](https://mlsanity.com/paper/1802.07191/) (2018)
- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [BANANAS: Bayesian Optimization with Neural Architectures for Neural Architecture Search](https://mlsanity.com/paper/1910.11858/) (2019)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Unexpected Improvements to Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2310.20708/) (2023)
- [Bayesian Optimization is Superior to Random Search for Machine Learning Hyperparameter Tuning: Analysis of the Black-Box Optimization Challenge 2020](https://mlsanity.com/paper/2104.10201/) (2021)
- [Practical Multi-fidelity Bayesian Optimization for Hyperparameter Tuning](https://mlsanity.com/paper/1903.04703/) (2019)
- [Bayesian optimization for materials design](https://mlsanity.com/paper/1506.01349/) (2015)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [A Literature Survey of Benchmark Functions For Global Optimization Problems](https://mlsanity.com/paper/1308.4008/) (2013)
- [BayesNAS: A Bayesian Approach for Neural Architecture Search](https://mlsanity.com/paper/1905.04919/) (2019)
- [Tuning Hyperparameters without Grad Students: Scalable and Robust Bayesian Optimisation with Dragonfly](https://mlsanity.com/paper/1903.06694/) (2019)
- [Bayesian Optimization for Materials Design with Mixed Quantitative and Qualitative Variables](https://mlsanity.com/paper/1910.01688/) (2019)
- [YAHPO Gym -- An Efficient Multi-Objective Multi-Fidelity Benchmark for Hyperparameter Optimization](https://mlsanity.com/paper/2109.03670/) (2021)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Greed is Good: Exploration and Exploitation Trade-offs in Bayesian Optimisation](https://mlsanity.com/paper/1911.12809/) (2019)
- [On the Sublinear Regret of GP-UCB](https://mlsanity.com/paper/2307.07539/) (2023)
- [Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency](https://mlsanity.com/paper/2310.15351/) (2023)
- [Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance](https://mlsanity.com/paper/2502.06363/) (2025)
- [Epsilon-Greedy Thompson Sampling to Bayesian Optimization](https://mlsanity.com/paper/2403.00540/) (2024)
- [Enhancing Gaussian Process Surrogates for Optimization and Posterior Approximation via Random Exploration](https://mlsanity.com/paper/2401.17037/) (2024)
- [Tighter Confidence Bounds for Sequential Kernel Regression](https://mlsanity.com/paper/2403.12732/) (2024)
- [Optimization on Manifolds via Graph Gaussian Processes](https://mlsanity.com/paper/2210.10962/) (2022)
- [Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient?](https://mlsanity.com/paper/2506.11831/) (2025)
- [Quasi-uniform designs with optimal and near-optimal uniformity constant](https://mlsanity.com/paper/2112.10401/) (2021)
- [On Regret Bounds of Thompson Sampling for Bayesian Optimization](https://mlsanity.com/paper/2603.09276/) (2026)

## Abstract (arXiv)

Existing cumulative regret guarantees for Bayesian optimization (BO) do not necessarily characterize the quality of the algorithm's final output. This gap is critical under noisy evaluations, where the goal is to return a single high-quality recommendation. To address it, we introduce efficient exploration strategies that can be incorporated into any BO procedure by occasionally replacing the acquisition query with an exploration query. To validate this approach, we bound the Gaussian process posterior standard deviation over the search space via the fill distance of the queries, which measures the largest region left unexplored. We then use this result to derive upper bounds on the inference regret, i.e., the gap between the global optimum and the function value at the algorithm's returned point. Empirically, these exploration strategies improve the final recommendations of existing BO algorithms on synthetic benchmarks, hyperparameter optimization, and a control task.