CCS Concepts
• Computing methodologies → Motion path planning; • Theory of computation → Stochastic control and optimization ; • Computer systems organization → Robotic control .
Introduction
Motion planning has become a central problem in robotics, enabling autonomous systems to operate safely in complex environments while avoiding obstacles. Applications span domains such as autonomous driving, aerial navigation, and robotic surgery. In this context, sampling-based algorithms have emerged as particularly successful approaches [7 ] , where samples from the state and control spaces are used to efficiently construct search trees and compute collision-free trajectories. However, real-world robotic systems are often subject to uncertainty arising from process and measurement noise, external disturbances, and imperfect knowledge of the system dynamics. Unfortunately, existing approaches either rely on linear-Gaussian assumptions to obtain tractable safety guarantees or accommodate more general uncertainty at the expense of formal correctness guarantees [3 , 8 , 20 , 30 , 31 , 34 , 37 ] . This work aims to bridge this gap by developing a motion planning framework for uncertain systems that provides both correctness and completeness guarantees.
Among approaches that seek formal safety guarantees under uncertain disturbances, two broad directions have emerged. The first assumes that disturbances have bounded support, reducing safety checks to a worst-case reachability problem [9 , 40 ] . While effective in some settings, these methods often become overly conservative when the support of the uncertainty is large. A second direction relies on distributionally robust optimization (DRO) [32 ] , constructing sets of plausible probability distributions, referred to as ambiguity sets, and evaluating worst-case probabilities over these sets [18 , 19 , 29 , 35 , 36 ] . Yet, most existing DRO-based approaches are limited to linear or locally linearized systems, can be overly conservative, and either require a predefined ambiguity set or face challenges in learning sufficiently tight ambiguity sets from data. To address these limitations, we show how recent advances in Wasserstein-based distribution learning [13 , 14 ] and nonlinear uncertainty propagation [12 ] can be combined to enable safe motion planning for nonlinear stochastic systems with unknown disturbance distributions.
In this paper, we propose Learn-To-Propagate Distributionally-Robust Forest (L2P-DR-Forest) , a novel and computationally efficient motion-planning algorithm that combines DRO, sampling-based planning, and nonlinear uncertainty propagation to handle stochastic systems with unknown initial state and disturbance distributions. Leveraging recent results in optimal transport, our approach estimates a compact ambiguity set centered around a discrete distribution that is guaranteed, with high probability, to contain the true underlying system distributions. Critically, Wasserstein ambiguity sets admit a highly tractable propagation rule through Lipschitz continuous dynamics, with their radii expanding at most linearly with the Lipschitz constant of the dynamics. Consequently, these sets can be efficiently propagated while preserving computable bounds errs? on distributional uncertainty, avoiding the need for relearning at every propagation step. This property enables rapid exploration of the planning tree and substantially reduces the computational burden associated with exhaustive sampling. Combined with existing DRO results [15 ] , this allows us to synthesize motion plans that carry formal collision-avoidance guarantees despite underlying distributional uncertainty.
L2P-DR-Forest grows a forest of trees in stages. Each new tree is rooted at a node of an existing tree, and the ambiguity set at this root is re-learned from samples rolled out through the controller leading to that node. Thus, the planner propagates ambiguity sets cheaply within each tree and re-learns tight ones only at the selected restart nodes. We prove that the algorithm is correct, i.e., any controller it returns solves the planning problem with the prescribed confidence, and probabilistically complete , i.e., if a control sequence is robustly feasible with some margin and the noise is sub-Gaussian, then, run for an unbounded number of stages with growing sample sizes, it returns a controller with probability one. We evaluate L2P-DR-Forest on a range of nonlinear robotics benchmarks. Our experiments demonstrate that the proposed approach achieves high task-success rates while enforcing safe controllers. In contrast, comparable methods that do not provide formal safety guarantees exhibit substantially lower reliability.
In summary, our main contributions are:
A novel distributionally robust sampling-based motion planning algorithm, L2P-DR-Forest , which, to the best of our knowledge, is the first motion planner that provides formal, high-confidence safety guarantees for nonlinear systems with unknown distributions.
An extension of data-driven distributionally robust algorithms to learn distributions with unbounded support from data, which is critical to formally reduce the uncertainty in our motion planner over forest expansion.
A formal proof that L2P-DR-Forest is correct and probabilistically complete .
An empirical evaluation including a neural model of a tractor trailer showing that our approach substantially outperforms comparable methods both in terms of success rate and planning time.
Related Works. Motion planning under uncertainty is commonly posed as a chance-constrained problem [3 , 8 , 24 , 30 , 31 ] , where the probability of unsafety (e.g., collision) must satisfy a given upper bound at every time step. There are two inherent challenges in such problems: (i) uncertainty propagation through the dynamics, and (ii) bounding the probability of unsafety. Most of the existing approaches assume linear or linearized dynamics and Gaussian uncertainty to obtain tractable probability bounds or approximations. Extensions to non-Gaussian uncertainty use moment-based bounds [22 , 37 ] , which provide formal guarantees under restrictive assumptions, such as access to the relevant moments and their dynamics. Even when these assumptions hold, such methods can be overly conservative or computationally expensive.
For nonlinear systems, a common alternative is to assess safety statistically from sampled rollouts. This accommodates general dynamics and noise distributions, but naive Monte Carlo estimation can require many samples to resolve small collision probabilities, motivating variance-reduction techniques [21 ] . Sampling also underperforms model predictive control methods such as MPPI [39 ] , whose original formulation does not provide finite-sample probabilistic safety certificates. Among sampling-based planners, ϵ \epsilon ϵ -RandUP-RRT [28 , 40 ] , which we use as a baseline in Section 5, checks collision avoidance using ϵ \epsilon ϵ -padded convex hulls of propagated particles. The finite-sample guarantees of its underlying reachable-set estimator depend on bounds on quantities such as Lipschitz constants, packing numbers, and sampling coverage, which can be difficult to obtain tightly in practice.
To mitigate these issues, scenario-based planning [10 ] has been introduced. It provides distribution-free, finite-sample guarantees from i.i.d. samples drawn from the true uncertainty distribution. These methods have been applied to nonlinear model predictive control and motion planning among uncertain obstacles, but they assume the robot dynamics are deterministic. These guarantees extend to nonconvex decision problems, although certification requires suitable feasibility conditions and bounds on the number of supporting scenarios. In contrast, in this work, we focus on offline, sampling-based planning for nonlinear systems with unknown disturbance distributions, with probabilistic safety guarantees derived from finite data.
Distributionally robust optimization addresses uncertainty about the underlying probability law by optimizing against the worst-case distribution within a set of plausible distributions, called an ambiguity set. In motion planning, ambiguity sets have been defined through means and covariances for linear systems with additive process noise [36 ] , and as Wasserstein balls centered on empirical distributions constructed from samples of obstacle motion within model predictive control [19 ] . Closely related work [18 ] learns Wasserstein ambiguity tubes from trajectory data under unknown disturbance distributions and incorporates them into a probabilistically complete sampling-based planner. Its construction exploits linear or feedback-linearizable dynamics to decouple uncertainty propagation from nominal planning, allowing the ambiguity tube to be learned offline and reused during search. In contrast, we propagate learned ambiguity sets through nonlinear Lipschitz continuous dynamics and re-learn them during search, using a forest of trees to mitigate growth in their radii.
Preliminaries
Notation. For a vector x ∈ R d \mathbf{x} \in\mathbb{R}^{d} x ∈ R d , we denote by x ( i ) x^{(i)} x ( i ) its i i i -th element. For a set X ⊆ R d \mathcal{X} \subseteq\mathbb{R}^{d} X ⊆ R d , the indicator function for X \mathcal{X} X is denoted as 1 X ( x ) : = 1 \mathbf{1}_{\mathcal{X}}(x) := 1 1 X ( x ) := 1 if x ∈ X x \in\mathcal{X} x ∈ X ; otherwise 0 0 0 . We represent the set of indexes { 1 , … , M } \{1,\ldots,M\} { 1 , … , M } by [ M ] [M] [ M ] . Given a Borel measurable set X ⊆ R d \mathcal{X} \subseteq\mathbb{R}^{d} X ⊆ R d , we denote by B ( X ) \mathcal{B}(\mathcal{X}) B ( X ) the Borel sigma algebra over X \mathcal{X} X and by P ( X ) \mathcal{P}(\mathcal{X}) P ( X ) the set of probability distributions on X \mathcal{X} X . The symbol ⊗ \otimes ⊗ is used to represent the product measure between two distributions. The restriction of a distribution P ∈ P ( X ) \mathbb{P} \in\mathcal{P}(\mathcal{X}) P ∈ P ( X ) to the subspace X c ⊆ X \mathcal{X}_{c} \subseteq\mathcal{X} X c ⊆ X is denoted by P ∣ X c \mathbb{P}|_{\mathcal{X}_{c}} P ∣ X c and defined as P ∣ X c ( A ) = P ( A ∩ X c ) / P ( X c ) \mathbb{P}|_{\mathcal{X}_{c}}(A) = \mathbb{P}(A \cap\mathcal{X}_{c})/\mathbb{P}(\mathcal{X}_{c}) P ∣ X c ( A ) = P ( A ∩ X c ) / P ( X c ) for all A ∈ B ( X ) A \in\mathcal{B}(\mathcal{X}) A ∈ B ( X ) . For a probability distribution P ∈ P ( X ) \mathbb{P} \in\mathcal{P}(\mathcal{X}) P ∈ P ( X ) and a measurable function g : X → Y ⊆ R q g : \mathcal{X} \to\mathcal{Y} \subseteq\mathbb{R}^{q} g : X → Y ⊆ R q , we denote the push-forward measure of P \mathbb{P} P by g g g as g # P g_{\#}\mathbb{P} g # P such that for all A ∈ B ( Y ) A \in\mathcal{B}(\mathcal{Y}) A ∈ B ( Y ) , ( g # P ) ( A ) = P ( g − 1 ( A ) ) (g_{\#}\mathbb{P})(A) = \mathbb{P}(g^{-1}(A)) ( g # P ) ( A ) = P ( g − 1 ( A )) . We note that g # P g_{\#}\mathbb{P} g # P is still a probability distribution such that g # P ∈ P ( Y ) g_{\#}\mathbb{P} \in\mathcal{P}(\mathcal{Y}) g # P ∈ P ( Y ) .
Wasserstein distance. We start by recalling the definition of the Wasserstein distance and Wasserstein ambiguity set , which we use to model distributional uncertainty in our framework. Let ρ ≥ 1 \rho\ge1 ρ ≥ 1 , X ⊆ R d \mathcal{X} \subseteq\mathbb{R}^{d} X ⊆ R d , and define P ρ ( X ) \mathcal{P}_{\rho}(\mathcal{X}) P ρ ( X ) as the set of probability distributions with finite ρ \rho ρ -th moment, i.e., all P ∈ P ( X ) \mathbb{P} \in\mathcal{P}(\mathcal{X}) P ∈ P ( X ) such that ∫ X ∥ x ∥ ρ d P ( x ) < ∞ \int_{\mathcal{X}} \|x\|^{\rho} \mathrm{d}\mathbb{P}(x) < \infty ∫ X ∥ x ∥ ρ d P ( x ) < ∞ , where ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ is any fixed norm on R d \mathbb{R}^{d} R d .
Definition 1 (ρ \rho ρ -Wasserstein distance). For distributions P , Q ∈ P ρ ( X ) \mathbb{P},\mathbb{Q} \in\mathcal{P}_{\rho}(\mathcal{X}) P , Q ∈ P ρ ( X ) , the ρ \rho ρ -Wasserstein distance between P \mathbb{P} P and Q \mathbb{Q} Q is defined as
W ρ ( P , Q ) : = ( inf γ ∈ Γ ( P , Q ) ∫ X × X ∥ x − y ∥ ρ d γ ( x , y ) ) 1 ρ (1) W_{\rho}(\mathbb{P},\mathbb{Q}) := \left(\inf_{\gamma\in\Gamma(\mathbb{P},\mathbb{Q})} \int_{\mathcal{X}\times\mathcal{X}} \|x-y\|^{\rho} \mathrm{d}\gamma(x,y)\right)^{\frac{1}{\rho}} \tag*{(1)} W ρ ( P , Q ) := ( γ ∈ Γ ( P , Q ) inf ∫ X × X ∥ x − y ∥ ρ d γ ( x , y ) ) ρ 1 (1)
where Γ ( P , Q ) ⊂ P ρ ( X × X ) \Gamma(\mathbb{P},\mathbb{Q}) \subset\mathcal{P}_{\rho}(\mathcal{X}\times\mathcal{X}) Γ ( P , Q ) ⊂ P ρ ( X × X ) represents the set of joint probability distributions with given marginals P \mathbb{P} P and Q \mathbb{Q} Q (also known as couplings between P \mathbb{P} P and Q \mathbb{Q} Q ), i.e., for all γ ∈ Γ ( P , Q ) \gamma\in\Gamma(\mathbb{P},\mathbb{Q}) γ ∈ Γ ( P , Q ) , it holds that γ ( A × X ) = P ( A ) \gamma(A \times\mathcal{X}) = \mathbb{P}(A) γ ( A × X ) = P ( A ) , γ ( X × A ) = Q ( A ) \gamma(\mathcal{X} \times A) = \mathbb{Q}(A) γ ( X × A ) = Q ( A ) for all sets A ∈ B ( X ) A \in\mathcal{B}(\mathcal{X}) A ∈ B ( X ) .
Additionally, we define the ρ \rho ρ -Wasserstein ambiguity set (ball) of radius ϵ ≥ 0 \epsilon\ge0 ϵ ≥ 0 centered at the probability distribution P ∈ P ρ ( X ) \mathbb{P} \in\mathcal{P}_{\rho}(\mathcal{X}) P ∈ P ρ ( X ) as:
B ϵ ( P ) : = { Q ∈ P ρ ( X ) : W ρ ( P , Q ) ≤ ϵ } . (2) \mathcal{B}_{\epsilon}(\mathbb{P}) := \left\{\mathbb{Q} \in\mathcal{P}_{\rho}(\mathcal{X}) : W_{\rho}(\mathbb{P},\mathbb{Q}) \le\epsilon\right\}. \tag*{(2)} B ϵ ( P ) := { Q ∈ P ρ ( X ) : W ρ ( P , Q ) ≤ ϵ } . (2)
That is, B ϵ ( P ) \mathcal{B}_{\epsilon}(\mathbb{P}) B ϵ ( P ) contains all the probability distributions within ϵ \epsilon ϵ distance of P \mathbb{P} P according to W ρ W_{\rho} W ρ .
Problem Formulation
We consider a robot with motion uncertainty, whose state evolution is described by the stochastic process
x k + 1 = f ( x k , u k , ω k ) , x 0 ∼ P 0 , ω k ∼ P ω , (3) x_{k+1} = f(x_k,u_k,\omega_k), \qquad x_0 \sim\mathbb{P}_0,\qquad\omega_k \sim\mathbb{P}_{\omega}, \tag*{(3)} x k + 1 = f ( x k , u k , ω k ) , x 0 ∼ P 0 , ω k ∼ P ω , (3)
where x k ∈ X ⊂ R d x_k \in\mathcal{X} \subset\mathbb{R}^{d} x k ∈ X ⊂ R d is the state, u k ∈ U ⊂ R q u_k \in\mathcal{U} \subset\mathbb{R}^{q} u k ∈ U ⊂ R q is the control action, and ω k ∈ W ⊆ R w \omega_k \in\mathcal{W} \subseteq\mathbb{R}^{w} ω k ∈ W ⊆ R w is the process noise at time step k k k . Both X \mathcal{X} X and U \mathcal{U} U are assumed to be bounded sets. Vector field f : X × U × W → X f:\mathcal{X}\times\mathcal{U}\times\mathcal{W}\to\mathcal{X} f : X × U × W → X is a (possibly nonlinear) function, jointly Lipschitz continuous w.r.t. ( x , u , ω ) (x,u,\omega) ( x , u , ω ) . The initial state x 0 x_0 x 0 of the robot is uncertain and distributed according to P 0 \mathbb{P}_0 P 0 . In this paper, we make the following assumption about P 0 \mathbb{P}_0 P 0 and noise distribution P ω \mathbb{P}_{\omega} P ω .
Assumption 1. We assume that, for any k ≥ 0 k \ge0 k ≥ 0 , ω k ∼ P ω \omega_k \sim\mathbb{P}_{\omega} ω k ∼ P ω are i.i.d. and independent from x 0 ∼ P 0 x_0 \sim\mathbb{P}_0 x 0 ∼ P 0 , with P 0 ∈ P ρ ( X ) \mathbb{P}_0 \in\mathcal{P}_{\rho}(\mathcal{X}) P 0 ∈ P ρ ( X ) and P ω ∈ P ρ ( W ) \mathbb{P}_{\omega} \in\mathcal{P}_{\rho}(\mathcal{W}) P ω ∈ P ρ ( W ) being unknown, but with finite ρ \rho ρ -moments. Furthermore, we assume access to two fixed, offline datasets, mutually independent of each other: N x 0 > 0 N_{x_0} > 0 N x 0 > 0 i.i.d. samples D x 0 \mathcal{D}_{x_0} D x 0 of x 0 ∼ P 0 x_0 \sim\mathbb{P}_0 x 0 ∼ P 0 , and N ω > 0 N_{\omega} > 0 N ω > 0 i.i.d. samples D ω \mathcal{D}_{\omega} D ω of ω ∼ P ω \omega\sim\mathbb{P}_{\omega} ω ∼ P ω .
The finite ρ \rho ρ -moment assumption ensures that the ρ \rho ρ -Wasserstein distance between the probability measures considered in this work is finite, while the i.i.d. assumption excludes temporal correlations in the process noise. The availability of samples from P ω \mathbb{P}_{\omega} P ω , although common in data-driven stochastic and distributionally robust settings [2 , 17 , 18 ] , is stronger. Nevertheless, it can be practically satisfied through, e.g., observations of the state and control. In practice, it suffices for f f f to be injective over only a subset of X \mathcal{X} X as discussed in [17 ] .
To make probabilistic statements about System (3), we define the probability law induced by a fixed control sequence. In particular, for k ≥ 1 k \ge1 k ≥ 1 and a given sequence of control inputs u k − 1 : = ( u 0 , … , u k − 1 ) ∈ U k u_{k-1} := (u_0,\ldots,u_{k-1}) \in\mathcal{U}^{k} u k − 1 := ( u 0 , … , u k − 1 ) ∈ U k , the distribution of System (3) at time k k k is denoted as P x k u k − 1 \mathbb{P}^{u_{k-1}}_{x_k} P x k u k − 1 and is defined by propagating the noise and input distribution through the dynamics k k k times using u k − 1 u_{k-1} u k − 1 , i.e.,
P x 1 u 0 = f ( P 0 ⊗ P ω ) , P x k u k − 2 = f ( P x k − 1 u k − 2 ⊗ P ω ) for k > 1. \mathbb{P}^{u_0}_{x_1} = f(\mathbb{P}_0 \otimes\mathbb{P}_{\omega}), \qquad
\mathbb{P}^{u_{k-2}}_{x_k} = f(\mathbb{P}^{u_{k-2}}_{x_{k-1}} \otimes\mathbb{P}_{\omega}) \quad\text{for } k>1. P x 1 u 0 = f ( P 0 ⊗ P ω ) , P x k u k − 2 = f ( P x k − 1 u k − 2 ⊗ P ω ) for k > 1.
The robot operates in a workspace with obstacles and is subject to state constraints, e.g., steering angle or velocity limits. We denote the set of such states O ⊂ X \mathcal{O} \subset\mathcal{X} O ⊂ X . The task of the robot is to avoid these states to get to a target set denoted by T ⊂ X \mathcal{T} \subset\mathcal{X} T ⊂ X . We are now ready to define our problem.
Problem 1 (Motion Planning under Unknown Noise). Given the robotic system in (3), the measurable obstacle and target sets O , T ⊆ X \mathcal{O},\mathcal{T} \subseteq\mathcal{X} O , T ⊆ X introduced above, unsafety probability thresholds ϵ O , ϵ T ∈ ( 0 , 1 ) \epsilon_{\mathcal{O}},\epsilon_{\mathcal{T}} \in(0,1) ϵ O , ϵ T ∈ ( 0 , 1 ) , and confidence-level threshold β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) , find a control sequence u H − 1 ∈ U H u_{H-1} \in\mathcal{U}^{H} u H − 1 ∈ U H for some horizon H ∈ N H \in\mathbb{N} H ∈ N such that
P x k u k − 1 ( O ) ≤ ϵ O ∀ k ∈ [ H ] , and P x H u H − 1 ( T ) ≥ 1 − ϵ T (4) \mathbb{P}^{u_{k-1}}_{x_k}(\mathcal{O}) \le\epsilon_{\mathcal{O}} \quad\forall k \in[H], \qquad\text{and} \qquad\mathbb{P}^{u_{H-1}}_{x_H}(\mathcal{T}) \ge1-\epsilon_{\mathcal{T}} \tag*{(4)} P x k u k − 1 ( O ) ≤ ϵ O ∀ k ∈ [ H ] , and P x H u H − 1 ( T ) ≥ 1 − ϵ T (4)
hold with probability at least 1 − β 1-\beta 1 − β .
The above chance-constrained motion planning problem is particularly challenging since System (3) is both nonlinear and stochastic, and the distributions P 0 \mathbb{P}_0 P 0 and P ω \mathbb{P}_{\omega} P ω are unknown. To address these challenges, our approach, introduced in Section 4, combines techniques from distribution learning [13 , 14 , 38 ] , uncertainty propagation [12 ] , and distributionally robust optimization [12 , 15 ] with sampling-based planning algorithms (e.g., RRT). The key novelty is learning Wasserstein ambiguity sets from data and propagating them through nonlinear dynamics within a search algorithm. This enables us to formally account for the uncertainty induced by finite data while propagating, through the system dynamics, sets of distributions that are statistically consistent with the observed data. In Section 4.2, we introduce the uncertainty propagation framework used to evolve these ambiguity sets over time. Our full planning algorithm is then presented in Section 4.3, where we also propose a multi-tree strategy that mitigates the accumulation of uncertainty over long horizons while maintaining soundness guarantees.
Learn-To-Propagate Motion Planning from Data
Before presenting the full algorithm, we first introduce its core building blocks: the learning and propagation of Wasserstein ambiguity sets, which drive the tree expansion mechanism and are, in principle, applicable to most kinodynamic sampling-based motion planners.
Learning Wasserstein Ambiguity Sets
Our approach is based on learning Wasserstein ambiguity sets centered at discrete distributions. As shown below, this representation allows us to leverage existing frameworks for learning Wasserstein ambiguity sets while also enabling particularly efficient propagation through the system dynamics.
Given a set of N + N p r e N+N_{\mathrm{pre}} N + N pre i.i.d. samples D N + N p r e \mathcal{D}_{N+N_{\mathrm{pre}}} D N + N pre from P \mathbb{P} P , our goal is to construct a discrete distribution P ^ \widehat{\mathbb{P}} P , together with a radius ϵ ≥ 0 \epsilon\ge0 ϵ ≥ 0 , such that, with high probability, P ∈ B ϵ ( P ^ ) \mathbb{P} \in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}) P ∈ B ϵ ( P ) . To this end, we follow an approach inspired by [13 ] , extending it to distributions with unknown and potentially unbounded support. The method is as follows. We first separate D N + N p r e \mathcal{D}_{N+N_{\mathrm{pre}}} D N + N pre into a pre-training dataset D N p r e \mathcal{D}_{N_{\mathrm{pre}}} D N pre and a training dataset D N \mathcal{D}_N D N . From D N p r e \mathcal{D}_{N_{\mathrm{pre}}} D N pre , we compute its bounding box (i.e., an axis-aligned hyperrectangle containing all of its samples) and partition it into M M M axis-aligned hyperrectangles, M ∈ N M \in\mathbb{N} M ∈ N being the desired support size, by cyclic bisections1 : ⌊ log 2 M ⌋ \lfloor\log_2 M \rfloor ⌊ log 2 M ⌋ rounds halve every current cell along the coordinates in cyclic order, and a last round halves M − 2 ⌊ log 2 M ⌋ M - 2^{\lfloor\log_2 M \rfloor} M − 2 ⌊ l o g 2 M ⌋ of the resulting cells (none if M M M is a power of two) along the next coordinate. The sets C 1 , … , C M C_1,\ldots,C_M C 1 , … , C M are the intersections of these hyperrectangles with X \mathcal{X} X , and the support of the discrete distribution P ^ \widehat{\mathbb{P}} P is { c 1 , … , c M } \{c_1,\ldots,c_M\} { c 1 , … , c M } , where c i ∈ C i c_i \in C_i c i ∈ C i is the center of the i i i -th hyperrectangle if it belongs to X \mathcal{X} X , and an arbitrary point of C i C_i C i otherwise.2 The following theorem then provides a method for constructing (i) a nominal discrete distribution P ^ \widehat{\mathbb{P}} P by counting the number of observed samples from D N \mathcal{D}_N D N in each region, and (ii) a Wasserstein ambiguity set B ϵ ( P ^ ) \mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}) B ϵ ( P ) such that P ∣ X c ∈ B ϵ ( P ^ ) \mathbb{P}|_{\mathcal{X}_c} \in\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}) P ∣ X c ∈ B ϵ ( P ) , where X c = ⋃ i = 1 M C i \mathcal{X}_c = \bigcup_{i=1}^M C_i X c = ⋃ i = 1 M C i , with guarantees.3
Theorem 1 (Learning Ambiguity Set). Let D N = { x 1 , … , x N } \mathcal{D}_N = \{x_1,\ldots,x_N\} D N = { x 1 , … , x N } be i.i.d. samples from P \mathbb{P} P and β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) be a confidence level threshold. For i ∈ [ M ] i \in[M] i ∈ [ M ] , let Z i = ∑ n = 1 N 1 C i ( x n ) Z_i = \sum_{n=1}^{N} \mathbf{1}_{C_i}(x_n) Z i = ∑ n = 1 N 1 C i ( x n ) be the number of samples from D N \mathcal{D}_N D N in C i C_i C i and N X c = ∑ i = 1 M Z i N_{\mathcal{X}_c} = \sum_{i=1}^{M} Z_i N X c = ∑ i = 1 M Z i . Further, define the discrete distribution
P ^ = ∑ i = 1 M Z i N X c δ c i \widehat{\mathbb{P}} = \sum_{i=1}^{M} \frac{Z_i}{N_{\mathcal{X}_c}} \delta_{c_i} P = i = 1 ∑ M N X c Z i δ c i associating probability Z i N X c \frac{Z_i}{N_{\mathcal{X}_c}} N X c Z i to each support point c i c_i c i . For i ∈ [ M ] i \in[M] i ∈ [ M ] , define lower- and upper-bound probabilities p ℓ ( i ) , p u ( i ) p_{\ell}^{(i)},p_u^{(i)} p ℓ ( i ) , p u ( i ) , where p ℓ ( i ) = 0 p_{\ell}^{(i)}=0 p ℓ ( i ) = 0 if Z i = 0 Z_i=0 Z i = 0 , otherwise p ℓ ( i ) p_{\ell}^{(i)} p ℓ ( i ) is such that
β 2 M = ∑ j = Z i N X c ( N X c j ) ( p ℓ ( i ) ) j ( 1 − p ℓ ( i ) ) N X c − j , \frac{\beta}{2M} = \sum_{j=Z_i}^{N_{\mathcal{X}_c}} \binom{N_{\mathcal{X}_c}}{j} (p_{\ell}^{(i)})^j(1-p_{\ell}^{(i)})^{N_{\mathcal{X}_c}-j}, 2 M β = j = Z i ∑ N X c ( j N X c ) ( p ℓ ( i ) ) j ( 1 − p ℓ ( i ) ) N X c − j , and p u ( i ) = 1 p_u^{(i)}=1 p u ( i ) = 1 if Z i = N X c Z_i=N_{\mathcal{X}_c} Z i = N X c , otherwise p u ( i ) p_u^{(i)} p u ( i ) is such that
β 2 M = ∑ j = 0 Z i ( N X c j ) ( p u ( i ) ) j ( 1 − p u ( i ) ) N X c − j . \frac{\beta}{2M} = \sum_{j=0}^{Z_i} \binom{N_{\mathcal{X}_c}}{j} (p_u^{(i)})^j(1-p_u^{(i)})^{N_{\mathcal{X}_c}-j}. 2 M β = j = 0 ∑ Z i ( j N X c ) ( p u ( i ) ) j ( 1 − p u ( i ) ) N X c − j . Finally, let ϵ ( D N ) \epsilon(\mathcal{D}_N) ϵ ( D N ) be the solution of the following mixed integer linear problem (MILP):
ϵ ( D N ) ρ = sup ω ∈ R + M , γ ∈ R + M × M ∑ i = 1 M ∑ j = 1 M max x ∈ C i ∥ x − c j ∥ ρ γ ( i , j ) \epsilon(\mathcal{D}_N)^\rho=
\sup_{\substack{\omega\in\mathbb{R}_+^M,\\ \gamma\in\mathbb{R}_+^{M\times M}}}
\sum_{i=1}^{M}\sum_{j=1}^{M}\max_{x\in C_i}\lVert x-c_j\rVert^\rho\gamma^{(i,j)} ϵ ( D N ) ρ = ω ∈ R + M , γ ∈ R + M × M sup i = 1 ∑ M j = 1 ∑ M x ∈ C i max ∥ x − c j ∥ ρ γ ( i , j ) s.t. γ 1 = ω ω ⊤ 1 = ( Z 1 / N X c , … , Z M / N X c ) γ ( i , i ) ≥ min { ω ( i ) , Z i / N X c } , ∀ i ∈ [ M ] ω ( i ) ∈ [ p ℓ ( i ) , p u ( i ) ] , ∀ i ∈ [ M ] . (5) \begin{aligned}
\text{s.t.}\quad
&\gamma\mathbf{1}=\omega\\
&\omega^\top\mathbf{1}=(Z_1/N_{\mathcal{X}_c},\ldots,Z_M/N_{\mathcal{X}_c})\\
&\gamma^{(i,i)}\geq\min\{\omega^{(i)},Z_i/N_{\mathcal{X}_c}\},\quad\forall i\in[M]\\
&\omega^{(i)}\in[p_{\ell}^{(i)},p_u^{(i)}],\quad\forall i\in[M]. \tag*{(5)}
\end{aligned} s.t. γ 1 = ω ω ⊤ 1 = ( Z 1 / N X c , … , Z M / N X c ) γ ( i , i ) ≥ min { ω ( i ) , Z i / N X c } , ∀ i ∈ [ M ] ω ( i ) ∈ [ p ℓ ( i ) , p u ( i ) ] , ∀ i ∈ [ M ] . (5) Then, with probability at least 1 − β 1-\beta 1 − β , it holds that P ∣ X c ∈ B ϵ ( D N ) ( P ^ ) \mathbb{P}|_{\mathcal{X}_c}\in\mathcal{B}_{\epsilon(\mathcal{D}_N)}(\widehat{\mathbb{P}}) P ∣ X c ∈ B ϵ ( D N ) ( P ) .
Theorem 1 generalizes Theorem 3.1 in [13 ] by allowing the support of P \mathbb{P} P to be unknown and potentially unbounded. Importantly, Proposition 2 below, which is a direct consequence of the law of total probability, guarantees that estimating P ∣ X c \mathbb{P}|_{\mathcal{X}_c} P ∣ X c allows one to control the probability of arbitrary measurable sets for P \mathbb{P} P . All proofs are provided in Appendix § 10 .
Proposition 2 (Validity Check). Consider the setting in Theorem 1 . Let β ~ ∈ ( 0 , 1 ) \tilde{\beta}\in(0,1) β ~ ∈ ( 0 , 1 ) be a confidence level threshold and the random variable N X c = N − N X c N_{\mathcal{X}_c}=N-N_{\mathcal{X}_c} N X c = N − N X c be the number of samples outside X c \mathcal{X}_c X c , and define p ℓ , p u p_{\ell},p_u p ℓ , p u as respectively satisfying
β ~ 2 = ∑ j = N X c N ( N j ) p ℓ j ( 1 − p ℓ ) N − j \frac{\tilde{\beta}}{2}=\sum_{j=N_{\mathcal{X}_c}}^{N}\binom{N}{j}p_{\ell}^{j}(1-p_{\ell})^{N-j} 2 β ~ = j = N X c ∑ N ( j N ) p ℓ j ( 1 − p ℓ ) N − j and
β ~ 2 = ∑ j = 0 N X c ( N j ) p u j ( 1 − p u ) N − j . \frac{\tilde{\beta}}{2}=\sum_{j=0}^{N_{\mathcal{X}_c}}\binom{N}{j}p_u^{j}(1-p_u)^{N-j}. 2 β ~ = j = 0 ∑ N X c ( j N ) p u j ( 1 − p u ) N − j . Then, for any set S ∈ B ( X ) S\in\mathcal{B}(\mathcal{X}) S ∈ B ( X ) , it holds with probability at least 1 − β − β ~ 1-\beta-\tilde{\beta} 1 − β − β ~ that
P ( S ) ≤ ( 1 − p ℓ ) ⋅ sup Q ∈ B ϵ ( D N ) ( P ^ ) Q ( S ) + p u . (6) \mathbb{P}(S)\leq(1-p_{\ell})\cdot\sup_{\mathbb{Q}\in\mathcal{B}_{\epsilon(\mathcal{D}_N)}(\widehat{\mathbb{P}})}\mathbb{Q}(S)+p_u. \tag*{(6)} P ( S ) ≤ ( 1 − p ℓ ) ⋅ Q ∈ B ϵ ( D N ) ( P ) sup Q ( S ) + p u . (6)
In Proposition 2, the interval ( p ℓ , p u ) (p_{\ell},p_u) ( p ℓ , p u ) is constructed to bound P ( X ∖ X c ) \mathbb{P}(\mathcal{X}\setminus\mathcal{X}_c) P ( X ∖ X c ) with high confidence. We refer to it as the ambiguity set’s escaped mass. Note that the bound in Eq. (6) still requires to compute sup Q ∈ B ϵ ( D N ) ( P ^ ) Q ( S ) \sup_{\mathbb{Q}\in\mathcal{B}_{\epsilon(\mathcal{D}_N)}(\widehat{\mathbb{P}})}\mathbb{Q}(S) sup Q ∈ B ϵ ( D N ) ( P ) Q ( S ) . While this is not trivial in general, in our case, where P ^ \widehat{\mathbb{P}} P is discrete with support size M M M , this can be done particularly efficiently in time O ( M log M ) O(M\log M) O ( M log M ) by sorting the distance of each support point of P ^ \widehat{\mathbb{P}} P to the set S S S , and then greedily moving mass to this set until the Wasserstein distance constraint ϵ ( D N ) \epsilon(\mathcal{D}_N) ϵ ( D N ) is met [15 ] .
These results give rise to two procedures: (i) LearnAmbiguitySet( D , β , M ) (\mathcal{D},\beta,M) ( D , β , M ) , taking a dataset D = D N + D N p r e \mathcal{D}=\mathcal{D}_N+\mathcal{D}_{N_{\mathrm{pre}}} D = D N + D N pre of i.i.d. samples from P \mathbb{P} P and a support size M M M , and constructing, with probability at least 1 − β 1-\beta 1 − β , an ambiguity set B ϵ ( P ^ ) \mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}) B ϵ ( P ) (with ∣ supp ( P ^ ) ∣ = M |\operatorname{supp}(\widehat{\mathbb{P}})|=M ∣ supp ( P ) ∣ = M ) containing P ∣ X c \mathbb{P}|_{\mathcal{X}_c} P ∣ X c , and escaped-mass bounds p ℓ , p u p_{\ell},p_u p ℓ , p u such that p ℓ ≤ P ( X ∖ X c ) ≤ p u p_{\ell}\leq\mathbb{P}(\mathcal{X}\setminus\mathcal{X}_c)\leq p_u p ℓ ≤ P ( X ∖ X c ) ≤ p u for a bounded constructed set X c \mathcal{X}_c X c ; and (ii) ValidityCheck, which takes a set S S S and a threshold ϵ \epsilon ϵ , and certifies P ( S ) ≤ ϵ \mathbb{P}(S)\leq\epsilon P ( S ) ≤ ϵ with probability at least 1 − β 1-\beta 1 − β (see Appendix § 9 ).
Propagating Wasserstein Ambiguity Sets
To complete the algorithm, we need to propagate the ambiguity sets obtained via Theorem 1 (the LearnAmbiguitySet procedure) through the system dynamics over multiple time steps. This can be performed efficiently as follows. Consider a Wasserstein ambiguity set B ϵ ( P ^ ) \mathcal{B}_{\epsilon}(\widehat{\mathbb{P}}) B ϵ ( P ) and an arbitrary Lipschitz continuous function h : R d → R d h:\mathbb{R}^{d}\to\mathbb{R}^{d} h : R d → R d with Lipschitz constant L h > 0 L_h>0 L h > 0 . Specializing [12, Thm 5.1] to this setting yields:
h # B ϵ ( P ^ ) ⊆ B L h ϵ ( h # P ^ ) . (7) h\#\mathcal{B}_{\epsilon}(\widehat{\mathbb{P}})\subseteq\mathcal{B}_{L_h\epsilon}(h\#\widehat{\mathbb{P}}). \tag*{(7)} h # B ϵ ( P ) ⊆ B L h ϵ ( h # P ) . (7)
Critically, when the center distribution P ^ \widehat{\mathbb{P}} P is discrete, the propagated center h # P ^ h\#\widehat{\mathbb{P}} h # P can be computed efficiently. Indeed, writing P ^ = ∑ i = 1 M π ( i ) δ c i \widehat{\mathbb{P}}=\sum_{i=1}^{M}\pi^{(i)}\delta_{c_i} P = ∑ i = 1 M π ( i ) δ c i for a probability vector π ∈ [ 0 , 1 ] M \pi\in[0,1]^M π ∈ [ 0 , 1 ] M , we have h # P ^ = ∑ i = 1 M π ( i ) δ h ( c i ) h\#\widehat{\mathbb{P}}=\sum_{i=1}^{M}\pi^{(i)}\delta_{h(c_i)} h # P = ∑ i = 1 M π ( i ) δ h ( c i ) ; that is, each support point c i c_i c i is mapped to h ( c i ) h(c_i) h ( c i ) . We note that the Lipschitz-based propagation method in (7) is significantly more computationally tractable than the general result in [12, Thm 5.1]. This efficiency is important for fast exploration of the search space in motion planning. However, it may yield conservatively large propagated ambiguity sets. Our planning algorithm uses a multi-tree (forest) strategy to mitigate this conservatism as described in § 4.3 .
These results lead to the procedure Propagate (see pseudocode in Appendix § 9 ), the core mechanism driving tree expansion in our motion planning algorithm. Given an ambiguity set, state and noise escaped masses ( p ℓ , p u ) (p_{\ell},p_u) ( p ℓ , p u ) , ( p ω , ℓ , p ω , u ) (p_{\omega,\ell},p_{\omega,u}) ( p ω , ℓ , p ω , u ) , and a target Delta-dirac δ x \delta_x δ x centered at a given state x x x , Propagate picks a control u ∈ U u\in\mathcal{U} u ∈ U 4 to steer that ambiguity set’s center distribution towards δ x \delta_x δ x , and returns the propagated Wasserstein ambiguity set obtained through h = f ( ⋅ , u , ⋅ ) h=f(\cdot,u,\cdot) h = f ( ⋅ , u , ⋅ ) via (7) , as well as the escaped mass via Proposition 5.
Learn-To-Propagate Distributionally-Robust Forest (L2P-DR-Forest) Algorithm
We are now ready to present our motion planning algorithm, called Learn-To-Propagate Distributionally-Robust Forest (L2P-DR-Forest) , whose pseudocode is given in Algorithm 1. It operates in stages and grows one motion tree per stage, which yields a forest. Within each stage, the tree is expanded according to standard tree-based kinodynamic sampling-based motion planning, e.g., RRT. The forest differs from existing multi-tree planners [25 , 26 , 33 ] , which grow trees from distinct states and connect them. Instead, we root each new tree at a node of an earlier tree and re-learn its ambiguity set from new data.
The trees are stored in a forest F \mathbb{F} F , initially empty, and each stage has four steps: (i) it selects a tree in F \mathbb{F} F and a node ν \nu ν from it (Line 3); (ii) it learns, from fresh data, the ambiguity set of the state distribution induced by the controller leading to ν \nu ν (Lines 5–7); (iii) it grows a new tree rooted at the newly learned node (Lines 8–16); and (iv) it adds the tree to the forest (Line 17). Figure 1 illustrates our proposed algorithm. The nodes of the trees represent ambiguity sets, learned, propagated, and checked using the methods described in the previous subsections. Specifically, the root node of each tree is a Wasserstein ambiguity set that is learned directly from data using LearnAmbiguitySet(), and all of its offspring nodes are propagated using Propagate(). The noise distribution P ω \mathbb{P}_{\omega} P ω is learned in the same way, once per stage. In other words, LearnAmbiguitySet() is used only twice per stage: once for the root of its tree and once for the noise. Each node stores: (i) a Wasserstein ambiguity set, together with its escaped-mass bounds ( p ℓ , p u ) (p_{\ell},p_{u}) ( p ℓ , p u ) , (ii) the control action used to reach it (for a root, the controller u u u leading to it), and (iii) a pointer to its parent node.
Figure 1. Schematic of Algorithm 1 on a scenario with an obstacle O O O and a target T \mathcal{T} T . The roots of the trees, learned with LearnAmbiguitySet, are highlighted. (1) The forest F F F stores the trees of the previous stages. (2) SelectRoot selects one of the available trees in F F F , and a node ν \nu ν (circled) from this tree, at which the root of the new tree is learned (Lines 3–7). (3) Each iteration of the tree search uniformly samples a state x ∈ X x \in\mathcal{X} x ∈ X (black point), selects the node closest to it, and steers it towards x x x with the best of K K K candidate controls (solid child; the others are dashed) (Lines 10–14). If no node passes TargetCheck, the tree is added to F F F and the next stage begins (Line 17). (4) Otherwise, backtrack returns the controller u \mathbf{u} u leading to the node that passes (black path; Lines 15–16).
Restart node. At the beginning of each stage, SelectRoot(F \mathbb{F} F ; λ 1 , λ 2 \lambda_1,\lambda_2 λ 1 , λ 2 ) selects the restart node ν \nu ν (Line 3) in two steps. First, it selects a tree t r e e ′ \mathrm{tree}' tree ′ of the forest: the most recent one with probability 1 − λ 1 1-\lambda_1 1 − λ 1 , and one drawn uniformly from F \mathbb{F} F otherwise. Then, it selects in t r e e ′ \mathrm{tree}' tree ′ the restart node ν \nu ν : with probability 1 − λ 2 1-\lambda_2 1 − λ 2 the promising node given by the heuristic of Appendix C.2, and a node drawn uniformly from t r e e ′ \mathrm{tree}' tree ′ otherwise. Such exploration (by setting both λ 1 , λ 2 > 0 \lambda_1,\lambda_2>0 λ 1 , λ 2 > 0 ) prevents the algorithm from committing irreversibly to a single refined prefix and will prove to be fundamental to show the probabilistic completeness of our algorithm in Theorem 4. The stage then restarts at the controller u = backtrack ( ν ) u=\operatorname{backtrack}(\nu) u = backtrack ( ν ) leading to ν \nu ν (Line 4).
Learning. The datasets D x 0 , D ω \mathcal{D}_{x_0},\mathcal{D}_{\omega} D x 0 , D ω supply not-yet-used, mutually disjoint subsets of D x 0 ( s ) , D ω ( s ) \mathcal{D}_{x_0}^{(s)},\mathcal{D}_{\omega}^{(s)} D x 0 ( s ) , D ω ( s ) , which are rolled forward under u u u into a dataset D N ( s ) ( s ) \mathcal{D}_{N(s)}^{(s)} D N ( s ) ( s ) of state samples (Line 5), and a batch D N ω ( s ) ( s ) \mathcal{D}_{N_{\omega}(s)}^{(s)} D N ω ( s ) ( s ) of N ω ( s ) N_{\omega}(s) N ω ( s ) noise samples. Formally, for a controller u = ( u 0 , … , u k − 1 ) u=(u_0,\ldots,u_{k-1}) u = ( u 0 , … , u k − 1 ) , an initial state x 0 x_0 x 0 and a noise sequence ω = ( ω 0 , … , ω k − 1 ) \omega=(\omega_0,\ldots,\omega_{k-1}) ω = ( ω 0 , … , ω k − 1 ) , the state reached at time k k k is
F u ( x 0 , ω ) : = x k , x j + 1 = f ( x j , u j , ω j ) , j = 0 , … , k − 1 , (8) F_u(x_0,\omega):=x_k,\qquad x_{j+1}=f(x_j,u_j,\omega_j),\qquad j=0,\ldots,k-1, \tag*{(8)} F u ( x 0 , ω ) := x k , x j + 1 = f ( x j , u j , ω j ) , j = 0 , … , k − 1 , (8)
and Line 5 applies (8) with k = ∣ u ∣ k=|u| k = ∣ u ∣ to the i i i -th initial state of D x 0 ( s ) \mathcal{D}_{x_0}^{(s)} D x 0 ( s ) and the h h h -th block of ∣ u ∣ |u| ∣ u ∣ consecutive samples of D ω ( s ) \mathcal{D}_{\omega}^{(s)} D ω ( s ) , for i = 1 , … , N ( s ) i=1,\ldots,N(s) i = 1 , … , N ( s ) . The N ( s ) N(s) N ( s ) trajectories use ∣ u ∣ |u| ∣ u ∣ fresh noise samples each, one per step, i.e., N ( s ) ∣ u ∣ N(s)|u| N ( s ) ∣ u ∣ in total, so that D N ( s ) ( s ) \mathcal{D}_{N(s)}^{(s)} D N ( s ) ( s ) is i.i.d. from the state distribution induced by u u u . Since the length of the stage controller ∣ u ∣ |u| ∣ u ∣ is not known a priori, the stage partition D ω , N ω ( s ) ( s ) \mathcal{D}_{\omega,N_{\omega}(s)}^{(s)} D ω , N ω ( s ) ( s ) of the noise dataset D ω , N ω ( s ) ( s ) \mathcal{D}_{\omega,N_{\omega}(s)}^{(s)} D ω , N ω ( s ) ( s ) must be performed during runtime, while D x 0 ( s ) \mathcal{D}_{x_0}^{(s)} D x 0 ( s ) can be defined prior to execution. LearnAmbiguitySet() invokes Theorem 1 on these two datasets to construct a high-confidence Wasserstein ambiguity set and escaped-mass bound for the root (Line 6) and for the noise (Line 7). The confidence schedule ( β s ) s = 1 N s t a g e (\beta_s)_{s=1}^{N_{\mathrm{stage}}} ( β s ) s = 1 N stage allocates a share β s \beta_s β s of the overall confidence budget β \beta β to each s s s : ζ β s \zeta\beta_s ζ β s for the root’s state distribution learning and ( 1 − ζ ) β s (1-\zeta)\beta_s ( 1 − ζ ) β s for the noise. Any schedule with ∑ s = 1 N s t a g e β s ≤ β \sum_{s=1}^{N_{\mathrm{stage}}}\beta_s\le\beta ∑ s = 1 N stage β s ≤ β is valid.5 The schedules ( N ( s ) , M ( s ) ) (N(s),M(s)) ( N ( s ) , M ( s )) and ( N ω ( s ) , M ω ( s ) ) (N_{\omega}(s),M_{\omega}(s)) ( N ω ( s ) , M ω ( s )) set the sample size and the support size of the root and noise cells, respectively.
Tree search. A new tree is initialized at the learned root node (Line 8), and the tree search routine (Lines 9–16) expands it in a sampling-based fashion, e.g., RRT, for N i t e r N_{\mathrm{iter}} N iter iterations, after which it is added to the forest F \mathbb{F} F (Line 17). In Line 10–12, SelectNode() selects a node6 , and Propagate() propagates the ambiguity set and escaped-mass bound of the selected node using (7) and Proposition 5, respectively, under a chosen control input u ∗ ∈ U u^*\in\mathcal{U} u ∗ ∈ U . This new node is added to the tree only if it satisfies the distributionally robust safety condition of Problem 1 (Lines 13–14), and the algorithm terminates successfully once a node satisfies the distributionally robust target condition, returning the controller leading to it (Lines 15–16).
The computational cost of each tree expansion is dominated by the (robust) ValidityCheck() and TargetCheck() procedures. As explained in Section 4.2, propagation itself is efficient because the center distributions are discrete. However, repeated propagation using the Lipschitz-based method may inflate the ambiguity radius, unless dynamics are contractive (L h < 1 \mathcal{L}_h<1 L h < 1 ). Consequently, nodes deep in a single tree may carry overly conservative ambiguity sets, causing them to fail the validity check in challenging regions, e.g., narrow passages. A key observation is that the ambiguity sets are tightest near the regions where they are directly learned from data. Our forest approach exploits this locality. At each stage, the root of the new tree is learned afresh from the state distribution induced by the controller u = backtrack ( ν ) u=\operatorname{backtrack}(\nu) u = backtrack ( ν ) leading to the restart node ν \nu ν (Lines 5–6), rather than reusing the ambiguity set of ν \nu ν , which may have been inflated by repeated propagation. The nodes of the new tree are propagated from this tight root, so their ambiguity sets stay small enough to pass the validity check farther along the trajectory, e.g., through narrow passages.
Correctness and Probabilistic Completeness
The following theorem proves the soundness of the returned solution by Algorithm 1.
Algorithm 1: Learn-To-Propagate Distributionally-Robust Forest (L2P-DR-Forest)
Input: Datasets D x 0 , D ω \mathcal{D}_{x_0}, \mathcal{D}_{\omega} D x 0 , D ω , unsafety thresholds ε T , ε O ∈ ( 0 , 1 ) \varepsilon_T, \varepsilon_O \in(0,1) ε T , ε O ∈ ( 0 , 1 ) , number of stages N s t a g e > 0 N_{\mathrm{stage}} > 0 N stage > 0 , number of iterations N i t e r > 0 N_{\mathrm{iter}} > 0 N iter > 0 , confidence level β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) , confidence weight ζ ∈ ( 0 , 1 ) \zeta\in(0,1) ζ ∈ ( 0 , 1 ) , confidence schedule ( β s ) s = 1 N s t a g e (\beta_s)_{s=1}^{N_{\mathrm{stage}}} ( β s ) s = 1 N stage with ∑ s = 1 N s t a g e β s ≤ β \sum_{s=1}^{N_{\mathrm{stage}}} \beta_s \le\beta ∑ s = 1 N stage β s ≤ β , size schedules ( N ( s ) , M ( s ) ) s = 1 N s t a g e (N^{(s)}, M^{(s)})_{s=1}^{N_{\mathrm{stage}}} ( N ( s ) , M ( s ) ) s = 1 N stage and ( N ω ( s ) , M ω ( s ) ) s = 1 N s t a g e (N_\omega^{(s)}, M_\omega^{(s)})_{s=1}^{N_{\mathrm{stage}}} ( N ω ( s ) , M ω ( s ) ) s = 1 N stage , exploration probabilities λ 1 , λ 2 ∈ [ 0 , 1 ) \lambda_1, \lambda_2 \in[0,1) λ 1 , λ 2 ∈ [ 0 , 1 ) .
Output: Solution u H − 1 \mathbf{u}_{H-1} u H − 1 to Problem 1.
Initialize F ← ∅ F \leftarrow\emptyset F ← ∅
for s ← 1 s \leftarrow1 s ← 1 to N s t a g e N_{\mathrm{stage}} N stage do
ν ← SelectRoot ( F ; λ 1 , λ 2 ) \nu\leftarrow\operatorname{SelectRoot}(F; \lambda_1,\lambda_2) ν ← SelectRoot ( F ; λ 1 , λ 2 )
u ← backtrack ( ν ) \mathbf{u} \leftarrow\operatorname{backtrack}(\nu) u ← backtrack ( ν )
D N ( s ) ( s ) ← { F u ( x 0 , ω ) : ( x 0 , ω ) ∈ D x 0 ( s ) × D ω ( s ) paired by index } \mathcal{D}_{N^{(s)}}^{(s)} \leftarrow\{F_{\mathbf{u}}(x_0,\omega) : (x_0,\omega) \in\mathcal{D}_{x_0}^{(s)} \times\mathcal{D}_{\omega}^{(s)}\text{ paired by index}\} D N ( s ) ( s ) ← { F u ( x 0 , ω ) : ( x 0 , ω ) ∈ D x 0 ( s ) × D ω ( s ) paired by index }
B ε r o o t ( P ^ r o o t ) , ( p ℓ , p u ) ← LearnAmbiguitySet ( D N ( s ) ( s ) , ζ β s , M ( s ) ) \mathcal{B}_{\varepsilon_{\mathrm{root}}}(\widehat{P}_{\mathrm{root}}), (p_\ell,p_u) \leftarrow\operatorname{LearnAmbiguitySet}(\mathcal{D}_{N^{(s)}}^{(s)},\zeta\beta_s,M^{(s)}) B ε root ( P root ) , ( p ℓ , p u ) ← LearnAmbiguitySet ( D N ( s ) ( s ) , ζ β s , M ( s ) )
B ε ω ( P ^ ω ) , ( p ω , ℓ , p ω , u ) ← LearnAmbiguitySet ( D ω , N ω ( s ) ( s ) , ( 1 − ζ ) β s , M ω ( s ) ) \mathcal{B}_{\varepsilon_\omega}(\widehat{P}_\omega), (p_{\omega,\ell},p_{\omega,u}) \leftarrow\operatorname{LearnAmbiguitySet}(\mathcal{D}_{\omega,N_\omega^{(s)}}^{(s)},(1-\zeta)\beta_s,M_\omega^{(s)}) B ε ω ( P ω ) , ( p ω , ℓ , p ω , u ) ← LearnAmbiguitySet ( D ω , N ω ( s ) ( s ) , ( 1 − ζ ) β s , M ω ( s ) )
tree ← { node r o o t ← ( B ε r o o t ( P ^ r o o t ) , ( p ℓ , p u ) , u , ∅ ) } \operatorname{tree} \leftarrow\{\operatorname{node}_{\mathrm{root}} \leftarrow(\mathcal{B}_{\varepsilon_{\mathrm{root}}}(\widehat{P}_{\mathrm{root}}),(p_\ell,p_u),\mathbf{u},\emptyset)\} tree ← { node root ← ( B ε root ( P root ) , ( p ℓ , p u ) , u , ∅ )}
for i ← 1 i \leftarrow1 i ← 1 to N i t e r N_{\mathrm{iter}} N iter do
node s e l e c t e d , δ x ← SelectNode ( tree ) \operatorname{node}_{\mathrm{selected}},\delta_x \leftarrow\operatorname{SelectNode}(\operatorname{tree}) node selected , δ x ← SelectNode ( tree )
( B ε ( P ^ ) , ( p ℓ ′ , p u ′ ) , u ⋆ ) ← Propagate ( node s e l e c t e d , B ε ω ( P ^ ω ) , ( p ω , ℓ , p ω , u ) , δ x ) (\mathcal{B}_{\varepsilon}(\widehat{P}),(p'_\ell,p'_u),\mathbf{u}^{\star}) \leftarrow\operatorname{Propagate}(\operatorname{node}_{\mathrm{selected}},\mathcal{B}_{\varepsilon_\omega}(\widehat{P}_\omega),(p_{\omega,\ell},p_{\omega,u}),\delta_x) ( B ε ( P ) , ( p ℓ ′ , p u ′ ) , u ⋆ ) ← Propagate ( node selected , B ε ω ( P ω ) , ( p ω , ℓ , p ω , u ) , δ x )
node p r o p a g a t e d ← ( B ε ( P ^ ) , ( p ℓ ′ , p u ′ ) , u ⋆ , node s e l e c t e d ) \operatorname{node}_{\mathrm{propagated}} \leftarrow(\mathcal{B}_{\varepsilon}(\widehat{P}),(p'_\ell,p'_u),\mathbf{u}^{\star},\operatorname{node}_{\mathrm{selected}}) node propagated ← ( B ε ( P ) , ( p ℓ ′ , p u ′ ) , u ⋆ , node selected )
if ValidityCheck ( node p r o p a g a t e d , O , ε O ) \operatorname{ValidityCheck}(\operatorname{node}_{\mathrm{propagated}},O,\varepsilon_O) ValidityCheck ( node propagated , O , ε O ) then
tree ← tree ∪ { node p r o p a g a t e d } \operatorname{tree} \leftarrow\operatorname{tree} \cup\{\operatorname{node}_{\mathrm{propagated}}\} tree ← tree ∪ { node propagated }
if TargetCheck ( node p r o p a g a t e d , T , ε T ) \operatorname{TargetCheck}(\operatorname{node}_{\mathrm{propagated}},\mathcal{T},\varepsilon_T) TargetCheck ( node propagated , T , ε T ) then
return u ← backtrack ( node p r o p a g a t e d ) \mathbf{u} \leftarrow\operatorname{backtrack}(\operatorname{node}_{\mathrm{propagated}}) u ← backtrack ( node propagated )
F ← F ∪ { tree } F \leftarrow F \cup\{\operatorname{tree}\} F ← F ∪ { tree }
Theorem 3 (Correctness of Alg. 1). If Algorithm 1 returns a controller u H − 1 \mathbf{u}_{H-1} u H − 1 (for the corresponding horizon H H H ), then u H − 1 \mathbf{u}_{H-1} u H − 1 solves Problem 1 with confidence at least 1 − β 1-\beta 1 − β over the datasets D x 0 , D ω \mathcal{D}_{x_0}, \mathcal{D}_{\omega} D x 0 , D ω .
The proof relies on the fact that, in each stage, the calls of LearnAmbiguitySet return ambiguity sets and escaped masses containing the true state and noise distributions with probability 1 − β s 1-\beta_s 1 − β s . Because the propagation and validity checks rely on guaranteed over- and under-approximations, their guarantees hold under the event that the learner is correct. The conclusion thus follows trivially from the application of the union bound and ∑ s β s ≤ β \sum_s \beta_s \le\beta ∑ s β s ≤ β .
We now move to showing that Algorithm 1 is probabilistic complete under some mild distributional assumptions. Completeness is usually formalized by requiring a noise-free trajectory to clear the unsafe and non-target regions by a margin Δ \Delta Δ [27 ] . In our stochastic setting, we state it directly on the propagated distributions P u k − 1 x k P_{\mathbf{u}_{k-1}}^{\mathbf{x}_k} P u k − 1 x k induced by a control sequence. Assumption 2 below requires the existence of a nominal controller u ~ \tilde{\mathbf{u}} u ~ such that the induced state distributions stay strictly safe under any perturbation of Wasserstein size Δ \Delta Δ , thus allowing for a margin in probability space.
Assumption 2 (Δ-Robust Feasibility). There exist Δ > 0 \Delta> 0 Δ > 0 , a horizon H ˉ ∈ N \bar{H} \in\mathbb{N} H ˉ ∈ N and a control sequence u ~ H ˉ − 1 = ( u ~ 0 , … , u ~ H ˉ − 1 ) ∈ U H ˉ \tilde{\mathbf{u}}_{\bar{H}-1} = (\tilde{u}_0, \ldots, \tilde{u}_{\bar{H}-1}) \in\mathcal{U}^{\bar{H}} u ~ H ˉ − 1 = ( u ~ 0 , … , u ~ H ˉ − 1 ) ∈ U H ˉ such that
sup Q ∈ B Δ ( P u ~ k − 1 x k ) Q ( O ) < ϵ O ∀ k ∈ [ H ˉ ] , \sup_{Q \in\mathbb{B}_{\Delta}\left(P_{\tilde{\mathbf{u}}_{k-1}}^{\mathbf{x}_k}\right)} Q(\mathcal{O}) < \epsilon_{\mathcal{O}} \quad\forall k \in[\bar{H}], Q ∈ B Δ ( P u ~ k − 1 x k ) sup Q ( O ) < ϵ O ∀ k ∈ [ H ˉ ] , sup Q ∈ B Δ ( P u ~ H ˉ − 1 x H ˉ ) Q ( X ∖ T ) < ϵ T . (9) \sup_{Q \in\mathbb{B}_{\Delta}\left(P_{\tilde{\mathbf{u}}_{\bar{H}-1}}^{\mathbf{x}_{\bar{H}}}\right)} Q(\mathcal{X} \setminus\mathcal{T}) < \epsilon_{\mathcal{T}}. \tag*{(9)} Q ∈ B Δ ( P u ~ H ˉ − 1 x H ˉ ) sup Q ( X ∖ T ) < ϵ T . (9)
We prove the probabilistic completeness of Algorithm 1 assuming the following limit conditions: the algorithm is run with N s t a g e = ∞ N_{\mathrm{stage}} = \infty N stage = ∞ on infinite i.i.d. sequences D x 0 , D ω \mathcal{D}_{x_0}, \mathcal{D}_{\omega} D x 0 , D ω , with schedules β s \beta_s β s , N ( s ) N(s) N ( s ) , M ( s ) M(s) M ( s ) , N ω ( s ) N_{\omega}(s) N ω ( s ) and M ω ( s ) M_{\omega}(s) M ω ( s ) satisfying the conditions of Appendix B.5.
Theorem 4 (Probabilistic Completeness). Suppose Assumption 2 holds, and the execution conditions from the previous paragraph. Further, assume P ω P_{\omega} P ω is sub-Gaussian, U \mathcal{U} U has positive Lebesgue measure in every ball centered at its points, and Algorithm 1 is run as above with λ 1 , λ 2 ∈ ( 0 , 1 ) \lambda_1, \lambda_2 \in(0,1) λ 1 , λ 2 ∈ ( 0 , 1 ) . Then, with probability 1, Algorithm 1 returns a controller u H − 1 \mathbf{u}_{H-1} u H − 1 within finitely many stages that solves Problem 1 with confidence at least 1 − β 1-\beta 1 − β .
The proof, provided in Appendix B, combines convergence of the learned uncertainty bounds with persistent exploration. As the sample sizes increase through successive learning and re-learning stages, the learned radii and escaped masses converge to zero. The sub-Gaussian assumption on P ω P_{\omega} P ω ensures that the bounding box of the pre-training samples, which scales the learned radius, grows at most logarithmically with the sample size, so that the radius can vanish. The robustness margin Δ \Delta Δ in Assumption 2 therefore ensures that nodes associated with controllers sufficiently close to the robustly feasible controller u ~ \tilde{\mathbf{u}} u ~ eventually pass the validity checks. Moreover, the restart mechanism, with λ 1 , λ 2 > 0 \lambda_1, \lambda_2 > 0 λ 1 , λ 2 > 0 , ensures that the search repeatedly revisits earlier nodes and explores alternative control extensions.
Empirical Evaluation
We empirically evaluate L2P-DR-Forest on five robotic benchmarks: a 2D 5-mode Switched System [16 ] , two 3D vehicle models (AV Maze [1 , 6 ] , and Unicycle Maze), a 4D Tractor Trailer [5 ] with residual neural-network dynamics, and a 6D Double Integrator. For all the experiments, we considered ρ = 2 \rho= 2 ρ = 2 with the Euclidean norm, a confidence parameter of β = 10 − 4 \beta= 10^{-4} β = 1 0 − 4 , exploration probabilities λ 1 = λ 2 = 10 − 2 \lambda_1 = \lambda_2 = 10^{-2} λ 1 = λ 2 = 1 0 − 2 , a confidence weight ζ = 0.75 \zeta= 0.75 ζ = 0.75 , the uniform schedule β s = β / N s t a g e \beta_s = \beta/N_{\mathrm{stage}} β s = β / N stage , sample sizes N ( s ) = N ω ( s ) N(s) = N_{\omega}(s) N ( s ) = N ω ( s ) growing linearly with s s s , and constant support sizes M ( s ) = M ω ( s ) = 4 M(s) = M_{\omega}(s) = 4 M ( s ) = M ω ( s ) = 4 (or 2 for Tractor Trailer). Dynamics, environmental details, and the remaining hyperparameters are provided in Appendix D. All experiments were executed on an Apple M2 Pro CPU with 16GB of RAM.7
Table 1 compares three experimental settings: (1) our full Algorithm 1 (L2P-DR-Forest in Table 1), (2) an ablation without uncertainty re-learning (No re-learning), i.e. where N s t a g e = 1 N_{\mathrm{stage}} = 1 N stage = 1 , and (3) the ϵ \epsilon ϵ -RandUP-RRT baseline [28 , 40 ] , a sampling-based planner that certifies safety by checking that the ϵ \epsilon ϵ -padded per time-step convex hulls of 1,000 randomly propagated points cover every obstacle (see Appendix E for details). Our key takeaways are:
Strong performance on nonlinear systems. Our approach successfully synthesizes formally safe controllers across challenging environments, achieving a 100% success rate on all five benchmarks, including the most demanding one, Tractor Trailer, whose dynamics are given by a learned neural network with a (Lipschitz-certified, see Appendix D.5) Lipschitz constant exceeding one (1.21) compounded over the benchmark’s ≈ 90 \approx90 ≈ 90 time steps. Total planning time ranges from 0.08s on Switched System to 55.51s on Tractor Trailer. Importantly, when we use the obtained safe controllers in a Monte-Carlo simulation of the actual underlying system for 5 × 10 3 5 \times10^3 5 × 1 0 3 simulations, unsafe probabilities are 0% in all time steps for all benchmarks, while target hitting probabilities are 100%.
Necessity of re-learning. The uncertainty re-learning mechanism proves essential. The no-relearning ablation reaches 0% success on all five benchmarks, despite being granted the same total iteration budget. Crucially, the MILP optimization required for this stage introduces negligible computational overhead (≤ 0.12 \le0.12 ≤ 0.12 s). This is because even with the high confidence considered in our experimental setting, the support size M M M required by Theorem 1 to achieve small enough Wasserstein ambiguity set radii remains relatively small, consistently below 10 for all examples.
Comparison against ϵ \epsilon ϵ -RandUP-RRT. ϵ \epsilon ϵ -RandUP-RRT [28 , 40 ] solves none of the benchmarks more reliably than our method: it reaches 85% on AV Maze and 80% on Unicycle Maze, matches our 100% on Double Integrator, and collapses entirely on the hybrid, mode-switching Switched System (0%) and on the highly nonlinear Tractor Trailer (0%, timing out on all 20 seeds). It is also slower whenever it does succeed, markedly so on the mazes (e.g., 31.30s vs. 1.56s for our method on AV Maze), since every extension requires rolling out 1,000 particles through the forward dynamics – an overhead that grows sharply with the cost of a single forward-dynamics evaluation, as on the neural-network-driven Tractor Trailer, whereas our method only ever propagates the much smaller distribution at the center of the ambiguity set. We note that these runs use a 2-minute per-seed budget; on Tractor Trailer every seed reached that budget without terminating, so its 0% should be read as a lower bound on what a longer budget would allow. Crucially, unlike our method, ϵ \epsilon ϵ -RandUP-RRT offers no certified statistical safety guarantee in practice: the confidence bound of [28 ] depends on quantities (e.g., packing numbers of the obstacle boundary) that are difficult to obtain for our benchmarks, so we could not instantiate it at a prescribed confidence level and its results should be read as empirical only.
Planning illustration. Figure 2 and Figure 3 illustrate the execution of the algorithm on the AV Maze and on the Double Integrator, depicting the planning trees of the successive stages via the means of the ambiguity sets’ center distributions. Each stage roots a new tree, with a freshly learned ambiguity set, at a promising node of a previous tree, so that the trees progressively push the explored region towards the target. On the AV Maze, SelectRoot draws the first tree at the third stage: the third tree restarts at the same node as the second one, with a root re-learned from more samples, and the second tree is not used by the returned controller. The fourth Double Integrator tree is abandoned in the same way. The first Double Integrator tree is only two steps deep (inset of Figure 3 (a)), since stage 1 learns from the fewest samples and its escaped-mass
(a) First stage
(b) Second stage
(c) Third stage (restarts in tree 1)
(d) Fourth (last) stage
(e) Safe trajectory
Figure 2. AV Maze, drawn through the means of the nodes’ center distributions in the positions (p x p_x p x , p y p_y p y ), with one color per stage. In each stage panel, the new tree is opaque, the tree drawn by SelectRoot is half faded, the other trees are faded, and circles mark the learned roots. At the third stage, SelectRoot draws the first tree: the third tree restarts at the same node as the second one, which is abandoned.
Figure 3. Double Integrator , in the positions ( p x , p y , p z ) (p_x,p_y,p_z) ( p x , p y , p z ) , with the encoding of Figure 2 . The inset of (a) zooms on the first tree, only two steps deep, in the ( p x , p y ) (p_x,p_y) ( p x , p y ) plane. At the fifth stage, SelectRoot draws the third tree: the fifth tree restarts at the same node as the fourth one, which is abandoned.
Table 1. Summary of average selected statistics (with one standard deviation).
bounds, which accumulate along the tree, are the loosest. Later stages learn from more samples and grow deeper trees. This is the behavior that re-learning enables, whereas a single tree (No re-learning ) fails on all benchmarks.
Limitations
A limitation of our approach is its scalability to high-dimensional systems. This limitation stems from the well-known curse of dimensionality affecting Wasserstein ambiguity sets, where the sample complexity required to attain a given approximation accuracy increases rapidly with the dimension of the uncertainty space [14 ] . We should also stress its dependence on reasonably tight Lipschitz bounds and access to a preferably large dataset of noise samples (or, equivalently, the ability to easily query them). An important future work direction is to investigate alternative probability metrics that alleviate this dependence, such as the sliced Wasserstein distance [4 , 23 ] .
Conclusion
We introduced Learn-To-Propagate Distributionally-Robust Forest (L2P-DR-Forest), a novel motion-planning algorithm based on distributionally robust optimization that supports nonlinear dynamics and unknown distributions while providing safety and correctness guarantees. By combining optimal transport, statistical learning, and nonlinear uncertainty propagation, L2P-DR-Forest enables the efficient synthesis of safe trajectories for stochastic systems beyond the linear-Gaussian setting. Our experimental results demonstrate that the proposed approach achieves superior performance compared to comparable methods. More broadly, the theoretical framework developed in this work establishes a new connection between Wasserstein-based distribution learning and uncertainty-aware motion planning, opening new directions for scalable and provably safe planning.
References
This Appendix provides supplementary material organized into five sections. Appendix A introduces the component algorithms underlying Algorithm 1, followed by Appendix B, which contains proofs for all theoretical results presented in this manuscript. Appendix C details the heuristics used by SelectRoot to select a promising node (Algorithm 3). Appendix D specifies the environment configurations used in the experiments of § 5 , and Appendix E details our implementation of the ϵ \epsilon ϵ -RandUP-RRT baseline.
Algorithms
We introduce the algorithms LearnAmbiguitySet, SelectRoot, SelectNode, Propagate, ValidityCheck, and TargetCheck, which are the building blocks of Algorithm 1.
Algorithm for LearnAmbiguitySet
Algorithm 2 follows naturally from § 4.1 .
The support size M M M of the discrete approximation P ^ \widehat{\mathbb{P}} P is a caller-supplied parameter. Of the dataset’s ∣ D ∣ |\mathcal{D}| ∣ D ∣ samples, N p r e N_{\mathrm{pre}} N pre are allocated to pre-training, leaving N = ∣ D ∣ − N p r e N=|\mathcal{D}|-N_{\mathrm{pre}} N = ∣ D ∣ − N pre for the training portion D N \mathcal{D}_{N} D N . The pre-training dataset D N p r e \mathcal{D}_{N_{\mathrm{pre}}} D N pre defines the bounding box B = ∏ k [ a k , b k ] B=\prod_k[a_k,b_k] B = ∏ k [ a k , b k ] of its samples, which is partitioned into M M M hyperrectangles by cyclic bisections. Let e e e be the dimension of the data and R : = ⌊ log 2 M ⌋ R:=\lfloor\log_2 M\rfloor R := ⌊ log 2 M ⌋ , so that 2 R ≤ M < 2 R + 1 2^R\le M<2^{R+1} 2 R ≤ M < 2 R + 1 . In round j ∈ [ R ] j\in[R] j ∈ [ R ] , every current cell is halved at its midpoint along coordinate ( ( j − 1 ) m o d e ) + 1 ((j-1)\bmod e)+1 (( j − 1 ) mod e ) + 1 , which yields 2 R 2^R 2 R cells. In round R + 1 R+1 R + 1 , only M − 2 R M-2^R M − 2 R of these cells are halved along coordinate ( R m o d e ) + 1 (R\bmod e)+1 ( R mod e ) + 1 , which yields 2 R + ( M − 2 R ) = M 2^R+(M-2^R)=M 2 R + ( M − 2 R ) = M cells; any choice of the cells to halve is valid as long as it does not depend on D N \mathcal{D}_{N} D N (e.g., the first ones in the order of construction), and there is no round R + 1 R+1 R + 1 if M M M is a power of two. Cells are products of half-open intervals, closed at b k b_k b k , so that they are disjoint. The cell C i C_i C i is the intersection of the i i i -th hyperrectangle with X \mathcal{X} X , and c i ∈ C i c_i\in C_i c i ∈ C i is the center of the hyperrectangle if it lies in X \mathcal{X} X , and an arbitrary point of C i C_i C i otherwise.
Algorithm for SelectRoot
SelectRoot (Algorithm 3) selects the tree of the forest in which a stage r r r restarts and, in it, the node whose controller roots the tree of the stage. With probability 1 − λ 1 1-\lambda_1 1 − λ 1 , it first picks the most recent tree of F \mathbb{F} F , and with probability λ 1 \lambda_1 λ 1 , a tree drawn uniformly from F \mathbb{F} F . Independently, with probability 1 − λ 2 1-\lambda_2 1 − λ 2 , it then returns the promising node of that tree, selected by the heuristic of Appendix § 11 .§ 2 , and with probability λ 2 \lambda_2 λ 2 a node drawn uniformly from that tree. The returned node determines where the new tree is rooted: its own ambiguity set is not reused, but instead learned afresh from new samples at the controller backtrack(v v v ) (Lines 5–6 of Algorithm 1), so that the certificate of every refined node is as tight as the sample sizes of the current stage allow. Since the promising node of a tree does not change, drawing an older tree typically restarts at a node where an earlier stage already restarted, with a root re-learned from more samples (Figure 2 and Figure 3 ).
Table 3.
Algorithms for SelectNode and Propagate
In motion planning algorithms, node selection and propagation require an underlying similarity measure between a state x ∈ X x\in\mathcal{X} x ∈ X and any node in the tree. In this work, we propose the following pseudometric: letting P n \mathbb{P}_n P n denote the ambiguity set associated with a node n ∈ n\in n ∈ tree and x ˉ n : = E y ∼ P [ y ] \bar{x}_n:=\mathbb{E}_{y\sim\mathbb{P}}[y] x ˉ n := E y ∼ P [ y ] the mean of its center, the distance between node n n n and x ∈ X x\in\mathcal{X} x ∈ X is defined as d m e a n ( P ^ , δ x ) : = ∥ x ˉ n − x ∥ d_{\mathrm{mean}}(\widehat{\mathbb{P}},\delta_x):=\lVert\bar{x}_n-x\rVert d mean ( P , δ x ) := ∥ x ˉ n − x ∥ . It is a pseudometric between distributions since it is blind to their spread, with the same mean are at distance zero) that ignores their spread, and it is dominated by the Wasserstein distance between the center and δ x \delta_x δ x , d m e a n ( P ^ , δ x ) ≤ W p ( P ^ , δ x ) d_{\mathrm{mean}}(\widehat{\mathbb{P}},\delta_x)\le W_p(\widehat{\mathbb{P}},\delta_x) d mean ( P , δ x ) ≤ W p ( P , δ x ) for every p ≥ 1 p\ge1 p ≥ 1 , by Jensen’s inequality (for p = 2 p=2 p = 2 this is the Wasserstein distance with the Euclidean norm, W 2 ( P ^ , δ x ) 2 = d m e a n ( P ^ , δ x ) 2 + tr Cov ( P ^ ) W_2(\widehat{\mathbb{P}},\delta_x)^2=d_{\mathrm{mean}}(\widehat{\mathbb{P}},\delta_x)^2+\operatorname{tr}\operatorname{Cov}(\widehat{\mathbb{P}}) W 2 ( P , δ x ) 2 = d mean ( P , δ x ) 2 + tr Cov ( P ) , i.e., d m e a n d_{\mathrm{mean}} d mean is W 2 W_2 W 2 without its covariance term). Crucially, because the center distributions P ^ \widehat{\mathbb{P}} P constructed in this work are always discrete, with at most M M M atoms, this distance is available in closed form. Ties between nodes at the same distance, e.g., nodes with identical means, are broken uniformly at random.
Once the node nodes e l e c t e d _{\mathrm{selected}} selected closest to δ x \delta_x δ x is identified, we determine the control input u ∗ u^* u ∗ that steers this node as close as possible to δ x \delta_x δ x (for the same distance, among K K K candidates sampled uniformly from U \mathcal{U} U ), leveraging the theoretical results presented in § 4.2 . Line 4 of Algorithm 5 approximates the arg min over U \mathcal{U} U by its minimizer over K K K candidates sampled uniformly from U \mathcal{U} U . The candidates are drawn independently of the node and of δ x \delta_x δ x . The distance in line 4 only requires the mean of the propagated distribution, which is available in closed form from its atoms. Lines 5 and 7 are extensively discussed in Section 4.2, and line 8 (propagating the escaped mass) in Proposition 5 below. Over multiple iterations, the support size of the resulting discrete distribution P ^ \widehat{P} P in line 5 may grow, thereby increasing computational and memory overhead. To mitigate this issue, we introduce a compression step in line 6. This step compresses P ^ \widehat{P} P back to at most M ( s ) M(s) M ( s ) atoms, the support size of the stage’s root: it partitions the bounding box of the atoms of P ^ \widehat{P} P into M ( s ) M(s) M ( s ) cells by cyclic bisections, as in LearnAmbiguitySet, and merges the atoms of each cell into a single atom located at their probability-weighted mean, which lies in the cell. The Wasserstein distance between P ^ \widehat{P} P and its compressed counterpart is at most the cost ϵ c o m p r \epsilon_{\mathrm{compr}} ϵ compr of the coupling that moves every atom to the mean of its cell.
Figure 4. Example of the bounding box of a given artificial dataset D p r e \mathcal{D}_{\mathrm{pre}} D pre , partitioned into M M M cells C i C_i C i with centers c i c_i c i as explained above, for M ∈ { 1 , 4 } M \in\{1,4\} M ∈ { 1 , 4 } .
Table 4.
Algorithms for ValidityCheck and TargetCheck
Before introducing the algorithms for ValidityCheck and TargetCheck, we introduce Proposition 5 which extends and specializes Proposition 2 to Problem 1. In the following, let f u = f ( ⋅ , u , ⋅ ) f_u=f(\cdot,u,\cdot) f u = f ( ⋅ , u , ⋅ ) for any given u ∈ U u\in\mathcal{U} u ∈ U , and u ∈ U k \mathbf{u}\in\mathcal{U}^k u ∈ U k a given controller.
Proposition 5. Let the state distribution induced by u \mathbf{u} u , P x k u P^{\mathbf{u}}_{x_k} P x k u , be such that P x k u ∣ X c ∈ B ϵ x ( P ^ x ) P^{\mathbf{u}}_{x_k}|_{\mathcal{X}_c}\in\mathbb{B}_{\epsilon_x}(\widehat{P}_x) P x k u ∣ X c ∈ B ϵ x ( P x ) and P x k u ( X ∖ X c ) ∈ [ p ℓ , p u ] P^{\mathbf{u}}_{x_k}(\mathcal{X}\setminus\mathcal{X}_c)\in[p_\ell,p_u] P x k u ( X ∖ X c ) ∈ [ p ℓ , p u ] for some bounded set X c ⊂ X \mathcal{X}_c\subset\mathcal{X} X c ⊂ X . Analogously, let the process noise distribution, P ω P_\omega P ω , be such that P ω ∣ W c ∈ B ϵ ω ( P ^ ω ) P_\omega|_{\mathcal{W}_c}\in\mathbb{B}_{\epsilon_\omega}(\widehat{P}_\omega) P ω ∣ W c ∈ B ϵ ω ( P ω ) and P ω ( W ∖ W c ) ∈ [ p ω , ℓ , p ω , u ] P_\omega(\mathcal{W}\setminus\mathcal{W}_c)\in[p_{\omega,\ell},p_{\omega,u}] P ω ( W ∖ W c ) ∈ [ p ω , ℓ , p ω , u ] for some bounded set W c ⊂ W \mathcal{W}_c\subset\mathcal{W} W c ⊂ W . Then, for any set S ∈ B ( X ) S\in\mathcal{B}(\mathcal{X}) S ∈ B ( X ) ,
f u # ( P x k u ⊗ P ω ) ( S ) ≤ ( 1 − p ℓ ) ( 1 − p ω , ℓ ) ⋅ sup Q ∈ B ϵ ( f u # ( P ^ x ⊗ P ^ ω ) ) Q ( S ) + p u + p ω , u − p u p ω , u , f_{u\#}(P^{\mathbf{u}}_{x_k}\otimes P_\omega)(S)\le(1-p_\ell)(1-p_{\omega,\ell})\cdot\sup_{Q\in\mathbb{B}_{\epsilon}(f_{u\#}(\widehat{P}_x\otimes\widehat{P}_\omega))}Q(S)+p_u+p_{\omega,u}-p_up_{\omega,u}, f u # ( P x k u ⊗ P ω ) ( S ) ≤ ( 1 − p ℓ ) ( 1 − p ω , ℓ ) ⋅ Q ∈ B ϵ ( f u # ( P x ⊗ P ω )) sup Q ( S ) + p u + p ω , u − p u p ω , u , where ϵ = L f u ( ϵ x + ϵ ω ) \epsilon=L_{f_u}(\epsilon_x+\epsilon_\omega) ϵ = L f u ( ϵ x + ϵ ω ) .
{#eq:10}
Because Proposition 5 bounds the escaped mass after a single application of f u f_u f u , it is applied once per Propagate() call, using the immediate parent node’s escaped-mass bound ( p ℓ r e f , p u r e f ) (p_\ell^{\mathrm{ref}},p_u^{\mathrm{ref}}) ( p ℓ ref , p u ref ) , as in line 8 of Algorithm 5. Both checks take a node as input. For a node storing B ϵ ( P ^ ) \mathbb{B}_{\epsilon}(\widehat{P}) B ϵ ( P ) and ( p ℓ , p u ) (p_\ell,p_u) ( p ℓ , p u ) , define
π ( S ) : = ( 1 − p ℓ ) sup Q ∈ B ϵ ( P ^ ) Q ( S ) + p u , S ∈ B ( X ) . (10) \pi(S):=(1-p_\ell)\sup_{Q\in\mathbb{B}_{\epsilon}(\widehat{P})}Q(S)+p_u,\qquad S\in\mathcal{B}(\mathcal{X}). \tag*{(10)} π ( S ) := ( 1 − p ℓ ) Q ∈ B ϵ ( P ) sup Q ( S ) + p u , S ∈ B ( X ) . (10)
Propositions 2 and 5 show that π ( S ) \pi(S) π ( S ) upper-bounds the probability of S S S under the state distribution P P P induced by the controller of the node, with high confidence. ValidityCheck (Algorithm 6) therefore returns whether π ( S ) ≤ ϵ S \pi(S)\le\epsilon_S π ( S ) ≤ ϵ S , which entails P ( S ) ≤ ϵ S P(S)\le\epsilon_S P ( S ) ≤ ϵ S . Since P ( T ) ≥ 1 − ϵ T P(\mathcal{T})\ge1-\epsilon_T P ( T ) ≥ 1 − ϵ T is equivalent to P ( X ∖ T ) ≤ ϵ T P(\mathcal{X}\setminus\mathcal{T})\le\epsilon_T P ( X ∖ T ) ≤ ϵ T , TargetCheck(node, T , ϵ T \mathcal{T},\epsilon_T T , ϵ T ) is analogous and returns ValidityCheck(node, $\mathcal{X}\setminus\mathcal{T},\epsilon_T).
To conclude, it remains to show how to efficiently solve sup Q ∈ B ϵ ( P ^ ) Q ( S ) \sup_{Q\in\mathbb{B}_{\epsilon}(\widehat{P})}Q(S) sup Q ∈ B ϵ ( P ) Q ( S ) for any set S ∈ B ( X ) S\in\mathcal{B}(\mathcal{X}) S ∈ B ( X ) . For this, we introduce SolveSup (Algorithm 7), which solves this problem by following Example 7 in [15 ] . In line 2, we compute the distance from each support point of the discrete distribution P ^ \widehat{P} P to the set S S S . For the points already in S S S , we sum their probabilities (line 4). For the outside points, we sort them ascendingly by distance to S S S (line 6). Lines 7-16 iteratively move as much probability mass to the set S S S as allowed by the Wasserstein budget ϵ \epsilon ϵ , starting from closer locations. Figure 5 depicts a schematic representation of Algorithm 7.
Figure 5. Representation of the worst-case probability mass displacement given by Algorithm 7.
Algorithm 5: Propagate (or steer) via ambiguity set propagation
1 Function Propagate(node_selected, $\mathcal{B}_{\epsilon_\omega}(\widehat{P}_\omega)$, $(p_{\omega,\ell},p_{\omega,u})$, $\delta_x$):
2 $\mathcal{B}_{\epsilon_{\mathrm{ref}}}(\widehat{P}_{\mathrm{ref}})$, $(p^{\mathrm{ref}}_\ell,p^{\mathrm{ref}}_u)$ $\leftarrow$ node_selected.(ambiguity_set, escaped_mass)
3 Sample $u_1,\ldots,u_K$ i.i.d. uniformly from $\mathcal{U}$
4 $u^\star \leftarrow \arg\min_{u\in\{u_1,\ldots,u_K\}}d_{\mathrm{mean}}\left(f_{u\#}(\widehat{P}_{\mathrm{ref}}\otimes\widehat{P}_\omega),\delta_x\right)$ // find control for steering
5 $\widehat{P}\leftarrow f_{u^\star\#}(\widehat{P}_{\mathrm{ref}}\otimes\widehat{P}_\omega)$ // propagate center
6 $\widehat{P},\epsilon_{\mathrm{compr}}\leftarrow \operatorname{Compress}(\widehat{P},M(s))$
7 $\epsilon\leftarrow L_{f_{u^\star}}(\epsilon_{\mathrm{ref}}+\epsilon_\omega)+\epsilon_{\mathrm{compr}}$ // propagate ambiguity radius
8 $p_\ell\leftarrow p^{\mathrm{ref}}_\ell+p_{\omega,\ell}-p^{\mathrm{ref}}_\ell p_{\omega,\ell},\quad p_u\leftarrow p^{\mathrm{ref}}_u+p_{\omega,u}-p^{\mathrm{ref}}_u p_{\omega,u}$ // propagate escaped mass
9 return $(\mathcal{B}_\epsilon(\widehat{P}),(p_\ell,p_u),u^\star)$
Algorithm 6: Check whether a node certifies $\mathbb{P}(S)\leq\epsilon_S$
1 Function ValidityCheck(node, $S$, $\epsilon_S$):
2 $\mathcal{B}_\epsilon(\widehat{P}),(p_\ell,p_u)\leftarrow$ node.(ambiguity_set, escaped_mass)
3 $q\leftarrow\operatorname{SolveSup}(\mathcal{B}_\epsilon(\widehat{P}),S)$ // Algorithm 7
4 return $(1-p_\ell)q+p_u\leq\epsilon_S$
Algorithm 7: Solving $\sup_{Q\in\mathcal{B}_\epsilon(\widehat{P})}Q(S)$ for a discrete distribution $\widehat{P}$ and a set $S\in\mathcal{B}(\mathcal{X})$ (Example 7 in [15]).
Input: Ambiguity set $\mathcal{B}_\epsilon(\widehat{P})$, where $\widehat{P}=\sum_{i=1}^{M}\pi^{(i)}\delta_{c_i}$, and set $S\in\mathcal{B}(\mathcal{X})$
Output: Result of $\sup_{Q\in\mathcal{B}_\epsilon(\widehat{P})}Q(S)$
1 function SolveSup($\mathcal{B}_\epsilon(\widehat{P}),S$):
2 $d^{(i)}\leftarrow\inf_{z\in S}\|z-c_i\|$ for $i\in[M]$
3 $I\leftarrow\{i\text{ s.t. }d^{(i)}>0\},\ I_0\leftarrow\{i\text{ s.t. }d^{(i)}=0\}$
4 $p\leftarrow\sum_{i\in I_0}\pi^{(i)}$
5 $W\leftarrow\epsilon$
6 $I\leftarrow$ sort ascendingly according to $d$
7 for $i\in I$ do
8 if $W=0$ then
9 break
10 else
11 if $\pi^{(i)}\times d^{(i)}\leq W$ then
12 $p\leftarrow p+\pi^{(i)}$
13 $W\leftarrow W-\pi^{(i)}\times d^{(i)}$
14 else
15 $p\leftarrow p+\frac{W}{d^{(i)}}$
16 break
17 return $p$
Proofs
Proof of Theorem 1
Proof. The proof follows directly from Theorem 3.1 in [13 ] after noting that gathering the N X c ≤ N N_{\mathcal{X}_c}\leq N N X c ≤ N samples from D N \mathcal{D}_N D N that lie on the set X c \mathcal{X}_c X c is equivalent to constructing a dataset D N X c \mathcal{D}_{N_{\mathcal{X}_c}} D N X c with N X c N_{\mathcal{X}_c} N X c i.i.d. samples from the distribution P ∣ X c P|_{\mathcal{X}_c} P ∣ X c . □
Proof of Proposition 2
Proof. By the law of total probability, we have that for any set S ⊆ X S\subseteq\mathcal{X} S ⊆ X ,
P ( S ) = P ( S ∩ X c ) + P ( S ∩ X ∖ X c ) . (11) \mathbb{P}(S)=\mathbb{P}(S\cap\mathcal{X}_c)+\mathbb{P}(S\cap\mathcal{X}\setminus\mathcal{X}_c). \tag*{(11)} P ( S ) = P ( S ∩ X c ) + P ( S ∩ X ∖ X c ) . (11)
We bound the two terms separately. We start with the second term. Since S ∩ ( X ∖ X c ) ⊆ X ∖ X c S\cap(\mathcal{X}\setminus\mathcal{X}_c)\subseteq\mathcal{X}\setminus\mathcal{X}_c S ∩ ( X ∖ X c ) ⊆ X ∖ X c , we have P ( S ∩ ( X ∖ X c ) ) ≤ P ( X ∖ X c ) \mathbb{P}(S\cap(\mathcal{X}\setminus\mathcal{X}_c))\leq\mathbb{P}(\mathcal{X}\setminus\mathcal{X}_c) P ( S ∩ ( X ∖ X c )) ≤ P ( X ∖ X c ) . We then proceed to bound the first term. By definition of the normalized restriction P ∣ X c P|_{\mathcal{X}_c} P ∣ X c , we have that
P ( S ∩ X c ) = P ∣ X c ( S ) ⋅ P ( X c ) ≤ P ∣ X c ( S ) ⋅ ( 1 − P ( X ∖ X c ) ) . (12) \mathbb{P}(S\cap\mathcal{X}_c)=P|_{\mathcal{X}_c}(S)\cdot\mathbb{P}(\mathcal{X}_c)\leq P|_{\mathcal{X}_c}(S)\cdot(1-\mathbb{P}(\mathcal{X}\setminus\mathcal{X}_c)). \tag*{(12)} P ( S ∩ X c ) = P ∣ X c ( S ) ⋅ P ( X c ) ≤ P ∣ X c ( S ) ⋅ ( 1 − P ( X ∖ X c )) . (12)
Substituting those bounds in (12), and using the fact that, by Clopper–Pearson Lemma, it holds with probability 1 − β ~ 1-\widetilde{\beta} 1 − β over D N \mathcal{D}_N D N that p ℓ ≤ P ( X ∖ X c ) ≤ p u p_\ell\leq\mathbb{P}(\mathcal{X}\setminus\mathcal{X}_c)\leq p_u p ℓ ≤ P ( X ∖ X c ) ≤ p u , we have that
P ( S ) ≤ P ∣ X c ( S ) ⋅ ( 1 − p ℓ ) + p u . (13) \mathbb{P}(S)\leq P|_{\mathcal{X}_c}(S)\cdot(1-p_\ell)+p_u. \tag*{(13)} P ( S ) ≤ P ∣ X c ( S ) ⋅ ( 1 − p ℓ ) + p u . (13)
Finally, we note that, from Theorem 1, with confidence 1 − β 1-\beta 1 − β , P ∣ X c ∈ B ϵ ( P ^ ) P|_{\mathcal{X}_c}\in\mathcal{B}_\epsilon(\widehat{P}) P ∣ X c ∈ B ϵ ( P ) . Therefore, by applying the union bound, with probability at least 1 − β − β ~ 1-\beta-\widetilde{\beta} 1 − β − β over D N \mathcal{D}_N D N it must hold that
P ( S ) ≤ ( 1 − p ℓ ) ⋅ sup Q ∈ B ϵ ( P ^ ) Q ( S ) + p u , (14) \mathbb{P}(S)\leq(1-p_\ell)\cdot\sup_{Q\in\mathcal{B}_\epsilon(\widehat{P})}Q(S)+p_u, \tag*{(14)} P ( S ) ≤ ( 1 − p ℓ ) ⋅ Q ∈ B ϵ ( P ) sup Q ( S ) + p u , (14)
which concludes the proof. □
Proof of Proposition 5
Soundness (Theorem 3 ) and completeness (Theorem 4 ) rest on one invariant: the true state distribution of every node belongs to the ambiguity set defined by the tuple ( P ^ , ϵ , p ℓ , p u ) (\widehat{\mathrm{P}},\epsilon,p_\ell,p_u) ( P , ϵ , p ℓ , p u ) stored at that node (Definition 2). Throughout, L f L_f L f is the joint Lipschitz constant of f f f , i.e., ∥ f ( x , u , ω ) − f ( x ′ , u ′ , ω ′ ) ∥ ≤ L f ( ∥ x − x ′ ∥ + ∥ u − u ′ ∥ + ∥ ω − ω ′ ∥ ) \lVert f(x,u,\omega)-f(x',u',\omega')\rVert\le L_f(\lVert x-x'\rVert+\lVert u-u'\rVert+\lVert\omega-\omega'\rVert) ∥ f ( x , u , ω ) − f ( x ′ , u ′ , ω ′ )∥ ≤ L f (∥ x − x ′ ∥ + ∥ u − u ′ ∥ + ∥ ω − ω ′ ∥) , so that f u : = f ( ⋅ , u , ⋅ ) f_u:=f(\cdot,u,\cdot) f u := f ( ⋅ , u , ⋅ ) is L f u L_{f_u} L f u -Lipschitz on X × W \mathcal{X}\times\mathcal{W} X × W , equipped with the norm ∥ x ∥ + ∥ ω ∥ \lVert x\rVert+\lVert\omega\rVert ∥ x ∥ + ∥ ω ∥ , with the constant L f u ≤ L f L_{f_u}\le L_f L f u ≤ L f used by Algorithm 5. Also, a ⊕ b : = a + b − a b = 1 − ( 1 − a ) ( 1 − b ) a\oplus b:=a+b-ab=1-(1-a)(1-b) a ⊕ b := a + b − ab = 1 − ( 1 − a ) ( 1 − b ) for a , b ∈ [ 0 , 1 ] a,b\in[0,1] a , b ∈ [ 0 , 1 ] , which is nondecreasing in each argument.
Definition 2 (Ambiguity set with escaped mass). For a discrete distribution P ^ \widehat{\mathrm{P}} P , a radius ϵ ≥ 0 \epsilon\ge0 ϵ ≥ 0 and 0 ≤ p ℓ ≤ p u ≤ 1 0\le p_\ell\le p_u\le1 0 ≤ p ℓ ≤ p u ≤ 1 , let
A ( P ^ , ϵ , p ℓ , p u ) : = { ( 1 − q ) μ + q ν : μ ∈ B ϵ ( P ^ ) , ν a probability measure , q ∈ [ p ℓ , p u ] } . \mathcal{A}(\widehat{\mathrm{P}},\epsilon,p_\ell,p_u):=\{(1-q)\mu+q\nu:\mu\in\mathcal{B}_\epsilon(\widehat{\mathrm{P}}),\ \nu\text{ a probability measure},\ q\in[p_\ell,p_u]\}. A ( P , ϵ , p ℓ , p u ) := {( 1 − q ) μ + q ν : μ ∈ B ϵ ( P ) , ν a probability measure , q ∈ [ p ℓ , p u ]} .
i.e., a Wasserstein ball around P ^ \widehat{\mathrm{P}} P for the mass 1 − q 1-q 1 − q that has not escaped, plus an arbitrary distribution ν \nu ν for the escaped mass q q q . For S ∈ B ( X ) S\in\mathcal{B}(\mathcal{X}) S ∈ B ( X ) , π ( S ) \pi(S) π ( S ) denotes the bound (11) of this tuple, which is tested by ValidityCheck and TargetCheck.
Lemma 6 (Calculus of ambiguity sets with escaped mass). It holds that:
(a) Validity. If P ∣ X c ∈ B ϵ ( P ^ ) \mathrm{P}|_{\mathcal{X}_c}\in\mathcal{B}_\epsilon(\widehat{\mathrm{P}}) P ∣ X c ∈ B ϵ ( P ) and P ( X ∖ X c ) ∈ [ p ℓ , p u ] \mathrm{P}(\mathcal{X}\setminus\mathcal{X}_c)\in[p_\ell,p_u] P ( X ∖ X c ) ∈ [ p ℓ , p u ] , then P ∈ A ( P ^ , ϵ , p ℓ , p u ) \mathrm{P}\in\mathcal{A}(\widehat{\mathrm{P}},\epsilon,p_\ell,p_u) P ∈ A ( P , ϵ , p ℓ , p u ) .
(b) Upper-bound. Further, every P ∈ A ( P ^ , ϵ , p ℓ , p u ) \mathrm{P}\in\mathcal{A}(\widehat{\mathrm{P}},\epsilon,p_\ell,p_u) P ∈ A ( P , ϵ , p ℓ , p u ) satisfies P ( S ) ≤ π ( S ) \mathrm{P}(S)\le\pi(S) P ( S ) ≤ π ( S ) for all S ∈ B ( X ) S\in\mathcal{B}(\mathcal{X}) S ∈ B ( X ) .
(c) Propagation.8 Let P x ∈ A ( P ^ x , ϵ x , p ℓ , p u ) \mathrm{P}_x\in\mathcal{A}(\widehat{\mathrm{P}}_x,\epsilon_x,p_\ell,p_u) P x ∈ A ( P x , ϵ x , p ℓ , p u ) and P ω ∈ A ( P ^ ω , ϵ ω , p ω , ℓ , p ω , u ) \mathrm{P}_\omega\in\mathcal{A}(\widehat{\mathrm{P}}_\omega,\epsilon_\omega,p_{\omega,\ell},p_{\omega,u}) P ω ∈ A ( P ω , ϵ ω , p ω , ℓ , p ω , u ) , and let u ∈ U u\in\mathcal{U} u ∈ U . Then
f u # ( P x ⊗ P ω ) ∈ A ( f u # ( P ^ x ⊗ P ^ ω ) , L f u ( ϵ x + ϵ ω ) , p ℓ ⊕ p ω , ℓ , p u ⊕ p ω , u ) . f_{u\#}(\mathrm{P}_x\otimes\mathrm{P}_\omega)\in\mathcal{A}\left(f_{u\#}(\widehat{\mathrm{P}}_x\otimes\widehat{\mathrm{P}}_\omega),L_{f_u}(\epsilon_x+\epsilon_\omega),p_\ell\oplus p_{\omega,\ell},p_u\oplus p_{\omega,u}\right). f u # ( P x ⊗ P ω ) ∈ A ( f u # ( P x ⊗ P ω ) , L f u ( ϵ x + ϵ ω ) , p ℓ ⊕ p ω , ℓ , p u ⊕ p ω , u ) .
Proof. (a) Take μ = P ∣ X c \mu=\mathrm{P}|_{\mathcal{X}_c} μ = P ∣ X c , ν = P ∣ X ∖ X c \nu=\mathrm{P}|_{\mathcal{X}\setminus\mathcal{X}_c} ν = P ∣ X ∖ X c , q = P ( X ∖ X c ) q=\mathrm{P}(\mathcal{X}\setminus\mathcal{X}_c) q = P ( X ∖ X c ) , which shows the first claim.
(b) If P ∈ A ( P ^ , ϵ , p ℓ , p u ) \mathrm{P}\in\mathcal{A}(\widehat{\mathrm{P}},\epsilon,p_\ell,p_u) P ∈ A ( P , ϵ , p ℓ , p u ) , then P ( S ) = ( 1 − q ) μ ( S ) + q ν ( S ) ≤ ( 1 − p ℓ ) sup B ϵ ( P ^ ) G ( S ) + p u \mathrm{P}(S)=(1-q)\mu(S)+q\nu(S)\le(1-p_\ell)\sup_{\mathrm{B}_\epsilon(\widehat{\mathrm{P}})}G(S)+p_u P ( S ) = ( 1 − q ) μ ( S ) + q ν ( S ) ≤ ( 1 − p ℓ ) sup B ϵ ( P ) G ( S ) + p u , as 1 − q ≤ 1 − p ℓ 1-q\le1-p_\ell 1 − q ≤ 1 − p ℓ and q ν ( S ) ≤ q ≤ p u q\nu(S)\le q\le p_u q ν ( S ) ≤ q ≤ p u .
(c) Write P x = ( 1 − q ) μ + q ν \mathrm{P}_x=(1-q)\mu+q\nu P x = ( 1 − q ) μ + q ν and P ω = ( 1 − q ω ) μ ω + q ω ν ω \mathrm{P}_\omega=(1-q_\omega)\mu_\omega+q_\omega\nu_\omega P ω = ( 1 − q ω ) μ ω + q ω ν ω as in the definition. Expanding the product, P x ⊗ P ω = ( 1 − q ′ ) μ ⊗ μ ω + q ′ ν ′ \mathrm{P}_x\otimes\mathrm{P}_\omega=(1-q')\mu\otimes\mu_\omega+q'\nu' P x ⊗ P ω = ( 1 − q ′ ) μ ⊗ μ ω + q ′ ν ′ , where q ′ : = q ⊕ q ω ∈ [ p ℓ ⊕ p ω , ℓ , p u ⊕ p ω , u ] q':=q\oplus q_\omega\in[p_\ell\oplus p_{\omega,\ell},p_u\oplus p_{\omega,u}] q ′ := q ⊕ q ω ∈ [ p ℓ ⊕ p ω , ℓ , p u ⊕ p ω , u ] and ν ′ : = ( q ν ⊗ P ω + ( 1 − q ) q ω μ ⊗ ν ω ) / q ′ \nu':=(q\nu\otimes\mathrm{P}_\omega+(1-q)q_\omega\mu\otimes\nu_\omega)/q' ν ′ := ( q ν ⊗ P ω + ( 1 − q ) q ω μ ⊗ ν ω ) / q ′ (arbitrary if q ′ = 0 q'=0 q ′ = 0 ). Hence f u # ( P x ⊗ P ω ) = ( 1 − q ′ ) f u # ( μ ⊗ μ ω ) + q ′ f u # ν ′ f_{u\#}(\mathrm{P}_x\otimes\mathrm{P}_\omega)=(1-q')f_{u\#}(\mu\otimes\mu_\omega)+q'f_{u\#}\nu' f u # ( P x ⊗ P ω ) = ( 1 − q ′ ) f u # ( μ ⊗ μ ω ) + q ′ f u # ν ′ , and it remains to show that f u # ( μ ⊗ μ ω ) f_{u\#}(\mu\otimes\mu_\omega) f u # ( μ ⊗ μ ω ) lies in the claimed ball around f u # ( P ^ x ⊗ P ^ ω ) f_{u\#}(\widehat{\mathrm{P}}_x\otimes\widehat{\mathrm{P}}_\omega) f u # ( P x ⊗ P ω ) . Indeed, applying Minkowski’s inequality gives W ρ ( μ ⊗ μ ω , P ^ x ⊗ P ^ ω ) ≤ ϵ x + ϵ ω W_\rho(\mu\otimes\mu_\omega,\widehat{\mathrm{P}}_x\otimes\widehat{\mathrm{P}}_\omega)\le\epsilon_x+\epsilon_\omega W ρ ( μ ⊗ μ ω , P x ⊗ P ω ) ≤ ϵ x + ϵ ω . Finally, pushing a coupling through ( f u , f u ) (f_u,f_u) ( f u , f u ) gives W ρ ( f u # α , f u # α ′ ) ≤ L f u W ρ ( α , α ′ ) W_\rho(f_{u\#}\alpha,f_{u\#}\alpha')\le L_{f_u}W_\rho(\alpha,\alpha') W ρ ( f u # α , f u # α ′ ) ≤ L f u W ρ ( α , α ′ ) . □ \square □
Proof of Proposition 5. Given the assumptions on P x k u \mathrm{P}_{x_k}^u P x k u and P ω \mathrm{P}_\omega P ω , it comes trivially from Lemma 6(a) that P x k u ∈ A ( P ^ x k , ϵ x , p ℓ , p u ) \mathrm{P}_{x_k}^u\in\mathcal{A}(\widehat{\mathrm{P}}_{x_k},\epsilon_x,p_\ell,p_u) P x k u ∈ A ( P x k , ϵ x , p ℓ , p u ) and P ω ∈ A ( P ^ ω , ϵ ω , p ω , ℓ , p ω , u ) \mathrm{P}_\omega\in\mathcal{A}(\widehat{\mathrm{P}}_\omega,\epsilon_\omega,p_{\omega,\ell},p_{\omega,u}) P ω ∈ A ( P ω , ϵ ω , p ω , ℓ , p ω , u ) . Then, from Lemma 6(c), we have that f u # ( P x k u ⊗ P ω ) ∈ A ( f u # ( P ^ x k ⊗ P ^ ω ) , ϵ , p ℓ ⊕ p ω , ℓ , p u ⊕ p ω , u ) f_{u\#}(\mathrm{P}_{x_k}^u\otimes\mathrm{P}_\omega)\in\mathcal{A}(f_{u\#}(\widehat{\mathrm{P}}_{x_k}\otimes\widehat{\mathrm{P}}_\omega),\epsilon,p_\ell\oplus p_{\omega,\ell},p_u\oplus p_{\omega,u}) f u # ( P x k u ⊗ P ω ) ∈ A ( f u # ( P x k ⊗ P ω ) , ϵ , p ℓ ⊕ p ω , ℓ , p u ⊕ p ω , u ) , with ϵ = L f u ( ϵ x + ϵ ω ) \epsilon=L_{f_u}(\epsilon_x+\epsilon_\omega) ϵ = L f u ( ϵ x + ϵ ω ) . Finally, applying Lemma 6(b) concludes the proof, since 1 − p ℓ ⊕ p ω , ℓ = ( 1 − p ℓ ) ( 1 − p ω , ℓ ) 1-p_\ell\oplus p_{\omega,\ell}=(1-p_\ell)(1-p_{\omega,\ell}) 1 − p ℓ ⊕ p ω , ℓ = ( 1 − p ℓ ) ( 1 − p ω , ℓ ) . □ \square □
Proof of Theorem 3
Proof. Let F \mathcal{F} F be the σ \sigma σ -algebra generated by all data consumed and all internal random draws made up to the end of stage s s s , together with the random draws of SelectRoot at stage s + 1 s+1 s + 1 (F 0 \mathcal{F}_0 F 0 is trivial, up to those of stage 1).
Step 1: all learning calls succeed with probability at least $1-\beta$. Let E \mathcal{E} E be the event that every call of LearnAmbiguitySet returns a tuple whose ambiguity set contains its target distribution (Lemma 6(a)). Stage s s s makes two calls, with targets Q s = P x k u Q_s=\mathrm{P}_{x_k}^u Q s = P x k u (root, line 6) and P ω \mathrm{P}_\omega P ω (noise, line 7), where u = backtrack ( v ) u=\operatorname{backtrack}(v) u = backtrack ( v ) for node v v v returned by SelectRoot at stage s s s , and k = ∣ u ∣ k=|u| k = ∣ u ∣ . The node v v v is a function of the forest, which is built by the stages before s s s , and of the draws of SelectRoot at stage $s (the reference trajectory of the heuristic of Appendix C.2 is computed beforehand from samples independent of D x 0 , D ω \mathcal{D}_{x_0},\mathcal{D}_\omega D x 0 , D ω ), and is therefore F s − 1 \mathcal{F}_{s-1} F s − 1 -measurable. Stage s s s consumes not-yet-used, disjoint blocks of D x 0 \mathcal{D}_{x_0} D x 0 and D ω \mathcal{D}_\omega D ω whose positions are determined by F s − 1 \mathcal{F}_{s-1} F s − 1 . Since both datasets are i.i.d., these blocks are independent of F s − 1 \mathcal{F}_{s-1} F s − 1 . Rolling the blocks D x 0 ( s ) , D ω ( s ) \mathcal{D}_{x_0}^{(s)},\mathcal{D}_\omega^{(s)} D x 0 ( s ) , D ω ( s ) forward under u u u (line 5) yields i.i.d. samples from Q s Q_s Q s , and the block D ω , N ( s ) ( s ) \mathcal{D}_{\omega,\mathcal{N}(s)}^{(s)} D ω , N ( s ) ( s ) consists of i.i.d. samples from P ω \mathrm{P}_\omega P ω . Conditionally on F s − 1 \mathcal{F}_{s-1} F s − 1 , both are thus fixed distributions, and Theorem 1 and Proposition 2 (with the internal split of the confidence level in Algorithm 2) give failure probabilities at most ζ β s \zeta\beta_s ζ β s and ( 1 − ζ ) β s (1-\zeta)\beta_s ( 1 − ζ ) β s for the two calls, hence at most β s \beta_s β s for stage s s s given F s − 1 \mathcal{F}_{s-1} F s − 1 , and unconditionally. Boole’s inequality gives P ( E c ) ≤ ∑ s β s ≤ β \mathrm{P}(\mathcal{E}^c)\le\sum_s\beta_s\le\beta P ( E c ) ≤ ∑ s β s ≤ β .
Step 2: soundness on E \mathcal{E} E . Fix an outcome in E \mathcal{E} E . By induction on the order of creation, every node n n n ever created stores a tuple whose ambiguity set contains P x k n u n \mathrm{P}_{x_{k_n}}^{u_n} P x k n u n , where u n : = backtrack ( n ) u_n:=\operatorname{backtrack}(n) u n := backtrack ( n ) and k n : = ∣ u n ∣ k_n:=|u_n| k n := ∣ u n ∣ . For a root this is E \mathcal{E} E , and for a child it is Lemma 6(c) applied to the parent’s tuple and the noise tuple of the same stage, for whichever control u ⋆ u^\star u ⋆ was used, followed by the compression of the center, which adds its radius ϵ c \epsilon_c ϵ c to the radius by the triangle inequality (footnote 8). This is exactly what lines 6, 7 and 8 of Algorithm 5 compute. By Lemma 6(b), π x k n u n ( S ) ≤ π n ( S ) \pi_{x_{k_n}}^{u_n}(S)\le\pi_n(S) π x k n u n ( S ) ≤ π n ( S ) for every S S S , and π n ( O , π n ( X ∖ T ) \pi_n(\mathcal{O},\pi_n(\mathcal{X}\setminus\mathcal{T}) π n ( O , π n ( X ∖ T ) are what ValidityCheck and TargetCheck compare with ϵ O \epsilon_{\mathcal{O}} ϵ O and ϵ T \epsilon_{\mathcal{T}} ϵ T . This holds for every node, accepted or not.
Step 3: conclusion. Suppose the algorithm returns u H − 1 u_{H-1} u H − 1 on an outcome in E \mathcal{E} E . Each u k − 1 u_{k-1} u k − 1 , k ∈ [ H ] k\in[H] k ∈ [ H ] , labels a node with prefix u k − 1 u_{k-1} u k − 1 that was accepted by ValidityCheck when created (by induction over the stage: the controller stored in a root is empty or the backtrack of a node of an earlier tree, whose prefixes are thus backtracks of accepted nodes, and the nodes of a tree other than its root were accepted when created), so P x k u k − 1 ( X ∖ T ) ≤ ϵ T \mathrm{P}_{x_k}^{u_{k-1}}(\mathcal{X}\setminus\mathcal{T})\le\epsilon_{\mathcal{T}} P x k u k − 1 ( X ∖ T ) ≤ ϵ T by Step 2, while the last node passed TargetCheck, so P x H − 1 u H − 1 ( X ∖ T ) ≤ ϵ T \mathrm{P}_{x_{H-1}}^{u_{H-1}}(\mathcal{X}\setminus\mathcal{T})\le\epsilon_{\mathcal{T}} P x H − 1 u H − 1 ( X ∖ T ) ≤ ϵ T . Both constraints of Problem 1 thus hold on E \mathcal{E} E , i.e., with probability at least 1 − β 1-\beta 1 − β .
The argument is unchanged if N s t a g e = ∞ N_{\mathrm{stage}}=\infty N stage = ∞ : Boole’s inequality extends to countably many calls whose confidence levels sum to at most β \beta β . □ \square □
Proof of Theorem 4
Auxiliary result #1: transferring check. ValidityCheck and TargetCheck test the bound π \pi π of the tuple ( P ^ , ϵ , p ℓ , p u ) (\widehat{\mathrm{P}},\epsilon,p_\ell,p_u) ( P , ϵ , p ℓ , p u ) stored at a node, whereas Assumption 2 gives a margin only for the worst-case probability over Δ \Delta Δ -balls around the nominal state distributions induced by u ~ \tilde{\mathbf{u}} u ~ . The following lemma transfers this margin to the checks: if the true distribution P \mathbb{P} P of the node is within Δ − 2 ϵ \Delta- 2\epsilon Δ − 2 ϵ of a reference distribution Q \mathbb{Q} Q (later, a nominal one), then π ( S ) \pi(S) π ( S ) exceeds the worst-case probability of S S S over B Δ ( Q ) \mathcal{B}_{\Delta}(\mathbb{Q}) B Δ ( Q ) by at most 2 p u 2p_u 2 p u , which is small for tight tuples.
Lemma 7 (Threshold transfer). Let P ∈ A ( P ^ , ϵ , p ℓ , p u ) \mathbb{P} \in\mathcal{A}(\widehat{P}, \epsilon, p_\ell, p_u) P ∈ A ( P , ϵ , p ℓ , p u ) and Q ∈ P ρ ( X ) \mathbb{Q} \in\mathcal{P}_{\rho}(\mathcal{X}) Q ∈ P ρ ( X ) be such that W ρ ( P , Q ) ≤ Δ − 2 ϵ W_{\rho}(\mathbb{P},\mathbb{Q}) \le\Delta- 2\epsilon W ρ ( P , Q ) ≤ Δ − 2 ϵ . Then, for all S ∈ B ( X ) S \in\mathcal{B}(\mathcal{X}) S ∈ B ( X ) ,
π ( S ) ≤ sup G ∈ B Δ ( Q ) G ( S ) + 2 p u . \pi(S) \le\sup_{\mathbb{G}\in\mathcal{B}_{\Delta}(\mathbb{Q})} \mathbb{G}(S) + 2p_u. π ( S ) ≤ G ∈ B Δ ( Q ) sup G ( S ) + 2 p u .
Proof. Using Definition 2, P ∈ A ( P ^ , ϵ , p ℓ , p u ) \mathbb{P} \in\mathcal{A}(\widehat{P}, \epsilon, p_\ell, p_u) P ∈ A ( P , ϵ , p ℓ , p u ) means that there exists μ ∈ B ϵ ( P ^ ) \mu\in\mathcal{B}_{\epsilon}(\widehat{P}) μ ∈ B ϵ ( P ) and q ∈ [ p ℓ , p u ] q \in[p_\ell,p_u] q ∈ [ p ℓ , p u ] such that P = ( 1 − q ) μ + q ν \mathbb{P}=(1-q)\mu+q\nu P = ( 1 − q ) μ + q ν . Now, let G ∈ B ϵ ( P ^ ) \mathbb{G} \in\mathcal{B}_{\epsilon}(\widehat{P}) G ∈ B ϵ ( P ) be any arbitrary measure, and define G ′ = ( 1 − q ) G + q ν \mathbb{G}'=(1-q)\mathbb{G}+q\nu G ′ = ( 1 − q ) G + q ν . From the joint convexity of W ρ p W_{\rho}^{p} W ρ p , we have that W ρ p ( G ′ , P ) ≤ ( 1 − q ) W ρ p ( G , μ ) + q W ρ p ( ν , ν ) ≤ ( 2 ϵ ) p W_{\rho}^{p}(\mathbb{G}',\mathbb{P}) \le(1-q)W_{\rho}^{p}(\mathbb{G},\mu)+qW_{\rho}^{p}(\nu,\nu)\le(2\epsilon)^p W ρ p ( G ′ , P ) ≤ ( 1 − q ) W ρ p ( G , μ ) + q W ρ p ( ν , ν ) ≤ ( 2 ϵ ) p , where we use that W ρ ( G , μ ) ≤ 2 ϵ W_{\rho}(\mathbb{G},\mu)\le2\epsilon W ρ ( G , μ ) ≤ 2 ϵ as both distributions belong to the W ρ W_{\rho} W ρ -ball of radius ϵ \epsilon ϵ around P ^ \widehat{P} P , and W ρ ( ν , ν ) = 0 W_{\rho}(\nu,\nu)=0 W ρ ( ν , ν ) = 0 . Hence W ρ ( G ′ , P ) ≤ 2 ϵ W_{\rho}(\mathbb{G}',\mathbb{P})\le2\epsilon W ρ ( G ′ , P ) ≤ 2 ϵ . From the triangle inequality, W ρ ( G ′ , Q ) ≤ W ρ ( G ′ , P ) + W ρ ( P , Q ) ≤ 2 ϵ + ( Δ − 2 ϵ ) = Δ W_{\rho}(\mathbb{G}',\mathbb{Q})\le W_{\rho}(\mathbb{G}',\mathbb{P})+W_{\rho}(\mathbb{P},\mathbb{Q})\le2\epsilon+(\Delta-2\epsilon)=\Delta W ρ ( G ′ , Q ) ≤ W ρ ( G ′ , P ) + W ρ ( P , Q ) ≤ 2 ϵ + ( Δ − 2 ϵ ) = Δ . Moreover, we observe that by construction G ′ ( S ) ≥ ( 1 − q ) G ( S ) \mathbb{G}'(S)\ge(1-q)\mathbb{G}(S) G ′ ( S ) ≥ ( 1 − q ) G ( S ) and 0 ≤ q − p ℓ ≤ p u 0\le q-p_\ell\le p_u 0 ≤ q − p ℓ ≤ p u . Thus,
( 1 − p ℓ ) G ( S ) = ( 1 − q ) G ( S ) + ( q − p ℓ ) G ( S ) ≤ ( 1 − q ) G ( S ) + p u G ( S ) + p u ≤ G ′ ( S ) + p u ≤ sup G ~ ∈ B Δ ( Q ) G ~ ( S ) + p u , \begin{aligned}
(1-p_\ell)\mathbb{G}(S)=(1-q)\mathbb{G}(S)+(q-p_\ell)\mathbb{G}(S)\le(1-q)\mathbb{G}(S)+p_u\mathbb{G}(S)+p_u \\
&\le\mathbb{G}'(S)+p_u\le\sup_{\widetilde{\mathbb{G}}\in\mathcal{B}_{\Delta}(\mathbb{Q})}\widetilde{\mathbb{G}}(S)+p_u,
\end{aligned} ( 1 − p ℓ ) G ( S ) = ( 1 − q ) G ( S ) + ( q − p ℓ ) G ( S ) ≤ ( 1 − q ) G ( S ) + p u G ( S ) + p u ≤ G ′ ( S ) + p u ≤ G ∈ B Δ ( Q ) sup G ( S ) + p u ,
since G ′ ∈ B Δ ( Q ) \mathbb{G}'\in\mathcal{B}_{\Delta}(\mathbb{Q}) G ′ ∈ B Δ ( Q ) . Adding p u p_u p u to both sides and taking the supremum over G \mathbb{G} G in B ϵ ( P ^ ) \mathcal{B}_{\epsilon}(\widehat{P}) B ϵ ( P ) on the left side gives the claim. □
Auxiliary result #2: learner consistency. Now, we move to a second auxiliary result and we prove that our distribution learner is consistent: under some scheduling conditions, both the learned radius ϵ \epsilon ϵ and the escaped-mass upper bound p u p_u p u can be controlled to any desired level.
In the following, let κ ≥ 1 \kappa\ge1 κ ≥ 1 be such that ∥ x ∥ ≤ κ ∥ x ∥ ∞ \lVert x\rVert\le\kappa\lVert x\rVert_{\infty} ∥ x ∥ ≤ κ ∥ x ∥ ∞ on R d \mathbb{R}^{d} R d and R w \mathbb{R}^{w} R w . Partition a box with longest side h h h in R e \mathbb{R}^{e} R e into M M M cells by cyclic bisections (Appendix A), and let R = ⌊ log 2 M ⌋ R=\lfloor\log_2 M\rfloor R = ⌊ log 2 M ⌋ . Every cell has been obtained by at least R R R cyclic bisections, so every coordinate has been halved at least ⌊ R / e ⌋ = ⌊ log 2 M / e ⌋ > log 2 M / e − 1 \lfloor R/e\rfloor=\lfloor\log_2 M/e\rfloor>\log_2 M/e-1 ⌊ R / e ⌋ = ⌊ log 2 M / e ⌋ > log 2 M / e − 1 times. The M M M cells thus have longest side at most h 2 − ⌊ log 2 M / e ⌋ ≤ 2 h M − 1 / e h2^{-\lfloor\log_2 M/e\rfloor}\le2hM^{-1/e} h 2 − ⌊ l o g 2 M / e ⌋ ≤ 2 h M − 1/ e , hence diameter at most
2 κ h M − 1 / e . (15) 2\kappa hM^{-1/e}. \tag*{(15)} 2 κh M − 1/ e . (15)
Lemma 8 (Consistency). Let ξ 1 , … , ξ n + N \xi_1,\ldots,\xi_{n+N} ξ 1 , … , ξ n + N be i.i.d. samples of a σ \sigma σ -sub-Gaussian distribution on R e \mathbb{R}^{e} R e , and consider the call LearnAmbiguitySet( ( ξ i ) i , β ′ , M ) ((\xi_i)_i,\beta',M) (( ξ i ) i , β ′ , M ) with pre-training samples ξ 1 , … , ξ n \xi_1,\ldots,\xi_n ξ 1 , … , ξ n and training samples ξ n + 1 , … , ξ n + N \xi_{n+1},\ldots,\xi_{n+N} ξ n + 1 , … , ξ n + N . Let τ ∈ ( 0 , 1 ] \tau\in(0,1] τ ∈ ( 0 , 1 ] , Λ : = ln ( 2 ( M + 1 ) / β ′ ) \Lambda:=\ln(2(M+1)/\beta') Λ := ln ( 2 ( M + 1 ) / β ′ ) , t : = Λ / N t:=\sqrt{\Lambda/N} t := Λ/ N and r : = 2 σ ln ( 2 ( n + N ) 2 ) r:=2\sigma\sqrt{\ln(2(n+N)^2)} r := 2 σ ln ( 2 ( n + N ) 2 ) . With probability at least 1 − 4 e / ( τ ( n + 1 ) ) 1-4e/(\tau(n+1)) 1 − 4 e / ( τ ( n + 1 )) , the returned radius ϵ \epsilon ϵ and escaped-mass upper bound p u p_u p u satisfy
p u ≤ τ 2 + t , ϵ ≤ κ r ( 2 M − 1 / e + ( M t / 2 ) 1 / ρ ) . p_u\le\frac{\tau}{2}+t,\qquad\epsilon\le\kappa r(2M^{-1/e}+(Mt/2)^{1/\rho}). p u ≤ 2 τ + t , ϵ ≤ κ r ( 2 M − 1/ e + ( M t /2 ) 1/ ρ ) .
Proof. Let B B B be the bounding box of the pre-training samples and h h h its longest side. By the union bound and the sub-Gaussian tail, with probability at least 1 − n ⋅ 2 exp ( − ln ( 2 ( n + N ) 2 ) ) ≥ 1 − 1 / ( n + N ) 1-n\cdot2\exp(-\ln(2(n+N)^2))\ge1-1/(n+N) 1 − n ⋅ 2 exp ( − ln ( 2 ( n + N ) 2 )) ≥ 1 − 1/ ( n + N ) all pre-training samples lie in the cube of center m m m and half-side σ ln ( 2 ( n + N ) 2 ) \sigma\sqrt{\ln(2(n+N)^2)} σ ln ( 2 ( n + N ) 2 ) , so that h ≤ r h\le r h ≤ r .
Let N o u t N_{\mathrm{out}} N out be the number of training samples outside B B B . In each coordinate, at most one of n + 1 n+1 n + 1 i.i.d. values is strictly smaller (larger) than all the others, so by exchangeability a fresh sample lies outside B B B with probability at most 2 e / ( n + 1 ) 2e/(n+1) 2 e / ( n + 1 ) . Hence E [ N o u t / N ] ≤ 2 e / ( n + 1 ) \mathbb{E}[N_{\mathrm{out}}/N]\le2e/(n+1) E [ N out / N ] ≤ 2 e / ( n + 1 ) , and N o u t / N ≤ τ / 2 N_{\mathrm{out}}/N\le\tau/2 N out / N ≤ τ /2 with probability at least 1 − 4 e / ( τ ( n + 1 ) ) 1-4e/(\tau(n+1)) 1 − 4 e / ( τ ( n + 1 )) by Markov's inequality. We work on this event and on the event above. On the former event, N X c = N − N o u t ≥ N / 2 N_{\mathcal{X}_c}=N-N_{\mathrm{out}}\ge N/2 N X c = N − N out ≥ N /2 .
By Algorithm 2, Theorem 1 and Proposition 2, the bounds computed by the call are one-sided Clopper–Pearson bounds of level β ′ / ( 2 ( M + 1 ) ) = e − Λ \beta'/(2(M+1))=e^{-\Lambda} β ′ / ( 2 ( M + 1 )) = e − Λ . Let p ˉ \bar{p} p ˉ be such an upper bound for Z Z Z successes in n ′ n' n ′ trials, i.e., P ( Bin ( n ′ , p ˉ ) ≤ Z ) = e − Λ \mathbb{P}(\operatorname{Bin}(n',\bar{p})\le Z)=e^{-\Lambda} P ( Bin ( n ′ , p ˉ ) ≤ Z ) = e − Λ , and let p ˉ = p ˉ − Z / n ′ \bar{p}=\bar{p}-Z/n' p ˉ = p ˉ − Z / n ′ . If a > 0 a>0 a > 0 , Hoeffding's inequality gives
e − Λ = P ( Bin ( n ′ , p ˉ ) − n ′ p ˉ ≤ − n ′ a ) ≤ exp ( − 2 n ′ a 2 ) e^{-\Lambda}=\mathbb{P}(\operatorname{Bin}(n',\bar{p})-n'\bar{p}\le-n'a)\le\exp(-2n'a^2) e − Λ = P ( Bin ( n ′ , p ˉ ) − n ′ p ˉ ≤ − n ′ a ) ≤ exp ( − 2 n ′ a 2 )
⟹ a ≤ Λ 2 n ′ . (16) \Longrightarrow\quad a\le\sqrt{\frac{\Lambda}{2n'}}. \tag*{(16)} ⟹ a ≤ 2 n ′ Λ . (16)
The same bound holds for a lower bound p ‾ \underline{p} p , defined by P ( Bin ( n ′ , p ‾ ) ≥ Z ) = e − Λ \mathbb{P}(\operatorname{Bin}(n',\underline{p})\ge Z)=e^{-\Lambda} P ( Bin ( n ′ , p ) ≥ Z ) = e − Λ , with a : = Z / n ′ − p ‾ a:=Z/n'-\underline{p} a := Z / n ′ − p . The call uses n ′ = N n'=N n ′ = N trials for p ˉ u \bar{p}_u p ˉ u (with Z = N o u t Z=N_{\mathrm{out}} Z = N out ) and n ′ = N X c ≥ N / 2 n'=N_{\mathcal{X}_c}\ge N/2 n ′ = N X c ≥ N /2 trials for the bounds of Theorem 1 (with Z = Z i Z=Z_i Z = Z i ), so (17) gives deviations of at most Λ / N = t \sqrt{\Lambda/N}=t Λ/ N = t . Hence p ˉ u ≤ N o u t / N + t ≤ τ / 2 + t \bar{p}_u\le N_{\mathrm{out}}/N+t\le\tau/2+t p ˉ u ≤ N out / N + t ≤ τ /2 + t , and the bounds of Theorem 1 satisfy q i − p ˉ ℓ ( i ) ≤ t q_i-\bar{p}_{\ell}^{(i)}\le t q i − p ˉ ℓ ( i ) ≤ t and p ˉ u ( i ) − q i ≤ t \bar{p}_{u}^{(i)}-q_i\le t p ˉ u ( i ) − q i ≤ t , with q i : = Z i / N X c q_i:=Z_i/N_{\mathcal{X}_c} q i := Z i / N X c .
Any feasible ( ω , γ ) (\omega,\gamma) ( ω , γ ) of (5) thus has ∑ i γ i ≥ ∑ i min { ω i , q i } = 1 − 1 2 ∥ ω − q ∥ 1 ≥ 1 − M t / 2 \sum_i\gamma_i\ge\sum_i\min\{\omega_i,q_i\}=1-\frac{1}{2}\lVert\omega-q\rVert_1\ge1-Mt/2 ∑ i γ i ≥ ∑ i min { ω i , q i } = 1 − 2 1 ∥ ω − q ∥ 1 ≥ 1 − M t /2 . By (16), the diagonal cost coefficients are at most ( 2 κ h M − 1 / e ) ρ (2\kappa hM^{-1/e})^\rho ( 2 κh M − 1/ e ) ρ , and all others at most diam ( B ) ρ ≤ ( κ h ) ρ \operatorname{diam}(B)^\rho\le(\kappa h)^\rho diam ( B ) ρ ≤ ( κh ) ρ (empty cells have zero coefficients, and atoms without mass play no role). As the diagonal mass is at most 1 1 1 and the off-diagonal mass at most M t / 2 Mt/2 M t /2 , ϵ ρ ≤ ( 2 κ h M − 1 / e ) ρ + ( κ h ) ρ M t / 2 \epsilon^\rho\le(2\kappa hM^{-1/e})^\rho+(\kappa h)^\rho Mt/2 ϵ ρ ≤ ( 2 κh M − 1/ e ) ρ + ( κh ) ρ M t /2 , and the claim follows from ( a ρ + b ρ ) 1 / ρ ≤ a + b (a^\rho+b^\rho)^{1/\rho}\le a+b ( a ρ + b ρ ) 1/ ρ ≤ a + b and h ≤ r h\le r h ≤ r . □
Auxiliary result #3: tight certificates. Finally, we show that the learner can be made arbitrarily tight along a sequence of calls. Consider stages s ∈ N s\in\mathbb{N} s ∈ N . In the setting of Lemma 8, we index by s s s each quantity in stage s s s . Further, for each e ∈ ( 0 , 1 ] e\in(0,1] e ∈ ( 0 , 1 ] , let N ˉ s = ( 1 − c ) N ˉ s \bar{N}_s=(1-c)\bar{N}_s N ˉ s = ( 1 − c ) N ˉ s and n s = c N ˉ s ∈ N n_s=c\bar{N}_s\in\mathbb{N} n s = c N ˉ s ∈ N (so that N ˉ s = N s + n s \bar{N}_s=N_s+n_s N ˉ s = N s + n s ). We assume the following schedule conditions , as s → ∞ s\to\infty s → ∞ :
N ˉ s , M s → ∞ , r s M s − 1 / e → 0 and M s 2 Λ s r s 2 ρ = o ( N s ) . \bar{N}_s,M_s\to\infty,\qquad r_sM_s^{-1/e}\to0\quad\text{and}\quad M_s^2\Lambda_sr_s^{2\rho}=o(N_s). N ˉ s , M s → ∞ , r s M s − 1/ e → 0 and M s 2 Λ s r s 2 ρ = o ( N s ) .
For instance, N ˉ s = 2 s \bar{N}_s=2s N ˉ s = 2 s with N s = n s = s N_s=n_s=s N s = n s = s (i.e., c = 1 2 c=\frac12 c = 2 1 ), M s = ⌈ s 1 / 4 ⌉ M_s=\lceil s^{1/4}\rceil M s = ⌈ s 1/4 ⌉ and β s ′ = a / s 2 \beta'_s=a/s^2 β s ′ = a / s 2 for some a > 0 a>0 a > 0 (e.g., a share of the polynomial schedule β s ′ = 6 β / ( π 2 s 2 ) \beta'_s=6\beta/(\pi^2s^2) β s ′ = 6 β / ( π 2 s 2 ) ) satisfy them: s 1 / 4 ≤ M s ≤ 2 s 1 / 4 s^{1/4}\le M_s\le2s^{1/4} s 1/4 ≤ M s ≤ 2 s 1/4 , Λ s = O ( ln s ) \Lambda_s=O(\ln s) Λ s = O ( ln s ) and r s = O ( ln s ) r_s=O(\sqrt{\ln s}) r s = O ( ln s ) , so r s M s − 1 / e = O ( ( ln s ) 1 / 2 s − 1 / ( 4 e ) ) → 0 r_sM_s^{-1/e}=O((\ln s)^{1/2}s^{-1/(4e)})\to0 r s M s − 1/ e = O (( ln s ) 1/2 s − 1/ ( 4 e ) ) → 0 and M s 2 Λ s r s 2 ρ = O ( s 1 / 2 ( ln s ) 1 + ρ ) = o ( s ) = o ( N s ) M_s^2\Lambda_sr_s^{2\rho}=O(s^{1/2}(\ln s)^{1+\rho})=o(s)=o(N_s) M s 2 Λ s r s 2 ρ = O ( s 1/2 ( ln s ) 1 + ρ ) = o ( s ) = o ( N s ) .
Lemma 9 (Tight certificates). Under the schedule conditions above, for every τ ∈ ( 0 , 1 ] \tau\in(0,1] τ ∈ ( 0 , 1 ] there is s τ s_\tau s τ such that, for all s ≥ s τ s\ge s_\tau s ≥ s τ and every σ \sigma σ -sub-Gaussian distribution on R e \mathbb{R}^{e} R e , the s s s -th call returns a radius ϵ ≤ τ \epsilon\le\tau ϵ ≤ τ and an escaped-mass upper bound p u ≤ τ p_u\le\tau p u ≤ τ with probability at least q s τ : = 1 − 4 e / ( τ ( n s + 1 ) ) − 1 / N ˉ s q_s^\tau:=1-4e/(\tau(n_s+1))-1/\bar{N}_s q s τ := 1 − 4 e / ( τ ( n s + 1 )) − 1/ N ˉ s , and q s τ → 1 q_s^\tau\to1 q s τ → 1 as s → ∞ s\to\infty s → ∞ .
Proof. Fix τ ∈ ( 0 , 1 ] \tau\in(0,1] τ ∈ ( 0 , 1 ] . Since M s 2 r s 2 ρ ≥ ( 2 σ ln 2 ) 2 ρ M_s^2r_s^{2\rho}\ge(2\sigma\sqrt{\ln2})^{2\rho} M s 2 r s 2 ρ ≥ ( 2 σ ln 2 ) 2 ρ , the schedule conditions give t s 2 = Λ s / N s → 0 t_s^2=\Lambda_s/N_s\to0 t s 2 = Λ s / N s → 0 , and also r s M s − 1 / e → 0 r_sM_s^{-1/e}\to0 r s M s − 1/ e → 0 and r s ( M s t s ) 1 / ρ = ( M s 2 Λ s r s 2 ρ / N s ) 1 / ( 2 ρ ) → 0 r_s(M_st_s)^{1/\rho}=(M_s^2\Lambda_sr_s^{2\rho}/N_s)^{1/(2\rho)}\to0 r s ( M s t s ) 1/ ρ = ( M s 2 Λ s r s 2 ρ / N s ) 1/ ( 2 ρ ) → 0 . Hence there is s τ s_\tau s τ such that, for all s ≥ s τ s\ge s_\tau s ≥ s τ , t s ≤ τ / 2 t_s\le\tau/2 t s ≤ τ /2 and κ r s ( 2 M s − 1 / e + ( M s t s ) 1 / ρ ) ≤ τ \kappa r_s(2M_s^{-1/e}+(M_st_s)^{1/\rho})\le\tau κ r s ( 2 M s − 1/ e + ( M s t s ) 1/ ρ ) ≤ τ . For such s s s and any σ \sigma σ -sub-Gaussian distribution, Lemma 8 gives p u ≤ τ / 2 + t s ≤ τ p_u \le\tau/2 + t_s \le\tau p u ≤ τ /2 + t s ≤ τ and ϵ ≤ κ r s M s − 1 / e + ( M s t s / 2 ) 1 / p ≤ τ \epsilon\le\kappa r_s M_s^{-1/e} + (M_s t_s/2)^{1/p} \le\tau ϵ ≤ κ r s M s − 1/ e + ( M s t s /2 ) 1/ p ≤ τ with probability at least 1 − 4 e / ( τ ( n s + 1 ) ) − 1 / N ˉ s = q s τ 1 - 4e/(\tau(n_s + 1)) - 1/\bar{N}_s = q_s^\tau 1 − 4 e / ( τ ( n s + 1 )) − 1/ N ˉ s = q s τ , and q s τ → 1 q_s^\tau\to1 q s τ → 1 as N ˉ s → ∞ \bar{N}_s \to\infty N ˉ s → ∞ .
In Algorithm 1, the two learning calls of stage s s s are instances of the s s s -th call above: the root call, with ( e , N ˉ s , M s , β s ′ ) = ( d , N ( s ) , M ( s ) , ζ β s ) (e,\bar{N}_s,M_s,\beta'_s) = (d,N^{(s)},M^{(s)},\zeta\beta_s) ( e , N ˉ s , M s , β s ′ ) = ( d , N ( s ) , M ( s ) , ζ β s ) , and the noise call, with ( e , N ˉ s , M s , β s ′ ) = ( w , N ω ( s ) , M ω ( s ) , ( 1 − ζ ) β s ) (e,\bar{N}_s,M_s,\beta'_s) = (w,N_\omega^{(s)},M_\omega^{(s)},(1-\zeta)\beta_s) ( e , N ˉ s , M s , β s ′ ) = ( w , N ω ( s ) , M ω ( s ) , ( 1 − ζ ) β s ) . We assume that, for both, a fraction c ∈ ( 0 , 1 ) c \in(0,1) c ∈ ( 0 , 1 ) of the samples is used for pre-training and that the schedule conditions hold.
Before moving on, we need to introduce two new notions. First, by Assumption 2, there is p † > 0 p^\dagger> 0 p † > 0 such that sup Q ∈ B Δ ( P u ~ k − 1 ) Q ( O ) ≤ ϵ O − p † \sup_{Q\in\mathcal{B}_\Delta(P_{\tilde{u}_{k-1}})} Q(O) \le\epsilon_O - p^\dagger sup Q ∈ B Δ ( P u ~ k − 1 ) Q ( O ) ≤ ϵ O − p † for k ∈ [ H ˉ ] k \in[\bar{H}] k ∈ [ H ˉ ] and sup Q ∈ B Δ ( P u ~ H ˉ − 1 ) Q ( X ∖ T ) ≤ ϵ T − p † \sup_{Q\in\mathcal{B}_\Delta(P_{\tilde{u}_{\bar{H}-1}})} Q(\mathcal{X}\setminus\mathcal{T}) \le\epsilon_T - p^\dagger sup Q ∈ B Δ ( P u ~ H ˉ − 1 ) Q ( X ∖ T ) ≤ ϵ T − p † .
Further, for η > 0 \eta> 0 η > 0 , define U η ( u ) : = { u ′ ∈ U : ∥ u ′ − u ∥ ≤ η } \mathcal{U}_\eta(u) := \{u' \in\mathcal{U} : \lVert u' - u\rVert\le\eta\} U η ( u ) := { u ′ ∈ U : ∥ u ′ − u ∥ ≤ η } . A controller ( u 0 , … , u j − 1 ) (u_0,\ldots,u_{j-1}) ( u 0 , … , u j − 1 ) is η \eta η -aligned (of length j j j ) if u i ∈ U η ( u ~ i ) u_i \in\mathcal{U}_\eta(\tilde{u}_i) u i ∈ U η ( u ~ i ) for all i < j i < j i < j . Coupling the trajectories of an η \eta η -aligned controller ( u 0 , … , u j ) (u_0,\ldots,u_j) ( u 0 , … , u j ) of length j + 1 ≤ H ˉ j+1 \le\bar{H} j + 1 ≤ H ˉ and of u ~ j \tilde{\boldsymbol{u}}_j u ~ j through the same x 0 x_0 x 0 and noise sequence, the Lipschitz continuity of f f f gives
W p ( P x j + 1 ( u 0 , … , u j ) , P x j + 1 u ~ j ) ≤ C η (17) \mathbb{W}_p\left(P_{x_{j+1}}^{(u_0,\ldots,u_j)},P_{x_{j+1}}^{\tilde{\boldsymbol{u}}_j}\right) \le C\eta \tag*{(17)} W p ( P x j + 1 ( u 0 , … , u j ) , P x j + 1 u ~ j ) ≤ C η (17)
for a constant C C C depending only on L f L_f L f and H ˉ \bar{H} H ˉ . Finally, let p η : = min k < H ˉ Leb ( U η ( u ~ k ) ) / Leb ( U ) p_\eta:= \min_{k<\bar{H}} \operatorname{Leb}(\mathcal{U}_\eta(\tilde{u}_k))/\operatorname{Leb}(\mathcal{U}) p η := min k < H ˉ Leb ( U η ( u ~ k )) / Leb ( U ) , which is positive as U \mathcal{U} U is bounded and has positive Lebesgue measure in every ball centered at its points.
Step 4: a stage advances the forest. Let F s \mathcal{F}_s F s be the forest at the beginning of stage s s s and F s ′ \mathcal{F}'_s F s ′ the σ \sigma σ -algebra generated by the data consumed and the random draws made up to the end of stage s s s . Let the largest η \eta η -aligned depth in the forest F s \mathcal{F}_s F s be J s : = max { j ≤ H ˉ − 1 : F s J_s := \max\{j \le\bar{H}-1 : \mathcal{F}_s J s := max { j ≤ H ˉ − 1 : F s has a node whose backtrack is η \eta η -aligned of length j } j\} j } . Let Y s ∈ F s ′ Y_s \in\mathcal{F}'_s Y s ∈ F s ′ be the event that the algorithm returns at stage s s s or J s + 1 > J s J_{s+1} > J_s J s + 1 > J s .
Lemma 10 (Advance). Fix η > 0 \eta> 0 η > 0 and τ ˉ ∈ ( 0 , 1 ] \bar{\tau} \in(0,1] τ ˉ ∈ ( 0 , 1 ] such that 2 τ ˉ + C η ≤ Δ 2\bar{\tau}+C\eta\le\Delta 2 τ ˉ + C η ≤ Δ and 2 τ ˉ ≤ p † 2\bar{\tau} \le p^\dagger 2 τ ˉ ≤ p † . On the event that the algorithm has not returned before stage s s s , under the schedule conditions, there is s 0 ≥ 2 s_0 \ge2 s 0 ≥ 2 such that, for all s ≥ s 0 s \ge s_0 s ≥ s 0 , P ( Y s ∣ F s − 1 ′ ) ≥ λ 1 λ 2 p η K 2 ( N i t e r + 1 ) s \mathbb{P}(Y_s \mid\mathcal{F}'_{s-1}) \ge\frac{\lambda_1\lambda_2p_\eta^K}{2(N_{\mathrm{iter}}+1)s} P ( Y s ∣ F s − 1 ′ ) ≥ 2 ( N iter + 1 ) s λ 1 λ 2 p η K , where K K K is the number of candidate controls sampled by Propagate.
Proof. First, for any τ ∈ ( 0 , 1 ] \tau\in(0,1] τ ∈ ( 0 , 1 ] , define q s q_s q s as the sum of the probabilities q s τ q_s^\tau q s τ of Lemma 9 for the root call and for the noise call of stage s s s , minus 1, i.e. q s = q s r o o t , τ + q s n o i s e , τ − 1 q_s = q_s^{\mathrm{root},\tau} + q_s^{\mathrm{noise},\tau} - 1 q s = q s root , τ + q s noise , τ − 1 . As q s → 1 q_s \to1 q s → 1 , β s → 0 \beta_s \to0 β s → 0 and M ( s ) → ∞ M(s) \to\infty M ( s ) → ∞ , there is s 0 ≥ 2 s_0 \ge2 s 0 ≥ 2 such that, for all s ≥ s 0 s \ge s_0 s ≥ s 0 , s ≥ s τ s \ge s_\tau s ≥ s τ for both calls, q s − β s ≥ 1 2 q_s-\beta_s \ge\frac{1}{2} q s − β s ≥ 2 1 and 2 κ ∥ X ∥ ∞ M ( s ) − 1 / d ≤ τ 2\kappa\lVert\mathcal{X}\rVert_\infty M(s)^{-1/d} \le\tau 2 κ ∥ X ∥ ∞ M ( s ) − 1/ d ≤ τ .
Work on the event that the algorithm has not returned before stage s s s . Let ν ⋆ ∈ F s \nu^\star\in\mathcal{F}_s ν ⋆ ∈ F s be a node whose backtrack u s \boldsymbol{u}_s u s is η \eta η -aligned of length J s J_s J s . Let G s G_s G s be the event intersecting: (1) SelectRoot returns an escaped-mass upper bound at most τ \tau τ . Since F s \mathcal{F}_s F s has s − 1 s-1 s − 1 trees with at most N i t e r + 1 N_{\mathrm{iter}}+1 N iter + 1 nodes each, and SelectRoot draws uniformly a tree and a node of it with probability λ 1 , λ 2 \lambda_1,\lambda_2 λ 1 , λ 2 , respectively, this has probability at least λ 1 λ 2 / ( s ( N i t e r + 1 ) ) \lambda_1\lambda_2/(s(N_{\mathrm{iter}}+1)) λ 1 λ 2 / ( s ( N iter + 1 )) ; (2) both learning calls of stage s s s are valid and return a radius and an escaped-mass upper bound at most τ \tau τ . Given (1), u s u_s u s is fixed and the data of stage s s s are fresh i.i.d. samples of P x J s u s P^{u_s}_{x_{J_s}} P x J s u s , which is sub-Gaussian as X \mathcal{X} X bounded, and P ω P_\omega P ω also sub-Gaussian. So the calls are valid with probability at least 1 − β s 1-\beta_s 1 − β s (same step), and, by Lemma 9, tight with probability at least q s q_s q s —thus by the union bound, they hold together with probability at least q s − β s ≥ 1 2 q_s-\beta_s \ge\frac{1}{2} q s − β s ≥ 2 1 ; (3) the K K K candidates drawn by Propagate at the first iteration lie in U η ( u ~ J s ) \mathcal{U}_\eta(\tilde{u}_{J_s}) U η ( u ~ J s ) , which has probability at least p η K p_\eta^K p η K . Hence, there exists s 0 s_0 s 0 such that P ( G s ∣ F s − 1 ′ ) ≥ λ 1 λ 2 p η K 2 ( N i t e r + 1 ) s \mathbb{P}(G_s\mid\mathcal{F}'_{s-1}) \ge\frac{\lambda_1\lambda_2p_\eta^K}{2(N_{\mathrm{iter}}+1)s} P ( G s ∣ F s − 1 ′ ) ≥ 2 ( N iter + 1 ) s λ 1 λ 2 p η K for any s ≥ s 0 s \ge s_0 s ≥ s 0 . We now need to show that G s ⊆ Y s G_s \subseteq Y_s G s ⊆ Y s for s ≥ s 0 s \ge s_0 s ≥ s 0 .
On G s G_s G s , by construction, ( u s , u ⋆ ) (u_s,u^\star) ( u s , u ⋆ ) is η \eta η -aligned of length J s + 1 J_s+1 J s + 1 . It only remains to check whether this node will be accepted into the tree. From our propagation, # B ( P ˉ x J s + 1 u J s + 1 ) \#\mathcal{B}(\bar{P}_{x_{J_s+1}}^{\boldsymbol{u}_{J_s+1}}) # B ( P ˉ x J s + 1 u J s + 1 ) has a radius of at most L τ \mathcal{L}\tau L τ , where L \mathcal{L} L is some finite Lipschitz constant. Also, the propagated escaped mass is at most 2 τ 2\tau 2 τ . The compression step adds at most 2 κ ∥ X ∥ ∞ M ( s ) − 1 / d 2\kappa\lVert\mathcal{X}\rVert_\infty M(s)^{-1/d} 2 κ ∥ X ∥ ∞ M ( s ) − 1/ d , which is at most τ \tau τ from our first paragraph. In particular, for τ = τ ˉ 2 ( τ ˉ + 1 ) \tau=\frac{\bar{\tau}}{2(\bar{\tau}+1)} τ = 2 ( τ ˉ + 1 ) τ ˉ , it holds that both the radius after compression and the escaped mass upper bound are at most τ ˉ \bar{\tau} τ ˉ .
Then, W p ( P ˉ x J s + 1 ( u s , u ⋆ ) , P ˉ x J s + 1 u ~ J s ) ≤ C η ≤ Δ − 2 τ ˉ \mathbb{W}_p(\bar{P}_{x_{J_s+1}}^{(u_s,u^\star)},\bar{P}_{x_{J_s+1}}^{\tilde{\boldsymbol{u}}_{J_s}}) \le C\eta\le\Delta-2\bar{\tau} W p ( P ˉ x J s + 1 ( u s , u ⋆ ) , P ˉ x J s + 1 u ~ J s ) ≤ C η ≤ Δ − 2 τ ˉ using (17) and the assumption on η \eta η . To conclude, from Lemma 7, we have that for this constructed node ρ ( O ) ≤ ϵ O − p † + 2 τ ˉ ≤ ϵ O \rho(O) \le\epsilon_O-p^\dagger+2\bar{\tau} \le\epsilon_O ρ ( O ) ≤ ϵ O − p † + 2 τ ˉ ≤ ϵ O , thus passing ValidityCheck. If J s + 1 < H ˉ J_s+1<\bar{H} J s + 1 < H ˉ , the new node is added to the tree, which joins the forest at the end of the stage, so J s + 1 ≥ J s + 1 > J s J_{s+1}\ge J_s+1>J_s J s + 1 ≥ J s + 1 > J s . If J s + 1 = H ˉ J_s+1=\bar{H} J s + 1 = H ˉ , the same computation with X ∖ T \mathcal{X}\setminus\mathcal{T} X ∖ T and the second inequality defining p † p^\dagger p † gives ρ ( X ∖ T ) ≤ ϵ T − p † + 2 τ ˉ ≤ ϵ T \rho(\mathcal{X}\setminus\mathcal{T}) \le\epsilon_T-p^\dagger+2\bar{\tau}\le\epsilon_T ρ ( X ∖ T ) ≤ ϵ T − p † + 2 τ ˉ ≤ ϵ T , so the new node also passes TargetCheck and the algorithm returns at stage s s s . □ \square □
Proof of Theorem 4. Let Ret \operatorname{Ret} Ret be the event that the algorithm returns. We show that P ( Ret ) = 1 \mathbb{P}(\operatorname{Ret})=1 P ( Ret ) = 1 , i.e., that the algorithm returns within finitely many stages. Let c ⋆ = λ 1 λ 2 p η K 2 ( N i t e r + 1 ) c_\star=\frac{\lambda_1\lambda_2p_\eta^K}{2(N_{\mathrm{iter}}+1)} c ⋆ = 2 ( N iter + 1 ) λ 1 λ 2 p η K . On Ret c \operatorname{Ret}^{c} Ret c , Lemma 10 holds for all s ≥ s 0 s\ge s_0 s ≥ s 0 , so ∑ s ≥ s 0 P ( Y s ∣ F s − 1 ′ ) ≥ ∑ s ≥ s 0 c ⋆ / s = ∞ \sum_{s\ge s_0}\mathbb{P}(Y_s\mid\mathcal{F}'_{s-1})\ge\sum_{s\ge s_0}c_\star/s=\infty ∑ s ≥ s 0 P ( Y s ∣ F s − 1 ′ ) ≥ ∑ s ≥ s 0 c ⋆ / s = ∞ . By Lévy’s extension of the Borel–Cantelli lemma (for events Y s ∈ F s ′ Y_s\in\mathcal{F}'_s Y s ∈ F s ′ ), almost surely ∑ s P ( Y s ∣ F s − 1 ′ ) = ∞ \sum_s\mathbb{P}(Y_s\mid\mathcal{F}'_{s-1})=\infty ∑ s P ( Y s ∣ F s − 1 ′ ) = ∞ if and only if Y s Y_s Y s occurs infinitely often, Y s Y_s Y s then occurs infinitely often, almost surely on Ret c \operatorname{Ret}^{c} Ret c . But without returning, Y s Y_s Y s means J s + 1 > J s J_{s+1}>J_s J s + 1 > J s , which can happen at most H ˉ − 1 \bar{H}-1 H ˉ − 1 times, as J s ∈ { 0 , … , H ˉ − 1 } J_s\in\{0,\ldots,\bar{H}-1\} J s ∈ { 0 , … , H ˉ − 1 } is nondecreasing. Hence P ( Ret c ) = 0 \mathbb{P}(\operatorname{Ret}^{c})=0 P ( Ret c ) = 0 .
Promising controller selection heuristics
In this Section, we present the heuristics employed by SelectRoot (Algorithm 3) to select a promising sequence of controls after each learning stage. This heuristic is based on a simple trajectory tracking rule; however, as highlighted in the main text, this represents only one of many possible strategies. Intuitively, we first execute a standard RRT on a deterministic variant of System 3 to rapidly generate multiple reference trajectories to the target set – a step we term Informed Search . We then select one of these trajectories and attempt to track using Algorithm 1.
Prior to executing Algorithm 1, we run a standard RRT on a deterministic version of System 3, wherein the initial state is set to the empirical mean of P x 0 \mathbb{P}_{x_0} P x 0 (estimated via sampling) and the process noise to zero (the mean of P ω \mathbb{P}_\omega P ω in all our benchmarks). The determinism reduces the computational overhead to a negligible fraction of that incurred by the full stochastic algorithm. Additionally, we utilize goal bias (probability 0.3) in the RRT, as we observe empirically that it significantly improves its efficiency, and inflate its unsafe boxes by a margin (Table 2) to leave clearance around obstacles. Figure 6 illustrates the tree generated by informed search after 20,000 iterations for the Double Integrator environment.
Figure 6. Informed search heuristic for Double Integrator (only the three first state dimensions are depicted).
From the set of all trajectories discovered during the Informed Search phase, we then select a reference trajectory that maximizes the minimum distance to the avoid sets across all time steps. The resulting selected trajectory is also depicted in Figure 6 for the Double Integrator . This reference trajectory is computed once per benchmark (with a fixed seed) and shared across all trials and methods. Its computation time is excluded from the reported planning times.
SelectRoot: Promising Controller and Node Selection
The promising node of a tree, returned by SelectRoot (Algorithm 3) when it does not explore, is a non-root node n ⋆ n^\star n ⋆ of the tree. The stage then re-learns its root from the state distribution induced by the controller backtrack(n ⋆ n^\star n ⋆ ) leading to n ⋆ n^\star n ⋆ (Lines 3–6). Let x ˉ n \bar{x}_n x ˉ n be the mean of the center distribution of a node n n n , x ˉ r o o t \bar{x}_{\mathrm{root}} x ˉ root that of the root, and x r e f = ( x ~ 1 , … , x ~ T ) \mathbf{x}_{\mathrm{ref}} = (\tilde{x}_1, \ldots, \tilde{x}_T) x ref = ( x ~ 1 , … , x ~ T ) the reference trajectory from Informed Search . The rule has two cases:
(a) Target nearly certified. If some node of the tree has 1 − π ( X ∖ T ) > 0.5 1-\pi(\mathcal{X}\setminus\mathcal{T}) > 0.5 1 − π ( X ∖ T ) > 0.5 , i.e., its TargetCheck bound (Eq. (10) ) certifies a target probability above 0.5, select the non-root node whose center is closest to the reach sets, measured by the probability-weighted average distance from its support points to the nearest reach-set center.
(b) Reference tracking. Otherwise, select the node that has advanced the farthest along the reference trajectory x r e f \mathbf{x}_{\mathrm{ref}} x ref while staying close to it. Only the part of x r e f \mathbf{x}_{\mathrm{ref}} x ref ahead of the root matters, i.e., the states after the one closest to x ˉ r o o t \bar{x}_{\mathrm{root}} x ˉ root , and the selection has two steps:
Candidates. Keep the 50 nodes whose means are the farthest from x ˉ r o o t \bar{x}_{\mathrm{root}} x ˉ root , which favors exploration.
Progress. A candidate n n n reaches the state x ~ i \tilde{x}_i x ~ i if ∥ x ˉ n − x ~ i ∥ ≤ d ˉ \lVert\bar{x}_n-\tilde{x}_i\rVert\le\bar{d} ∥ x ˉ n − x ~ i ∥ ≤ d ˉ , where d ˉ \bar{d} d ˉ is the average distance between consecutive states ahead. Select the candidate that reaches the state with the largest index i i i , i.e., the farthest along x r e f \mathbf{x}_{\mathrm{ref}} x ref .
The heuristic balances exploration (nodes far from the root) and guidance (progress along the reference), and has demonstrated strong empirical performance across the experiments considered in this work.
Experimental details
We summarize the system dynamics, and environment specifications used in the experiments presented in § 5 .
Autonomous Vehicle Maze [1]
The AV Maze benchmark from [1 ] uses a reduced autonomous vehicle model with state
x k = ( p x , k , p y , k , θ k ) ∈ [ 0 , 4 ] × [ 0 , 10 ] × [ − π − 0.4 , π + 0.4 ] , x_k=(p_{x,k},p_{y,k},\theta_k)\in[0,4]\times[0,10]\times[-\pi-0.4,\pi+0.4], x k = ( p x , k , p y , k , θ k ) ∈ [ 0 , 4 ] × [ 0 , 10 ] × [ − π − 0.4 , π + 0.4 ] ,
where ( p x , k , p y , k ) (p_{x,k},p_{y,k}) ( p x , k , p y , k ) is position and θ k \theta_k θ k is the heading angle, both at time k k k . The control input is given by u k = ( v k , δ k ) ∈ [ − 1 , 1 ] 2 u_k=(v_k,\delta_k)\in[-1,1]^2 u k = ( v k , δ k ) ∈ [ − 1 , 1 ] 2 , where v k v_k v k represents the longitudinal velocity and δ k \delta_k δ k the steering angle.
Let
α k = arctan ( tan ( δ k ) 2 ) . \alpha_k=\arctan\left(\frac{\tan(\delta_k)}{2}\right). α k = arctan ( 2 tan ( δ k ) ) .
We consider the dynamics to be described by an additive noise dynamical process with x k + 1 = f ( x k , u k , ω k ) = g ( x k , u k ) + ω k x_{k+1}=f(x_k,u_k,\omega_k)=g(x_k,u_k)+\omega_k x k + 1 = f ( x k , u k , ω k ) = g ( x k , u k ) + ω k , where the function g g g is given by
p x , k + 1 = p x , k + τ v k cos ( θ k + α k ) cos ( α k ) , p y , k + 1 = p y , k + τ v k sin ( θ k + α k ) cos ( α k ) , θ k + 1 = wrap [ − π , π ] ( θ k + τ v k tan ( δ k ) ) . \begin{aligned}
p_{x,k+1}&=p_{x,k}+\tau v_k\frac{\cos(\theta_k+\alpha_k)}{\cos(\alpha_k)},\\
p_{y,k+1}&=p_{y,k}+\tau v_k\frac{\sin(\theta_k+\alpha_k)}{\cos(\alpha_k)},\\
\theta_{k+1}&=\operatorname{wrap}_{[-\pi,\pi]}(\theta_k+\tau v_k\tan(\delta_k)).
\end{aligned} p x , k + 1 p y , k + 1 θ k + 1 = p x , k + τ v k cos ( α k ) cos ( θ k + α k ) , = p y , k + τ v k cos ( α k ) sin ( θ k + α k ) , = wrap [ − π , π ] ( θ k + τ v k tan ( δ k )) .
with sampling time τ = 0.5 \tau=0.5 τ = 0.5 . For any u ∈ U u\in\mathcal{U} u ∈ U , the Lipschitz constant of g ( ⋅ , u ) g(\cdot,u) g ( ⋅ , u ) is
L g u = 1 + σ 2 2 + σ 2 σ 2 + 4 , \mathcal{L}_{g_u}=\sqrt{1+\frac{\sigma^2}{2}+\frac{\sigma}{2}\sqrt{\sigma^2+4}}, L g u = 1 + 2 σ 2 + 2 σ σ 2 + 4 ,
σ = 0.5 ∣ v ∣ cos ( α ) = 0.5 ∣ v ∣ 1 + tan 2 ( δ ) 4 , \sigma=\frac{0.5\lvert v\rvert}{\cos(\alpha)}=0.5\lvert v\rvert\sqrt{1+\frac{\tan^2(\delta)}{4}}, σ = cos ( α ) 0.5 ∣ v ∣ = 0.5 ∣ v ∣ 1 + 4 tan 2 ( δ ) ,
with α \alpha α being the slip angle defined above. This constant is tight: the Jacobian of g ( ⋅ , u ) g(\cdot,u) g ( ⋅ , u ) is I + w e 3 T I+w e_3^\mathsf{T} I + w e 3 T with ∥ w ∥ 2 = σ \lVert w\rVert_2=\sigma ∥ w ∥ 2 = σ independently of the state, and the expression above is its spectral norm. Over u u u , it ranges between [ 1 , 1.3659 ] [1,1.3659] [ 1 , 1.3659 ] .
The unsafe set is defined as O = O 1 ∪ O 2 ∪ O 3 \mathcal{O}=\mathcal{O}_1\cup\mathcal{O}_2\cup\mathcal{O}_3 O = O 1 ∪ O 2 ∪ O 3 , where
O 1 = [ 1.00 , 1.12 ] × [ 0 , 8.6 ] × [ − π − 0.4 , π + 0.4 ] , O 2 = [ 2.24 , 2.36 ] × [ 0 , 4.6 ] × [ − π − 0.4 , π + 0.4 ] , O 3 = [ 2.24 , 2.36 ] × [ 6.4 , 10.0 ] × [ − π − 0.4 , π + 0.4 ] . \begin{aligned}
\mathcal{O}_1&=[1.00,1.12]\times[0,8.6]\times[-\pi-0.4,\pi+0.4],\\
\mathcal{O}_2&=[2.24,2.36]\times[0,4.6]\times[-\pi-0.4,\pi+0.4],\\
\mathcal{O}_3&=[2.24,2.36]\times[6.4,10.0]\times[-\pi-0.4,\pi+0.4].
\end{aligned} O 1 O 2 O 3 = [ 1.00 , 1.12 ] × [ 0 , 8.6 ] × [ − π − 0.4 , π + 0.4 ] , = [ 2.24 , 2.36 ] × [ 0 , 4.6 ] × [ − π − 0.4 , π + 0.4 ] , = [ 2.24 , 2.36 ] × [ 6.4 , 10.0 ] × [ − π − 0.4 , π + 0.4 ] .
The reach set is given by T = [ 2.85 , 3.75 ] × [ 0.22 , 0.97 ] × [ − π − 0.4 , π + 0.4 ] \mathcal{T}=[2.85,3.75]\times[0.22,0.97]\times[-\pi-0.4,\pi+0.4] T = [ 2.85 , 3.75 ] × [ 0.22 , 0.97 ] × [ − π − 0.4 , π + 0.4 ] . Risk thresholds are ϵ O = 0.05 \epsilon_{\mathcal{O}}=0.05 ϵ O = 0.05 and ϵ T = 0.05 \epsilon_{\mathcal{T}}=0.05 ϵ T = 0.05 . The unknown distributions P x 0 , P ω \mathcal{P}_{x_0},\mathcal{P}_{\omega} P x 0 , P ω are respectively set to a Dirac distribution at ( 0.4 , 0.4 , 0 ) (0.4,0.4,0) ( 0.4 , 0.4 , 0 ) , and a zero-mean Gaussian with a diagonal covariance matrix defined as diag ( 10 − 10 , 10 − 10 , 0 ) \operatorname{diag}(10^{-10},10^{-10},0) diag ( 1 0 − 10 , 1 0 − 10 , 0 ) , i.e., the heading angle θ \theta θ is unaffected by process noise.
Unicycle Maze
The Unicycle Maze benchmark reuses the reduced kinematic-vehicle dynamics of Appendix D.1 (same σ \sigma σ , same τ = 0.5 \tau=0.5 τ = 0.5 , same Lipschitz-constant expression) over a larger, more cluttered 9.8 × 9.8 9.8\times9.8 9.8 × 9.8 arena with state
x k = ( p x , k , p y , k , θ k ) ∈ [ − 4.9 , 4.9 ] × [ − 4.9 , 4.9 ] × [ − π − 0.4 , π + 0.4 ] , x_k=(p_{x,k},p_{y,k},\theta_k)\in[-4.9,4.9]\times[-4.9,4.9]\times[-\pi-0.4,\pi+0.4], x k = ( p x , k , p y , k , θ k ) ∈ [ − 4.9 , 4.9 ] × [ − 4.9 , 4.9 ] × [ − π − 0.4 , π + 0.4 ] ,
and control u k = ( v k , δ k ) ∈ [ − 1 , 1 ] 2 u_k=(v_k,\delta_k)\in[-1,1]^2 u k = ( v k , δ k ) ∈ [ − 1 , 1 ] 2 . The unsafe set is defined as O = O 1 ∪ O 2 ∪ O 3 ∪ O 4 ∪ O 5 \mathcal{O}=\mathcal{O}_1\cup\mathcal{O}_2\cup\mathcal{O}_3\cup\mathcal{O}_4\cup\mathcal{O}_5 O = O 1 ∪ O 2 ∪ O 3 ∪ O 4 ∪ O 5 , where
O 1 = [ 1.5 , 2.0 ] × [ 1.0 , 4.2 ] × [ − π − 0.4 , π + 0.4 ] , O 2 = [ − 3.0 , 2.0 ] × [ 1.0 , 1.5 ] × [ − π − 0.4 , π + 0.4 ] , O 3 = [ − 3.0 , 2.0 ] × [ − 1.0 , − 0.5 ] × [ − π − 0.4 , π + 0.4 ] , O 4 = [ 1.5 , 2.0 ] × [ − 3.5 , − 2.1 ] × [ − π − 0.4 , π + 0.4 ] , O 5 = [ − 4.3 , 2.0 ] × [ − 3.5 , − 3.0 ] × [ − π − 0.4 , π + 0.4 ] , \begin{aligned}
\mathcal{O}_1&=[1.5,2.0]\times[1.0,4.2]\times[-\pi-0.4,\pi+0.4],\\
\mathcal{O}_2&=[-3.0,2.0]\times[1.0,1.5]\times[-\pi-0.4,\pi+0.4],\\
\mathcal{O}_3&=[-3.0,2.0]\times[-1.0,-0.5]\times[-\pi-0.4,\pi+0.4],\\
\mathcal{O}_4&=[1.5,2.0]\times[-3.5,-2.1]\times[-\pi-0.4,\pi+0.4],\\
\mathcal{O}_5&=[-4.3,2.0]\times[-3.5,-3.0]\times[-\pi-0.4,\pi+0.4],
\end{aligned} O 1 O 2 O 3 O 4 O 5 = [ 1.5 , 2.0 ] × [ 1.0 , 4.2 ] × [ − π − 0.4 , π + 0.4 ] , = [ − 3.0 , 2.0 ] × [ 1.0 , 1.5 ] × [ − π − 0.4 , π + 0.4 ] , = [ − 3.0 , 2.0 ] × [ − 1.0 , − 0.5 ] × [ − π − 0.4 , π + 0.4 ] , = [ 1.5 , 2.0 ] × [ − 3.5 , − 2.1 ] × [ − π − 0.4 , π + 0.4 ] , = [ − 4.3 , 2.0 ] × [ − 3.5 , − 3.0 ] × [ − π − 0.4 , π + 0.4 ] ,
forming a corridor-and-wall maze. The reach set is given by T = [ − 1.1 , 1.0 ] × [ − 2.6 , − 1.5 ] × [ − π − 0.4 , π + 0.4 ] \mathcal{T}=[-1.1,1.0]\times[-2.6,-1.5]\times[-\pi-0.4,\pi+0.4] T = [ − 1.1 , 1.0 ] × [ − 2.6 , − 1.5 ] × [ − π − 0.4 , π + 0.4 ] . Risk thresholds are ϵ O = ϵ T = 0.05 \epsilon_{\mathcal{O}}=\epsilon_{\mathcal{T}}=0.05 ϵ O = ϵ T = 0.05 . The unknown distributions P x 0 , P ω \mathcal{P}_{x_0},\mathcal{P}_{\omega} P x 0 , P ω are respectively set to a Dirac distribution at ( 4.0 , 4.0 , 0 ) (4.0,4.0,0) ( 4.0 , 4.0 , 0 ) , and a zero-mean Gaussian with a diagonal covariance matrix defined as diag ( 5 × 10 − 7 , 5 × 10 − 7 , 5 × 10 − 7 ) \operatorname{diag}(5\times10^{-7},5\times10^{-7},5\times10^{-7}) diag ( 5 × 1 0 − 7 , 5 × 1 0 − 7 , 5 × 1 0 − 7 ) .
Table 2 (PDF p. 18). Hyperparameters per benchmark.
3D Double Integrator
The 3D Double Integrator benchmark consists of a six-dimensional model with state described by
x k = ( p x , k , p y , k , p z , k , v x , k , v y , k , v z , k ) x_k = (p_{x,k},p_{y,k},p_{z,k},v_{x,k},v_{y,k},v_{z,k}) x k = ( p x , k , p y , k , p z , k , v x , k , v y , k , v z , k )
∈ [ − 12 , 12 ] × [ − 12 , 12 ] × [ − 2 , 10 ] × [ − 4 , 4 ] × [ − 4 , 4 ] × [ − 3 , 3 ] \in[-12,12]\times[-12,12]\times[-2,10]\times[-4,4]\times[-4,4]\times[-3,3] ∈ [ − 12 , 12 ] × [ − 12 , 12 ] × [ − 2 , 10 ] × [ − 4 , 4 ] × [ − 4 , 4 ] × [ − 3 , 3 ] , representing 3D positions and velocities, and control u k = ( a x , k , a y , k , a z , k ) ∈ [ − 1 , 1 ] 3 u_k=(a_{x,k},a_{y,k},a_{z,k})\in[-1,1]^3 u k = ( a x , k , a y , k , a z , k ) ∈ [ − 1 , 1 ] 3 . We consider the dynamics to be described by an additive noise dynamical process given by
x k + 1 = f ( x k , u k , ω k ) = g ( x k , u k ) + ω k = A x k + B u k + ω k , x_{k+1}=f(x_k,u_k,\omega_k)=g(x_k,u_k)+\omega_k=Ax_k+Bu_k+\omega_k, x k + 1 = f ( x k , u k , ω k ) = g ( x k , u k ) + ω k = A x k + B u k + ω k ,
where
A = [ 1 0 0 τ 0 0 0 1 0 0 τ 0 0 0 1 0 0 τ 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 ] , B = [ 1 2 τ 2 0 0 0 1 2 τ 2 0 0 0 1 2 τ 2 τ 0 0 0 τ 0 0 0 τ ] . A=\begin{bmatrix}
1&0&0&\tau&0&0\\
0&1&0&0&\tau&0\\
0&0&1&0&0&\tau\\
0&0&0&1&0&0\\
0&0&0&0&1&0\\
0&0&0&0&0&1
\end{bmatrix},
\qquad
B=\begin{bmatrix}
\frac{1}{2}\tau^2&0&0\\
0&\frac{1}{2}\tau^2&0\\
0&0&\frac{1}{2}\tau^2\\
\tau&0&0\\
0&\tau&0\\
0&0&\tau
\end{bmatrix}. A = 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 τ 0 0 1 0 0 0 τ 0 0 1 0 0 0 τ 0 0 1 , B = 2 1 τ 2 0 0 τ 0 0 0 2 1 τ 2 0 0 τ 0 0 0 2 1 τ 2 0 0 τ .
with sampling time τ = 0.3 \tau=0.3 τ = 0.3 . For any u ∈ U u\in\mathcal{U} u ∈ U , the Lipschitz constant of g ( ⋅ , u ) g(\cdot,u) g ( ⋅ , u ) is the spectral norm of the state-transition matrix L g u = ∥ A ∥ ≈ 1.1612 \mathcal{L}_{g_u}=\lVert A\rVert\approx1.1612 L g u = ∥ A ∥ ≈ 1.1612 . The unsafe set is defined as O = O 1 ∪ O 2 ∪ O 3 O=O_1\cup O_2\cup O_3 O = O 1 ∪ O 2 ∪ O 3 , where
O 1 = [ − 1.5 , 1.5 ] × [ − 1.5 , 1.5 ] × [ − 2.0 , 4.0 ] × [ − 4 , 4 ] × [ − 4 , 4 ] × [ − 3 , 3 ] , O_1=[-1.5,1.5]\times[-1.5,1.5]\times[-2.0,4.0]\times[-4,4]\times[-4,4]\times[-3,3], O 1 = [ − 1.5 , 1.5 ] × [ − 1.5 , 1.5 ] × [ − 2.0 , 4.0 ] × [ − 4 , 4 ] × [ − 4 , 4 ] × [ − 3 , 3 ] ,
O 2 = [ − 7.0 , − 4.0 ] × [ 2.5 , 5.5 ] × [ 1.0 , 6.5 ] × [ − 4 , 4 ] × [ − 4 , 4 ] × [ − 3 , 3 ] , O_2=[-7.0,-4.0]\times[2.5,5.5]\times[1.0,6.5]\times[-4,4]\times[-4,4]\times[-3,3], O 2 = [ − 7.0 , − 4.0 ] × [ 2.5 , 5.5 ] × [ 1.0 , 6.5 ] × [ − 4 , 4 ] × [ − 4 , 4 ] × [ − 3 , 3 ] ,
O 3 = [ 3.0 , 6.5 ] × [ − 7.0 , − 3.5 ] × [ 0.5 , 5.5 ] × [ − 4 , 4 ] × [ − 4 , 4 ] × [ − 3 , 3 ] . O_3=[3.0,6.5]\times[-7.0,-3.5]\times[0.5,5.5]\times[-4,4]\times[-4,4]\times[-3,3]. O 3 = [ 3.0 , 6.5 ] × [ − 7.0 , − 3.5 ] × [ 0.5 , 5.5 ] × [ − 4 , 4 ] × [ − 4 , 4 ] × [ − 3 , 3 ] .
The reach set is given by T = [ 6.5 , 9.5 ] × [ 6.5 , 9.5 ] × [ 5.0 , 8.0 ] × [ − 1.5 , 1.5 ] 3 \mathcal{T}=[6.5,9.5]\times[6.5,9.5]\times[5.0,8.0]\times[-1.5,1.5]^3 T = [ 6.5 , 9.5 ] × [ 6.5 , 9.5 ] × [ 5.0 , 8.0 ] × [ − 1.5 , 1.5 ] 3 . Risk thresholds are e 0 = ε T = 0.05 e_0=\varepsilon_T=0.05 e 0 = ε T = 0.05 . The unknown distributions P 0 , P ω \mathbb{P}_0,\mathbb{P}_\omega P 0 , P ω are respectively set to a Dirac distribution at ( − 8.5 , − 8.5 , 0 , 0 , 0 , 0 ) (-8.5,-8.5,0,0,0,0) ( − 8.5 , − 8.5 , 0 , 0 , 0 , 0 ) , and a zero-mean Gaussian with a diagonal covariance matrix defined as diag ( 0 , 0 , 0 , 10 − 8 , 10 − 8 , 10 − 8 ) \operatorname{diag}(0,0,0,10^{-8},10^{-8},10^{-8}) diag ( 0 , 0 , 0 , 1 0 − 8 , 1 0 − 8 , 1 0 − 8 ) .
Switched Systems (5 Modes) gracia2025efficient
The Switched Systems (5 Modes) benchmark from [16 ] considers a two-dimensional state
x k = ( p x , k , p y , k ) ∈ [ − 2 , 2 ] 2 , x_k=(p_{x,k},p_{y,k})\in[-2,2]^2, x k = ( p x , k , p y , k ) ∈ [ − 2 , 2 ] 2 ,
with scalar control input u k ∈ [ 0 , 5 ] u_k\in[0,5] u k ∈ [ 0 , 5 ] . The control selects one of five linear modes via
σ ( u k ) = { 1 , 0 ≤ u k < 1 , 2 , 1 ≤ u k < 2 , 3 , 2 ≤ u k < 3 , 4 , 3 ≤ u k < 4 , 5 , 4 ≤ u k ≤ 5. \sigma(u_k)=
\begin{cases}
1, & 0\leq u_k<1,\\
2, & 1\leq u_k<2,\\
3, & 2\leq u_k<3,\\
4, & 3\leq u_k<4,\\
5, & 4\leq u_k\leq5.
\end{cases} σ ( u k ) = ⎩ ⎨ ⎧ 1 , 2 , 3 , 4 , 5 , 0 ≤ u k < 1 , 1 ≤ u k < 2 , 2 ≤ u k < 3 , 3 ≤ u k < 4 , 4 ≤ u k ≤ 5.
We consider the dynamics to be described by an additive noise dynamical process given by
x k + 1 = f ( x k , u k , ω k ) = g ( x k , u k ) + ω k = A σ ( u k ) x k + ω k , x_{k+1}=f(x_k,u_k,\omega_k)=g(x_k,u_k)+\omega_k=A_{\sigma(u_k)}x_k+\omega_k, x k + 1 = f ( x k , u k , ω k ) = g ( x k , u k ) + ω k = A σ ( u k ) x k + ω k ,
where the mode-dependent matrices are
A 1 = [ 0.79 0.035 0.0 0.825 ] , A 2 = [ 0.79 0.175 0.0 0.825 ] , A_1=\begin{bmatrix}0.79&0.035\\0.0&0.825\end{bmatrix},\qquad
A_2=\begin{bmatrix}0.79&0.175\\0.0&0.825\end{bmatrix}, A 1 = [ 0.79 0.0 0.035 0.825 ] , A 2 = [ 0.79 0.0 0.175 0.825 ] ,
A 3 = [ 0.79 0.0 0.175 0.825 ] , A_3=\begin{bmatrix}0.79&0.0\\0.175&0.825\end{bmatrix}, A 3 = [ 0.79 0.175 0.0 0.825 ] ,
A 4 = [ 1.0 0.2 − 0.2 1.0 ] , A 5 = [ 1.0 − 0.2 0.2 1.0 ] . A_4=\begin{bmatrix}1.0&0.2\\-0.2&1.0\end{bmatrix},\qquad
A_5=\begin{bmatrix}1.0&-0.2\\0.2&1.0\end{bmatrix}. A 4 = [ 1.0 − 0.2 0.2 1.0 ] , A 5 = [ 1.0 0.2 − 0.2 1.0 ] .
For any u ∈ U u \in\mathcal{U} u ∈ U , the Lipschitz constant of g ( ⋅ , u ) g(\cdot,u) g ( ⋅ , u ) is the spectral norm (largest singular value) of the active mode matrix, i.e. L g u ≈ 0.8324 , 0.9015 , 0.9015 , 1.0198 , 1.0198 \mathcal{L}_{g_u} \approx0.8324, 0.9015, 0.9015, 1.0198, 1.0198 L g u ≈ 0.8324 , 0.9015 , 0.9015 , 1.0198 , 1.0198 for modes 1 to 5 respectively.
The unsafe set is defined as O = O 1 ∪ O 2 ∪ O 3 ∪ O 4 \mathcal{O}=\mathcal{O}_1\cup\mathcal{O}_2\cup\mathcal{O}_3\cup\mathcal{O}_4 O = O 1 ∪ O 2 ∪ O 3 ∪ O 4 , where
O 1 = [ − 2.0 , − 1.0 ] × [ − 2.0 , − 1.0 ] , O 2 = [ − 1.0 , 0.0 ] × [ 0.0 , 1.0 ] , \mathcal{O}_1=[-2.0,-1.0]\times[-2.0,-1.0],\qquad
\mathcal{O}_2=[-1.0,0.0]\times[0.0,1.0], O 1 = [ − 2.0 , − 1.0 ] × [ − 2.0 , − 1.0 ] , O 2 = [ − 1.0 , 0.0 ] × [ 0.0 , 1.0 ] ,
O 3 = [ 0.0 , 1.0 ] × [ − 1.0 , 0.0 ] , O 4 = [ 1.0 , 2.0 ] × [ 1.0 , 2.0 ] , \mathcal{O}_3=[0.0,1.0]\times[-1.0,0.0],\qquad
\mathcal{O}_4=[1.0,2.0]\times[1.0,2.0], O 3 = [ 0.0 , 1.0 ] × [ − 1.0 , 0.0 ] , O 4 = [ 1.0 , 2.0 ] × [ 1.0 , 2.0 ] ,
together with the complement of the support [ − 2 , 2 ] 2 [-2,2]^2 [ − 2 , 2 ] 2 . The reach set is given by
T 1 = [ 0.0 , 1.0 ] × [ 0.0 , 1.0 ] , T 2 = [ − 1.0 , 0.0 ] × [ − 1.0 , 0.0 ] . \mathcal{T}_1=[0.0,1.0]\times[0.0,1.0],\qquad
\mathcal{T}_2=[-1.0,0.0]\times[-1.0,0.0]. T 1 = [ 0.0 , 1.0 ] × [ 0.0 , 1.0 ] , T 2 = [ − 1.0 , 0.0 ] × [ − 1.0 , 0.0 ] .
Risk thresholds are ε O = ε T = 0.05 \varepsilon_O=\varepsilon_T=0.05 ε O = ε T = 0.05 . The unknown distributions P x 0 , P ω \mathbb{P}_{x_0},\mathbb{P}_{\omega} P x 0 , P ω are respectively set to a Dirac distribution at ( − 1.5 , 1.0 ) (-1.5,1.0) ( − 1.5 , 1.0 ) , and a zero-mean Gaussian with a diagonal covariance matrix defined as diag ( 10 − 6 , 10 − 6 ) \operatorname{diag}(10^{-6},10^{-6}) diag ( 1 0 − 6 , 1 0 − 6 ) .
Tractor-Trailer NN [5 ]
The Tractor-Trailer NN benchmark uses a four-dimensional state
x k = ( p x , k , p y , k , θ k , α k ) ∈ [ − 4.0 , 10.0 ] × [ − 4.0 , 10.0 ] × [ − 3.15 , 3.15 ] × [ − 1.57 , 1.57 ] , x_k=(p_{x,k},p_{y,k},\theta_k,\alpha_k)
\in[-4.0,10.0]\times[-4.0,10.0]\times[-3.15,3.15]\times[-1.57,1.57], x k = ( p x , k , p y , k , θ k , α k ) ∈ [ − 4.0 , 10.0 ] × [ − 4.0 , 10.0 ] × [ − 3.15 , 3.15 ] × [ − 1.57 , 1.57 ] ,
where ( p x , k , p y , k ) (p_{x,k},p_{y,k}) ( p x , k , p y , k ) is the position of the tractor, θ k \theta_k θ k its heading, and α k \alpha_k α k the hitch angle between the tractor and the trailer, with control u k = ( v k , ω k ) ∈ [ − 2.0 , 2.0 ] × [ − 1.0 , 1.0 ] u_k=(v_k,\omega_k)\in[-2.0,2.0]\times[-1.0,1.0] u k = ( v k , ω k ) ∈ [ − 2.0 , 2.0 ] × [ − 1.0 , 1.0 ] representing the longitudinal velocity and the steering rate. The nominal dynamics are given by a residual neural network,
x k + 1 = f ( x k , u k , ω k ) = g ( x k , u k ) + ω k = x k + N N ( θ k , α k , v k , ω k ) + ω k , x_{k+1}=f(x_k,u_k,\omega_k)=g(x_k,u_k)+\omega_k=x_k+\mathcal{NN}(\theta_k,\alpha_k,v_k,\omega_k)+\omega_k, x k + 1 = f ( x k , u k , ω k ) = g ( x k , u k ) + ω k = x k + NN ( θ k , α k , v k , ω k ) + ω k ,
where N N \mathcal{NN} NN is a fully connected network with architecture 4-64-64-4, Tanh activations on the two hidden layers, and a linear output layer, trained offline to approximate the discrete-time residual kinematics of the truck-trailer model of [5 ] ; only the heading and hitch angle ( θ k , α k ) (\theta_k,\alpha_k) ( θ k , α k ) and the control ( v k , ω k ) (v_k,\omega_k) ( v k , ω k ) are fed to the network, while the position increments ( Δ p x , k , Δ p y , k ) (\Delta p_{x,k},\Delta p_{y,k}) ( Δ p x , k , Δ p y , k ) are read off its output. The Lipschitz constant of g ( ⋅ , u ) g(\cdot,u) g ( ⋅ , u ) used by our implementation is bounded by
L g u n a i v e = 1 + ∥ W 3 ∥ 2 ∥ W 2 ∥ 2 ∥ W 1 ( θ , α ) ∥ 2 ≈ 1.6468 , \mathcal{L}_{g_u}^{\mathrm{naive}}=1+\lVert W_3\rVert_2\lVert W_2\rVert_2\lVert W_1^{(\theta,\alpha)}\rVert_2\approx1.6468, L g u naive = 1 + ∥ W 3 ∥ 2 ∥ W 2 ∥ 2 ∥ W 1 ( θ , α ) ∥ 2 ≈ 1.6468 ,
where W 1 W_1 W 1 , W 2 W_2 W 2 , and W 3 W_3 W 3 are the weight matrices of the three linear layers and W 1 ( θ , α ) W_1^{(\theta,\alpha)} W 1 ( θ , α ) denotes the two columns of W 1 W_1 W 1 acting on ( θ k , α k ) (\theta_k,\alpha_k) ( θ k , α k ) (the position channels ( p x , k , p y , k ) (p_{x,k},p_{y,k}) ( p x , k , p y , k ) do not feed N N \mathcal{NN} NN , and ( v k , ω k ) (v_k,\omega_k) ( v k , ω k ) are controls rather than state variables). The leading 1 accounts for the residual (skip) connection: the Jacobian of g ( ⋅ , u ) g(\cdot,u) g ( ⋅ , u ) is I 4 + M I_4+M I 4 + M , where M M M is supported on the ( θ , α ) (\theta,\alpha) ( θ , α ) columns and satisfies
∥ M ∥ 2 ≤ ∥ W 3 ∥ 2 ∥ W 2 ∥ 2 ∥ W 1 ( θ , α ) ∥ 2 \lVert M\rVert_2\leq\lVert W_3\rVert_2\lVert W_2\rVert_2\lVert W_1^{(\theta,\alpha)}\rVert_2 ∥ M ∥ 2 ≤ ∥ W 3 ∥ 2 ∥ W 2 ∥ 2 ∥ W 1 ( θ , α ) ∥ 2
since Tanh is 1-Lipschitz. In particular L g u ≥ 1 \mathcal{L}_{g_u}\geq1 L g u ≥ 1 , as perturbing only ( p x , k , p y , k ) (p_{x,k},p_{y,k}) ( p x , k , p y , k ) leaves the network input unchanged and is therefore propagated isometrically.
This bound is conservative – it assumes all 128 hidden units saturate simultaneously – and, compounded once per time step over the ≈ 90 \approx90 ≈ 90 steps of this benchmark, it renders the propagated ambiguity sets vacuous. We therefore certify the constant with the LipSDP semidefinite relaxation of [11 ] , applied to the residual map g ( ⋅ , u ) g(\cdot,u) g ( ⋅ , u ) (see src/lipschitz.jl). This yields L g u L i p S D P ≃ 1.2096 \mathcal{L}_{g_u}^{\mathrm{LipSDP}}\simeq1.2096 L g u LipSDP ≃ 1.2096 , against ≈ 1.1046 \approx1.1046 ≈ 1.1046 for the numerically estimated true constant. All Tractor-Trailer NN results use L g u L i p S D P \mathcal{L}_{g_u}^{\mathrm{LipSDP}} L g u LipSDP ; with L g u n a i v e \mathcal{L}_{g_u}^{\mathrm{naive}} L g u naive the success rate collapses to 5%.
The unsafe set is defined as O = O 1 \mathcal{O}=\mathcal{O}_1 O = O 1 , where
O 1 = [ 2.0 , 3.0 ] × [ 2.0 , 3.0 ] × [ − 3.15 , 3.15 ] × [ − 1.57 , 1.57 ] , \mathcal{O}_1=[2.0,3.0]\times[2.0,3.0]\times[-3.15,3.15]\times[-1.57,1.57], O 1 = [ 2.0 , 3.0 ] × [ 2.0 , 3.0 ] × [ − 3.15 , 3.15 ] × [ − 1.57 , 1.57 ] ,
together with the complement of the support. The reach set is given by
T = [ 4.0 , 7.0 ] × [ 4.0 , 7.0 ] × [ − 3.15 , 3.15 ] × [ − 1.57 , 1.57 ] . \mathcal{T}=[4.0,7.0]\times[4.0,7.0]\times[-3.15,3.15]\times[-1.57,1.57]. T = [ 4.0 , 7.0 ] × [ 4.0 , 7.0 ] × [ − 3.15 , 3.15 ] × [ − 1.57 , 1.57 ] .
Risk thresholds are ε O = ε T = 0.05 \varepsilon_O=\varepsilon_T=0.05 ε O = ε T = 0.05 . The unknown distributions P x 0 , P ω \mathbb{P}_{x_0},\mathbb{P}_{\omega} P x 0 , P ω are respectively set to a Dirac distribution at ( − 0.5 , 1.5 , 0.78 , 0.0 ) (-0.5,1.5,0.78,0.0) ( − 0.5 , 1.5 , 0.78 , 0.0 ) , and a zero-mean Gaussian with a diagonal covariance matrix defined as diag ( 10 − 8 , 10 − 8 , 10 − 8 , 10 − 8 ) \operatorname{diag}(10^{-8},10^{-8},10^{-8},10^{-8}) diag ( 1 0 − 8 , 1 0 − 8 , 1 0 − 8 , 1 0 − 8 ) .
Hyperparameters
Table 2 lists the hyperparameters of Algorithm 1 that are not given in Section 5. At stage s s s , both calls to LearnAmbiguitySet (root and noise) use N p r e ( 1 ) N_{\mathrm{pre}}^{(1)} N pre ( 1 ) pre-training and s N ( 1 ) sN^{(1)} s N ( 1 ) training samples, i.e., N ( s ) = N ω ( s ) = s ( N p r e ( 1 ) + N ( 1 ) ) N(s)=N_{\omega}(s)=s(N_{\mathrm{pre}}^{(1)}+N^{(1)}) N ( s ) = N ω ( s ) = s ( N pre ( 1 ) + N ( 1 ) ) . Line 4 of Algorithm 5 takes the best of the number K K K of uniformly sampled steering candidates indicated in the table. The last two rows are the settings of the informed search of Appendix C.
Table 2.
E -RandUP-RRT baseline
We implement ϵ \epsilon ϵ -RandUP-RRT following the reference code released by [40 ] at https://github.com/StanfordASL/randUP_RRT, which combines the particle-based, ϵ \epsilon ϵ -padded convex-hull reachability check of [28 ] with an RRT planner: each tree node holds N N N particles propagated under independently sampled noise trajectories, and a node (or edge) is accepted only if the convex hull of its particles avoids every padded obstacle and, to certify the target, is contained in the padded target set, both checked via a linear program. Two differences from the released code: (i) we bias sampling toward a nominal reference trajectory, computed once up front with our own risk-agnostic tree-expansion routine, rather than sampling uniformly, to aid convergence in the more cluttered mazes, and (ii) we impose a 2-minute wall-clock budget per run, recording unresolved runs as timeouts. Following [40 ] , we use a padding of ϵ = 0.3 \epsilon=0.3 ϵ = 0.3 from their quadrotor experiment, and set N = 1,000 N=1{,}000 N = 1 , 000 particles for every benchmark.