Cross-Entropy Method (CEM)

• Also called: CEM
• Category: Planning & manipulation › Trajectory optimisation
• Tags: optimization, sampling-based-planning, model-predictive-control, model-based-rl, trajectory-optimization

A sampling-based optimizer that repeatedly samples candidate solutions, keeps the best-scoring fraction and refits the sampling distribution to them; widely used to optimize action sequences in model-based control.

Definition

The cross-entropy method (CEM) is a simple derivative-free optimization algorithm. It keeps a probability distribution over candidate solutions, usually a Gaussian with a mean and a diagonal variance. Each iteration it draws a batch of samples, evaluates the cost of each, selects the best-scoring fraction (the elites), and refits the distribution's mean and variance to those elites, often with some smoothing toward the previous values. Over iterations the distribution narrows around a good solution. The method was developed by Reuven Rubinstein in the late 1990s, first for estimating rare-event probabilities and then for optimization; its name comes from the fact that the refitting step minimizes the cross-entropy, or KL divergence, between the sampling distribution and a distribution concentrated on high-scoring samples.

In robotics, CEM is best known as the trajectory optimizer inside sampling-based model predictive control. The decision variable is a sequence of actions over a planning horizon. Each sampled sequence is rolled out through a dynamics model, either a physics simulator or a learned model, and scored by the summed cost or predicted reward. After a few CEM iterations, the robot executes the first action of the mean or best sequence, then replans at the next step, typically warm-starting by shifting the previous solution forward in time. Model-based reinforcement learning methods such as PETS and PlaNet use CEM in this way with learned models, and variants add temporally correlated noise, reuse elites across steps or combine CEM with a learned policy that proposes samples.

CEM's appeal is that it needs no gradients, handles non-smooth or discontinuous costs and is easy to run in parallel on a GPU. Its weaknesses are sample cost, which grows quickly with the length of the horizon and the number of action dimensions, and a tendency to collapse its variance too early onto a local optimum. Unlike MPPI, which weights all samples by an exponential of their cost, CEM uses a hard cutoff and treats the elites equally. Unlike gradient-based trajectory optimizers such as iLQR or DDP, it does not exploit model derivatives, so it is usually less sample-efficient on smooth problems but more forgiving of learned or black-box models.

Why it matters

CEM is one of the simplest ways to turn a dynamics model into a controller, and it appears as the default planner in many model-based learning papers. Understanding its elite selection, horizon and sample-count trade-offs is necessary to reproduce those results or to decide whether a gradient-based or MPPI-style planner fits a problem better.

Key applications

• Sampling-based model predictive control with learned dynamics models
• Planning in latent world models for visual control
• Grasp and action selection by sampling and scoring candidates
• Policy search and parameter tuning without gradients
• Optimizing actions in Q-learning with continuous action spaces

In practice

A team using a learned dynamics model for a pushing task runs CEM-based MPC at each control step. They sample several hundred action sequences over a short horizon from a Gaussian, roll each through the learned model on the GPU, keep the top tenth by predicted cost, refit the mean and variance, and repeat a few times before executing the first action. When the planner chatters between steps, they shift and reuse the previous mean as a warm start and add a minimum variance so the search does not collapse. Because CEM will exploit model errors that predict unrealistically low costs, they also add a penalty for action sequences that move far from the training data of the model.

Common misconceptions

• CEM is a reinforcement learning algorithm — it is a general-purpose optimizer; in model-based RL it plans with a model, while learning happens in the model or value function
• More CEM iterations always help — the variance can collapse prematurely onto a poor local optimum, and with a learned model extra optimization can exploit model errors
• CEM and MPPI are the same — both sample action sequences, but CEM refits to a hard-selected elite set while MPPI weights every sample by its exponentiated cost

Who should know this

• Model-based reinforcement learning researchers
• Control engineers using sampling-based MPC
• Manipulation engineers planning with learned or simulated models
• Students comparing trajectory optimization methods

Related technologies

• PETS
• PlaNet
• iCEM
• Random Shooting
• CMA-ES
• JAX

Related terms

• Model Predictive Path Integral
• Model Predictive Control
• Forward Dynamics Model
• World Model
• Differential dynamic programming
• Trajectory Planning

Related projects

• Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
• GTSAM: Factor-graph optimization library powering many modern SLAM backends
• PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
• MuJoCo MPC: DeepMind's interactive real-time model predictive control framework for MuJoCo
• PyPose: PyTorch library for differentiable robotics with deep learning and Lie group optimization
• NeuPAN: Real-time end-to-end planner that maps raw lidar points directly to robot actions