Many real-world tasks require optimizing expensive black-box functions accessible only through noisy evaluations, a setting commonly addressed with Bayesian optimization. While Gaussian processes(GPs) and Bayesian neural networks have driven significant progress, GP-based methods scale cubically with observations, and BNN-based approaches remain burdened by expensive posterior sampling such as Hamiltonian Monte Carlo, and inner-loop acquisition optimization in high-dimensional setting. In this work, we propose VBO-MI, a fully gradient-based BO framework that requires no assumptions on a Gaussian prior or a variational posterior family over f. While our framework uses gradient-based updates to train the internal action and information-estimation networks, it treats the objective function f as a strict black box, requiring only zeroth-order evaluations. To enable end-to-end gradient flow, we employ an actor-critic architecture consisting of an action-net to navigate the input space and a variational critic to estimate a surrogate information signal for exploration. Additionally, we design a lightweight surrogate that approximates the objective from observed data using a replay buffer, which reduces the total required real function queries to one batch per iteration. We provide theoretical analysis for our framework, establishing convergence of its training objective and surrogate estimator, and showing, that near-optimal solutions exist. We evaluate our method on a diverse suite of benchmarks, including high-dimensional synthetic function and complex real-world tasks such as Rover Trajectory planning optimization, the Lunar Lander, and Pest Control problems. Our experiments demonstrate that VBO-MI provides the same or superior optimization performance over the various baselines.
Figures & tables
Figure 1: VBO-MI framework. An action-net Eϕ maps random seeds st to candidate inputs xt(i) . A surrogate f^ψ predicts rewards y^t(i) , enabling oracle-free updates of the helper Dθ ( Ka steps) and action-net ( Kb steps) via the acquisition loss LEϕ , which balances exploitation (surrogate mean) and exploration (variational MI estimate Iθ ). One real oracle query per iteration yields yt(i) , which replenishes the replay buffer H used to retrain f^ψ via MSE ( Ks steps) (real queries happen after internal model updates) . Dashed arrows indicate gradient flows.
Figure 2: Performance comparison on synthetic benchmark tasks (a–c). Global optimum is 0 for all functions. All curves show mean ± one standard deviation over 5 trials.
Figure 3: Performance comparison on real-world benchmark tasks (a–c). All curves show mean ± one standard deviation over 5 trials.
Figure 4: Ablation I: surrogate network contribution. Surrogate-assisted VBO-MI vs. the original variant that queries f directly inside the Ka and Kb loops. Mean ± 1 std over three trials.
Figure 5: Ablation II: acquisition function term contribution. Full VBO-MI vs. two hybrid variants: one replaces the exploration term with the GP posterior variance ( σGP2 ), and one replaces the exploitation term with the GP posterior mean ( μGP ). Mean ± 1 std over three trials.
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 6: Theoretical computational complexity comparison measured in Floating-Point Operations (FLOPs) per iteration
Table 1: Baseline architecture and inference hyperparameters.
Task
d
B
W
Warm-up queries
Main iters. T
Total queries
Ackley
10
60
30
1,800
70
6,000
Levy
20
60
30
1,800
70
6,000
Griewank
20
60
30
1,800
70
6,000
Lunar Lander
12
30
30
900
70
3,000
Pest Control
25
30
30
900
36
2,000 †
Rover Trajectory
60
30
30
900
70
3,000
Appendix
Table 2: VBO-MI per-task experimental configuration. Warm-up queries and total queries are both oracle evaluations of f ; training mini-batch size equals the oracle batch size B throughout.
Method
Surrogate Update
Acquisition Opt.
Real f /iter
Scaling
GP (Exact)
O(T3)
N⋅O(T2)
B
Cubic
HMC-BNN
O(S⋅L⋅T⋅W)
N⋅O(S⋅W)
B
High Linear
DKL
O(T⋅W+T3)
N⋅O(T2+W)
B
Cubic
LLA
O(T⋅W+W3)
N⋅O(W2)
B
Linear
VBO-MI (ours)
O(Ks⋅B⋅Ws+Ka⋅B⋅H)
O(Kb⋅(B⋅Ws+We))
B
Constant
Appendix
Table 3: Comparison of FLOP and oracle-call complexity per BO iteration. T : observations, W : BNN weights, Ws : surrogate weights, H : LSTM hidden dim, S : HMC samples, L : leapfrog steps, Ka,b,s : update steps. We assume W>H and S,L>Ka,b .
Parameter
Value
Description
W
10,000
BNN parameter count (weights + biases)
Ws
≈500
Surrogate network parameter count (3-layer MLP)
We
≈400
Action-net parameter count (3-layer MLP)
D
10
Input dimensionality of the objective function
H
64
Hidden state dimension of the Helper LSTM
S
50
Number of HMC posterior samples
Appendix
Table 4: Parameters used for the FLOP complexity analysis in Section D .
Method
Ackley ( d=10 )
Rover Trajectory ( d=60 )
GP
32.68±1.22
109.49±2.72
I-BNN
20.69±0.92
0.819±0.08
Laplace
34.11±1.18
18.85±0.95
HMC
202.2±6.21
197.40±5.67
SGHMC
37.74±2.16
43.24±2.94
Sparse GP (Focal)
157.80±4.31
48.98±1.55
Appendix
Table 5: Average wall-clock time (per second) for each iteration on for each method on the synthetic (Ackley), and Real-world (Rover Trajectory), benchmarks, with total of 100 iteration.
Figure 7: Comparison of VBO-MI with two additional synthetic functions
Figure 8: Effect of observation noise on VBO-MI. Solid lines: surrogate-assisted variant. Dashed lines: original variant (direct oracle queries in Ka , Kb loops).
Figure 9: Comparison of VBO-MI with and without surrogate modeling for different numbers of warm-up steps. The surrogate-based version consistently outperforms the non-surrogate counterpart. Increasing the warm-up steps improves performance up to approximately 40 steps, while further increases provide marginal gains.
Figure 10: Batch size sensitivity of VBO-MI and baselines on four real-world tasks. Final reward improves with batch size up to a threshold, after which gains diminish.
Figure 11: Sensitivity to exploration parameter β across four real-world tasks. VBO-MI is less sensitive to β than GP-based baselines, maintaining high reward across β∈[10,200] .
Figure 12: Extended acquisition term ablation on four additional real-world tasks (cf. Section 5.3 for results on Ackley and Rover). VBO-MI w/ GP exploration : the exploration term βIθ is replaced by βσGP2 . VBO-MI w/ GP exploitation : the exploitation term f^ψ is replaced by μGP . Full VBO-MI outperforms both hybrids on all four tasks.
Bayesian optimization (BO) of expensive black-box functions is traditionally addressed with Gaussian processes (GPs), which scale cubically with observations, or Bayesian neural networks (BNNs), which incur costly posterior sampling and inner-loop acquisition optimization. We propose VBO-MI (Variational Bayesian Optimization with Mutual Information), a fully gradient-based BO framework that requires no explicit GP prior or fixed parametric posterior family over objective function and treats it as a strict black box. An actor-critic architecture pairs an action-net with a variational critic that estimates information gain, eliminating the acquisition optimization bottleneck and achieving up to 102× fewer FLOPs than BNN-BO baselines. A lightweight surrogate network further reduces real function queries to one batch per iteration. We establish consistency guarantees and evaluate VBO-MI on synthetic benchmarks (Ackley, Levy, Griewank) and real-world tasks (Rover Trajectory, Lunar Lander, Pest Control), demonstrating competitive or superior performance over the baselines.
Bayesian optimization (BO) is a powerful paradigm for optimizing expensive black-box functions. Traditional BO methods typically rely on separate hand-crafted acquisition functions and surrogate models for the underlying function, and often operate in a myopic manner. In this paper, we propose a novel direct regret optimization approach that jointly learns the optimal model and non-myopic acquisition by distilling from a set of candidate models and acquisitions, and explicitly targets minimizing the multi-step regret. Our framework leverages an ensemble of Gaussian Processes (GPs) with varying hyperparameters to generate simulated BO trajectories, each guided by an acquisition function drawn from a pool of conventional choices and terminated by a Bayesian early stop criterion. These trajectories train an end-to-end Decision Transformer that selects the next query so as to improve the ultimate objective, following a dense training sparse learning paradigm: the transformer is trained on abundant simulated data, while a limited number of real evaluations refine the GPs online. On synthetic and real-world benchmarks, our method attains the best or near-best final simple regret against standard, lookahead, trust-region and amortized BO baselines, with the largest gains in high-dimensional settings. Ablations attribute the gains jointly to region-of-interest filtering and the learned policy, and matched-budget comparisons against explicit two-step lookahead acquisitions show that the advantage is not shared by lookahead alone.
Fengxue Zhang, Yuxin Chen
Department of Computer Science University of Chicago Chicago, IL 60637
TREGO, a trust-region Bayesian optimization (BO) method for expensive blackbox problems, has convergence guarantees, but only for exact function values. In high dimension, its performance tends to deteriorate. This paper asks whether a trust-region BO method can be extended to handle noisy evaluations while being competitive in high dimension. We first generalize TREGO into a trust-region framework for noisy BO and extend its convergence analysis to noisy function estimates that are sufficiently accurate with sufficiently high probability. We then propose STREGO, a scalable implementation of this framework. Its global phase selects a batch of candidates by solving a bi-objective problem on the posterior mean of a Gaussian process and the integrated variance reduction. Unlike the predictive variance, this second objective does not favor boundary points merely because they are far from the data. Its local phase minimizes the posterior mean of a second Gaussian process, trained only on points close to the incumbent. STREGO is compared with TREGO, TURBO, BAXUS and NSMA-BO on synthetic and real-world problems of dimension 4 to 124, with and without noise. It gives the best average results in every synthetic setting tested and the best or tied-best solution on four of the six real-world problems. An implementation of STREGO is available at https://github.com/Mayousk/STREGO.
Youssef Diouane, Issmail El Hallaoui, Meisseme Kadri +1
GERAD & Department of Mathematics and Industrial Engineering, Polytechnique Montr´eal. · GERAD & Department of Management, Universit´e du Qu´ebec `a Trois-Rivi`eres.