Full search page →

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

On this page

Supplementary notes · 3

  1. The ELBO and the reparameterization trick: training a latent state
  2. More of the JEPA line: I-JEPA, V-JEPA and V-JEPA 2.1
  3. The cross-entropy method: planning by sampling and refitting

Deep Learning for Computer Vision

  1. 02 · Deep Image Classification
View the whole course tree →

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 J(a)J(a) over an action sequence a=(a0,…,aH−1)a=(a_0,\dots,a_{H-1}), where JJ is computed by rolling the model forward from the current state. It keeps a Gaussian N(μ,diag⁡σ2)\mathcal N(\mu,\operatorname{diag}\sigma^2) over sequences and repeats four steps:

  1. sample NN sequences a(1),…,a(N)a^{(1)},\dots,a^{(N)} from the Gaussian (and clip them to the allowed action range);
  2. evaluate J(a(i))J(a^{(i)}) for each by a model rollout;
  3. keep the KK cheapest, the elites, forming the set E\mathcal E;
  4. refit: μ←1K∑a∈Ea\mu\leftarrow\frac1K\sum_{a\in\mathcal E}a and σ←std⁡E(a)\sigma\leftarrow\operatorname{std}_{\mathcal E}(a) (computed per time step).

Here HH is the horizon, NN the number of samples per round and K<NK\lt N 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 R N HR\,N\,H model steps per plan for RR rounds, with no gradients required, so JJ may be non-differentiable and all NN rollouts run in parallel. The chapter’s CPU experiment adds a floor of 0.050.05 to σ\sigma 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.669

The 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 0.570→0.2100.570\to0.210), so the best cost falls from 47.31447.314 to 34.08934.089. Random shooting with the same 320320 samples reaches only 46.67246.672, and doing nothing costs 78.75078.750. 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 HH. 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

  1. 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
  2. C. M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006, ch. 13 “Sequential Data”. book
  3. R. Szeliski, Computer Vision: Algorithms and Applications, 2nd ed., Springer, 2022. book
  4. R. S. Sutton, “Dyna, an integrated architecture for learning, planning, and reacting,” ACM SIGART Bulletin, vol. 2, no. 4, 1991. doi
  5. 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
  6. D. Ha and J. Schmidhuber, “Recurrent world models facilitate policy evolution,” NeurIPS, 2018; interactive version “World Models,” arXiv:1803.10122. paper interactive
  7. D. Hafner et al., “Learning latent dynamics for planning from pixels,” ICML, 2019. paper
  8. D. Hafner, T. Lillicrap, J. Ba and M. Norouzi, “Dream to control: learning behaviors by latent imagination,” ICLR, 2020. arXiv
  9. D. Hafner, T. Lillicrap, M. Norouzi and J. Ba, “Mastering Atari with discrete world models,” ICLR, 2021. arXiv
  10. D. Hafner, J. Pasukonis, J. Ba and T. Lillicrap, “Mastering diverse control tasks through world models,” Nature, vol. 640, 2025. doi arXiv
  11. N. Hansen, H. Su and X. Wang, “TD-MPC2: scalable, robust world models for continuous control,” ICLR, 2024. arXiv
  12. V. Micheli, E. Alonso and F. Fleuret, “Transformers are sample-efficient world models,” ICLR, 2023. arXiv
  13. E. Alonso et al., “Diffusion for world modeling: visual details matter in Atari,” NeurIPS, 2024. arXiv
  14. J. Schrittwieser et al., “Mastering Atari, Go, chess and shogi by planning with a learned model,” Nature, vol. 588, 2020. doi arXiv
  15. C. Finn, I. Goodfellow and S. Levine, “Unsupervised learning for physical interaction through video prediction,” NIPS, 2016. arXiv
  16. M. Babaeizadeh, C. Finn, D. Erhan, R. H. Campbell and S. Levine, “Stochastic variational video prediction,” arXiv:1710.11252, 2017. arXiv
  17. A. Hu et al., “GAIA-1: a generative world model for autonomous driving,” technical report, arXiv:2309.17080, 2023. arXiv
  18. S. Yang et al., “Learning interactive real-world simulators,” arXiv:2310.06114, 2023. arXiv
  19. J. Bruce et al., “Genie: generative interactive environments,” arXiv:2402.15391, 2024. arXiv
  20. Google DeepMind, “Genie 3: a new frontier for world models,” blog post, August 5, 2025. blog
  21. NVIDIA (N. Agarwal et al.), “Cosmos world foundation model platform for physical AI,” arXiv:2501.03575, 2025. arXiv
  22. S. Motamed, L. Culp, K. Swersky, P. Jaini and R. Geirhos, “Do generative video models understand physical principles?,” arXiv:2501.09038, 2025. arXiv
  23. B. Kang et al., “How far is video generation from world model: a physical law perspective,” ICML, 2025. arXiv
  24. M. Assran et al., “Self-supervised learning from images with a joint-embedding predictive architecture,” CVPR, 2023. doi arXiv
  25. A. Bardes et al., “Revisiting feature prediction for learning visual representations from video,” arXiv:2404.08471, 2024. arXiv
  26. M. Assran et al., “V-JEPA 2: self-supervised video models enable understanding, prediction and planning,” arXiv:2506.09985, 2025. arXiv
  27. L. Mur-Labadia et al., “V-JEPA 2.1: unlocking dense features in video self-supervised learning,” arXiv:2603.14482, 2026. arXiv
  28. 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
  29. K. Chua, R. Calandra, R. McAllister and S. Levine, “Deep reinforcement learning in a handful of trials using probabilistic dynamics models,” NeurIPS, 2018. arXiv
  30. M. Janner, J. Fu, M. Zhang and S. Levine, “When to trust your model: model-based policy optimization,” NeurIPS, 2019. arXiv
  31. Z. Zhu et al., “Is Sora a world simulator? A comprehensive survey on general world models and beyond,” arXiv:2405.03520, 2024. arXiv
  32. Y. Guan et al., “World models for autonomous driving: an initial survey,” arXiv:2403.02622, 2024. arXiv
  33. D. P. Kingma and M. Welling, “Auto-encoding variational Bayes,” International Conference on Learning Representations (ICLR), 2014; arXiv:1312.6114. arXiv
  34. D. J. Rezende, S. Mohamed and D. Wierstra, “Stochastic backpropagation and approximate inference in deep generative models,” ICML, 2014. paper
  35. R. Y. Rubinstein, “The cross-entropy method for combinatorial and continuous optimization,” Methodology and Computing in Applied Probability, vol. 1, no. 2, 1999. doi
  36. 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