# Structured Evolution with Compact Architectures for Scalable Policy Optimization

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

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Apr 2018.

## Built on by (most cited first, 30 of 48)

- [EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning](https://mlsanity.com/paper/2108.08842/) (2021)
- [On the Expressive Power of Self-Attention Matrices](https://mlsanity.com/paper/2106.03764/) (2021)
- [MLGO: a Machine Learning Guided Compiler Optimizations Framework](https://mlsanity.com/paper/2101.04808/) (2021)
- [Evolutionary Reinforcement Learning: A Survey](https://mlsanity.com/paper/2303.04150/) (2023)
- [Deep Reinforcement Learning Versus Evolution Strategies: A Comparative Survey](https://mlsanity.com/paper/2110.01411/) (2021)
- [DPZero: Private Fine-Tuning of Language Models without Backpropagation](https://mlsanity.com/paper/2310.09639/) (2023)
- [On the Convergence of Prior-Guided Zeroth-Order Optimization Algorithms](https://mlsanity.com/paper/2107.10110/) (2021)
- [Combining Evolution and Deep Reinforcement Learning for Policy Search: a Survey](https://mlsanity.com/paper/2203.14009/) (2022)
- [Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2301.06428/) (2023)
- [Derivative-Free Reinforcement Learning: A Review](https://mlsanity.com/paper/2102.05710/) (2021)
- [TTOpt: A Maximum Volume Quantized Tensor Train-based Optimization and its Application to Reinforcement Learning](https://mlsanity.com/paper/2205.00293/) (2022)
- [Generalizing Gaussian Smoothing for Random Search](https://mlsanity.com/paper/2211.14721/) (2022)
- [Robotic Table Tennis: A Case Study into a High Speed Learning System](https://mlsanity.com/paper/2309.03315/) (2023)
- [Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations](https://mlsanity.com/paper/2510.19975/) (2025)
- [Stochastic Zeroth order Descent with Structured Directions](https://mlsanity.com/paper/2206.05124/) (2022)
- [A Scalable Gradient-Free Method for Bayesian Experimental Design with Implicit Models](https://mlsanity.com/paper/2103.08026/) (2021)
- [Curvature-Aware Derivative-Free Optimization](https://mlsanity.com/paper/2109.13391/) (2021)
- [Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradients](https://mlsanity.com/paper/2210.01496/) (2022)
- [Repelling Random Walks](https://mlsanity.com/paper/2310.04854/) (2023)
- [Variance-Reduced Gradient Estimation via Noise-Reuse in Online Evolution Strategies](https://mlsanity.com/paper/2304.12180/) (2023)
- [Magellan: Autonomous Discovery of Novel Compiler Optimization Heuristics with AlphaEvolve](https://mlsanity.com/paper/2601.21096/) (2026)
- [Evolutionary Policy Optimization](https://mlsanity.com/paper/2503.19037/) (2025)
- [Dimensionality Reduction and Prioritized Exploration for Policy Search](https://mlsanity.com/paper/2203.04791/) (2022)
- [Multitask Neuroevolution for Reinforcement Learning with Long and Short Episodes](https://mlsanity.com/paper/2203.10844/) (2022)
- [Implicit Two-Tower Policies](https://mlsanity.com/paper/2208.01191/) (2022)
- [Towards A Unified Policy Abstraction Theory and Representation Learning Approach in Markov Decision Processes](https://mlsanity.com/paper/2209.07696/) (2022)
- [AutoQD: Automatic Discovery of Diverse Behaviors with Quality-Diversity Optimization](https://mlsanity.com/paper/2506.05634/) (2025)
- [Neural Auto-Curricula](https://mlsanity.com/paper/2106.02745/) (2021)
- [On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization](https://mlsanity.com/paper/2510.19953/) (2025)
- [Scalable Random Wavelet Features: Efficient Non-Stationary Kernel Approximation with Convergence Guarantees](https://mlsanity.com/paper/2602.00987/) (2026)

## Abstract (arXiv)

We present a new method of blackbox optimization via gradient approximation with the use of structured random orthogonal matrices, providing more accurate estimators than baselines and with provable theoretical guarantees. We show that this algorithm can be successfully applied to learn better quality compact policies than those using standard gradient estimation techniques. The compact policies we learn have several advantages over unstructured ones, including faster training algorithms and faster inference. These benefits are important when the policy is deployed on real hardware with limited resources. Further, compact policies provide more scalable architectures for derivative-free optimization (DFO) in high-dimensional spaces. We show that most robotics tasks from the OpenAI Gym can be solved using neural networks with less than 300 parameters, with almost linear time complexity of the inference phase, with up to 13x fewer parameters relative to the Evolution Strategies (ES) algorithm introduced by Salimans et al. (2017). We do not need heuristics such as fitness shaping to learn good quality policies, resulting in a simple and theoretically motivated training mechanism.