交叉熵方法:用取樣與重新擬合來規劃
選讀・DLCV 13・世界模型:影片、潛在動態與規劃 的補充資料(第 3/3 則)。主線不依賴這則補充;引用編號對應本頁底部的參考文獻。
導覽:本頁與本系列: 導覽:本頁與本系列
白話版。 在一個粗略的猜測附近丟 64 支飛鏢,看哪 8 支最靠近靶心,把瞄準點移到這 8 支的中央,縮小散布範圍,再丟一次。幾輪之後飛鏢就會集中在一個不錯的位置,而你從頭到尾都不需要知道靶面的斜率。
精確版。 規劃器要在動作序列 上最小化成本 ,其中 是從目前狀態出發、用模型向前推演算出來的。它維護序列上的一個高斯分布 ,並重複四個步驟:
- 從高斯分布取樣 條序列 (並裁切到允許的動作範圍);
- 對每一條用模型推演計算 ;
- 保留成本最低的 條,即菁英(elites),組成集合 ;
- 重新擬合:,(逐時間步計算)。
這裡 是視野長度, 是每一輪的樣本數, 是菁英數。第 4 步是把高斯分布以最大概似法擬合到菁英上,這個選擇會最小化菁英樣本與高斯分布族之間的交叉熵,方法的名稱也由此而來。Rubinstein 把它發展成針對組合與連續問題的最佳化方法,建立在 Kullback–Leibler 交叉熵與重要性取樣(importance sampling)之上 [35];de Boer 等人寫了一篇導論,也涵蓋罕見事件模擬 [36]。PETS 在 MPC 中使用了以 CEM 為基礎的規劃 [29]。若跑 輪,每次規劃的成本是 個模型步,而且不需要梯度,所以 可以不可微, 條推演也能平行執行。本章的 CPU 實驗在 上加了 的下限,避免分散度太早塌縮(下面的程式碼也這樣做);在 MPC 中,則會把平均向前移一步,當作下一個時間步的起始猜測。
程式碼 · Python · 29 行
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}")輸出:
程式碼 · 8 行
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第一輪就是單純的隨機射擊(random shooting)。之後每一輪都從一個已經移向低成本區域、並且變窄的分布取樣(平均標準差 ),所以最佳成本從 降到 。用同樣 個樣本做隨機射擊只能達到 ,什麼都不做則要 。這些數字來自這個玩具例子,不是基準測試結果。
何時會失敗。 單一高斯分布只涵蓋一個盆地,當成本有多個盆地時,它可能鎖定錯的那一個;樣本太少或散布太小,會讓它無法探索;搜尋空間也會隨視野 增大。最重要的是,CEM 會非常賣力地最佳化模型的成本,所以找到模型錯誤和找到好動作一樣容易(見「規劃、不確定性與模型被利用」一節)。
參考文獻
- 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