# Cost-augmented Schr"odinger bridges on graphs are exactly solvable: a Feynman-Kac tilt replaces learned control

arXiv: https://arxiv.org/abs/2610.02195 · HTML: https://mlsanity.com/paper/2610.02195/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 41 references that are in the map.
- First posted on arXiv 1 Oct 2026.

## Builds on (most cited first, 22 of 22)

- [A survey of the Schr"odinger problem and some of its connections with optimal transport](https://mlsanity.com/paper/1308.0215/) (2013)
- [Approximately Solving Mean Field Games via Entropy-Regularized Deep Reinforcement Learning](https://mlsanity.com/paper/2102.01585/) (2021)
- [Deep Generalized Schr"odinger Bridge](https://mlsanity.com/paper/2209.09893/) (2022)
- [Generalized Schr"odinger Bridge Matching](https://mlsanity.com/paper/2310.02233/) (2023)
- [Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transport](https://mlsanity.com/paper/1711.01851/) (2017)
- [Schr"odinger Bridge with Quadratic State Cost is Exactly Solvable](https://mlsanity.com/paper/2406.00503/) (2024)
- [Robust transport over networks](https://mlsanity.com/paper/1603.08129/) (2016)
- [Geodesic Sinkhorn for Fast and Accurate Optimal Transport on Manifolds](https://mlsanity.com/paper/2211.00805/) (2022)
- [An entropy minimization approach to second-order variational mean-field games](https://mlsanity.com/paper/1807.09078/) (2018)
- [Conditional gradient type methods for composite nonlinear and stochastic optimization](https://mlsanity.com/paper/1602.00961/) (2016)
- [Schr"odinger's control and estimation paradigm with spatio-temporal distributions on graphs](https://mlsanity.com/paper/2312.05679/) (2023)
- [Discrete Adjoint Schr"odinger Bridge Sampler](https://mlsanity.com/paper/2602.08243/) (2026)
- [Randomized Optimal Transport on a Graph: framework and new distance measures](https://mlsanity.com/paper/1806.03232/) (2018)
- [Markovian Traffic Equilibrium Assignment based on Network Generalized Extreme Value Model](https://mlsanity.com/paper/2009.02033/) (2020)
- [A Generalized Sinkhorn Algorithm for Mean-Field Schr"odinger Bridge](https://mlsanity.com/paper/2604.06531/) (2026)
- [Graph-structured tensor optimization for nonlinear density control and mean field games](https://mlsanity.com/paper/2112.05645/) (2021)
- [Entropic Optimal Transport Problem with Convex Functional Cost](https://mlsanity.com/paper/2503.11843/) (2025)
- [Generalized Schr"odinger Bridge on Graphs](https://mlsanity.com/paper/2602.04675/) (2026)
- [Spectral analysis of the logit mapping and implications for stochastic user equilibrium algorithms](https://mlsanity.com/paper/2605.21843/) (2026)
- [Twisted Schr"odinger Bridge Matching](https://mlsanity.com/paper/2607.16987/) (2026)
- [The BAR-SOT Method: Long-term Average Cost Control as Stochastic Optimal Self-Transport](https://mlsanity.com/paper/2609.17966/) (2026)
- [Quantum-Enhanced Sampling of Schr"odinger Bridges](https://mlsanity.com/paper/2609.27103/) (2026)

## Abstract (arXiv)

The generalized Schr"odinger 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 is gradient descent on a strongly convex function, and its residual bounds its error. On a protein-folding model, a free-energy cost lowers the expected barrier of the folding paths. On the learned approach's road network, roll-outs of the exact bridge match the target within sampling error, and on networks with millions of intersections its memory grows linearly.