mlsanityData to 14 Oct 2026

Second-Order Smooth Planning with Optimal-Transport Bellman Smoothing

arXiv 2609.06484 ↗First posted 6 Sep 2026cs.LG cs.AIcited by 1

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 13 of its 26 references that are in the map. First posted on arXiv 6 Sep 2026.

Builds on

13 of 26 references.

References · 13

  1. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  2. 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,316
  3. 2018Computational Optimal Transportcited by 780
  4. 2017Reinforcement Learning with Deep Energy-Based Policiescited by 669
  5. 2019A Theory of Regularized Markov Decision Processescited by 286
  6. 2016Stochastic Optimization for Large-scale Optimal Transportcited by 189
  7. 2017A unified view of entropy-regularized Markov decision processescited by 182
  8. 2020Planning in Markov Decision Processes with Gap-Dependent Sample Complexitycited by 34
  9. 2014Bandit Algorithms for Tree Searchcited by 25
  10. 2017Monte-Carlo Tree Search by Best Arm Identificationcited by 13
  11. 2026Blazing the trails before beating the path: Sample-efficient Monte-Carlo planningcited by 5
  12. 2025Efficient Learning for Entropy-Regularized Markov Decision Processes via Multilevel Monte Carlocited by 3
1 more
  1. 2026Planning in entropy-regularized Markov decision processes and gamescited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Graph-Based Stochastic Power-UCT: Monte-Carlo Graph Search with Power Mean Estimationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework
  2. 2024Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs
  3. 2026Mean-Field Diffuser: Scaling Offline MARL to Thousands of Agents
  4. 2026Retimed Bellman Flows: Escaping the Impossible Triangle of Velocity Bootstrapping
  5. 2026P3: Persistent Particle Planning for Constrained Diffusion Control
  6. 2026End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions
  7. 2023On the Sample Complexity of Imitation Learning for Smoothed Model Predictive Control
  8. 2024Optimally Solving Simultaneous-Move Dec-POMDPs: The Sequential Central Planning Approach