mlsanityData to 14 Oct 2026

Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds

arXiv 2311.03760 ↗First posted 7 Nov 2023cs.LG stat.MLcited by 16

Not on the map. Why?

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.

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

21 of 42 references.

References · 21

  1. 2018BOHB: Robust and Efficient Hyperparameter Optimization at Scalecited by 470
  2. 2017On Kernelized Multi-armed Banditscited by 352
  3. 2013Learning to Optimize Via Posterior Samplingcited by 256
  4. 2017Max-value Entropy Search for Efficient Bayesian Optimizationcited by 206
  5. 2014Predictive Entropy Search for Efficient Global Optimization of Black-box Functionscited by 204
  6. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  7. 2015High Dimensional Bayesian Optimisation and Bandits via Additive Modelscited by 139
  8. 2016Fast Bayesian Optimization of Machine Learning Hyperparameters on Large Datasetscited by 132
  9. 2018A Flexible Framework for Multi-Objective Bayesian Optimization using Random Scalarizationscited by 99
  10. 2019ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendationscited by 77
  11. 2021Misspecified Gaussian Process Bandit Optimizationcited by 55
  12. 2022Joint Entropy Search for Maximally-Informed Bayesian Optimizationcited by 55
9 more
  1. 2019No-Regret Bayesian Optimization with Unknown Hyperparameterscited by 51
  2. 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
  3. 2014Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameterscited by 31
  4. 2018Regret bounds for meta Bayesian optimization with an unknown Gaussian process priorcited by 31
  5. 2020Olympus: a benchmarking framework for noisy optimization and experiment planningcited by 29
  6. 2021Sequential- and Parallel- Constrained Max-value Entropy Search via Information Lower Boundcited by 23
  7. 2015Optimization as Estimation with Gaussian Processes in Bandit Settingscited by 17
  8. 2021Bayesian Optimization for Cascade-type Multi-stage Processescited by 17
  9. 2023Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Boundscited by 16

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 3; 2025: 6; 2026: 6.

16 papers.

Sort:

By area:

  1. 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 15
  2. 2024Variational Search Distributionscited by 6
  3. 2024Regret Analysis for Randomized Gaussian Process Upper Confidence Boundcited by 4
  4. 2025Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimizationcited by 4
  5. 2024A Quadrature Approach for General-Purpose Batch Bayesian Optimization via Probabilistic Liftingcited by 3
  6. 2025Distributionally Robust Active Learning for Gaussian Process Regressioncited by 3
  7. 2026On Regret Bounds of Thompson Sampling for Bayesian Optimizationcited by 3
  8. 2023Bayesian Analysis of Combinatorial Gaussian Process Banditscited by 2
  9. 2025Adaptive Prior Selection in Gaussian Process Bandits with Thompson Samplingcited by 2
  10. 2026Randomized Kriging Believer for Parallel Bayesian Optimization with Regret Boundscited by 2
  11. 2026Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spacescited by 2
  12. 2025Thompson Sampling in Function Spaces via Neural Operatorscited by 1
4 more
  1. 2026Improved Regret Analysis for Parallel Gaussian Process Bandit Optimizationcited by 1
  2. 2025Information-Theoretic Bayesian Optimization for Bilevel Optimization Problemscited by 0
  3. 2026Towards Regret Guarantees for One-Step Lookahead Bayesian Optimizationcited by 0
  4. 2026Principled Design of Expected Improvement for Continuous Simulation Optimizationcited by 0