# Regret Analysis for Randomized Gaussian Process Upper Confidence Bound

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 64 references that are in the map.
- First posted on arXiv 2 Sep 2024.

## Builds on (most cited first, 29 of 29)

- [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)
- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [High Dimensional Bayesian Optimisation and Bandits via Additive Models](https://mlsanity.com/paper/1503.01673/) (2015)
- [Multi-fidelity Bayesian Optimisation with Continuous Approximations](https://mlsanity.com/paper/1703.06240/) (2017)
- [A Flexible Framework for Multi-Objective Bayesian Optimization using Random Scalarizations](https://mlsanity.com/paper/1805.12168/) (2018)
- [ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendations](https://mlsanity.com/paper/1908.01425/) (2019)
- [Adversarially Robust Optimization with Gaussian Processes](https://mlsanity.com/paper/1810.10775/) (2018)
- [Multi-objective Bayesian Optimization using Pareto-frontier Entropy](https://mlsanity.com/paper/1906.00127/) (2019)
- [Joint Entropy Search for Maximally-Informed Bayesian Optimization](https://mlsanity.com/paper/2206.04771/) (2022)
- [Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration](https://mlsanity.com/paper/1304.5350/) (2013)
- [Benchmarking the Performance of Bayesian Optimization across Multiple Experimental Materials Science Domains](https://mlsanity.com/paper/2106.01309/) (2021)
- [Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation](https://mlsanity.com/paper/1610.07379/) (2016)
- [Bandit optimisation of functions in the Mat'ern kernel RKHS](https://mlsanity.com/paper/2001.10396/) (2020)
- [Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameters](https://mlsanity.com/paper/1406.7758/) (2014)
- [Sequential- and Parallel- Constrained Max-value Entropy Search via Information Lower Bound](https://mlsanity.com/paper/2102.09788/) (2021)
- [Randomised Gaussian Process Upper Confidence Bound for Bayesian Optimisation](https://mlsanity.com/paper/2006.04296/) (2020)
- [Tight Regret Bounds for Bayesian Optimization in One Dimension](https://mlsanity.com/paper/1805.11792/) (2018)
- [Mean-Variance Analysis in Bayesian Optimization under Uncertainty](https://mlsanity.com/paper/2009.08166/) (2020)
- [Optimization as Estimation with Gaussian Processes in Bandit Settings](https://mlsanity.com/paper/1510.06423/) (2015)
- [Bayesian Optimization for Cascade-type Multi-stage Processes](https://mlsanity.com/paper/2111.08330/) (2021)
- [Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Bounds](https://mlsanity.com/paper/2302.01511/) (2023)
- [Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds](https://mlsanity.com/paper/2311.03760/) (2023)
- [Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2203.07875/) (2022)
- [Bayesian Optimization for Distributionally Robust Chance-constrained Problem](https://mlsanity.com/paper/2201.13112/) (2022)
- [Bounding Box-based Multi-objective Bayesian Optimization of Risk Measures under Input Uncertainty](https://mlsanity.com/paper/2301.11588/) (2023)
- [Active Learning for Level Set Estimation Using Randomized Straddle Algorithms](https://mlsanity.com/paper/2408.03144/) (2024)

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

- [On Regret Bounds of Thompson Sampling for Bayesian Optimization](https://mlsanity.com/paper/2603.09276/) (2026)
- [Randomized Kriging Believer for Parallel Bayesian Optimization with Regret Bounds](https://mlsanity.com/paper/2603.01470/) (2026)
- [Towards Regret Guarantees for One-Step Lookahead Bayesian Optimization](https://mlsanity.com/paper/2606.00956/) (2026)
- [Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration](https://mlsanity.com/paper/2608.18863/) (2026)

## Abstract (arXiv)

Gaussian process upper confidence bound (GP-UCB) is a theoretically established algorithm for Bayesian optimization (BO), where we assume the objective function f follows a GP. One notable drawback of GP-UCB is that the theoretical confidence parameter β increases along with the iterations and is too large. To alleviate this drawback, this paper analyzes the randomized variant of GP-UCB called improved randomized GP-UCB (IRGP-UCB), which uses the confidence parameter generated from the shifted exponential distribution. We analyze the expected regret and conditional expected regret, where the expectation and the probability are taken respectively with f and noise and with the randomness of the BO algorithm. In both regret analyses, IRGP-UCB achieves a sub-linear regret upper bound without increasing the confidence parameter if the input domain is finite. Furthermore, we show that randomization plays a key role in avoiding an increase in confidence parameter by showing that GP-UCB using a constant confidence parameter can incur linearly growing expected cumulative regret. Finally, we show numerical experiments using synthetic and benchmark functions and real-world emulators.