Source-linked AI summary
Sample-efficient Cross-Entropy Method for Real-time Planning
Cristina Pinneri, Shambhuraj Sawant, Sebastian Blaes, Jan Achterhold, Joerg Stueckler, Michal Rolinek, Georg Martius
TL;DR
CEM-based trajectory optimization is promising for high-dimensional and sparse-reward control but is too sampling-intensive for real-time planning. The paper introduces iCEM with memory and temporally correlated action sampling, achieving substantially better sample efficiency and performance across challenging control tasks. Its experiments enter the real-time regime when using learned models.
Problem
CEM produces strong results in high-dimensional and sparse-reward control, but its high computational cost and sampling inefficiency hinder real-time planning and control.
Method
iCEM improves CEM for model-predictive trajectory optimization by introducing memory and temporally correlated action sequences.
Results
Across environments, iCEM is 2.7–21.9× more sample efficient and reaches 120–1030% of the best baseline performance under the reported budgets.
Takeaways & Limitations
With only 45 trajectories per step, iCEM solves complicated tasks such as humanoid stand-up and sparse-reward door opening, entering the real-time regime with learned models.
Abstract
from arXiv · showhide
Trajectory optimizers for model-based reinforcement learning, such as the Cross-Entropy Method (CEM), can yield compelling results even in high-dimensional control tasks and sparse-reward environments. However, their sampling inefficiency prevents them from being used for real-time planning and control. We propose an improved version of the CEM algorithm for fast planning, with novel additions including temporally-correlated actions and memory, requiring 2.7-22x less samples and yielding a performance increase of 1.2-10x in high-dimensional control problems.
1 Introduction
The paper targets the high computational cost that makes population-based CEM unsuitable for real-time planning and control. It introduces iCEM, which adds memory and temporally correlated action sequences, and evaluates it across challenging continuous-control and manipulation tasks.
- Motivation: High computational cost and large sampling requirements make population-based optimizers unsuitable for real-time planning and control.The paper identifies this as a key deployment barrier for robotics.
- Approach: iCEM enhances CEM with memory and temporally correlated action sequences to address sampling inefficiency in high-dimensional systems.These upgrades are unified under the name iCEM.
- Evaluation: iCEM is evaluated on hard continuous-control and sparse-reward manipulation tasks in the MuJoCo simulator.The evaluation includes HUMANOID STANDUP, FETCH PICK&PLACE, DOOR, and RELOCATE.
- Results: 90% success on RELOCATE uses 13.7× fewer samples and yields 400% higher average performance than state-of-the-art CEM.The comparison is reported for the RELOCATE task.
- Scope: The method is designed to make CEM itself fast enough for real-time robot planning and can integrate with existing methods using CEM or other zeroth-order optimizers.The paper presents this as its claimed novelty and intended compatibility.
2 The Cross-Entropy Method
CEM is a derivative-free, population-based optimizer that iteratively concentrates a Gaussian sampling distribution around low-cost candidates. In model-predictive control, it repeatedly optimizes action-sequence plans while shifting the previous solution forward between environment steps.
- Definition: CEM is a derivative-free optimization technique that originated as an adaptive importance-sampling procedure for estimating rare-event probabilities.It uses the cross-entropy measure.
- Optimization procedure: CEM samples candidate individuals, evaluates their costs, sorts them, and selects a fixed number of elite candidates.The elite set determines the population parameters for the next iteration.
- Optimization procedure: The standard sampling population is Gaussian with mean µ and diagonal covariance diag(σ^2), fitted to the elite set so sampling concentrates around low-cost solutions.The iterative procedure can approach a local or global optimum.
- Computational cost: Repeated sampling and evaluation can make CEM slow because the total number of evaluated samples becomes extensive.The runtime depends partly on the computational cost of the objective function.
- CEMMPC: In MPC, CEM optimizes an h-step action-sequence planning problem at every timestep, with the previous optimized mean shift-initializing the next distribution.Both µ_t and σ_t have shape d×h, where d is action-space dimensionality.
- CEMMPC: Momentum refitting smooths distribution updates between CEM iterations because a small elite set estimates many sampling-distribution parameters.The standard modification uses a momentum coefficient α.
- CEMMPC: CEMMPC uses truncated normal distributions to keep sampled actions within their bounds.The PETS variant instead uses truncation based on 2σ with σ adapted to the action bounds.
3 Improved CEM – iCEM
iCEM improves CEM for MPC by combining temporally correlated action sampling with reuse of information across iterations and time steps. These changes target coherent exploration and lower sampling inefficiency in high-dimensional trajectory optimization.
- Colored noise and correlations: Successful HUMANOID STANDUP action sequences are far from white noise, motivating colored search noise in CEM.The comparison uses action-sequence power spectra for different β values and successful iCEM sequences.
- Colored noise and correlations: Colored-noise actions produce more coherent trajectories and greater reachable distances than uncorrelated actions at the same variance.Increasing β strengthens low-frequency components and increases trajectory coherence.
- Colored noise and correlations: iCEM generates colored action sequences by transforming white noise in the frequency domain using an FFT-based implementation.The sampling function returns sequences with exponent β, zero mean, and unit variance.
- Memory and elite reuse: CEM discards optimized distributions and elite sets after each inner loop, wasting about ∼55000 actions per environment step in one reported setting.iCEM reuses this information through elite retention and shifted elites.
- Memory and elite reuse: Keep elites and shift elites reuse fractions of prior elite sets across iterations and environment steps, while retaining diversity with a fraction of 0.3.The full elite set is not shifted because it would sharply shrink variance during the next CEM iteration.
- MPC-specific modifications: The algorithm selects the first action from the best evaluated sequence, clips sampled actions to permitted bounds, and decays population size across iterations.These choices adapt CEM to MPC trajectory optimization and exploit shrinking variance near an optimum.
4 Experiments
Experiments evaluate iCEM on challenging high-dimensional locomotion and manipulation tasks under low-sampling budgets, using both ground-truth and learned dynamics models. iCEM remains effective at very low budgets, improves sample efficiency and performance over baselines, and supports near-real-time planning.
- Evaluation setup: The benchmark covers long-horizon locomotion and manipulation tasks with observation dimensions of 18–376 and action spaces up to 30 dimensions.Experiments use both MuJoCo ground-truth dynamics and learned latent-dynamics models in PlaNet.
- Evaluation setup: The experiments include HalfCheetah running, Humanoid Standup, Fetch Pick&Place, Door, Door with sparse reward, and Relocate environments.These tasks span locomotion, sparse-reward manipulation, and high-degree-of-freedom robotic control.
- Main results: iCEM is the only evaluated method that performs well at extremely low planning budgets and consistently exceeds the baselines across considered budgets.Figure 3 compares iCEM, CEMMPC, CEMPETS, and vanilla CEM as the total number of trajectories per step varies.
- Main results: 2.7–21.9× higher sample efficiency is achieved by iCEM, measured by the budget required to reach 90% of the best baseline performance.The comparison uses the respective best baseline in each environment and a reference budget of 4000.
- Main results: 120–1030% of the best baseline performance is obtained by iCEM on average for budgets below 1000 trajectories.The reported improvement is averaged over the specified low-budget interval.
- Learned dynamics models: With learned pixel-based dynamics, iCEM using budget 366 and three CEM iterations is not far behind extensive CEM using budget 10000 and ten iterations.At the same low budget, iCEM outperforms CEM on CHEETAH RUN and WALKER WALK and performs similarly on CUP CATCH.
- Runtime: iCEM reaches real-time planning with learned PlaNet models and close to real-time performance for simple ground-truth environments such as HALFCHEETAH.Runtime measurements are reported for different compute budgets using MuJoCo and PlaNet models.
- Ablation study: Ablations identify colored noise, keeping and shifting elites, and best-action execution as influential components, while combining all components is necessary for top performance.The effects of the additions become more relevant in the low-budget regime.
5 Conclusions
iCEM combines temporally correlated action sampling and memory to improve sample efficiency for real-time planning. The additions support difficult tasks with very few trajectories and enter the real-time regime in learned-model experiments.
- iCEM introduces temporally correlated action sampling and memory for previous trajectories.
- 45 trajectories per step were sufficient for humanoid stand-up and sparse-reward door-opening tasks.
- iCEM entered the real-time regime in experiments using learned dynamics models.
Supplementary Material
The supplementary material provides additional performance results, ablations, hyperparameter sensitivity analysis, and an analysis connecting time-correlated actions with their power spectrum.
- The supplement details iCEM performance with ground-truth and learned models and analyzes hyperparameter sensitivity.
- It reports ablation figures across all environments and three fixed budgets.
- It analyzes the relationship between time-correlated action sequences and their power spectrum.
A Pseudocode of the vanilla Cross Entropy Method (CEM) in the MPC setting.
The vanilla CEM pseudocode samples and iteratively refines action sequences, then executes the first action of the optimized mean sequence in the MPC loop.
- CEM uses N samples, an elite-set of size K, horizon h, and a specified number of CEM iterations.
- The algorithm initializes the standard deviation as a constant vector with value σinit.
- MPC executes the first action of the optimized mean sequence µt.
B Performance results
Supplementary performance results report cumulative reward and success rate across selected budgets and environments, with additional PlaNet experiments shown for three tasks.
- Ground-truth results use 50 independent runs, or 100 for FETCH PICK&PLACE.
- PlaNet results use three independent training runs with ten evaluation rollouts each.
- Table S3 reports cumulative reward and success rate for selected budgets across all environments.
- Figure S6 adds PlaNet experiments for REACHER EASY, FINGER SPIN, and CARTPOLE SWINGUP.
B.1 Budget selection
The optimizer uses budget-dependent internal settings, while iCEM adds colored noise and other mechanisms to make sampling more efficient across tasks. Colored-noise choices are linked to task frequency, with moderate β values generally adequate except for high-frequency control.
- Budget-dependent settings: More CEM iterations are possible under the same budget because iCEM uses a decay factor γ = 1.25.The number of iterations and initial trajectories N depend on the overall budget.
- iCEM parameters: iCEM adds the colored-noise exponent β, decay factor γ, and reused-elite fraction ξ to CEM's main parameters.The values of α, K, σinit, γ, and ξ are unified across the presented tasks.
- Task-dependent noise: Higher β is used for low-frequency control, whereas lower β is used for high-frequency control such as HALFCHEETAH RUNNING.Colored noise generates action sequences more specific to each task's intrinsic frequency.
- Task-dependent noise: Choosing β in the appropriate range avoids wasting energy on action sequences mismatched to the task's frequency structure.The HUMANOID STANDUP spectrum favors lower frequencies, motivating correlated noise rather than Gaussian actions.
- Task-dependent noise: For high-frequency tasks β should be low, while values around 2–4 are generally adequate otherwise.The passage states that precise β selection is not critical outside high-frequency control.
C.2 Sensitivity
Sensitivity depends strongly on the sampling budget and task: many parameters matter less with more trajectories, but β can remain decisive and iCEM is less sensitive to σinit. Temporal correlations also help exploit longer horizons under low budgets.
- Budget sensitivity: At very low budgets relevant to real-time planning, selecting the right parameters becomes more important than at higher budgets.With enough trajectories, sensitivity to other parameters is small; the comparison uses low- and higher-budget columns of the ablation figure.
- Colored-noise sensitivity: β can significantly affect performance even at higher budgets, depending on the task.High β is unsuitable for HALFCHEETAH RUNNING, while HUMANOID STANDUP requires β above 2 under budget 100.
- Initial-variance sensitivity: iCEM performs similarly for any σinit above 0.2 on FETCH PICK&PLACE, whereas CEM-MPC prefers σinit between 0.4 and 0.6.This indicates lower sensitivity to the initial sampling standard deviation for iCEM.
- Horizon sensitivity: iCEM better exploits longer HUMANOID STANDUP action sequences even at low budgets by generating samples with higher temporal correlations.The sensitivity analysis concerns the planning horizon h.
D Ablation results
Ablations show that component usefulness varies across environments, while the complete iCEM generally performs best. Adding the mean late avoids the degradation caused by adding it at every iteration, and correlated noise shapes exploration through action autocorrelation.
- Overall ablations: The complete iCEM version has the best overall performance, although some ablated variants perform slightly better in individual environments.The experiments use shared hyperparameters across environments, which can favor ablated variants in particular settings.
- Environment-specific effects: Different environments benefit from different components because HUMANOID STANDUP can get stuck sitting, whereas FETCH PICK&PLACE depends critically on initial exploration.The tasks pose distinct optimization challenges, including balance and sparse-reward exploration.
- Mean sampling: Adding the mean to samples helps high-dimensional tasks select clean action sequences and closes the gap with original CEM.The mean is useful for manipulation, object-reaching, and linear state-space trajectories.
- Mean sampling: Adding the mean only at the final iteration avoids the performance degradation caused by adding it at every CEM iteration.Adding it every iteration can narrow the variance too quickly; a surviving mean is shifted to the next time step.
- Correlated noise: The action autocorrelation function is obtained as the inverse Fourier transform of the control input's power spectral density.This relation connects the chosen noise spectrum to temporal correlations between actions.