# Accelerating Evolutionary Strategy via Rao-Blackwellizing Realization of Uncertain Input

arXiv: https://arxiv.org/abs/2608.02073 · HTML: https://mlsanity.com/paper/2608.02073/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 55 references that are in the map.
- First posted on arXiv 3 Aug 2026.

## Builds on (most cited first, 22 of 22)

- [Evolution Strategies as a Scalable Alternative to Reinforcement Learning](https://mlsanity.com/paper/1703.03864/) (2017)
- [The CMA Evolution Strategy: A Tutorial](https://mlsanity.com/paper/1604.00772/) (2016)
- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [Black Box Variational Inference](https://mlsanity.com/paper/1401.0118/) (2013)
- [Monte Carlo Gradient Estimation in Machine Learning](https://mlsanity.com/paper/1906.10652/) (2019)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [COCO: A Platform for Comparing Continuous Optimizers in a Black-Box Setting](https://mlsanity.com/paper/1603.08785/) (2016)
- [Gradient Estimation Using Stochastic Computation Graphs](https://mlsanity.com/paper/1506.05254/) (2015)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Improving Exploration in Evolution Strategies for Deep Reinforcement Learning via a Population of Novelty-Seeking Agents](https://mlsanity.com/paper/1712.06560/) (2017)
- [Variance Reduction for Policy Gradient with Action-Dependent Factorized Baselines](https://mlsanity.com/paper/1803.07246/) (2018)
- [Variance reduction properties of the reparameterization trick](https://mlsanity.com/paper/1809.10330/) (2018)
- [ES Is More Than Just a Traditional Finite-Difference Approximator](https://mlsanity.com/paper/1712.06568/) (2017)
- [Rao-Blackwellized Stochastic Gradients for Discrete Distributions](https://mlsanity.com/paper/1810.04777/) (2018)
- [Noisy-Input Entropy Search for Efficient Robust Bayesian Optimization](https://mlsanity.com/paper/2002.02820/) (2020)
- [Bayesian optimisation under uncertain inputs](https://mlsanity.com/paper/1902.07908/) (2019)
- [ARSM: Augment-REINFORCE-Swap-Merge Estimator for Gradient Backpropagation Through Categorical Variables](https://mlsanity.com/paper/1905.01413/) (2019)
- [Particle Swarm Metaheuristics for Robust Optimisation with Implementation Uncertainty](https://mlsanity.com/paper/2003.09664/) (2020)
- [A Largest Empty Hypersphere Metaheuristic for Robust Optimisation with Implementation Uncertainty](https://mlsanity.com/paper/1809.02437/) (2018)
- [Ancestral Reinforcement Learning: Unifying Zeroth-Order Optimization and Genetic Algorithms for Reinforcement Learning](https://mlsanity.com/paper/2408.09493/) (2024)
- [Rao-Blackwellised Reparameterisation Gradients](https://mlsanity.com/paper/2506.07687/) (2025)
- [Can a One-Point Feedback Zeroth-order Algorithm Achieve Linear Dimension Dependent Sample Complexity?](https://mlsanity.com/paper/2508.12228/) (2025)

## Abstract (arXiv)

We investigate Optimization under Input Uncertainty (OIU), in which the input to the objective function, rather than the objective function itself, is subject to uncertainty. OIU appears in manufacturing processes with production tolerance, control of physical systems with actuation noise, Mixture of Experts, and Reinforcement Learning (RL). Most of the existing approaches solve OIU by using the value of the objective function but discard the information of the realized input, even though the realized input is observable in various applications. The question here is whether the discarded information of the realized input is useful to accelerate the optimization process. We affirmatively answer this question for Evolutionary Strategy (ES) by theoretically showing that the information of the realized input can reduce the variance of the gradient estimator via Rao-Blackwellization. Using the Rao-Blackwellized gradient estimator, we propose Phenotype-Accelerated Evolutionary Strategy (PAES), which is a refinement of ES for OIU. Numerical experiments show that PAES converges faster than the usual ES from simple continuous optimization problems to RL benchmarks.