文章背景与核心概要
本文介绍了在 ICML 2026 上发表的由 Tuan Dam 所著的全新规划算法 SecondOrderSmoothCruiser。该研究表明，平滑生成式规划的样本复杂度指数由局部泰勒余项的阶数 \(\beta\) 决定。通过采用基于最优输运平滑的贝尔曼备份，算法成功将 SmoothCruiser 一阶 \(\widetilde O(\varepsilon^{-4})\) 的复杂度改进到了二阶 \(\widetilde O(\varepsilon^{-3})\) 的预言机复杂度。
这一突破通过在动作分布上引入具有闭式解、策略梯度以及 Lipschitz 海森矩阵的最优输运平滑贝尔曼备份实现，其二次修正项允许使用无偏的交叉积估计器。本文通过显式的正则化偏差界，将最优输运、熵正则化以及未正则化的目标函数联系起来，为高效规划提供了重要的理论和算法支持。
Second-Order Smooth Planning with Optimal-Transport Bellman Smoothing
Summary
本文介绍了 SecondOrderSmoothCruiser，这是一种由 Tuan Dam 在 ICML 2026 上发表的新型规划算法。该研究表明，平滑生成式规划的样本复杂度指数由局部泰勒余项的阶数 \(\beta\) 决定，通过使用最优输运平滑的贝尔曼备份，将 SmoothCruiser 的一阶 \(\widetilde O(\varepsilon^{-4})\) 复杂度提升至二阶 \(\widetilde O(\varepsilon^{-3})\) 的预言机（oracle）复杂度。
Summary
This paper introduces SecondOrderSmoothCruiser, a novel planning algorithm published at ICML 2026 by Tuan Dam. The research demonstrates that the sample-complexity exponent of smooth generative planning is governed by the order \(\beta\) of the local Taylor remainder, improving from the first-order \(\widetilde O(\varepsilon^{-4})\) complexity of SmoothCruiser down to a second-order \(\widetilde O(\varepsilon^{-3})\) oracle complexity using an optimal-transport-smoothed Bellman backup.
Paper Metadata
| Field | Details |
|---|---|
| Title | Second-Order Smooth Planning with Optimal-Transport Bellman Smoothing |
| Author | Tuan Dam |
| Submitted | September 6, 2026 |
| Conference | International Conference on Machine Learning (ICML 2026) |
| Primary Subject | Machine Learning (cs.LG), Artificial Intelligence (cs.AI) |
| Identifiers | arXiv:2609.06484 [cs.LG] / DOI: 10.48550/arXiv.2609.06484 |
| License | Creative Commons Attribution 4.0 International  |
Paper Metadata
Field Details Title Second-Order Smooth Planning with Optimal-Transport Bellman Smoothing Author Tuan Dam Submitted September 6, 2026 Conference International Conference on Machine Learning (ICML 2026) Primary Subject Machine Learning ( cs.LG), Artificial Intelligence (cs.AI)Identifiers arXiv:2609.06484 [cs.LG] / DOI: 10.48550/arXiv.2609.06484 License Creative Commons Attribution 4.0 International
Abstract
使用生成模型的规划旨在通过尽可能少的模拟器调用来估计状态的价值。SmoothCruiser 通过利用熵正则化贝尔曼备份的平滑性，实现了与问题无关的复杂度 \(\widetilde O(\varepsilon^{-4})\)，但其估计器仅为一阶。
我们证明了 SmoothCruiser 类规划器的样本复杂度指数由局部泰勒余项的阶数 \(\beta\) 决定，从而得出预言机复杂度 \(\widetilde O(\varepsilon^{-(2+2/(\beta-1))})\)： * 一阶情况（\(\beta = 2\)）可恢复 SmoothCruiser 的结果。 * 二阶/三次余项（\(\beta = 3\)）可产生 \(\widetilde O(\varepsilon^{-3})\) 的复杂度。
我们通过在动作分布上采用最优输运平滑的贝尔曼备份达到了这一收敛区间，该备份具有闭式解、策略梯度以及 Lipschitz 海森矩阵，其二次修正项支持无偏交叉积估计器。由此产生的 SecondOrderSmoothCruiser 在固定最优输运参数的情况下实现了 \(\widetilde O(\varepsilon^{-3})\) 的预言机复杂度，并且我们通过显式的正则化偏差界将最优输运、熵正则化以及未正则化的目标函数联系在了一起。
Abstract
Planning with a generative model aims to estimate the value of a state using as few simulator calls as possible. SmoothCruiser achieves problem-independent complexity \(\widetilde O(\varepsilon^{-4})\) by exploiting the smoothness of the entropy-regularized Bellman backup, but its estimator is only first-order.
We show that the sample-complexity exponent of SmoothCruiser-type planners is governed by the order \(\beta\) of the local Taylor remainder, giving oracle complexity \(\widetilde O(\varepsilon^{-(2+2/(\beta-1))})\): * The first-order case (\(\beta = 2\)) recovers SmoothCruiser. * A second-order/cubic remainder (\(\beta = 3\)) yields \(\widetilde O(\varepsilon^{-3})\).
We reach this regime with an optimal-transport-smoothed Bellman backup over action distributions, which has a closed form, a policy gradient, and a Lipschitz Hessian, and whose quadratic correction admits an unbiased cross-product estimator. The resulting SecondOrderSmoothCruiser achieves \(\widetilde O(\varepsilon^{-3})\) oracle complexity for fixed OT parameters, and we relate the OT, entropy-regularized, and unregularized objectives through explicit regularization-bias bounds.
Links & Full-Text Access
Links & Full-Text Access