Depth over Fidelity in Fixed-Budget Noisy Evolution Strategies
For practitioners using evolution strategies with noisy evaluations and limited budgets, this work offers a principled method to improve optimization efficiency.
The paper tackles the depth-fidelity trade-off in noisy evolution strategies under fixed evaluation budgets, proposing probabilistic elite membership (PEM) to prioritize depth over fidelity. RB-PEM achieves consistent gains in high-misranking, budget-constrained settings across COCO bbob-noisy, RL policy search, and hyperparameter optimization.
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.