PaperlayerView exact revision on arXiv

Source-linked AI summary

Second-Order Smooth Planning with Optimal-Transport Bellman Smoothing

Tuan Dam

arXiv:2609.06484v1cs.LGcs.AI

TL;DR

Generative-model planning seeks accurate root-state values with few simulator calls, but first-order SmoothCruiser has ˜O(ε^-4) complexity. The paper characterizes complexity through Taylor-remainder order and introduces OT-smoothed Bellman backups with estimable second-order corrections. For fixed OT parameters, SecondOrderSmoothCruiser achieves ˜O(ε^-3), while unregularized transfer remains a regularization-bias tradeoff.

  • Problem

    First-order smooth Bellman planning reaches ˜O(ε^-4), motivating whether higher-order local approximations can improve the oracle-complexity exponent.

  • Method

    The paper introduces an optimal-transport-smoothed Bellman backup with a closed form, gradient policy, Lipschitz Hessian, and unbiased cross-product estimation of its quadratic correction.

  • Results

    ˜O(ε^-3) oracle complexity is obtained by SecondOrderSmoothCruiser for finite action sets and fixed OT parameters.

  • Takeaways & Limitations

    The order of the local Taylor remainder governs the recursive planning exponent, with the second-order/cubic regime improving the first-order case.

  • Takeaways & Limitations

    The unregularized transfer is a regularization-bias tradeoff rather than a parameter-free ˜O(ε^-3) theorem, and gap-dependent extensions assume exact bound propagation in finite-support or tabular settings.

Abstract

from arXiv · show

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.

1. Introduction

Planning with a generative model asks how to estimate a root state's value using few simulator calls. The paper links oracle complexity to local Taylor-remainder order and introduces OT smoothing to obtain a second-order regime.

  • Motivation: Generative-model planning targets the value or best action at a current root state without scaling guarantees with the number of states.The setting is simulation-based control, games, and online decision making, where a simulator returns reward samples and next states.
  • Smooth Bellman backups: Entropy regularization smooths the hard maximum, while SmoothCruiser uses a first-order Taylor model whose quadratic remainder yields ˜O(ε^-4) complexity.The smooth backup also provides a policy for sampling actions, but the first-order remainder determines the exponent.
  • Curvature controls complexity: ˜O(ε^-(2+2/(β-1))) is the curvature–complexity law: β=2 recovers ˜O(ε^-4), whereas β=3 yields ˜O(ε^-3).Here β denotes the order of the local approximation error in the Q-estimation error.
  • Optimal-transport smoothing: The OT-smoothed backup operates over action distributions using an entropically regularized transport cost and an action-cost matrix that encodes action geometry.It reduces to entropy regularization when C≡0 and retains a closed form, gradient policy, and Lipschitz Hessian.
  • Results and scope: SECONDORDERSMOOTHCRUISER achieves ˜O(ε^-3) worst-case oracle complexity for finite action sets and fixed (τ,λ), improving the first-order ˜O(ε^-4) result.The theorem concerns the regularized objective; transferring to unregularized planning introduces a regularization-bias tradeoff with parameter-dependent constants.
  • Optimal-transport smoothing: A variance/cross-product identity estimates the quadratic Taylor correction without explicitly forming the Hessian or solving an OT problem at every state.The estimator uses a constant number of additional sampled actions.
  • Extensions: OT-GapE and OT-GapCruiser extend the framework to gap-dependent planning, including (∆∨ε)^-2 root-gap dependence and curvature-controlled instance-dependent bounds.These extensions propagate confidence bounds through a smooth Bellman aggregator or combine the second-order planner with root elimination.

2. Related Work

The paper situates its contribution among generative-model planning methods, SmoothCruiser’s smooth-backup guarantees, multilevel variance reduction, and gap-dependent action-identification analyses.

  • Classical Sparse Sampling and MCTS methods can have non-polynomial or exponential worst-case sample complexity in generative-model planning.
  • SmoothCruiser achieves ˜O(ε−4) value-estimation complexity by exploiting entropy-regularized Bellman smoothness, while non-regularized max/min operators lack polynomial worst-case bounds.
  • Multilevel Monte Carlo reduces variance in entropy-regularized MDPs, whereas this framework modifies the local backup with an estimable second-order OT correction.
  • Gap-dependent methods study fixed-confidence action identification, and OT-GapCruiser and OT-GapE extend this analysis to regularized higher-order SmoothCruiser planning.
  • The paper studies how a specific regularizer shapes Bellman curvature and planning complexity, connecting regularized MDP theory with computational optimal transport.

3. Background: Regularized Bellman Operators and SmoothCruiser

