⚡ electrical engineering

Sample-Efficient and Smooth Cross-Entropy Method Model Predictive Control Using Deterministic Samples

This paper proposes deterministic sampling CEM (dsCEM), a novel framework that replaces random sampling with deterministic samples derived from localized cumulative distributions to significantly improve sample efficiency and control smoothness in nonlinear optimal control, particularly in low-sample regimes.

Original authors: Markus Walker, Daniel Frisch, Uwe D. Hanebeck

Published 2026-05-12

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Markus Walker, Daniel Frisch, Uwe D. Hanebeck

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to drive a car up a steep, winding hill or balance a pole on a moving cart. The robot needs to figure out the perfect sequence of moves (accelerating, braking, turning) to succeed. This is a complex puzzle, and the robot has to solve it over and over again, every second, to stay on track.

This paper introduces a new way for the robot to solve these puzzles, making it faster, smoother, and more efficient. Here is the breakdown using simple analogies:

The Problem: The "Random Guessing" Game

The current standard method (called CEM-MPC) works like a student taking a test by guessing answers randomly.

The Process: The robot generates thousands of random sequences of moves.
The Selection: It tries them all out (in a simulation) and picks the top 10% that worked best.
The Refinement: It uses those "winning" guesses to make the next batch of random guesses slightly better.
The Flaw: Because it relies on randomness, it often wastes time. It might guess the same bad move twice, or leave huge gaps in its search where it never tries a good move. Also, because the guesses are random, the resulting movements can be jerky and jerky, like a driver slamming the gas and brake randomly. This can wear out the robot's parts.

The Solution: The "Strategic Map" (dsCEM)

The authors propose a new method called dsCEM (Deterministic Sampling Cross-Entropy Method). Instead of rolling dice to pick their next guesses, the robot uses a pre-calculated, perfectly spaced map.

The Analogy: Imagine you need to paint a wall.
- Random Sampling (Old Way): You throw paintballs at the wall randomly. You might get a thick clump of paint in one spot and a bare patch in another. You have to throw thousands of balls to get even coverage.
- Deterministic Sampling (New Way): You use a stencil with holes perfectly spaced out. You only need to throw a few paintballs to cover the entire wall evenly. There are no gaps and no clumps.

How It Works

Pre-Made Patterns: Before the robot even starts driving, the researchers create a set of "perfectly spaced" sample patterns (based on something called Localized Cumulative Distributions). Think of these as a master template.
Adapting the Template: When the robot needs to make a decision, it takes this master template and stretches or shrinks it to fit the current situation.
Adding Smoothness: The old method often produced jerky movements. The new method includes a rule that ensures the "paintballs" (the control moves) flow smoothly from one moment to the next, like a dancer rather than a jittery robot.

The Results: Faster and Smoother

The authors tested this on two classic robot challenges:

The Mountain Car: A car that is too weak to drive straight up a hill and must swing back and forth to build momentum.
The Cart-Pole: Balancing a long pole on a moving cart.

What they found:

Less is More: The new method (dsCEM) achieved better results using far fewer guesses than the old random method. In the "low-sample" regime (when the computer has very little time to think), the new method was significantly better.
Smoother Moves: The movements generated by the new method were much smoother. This is crucial because jerky movements can break real-world robots.
No Extra Cost: The new method didn't take longer to compute; in fact, because it needed fewer samples, it was often faster.

The Bottom Line

The paper claims that by swapping "random guessing" for "strategic, pre-spaced patterns," robots can learn to control themselves much more efficiently. They can solve complex problems with fewer computer calculations and move more smoothly, which is a huge win for real-time control on hardware that doesn't have super-computer power.

The authors emphasize that this is a "drop-in replacement," meaning you can swap this new method into existing robot controllers without having to rebuild the whole system. They also note that this method works well alongside other advanced AI techniques, like learning from past experiences.

Technical Summary: Sample-Efficient and Smooth Cross-Entropy Method

Problem Statement

Model Predictive Control (MPC) is a standard approach for nonlinear optimal control, yet solving the underlying optimization problem remains challenging, particularly for systems with non-differentiable dynamics or non-convex cost functions. In such scenarios, gradient-free methods like the Cross-Entropy Method (CEM) are preferred. However, standard CEM-based MPC (CEM-MPC) relies on random sampling to explore the control space. This reliance presents two primary limitations:

Inefficiency: Random sampling often leads to inefficient exploration, requiring a large number of samples to achieve satisfactory results, which is computationally expensive.
Non-Smoothness: Even with improvements like temporal correlations (e.g., in the Improved CEM or iCEM), random sampling can produce non-smooth control trajectories. This erratic behavior is undesirable in practice as it can damage actuators and cause unstable system behavior.

