PaperlayerView exact revision on arXiv

Source-linked AI summary

Higher-Order Approximation of Exit Functionals in Sampling-Based Stochastic Model Predictive Control

Sashank Modali, Takashi Tanaka

arXiv:2609.25257v2eess.SYcs.NAcs.ROcs.SYmath.NAmath.OC

TL;DR

Safety evaluation based on continuous-time exit events depends on accurate numerical approximations of exit times and indicators. The paper applies adaptive higher-order methods to safe stochastic control and derives conditions for transferring exit-time accuracy to failure indicators. Experiments show improved error behavior and constraint satisfaction relative to Euler–Maruyama.

Abstract

from arXiv · show

Safety evaluation in sampling-based stochastic model predictive control often requires numerical estimation of exit functionals. The approximation of first-exit times and exit indicators is therefore a key numerical bottleneck, and discretization error in these quantities directly affects the resulting controller. This paper studies how existing higher-order methods for strong approximation of exit times can be brought into safe control. Two cases are highlighted. For general noncommutative dynamics, an adaptive order-1 Milstein discretization is used together with L\'evy-area simulation via Wiktorsson's method. For commutative dynamics, an adaptive order-1.5 construction achieves a stronger exit-time rate. Under a local anti-concentration condition on the exit-time law, we show that strong exit-time approximation transfers to strong approximation of the failure indicator. The methods are then studied in the context of chance-constrained path integral control, which provides an exact continuous-time representation of safety through exit events. Numerical experiments compare the two cases in terms of strong exit-time error, failure-indicator error, and closed-loop constraint satisfaction, showing improvement over Euler-Maruyama and thereby enabling existing and future techniques whose applicability depends on improved strong approximation.

I. INTRODUCTION

Exit-event discretization is a bottleneck for safety evaluation because boundary crossing makes continuous-time indicators sensitive to mesh size. The paper brings higher-order exit-time methods into safe control and studies when their accuracy transfers to safety quantities.

I. INTRODUCTION

  • Chance-constrained path-integral control represents optimal failure probability exactly through exit-event indicators, whose numerical accuracy limits the safety guarantee.Discretizing continuous-time exit events can miss boundary crossings between mesh points.Source: §I · p. 1
  • Existing adaptive methods achieve exit-time rates O(h1−ξ) and O(h3/2−ξ), but the latter requires restrictive noise commutativity.The transfer of exit-time accuracy to control-relevant indicators and stopped costs, and convergence for noncommutative diffusions with Lévy areas, remain gaps.Source: §I · p. 1
  • The paper establishes a terminal boundary-layer condition for transferring exit-time and state approximation rates to failure indicators and relaxed stopped functionals.For noncommutative dynamics it uses adaptive order-1 Milstein with Wiktorsson Lévy areas; for commutative dynamics it uses an adaptive order-1.5 method.Source: §I · p. 1

A. Standing regularity conditions

  • The formulation uses a nominal feedback to define closed-loop drift and assumes smooth coefficients and uniform ellipticity near the safe set.The safe set has a smooth boundary and the drift and diffusion coefficients have C3 extensions to a neighborhood.Source: §II · p. 2, A. Standing regularity conditions · p. 2

B. Exit time and safety functional

Safety is represented by whether the controlled diffusion exits the prescribed safe set before the horizon. The paper formulates safety-constrained control through a trajectory-level safety functional and a multiplier-based stopped-cost problem.

B. Exit time and safety functional

  • The first exit time from the safe set defines failure, while the clipped exit time stops at the deterministic horizon T.The stopped state is evaluated at the clipped exit time.Source: B. Exit time and safety functional · p. 2

C. Safe stochastic optimal control

  • The safety-constrained problem bounds an expected trajectory-level safety functional, and a multiplier absorbs its penalty into augmented costs.For the survival event, the functional is failure probability minus the prescribed threshold.Source: C. Safe stochastic optimal control · p. 2
  • For each fixed multiplier, the inner problem is an unconstrained stopped-cost problem characterized by an exit-time Hamilton–Jacobi–Bellman equation.The minimizing feedback is assumed admissible, with closed-loop drift Lipschitz in state uniformly over time.Source: C. Safe stochastic optimal control · p. 2

