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

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 realistic scenarios, this paper investigates the effect of using inexact acquisition function maximizers in BO. Defining a measure of inaccuracy in acquisition solutions, we establish cumulative regret bounds for both GPUCB and GP-TS based on imperfect acquisition function maximizers. Our results show that under appropriate conditions on accumulated inaccuracy, BO algorithms with inexact maximizers 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.