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 O(ε−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 O(ε−(2+2/(β−1))): the first-order case β=2 recovers SmoothCruiser, while a second-order/cubic remainder β=3 yields O(ε−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 O(ε−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/ε
SmoothCruiser ( Grill et al., 2019 )
value-based
LogSumExp
quadratic: O(∥ΔQ∥22)
O~(ε−2)
O~(ε−4)
SecondOrderSmoothCruiser (ours)
value-based
OT-smoothed / LogSumExp
cubic: O(∥ΔQ∥23)
O~(ε−1)
O~(ε−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 β for Fs , nonnegative gradient (policy) and Monte Carlo estimation of Qs , leading to general cascade exponent αβ=2/(β−1) and total exponent 2+2/(β−1) .
Unifies SmoothCruiser, our OT method, and potential higher-order variants in a single analytical template.
Section 4
OT-smoothed Bellman operator
Define FsOT(Q)=maxπ∈Δ(A){⟨π,Q⟩−τWλ(π,μs)} ; derive closed form as μs -mixture of LogSumExp ; prove Lipschitz Hessian M=O(1/(τ2λ2)) .
Provides a concrete β=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 δQs .
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 Δ1(s0,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.
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.
Jean-Bastien Grill, Omar Darwiche Domingues, Pierre Ménard +2
You are a robot and you live in a Markov decision process (MDP) with a finite or an infinite number of transitions from state-action to next states. You got brains and so you plan before you act. Luckily, your roboparents equipped you with a generative model to do some Monte-Carlo planning. The world is waiting for you and you have no time to waste. You want your planning to be efficient. Sample-efficient. Indeed, you want to exploit the possible structure of the MDP by exploring only a subset of states reachable by following near-optimal policies. You want guarantees on sample complexity that depend on a measure of the quantity of near-optimal states. You want something, that is an extension of Monte-Carlo sampling (for estimating an expectation) to problems that alternate maximization (over actions) and expectation (over next states). But you do not want to StOP with exponential running time, you want something simple to implement and computationally efficient. You want it all and you want it now. You want TrailBlazer.
Jean-Bastien Grill, Michal Valko, Rémi Munos
SequeL team, INRIA Lille - Nord Europe, France · Google DeepMind, UK∗
We address the problem of planning in an environment with deterministic dynamics and stochastic rewards with discounted returns. The optimal value function is not known, nor are the rewards bounded. We propose Platypoos, a simple scale-free planning algorithm that adapts to the unknown scale and smoothness of the reward function. We provide a sample complexity analysis for Platypoos that improves upon prior work and holds simultaneously over a broad range of discount factors and reward scales, without the algorithm knowing them. We also establish a matching lower bound showing our analysis is optimal up to constants.
Peter L. Bartlett, Victor Gabillon, Jennifer Healey +1
University of California, Berkeley, USA · Noah’s Ark Lab, Huawei Technologies, London, UK · Adobe Research, San Jose, USA +1