Distribution Matching Evolutionary Algorithms for Rare Event Sampling

A novel discovery is one which is both useful and surprising: a generative model's output is a useful discovery if it has a low probability of being generated (is surprising) and a high reward (is useful). Modern search methods for discovery typically use evolutionary algorithms with local reward maximizing objectives, permitting the search to focus only on high probability samples. Global objectives, i.e. training a model to generate samples from a target distribution over the entire space, are a more robust alternative but typically require optimizing model weights. However, gradient based optimization is expensive and bars using capable closed source models. In this paper, we interpret various evolutionary algorithms as approximate Markov Chain Monte Carlo, an optimization-free method to sample from complex distributions. Practically, this framework allows developing Distribution Matching Evolutionary Algorithms (DME), a class of search methods which sample from a global target distribution without updating weights. Empirically, DME has a higher sample efficiency than existing methods on problems requiring many samples to find a solution.