The background contrasts the non-smooth hard maximum with entropy-regularized smooth backups and explains how SmoothCruiser uses first-order sampling to obtain its ˜O(ε−4) guarantee.

  • A generative model returns reward and next-state samples for a queried state-action pair in a discounted finite-action MDP.
  • The LogSumExp Bellman operator replaces the hard maximum with a smooth backup whose gradient is a Boltzmann policy.
  • SmoothCruiser estimates a coarse Q function and uses a first-order Taylor expansion, sampling one action according to the backup gradient.
  • ˜O(ε−4) oracle calls result because the quadratic Taylor remainder requires Θ(√ε) Q-estimation accuracy, producing a recursive cascade.

4. Curvature-Driven Planning: General Theory

The general theory links planning complexity to the order of the local Taylor remainder and identifies β = 3 as the first higher-order regime improving SmoothCruiser’s exponent.

  • A curvature model requires a simplex-valued policy gradient and controls the local Taylor remainder around a reference Q estimate.
  • The Taylor correction is estimated unbiasedly; for β = 2 it is the gradient-policy sample, while for β = 3 it is estimated through a variance identity.
  • The required tolerance schedule makes the Taylor remainder O(ε) by controlling the distance between Q and its reference estimate.
  • ˜O(ε^−(2+2/(β−1))) oracle complexity follows from the curvature-driven recursion under bounded-variance Taylor-term estimators.
  • β = 2 yields exponent 4, whereas β = 3 yields exponent 3, turning higher-order smoothness into a quantitative planning advantage.

5. OT-Smoothed Bellman Aggregators over Actions

The paper introduces an entropically regularized OT backup over action distributions, derives its closed form and derivatives, and shows that its Lipschitz Hessian supplies the β = 3 regime.

  • Definition and setup: The OT-smoothed aggregator regularizes action distributions using an entropic transport cost induced by an action-cost matrix and a full-support reference distribution.
  • Reference distribution: The reference distribution affects constants and practical variance, while the worst-case exponent is unchanged when full support is maintained.
  • Closed form and derivatives: The OT maximization has a closed form based on columnwise softmax probabilities, with a known Q-independent offset for normalized comparison.
  • Closed form and derivatives: The OT gradient lies in the action simplex and can serve as a policy, while the construction provides explicit gradient and Hessian formulas.
  • Relation to other backups: The normalized OT backup admits an explicit transfer bound, and setting C ≡ 0 recovers entropy regularization with η = τλ.
  • Relation to other backups: The ˜O(ε−3) theorem assumes fixed smoothing parameters; transferring to the unregularized objective requires tracking ε-dependent constants and is treated as a bias tradeoff.
  • Lipschitz Hessian: A Lipschitz Hessian gives β = 3 and c3 = M/6, making the OT operator an explicit higher-order instance of the curvature theory.

6. Second-Order SmoothCruiser with OT-Smoothed Aggregators

This section develops a second-order SmoothCruiser estimator using OT-smoothed structure and an unbiased sampled quadratic correction. It also specifies value bounds, clipping, and tolerance control for the recursive routines.

  • Quadratic correction: The quadratic Taylor term is represented through a variance identity involving a reference distribution and conditionally sampled actions.The construction uses J sampled from μ_s and A, A′ independently sampled from the local softmax distribution at the reference point.
  • Quadratic correction: Independent unbiased estimates of the Taylor direction enable an unbiased cross-product estimator for the quadratic correction.The direction is Q_s − Q̂_s; independent oracle and recursive calls provide its estimates, and the cross-product identity debiases the quadratic term.
  • Estimator design: The resulting routines mirror SmoothCruiser while replacing first-order corrections with second-order corrections and OT-induced sampling.The estimator samples actions from distributions associated with the OT structure and adds the estimated quadratic term to the linear component.
  • Estimator design: A known value bound B supports clipping all intermediate estimates to the interval [0, B].The section gives B through the reward and regularizer bounds and applies clipping throughout the estimation procedure.
  • Estimator design: The value-estimation routine samples rewards and next states, recursively estimates successor values, forms action-value estimates, and clips them before returning.For each action, oracle samples are combined with discounted recursive estimates, then averaged and clipped.
  • Error control: The tolerance schedule is chosen so the Taylor remainder is at most ε, while the oracle sample remains explicit in the estimator.The quadratic term is debiased through the stated correction identity rather than formed from an exact Taylor direction.

7. Complexity Analysis for SecondOrderSmoothCruiser

