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.
GERAD & Department of Mathematics and Industrial Engineering, Polytechnique Montr´eal. · GERAD & Department of Management, Universit´e du Qu´ebec `a Trois-Rivi`eres.