A Derivative-Free Bellman Equation for Dynamic Time-to-Collision: Two-Sided Certificates and Explicit ReLU Approximation

arXiv:2611.16663 · math.OC · Submitted 2026-11-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: I'm Ada.

Emmy: And I'm Emmy, here with Kolya.

Ada: We're looking at the paper: "A Derivative-Free Bellman Equation for Dynamic Time-to-Collision".

Emmy: Here's the gist of the paper. Dynamic time-to-collision (TTC) is studied through a derivative-free stopped-step Bellman equation that characterizes its value function uniquely and provides explicit ReLU approximations The paper establishes a self-contained argument for local Lipschitz continuity on the transversal collision domain and presents a two-sided error bound using only the candidate’s residual along complete stopped trajectories Exact continuum iteration recovers V after finitely many sweeps, including one additional sweep for initializations that violate the boundary condition Finally, an optimization-free ReLU construction provides an explicit size and controlled local residual for V on compact subsets of the transversal domain.

Ada: Characterization of the Value Function The paper introduces a derivative-free stopped-step Bellman equation that advances the prediction for a fixed duration or until contact and adds the elapsed time.

Emmy: This equation is evaluated along the prediction flow and requires no derivative of the candidate.

Ada: The uniqueness of its solution is established with a two-sided residual certificate.

Paper summary: Emmy: To wrap up, the paper "A Derivative-Free Bellman Equation for Dynamic Time-to-Collision: Two-Sided Certificates and Explicit ReLU Approximation" is about taking a complex prediction flow problem, like TTC in car following dynamics, and solving it using tools that don't require derivatives.

Ada: They introduce a derivative-free stopped step Bellman equation to characterize the value function uniquely, establishing local Lipschitz continuity on the collision domain to support this.

Kolya: And they provide a two-sided error bound based on the candidate's residual along complete stopped trajectories and its endpoint errors, which is pretty strong for verifying accuracy.

Emmy: On top of that, they give an optimization-free ReLU construction that provides an explicit size and controlled local residual for V on compact subsets of the transversal domain, which is a direct way to build a usable approximation network.

Ada: It really boils down to getting a concrete, derivative-free method for finding TTC values and then showing you exactly how good an AI approximation can be in that domain.

Emmy: For someone listening who isn't deep in the math, this means they have found a stable way to solve these time-to-collision problems without needing calculus or complex optimization routines for every single prediction step.

Kolya: The implication is that we can use these explicit ReLU constructions to build faster and more reliable models for things like autonomous driving safety predictions.

Ada: Precisely, because they've shown the convergence properties and the error bounds are tied to measurable quantities, which is what you need when you're dealing with real-world sensors.

Conclusion: Ada: So, we've been looking at this paper about a derivative free Bellman equation for dynamic time to collision. It’s titled "A Derivative-Free Bellman Equation for Dynamic Time-to-Collision: Two-Sided Certificates and Explicit ReLU Approximation."

Emmy: Yeah, the authors are Matin and Delle Monache. They’ve built this specific way to characterize that value function uniquely without needing any derivatives at all. It's like finding the answer to a game without having to calculate every single slope of the path you take.

Kolya: From my side, I'm focused on those two sided residual error bounds they present. They’re saying we can get a guarantee on how much error there is based just on looking at the candidate function along complete stopped trajectories and its endpoint errors. That’s pretty concrete.

Ada: That guarantee is what really matters for real applications, right? It means we have a measurable way to know if our approximation is good enough for safety predictions. And they also show how you can actually build this using a ReLU network without needing any special optimization setup beforehand.

Emmy: The structure behind it is quite neat because the exact continuum iteration recovers the value function after just a finite number of sweeps, including one extra sweep if you start with something that doesn't perfectly follow the boundary conditions. That’s a strong structural property there.

Kolya: I mean, if we can recover it finitely, that suggests it's not some infinite process we’re stuck in. But I wonder how robust those finite sweeps are when the underlying dynamics get really complex or noisy in a real world scenario.

Ada: Exactly what I'm curious about. So this paper essentially gives us a tool to solve these complex time to collision problems using simple, derivative free math and then shows us how to build a practical neural network approximation for it with clear error controls. Next up, we're going to look at some of the specific mathematical details behind that ReLU construction.

LIX · Ecole Polytechnique · IP Paris

math.OC

Submitted: 2026-11-12

Updated: 2026-11-12

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

Importance score: 87/100

