How Many Initial Points Does Bayesian Optimization Need?

Bayesian Optimization (BO) generally begins with an initialization phase: a batch of n0 uninformed evaluations. The choice of n0 remains largely heuristic, and we empirically observe that the total cost (random initial points plus BO iterations needed to find the global optimum) is U-shaped in n0, i.e., a practitioner wastes resources by selecting either too low or too high a value of n0. We find this tradeoff persists across MLE, Bayesian MCMC, and exact GP hyperparameters, as well as across acquisition functions. Toward the latter, Thompson Sampling appears an exception, with both total cost and simple regret essentially n0-agnostic, though higher in our experiments. We attribute this U-shape to the known boundary issue of variance-driven BO: BO burns early budget on corners of the hypercube before turning inward. We demonstrate this effect using a 3D BO trajectory where the exact hyperparameters are known. We conclude with practical recommendations: use multi-step lookahead BO where possible; otherwise use Thompson Sampling when n0 cannot be tuned, and a generously large n0 when it can.