An Introduction to Zero-Order Optimization Techniques for Robotics

The gist The authors propose a mathematical tutorial on random search to provide a simple and unifying perspective for understanding various zero-order optimization techniques used in robotics, such as trajectory optimization and reinforcement learning.

Zero-Order Optimization Techniques

Zero-order (or derivative-free) optimization techniques are becoming increasingly popular in robotics due to their ability to handle nondifferentiable functions and escape local minima<ref:2506.22087#pg2>. These advantages make them particularly useful for trajectory optimization and policy optimization<ref:2506.22087#pg2>. They share a common property: they do not require access to the simulator’s gradients, which allows them to optimize non-smooth objective functions typically arising in problems involving contact, such as locomotion or manipulation<ref:2506.22087#pg2>. Furthermore, while deterministic gradient-based algorithms are prone to getting stuck in local minima, zero-order techniques are mostly stochastic, which can help escape local minima<ref:2506.22087#pg2>.

Random Search Approaches

The basic idea of zero-order optimization performs a random search by generating samples at random and updating an estimate of the optimal solution based on the performance of each sample<ref:2506.22087#pg2>. Simple random search, or Pure Random Search, consists of iteratively sampling points at random and keeping the best one found so far<ref:2506.22087#pg2>. A common attempt to break the curse of dimensionality is Greedy Local Search, which involves iteratively searching around the previous estimate with additive Gaussian noise<ref:2506.22087#pg2>.

Gradient Approximation Methods

Various ways exist to perform approximate gradient descent using only function evaluations, summarized in Algorithm 3<ref:2506.22087#pg2>. Techniques include:

1. Forward finite difference technique, which requires n + 1 function evaluations<ref:2506.22087#pg2>.

2. Random Coordinate Descent, which alternates descent steps on random coordinates and can require on average at most n times more steps compared to classical gradient descent<ref:2506.22087#pg2>.

3. Simultaneous Perturbation Stochastic Approximation (SPSA), which replaces finite differences with a stochastic estimate that can achieve performance similar to finite differences while requiring n times fewer samples<ref:2506.22087#pg2>.

4. Gaussian Smoothing, which studies a smoothed surrogate function fµ(x) = E[f(x + µϵ)], and its gradient can be estimated using only function evaluations of the original function f<ref:2506.22087#pg2>.

Simulated Annealing and Langevin Dynamics

Additive Gaussian noise can lead to asymptotic global convergence guarantees in nonconvex settings through Langevin dynamics, defined by dXt = ∇x log p(Xt) + dWt<ref:2506.22087#pg2>. This SDE can be used to sample from a distribution with probability density p ∝ exp − 1/λ f, where λ > 0 is the temperature<ref:2506.22087#pg2>. The discretized Stochastic Langevin Gradient Dynamics guarantees asymptotic convergence to global solutions when the step sizes are chosen appropriately, which is called Simulated Annealing<ref:2506.22087#pg2>.

Trajectory Optimization Applications

Trajectory Optimization aims to solve min x∈Rn f(x) subject to dynamics and cost functions<ref:2506.22087#pg2>. Predictive sampling can be seen as a variation of Greedy Local Search, where K search directions are sampled and the best one is kept<ref:2506.22087#pg2>. Model Predictive Path Integral (MPPI) iteratively samples around the current guess and updates it using a weighted exponential average, which can be interpreted as a generalization of Gaussian smoothing<ref:2506.22087#pg2>. Covariance Matrix Adaptation (CMA) optimizes the smooth surrogate function by searching over the mean and covariance of a Gaussian distribution, where optimizing Equation (5) can be interpreted as a search over the mean of a Gaussian distribution<ref:2506.22087#pg2>.

Policy Optimization Connections

In policy optimization, one approach is to directly rely on zero-order techniques by sampling in the parameter space of a neural network<ref:2506.22087#pg2>. Gaussian smoothing on the Q-function can be used to estimate the gradient of the Q-function and use an estimate for the gradient of the cost, leading to an Actor-Critic structure<ref:2506.22087#pg2>. The policy gradient theorem is analogous to the log-likelihood trick of Gaussian smoothing, suggesting that stochasticity in RL algorithms could explain their empirical ability to avoid poor local minima<ref:2506.22087#pg2>.

Population Based Algorithms

To mitigate issues with samples failing to mix well in multimodal distributions, algorithms can consider multiple starting points through Random Restart or (N + λ)-ES<ref:2506.22087#pg2>. The (N + λ)-ES procedure involves maintaining a population of N samples and generating a new population by applying local search, selecting the N best samples<ref:2506.22087#pg2>.

Parallel Computing

To improve computational efficiency, parallelizing function evaluations is a typical strategy, utilizing parallel simulators such as MuJoCo XLA (MJX) and Isaac Sim for massively parallel rollouts<ref:2506.22087#pg2>. Algorithmic implementations of random search and popular ES algorithms based on JAX can then be used for zero-order MPC with Hydrax<ref:2506.22087#pg2>.

Conclusion

The work demonstrates how random search provides a unifying perspective on zero-order algorithms commonly used in robotics and discusses theoretical concepts explaining why sampling-based zero-order techniques can escape local minima<ref:2506.22087#pg2>. Leveraging this understanding, the authors propose novel and competitive RL algorithms that are examples of the potential outcomes enabled by this unified viewpoint<ref:2506.22087#pg2>.

1. Improved Trajectory Optimization (TO) via MPPI-CMA: The system can solve constrained trajectory optimization problems with linear complexity in terms of time horizon T by using a block-diagonal covariance matrix for CMA updates, which ensures linear complexity with respect to the time horizon T as noted in the text.

2. Improved Policy Optimization (RL) via Randomized Smoothing: The RL algorithm can achieve better performance than standard Deterministic Policy Gradient (DPG) algorithms by using Gaussian smoothing on the Q-function, as demonstrated by RS-DDPG and LSE-DDPG significantly outperform DDPG.

3. Improved Sample Efficiency in Optimization: The system can perform derivative-free optimization with reduced function evaluations by employing methods like Random Coordinate Descent or Simultaneous Perturbation Stochastic Approximation (SPSA), which offer the hope of matching the gradient’s descent performance with a few samples.

4. Improved Global Convergence in Nonconvex Settings: The system can be designed to escape local minima by incorporating stochasticity, as shown by discretized Stochastic Langevin Gradient Dynamics which guarantees asymptotic convergence to global solutions for optimization problems.

5. Improved Policy Search via Action Space Sampling: A novel RL algorithm can be derived that leverages the structure of the problem to sample from the action space, moving beyond direct sampling in parameter space and potentially achieving state-of-the-art performance in deterministic policy gradient algorithms.

Zero-order optimization techniques are becoming increasingly popular in robotics due to their ability to handle non-differentiable functions and escape local minima. These advantages make them particularly useful for trajectory optimization and policy optimization. In this work, we propose a mathematical tutorial on random search. It offers a simple and unifying perspective for understanding a wide range of algorithms commonly used in robotics. Leveraging this viewpoint, we classify many trajectory optimization methods under a common framework and derive novel competitive RL algorithms.