Depth over Fidelity in Fixed-Budget Noisy Evolution Strategies

Noisy evolution strategies under fixed evaluation budgets face a depth–fidelity trade-off: spending evaluations to denoise intra-generation rankings reduces the number of distribution updates the optimizer can execute. We argue for depth over fidelity and propose probabilistic elite membership (PEM), which replaces hard rank-based weights in evolution strategies with conditional expected rank weights that integrate over ranking uncertainty. PEM preserves the conditional mean update while reducing conditional update dispersion—a Rao–Blackwellization of the noisy rank-based step. We instantiate PEM via residual bootstrapping (RB-PEM) with capped per-generation overhead, complemented by an adaptive probe-and-switch mechanism for low-noise regimes. Across the COCO bbob-noisy suite and external tasks including RL policy search and hyperparameter optimization, RB-PEM achieves consistent gains in high-misranking, budget-constrained settings.

Many tasks, from training game-playing robots to tuning AI systems, come down to searching for the best settings by trial and error, where each trial gives only a noisy score and trials are limited. A widely used optimizer called CMA-ES (an evolution strategy) tackles this like a talent competition: it scores a batch of candidates, keeps the apparent winners, and uses them to propose a better batch over many rounds. But noise corrupts the ranking, so a mediocre candidate can win by luck and steer the search astray. The standard fix is to re-score each candidate several times, yet under a fixed budget every extra score is one fewer round of improvement, a tension we call the depth-versus-fidelity trade-off. We argue for depth: running more rounds usually beats chasing cleaner rankings. Our method, RB-PEM, replaces the hard yes-or-no "winner" label with a probability that each candidate truly belongs among the best, and estimates these almost for free by recycling already-seen noise through a statistical technique called bootstrapping. A quick probe reverts to plain CMA-ES when noise is low. The result is more progress from the same fixed budget, lowering the cost of these expensive searches.