Methodology

The authors propose deterministic sampling Cross-Entropy Method (dsCEM), a framework that replaces the random sampling step in CEM-MPC with deterministic samples derived from Localized Cumulative Distributions (LCDs).

Core Mechanism

Instead of drawing random samples from a proposal distribution, dsCEM utilizes pre-computed optimal sample sets based on LCDs. These samples are designed to cover the solution space with low discrepancy, avoiding the clustering and gaps inherent in random sampling.

Offline Generation: Optimal deterministic samples $\{\tilde{\xi}^{(i)}\}$ are generated offline for an isotropic standard Gaussian distribution by minimizing a modified Cramér–von Mises (CvM) distance between the target Gaussian and a Dirac mixture approximation.
Online Transformation: At runtime, these pre-computed samples are transformed to match the current proposal distribution $N(\hat{\xi}_j, C_j)$ of the CEM optimizer using the affine transformation:
$\xi^{(i)} = \hat{\xi}_j + L_j \tilde{\xi}^{(i)}$
where $L_j$ is the matrix square root of the covariance matrix $C_j$ .

Variability and Adaptation Schemes

To prevent premature convergence and ensure adequate exploration, the authors introduce modular schemes for generating varied sample sets across iterations and time steps:

Variability Schemes (V1–V3):
- V1 (Random Rotation): Rotates samples by a random matrix in each iteration, introducing stochasticity.
- V2 (Deterministic Joint Density): Pre-computes samples in a high-dimensional space encompassing all iterations, partitioning them to provide unique deterministic sets for each step.
- V3 (Combined): Rotates a high-dimensional set once per MPC time step, then uses the resulting samples deterministically for all internal CEM iterations.
Covariance Adaptation (M1–M2):
- M1 (Fixed Correlation, Adaptive Variance): Maintains a fixed temporal correlation structure (derived from colored noise power spectral density) while updating marginal variances.
- M2 (Adaptive Full Covariance): Updates the full covariance matrix online to adapt temporal correlations, requiring a larger elite set.

These schemes are designed as "drop-in" replacements for the sampling step in existing CEM-based controllers.

Key Contributions

Novel Framework: Introduction of dsCEM, which integrates deterministic sampling via LCDs into the CEM-MPC loop.
Modular Design: The proposed sampling schemes are orthogonal to other CEM improvements (e.g., learning-based warm-starts) and can be combined with them.
Smoothness and Efficiency: The method explicitly targets the generation of smooth control trajectories without requiring explicit smoothness penalties or additional hyperparameters, while simultaneously improving sample efficiency.

Experimental Results

The authors evaluated dsCEM against the state-of-the-art iCEM method on two nonlinear control benchmarks: the Mountain Car task and the Cart-Pole Swing-Up task. The evaluation focused on cumulative cost and control input smoothness across varying sample sizes ( $N_{CEM}$ from 20 to 300).

Performance: Across both tasks, dsCEM variants consistently outperformed iCEM in terms of cumulative cost, particularly in the low-sample regime. While performance converged for larger sample sizes, dsCEM achieved results comparable to an iCEM baseline with $10^4$ samples using significantly fewer samples.
Smoothness: dsCEM produced significantly smoother control trajectories than iCEM. Notably, the fully deterministic variant (dsCEM-Var V2) achieved the highest smoothness, often surpassing the extensive iCEM baseline even with a fraction of the sample budget.
Convergence: In convergence plots (fixed sample size of 50), dsCEM variants demonstrated faster convergence to low stage costs compared to iCEM.
Computational Overhead: The authors report no measurable runtime overhead from the deterministic sampling and variation schemes compared to random sampling, with parallelization capable of further reducing execution time.

Significance and Claims

The paper claims that replacing random sampling with deterministic sampling based on LCDs addresses the fundamental inefficiencies of CEM-MPC. The significance of this work lies in:

Sample Efficiency: Enabling high-performance control with fewer samples, which is critical for real-time applications where computational resources are limited.
Inherent Smoothness: Achieving smooth control inputs naturally through the structure of the sampling process, rather than through additional penalty terms.
Practical Deployment: The reduction in sample requirements lowers the computational burden across all stages of the CEM algorithm (sampling, elite selection, trajectory shooting, and cost evaluation). This makes MPC feasible for systems with complex models and longer prediction horizons on hardware with limited parallelization capabilities.

The authors conclude that dsCEM is a promising option for real-time control on computationally constrained hardware and suggest that its orthogonal nature allows for future combination with learning-based improvements.