Probabilistic elite membership boosts noisy evolution strategies
Researchers replace hard rank weights with conditional expected ranks, achieving consistent gains across benchmarks.
Researchers Sichen Wang and Zhipeng Lu have published a paper accepted at ICML 2026 that tackles a key challenge in noisy evolution strategies: the depth-fidelity trade-off. Under fixed evaluation budgets, spending evaluations to denoise intra-generation rankings reduces the number of distribution updates the optimizer can execute. The authors argue for prioritizing depth (more updates) over fidelity (precise rankings). To that end, they introduce probabilistic elite membership (PEM), which replaces traditional hard rank-based selection weights with conditional expected rank weights that account for ranking uncertainty. This acts as a Rao-Blackwellization of the noisy step, preserving the conditional mean update while reducing conditional update dispersion.
The authors instantiate PEM via residual bootstrapping (RB-PEM), which adds capped per-generation overhead, and complement it with an adaptive probe-and-switch mechanism for low-noise regimes. Across the COCO bbob-noisy suite, as well as external tasks including reinforcement learning policy search and hyperparameter optimization, RB-PEM delivers consistent gains in settings with high misranking rates and tight computational budgets. The work provides both theoretical grounding and practical algorithms that improve sample efficiency without sacrificing update frequency, making it relevant for practitioners using evolution strategies in noisy real-world optimization problems.
- Probabilistic elite membership (PEM) uses conditional expected rank weights instead of hard rank-based weights to reduce update dispersion in noisy evolution strategies.
- RB-PEM (residual bootstrapping) implements PEM with capped overhead, plus an adaptive probe-and-switch mechanism for low-noise regimes.
- Tested on COCO bbob-noisy, RL policy search, and hyperparameter optimization; RB-PEM consistently outperforms baselines under high noise and limited budgets.
Why It Matters
This method improves sample efficiency for noisy black-box optimization, benefiting RL and hyperparameter tuning practitioners with limited compute budgets.