TR-BEACON: Shedding Light on Efficient Behavior Discovery in High-Dimensional Spaces with Bayesian Novelty Search over Trust Regions

Authors: wei-ting  tang
ankush  chakrabarty
joel a paulson
Venue: NeurIPS_cc_2024_Workshop_BDU
Published: 2024-09-05 03:48:44

Abstract: Novelty search (NS) algorithms automatically discover diverse system behaviors through simulations or experiments, often treating the system as a black box due to unknown input-output relationships. Previously, we introduced BEACON, a sample-efficient NS algorithm that uses probabilistic surrogate models to select inputs likely to produce novel behaviors. In this paper, we present TR-BEACON, a high-dimensional extension of BEACON that mitigates the curse of dimensionality by constructing local probabilistic models over a trust region whose geometry is adapted as information is gathered. Through numerical experiments, we demonstrate that TR-BEACON significantly outperforms state-of-the-art NS methods on high-dimensional problems, including a challenging robot maze navigation task.

Main paper: 
 introduction: 
 Novelty search (NS) refers to a class of methods that, as opposed to minimizing or maximizing over specific objectives, aim to search for diverse system outcomes [1, 2] . Mathematically, we assume our system outcomes are determined by evaluating a function f : R D → R M that maps a D-dimensional input vector x ∈ R D to a M -dimensional outcome space. The inputs typically represent design parameters that we can tweak in our system and the outcomes correspond to important dimensions of variation. In airplane design, x would represent things like the size and shape of the wing while f (x) represents the collection of all important measurable quantities like the drag coefficient, life, structural integrity, and fuel efficiency. For drug molecules, x could represent different molecular substitution patterns while f (x) represents the size, effectiveness, and stability of the molecules. NS has demonstrated strong potential for solving so-called deceptive optimization problems where it is common for many existing optimization algorithms get stuck in local optima [3, 4, 5] .Assuming we have evaluated f at n > 0 input values, yielding dataset D n = {(x i , f (x i ))} n i=1 , a popular way to measure the "novelty" is the average distance to the k-nearest neighbors as followsEQUATIONwhere {y ⋆ 1 , . . . , y ⋆ k } are the k closest outcomes to f (x) and dist(•) is any valid distance metric in R M . If we had knowledge of f , we could sequentially select inputs that maximize novelty at every iteration, i.e., x n+1 = argmax x∈X ρ(x|D n ) over our design space X ⊂ R D . The key challenge in practice is that f is often a black-box function such that we cannot solve this optimization problem exactly. To overcome this challenge, the vast majority of existing NS methods rely on meta-heuristics, such as evolutionary algorithms, to select new evaluation points, e.g., [1, 6] . These methods can be effective when we have a large evaluation budget (e.g., can evaluate f several thousand or more times); however, for many applications of interest, we have expensive evaluations. For example, in the airplane design problem, evaluating f (x) may require a complex computational fluid dynamic simulation or physical experiment. These problems naturally require a much smaller evaluation budget for which existing NS methods are not designed.Recently, the authors proposed an NS method, called BEACON, specifically designed for expensive black-box functions [7] . BEACON constructs a multi-output Gaussian process surrogate model for f that is combined with a novel acquisition function for trading off exploration and exploitation of the input space, which enables efficient sampling of the search space. However, BEACON relies on a global surrogate model and thus is inherently limited by the curse of dimensionality. Although we previously explored the use of custom priors and kernels to deal with this challenge, these require f to exhibit special structure and are likely to fail when these assumptions do not hold.Motivated by this challenge, we propose a local variant of BEACON for high-dimensional NS (or behavior discovery) problems. Our proposed approach, TR-BEACON, leverages the notion of a trust region (TR) [8] to limit the size of the search space over which we need to build our surrogate model. Trust regions are commonly applied in the optimization literature and have been used within the TuRBO algorithm [9] for high-dimensional Bayesian optimization. A key component of TR-BEACON is the development of a new trust region management system that at every iteration (i) computes a center point based on the most novel data point observed so far and (ii) uses a variancebased measure to decide if the trust region should be enlarged or shrunk. The next section provides a detailed description of TR-BEACON, which is followed by numerical experiments on a synthetic objective and a challenging robot maze navigation problem from the NS literature that demonstrate its strong empirical performance on high-dimensional problems. 
