Non-Replacement Function Space Sampling for Bayesian Optimization

Bayesian optimization (BO) is a probabilistic framework for optimizing expensive black-box functions through sequential decision making guided by an acquisition function. Existing acquisition strategies explicitly balance exploration and exploitation, often requiring carefully designed heuristics or hyper-parameter tuning. We introduce Non-Replacement Function Space Sampling (NRFS), achieving desired exploration-exploitation balance by prioritizing the functions that have not contributed to previous acquisition decisions, rather than relying on explicit tuning. By establishing a correspondence between each candidate and the set of functions that consider it as the corresponding optimizer, NRFS induces a principled and efficient search strategy in the design space. Empirical evaluations on a diverse set of benchmark problems demonstrate that NRFS outperforms state-of-the-art BO methods, particularly in challenging regimes that demand both global exploration and local refinement. Moreover, we provide theoretical guarantees that NRFS converges for any Lipschitz-continuous objective function, regardless of the complexity of its landscape.