Second-Order Smooth Planning with Optimal-Transport Bellman Smoothing

Tuan Dam

cs.LGSep 6, 2026

Second-Order Smooth Planning with Optimal-Transport Bellman Smoothing

Authors: Tuan Dam

Organizations: Hanoi University of Science and Technology, Hanoi, Vietnam

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 $β$ of the local Taylor remainder, giving oracle complexity $\widetilde O(\varepsilon^{-(2+2/(β-1))})$ : the first-order case $β=2$ recovers SmoothCruiser, while a second-order/cubic remainder $β=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.

Figures & tables

Algorithm	Setting	Bellman aggregator	Local Taylor remainder	Cascade calls	Total oracle calls (worst-case)
Sparse Sampling (SSA) ( Kearns et al., 2002 )	value-based	hard $\max$	(non-smooth)	–	non-polynomial in $1/\varepsilon$
SmoothCruiser ( Grill et al., 2019 )	value-based	LogSumExp	quadratic: $O(\lVert\Delta Q\rVert_{2}^{2})$	$\tilde{\mathcal{O}}(\varepsilon^{-2})$	$\tilde{\mathcal{O}}(\varepsilon^{-4})$
SecondOrderSmoothCruiser (ours)	value-based	OT-smoothed / LogSumExp	cubic: $O(\lVert\Delta Q\rVert_{2}^{3})$	$\tilde{\mathcal{O}}(\varepsilon^{-1})$	$\tilde{\mathcal{O}}(\varepsilon^{-3})$

Table 1: Planning with a generative model: comparison of guarantees in the fixed-confidence, value-based setting.

Component	Technical ingredient	Planning consequence	Pointer
Curvature–complexity theory	Taylor remainder of order $\beta$ for $F_{s}$ , nonnegative gradient (policy) and Monte Carlo estimation of $Q_{s}$ , leading to general cascade exponent $\alpha_{\beta}=2/(\beta-1)$ and total exponent $2+2/(\beta-1)$ .	Unifies SmoothCruiser, our OT method, and potential higher-order variants in a single analytical template.	Section 4
OT-smoothed Bellman operator	Define $F^{\mathrm{OT}}_{s}(Q)=\max_{\pi\in\Delta(\mathcal{A})}\{\langle\pi,Q\rangle-\tau W_{\lambda}(\pi,\bm{\mu}_{s})\}$ ; derive closed form as $\bm{\mu}_{s}$ -mixture of LogSumExp ; prove Lipschitz Hessian $M=\mathcal{O}(1/(\tau^{2}\lambda^{2}))$ .	Provides a concrete $\beta=3$ aggregator with explicit derivatives and controllable curvature; gradient is a policy and couplings induce geometry.	Section 5
SecondOrderSmoothCruiser	Quadratic term identity and cross-product debiasing yield a one-sample estimator of the second-order term without estimating full $\delta Q_{s}$ .	Improves worst-case exponent from $4$ to $3$ while keeping problem-independence and state-space agnosticism.	Sections 6 and 7
OT-GapCruiser (gap-dependent)	Combines SecondOrderSmoothCruiser at the root with UGapE-style confidence intervals and elimination across actions.	Instance-dependent, fixed-confidence guarantees depending on root gaps $\Delta_{1}(s_{0},a)$ , extending gap-dependent planning (e.g. MDP-GapE) to regularized, higher-order planning.	Section 9

Table 2: Contributions of our framework relative to SmoothCruiser.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
$\mathcal{A}$	Finite action set; $K=\|\mathcal{A}\|$ .
$s$	State.
$Q\in\mathbb{R}^{K}$	Vector of action scores.
$\hat{Q}_{s}$	Taylor expansion point.
$\Delta=Q_{s}-\hat{Q}_{s}$	Taylor error direction.
$C\in\mathbb{R}^{K\times K}$	Action-cost matrix; $C_{\cdot j}$ is its $j$ th column.

Appendix

Table 3

Model-Based Planning

Model-Based Planning uses explicit or learned models of how actions change states to simulate futures, compare plans, and choose actions.

See all 208 papers

Planning in entropy-regularized Markov decision processes and games
Apr 21, 2026Jean-Bastien Grill, Omar Darwiche Domingues, Pierre Ménard +2Value Function Estimation Markov Models
DeepMind Paris · SequeL team, Inria Lille
Blazing the trails before beating the path: Sample-efficient Monte-Carlo planning
Apr 16, 2026Jean-Bastien Grill, Michal Valko, Rémi MunosMarkov Decision Processes Markov Models
SequeL team, INRIA Lille - Nord Europe, France · Google DeepMind, UK∗
Scale-free adaptive planning for deterministic dynamics & discounted rewards
Apr 20, 2026Peter L. Bartlett, Victor Gabillon, Jennifer Healey +1Markov Decision Processes Model-Based Planning
University of California, Berkeley, USA · Noah’s Ark Lab, Huawei Technologies, London, UK · Adobe Research, San Jose, USA +1

Apr 21, 2026J/K move · Enter open · S save

Planning in entropy-regularized Markov decision processes and games

Jean-Bastien Grill, Omar Darwiche Domingues, Pierre Ménard, Rémi Munos+1

DeepMind Paris · SequeL team, Inria Lille

Value Function Estimation Markov Models Maximum Entropy RL Model-Based Planning Sample-Efficient RL Regularized RL

Open paper AskPDF arXiv

We propose SmoothCruiser, a new planning algorithm for estimating the value function in entropy-regularized Markov decision processes and two-player games, given a generative model of the environment. SmoothCruiser makes use of the smoothness of the Bellman operator promoted by the regularization to achieve problem-independent sample complexity of order O~(1/epsilon^4) for a desired accuracy epsilon, whereas for non-regularized settings there are no known algorithms with guaranteed polynomial sample complexity in the worst case.

Abstract

Model-Based Planning

Explore similar work

Planning in entropy-regularized Markov decision processes and games

Blazing the trails before beating the path: Sample-efficient Monte-Carlo planning

Scale-free adaptive planning for deterministic dynamics & discounted rewards