Second-Order Smooth Planning with Optimal-Transport Bellman Smoothing

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 $\tilde{O}({\epsilon }^{-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 $\tilde{O}({\epsilon }^{-(2+2/(\beta -1))})$: the first-order case $\beta =2$ recovers SmoothCruiser, while a second-order/cubic remainder $\beta =3$ yields $\tilde{O}({\epsilon }^{-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 $\tilde{O}({\epsilon }^{-3})$ oracle complexity for fixed OT parameters, and we relate the OT, entropy-regularized, and unregularized objectives through explicit regularization-bias bounds.

Published at the International Conference on Machine Learning (ICML 2026)