Abstract
Evolution Strategies (ES) are effective black-box optimization algorithms for reinforcement learning (RL), particularly in handling sparse rewards. However, their performance degrades in "noisy" environments where many input features are irrelevant to the task. We introduce NESHT (Natural Evolution Strategies with Hard-Thresholding), a framework that integrates a hard-thresholding operator directly into the evolution strategy. By enforcing sparsity, NESHT effectively filters out distractors and reduces the variance of gradient estimates. We provide a rigorous convergence analysis for non-convex objectives and demonstrate that NESHT achieves superior performance on complex Mujoco and Atari benchmarks compared to vanilla NES and standard gradient-based RL methods.
Introduction
Evolution Strategies (ES) estimate gradients by sampling random perturbations of policy parameters, making them robust to non-differentiable objectives. However, ES operates under the assumption that every input feature is relevant. In real-world scenarios, agents are often bombarded with task-irrelevant data—such as background animations in video games—which increases the variance of the reward function and leads to unstable training. NESHT bridges the gap between sparse learning and evolution strategies to address this challenge.
Methods
NESHT combines Natural Evolution Strategies (NES) with a Hard-Thresholding (HT) operator:
- NES Gradient Estimation: The algorithm estimates the gradient of a smoothed fitness function by observing the effects of random Gaussian perturbations on the reward.
- Hard-Thresholding (HT): After each update, the HT operator retains only the $k$ parameters with the largest absolute magnitudes, setting others to zero. This enforces an $L_0$ constraint.
- Theoretical Convergence: The paper proves that NESHT converges to a stationary point even for non-convex and discontinuous fitness functions, deriving an explicit smoothness constant that relates noise levels and parameter dimensions to training speed.
Experimental Results
Robustness to Noise
The researchers evaluated NESHT on "Noisy Mujoco" tasks and high-dimensional Atari games. In Mujoco tasks with 20x Gaussian noise, NESHT consistently outperformed vanilla NES and classic algorithms like TD3. For instance, on Hopper-v3, NESHT achieved a score of ~1006, while vanilla NES trailed at ~147.
Feature Selection and Sparsity
A key insight is that irrelevant features act as variance multipliers for gradient estimators. Hard-thresholding acts as a proactive filter, allowing the agent to ignore noisy segments of the input.
Atari Performance
On pixel-based Atari games, applying a hard-thresholding ratio (keeping 10-40% of weights) led to faster convergence and higher final scores.
Conclusion
NESHT demonstrates that sparsity must be enforced iteratively during training to reduce gradient variance effectively. While the algorithm introduces a new hyperparameter—the hard-thresholding ratio—it significantly improves robustness in high-noise environments. Future work includes extending this theoretical rigor to deeper architectures and improving sample efficiency for real-world robotics applications.
Summary updated