🤖 machine learning

Exploring Exploration in Bayesian Optimization

This paper introduces two novel quantitative measures, observation traveling salesman distance and observation entropy, to analyze and compare the exploration characteristics of Bayesian optimization acquisition functions, thereby revealing links between exploration and performance while providing a foundation for their principled design.

Original authors: Leonard Papenmeier, Nuojin Cheng, Stephen Becker, Luigi Nardi

Published 2026-05-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Leonard Papenmeier, Nuojin Cheng, Stephen Becker, Luigi Nardi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the highest peak in a vast, foggy mountain range, but you can't see the whole landscape at once. You can only stand at one spot, measure the height, and then decide where to walk next. This is the essence of Bayesian Optimization: a smart way to find the best solution to a complex problem without testing every single possibility.

To make good decisions, your "guide" (called an Acquisition Function) needs to balance two conflicting desires:

Exploitation: Walking toward the highest spot you've already seen, hoping the peak is just a little higher nearby.
Exploration: Venturing into the unknown, foggy areas to see if there's an even taller mountain you haven't discovered yet.

The problem is, we didn't have a good ruler to measure how much a guide was exploring. We knew some guides were "adventurous" and others were "cautious," but we couldn't quantify it.

This paper introduces two new "rulers" to measure exactly how adventurous an algorithm is.

The Two New Rulers

The authors propose two creative ways to measure exploration based on the trail of footprints (observations) the algorithm leaves behind:

1. The "Tour Guide" Distance (Observation Traveling Salesman Distance)
Imagine the algorithm has visited several spots on the mountain. To measure how far it has wandered, we ask: "If a tour guide had to walk from the starting point, visit every single spot the algorithm checked, and return home, what is the shortest path they could take?"

High Distance: The guide had to walk all over the map, zig-zagging between distant peaks and valleys. This means the algorithm was highly explorative.
Low Distance: The guide just walked in a tight circle around one spot. This means the algorithm was stuck in one area (exploitative).

2. The "Crowded Room" Measure (Observation Entropy)
Imagine the spots the algorithm visited are people standing in a room.

High Entropy: The people are spread out evenly across the entire room. No one is clumped together. This means the algorithm is exploring the whole space.
Low Entropy: Everyone is huddled in a single corner. This means the algorithm is ignoring most of the room.

What They Discovered

Using these two rulers, the authors tested many different "guides" (algorithms) on both simple computer puzzles and complex real-world problems (like tuning robot movements or optimizing DNA models). Here is what they found:

The "Goldilocks" Zone: The best-performing algorithms weren't the ones that explored the most, nor the ones that explored the least. They were the ones that found a balanced middle ground.
The Over-Explorers: Some algorithms, like Thompson Sampling, were so adventurous that they acted like a tourist who refuses to look at the map and just runs randomly in circles. While they covered a lot of ground, they often failed to find the actual highest peak because they wasted too much time wandering.
The Under-Explorers: Other algorithms were too cautious, sticking to the first high spot they found and never checking if a better one existed nearby.
The "Batch" Effect: When the algorithm is allowed to check multiple spots at once (like sending a team of hikers instead of one), it naturally becomes more adventurous and covers more ground.
The "Trust Region" Effect: When the algorithm is told to stay within a specific small area (a "trust region"), it becomes much less adventurous and focuses intensely on that small patch.

The New Map (Taxonomy)

The paper creates a new "map" or ranking system for these algorithms. Before, people had a vague idea of which algorithms were adventurous and which were cautious. Now, they have a precise, data-backed ranking.

For example, they confirmed that Expected Improvement is generally a balanced guide, while Probability of Improvement is very cautious. They also found that Knowledge Gradient is slightly more adventurous than Max-Value Entropy Search, a detail that was previously unclear.

Why This Matters (According to the Paper)

The authors argue that having these precise rulers allows us to:

Diagnose Problems: If an algorithm is performing poorly, we can check its "ruler" score. If it's too high, we know it's wandering too much. If it's too low, we know it's stuck.
Design Better Guides: Instead of guessing how to tweak an algorithm, we can use these measures to build new guides that hit the perfect balance of adventure and caution.
Know When to Stop: If an algorithm's exploration score suddenly spikes (like it's running randomly again), it might be a sign that it has already checked all the good spots and should stop.

In short, this paper gives us the tools to stop guessing whether an optimization algorithm is being too bold or too shy, and instead measure it with a ruler, allowing us to tune it for better results.

Technical Summary: Exploring Exploration in Bayesian Optimization

Problem Statement

Bayesian Optimization (BO) is a standard method for maximizing black-box functions by sequentially constructing probabilistic surrogates (typically Gaussian Processes) and selecting new sampling points via an acquisition function (AF). A critical component of any successful BO algorithm is the acquisition function's ability to balance exploration (searching unexplored regions to discover global optima) and exploitation (refining the search in promising regions).