D. Numerical approximation

The numerical scheme evaluates value, dual, and failure-probability quantities using sampled trajectories on an adaptive mesh. Its error analysis assumes strong exit-time and mesh-point state approximation, together with regularity conditions near the safe set and terminal horizon.

D. Numerical approximation

  • Discretized sampled trajectories on an adaptive mesh are used to evaluate the value function, dual function, and failure probability.The numerical exit time is defined from the mesh-based approximation.Source: D. Numerical approximation · p. 2

E. Assumptions

  • The analysis assumes strong exit-time error of order h^α, with α = 1−ξ for order 1 or α = 3/2−ξ for order 1.5 methods.It also assumes mesh-point strong state approximation with order γ = 1 or γ = 3/2, respectively.Source: E. Assumptions · pp. 2–3
  • The terminal tube estimate bounds the probability that the exact diffusion approaches the boundary near T and enables transfer of exit-time rates to indicator rates.It is stronger than a bound on exit-time probability near T because it controls path-level disagreement between exact and numerical indicators.Source: E. Assumptions · p. 3
  • Assumption A5 requires a classical HJB solution, an admissible minimizing feedback, Lipschitz closed-loop drift, and an optimal multiplier with complementary slackness.The augmented running cost is assumed bounded and regular, and the survival penalty has a bounded Lipschitz extension.Source: E. Assumptions · p. 3

III. DISCRETIZATION ERROR IN EXIT-EVENT ESTIMATION

The section relates strong exit-time and state approximation to errors in failure indicators and stopped costs. A terminal tube condition controls near-horizon boundary grazing, which is essential for the indicator transfer.

B. Clipped exit-time to indicator transfer

  • A small clipped exit-time error alone need not imply a small failure-indicator error, because near-horizon disagreements can misclassify safety.The terminal tube estimate controls how often the exact path grazes the boundary near T.Source: B. Clipped exit-time to indicator… · p. 3
  • Under Assumptions A1, A2, and A4, the indicator error is bounded using exit-time error, state error, and the terminal tube estimate.The transfer rate depends on the exit-time rate and terminal tube exponent β; when β ≥ α, optimizing the bound gives the order h^(αβ/(1+β)).Source: B. Clipped exit-time to indicator… · p. 3
  • When the terminal region is separated from the boundary, the indicator rate can recover the full exit-time rate as β increases.The passage identifies β = 1 with the bounded-density regime and β > 1 with stronger decay.Source: B. Clipped exit-time to indicator… · p. 3

C. Running-cost approximation

  • The stopped running-cost approximation error is bounded by C h^min(γ,α), combining exit-time and state approximation errors.For γ = 3/2, the running-cost update must match the order of the Itô–Taylor state update.Source: C. Running-cost approximation · p. 3

D. Reduction theorem for the relaxed stopped cost

The reduction theorem combines failure-indicator, survival-penalty, and running-cost approximation errors to bound the relaxed stopped-cost error. With order-matched state and running-cost rates, the indicator term dominates, and the resulting numerical cost error vanishes at rate O(h^κ).

D. Reduction theorem for the relaxed stopped cost

  • Theorem 2 bounds relaxed stopped-cost error by combining the failure-indicator, survival-penalty, and running-cost contributions under its assumptions and a truncated adaptive mesh.The indicator term is controlled by Theorem 1; the survival-term contribution is O(h^γ), and the running-cost bound is (23).Source: D. Reduction theorem for the relaxed… · p. 4
  • When state and running-cost rates are order-matched so min(γ, α) = α, the indicator term is dominant.This is the stated regime for the methods in Section IV.Source: D. Reduction theorem for the relaxed… · p. 4
  • In practice, replacing the exact relaxed stopped cost with its numerical counterpart incurs error that vanishes at rate O(h^κ).Improving the exit-time propagator (larger α) directly tightens the cost estimate and, through dual ascent, constraint satisfaction.Source: D. Reduction theorem for the relaxed… · p. 4