The gist: Dynamic time-to-collision (TTC) is studied through a derivative-free stopped-step Bellman equation that characterizes its value function uniquely and provides explicit ReLU approximations The paper…

Key concepts

Derivative-Free Stopped-Step Bellman Equation
This is a method used to find the TTC's value function without needing its derivative. It predicts the TTC for a fixed time or until a collision occurs, adding the elapsed time to track progress along the prediction path.
ReLU Approximation
The paper uses Rectified Linear Unit (ReLU) neural networks to approximate the complex TTC value function. This construction is optimization-free, meaning it builds the network directly from the dynamics without needing iterative training methods.
Two-Sided Error Bound
This provides a rigorous guarantee on how accurate the ReLU approximation of TTC is. It uses information (the residual) along complete stopped trajectories to establish both an upper and lower limit on the error, ensuring reliability.

Terminology

Summary

Dynamic time-to-collision (TTC) is studied through a derivative-free stopped-step Bellman equation that characterizes its value function uniquely and provides explicit ReLU approximations The paper establishes a self-contained argument for local Lipschitz continuity on the transversal collision domain and presents a two-sided error bound using only the candidate’s residual along complete stopped trajectories Exact continuum iteration recovers V after finitely many sweeps, including one additional sweep for initializations that violate the boundary condition Finally, an optimization-free ReLU construction provides an explicit size and controlled local residual for V on compact subsets of the transversal domain. p. 0

Where the paper says it

A two-sided error bound uses only the candidate’s residual along complete stopped trajectories and its error at their endpoints. Exact continuum iteration recovers V after finitely many sweeps, including one additional sweep for initializations that violate the boundary condition.

Characterization of the Value Function

The paper introduces a derivative-free stopped-step Bellman equation that advances the prediction for a fixed duration or until contact and adds the elapsed time. This equation is evaluated along the prediction flow and requires no derivative of the candidate. p. 0

Where the paper says it

PARIS and State funding managed by the French National Research Agency (ANR) under the France 2030 program, reference ANR-23-IACL-0005. The equation is evaluated along the prediction flow, needs no derivative of the candidate, and has V as its unique solution with a two-sided residual certificate.

The uniqueness of its solution is established with a two-sided residual certificate. p. 0
Where the paper says it

• The stopped-step equation: uniqueness of its solution, a two-sided a priori error bound in terms of the residual along trajectories, and exact recovery of V after finitely many sweeps from any initialization (Theorems 5 and 6). The certificate permits arbitrary finite-valued candidates on the trajectories and their reached endpoints.

Analysis of Prediction Dynamics

The prediction dynamics are modeled by the flow y˙ = G(t, y). The TTC is defined as the value function V (s, y) which minimizes the infimum of time to contact or terminal time. p. 0

Where the paper says it

Closed-loop model The controlled system has state ϕ ∈ R p and dynamics ϕ˙ = F t, ϕ, τ (t, ϕ) , τ (t, ϕ) := V t, π(ϕ) , (1) where τ is the dynamic-based TTC, V is the value function defined in (6) below from a prediction model, and π : R p → R d extracts from the actual state the initial condition of the prediction. Thus τ is a time-varying static state feedback, defined implicitly through the prediction model, as a model predictive controller is; this paper concerns the regularity arXiv:2611.

Approximation via ReLU Networks