The complexity analysis combines local Taylor-remainder control, recursive bias management, and the second-order correction to establish the estimator’s worst-case guarantee. The result is an oracle-complexity theorem, while local arithmetic can remain substantial.

  • Worst-case guarantee: The unconditional bias is O(ε) after distributing failure probabilities across recursive calls and applying clipping.This complements the high-probability recursive analysis used in the theorem.
  • Worst-case guarantee: Under the stated assumptions, SecondOrderSmoothCruiser returns an ε-accurate value estimate with probability at least 1 − δ.The theorem’s oracle-call bound has constants depending on K, γ, λ, τ, μ_min, and ||C||∞.
  • Estimator construction: The fine regime uses a second-order Taylor correction after coarse estimation of Q̂_s and computation of OT-induced distributions.The estimator samples actions for the linear and quadratic terms and combines them with the OT backup and correction components.
  • Estimator construction: The quadratic estimator uses independent sampled actions and recursive oracle calls to implement the debiased correction.The algorithm forms the cross-product correction from independently estimated differences and adds it to the linear term.
  • Oracle complexity versus local computation: The formal complexity measure counts generative-model calls, not local arithmetic or repeated Sinkhorn iterations.The closed form avoids Sinkhorn iterations, but dense cost matrices still require O(K^2) arithmetic per visited state.
  • Oracle complexity versus local computation: The theorem therefore establishes an oracle-complexity result rather than immediate large-scale computational superiority.The quadratic correction uses only a constant number of additional sampled actions and recursive calls, while finite-action arithmetic overhead remains.

8. OT-GapE: Matching ε−2 via Confidence-Bound Trajectory Planning

OT-GapE combines time-uniform confidence bounds with monotone smooth Bellman aggregation to identify an ε-optimal root action. Its analysis matches the bandit-optimal ε−2 dependence under the stated exact-recursion assumptions.

  • Confidence-bound trajectories: OT-GapE maintains optimistic and pessimistic value bounds by recursively propagating reward and transition confidence sets through a monotone smooth aggregator.The construction applies backward recursions over a finite-horizon episodic MDP with bounded rewards.
  • Smooth exploration: The algorithm samples non-root actions using a smooth optimistic policy defined by the aggregator’s gradient.For LogSumExp this is a Boltzmann policy, while for F_OT it is the OT-induced policy; a mixture can retain greedy optimistic behavior.
  • Root identification: At the root, best-guess and challenger actions are compared, and the algorithm stops when the optimistic gap is at most ε.This follows the MDP-GapE-style fixed-confidence selection principle.
  • Guarantee: The correctness proof uses a simultaneous high-probability confidence event, backward induction, and the root stopping rule.The resulting procedure returns an ε-optimal root action with probability at least 1 − δ.
  • Guarantee: The instance-dependent sample complexity has ε and gap dependence matching the bandit-optimal exponent 2.The theorem states this result under uniformly valid confidence bounds and exact computation of the optimistic and pessimistic recursions.
  • Smooth exploration: The gradient policy aligns exploration with the regularized Bellman operator, concentrating on optimistic actions while retaining smoothness.For OT smoothing, the resulting policy is geometry-aware through the action-cost matrix.

9. Gap-Dependent Extensions

The paper extends the second-order estimator to gap-dependent root-action selection. These extensions use confidence intervals and variance-reduced estimates, yielding an instance-dependent exponent below SmoothCruiser’s worst-case exponent under stated assumptions.

  • Scope: The gap-dependent extensions combine the OT-smoothed second-order estimator with confidence-gap ideas when root action gaps are favorable.They are presented as extensions beyond the main worst-case result rather than as prerequisites for Theorem 7.2.
  • Algorithm: OT-GapCruiser maintains confidence intervals for root action values and selects actions using a UGapE-style comparison of plausible best and competing actions.Each selected action receives a root-centered SecondOrderSmoothCruiser estimate before the intervals are updated.
  • Algorithm: The algorithm updates intervals with self-normalized concentration and stops when the best action’s upper bound is within ε of every challenger’s lower bound.This stopping condition directly targets ε-optimal root-action identification.
  • Guarantee: Under standard sub-Gaussian noise conditions, OT-GapCruiser returns an ε-optimal root action with probability at least 1 − δ.The corresponding sample-complexity statement is given in Theorem 9.1.
  • Guarantee: The instance-dependent exponent lies strictly below SmoothCruiser’s worst-case exponent 4, with β = 3 giving p approximately 3 in the stated regime.The precise exponent and constants depend on accuracy scheduling and variance bounds.

10. Discussion and Limitations

The paper frames second-order smooth planning as a curvature-driven improvement over SmoothCruiser, while limiting its main guarantees to fixed smoothing parameters and finite-action oracle complexity. It also identifies approximation and scalability boundaries for extensions and unregularized transfer.

  • Curvature-driven planning: The order of the local Taylor remainder controls recursive planning complexity: β = 2 gives exponent 4, whereas β = 3 gives exponent 3.The second-order regime is realized by the OT-smoothed Bellman operator.
  • OT smoothing: The OT operator has a closed form, gradient policy, Lipschitz Hessian, and variance identity for estimating the quadratic correction without explicitly forming the Hessian.At C ≡0 it reduces to the entropy-regularized LogSumExp backup; nonzero C incorporates action geometry.
  • Scope and bias: The guarantees primarily cover finite action sets with fixed smoothing parameters and provide an exact entropy-regularized connection through C ≡0.The unregularized connection is treated separately as a regularization-bias tradeoff.
  • Scope and bias: The unregularized transfer is not claimed to yield a parameter-free eO(ε^-3) theorem because choosing smoothing parameters as functions of ε changes hidden constants.The relevant constants include the Lipschitz-Hessian contribution.
  • Extensions and limitations: Gap-dependent OT-GapE and OT-GapCruiser extensions rely on exact confidence-bound propagation that is appropriate for finite-support or tabular settings.Continuous or very large state spaces would require approximation, and practical large-scale implementations remain future work.

