Abstract
We propose a simple drop-in noise-tolerant replacement for the standard finite difference procedure used ubiquitously in blackbox optimization. In our approach, parameter perturbation directions are defined by a family of structured orthogonal matrices. We show that at the small cost of computing a Fast Walsh-Hadamard/Fourier Transform (FWHT/FFT), such structured finite differences consistently give higher quality approximation of gradients and Jacobians in comparison to vanilla approaches that use coordinate directions or random Gaussian perturbations. We find that trajectory optimizers like Iterative LQR and Differential Dynamic Programming require fewer iterations to solve several classic continuous control tasks when our methods are used to linearize noisy, blackbox dynamics instead of standard finite differences. By embedding structured exploration in a quasi-Newton optimizer (LBFGS), we are able to learn agile walking and turning policies for quadruped locomotion, that successfully transfer from simulation to actual hardware. We theoretically justify our methods via bounds on the quality of gradient reconstruction and provide a basis for applying them also to nonsmooth problems.
Introduction
In the field of robotics and simulation, the underlying physics engines are often treated as "black boxes." Calculating exact gradients is frequently impossible due to non-smooth dynamics or inaccessible source code. Consequently, researchers rely on the finite difference (FD) method, which estimates gradients by perturbing system parameters and observing output changes. However, standard FD is notoriously brittle; even minimal numerical noise or simulation randomness can render gradient estimates unusable, causing optimization algorithms like Iterative Linear Quadratic Regulator (iLQR) to fail. While randomized Gaussian perturbations offer some relief, they typically suffer from high variance and data inefficiency.
Methodology: Structured Orthogonal Perturbations
To address these limitations, we introduce a family of perturbation matrices termed "balanced spinners." Instead of the traditional approach of perturbing one coordinate at a time or using independent Gaussian noise, we utilize rows of structured orthogonal matrices, such as Hadamard or Quadratic Residue matrices.
This approach offers several key advantages:
- Noise Resilience: We mathematically demonstrate that these structured directions provide tighter bounds on gradient reconstruction error compared to standard methods, particularly in noisy environments.
- Computational Efficiency: The inherent structure of these matrices allows for gradient reconstruction via the Fast Walsh-Hadamard Transform (FWHT) or Fast Fourier Transform (FFT). This maintains a computational complexity of $O(n \log n)$, nearly as efficient as the $O(n)$ cost of standard FD but with significantly higher accuracy.
- Seamless Integration: Our method serves as a "drop-in" replacement for existing solvers, including iLQR, Differential Dynamic Programming (DDP), and L-BFGS-B.
Benchmarking and Trajectory Optimization
We evaluated our structured exploration method across a variety of simulation benchmarks, ranging from classic control tasks like Cartpole and Acrobot to more complex trajectory optimization problems.
The geometry of exploration proves critical: by ensuring that perturbation directions are spread efficiently across the parameter space, we avoid the "clumping" or gaps inherent in pure Gaussian randomness. This middle ground between deterministic coordinate-wise FD and fully random search provides the coverage of randomness with the stability of orthogonality.
Results and Hardware Deployment
Our results indicate significant improvements in both convergence speed and robustness. In the Acrobot balancing task, iLQR using structured FD converged in fewer than 30 iterations, whereas standard FD failed entirely under noisy conditions. Despite the slightly higher per-gradient computational cost ($O(n \log n)$ vs $O(n)$), the total wall-clock time to reach convergence was reduced by up to 50% due to the drastic reduction in required optimization steps.
A key highlight of this work is the successful sim-to-real transfer for the Minitaur quadruped robot. By utilizing high-quality gradients during training in the Bullet simulator, we developed agile walking and turning maneuvers that transferred directly to the physical hardware without major flaws.
Conclusion and Future Work
While our current focus has been on open-loop policies, future research will explore training closed-loop feedback policies, which involve higher-dimensional parameter spaces. We also aim to scale these methods further by combining them with block-coordinate updates and massive parallelization to handle complex neural network policies. Although we have established a theoretical basis for non-smooth problems via Gaussian smoothing, further testing in highly discontinuous environments remains a priority.
Summary updated