Source-linked AI summary
Structured Evolution with Compact Architectures for Scalable Policy Optimization
Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani, Richard E. Turner, Adrian Weller
TL;DR
Blackbox policy optimization must work with noisy function evaluations while remaining scalable in high-dimensional parameter spaces. The paper combines structured orthogonal exploration with compact, parameter-sharing policies, showing that the resulting methods learn quality policies with substantially fewer parameters and scalable computation. These policies solve most evaluated MuJoCo tasks with networks of barely 300 parameters, up to 13 times smaller than the ES baseline.
Problem
Noisy, expensive blackbox evaluations provide no gradients, while conventional derivative-free optimization is difficult to scale to high-dimensional policy spaces.
Method
The paper combines structured evolution strategies using orthogonal, discrete, and Quasi Monte Carlo directions with compact policy networks based on parameter sharing.
Results
Most evaluated MuJoCo tasks were solved with networks of barely 300 parameters, up to 13 times smaller than those of Salimans et al. (2017), without losing accuracy.
Takeaways & Limitations
Structured exploration and compact architectures provide scalable blackbox optimization and policy learning for resource-constrained settings.
Takeaways & Limitations
Gaussian orthogonal exploration requires Gram-Schmidt orthogonalization at every optimization iteration, although this remains reasonable for compact policies with only a few hundred parameters.
Abstract
from arXiv · showhide
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.
1. Introduction
Derivative-free optimization addresses policy learning when rewards are noisy, expensive, and gradient-free. The paper improves its efficiency through structured exploration and compact policy architectures, showing strong results on benchmark optimization and control tasks.
- Noisy, expensive blackbox evaluations make standard gradient ascent unavailable in stochastic simulators and real robotic systems.
- DFO is difficult to scale because it typically requires O(d) more iterations than gradient methods, limiting conventional applications to relatively small problems.
- The approach combines structured exploration with parameter-sharing architectures to reduce policy dimensionality without losing accuracy.
- The paper proposes structured exploration using orthogonal and Quasi Monte Carlo directions instead of the Gaussian directions used by standard ES.
- Most evaluated MuJoCo tasks can be solved with policies of barely 300 parameters, up to 13 times smaller than those of Salimans et al. (2017).The compact networks use Toeplitz weight matrices, supporting fast Fourier-transform inference.
2. Gaussian Smoothings and Monte Carlo Gradient Estimation
The paper smooths the blackbox objective and estimates the smoothed gradient with Monte Carlo finite-difference methods. It compares vanilla, antithetic, and forward finite-difference estimators while motivating mean-squared error as the comparison criterion.
- Gaussian smoothing replaces the possibly nondifferentiable objective with a differentiable averaged function obtained by perturbing parameters along Gaussian directions.
- The smoothed objective can differ qualitatively from the original, with its optimum lacking a general guarantee of proximity to the original optimum.
- Because the smoothed gradient is intractable, the paper estimates it using Monte Carlo estimators and investigates variance-reduction techniques.
- Estimators: The vanilla ES estimator samples independent Gaussian parameter-exploration directions for the gradient estimate.
- Estimators: Antithetic ES pairs each Gaussian direction with its negative, whereas forward finite-difference ES introduces a control variate without an additional function evaluation.
- Estimator comparison: Neither forward finite-difference nor antithetic estimation uniformly dominates the other, so the paper evaluates estimators using mean squared error.
3. Variance Reduction via Orthogonality and Quasi-Monte Carlo Exploration
The paper improves blackbox gradient estimation by coordinating exploration directions through exact orthogonality, structured matrices, and quasi-Monte Carlo sequences. These choices provide lower estimator error or faster numerical integration while offering computationally efficient constructions.
- Gaussian Orthogonal Exploration: The Gaussian orthogonal construction gives each exploration direction a marginal N(0, I) distribution while conditioning directions to be mutually orthogonal when N ≤ d.For N > d, consecutive sets of d vectors are orthogonal while distinct sets remain independent.
- Gaussian Orthogonal Exploration: Orthogonal exploration directions yield an unbiased antithetic ES estimator with lower MSE than its iid counterpart.The improvement remains valid when function evaluations contain independent mean-zero noise.
- Computational Considerations: Gaussian orthogonal exploration can improve estimator quality but requires Gram-Schmidt orthogonalization at every optimization iteration.The paper considers this practical for compact policies with only a few hundred parameters.
- Discrete Orthogonal Exploration: Structured discrete matrices replace Gaussian orthogonalization with directions from Mstruct, preserving analogous orthogonality properties without preprocessing.Random Hadamard-Rademacher matrices are a concrete construction whose products can be computed in subquadratic time.
- Quasi-Monte Carlo Exploration: QMC gradient estimation uses low-discrepancy sequences, which offer faster convergence rates than random point sets for numerical integration.The experiments use generalized Halton sequences after transforming the integral to the unit cube.
4. Learning Compact Policies
The paper learns compact neural policies by imposing parameter-sharing structures such as Toeplitz weight matrices. This reduces storage and computation while maintaining strong derivative-free optimization performance on MuJoCo tasks.
- Motivation: Dense policy matrices can make storage and O(mn) matrix-vector products prohibitive on resource-constrained hardware.Parameter sharing reduces the policy search space, which the paper identifies as beneficial for ES/DFO training as well as inference.
- Compact Policy Architecture: 13× compression relative to Salimans et al. (2017) was achieved on 12 MuJoCo reinforcement-learning tasks with Toeplitz policies and superior DFO training curves.Toeplitz matrices have constant diagonals and support fast matrix-vector products via Fast Fourier Transforms.
5. Distributed Implementation
The distributed implementation partitions exploration directions across workers, aggregates their estimator contributions centrally, and reduces communication by reconstructing structured perturbations locally. Hadamard-based directions retain scalable computation, while compact networks reduce worker and inference costs relative to unstructured architectures.
- Distributed estimator computation: Exploration directions are partitioned among workers, each computing its assigned contribution before a central worker averages the results.The approach can handle thousands of directions for larger policy networks.
- Communication complexity: Workers and the master share a seed and row assignments, allowing each worker to generate only its required Hadamard-Rademacher directions.Only function-evaluation results need to be collected by the master.
- Computational complexity: Hadamard-Rademacher perturbations cost O(kd log d) per worker per direction to reconstruct, compared with O(d) for iid perturbations.The Fast Hadamard Transform provides the stated reconstruction procedure.
- Computational complexity: For k = 1, randomized Hadamard rows can be generated in linear time, whereas Gaussian orthogonal directions require O(d3) per worker.The Gaussian construction includes forming a random Gaussian matrix and applying Gram-Schmidt orthogonalization.
- Compact policy architecture: Compactly parameterized networks reduce worker computation and provide log-linear rather than quadratic inference complexity compared with unstructured networks.The networks are trained in their already compressed form rather than compressed after training.
6. Experiments
The experiments evaluate structured exploration and compact policy architectures across blackbox optimization and 12 OpenAI Gym control tasks. Structured methods generally outperform iid or unstructured baselines while using substantially fewer policy parameters or roll-outs.
- Lower-Dimensional Blackbox Optimization: 212 blackbox optimization problems compare iid, orthogonal, Hadamard, and QMC antithetic ES estimators using objective quality and function-evaluation counts.The benchmark covers smooth, nondifferentiable, deterministically noisy, and stochastically noisy variants.
- Lower-Dimensional Blackbox Optimization: Structured exploration outperforms IID exploration across the evaluated blackbox optimization tasks.Performance is summarized using normalized scores and average rankings across the benchmark tasks.
- Learning Structured Policies: CP:ST combines compact policies with structured directions, while CP:UN and FP:UN use unstructured directions with compact and full architectures, respectively.The compact architectures use Toeplitz weight matrices and tanh nonlinearities.
- Learning Structured Policies: CP:ST learned high-quality policies for most tasks and solved Swimmer, Ant, HalfCheetah, Hopper, Walker2d, Pusher, Reacher, Striker, Continuous Mountain Car, and Pendulum.Competitive FP:UN policies were generally not learned without fitness shaping.
- Learning Structured Policies: CP:ST outperformed CP:UN on most tasks, while fully unstructured networks were better than Toeplitz networks on only one of twelve tasks.The reported task list includes both Gaussian orthogonal and Hadamard structured mechanisms.
- Learning Structured Policies: CP:ST with Gaussian orthogonal directions achieved Ant reward R = 9249, while CP:UN achieved R = 8615.Training used shortened roll-outs, followed by evaluation of the best policy with full roll-outs.
- Learning Structured Policies: 167 roll-outs per iteration solved Swimmer with 253 parameters, compared with 4864 roll-outs required by Salimans et al. (2017).The comparison uses Gaussian orthogonal directions and structured exploration with N < d.
7. Conclusion
The paper proposes structured evolution strategies and compact policy networks as complementary methods for derivative-free optimization in reinforcement learning. It presents them as scalable blackbox optimization approaches that learn good-quality policies, while identifying further questions about matrix structures and variance reduction.
- The paper proposes structured evolution strategies and compact policy networks for derivative-free optimization in reinforcement learning.
- These methods are applied as scalable blackbox optimization algorithms that learn good-quality reinforcement-learning policies.
- Future work concerns exploiting other matrix structures and developing additional variance-reduction methods for evolution strategies.
8. Proofs
The proofs compare the mean-squared error of iid and orthogonal gradient estimators. Their conclusion is that exact orthogonality yields a strictly lower MSE under the stated construction.
- The proof assumes marginally Gaussian, almost-surely orthogonal directions and considers the case N ≤ d.
- The iid estimator's cross-direction terms are nonnegative, whereas orthogonality makes the corresponding inner products zero almost surely.
9. Implementation details
The implementation details specify Hadamard-Rademacher and QMC constructions for exploration directions and explain how Toeplitz policy parameters are represented. These procedures replace iid Gaussian directions while retaining forward-pass-only policy evaluation.
- Hadamard-Rademacher exploration: Hadamard-Rademacher directions are generated by randomized diagonal matrices, Hadamard transforms, normalization, and selection of matrix rows.
- Toeplitz policy representation: Toeplitz layers encode each connection matrix with a vector of size m + n − 1 and are reconstructed during inference.
- QMC exploration: QMC directions start from quasi-Monte Carlo samples in [0, 1]^d and transform each coordinate with the standard Normal CDF.
- Toeplitz policy representation: The implementation does not backpropagate through the network; it runs forward passes and updates vectorized parameter representations.
10. Related work
The paper compares exploration methods using normalized scores and average rankings across optimization tasks, then examines whether their relative behavior changes with exploration noise. Additional results cover learning curves and mean rewards across robotics environments and architectures.
- Comparison methodology: Rank-based comparisons are broadly consistent with comparisons based on normalized scores.
- Noise sensitivity: Relative exploration-method behavior remains similar when σ changes from 10^-6 to 10^-7 or 10^-5.The corresponding results are reported in Figures 5–8.
- Robotics experiments: Learning-curve results cover different OpenAI Gym environments and algorithms, with additional experiments using 20 random seeds and mean-reward standard deviations.The supplementary setup also compares structured and unstructured architectures with standard finite-difference gradient approximation in robotics tasks.