A.2. Proof of Theorem 4.3

The proof derives a general curvature–complexity recurrence for SmoothCruiser-type planners by linking Taylor accuracy to recursive Monte Carlo estimation. Solving the recurrence yields the exponent 2/(β−1), with outer concentration adding the canonical ε^-2 factor.

  • Complexity measures: The analysis counts recursive value calls and generative-model oracle calls separately, with nβ(ε, δ) denoting total oracle calls of the high-probability planner.Cβ(ε) counts the full recursive value-estimation subtree from one SAMPLEβ call.
  • Tolerance and recursion: To make the Taylor remainder O(ε), the planner estimates Qs to a tolerance proportional to ε^(1/β), so bounded-sample averaging costs ε^(-2/β) per action.Each Q estimate uses recursive calls on next states at the same curvature-driven accuracy scale.
  • Tolerance and recursion: Each Monte Carlo one-step return triggers one recursive value call, producing a recurrence whose tolerance map raises ε to the power 1/β.The Taylor-term estimators add only constant-order cost under the bounded-variance assumption.
  • Recurrence solution: Solving the recurrence gives recursion exponent αβ = 2/(β−1), up to polylogarithmic factors.The tolerance sequence reaches a constant after O(log log(1/ε)) levels, leaving only polylogarithmic overhead.
  • Final complexity: The outer high-probability aggregation contributes ε^-2, yielding total complexity eO(ε^-(2+2/(β−1))).For β = 2 this recovers eO(ε^-4), while β = 3 gives eO(ε^-3).

B.4. Proof of Lemma 5.6

The lemma proves that the OT-smoothed Bellman backup has a globally Lipschitz Hessian, establishing the cubic Taylor remainder needed for the second-order planning regime. The proof combines softmax covariance bounds with Lipschitz bounds on the induced probabilities and policy.

  • Probability representation: The OT backup is analyzed through columnwise softmax probabilities and their mixture under the reference distribution.The action-cost matrix enters these probabilities through the OT Gibbs kernel.
  • Derivative bounds: A uniform covariance bound yields a global Jacobian bound for each columnwise probability map.The resulting bounds control how the softmax distributions change with Q.
  • Derivative bounds: The probability maps and gradient policy are Lipschitz in Q, allowing their differences to bound the Hessian difference.The proof uses convex-mixture structure and rank-one operator-norm bounds.
  • Lipschitz Hessian: The Hessian is globally Lipschitz with a constant scaling as O(1/(τ^2λ^2)) times polynomial factors in K and reference-distribution parameters.This establishes the curvature constant required by the second-order Taylor analysis.
  • Cubic remainder: A Lipschitz Hessian implies a cubic Taylor remainder bounded by a constant times ∥Q−Qhat∥_2^3.This is the β = 3 condition used by the complexity theorem.

D.2. Proof of Theorem 7.2

The theorem proves correctness and eO(ε^-3) oracle complexity for SecondOrderSmoothCruiser by combining cubic OT curvature with recursive value estimation and outer concentration. The analysis tracks bounded outputs, recursive bias, and a cascade recurrence whose solution scales as ε^-1 before the final ε^-2 factor.

  • Correctness: SecondOrderSmoothCruiser returns an estimate within ε of V(s) with probability at least 1−δ.The proof combines the value-estimation accuracy event with recursive failure-probability bookkeeping.
  • Cascade recurrence: The fine-regime cascade uses Θ(ρ(η)^-2) current-state samples, with each sample triggering a recursive call at tolerance ρ(η)/√γ.Since ρ(η) = Θ(η^(1/3)), the dominant per-level factor is η^-2/3.
  • Cascade recurrence: Solving the cascade recurrence gives T(η) = eO(η^-1) oracle calls for a single SAMPLEV2 execution.The tolerance sequence reaches a constant in O(log log(1/η)) levels, contributing polylogarithmic overhead.
  • Final complexity: The full planner uses at most eO(ε^-3) oracle calls, with constants depending on fixed action, discount, and OT parameters.The outer Q estimation contributes ε^-2, while the recursive call contributes the ε^-1 cascade.
Loading 2609.06484v1…