tr-beacon: algorithm description: 
 A complete description of TR-BEACON is given in Algorithm 1. The first key component is the construction of a (local) multi-output Gaussian processes (MOGPs) [10] to model the M -dimensional outcome space. Recall that a GP is a non-parametric model that learns a probabilistic surrogate function from (potentially) noisy data. To build an MOGP, we introduce an additional input variable j ∈ {1, • • • , M } to describe the j th element of the outcome vector [f (x)] j . Given observed data D n , the expressions for the posterior mean and variance of the MOGP can be derived analytically; see Appendix A. The second key component is the choice of the "trust region" (TR). Here, we choose the TR to be a hyperrectangle with center equal to the input that gave the output that is furthest away from its neighbors, denoted by x c n . At the start of the method, we set the base side length of the TR to L ← L init . Following TuRBO, the base side length is rescaled according to the estimated average lengthscale ℓ i for dimension i across the different outputs in the MOGP model such thatL i = ℓ i L/( D j=1 ℓ j ) 1/D .As commonly done in TR methods, if the optimizer "makes progress", the TR will be expanded whereas, if it "fails", the TR will be shrunk. We double and halve the size of the TR after, respectively, τ succ consecutive successes and τ fail consecutive failures. In addition, we do not let the TR length exceed a size L max and reset the length to L init if L falls below a minimum threshold L min . Since the novelty measure (1) changes at every iteration (depends on the full set of collected data), we cannot define a "success" as simply improving upon the best-known value. Instead, we define a "success" as choosing a candidate that increases the total variance of the outcomes and a "failure" as choosing one that does not. The last critical component is the choice of acquisition function inside of the TR for which we use with the same approach as BEACON, i.e.,EQUATIONwhere g ∼ f |D n is a Thompson sample (TS) from the MOGP posterior, ∆ n denotes the TR at the current iteration n, e k is a vector of ones in the first k entries and zeros in the remaining entries, and sort(•) is the standard sort operator that sorts its input in descending order. The formulation can be thought of as a differentiable version of (1) where the true unknown function f is replaced with a TS g. We let D x and D y denote the subset of input and output values in the dataset D, respectively. An illustration of the evolution of TR-BEACON is shown in Fig. 1 for a simple 2-D function. We see Train MOGP surrogate model MOGP n given all available data Dn.Set the trust region center as x c n = xi⋆ where i ⋆ = argmax i=1,...,q j̸ =i dist(y i , y j ).Set trust region lengths as Li ← ℓiL/( D j=1 ℓj) The trust region is below the minimum size; stop the optimization process.end if 24: end for that our proposed approach is able to efficiently explore the space of outcomes (finding many values along the edge of the support of the distribution of outcomes), even though the MOGP model does not accurately capture the novelty metric surface especially in the early iterations. 