An optimization-free ReLU construction is presented for V on compact subsets of the transversal domain. This network has depth at most Cm(ln(Θ/ε) + 1) and at most N (ε, D') weights and units in a sparse realization. The approximation satisfies the local residual bound of Vθ∗ − Sh[Vθ∗]L∞(D) ≤ 2ε. p. 4

Where the paper says it

Theorem 8 (Optimization-free ReLU realization). There is a constant Cm depending only on m such that, for every ε ∈ (0, Θ), there exist grid points {zj}j∈J ⊂ K and ReLU networks {φ˜j}j∈J , depending only on (B, D′ , r, m, ε, Th, L) and not on the values of V , such that the network Vθ ∗ (z) := X j∈J cj φ˜j (z), cj := V (zj ), (15) has depth at most Cm(ln(Θ/ε) + 1) and at most N (ε, D′ ) ≤ Cm Θ ε + ℓB r m ln Θ ε + 1 (16) weights and units in a sparse realization, and satisfies ∥Vθ ∗ − V ∥L∞(D′) ≤ ε, (17) ∥Vθ ∗ − Sh[Vθ ∗ ]∥L∞(D) ≤ 2ε.

Limitations and Future Directions

The optional-duration infimum operator is characterized such that its fixed points are exactly the dynamic-programming subsolutions, meaning its residual alone cannot identify the TTC. The numerical illustration shows that while residual training modestly improves RMSE, full-sample maxima exhibit large errors near the contact/noncontact interface. p. 5

Where the paper says it

Full-sample maxima are (0. 9333), with large errors near the contact/noncontact interface; the regularity and approximation results make no uniform claim there (Fig.

Uniform numerical certification still requires validated flow, event, nodal and roundoff error bounds. p. 6
Where the paper says it

The computations illustrate these mechanisms with independent tests, a fully covered four-dimensional construction, and grid refinement. Uniform numerical certification still requires validated flow, event, nodal and roundoff error bounds.

Appendix Details

Lemma 10 establishes a compact C1 subset of P such that every maximal solution in P from a datum in [0, Th] × C0 takes its values in C1. Complete finite chains give a twosided residual error bound and finite recovery by the exact operator. p. 6

Where the paper says it

CONCLUSION Dynamic TTC under a prescribed Caratheodory prediction ´ flow is locally Lipschitz on the transversal collision domain and is uniquely characterized by a derivative-free stoppedstep Bellman equation. Complete finite chains give a twosided residual error bound and finite recovery by the exact operator; optional-duration infimum residuals alone do not identify the value function.

A local ReLU construction gives explicit approximation and nodal-perturbation bounds. p. 6
Where the paper says it

Complete finite chains give a twosided residual error bound and finite recovery by the exact operator; optional-duration infimum residuals alone do not identify the value function. A local ReLU construction gives explicit approximation and nodal-perturbation bounds.

The computations illustrate these mechanisms with independent tests, a fully covered four-dimensional construction, and grid refinement. p. 6
Where the paper says it

A local ReLU construction gives explicit approximation and nodal-perturbation bounds. The computations illustrate these mechanisms with independent tests, a fully covered four-dimensional construction, and grid refinement.

References

[1] J. Hayward, “Near misses as a measure of safety at urban intersections,” Pennsylvania Transportation and Traffic Safety Center, Tech. p. 7

Where the paper says it

REFERENCES [1] J. Hayward, “Near misses as a measure of safety at urban intersections,” Pennsylvania Transportation and Traffic Safety Center, Tech.

Rep., 1971

[2] D. N. Lee, “A theory of visual control of braking based on information about time-to-collision,” Perception, vol. p. 7

Where the paper says it

Hayward, “Near misses as a measure of safety at urban intersections,” Pennsylvania Transportation and Traffic Safety Center, Tech. Lee, “A theory of visual control of braking based on information about time-to-collision,” Perception, vol.

5, no. 4, pp. 437–459, 1976

[3] H. N. Z. Matin, Y. Yeo, A. J.-K. Ngo, A. R Paiva, J Utke and M L D Monache “Second-order time to collision with non-static acceleration” in Traffic and Autonomy Cham Springer Nature Switzerland 2026 pp 37–83

[4] H Nick Zinat Matin Y Yeo and M L Delle Monache “Regularity of the time-to-collision map and convergence of learned Hamilton–Jacobi solutions” Preprint 2026 Archived snapshot commit edb3eb0 Oct 27 2026

[5] H Nick Zinat Matin and R B Sowers “Nonlinear optimal velocity car following dynamics I Approximation in presence of deterministic and stochastic perturbations” in American Control Conference 2020 pp 410–415

[6] H Nick Zinat Matin “Nonlinear optimal velocity car following dynamics II Rate of convergence in the presence of fast perturbation” in American Control Conference 2020 pp 416–421

[7] H Nick Zinat Matin Y Yeo X Gong and M L Delle Monache “On the analytical properties of a nonlinear microscopic dynamical model for connected and automated vehicles” IEEE Control Systems Letters vol 8 pp 1607–1612 2024

[8] H Nick Zinat Matin and R B Sowers “Near-collision dynamics in a noisy car-following model” SIAM Journal on Applied Mathematics vol 82 no 6 pp 2080–2110 2022

[9] I M Mitchell A M Bayen and C J Tomlin “A time-dependent Hamilton–Jacobi formulation of reachable sets for continuous dynamic games” IEEE Transactions on Automatic Control vol 50 no 7 pp 947–957 2005

[10] S Bansal M Chen S Herbert and C J Tomlin “Hamilton–Jacobi reachability A brief overview and recent advances” in IEEE Conference on Decision and Control 2017 pp 2242–2253

[11] M Raissi P Perdikaris and G E Karniadakis “Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations Journal of Computational Physics vol 378 pp 686–707 2019

[12] V M Veliov “Lipschitz continuity of the value function in optimal control Journal of Optimization Theory and Applications vol 94 pp 335–363 1997

[13] M Motta and C Sartori “On asymptotic exit-time control problems lacking coercivity ESAIM Control Optimisation and Calculus of Variations vol 20 no 4 pp 957–982 2014

[14] A S Manne “Linear programming and sequential decisions Management Science vol 6 no 3 pp 259–267 1960

[15] D P de Farias and B Van Roy “The linear programming approach to approximate dynamic programming Operations Research vol 51 no 6 pp 850–865 2003

[16] M Bardi and M Falcone “An approximation scheme for the minimum time function SIAM Journal on Control and Optimization vol 28 no 4 pp 950–965 1990

[17] D Yarotsky “Error bounds for approximations with deep ReLU networks Neural Networks vol 94 pp 103–114 2017

[18] J He L Li J Xu and C Zheng “ReLU deep neural networks and linear finite elements Journal of Computational Mathematics vol 38 no 3 pp 502–527 2020

[19] A Oustry and M Tacchi “Minimal time nonlinear control via semiinfinite programming SIAM Journal on Control and Optimization vol 64 no 2 pp 698–726 2026

[20] J Liu “Verifiable error bounds for physics-informed neural network solutions of Lyapunov and Hamilton–Jacobi–Bellman equations IEEE Control Systems Letters vol 10 pp 403–408 2026

[21] M Bando K Hasebe A Nakayama A Shibata and Y Sugiyama “Dynamical model of traffic congestion and numerical simulation Physical Review E vol 51 no 2 pp 1035–1042 1995

[22] A F Filippov Differential Equations with Discontinuous Righthand Sides Dordrecht Kluwer Academic Publishers 1988

[23] H Nick Zinat Matin “Derivative free bellman qquation for ttc with two-sided certificate code and numerical companion” https://github.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Derivative-free Bellman equation for dynamic time-to-collision allows for characterization of V uniquely by advancing prediction for a fixed duration or until contact and adding elapsed time. This enables explicit approximation of the feedback map V without needing derivatives of the candidate, which is crucial when evaluating maps requires forward integration.

  2. Two-sided error bounds use only the candidate’s residual along complete stopped trajectories and its error at their endpoints to characterize V uniquely. This provides a certificate that permits arbitrary finite-valued candidates on the trajectories and their reached endpoints, offering robustness to errors in nodal TTC values.

  3. Optimization-free ReLU realization of V has explicit size, controlled local residual, and robustness to errors in nodal TTC values when restricted to compact subsets of the transversal domain. This allows for the construction of a computable approximation with depth and size estimates based only on geometric parameters.

  4. The system can utilize exact iteration where Exact continuum iteration recovers V after finitely many sweeps, including one additional sweep for initializations that violate the boundary condition. This suggests a method to achieve high accuracy in dynamic programming subsolutions through finite sweeps of the operator.

  5. The optional-duration infimum operator's fixed points are exactly the dynamic-programming subsolutions, so its residual alone does not identify V. This distinction helps researchers understand what information is contained in different formulations of the TTC map, preventing reliance on residuals that do not uniquely determine V.

Abstract

Dynamic time-to-collision (TTC) is the first contact time of a prediction flow and defines a feedback map implicitly. We study its capped value function for Carathéodory dynamics with bounded, measurable forcing. A self-contained argument establishes local Lipschitz continuity on the transversal collision domain. A derivative-free stopped-step Bellman equation then characterizes uniquely: it advances the prediction for a fixed duration or until contact and adds the elapsed time. A two-sided error bound uses only the candidate's residual along complete stopped trajectories and its error at their endpoints. Exact continuum iteration recovers after finitely many sweeps, including one additional sweep for initializations that violate the boundary condition. We also characterize an optional-duration infimum operator: its fixed points are the dynamic-programming subsolutions, so its residual alone does not identify. Finally, on compact subsets of the transversal domain, an optimization-free ReLU construction has explicit size, controlled local residual, and robustness to errors in its nodal TTC values. The optimal velocity model provides the running application.

Related papers