# Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient?

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 55 references that are in the map.
- First posted on arXiv 13 Jun 2025.

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

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [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)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [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)
- [High Dimensional Bayesian Optimisation and Bandits via Additive Models](https://mlsanity.com/paper/1503.01673/) (2015)
- [Neural Thompson Sampling](https://mlsanity.com/paper/2010.00827/) (2020)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Maximizing acquisition functions for Bayesian optimization](https://mlsanity.com/paper/1805.10196/) (2018)
- [Practical Multi-fidelity Bayesian Optimization for Hyperparameter Tuning](https://mlsanity.com/paper/1903.04703/) (2019)
- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Bayesian optimization for materials design](https://mlsanity.com/paper/1506.01349/) (2015)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendations](https://mlsanity.com/paper/1908.01425/) (2019)
- [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)
- [Ensemble Sampling](https://mlsanity.com/paper/1705.07347/) (2017)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [Scalable Thompson Sampling using Sparse Gaussian Process Models](https://mlsanity.com/paper/2006.05356/) (2020)
- [Sample-Then-Optimize Batch Neural Thompson Sampling](https://mlsanity.com/paper/2210.06850/) (2022)
- [Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning](https://mlsanity.com/paper/2202.04005/) (2022)
- [Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance](https://mlsanity.com/paper/2502.06363/) (2025)
- [Triangulation candidates for Bayesian optimization](https://mlsanity.com/paper/2112.07457/) (2021)
- [The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle](https://mlsanity.com/paper/2111.04295/) (2021)
- [Introduction To Gaussian Process Regression In Bayesian Inverse Problems, With New ResultsOn Experimental Design For Weighted Error Measures](https://mlsanity.com/paper/2302.04518/) (2023)
- [When Combinatorial Thompson Sampling meets Approximation Regret](https://mlsanity.com/paper/2302.11182/) (2023)
- [Voronoi Candidates for Bayesian Optimization](https://mlsanity.com/paper/2402.04922/) (2024)
- [Batched Stochastic Bayesian Optimization via Combinatorial Constraints Design](https://mlsanity.com/paper/1904.08102/) (2019)

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

- [Efficient optimization of expensive black-box simulators via marginal means, with application to neutrino detector design](https://mlsanity.com/paper/2508.01834/) (2025)
- [Bayesian Optimization on Networks](https://mlsanity.com/paper/2510.27643/) (2025)
- [BONSAI: Bayesian Optimization with Natural Simplicity and Interpretability](https://mlsanity.com/paper/2602.07144/) (2026)
- [Optimal Transport-based Permutation-Invariant Bayesian Optimization of Offshore Wind Farm Layouts](https://mlsanity.com/paper/2606.00009/) (2026)
- [Exploration strategies for Gaussian process bandit optimization with inference regret guarantees](https://mlsanity.com/paper/2610.16187/) (2026)

## Abstract (arXiv)

Bayesian optimization (BO) is a widely used iterative algorithm for optimizing black-box functions. Each iteration requires maximizing an acquisition function, such as the upper confidence bound (UCB) or a sample path from the Gaussian process (GP) posterior, as in Thompson sampling (TS). However, finding an exact solution to these maximization problems is often intractable and computationally expensive. Reflecting such realistic situations, in this paper, we delve into the effect of inexact maximizers of the acquisition functions. Defining a measure of inaccuracy in acquisition solutions, we establish cumulative regret bounds for both GP-UCB and GP-TS without requiring exact solutions of acquisition function maximization. Our results show that under appropriate conditions on accumulated inaccuracy, inexact BO algorithms can still achieve sublinear cumulative regret. Motivated by such findings, we provide both theoretical justification and numerical validation for random grid search as an effective and computationally efficient acquisition function solver.