numerical experiments: 
 We compare TR-BEACON with several state-of-the-art (SOTA) baseline algorithms on a synthetic and a reinforcement learning (RL) problem. Details for all methods are included in Appendix B. All experiments can be reproduced with the code provided in https://github.com/PaulsonLab/ TR-BEACON.git.For the first case study, we consider a 20-D Ackley synthetic function; see Appendix C for its analytical form. We consider the domain x ∈ [-2, 2] and generate 40 initial samples using the Sobol sequence [11] to train a GP with a standard radial basis function (RBF) kernel. We use reachability as the performance metric, which corresponds to the number of bins visited by the algorithms given a finite number of evaluations (50 equally sized bins are chosen, with each bin effectively representing a behavior we would like to discover). Results are shown in Fig. 2a over 10 replicates of randomly selected initial points (the dark lines represent the mean and the shaded regions correspond to 95% confidence regions). We see that TR-BEACON achieves the highest reachability of all the methods, with BEACON performing second best as the performance drops off due to the difficulty of globally modeling the outcome over a 20-D input space.Next, we examine a challenging RL problem from the OpenAI Gym [12] environment. The task is to move a ball from its starting location to a target location within a given number of time steps (see Appendix D for details). We define the actor policy using a bias-free feed-forward neural network. We want to compute the optimal set of weight parameters that can maximize the reward of successfully getting the ball to the exit. This is known to be a deceptive problem in the sense that the algorithm can often unexpectedly push the system to have the ball get trapped on a wall when directly optimizing the objective (distance to the exit) [13] . NS methods can overcome this challenge by considering the (x, y) coordinates of the landing position as outcomes and biasing the samples toward discovering new outcomes. Fig. 2b shows the mean of the best reward found by all baseline methods across 30 replicates. The percentage of reaching the maximum achievable reward for all baseline methods is shown in Table 1 in Appendix D. TR-BEACON substantially outperforms all considered baselines; it can in fact reach the maximum achievable reward within 300 episodes in all replicates. NS-EA has the second-best performance; however, only reaches ∼ 90% of the best possible reward, with even lower performance in the earlier iterations. Lastly, two SOTA black-box optimizers, mainly TuRBO [9] and LogEI [14] , interestingly exhibit the worst performance out of all tested methods, which is a consequence of the deceptive characteristics of this problem.NS-EA (Novelty Search based on Evolutionary Algorithm) is a vanilla NS algorithm that replaces the objective-oriented fitness function with novelty-based fitness function in the evolutionary algorithm. The fitness function is shown in (7) .EQUATIONwhere {y nn 1 , ..., y nn K } denotes the K-nearest observed outcomes, given an outcome f (x), and dist(•, •) is a distance metric in R n f , e.g., the 2-norm. The code for implementing NS-EA can be found in https://github.com/alaflaquiere/simple-ns.NS-FS (Novelty Search in Feature Space) is a NS-based algorithm proposed by Tang et al. [7] . It is similar to the idea of vanilla NS algorithm, in which we calculate the distance w.r.t. the feature space instead of the outcome space. NS-FS sequentially sample new candidate by maximizing the following acquisition function for each iteration:α NS-FS (x) = k i=1 dist X (x, x ⋆ i ),This acquisition function calculates the sum of distance from x to its k-nearest feature x * i . It is worth noting that NS-FS doesn't require the need to build surrogate model. The acquisition function α NS-FS can be maximized by gradient-based solver such as L-BFGS-B implemented in this work.Random search (RS) is one of the most commonly used baseline algorithm for optimizing black-box functions. It works by sequentially sampling new candidate from a uniformly distributed set of continuous/discrete candidates.Sobol is a sampling algorithm that sequentially sample new point from the quasi-random lowdiscrepancy sequences. Unlike purely random sampling, Sobol sequences are designed to cover the space more uniformly, reducing the occurrence of clusters and gaps. Sobol sequence is a common baseline algorithm implemented in optimization literature due to its straightforward implementation and the guarantee of dense sampling in the limit of an infinite budget.The D dimensional Ackley function can be expressed as follow [17] :f (x) = -a exp   -b 1 D D i=1 x 2 i   -exp 1 D D i=1 cos(cx i ) + a + exp(1),where a = -20, b = 0.2, and c = 2π. This function has a global minimum y * = 0 locating at x * = (0, ..., 0).In Figure 3 , the starting location is represented by the green ball, while the target location is represented by the red ball. This problem involves four state variables (coordinates and velocity in the x and y directions) and two actions (linear force in the x and y directions). The process terminates when the Euclidean distance between the achieved location and the target location is less or equal to We define the control policy as a bias-free single-hidden layer feedforward neural network with 24 weight parameters, structured as 4-4-2. We also include the percentage of reaching reward = 1 for all baseline methods, as shown in Table 1 .Workshop on Bayesian Decision-making and Uncertainty, 38th Conference on Neural Information Processing Systems (NeurIPS 2024). 
 
 Appendix:  



Reviews: review: title: title: TR-BEACON: Shedding Light on Efficient Behavior Discovery in High-Dimensional Spaces with Bayesian Novelty Search over Trust Regions
main_review: main_review: 1. Summary and contributions:

The main contribution of this paper is proposing a high-dimensional extension of BEACON. The authors implement local probabilistic models over trust regions, which effectively addresses the curse of dimensionality, allowing for efficient behavior discovery in complex systems.


2. Strengths and Weaknesses:

The paper is generally well-written and structured clearly. The authors clearly present the motivation of the paper and algorithms which makes me quite easy to read. Besides, experimental results demonstrate that TR-BEACON effectively identifies potential functional deficiencies. While the numerical experiments are convincing, they primarily focus on two specific tasks.  A broader range of applications could strengthen the argument for TR-BEACON's generalizability.
title: title: Review of TR-BEACON
main_review: main_review: Overall, the authors introduce TR-BEACON to extend their previously proposed BEACON to high-dimensional scenarios. The key idea is to leverage the trust region to limit search space size for building the surrogate model. Although trust region has been widely applied in diverse algorithms, the authors have developed a novel trust region management system and made a detailed algorithm description, which makes this work solid.

Strength:
[1] propose a novel trust region-based novelty search algorithm that can adapt to high-dimension scenarios.

[2] The authors give a detailed description of their proposed algorithm and spell out the difference between their early-stage works.

[3] The experimental results are extensive and convincing.

Weakness:

[1] Computation complexity analysis of the mentioned algorithms is lacking.