Technical Summary: BEACON

Problem Formulation

The paper addresses the challenge of Novelty Search (NS) in the context of expensive, noisy, black-box systems common in chemistry, materials science, and molecular design. Unlike traditional optimization, which seeks a single scalar optimum, the goal here is to uncover a diverse set of attainable system behaviors (outcomes) within a limited evaluation budget.

Formally, the problem involves a vector-valued black-box function $f: \mathcal{X} \to \mathcal{O}$, where $\mathcal{X} \subset \mathbb{R}^d$ is the input space and $\mathcal{O} \subset \mathbb{R}^n$ is the outcome (behavior) space. The objective is to maximize reachability, defined as the fraction of distinct behavior regions discovered within a finite partition of the outcome space.

Existing NS methods, often based on meta-heuristics like evolutionary algorithms, are typically sample-inefficient. They struggle in settings where each function evaluation (e.g., a simulation or physical experiment) is costly. Furthermore, standard Bayesian Optimization (BO) is ill-suited because it collapses outcomes into a single utility function, potentially overlooking scientifically valuable intermediate or rare behaviors.

Methodology: BEACON

The authors propose BEACON (Bayesian Exploration Algorithm for outCOme Novelty), a sample-efficient strategy inspired by Bayesian Optimization principles but adapted for novelty search.

Core Components

1. Multi-Output Gaussian Process (MOGP) Surrogate:
   Instead of modeling a scalar objective, BEACON places a probabilistic surrogate model directly on the input-to-outcome map $f$. The framework utilizes Multi-Output GPs to model the full vector-valued function. In most experiments, the authors employ independent-output GP models (fitting one scalar GP per outcome coordinate) to maintain simplicity, though the framework supports correlated outputs and chemistry-aware kernels (e.g., Tanimoto-fragprint) for specific domains.

2. Thompson Sampling-Based Acquisition Function:
   BEACON introduces a novel acquisition function that scores candidate inputs based on the distance of their plausible outcomes from a denoised archive of previously observed outcomes.

   • Denoising: Raw observations are replaced with posterior mean predictions ($\mu_D$) to mitigate the effects of observation noise.
   • Uncertainty Quantification: The algorithm draws a sample function $g(x)$ from the MOGP posterior (using Thompson sampling).
   • Scoring: The novelty score $\alpha_{NS}$ for a candidate $x$ is the average distance between the sampled outcome $g(x)$ and the $k$ nearest neighbors in the denoised archive:
     $$\alpha_{NS}(x | g, D) = \frac{1}{k} \sum_{i=1}^{k} \text{dist}(g(x), \mu_D(x_i^*))$$
   • Optimization: This acquisition function is optimized using gradient-based methods (e.g., L-BFGS-B) with multiple restarts. The use of differentiable relaxations for the sorting operation in the $k$-nearest-neighbor calculation allows for efficient gradient-based maximization.

3. Extensions:

   • High-Dimensional Scaling: For high-dimensional input spaces, BEACON integrates SAAS (Sparse Axis-Aligned Subspace) priors to induce sparsity in the GP length scales, or utilizes chemistry-aware surrogates (e.g., molecular kernels) for structured discrete inputs.
   • User-Guided Constraints (UG-BEACON): The framework allows users to define partitions of the outcome space to either exclude already explored regions or focus search efforts on specific regimes of interest.

Key Contributions

The paper outlines four primary contributions:

1. Algorithm Development: Introduction of BEACON, a new NS algorithm designed specifically for noisy, expensive black-box systems that improves behavior-space reachability with limited evaluations.
2. Novel Acquisition Strategy: A Thompson sampling-based acquisition function that operates in continuous outcome space. It accounts for predictive uncertainty and observational noise without requiring direct optimization over a fixed, discretized behavior partition.
3. Scalability: Extensions to high-dimensional settings via sparsity-inducing priors and domain-specific surrogate modeling (e.g., for molecular graphs).
4. Empirical Validation: Demonstration of the algorithm's efficacy across synthetic benchmarks, materials discovery (Metal-Organic Frameworks), molecular property discovery, and reinforcement learning tasks.

Results

The authors evaluated BEACON against several baselines, including evolutionary novelty search (NS-EA), distance-to-explored-area search (NS-DEA), maximum variance sampling, and random search.

• Synthetic Benchmarks: On Ackley, Rosenbrock, and Styblinski-Tang functions, BEACON consistently achieved the highest reachability, particularly in higher-dimensional input spaces (up to 12 dimensions). It also outperformed baselines on a synthetic multi-output problem with a long-tailed distribution, effectively covering low-density tail regions that other methods missed.
• Materials Discovery: In tasks involving Hydrogen uptake, Nitrogen uptake, and joint CO2/CH4 uptake in Metal-Organic Frameworks (MOFs), BEACON achieved full coverage of the discretized behavior space within the evaluation budget, outperforming applicable baselines.
• Molecular Discovery: For water solubility, ESOL (aqueous solubility with 2,133-dimensional inputs), and LogD tasks, BEACON demonstrated superior coverage. The use of task-specific kernels (Tanimoto-fragprint) and SAAS priors was critical for performance in high-dimensional molecular spaces.
• Deceptive Landscapes: In a reinforcement learning maze navigation task with a deceptive reward landscape, BEACON was the only method to consistently solve the task across all replicates, whereas reward-driven methods (like Expected Improvement) and other novelty baselines failed to escape local traps.
• User-Guided Discovery: In constrained tasks (MNIST digit discovery and oil sorbent material design), UG-BEACON successfully incorporated user preferences to discover target behaviors faster than unconstrained versions.

Significance and Claims

The paper claims that BEACON makes novelty-driven exploration practical for domains where traditional evolutionary approaches are too sample-inefficient. By leveraging Bayesian surrogate modeling, BEACON can direct evaluations toward unexplored regions of outcome space while rigorously accounting for model uncertainty and noise.

The authors position BEACON as a tool for low-data discovery settings, where the scientific goal is broad coverage of attainable properties rather than a single optimum. They suggest that this approach is particularly valuable for autonomous experimentation workflows in chemistry and materials science, where uncovering previously unseen phenomena is as critical as optimizing known targets.

The paper acknowledges limitations regarding "sharp" outcome spaces (e.g., phase changes) where the surrogate model might over-smooth abrupt jumps, noting that discovery in such cases may still rely on broad exploration or chance sampling if no learnable structure exists. However, they argue that the framework is flexible enough to incorporate hybrid strategies (e.g., space-filling initialization) to mitigate these issues.