# Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 42 references that are in the map.
- First posted on arXiv 7 Nov 2023.

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

- [BOHB: Robust and Efficient Hyperparameter Optimization at Scale](https://mlsanity.com/paper/1807.01774/) (2018)
- [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)
- [Fast Bayesian Optimization of Machine Learning Hyperparameters on Large Datasets](https://mlsanity.com/paper/1605.07079/) (2016)
- [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)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [Joint Entropy Search for Maximally-Informed Bayesian Optimization](https://mlsanity.com/paper/2206.04771/) (2022)
- [No-Regret Bayesian Optimization with Unknown Hyperparameters](https://mlsanity.com/paper/1901.03357/) (2019)
- [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)
- [Regret bounds for meta Bayesian optimization with an unknown Gaussian process prior](https://mlsanity.com/paper/1811.09558/) (2018)
- [Olympus: a benchmarking framework for noisy optimization and experiment planning](https://mlsanity.com/paper/2010.04153/) (2020)
- [Sequential- and Parallel- Constrained Max-value Entropy Search via Information Lower Bound](https://mlsanity.com/paper/2102.09788/) (2021)
- [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)

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

- [Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance](https://mlsanity.com/paper/2502.06363/) (2025)
- [Variational Search Distributions](https://mlsanity.com/paper/2409.06142/) (2024)
- [Regret Analysis for Randomized Gaussian Process Upper Confidence Bound](https://mlsanity.com/paper/2409.00979/) (2024)
- [Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2507.09828/) (2025)
- [A Quadrature Approach for General-Purpose Batch Bayesian Optimization via Probabilistic Lifting](https://mlsanity.com/paper/2404.12219/) (2024)
- [Distributionally Robust Active Learning for Gaussian Process Regression](https://mlsanity.com/paper/2502.16870/) (2025)
- [On Regret Bounds of Thompson Sampling for Bayesian Optimization](https://mlsanity.com/paper/2603.09276/) (2026)
- [Bayesian Analysis of Combinatorial Gaussian Process Bandits](https://mlsanity.com/paper/2312.12676/) (2023)
- [Adaptive Prior Selection in Gaussian Process Bandits with Thompson Sampling](https://mlsanity.com/paper/2502.01226/) (2025)
- [Randomized Kriging Believer for Parallel Bayesian Optimization with Regret Bounds](https://mlsanity.com/paper/2603.01470/) (2026)
- [Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spaces](https://mlsanity.com/paper/2603.08287/) (2026)
- [Thompson Sampling in Function Spaces via Neural Operators](https://mlsanity.com/paper/2506.21894/) (2025)
- [Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2608.16492/) (2026)
- [Information-Theoretic Bayesian Optimization for Bilevel Optimization Problems](https://mlsanity.com/paper/2509.21725/) (2025)
- [Towards Regret Guarantees for One-Step Lookahead Bayesian Optimization](https://mlsanity.com/paper/2606.00956/) (2026)
- [Principled Design of Expected Improvement for Continuous Simulation Optimization](https://mlsanity.com/paper/2610.18434/) (2026)

## Abstract (arXiv)

Among various acquisition functions (AFs) in Bayesian optimization (BO), Gaussian process upper confidence bound (GP-UCB) and Thompson sampling (TS) are well-known options with established theoretical properties regarding Bayesian cumulative regret (BCR). Recently, it has been shown that a randomized variant of GP-UCB achieves a tighter BCR bound compared with GP-UCB, which we call the tighter BCR bound for brevity. Inspired by this study, this paper first shows that TS achieves the tighter BCR bound. On the other hand, GP-UCB and TS often practically suffer from manual hyperparameter tuning and over-exploration issues, respectively. Therefore, we analyze yet another AF called a probability of improvement from the maximum of a sample path (PIMS). We show that PIMS achieves the tighter BCR bound and avoids the hyperparameter tuning, unlike GP-UCB. Furthermore, we demonstrate a wide range of experiments, focusing on the effectiveness of PIMS that mitigates the practical issues of GP-UCB and TS.