Cost-augmented Schrödinger bridges on graphs are exactly solvable: a Feynman-Kac tilt replaces learned control

TL;DR

The paper shows that cost-augmented Schrödinger bridges on graphs can be solved exactly using a Feynman-Kac transformation to absorb state costs into a reference process. This eliminates the need for learned control or temporal-difference penalties, enabling exact computation via alternating sparse matrix exponentials. The method scales linearly in memory and converges rapidly, with error bounded by a residual in a gradient descent framework.

Why It Matters

It provides a computationally efficient, non-iterative solution to a class of optimal transport problems with costs, which are central to modeling dynamic systems like molecular folding and traffic networks. The absence of learned components and discretization makes it more reliable and scalable than prior methods.

Key Findings

• State costs in Schrödinger bridges can be absorbed into the reference process via a Feynman-Kac tilt, removing the need for learned control or penalty terms.
• The exact bridge is computed through alternating sparse matrix-exponential operations on endpoints, with convergence rate determined solely by the coupling between endpoints.
• For quadratic congestion costs, damped best response around the exact bridge corresponds to gradient descent on a strongly convex objective, with error bounded by the residual.