IV. HIGHER-ORDER ADAPTIVE METHODS

The higher-order method depends on whether the diffusion satisfies commutativity conditions: noncommutative dynamics use adaptive order-1 Milstein with approximated Lévy areas, while commutative dynamics permit order 1.5. The noncommutative method achieves exit-time rate O(h^(1−ξ)) and improves the failure-indicator rate over Euler–Maruyama.

IV. HIGHER-ORDER ADAPTIVE METHODS

  • If the diffusion commutativity conditions hold, adaptive order-1.5 is available and yields a stronger exit-time rate; otherwise, order-1 Milstein is the stated higher-order choice.The two cases are distinguished by the commutativity structure of the diffusion.Source: §IV · p. 4

A. Noncommutative adaptive order-1 Milstein with Lévy areas

  • When commutativity conditions are not imposed, adaptive order-1 Milstein with Wiktorsson approximations of off-diagonal iterated Itô integrals achieves exit-time rate O(h^(1−ξ)).The step size is selected adaptively from {h, h^2} based on boundary distance; Lévy-area truncation preserves the local L2 order.Source: A. Noncommutative adaptive order-1… · p. 4
  • For any β > 0, the order-1 method roughly doubles the failure-indicator exponent relative to Euler–Maruyama, and as β → ∞ its rate approaches 1 − ξ.The compared exponents are αβ/(1+β) and αβ/(2(1+β)).Source: A. Noncommutative adaptive order-1… · p. 4

B. Commutative adaptive order-1.5 method

Under the stated commutativity conditions, an adaptive order-1.5 method gives a stronger exit-time rate and avoids Lévy-area simulation. Its indicator and stopped-cost rates coincide; the paper then specializes the framework to chance-constrained path-integral control.

B. Commutative adaptive order-1.5 method

  • Under the commutativity conditions, adaptive order-1.5 achieves exit-time rate O(h^(3/2−ξ)) and improves the order-1 rate for any β without Lévy-area simulation.Its three-scale mesh is {h, h^2, h^3}, selected based on boundary distance.Source: B. Commutative adaptive order-1.5 method · p. 5
  • At β = 1, corresponding to bounded density, the failure-indicator rate is near 3/4, compared with Euler–Maruyama’s 1/4.The stopped-cost rates coincide with the indicator rates.Source: B. Commutative adaptive order-1.5 method · p. 5

V. STRONG APPROXIMATION IN CHANCE-CONSTRAINED PATH-INTEGRAL CONTROL

  • The paper next specializes the framework to control-affine dynamics with control-quadratic running cost.Source: §V · p. 5

A. Path-integral-solvable subclass

The path-integral-solvable subclass linearizes the HJB equation and represents the solution using uncontrolled-process expectations stopped at exit or the horizon. The section then bounds the error in the closed-loop failure probability estimated from numerical trajectories, under regularity and boundedness assumptions.

A. Path-integral-solvable subclass

  • The Cole–Hopf transform linearizes the HJB equation, and the Feynman–Kac representation expresses its solution as an expectation over the uncontrolled process stopped at exit or the horizon.The optimal control is recovered by differentiating that representation.Source: A. Path-integral-solvable subclass · p. 5
  • The specialization sets Γ1 = 1 and Γ2 = 0; the failure probability is estimated from the same sampled trajectories used for the control update.Under Assumption A5, strong duality and an optimal multiplier satisfying complementary slackness hold.Source: A. Path-integral-solvable subclass · p. 5

B. Approximation of the closed-loop failure probability

  • Under the stated assumptions, the numerical closed-loop failure probability differs from the exact probability by at most C h^κ.The bound requires bounded exact and numerical stopped costs, positive lower bounds on their exponential-weight expectations, and γ ≥ α.Source: B. Approximation of the closed-loop… · p. 5
  • The analysis assumes uniform ellipticity and a C4 boundary, while noting that practical systems may be hypoelliptic or have less regular boundaries.The paper tests whether predicted rate improvements persist in such practical settings.Source: B. Approximation of the closed-loop… · p. 5

C. Controller algorithm

