Cost-Augmented Schrödinger Bridges on Graphs Are Exactly Solvable: A Feynman-Kac Approach (arXiv 2610.02195)

Paper Overview

• Field: Machine Learning
• Author: Akshay Balsubramani
• Published: 2026-10-01
• arXiv: 2610.02195

Summary

The generalized Schrödinger bridge on a graph moves mass between two distributions while charging a cost for the states visited. Existing approaches learn the rates of a controlled continuous-time Markov chain, using a temporal-difference penalty to restore the cost term.

This paper shows that a state cost can be folded into the reference process as a Feynman-Kac tilt. With this reformulation, the cost-augmented bridge becomes a plain bridge against the tilted reference, and the penalty term is no longer necessary.

Key Points

• Exact solvability: The bridge is computed exactly by alternating two endpoint rescalings, each requiring only a single sparse matrix-exponential application.
• No discretization or learning: Nothing is discretized in time, and no model learning is required.
• Convergence guarantee: The alternation converges at a rate determined solely by the endpoint coupling.
• Quadratic congestion cost: For quadratic costs on time-averaged occupancies, damped best response around the exact bridge is equivalent to gradient descent on a strongly convex function; its residual bounds the error.
• Protein folding: Free-energy costs reduce the expected potential barrier along folding paths.
• Scalability: On the road networks used by learning-based methods, rollouts of the exact bridge match the target distribution within sampling error, with memory growing linearly on networks with millions of intersections.

Original Abstract (excerpt)

> The generalized Schrödinger bridge on a graph moves mass between two distributions while charging a cost for the states visited. It has been approached by learning the rates of a controlled continuous-time Markov chain, with a temporal-difference penalty that restores the cost. A state cost folds into the reference process as a Feynman-Kac tilt. The cost-augmented bridge is then a plain bridge against the tilted reference, and the penalty is unnecessary. The bridge is computed exactly by alternating two endpoint rescalings, each one sparse matrix-exponential application; nothing is discretized in time or learned. The alternation converges at a rate set by the endpoint coupling alone. For a quadratic congestion cost on time-averaged occupancies, damped best response around the exact bridge ...

---

*Automatically collected on 2026-10-04*