Second-Order Smooth Planning with Optimal-Transport Bellman Smoothing

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, while 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.

Imagine you're standing at a decision point - a position in a game, a state of a simulation - and you want to know how good it is, or what the best move is. You have a simulator you can poke: feed it a state and an action, and it spits back a reward and a next state. Each poke costs something. The central question is: *how many pokes do you need* to estimate the value of where you're standing, accurately, without having to map out the entire universe of possible futures? A 2019 method called SmoothCruiser answered this with a clever idea. The "true" rule for valuing a state is to take the *best* action - but a hard maximum is jumpy: a tiny estimation error can flip which action looks best. So you *smooth* it (using entropy regularization), turning the sharp max into a soft, differentiable version. Smoothness lets you build a cheap local approximation and estimate corrections by sampling just one action. This gets you a guarantee that's independent of how big the problem is: roughly **$\epsilon^{-4}$** simulator calls to reach accuracy $\epsilon$. SmoothCruiser uses only a *first-order* (straight-line) local approximation. The leftover error from that approximation is quadratic, and *that* leftover is exactly what locks the cost at the exponent 4. Dam's paper shows this is a general principle: **the cost of planning is governed by how curved your smoothing is** - specifically, by the order β of the local Taylor remainder. The complexity follows a clean formula, $\epsilon^{−(2 + 2/(β−1))}$. First-order ($\beta$=2) reproduces the old $\epsilon^{-4}$. A genuine *second-order* approximation ($\beta=3$) drops it to **$\epsilon^{-3}$** - a real improvement. To get the second-order behavior, you need a smoothing that is extra-smooth in a precise sense (a "Lipschitz Hessian," meaning its curvature doesn't change too abruptly). They build one using **optimal transport** - the mathematics of moving mass from one distribution to another at minimal cost. Where entropy treats every action as an unrelated label, optimal transport lets a cost matrix encode *which actions are similar or interchangeable*, baking geometry into the smoothing. Two nice facts make it practical: (1) when the cost is zero, it collapses exactly back to the familiar entropy method, so it's a strict generalization; and (2) it has a clean closed form, so you don't have to solve an expensive transport problem at every state. The second-order correction term *looks* like it would require computing a full matrix of second derivatives (a Hessian) at every step - expensive and unpleasant. The paper shows this term is secretly just a **variance**, and a variance can be estimated by a simple cross-product of two independent noisy samples. So the whole second-order correction is recovered by drawing a *constant* handful of extra actions - no Hessian, no per-state transport solve. That's what keeps the improved ε⁻³ method genuinely cheap rather than improved-on-paper-only. Beyond the worst-case result, the paper adapts these ideas to the "best-action identification" setting, where you only care about picking the right move at the root. There, it recovers the optimal gap-dependent scaling (you spend less effort when the best action is clearly best), and combines the second-order estimator with confidence-interval elimination to get instance-dependent guarantees. Regularizers in planning are usually chosen for exploration or robustness — this paper argues they should *also* be chosen for **curvature**, because the smoothness of your smoothing directly controls how statistically efficient your planning can be. Optimal transport gives a concrete, computable way to buy that extra curvature and turn a quadratic leftover into a cubic one, cutting the worst-case cost from $\epsilon^{-4}$ to $\epsilon^{-3}$.