The algorithm uses sampled rollouts to estimate costs and update the control and safety multiplier. Its two higher-order cases differ only in the propagator, with running-cost integration matched to its order.

C. Controller algorithm

  • The higher-order propagator is the only component that differs between the two cases, and running-cost integration is matched to its order.The algorithm uses the numerical relaxed stopped cost for each rollout.Source: C. Controller algorithm · p. 5
  • The controller initializes η, repeatedly generates K rollouts, computes numerical costs and exponential weights, and recovers a control update from weighted samples.The loop ends at convergence or a receding-horizon shift.Source: C. Controller algorithm · p. 5

VI. RESULTS

The experiments use two unicycle models and two safe-set designs to assess strong-error rates and closed-loop constraint satisfaction. The benchmark cases differ in whether their dynamics are noncommutative or commutative.

VI. RESULTS

  • Three experiments on a unicycle system assess strong-error rates in two offline benchmarks and closed-loop constraint satisfaction with CC-PIC.The offline cases verify rates from Theorems 1, 3–4.Source: §VI · p. 6

A. Benchmark models

  • Model A is a noncommutative unicycle, for which accurate strong approximation beyond order 0.5 requires Lévy-area simulation.Its state is planar position and heading, with driftless autonomous dynamics.Source: A. Benchmark models · p. 6
  • Model B lifts controls into actuator states, yielding commutative dynamics that permit the order-1.5 method without Lévy areas.The physical block is deterministic, and the lifted model has five state dimensions.Source: A. Benchmark models · p. 6
  • The offline cases use a disk with a circular obstacle, while the closed-loop case uses a rounded rectangle with two obstacles forming a narrow passage.A C4 approximation of the latter boundary is possible but not pursued.Source: A. Benchmark models · p. 6
  • Strong-error estimates use paired-path Monte Carlo with 20,000 samples sharing a Brownian path; 21.8% of Case A and 90.8% of Case B reference paths exit.The study compares EM and higher-order variants, including Wiktorsson-area and adaptive order-1.5 methods.Source: A. Benchmark models · p. 6

B. Case A: Noncommutative strong error

The adaptive higher-order methods improve strong exit-functional approximation over Euler–Maruyama and yield tighter closed-loop constraint satisfaction in the reported cases. The commutative order-1.5 method avoids Lévy-area simulation, while the noncommutative order-1 method uses it.

B. Case A: Noncommutative strong error

  • For the noncommutative model, HR-W’s fitted exit-time slope is 0.93 versus EM’s 0.48, and its indicator error is 0.92 versus EM’s 0.54.The exit-time slope approaches order 1.Source: B. Case A: Noncommutative strong error · p. 6

C. Case B: Commutative strong error

  • For the commutative model, HR-1.5’s fitted exit-time slope is 1.44, while EM and Mil both achieve approximately 0.96.The indicator error for HR-1.5 is reported as 9.13 and described as effectively vanishing at these step sizes.Source: C. Case B: Commutative strong error · p. 6

D. Case C: CC-PIC

  • At ∆ = 0.10 in the noncommutative closed loop, EM produces 13.4% violations while HR-W produces 10.5%, near the threshold.The reported converged multiplier is η* = 14.26.Source: Figure 2 · p. 6, D. Case C: CC-PIC · p. 7
  • At ∆ = 0.10 in the commutative closed loop, EM produces 13.0% violations while HR-1.5 produces exactly 10.0%.The reported converged multiplier is η* = 8.73.Source: D. Case C: CC-PIC · p. 7

E. Comparison of discretization methods

  • Adaptive methods improve over Euler–Maruyama in both studied cases and produce tighter constraint satisfaction than fixed-step counterparts with marginal total-cost-rate overhead.The commutative order-1.5 case has a half-order improvement without Lévy areas and requires β = 1; the noncommutative Milstein case requires β > 1.Source: E. Comparison of discretization methods · p. 7, §VII · p. 7

VII. CONCLUSION

  • The conclusion identifies state-dependent exit penalties, sharper exit-functional rates, and multilevel Monte Carlo estimation as open directions.Source: §VII · p. 7
Loading 2609.25257v2…