The cross-entropy method: planning by sampling and refitting
Optional · supplementary note 3 of 3 for DLCV 13 · World Models: Video, Latent Dynamics and Planning. Nothing in the main text depends on it; citation numbers refer to the reference list at the bottom of this page.
Navigate: this page and this track: Navigate: this page and this track
Plain version. Throw 64 darts around a rough guess, see which 8 land closest to the bullseye, move your aim to the middle of those 8, tighten your spread, and throw again. After a few rounds the darts cluster near a good spot, and you never needed to know the slope of the board.
Precise version. The planner minimizes a cost over an action sequence , where is computed by rolling the model forward from the current state. It keeps a Gaussian over sequences and repeats four steps:
- sample sequences from the Gaussian (and clip them to the allowed action range);
- evaluate for each by a model rollout;
- keep the cheapest, the elites, forming the set ;
- refit: and (computed per time step).
Here is the horizon, the number of samples per round and the number of elites. Step 4 is the maximum-likelihood fit of the Gaussian to the elites, which is the choice that minimizes the cross-entropy between the elite samples and the Gaussian family; this is where the method gets its name. Rubinstein presented it as an optimizer for combinatorial and continuous problems built on Kullback–Leibler cross-entropy and importance sampling [35]; de Boer et al. give a tutorial that also covers rare-event simulation [36]. PETS used CEM-based planning inside MPC [29]. The cost is model steps per plan for rounds, with no gradients required, so may be non-differentiable and all rollouts run in parallel. The chapter’s CPU experiment adds a floor of to to stop the spread from collapsing too early (the snippet below does the same), and in MPC the mean is shifted by one step and reused as the starting guess at the next time step.
Code · Python · 29 lines
import numpy as np
rng = np.random.default_rng(0)
A = np.array([[1.0, 0.1], [0.0, 0.94]]) # known model: position, velocity
B = np.array([0.005, 0.1])
H, N, K = 15, 64, 8 # horizon, samples per round, elites
def cost(x0, U): # U: (N, H) action sequences -> (N,) costs
x = np.broadcast_to(x0, (len(U), 2)).copy()
c = np.zeros(len(U))
for t in range(H):
x = x @ A.T + U[:, t, None] * B
c += x[:, 0] ** 2 + 0.15 * x[:, 1] ** 2 + 0.02 * U[:, t] ** 2
return c + 20 * x[:, 0] ** 2
x0 = np.array([1.5, 0.0])
mean, std = np.zeros(H), np.ones(H)
for i in range(5):
U = np.clip(rng.normal(mean, std, (N, H)), -1, 1)
c = cost(x0, U)
elite = U[np.argsort(c)[:K]]
mean, std = elite.mean(axis=0), elite.std(axis=0) + 0.05 # refit to the elites
print(f"round {i}: best {c.min():.3f}, mean of elites {np.sort(c)[:K].mean():.3f}, "
f"mean std {std.mean():.3f}")
U = np.clip(rng.normal(0.0, 1.0, (5 * N, H)), -1, 1) # same budget, no refitting
print(f"random shooting, {5 * N} samples: best {cost(x0, U).min():.3f}")
print(f"zero actions: {cost(x0, np.zeros((1, H)))[0]:.3f}")
print(f"cost of the final mean sequence: {cost(x0, mean[None])[0]:.3f}")Output:
Code · 8 lines
round 0: best 47.314, mean of elites 53.939, mean std 0.570
round 1: best 42.572, mean of elites 45.558, mean std 0.408
round 2: best 37.952, mean of elites 39.610, mean std 0.325
round 3: best 35.143, mean of elites 37.146, mean std 0.231
round 4: best 34.089, mean of elites 35.691, mean std 0.210
random shooting, 320 samples: best 46.672
zero actions: 78.750
cost of the final mean sequence: 35.669The first round is plain random shooting. Each later round samples from a distribution that has moved toward the cheap region and narrowed (mean standard deviation ), so the best cost falls from to . Random shooting with the same samples reaches only , and doing nothing costs . These are numbers from this toy, not a benchmark.
When it fails. A single Gaussian covers one basin, so it can commit to the wrong one when the cost has several; too few samples or too small a spread stops it exploring; and the search space grows with the horizon . Most importantly, CEM optimizes the model’s cost with great energy, so it finds model errors as readily as good actions (see the section on uncertainty and exploitation).
References
- J. Ding et al., “Understanding world or predicting future? A comprehensive survey of world models,” ACM Computing Surveys, vol. 58, no. 3, 2025. doi arXiv
- C. M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006, ch. 13 “Sequential Data”. book
- R. Szeliski, Computer Vision: Algorithms and Applications, 2nd ed., Springer, 2022. book
- R. S. Sutton, “Dyna, an integrated architecture for learning, planning, and reacting,” ACM SIGART Bulletin, vol. 2, no. 4, 1991. doi
- T. M. Moerland, J. Broekens, A. Plaat and C. M. Jonker, “Model-based reinforcement learning: a survey,” Foundations and Trends in Machine Learning, vol. 16, no. 1, 2023. doi arXiv
- D. Ha and J. Schmidhuber, “Recurrent world models facilitate policy evolution,” NeurIPS, 2018; interactive version “World Models,” arXiv:1803.10122. paper interactive
- D. Hafner et al., “Learning latent dynamics for planning from pixels,” ICML, 2019. paper
- D. Hafner, T. Lillicrap, J. Ba and M. Norouzi, “Dream to control: learning behaviors by latent imagination,” ICLR, 2020. arXiv
- D. Hafner, T. Lillicrap, M. Norouzi and J. Ba, “Mastering Atari with discrete world models,” ICLR, 2021. arXiv
- D. Hafner, J. Pasukonis, J. Ba and T. Lillicrap, “Mastering diverse control tasks through world models,” Nature, vol. 640, 2025. doi arXiv
- N. Hansen, H. Su and X. Wang, “TD-MPC2: scalable, robust world models for continuous control,” ICLR, 2024. arXiv
- V. Micheli, E. Alonso and F. Fleuret, “Transformers are sample-efficient world models,” ICLR, 2023. arXiv
- E. Alonso et al., “Diffusion for world modeling: visual details matter in Atari,” NeurIPS, 2024. arXiv
- J. Schrittwieser et al., “Mastering Atari, Go, chess and shogi by planning with a learned model,” Nature, vol. 588, 2020. doi arXiv
- C. Finn, I. Goodfellow and S. Levine, “Unsupervised learning for physical interaction through video prediction,” NIPS, 2016. arXiv
- M. Babaeizadeh, C. Finn, D. Erhan, R. H. Campbell and S. Levine, “Stochastic variational video prediction,” arXiv:1710.11252, 2017. arXiv
- A. Hu et al., “GAIA-1: a generative world model for autonomous driving,” technical report, arXiv:2309.17080, 2023. arXiv
- S. Yang et al., “Learning interactive real-world simulators,” arXiv:2310.06114, 2023. arXiv
- J. Bruce et al., “Genie: generative interactive environments,” arXiv:2402.15391, 2024. arXiv
- Google DeepMind, “Genie 3: a new frontier for world models,” blog post, August 5, 2025. blog
- NVIDIA (N. Agarwal et al.), “Cosmos world foundation model platform for physical AI,” arXiv:2501.03575, 2025. arXiv
- S. Motamed, L. Culp, K. Swersky, P. Jaini and R. Geirhos, “Do generative video models understand physical principles?,” arXiv:2501.09038, 2025. arXiv
- B. Kang et al., “How far is video generation from world model: a physical law perspective,” ICML, 2025. arXiv
- M. Assran et al., “Self-supervised learning from images with a joint-embedding predictive architecture,” CVPR, 2023. doi arXiv
- A. Bardes et al., “Revisiting feature prediction for learning visual representations from video,” arXiv:2404.08471, 2024. arXiv
- M. Assran et al., “V-JEPA 2: self-supervised video models enable understanding, prediction and planning,” arXiv:2506.09985, 2025. arXiv
- L. Mur-Labadia et al., “V-JEPA 2.1: unlocking dense features in video self-supervised learning,” arXiv:2603.14482, 2026. arXiv
- G. Zhou, H. Pan, Y. LeCun and L. Pinto, “DINO-WM: world models on pre-trained visual features enable zero-shot planning,” arXiv:2411.04983, 2024. arXiv
- K. Chua, R. Calandra, R. McAllister and S. Levine, “Deep reinforcement learning in a handful of trials using probabilistic dynamics models,” NeurIPS, 2018. arXiv
- M. Janner, J. Fu, M. Zhang and S. Levine, “When to trust your model: model-based policy optimization,” NeurIPS, 2019. arXiv
- Z. Zhu et al., “Is Sora a world simulator? A comprehensive survey on general world models and beyond,” arXiv:2405.03520, 2024. arXiv
- Y. Guan et al., “World models for autonomous driving: an initial survey,” arXiv:2403.02622, 2024. arXiv
- D. P. Kingma and M. Welling, “Auto-encoding variational Bayes,” International Conference on Learning Representations (ICLR), 2014; arXiv:1312.6114. arXiv
- D. J. Rezende, S. Mohamed and D. Wierstra, “Stochastic backpropagation and approximate inference in deep generative models,” ICML, 2014. paper
- R. Y. Rubinstein, “The cross-entropy method for combinatorial and continuous optimization,” Methodology and Computing in Applied Probability, vol. 1, no. 2, 1999. doi
- P.-T. de Boer, D. P. Kroese, S. Mannor and R. Y. Rubinstein, “A tutorial on the cross-entropy method,” Annals of Operations Research, vol. 134, no. 1, 2005. doi