(531c) A Bayesian Approach to Novelty Search for Efficient Exploration of Expensive-to-Evaluate Function Landscapes with Unknown Internal Structure

Most optimization algorithms aim to maximize or minimize a known objective. However, in many scientific or engineering discovery settings (e.g., molecular and materials design), the goal is often not to optimize a single property, but to explore a diverse range of candidate structures with unique or out-of-trend behaviors. Novelty Search (NS) offers a compelling approach to this problem by explicitly rewarding diversity in function outcomes rather than objective value [1]. Originally developed for deceptive optimization problems (e.g., certain reinforcement learning tasks like maze navigation) [2, 3], NS has since gained traction in chemistry and materials science, where desirable design targets may be poorly defined or fundamentally unknown [4].

Despite its promise, existing NS algorithms rely on population-based heuristics such as genetic algorithms [5, 6, 7], which are not sample-efficient and become impractical when evaluating expensive black-box functions (e.g., physics-based simulators or wet-lab experiments). To address this challenge, we introduce BEACON, a Bayesian Optimization-inspired novelty search algorithm designed for sample-efficient exploration of expensive design spaces. BEACON models the outcome space using multi-output Gaussian processes (MOGPs) [8] and introduces a novel acquisition function that prioritizes outcome diversity while accounting for uncertainty – enabling it to make informed, high-impact queries in sparse data settings.

We validate BEACON across a range of benchmarks and real-world discovery problems. These include a first-of-its-kind application of NS to metal-organic framework discovery, targeting materials with unique structural and adsorption properties relevant to clean energy technologies. BEACON is also applied to a challenging molecular discovery task defined in terms of 2,133 feature/input dimensions, demonstrating its scalability and performance in high-dimensional design spaces. Across all tasks, BEACON outperforms state-of-the-art NS and optimization baselines in both diversity and sample efficiency. Finally, we benchmark BEACON on a classical maze navigation task, where it achieves higher average reward than traditional NS and Bayesian optimization algorithms. By uniting the exploration power of novelty search with the sample-efficiency of Bayesian methods, BEACON provides a powerful framework for guiding scientific discovery in domains where objectives are unknown, ambiguous, or intentionally open-ended.

References:

[1] Lehman, J., & Stanley, K. O. (2011). Abandoning objectives: Evolution through the search for novelty alone. Evolutionary computation, 19(2), 189-223.

[2] Forrester, A., & Jones, D. (2008, September). Global optimization of deceptive functions with sparse sampling. In 12th AIAA/ISSMO multidisciplinary analysis and optimization conference (p. 5996).

[3] Mason, K., Duggan, J., & Howley, E. (2018). Maze navigation using neural networks evolved with novelty search and differential evolution. In Adaptive and learning agents workshop (at ICML-AAMAS 2018).

[4] Terayama, K., Sumita, M., Tamura, R., Payne, D. T., Chahal, M. K., Ishihara, S., & Tsuda, K. (2020). Pushing property limits in materials discovery via boundless objective-free exploration. Chemical science, 11(23), 5959-5968.

[5] Gomes, J., Mariano, P., & Christensen, A. L. (2015, July). Devising effective novelty search algorithms: A comprehensive empirical study. In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation (pp. 943-950).

[6] Doncieux, S., Laflaquière, A., & Coninx, A. (2019, July). Novelty search: a theoretical perspective. In Proceedings of the Genetic and Evolutionary Computation Conference (pp. 99-106).

[7] Lehman, J., & Stanley, K. O. (2011, July). Evolving a diversity of virtual creatures through novelty search and local competition. In Proceedings of the 13th annual conference on Genetic and evolutionary computation (pp. 211-218).

[8] Liu, H., Cai, J., & Ong, Y. S. (2018). Remarks on multi-output Gaussian process regression. Knowledge-Based Systems, 144, 102-121.