Abstract
Evolution Strategies (ES) are a class of black-box optimization algorithms widely applied to problems where true gradients are unavailable, such as reinforcement learning (RL). ES estimate gradients by randomly sampling search directions and evaluating parameter perturbations. However, these estimators often suffer from high variance in high-dimensional spaces, necessitating large sample sizes and reducing efficiency. We propose Self-Guided Evolution Strategies (SGES), which utilizes historical estimated gradients to construct a low-dimensional subspace for sampling. By adaptively adjusting the importance of this subspace, SGES significantly reduces variance while maintaining bounded bias. Empirical evaluations on benchmark functions and RL tasks demonstrate that SGES outperforms state-of-the-art ES algorithms in both speed and accuracy.
Introduction
Evolution Strategies (ES) have emerged as a robust alternative to gradient-based methods in scenarios where the objective function is non-differentiable or the gradient is difficult to compute. Despite their success in Reinforcement Learning (RL), ES face the "curse of dimensionality." In high-dimensional parameter spaces, random search directions are likely to be uninformative, leading to high variance in gradient estimation. While methods like CMA-ES or ASEBO attempt to model the search space geometry, they often incur significant computational overhead, such as $O(n^2)$ or $O(n^3)$ complexity for $n$ parameters, making them impractical for large-scale neural networks.
The SGES Framework
SGES addresses the efficiency bottleneck by leveraging the history of recent gradient estimates to guide future searches. The algorithm is built on four key pillars:
- Gradient Subspace Construction: Instead of exploring the full $n$-dimensional space, SGES maintains an archive of the $k$ most recent estimated gradients. A low-dimensional "gradient subspace" is defined by performing a decomposition on this $n \times k$ matrix. Since $k \ll n$, this process is computationally efficient.
- Hybrid Sampling: Search directions are sampled from two distinct components: the low-dimensional gradient subspace (exploitation) and its orthogonal complement (exploration).
- Adaptive Tradeoff: A dynamic parameter, $\alpha$, balances the weight between subspace sampling and full-space exploration. If directions within the subspace yield better improvements, $\alpha$ is increased to prioritize exploitation.
- Theoretical Guarantees: The authors provide mathematical proof that this structured sampling significantly reduces the variance of the gradient estimator compared to Vanilla ES, while ensuring that the bias remains within acceptable bounds.
Experimental Evaluation
SGES was evaluated against several baselines, including Vanilla ES, Guided ES, and ASEBO, across two primary domains: high-dimensional benchmarks and reinforcement learning tasks.
High-Dimensional Benchmarks
Using the Nevergrad benchmark suite, the algorithms were tested on functions like Sphere, Rosenbrock, Rastrigin, and Lunacek, scaled to 1,000 dimensions. SGES consistently demonstrated faster convergence and lower final loss values across these diverse landscapes.
Reinforcement Learning Tasks
The performance was further validated on MuJoCo locomotion tasks (e.g., HalfCheetah-v2, Humanoid-v2). On the challenging Humanoid-v2 task, SGES achieved a median return of 4023, significantly outperforming Vanilla ES (3867) and Guided ES (1765).
Key Insights and Results
- Computational Efficiency: By focusing on a low-rank $n \times k$ matrix, SGES maintains a runtime nearly as fast as Vanilla ES, whereas methods like ASEBO can be up to 100 times slower on the same tasks.
- Robustness: SGES exhibits lower variance across different random seeds, providing more reliable performance on single runs compared to previous methods which were often inconsistent.
- Exploration vs. Exploitation: The adaptive $\alpha$ mechanism is crucial. In tasks like HalfCheetah, the algorithm maintains a level of exploration outside the gradient subspace to avoid sub-optimal local behaviors like swaying or flipping.
Conclusion
SGES represents a significant step forward in making Evolution Strategies practical for high-dimensional optimization. By using historical data to intelligently constrain the search space, it achieves superior performance without the computational burden of traditional covariance-matrix adaptation methods. While highly effective, future work may address the sensitivity to the history length $k$ and explore non-linear manifold assumptions for the search subspace.
Summary updated