HJ-Gauss: A Monte-Carlo HJ Reachability Scheme
Lekan Molu, Venkatraman Renganathan, Namhoon Cho · 2026
Read HJ-Gauss: A Monte-Carlo HJ Reachability Scheme by Lekan Molu, Venkatraman Renganathan, Namhoon Cho (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-18566.txt.
Introduction
Lekan Molu and two co-authors present HJ-Gauss, a 2026 Monte-Carlo Hamilton-Jacobi reachability scheme free of grids and discretization. A Cole-Hopf-type transformation reduces the HJ equation to linear heat equations, whose values return via Gaussian heat-kernel expectations. Memory scales as N times n for N samples in n dimensions, with polynomial sampling cost and conditional linear convergence. Tests include a 45-dimensional multi-rocket pursuit-evasion game and safety certification for 100,000 starlings in murmurations.
Catalog record
| CREATOR | Lekan Molu, Venkatraman Renganathan, Namhoon Cho |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 89414 |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.18566
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
HJ-Gauss: A Monte-Carlo HJ Reachability Scheme Lekan Molu, Venkatraman Renganathan, Namhoon Cho Abstract Backward reachable tubes (BRTs), computed via viscous Hamilton-Jacobi (HJ) partial differential equations, provide principled safety certificates for learned controllers and planning algorithms in trustworthy machine learning. However, classical grid-based HJ solvers require O ( M n ) O(M^{n}) memory footprint for M M grid points per n n state dimension. This renders them impractical for high-dimensional systems. We address this bottleneck with a local PDE linearization that enables a frozen-coefficient sampling scheme for the viscous HJ PDE: a generalized Cole-Hopf-type transformation reduces the nonlinear HJ equation to a sequence of linear heat equations whose solutions admit Gaussian heat-kernel representations. The value function and its spatial gradient are then recovered via roll-outs of Monte Carlo expectations on Gaussian densities, yielding a storage and grid-free algorithm that scales as N ⋅ n N\cdot n for N N samples. This decoupling of memory from dimensionality enables reachability analysis on problems where grid-based methods are simply impossible. We prove a finite-sample concentration bound O ( N − 1 / 2 ) O(N^{-1/2}) error and conditional linear convergence for the introduced Monte-Carlo Picard iterative scheme. Numerical validation on pursuit-evasion games demonstrates relative L rel 2 L^{2}_{\text{rel}} errors of 0.03 − 0.20 0.03-0.20 , with 14 − 26 14-26 second wall-clock times per 2D slice on a CPU. Crucially, the method scales with validation on up to (but not limited to) n = 45 n=45 -dimensional multi-agent games. 1 Introduction A central challenge in trustworthy machine learning is certifying that a learned controller, neural policy, or planning algorithm will not violate safety constraints at deployment time. This concern appears directly in safe reinforcement learning ( 18 ) , model-based RL with learned dynamics ( 3 ) , and any pipeline where a learned model must operate in a continuous, possibly high-dimensional state space under adversarial or uncertain inputs. Backward reachable (reach-avoid) tubes or BRTs(BRATs) are the set of all states from which a system is guaranteed to reach (avoid) a target region regardless of disturbances that may affect its behavioral evolution during deployment; they provide a principled certificate for solving reachability problems. Computing a BRT amounts to solving a Hamilton-Jacobi-Isaacs (HJI) partial differential equation (PDE) ( 23 ; 21 ) , typically under two competing inputs. Figure 1 : Rockets BRT slices: Grid-based levelsetpy from ( 27 ) vs. Monte Carlo (ours). The bottom row shows a heat map of the pointwise errors at various relative vehicle orientations \theta ; errors are largest near the boundary of the usable part where |D\bm{v}^{\delta}| is largest. Central Contribution: Monte-Carlo Trajectory Optimization of Quasi-Linear BRTs A backward reachable tube (BRT) is the set of initial states from which a controlled system is guaranteed to reach a target set within a given time horizon, for all adversarial inputs. Given system dynamics \dot{\bm{x}}=f(t;\bm{x},\bm{u},\bm{w}) with controller \bm{u} and disturbance \bm{w} , the BRT is the zero sublevel set of a value function \bm{v}^{\delta} that solves the viscous HJI PDE ( HJI-RCBRT-Visc ). Classical grid-based solvers ( 23 ; 28 ) discretize the state space on a grid with M points per dimension; the resulting memory cost is O(M^{n}) , which grows exponentially in the state dimension n . For n=6 with M=100 , this already requires 10^{12} grid cells. The proposed method replaces the grid with N Monte Carlo samples of state space trajectories, reducing spatial memory to O(N\cdot n) . The major bottleneck for realizing the solutions to the BRT of complex systems is computational: classical HJ solvers scale as O(M^{n}) in memory, where M is the number of grid points per dimension and n is the state dimension. While GPU-accelerated implementations ( 27 ; 28 ) reduce wall-clock time, they retain the same exponential memory footprint. Self-supervised, PINN-based approaches such as DeepReach ( 1 ) train a neural network to minimize the HJ PDE residual directly via a physics-informed loss, without requiring a reference grid solution. However, the method scales moderately in dimensions (reportedly 9D) and accuracy degrades in the limit of higher-dimensional data. We introduce a fundamentally different approach that replaces grid storage with a sampling scheme so that the memory cost is O(N\cdot n) and the algorithm is grid-free. We consider first-order nonlinear scalar HJ PDEs of the form \displaystyle\bm{v}_{t}+\bm{H}(t;\bm{x},D\bm{v})=0\text{ in }\Omega\times(0,T],\quad\bm{v}(0;\bm{x})=\bm{g}(0;\bm{x})\text{ on }\partial\Omega\times\{t=0\} (HJ-IVP) where the state \bm{x} belongs to the open set \Omega\subseteq\mathbb{R}^{n} ; \bm{v}_{t} denotes the partial time derivative of \bm{v}(t;\bm{x}) ; \bm{H}(t;\bm{x},D\bm{v}) is the Hamiltonian, continuously defined on \mathbb{R}^{n} , with D\bm{v} representing the spatial gradient; and \bm{g}(\bm{x}) being bounded and uniformly continuous (BUC) on \mathbb{R}^{n} . Fixing a viscosity parameter \delta>0 , Crandall and Lions ( 8 ) introduced the vanishing viscosity solution, \bm{v}^{\delta} , of ( HJ-IVP ) i.e. , \displaystyle\bm{v}_{t}^{\delta}+\bm{H}(t;\bm{x},D\bm{v}^{\delta})=\dfrac{\delta}{2}\Delta\bm{v}^{\delta}\text{ in }\Omega\times(0,T];\quad\bm{v}^{\delta}(0;\bm{x})=\bm{g}(0;\bm{x})\text{ on }\partial\Omega\times\{t=0\} (HJ-Visc) such that ( HJ-Visc ) satisfies the uniform convergence bound \displaystyle\sup_{t\in(0,T]}\sup_{\bm{x}\in\mathbb{R}^{n}}\left|\bm{v}(t;\bm{x})-\bm{v}^{\delta}(t;\bm{x})\right|\leq k\sqrt{\delta} (1) for a constant k>0 . Our key insight is that ( HJ-Visc ) can be reduced, via a generalized Cole-Hopf-type transformation, to a sequence of linear heat equations admitting explicit Gaussian heat-kernel solutions. This yields a locally linearized PDE. The scheme is not an exact Cole-Hopf reduction for general Hamiltonians; it is an iterative (Picard) approximation in which the nonlinear coefficient is frozen at each step and updated after the linear solution is found. The exact reduction holds for the quadratic case \bm{H}=\tfrac{1}{2}|p|^{2} , where the frozen coefficient is constant and the residual vanishes identically. Connections to ML. Beyond reachability, the proposed scheme connects to several active ML research directions. (i) Safe RL and policy verification : certifying that a learned policy satisfies safety constraints requires computing BRTs for the closed-loop system; the memory bottleneck of grid-based solvers is the primary obstacle to safe RL in high-dimensional spaces ( 18 ; 3 ) . (ii) Model-based RL : planning algorithms that learn a dynamics model and then verify safety via HJ reachability are limited to low-dimensional state spaces ( 1 ) . (iii) Diffusion-based methods : the Gaussian heat-kernel representation derived here is structurally similar to score-matching objectives and denoising score functions ( 5 ; 15 ) , opening potential bridges to score-based generative models for safety certificates. Contributions. Our contributions are as follows. (i) A generalized Cole-Hopf-type transformation decouples the nonlinear viscous HJ equation into linear heat equations with Gaussian heat-kernel solutions; this enables a frozen-coefficient quasi-linearization. (ii) A sampling-based Algorithm 1 ) with O(N\cdot n) memory complexity that scales with sample count rather than discretization dimension, offers a viable alternative to impractical grid-based O(M^{n}) approaches in high dimensions. (iii) Theoretical guarantees: (a) a finite-sample concentration bound of O(N^{-1/2}) for the Monte Carlo value estimator, independent of state dimensions (Theorem 2.5 ), and (b) conditional linear convergence of the Picard iteration with explicit contraction constant (Theorem 2.10 ). (iv) Validation on two-player pursuit-evasion games achieving L^{2}_{\text{rel}} errors of 0.03 – 0.20 (below the O(\sqrt{\delta})\approx 0.28 viscosity bound) in 12–15 iterations; and scalable demonstration on 45-dimensional multi-agent problems where grid-based discretization are currently computationally prohibitive. The rest of this work is structured as follows. Readers not familiar with existing literature can consult the background in Appendix A . Section 2 derives the quasi-linearization of ( HJ-Visc ), states the