While the BO community widely acknowledges that different AFs exhibit varying degrees of explorative preference, there is a significant lack of quantitative measures to define and compare these characteristics. Existing metrics, such as Total Center Distance (TCD) or incumbent distance, suffer from notable shortcomings: they may fail when the initial sample hits the optimum, do not capture oscillatory behavior, or conflate distance from a specific point with genuine exploration. Furthermore, comparing AFs from different families (e.g., Upper Confidence Bound vs. Information-Theoretic methods) is challenging without a universal metric. This gap hinders the systematic analysis, design, and selection of AFs for specific real-world problems.

Methodology

To address the lack of quantitative exploration metrics, the authors propose two novel approaches based on the spatial distribution of observations selected during the optimization process:

1. Observation Traveling Salesman Distance (OTSD)

OTSD quantifies exploration by calculating the minimum Euclidean distance required to connect all observation points in the search space, formulated as a Traveling Salesman Problem (TSP).

Definition: Given a set of $t$ observation points $X_t$ , OTSD is the total length of the shortest route visiting each point exactly once and returning to the start.
Normalization: Since raw OTSD increases monotonically with the number of observations and depends on dimensionality, the authors introduce a Normalized OTSD. This is derived by dividing the raw OTSD by a theoretical upper bound $\Psi(d, t)$ , which depends on the dimension $d$ and the number of points $t$ . This normalization allows for comparison across different problem dimensions and iteration counts.
Computation: Due to the NP-hard nature of TSP, the authors employ an insertion heuristic algorithm with $O(dT^2)$ complexity, which guarantees a tour length at most twice the optimal.

2. Observation Entropy (OE)

OE quantifies exploration by measuring the uniformity of the data distribution of the observations using information theory.

Definition: OE treats observation points as samples from a random variable and estimates the empirical differential entropy. Higher entropy values indicate a more uniform spread of points, reflecting greater exploration.
Estimation: The authors utilize the non-parametric Kozachenko-Leonenko (KL) estimator, which is based on nearest-neighbor distances. This method is chosen for its sample efficiency and applicability in moderate-dimensional spaces ( $d \le 50$ ).
Properties: Unlike OTSD, OE is non-monotonic and can take positive or negative values. An increasing OE over iterations suggests the AF is becoming more explorative, while a decrease suggests a shift toward exploitation.

Key Contributions

Novel Quantification Metrics: The introduction of OTSD and OE as the first dedicated, quantitative measures to characterize the exploration behavior of acquisition functions based on their selected observations.
Empirical Taxonomy: The creation of the first empirical taxonomy of acquisition function exploration. By applying OTSD and OE across diverse benchmarks, the authors establish a partial ordering of AFs (e.g., Random Search $\succeq$ UCB (high $\beta$ ) $\succeq$ Information Theoretic $\approx$ KG $\succeq$ EI $\succeq$ PI $\succeq$ UCB (low $\beta$ ) $\succ$ Deterministic Selection).
Comprehensive Evaluation: Extensive experiments on synthetic and real-world benchmarks (ranging from low-dimensional to high-dimensional, $d=2$ to $d=180$ ) and various AF variants (including batched evaluations, Trust Regions, and RAASP sampling).
Theoretical Bounds: The derivation of theoretical upper and lower bounds for the true OTSD and OE values, providing a statistical foundation for the proposed estimators.

Results

The experiments validate the effectiveness of OTSD and OE in capturing exploration behaviors:

Consistency: OTSD and OE strongly correlate across benchmark problems, cross-validating their reliability. Both metrics successfully distinguish between known explorative (e.g., Random Search, UCB with high $\beta$ ) and exploitative (e.g., PI, Deterministic Selection) strategies.
Dimensionality Effects: The study reveals that dimensionality significantly impacts exploration behavior. For instance, Thompson Sampling (TS) is moderately explorative in low dimensions but becomes overly explorative in high dimensions, often surpassing Random Search in OTSD. Conversely, Expected Improvement (EI) is more explorative than UCB in low dimensions but becomes less so in high dimensions.
Impact of Techniques:
- Batching: Increases exploration (higher OTSD/OE) as larger batch sizes force the selection of diverse points.
- Trust Regions (TRs) and RAASP: Consistently reduce exploration, leading to more exploitative behavior.
Performance Correlation: The results suggest that the best-performing methods generally do not exhibit extreme exploration quantities. Instead, they maintain a balanced Exploration-Exploitation Trade-Off (EETO). Overly explorative methods (like TS in high dimensions) or overly exploitative methods often yield suboptimal optimization performance.

Significance and Claims

The paper claims that these new measures provide a foundation for guiding the design of acquisition functions in a more principled and systematic manner. By quantifying exploration, practitioners can:

Diagnose AF Behavior: Identify if an AF is too explorative (e.g., TS in high dimensions) or too exploitative for a specific problem, potentially serving as a warning sign.
Construct Portfolios: Select appropriate AFs or combinations (e.g., adding RAASP to a highly explorative AF) based on the required level of exploration.
Early Stopping: Detect when an AF has exhausted local minima (indicated by a shift in OTSD/OE trends), suggesting the optimization process may be ready to terminate.

The authors emphasize that while their results are empirically robust, they are limited to continuous domains and do not currently account for the specific effects of GP hyperparameters. Future work aims to extend these taxonomies to non-Euclidean domains and investigate the influence of kernel and likelihood hyperparameters.