CS Paper Radar

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

Akshay Balsubramani

cs.LG ·submitted 2026-10-01 17:59 UTC · v1

Abstract

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 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.

Closest papers

Nearest neighbours by meaning across the whole index.

The BAR-SOT Method: Long-term Average Cost Control as Stochastic Optimal Self-Transport

eess.SY math.OCmath.PR ·2026-09-16 ·Sharan Srinivasan, Berke M. Turkay, Harsha Honnappa
similarity 0.64
Abstract

We reformulate average-cost (ergodic) control of a Markov jump process as a finite-horizon stochastic optimal transport (SOT) problem that jointly optimizes over the controlled evolution and the marginal law from which it starts and returns to (i.e., a self-transport). The constraint relating the marginal flow to the controlled generator is the basic adjoint relationship (BAR), so we call the resulting problem BAR-SOT. For any time horizon T>0, its optimal value is a constant scaling of the long-run average-cost rate. We give three equivalent formulations (through controlled processes, a Fokker--Planck constraint, and relaxed marginal measures) and show that the optimal dual is a stationary potential plus a term linear in time, with slope equal to the rate. A relative-entropy penalty on the control yields a cost-tilted Schrodinger bridge problem, computable by a Sinkhorn-type iteration when every transition rate is controlled, whose value converges to the unregularized optimum as the penalty vanishes. We develop the theory for finite Markov decision processes and then for general controlled Markov jump processes. A neural parametrization of the dual, trained as a physics-informed neural network (PINN), that encodes Harrison's equivalent-workload formulation (see Harrison 2000) matches the strong reinforcement-learning baseline of Dai and Gluzman (2022); numerically conditioning the fit of a sub-dominant transverse correction then improves on both that baseline and the best priority heuristic. On the input-queued switch, a graph-attention parametrization of the dual improves on the strongest matching heuristic we are aware of, with a parameter count that does not grow with the switch size.

0.38

Elysium: Simulation-Free Unbalanced Schrödinger Bridges

cs.LG cs.AIq-bio.QM ·2026-11-18 ·Zihan Wang, Jianzhe Li, Zhenyi Zhang, Peijie Zhou
similarity 0.60
Abstract · 44 pages, 9 figures

Reconstructing cellular dynamics from snapshots is challenging because the destructive nature of single-cell measurements makes tracking the same cells over time impossible. Cellular dynamics are inherently stochastic and involve changes in population size through proliferation and apoptosis. Growth-based methods represent population change as a rate on the density, which does not assign exits and entries to individual cells. Unbalanced Schrödinger bridges model individual events, but neural solvers for killed diffusion bridges simulate trajectories during training. We introduce Elysium, a simulation-free solver that jointly learns state transition and mass change. Using a killed Brownian reference and its time reversal, Elysium constructs direct regression objectives from an optimal endpoint coupling and conditional bridge distributions, without simulating trajectories during training. We show that the minimizers of the expected training objectives recover the optimal unbalanced Schrödinger bridge. Empirically, Elysium reconstructs state transitions, population size, and event distributions on simulated benchmarks with known killed-diffusion ground truth, outperforming existing deterministic and bridge-based solvers. On single-cell time courses, it interpolates cell state distributions at unobserved time points, tracks population expansion and contraction, and captures biphasic drug-response dynamics.

0.30

Learning hidden-state dynamics from unpaired snapshots with lift-project SDEs

cs.LG eess.SYmath.DS ·2026-10-31 ·Qi Wang, Uduak George, Gustaaf Jacobs
theory similarity 0.59
Abstract · 26 pages, 12 figures

Many systems are observed only through unpaired snapshots, with population samples available at each time point but no correspondence between samples at different times. These snapshots determine the one-time distributions but leave the temporal coupling unspecified, requiring a modeling prior to connect successive times. We propose the lift-project stochastic differential equation (SDE), an autonomous SDE on the observed coordinate and a few hidden coordinates, trained only to match the snapshots. Most existing methods, including time-dependent SDEs, Schrödinger bridges and optimal transport, evolve the observed coordinate alone. For a scalar observation, the classical comparison theorem implies that all such models have non-negative lagged covariance, so on data whose lagged covariance turns negative, their error has a computable floor. The lift-project SDE is not bound by this floor. On two representative partially observed systems, the Duffing and pendulum oscillators, at comparable fit to the snapshots, the proposed method reduces the lagged-covariance error by factors of 2.4 and 6.6 relative to the strongest baseline and is the only model below the error floor; one hidden coordinate is already enough for such improvement. Furthermore, if a second experiment changes only the initial state of the hidden coordinate, no single model that evolves the observed coordinate alone can fit both experiments, whereas a single lift-project SDE can.

0.29

Tangent Schrödinger Bridge Matching: Learning Stochastic Transport with Mechanistic Sensitivities

cs.LG ·2026-10-02 ·Jowaria Khan, Elizabeth Bondi-Kelly
hot direction similarity 0.58
Abstract

Predicting how stochastic systems respond to changes in viscosity, reaction rates, or external forces requires costly simulations, motivating reusable learned models. Yet matching observed outcome distributions does not ensure accurate intervention responses. We introduce Tangent Schrödinger Bridge Matching (Tangent-SBM), which learns stochastic transports from endpoint observations and mechanistic sensitivities. It propagates parameter derivatives alongside trajectories and supervises them against supplied targets. For average-response targets, single-rollout squared error also penalizes response variability; our objective uses two independent rollouts to match the mean without this additional penalty. We establish conditions under which sensitivity accuracy bounds finite-change prediction error and decision regret. Across Gaussian, stochastic double-well, PDEBench reaction--diffusion, and stochastic Navier--Stokes systems, Tangent-SBM improves sensitivity and finite-change prediction over matched conditional-bridge baselines while maintaining comparable endpoint and distributional accuracy. Controls examine target correctness, response objectives, and simulator-budget allocation. To test decision usefulness, we evaluate calibrated viscosity selection in Navier--Stokes: Tangent-SBM reduces tracking error relative to taking no action on every evaluated task.

0.36

The Risk-Sensitive Schrödinger Bridge: Is Not a KL Projection

cs.IT cs.AI ·2026-09-23 ·Hamidreza Behjoo
theory similarity 0.57
Abstract

The Schrödinger bridge owes its computational power to a single structural fact: by Girsanov's theorem the controlled problem is a Kullback--Leibler (KL) projection onto a fixed reference measure, solvable by alternating projections. This letter shows that the fact does not survive risk sensitivity. When the expected path cost is replaced by the entropic risk measure and both endpoint marginals are kept as hard constraints, the resulting fixed-point bridge value $J_θ$ (the soft-problem value at the multiplier that enforces the terminal constraint) admits no representation as a constrained KL minimum against any fixed path-space reference with a regular endpoint law (a class strictly larger than the uniformly elliptic diffusion references: no Markov property is required), even allowing an additive normalisation depending on the initial marginal. Moreover, no single reference generates the one-parameter family in the risk parameter. The obstruction is computed in closed form: the Gaussian bridge value violates, by exactly $θ/2$, a heat equation that any Gaussian smoothing of a fixed endpoint density must obey. In place of the projection, the theory rests on a terminal-multiplier fixed point and an asymmetric factorisation penalising the score energy of the backward factor.

0.24

A Trust Region Approach for Learning Schrödinger Bridges

cs.LG stat.ML ·2026-11-08 ·Takeshi Koshizuka, Denis Blessing, Max Zimmer, Sebastian Pokutta, Lorenz Richter
top venue similarity 0.57
Abstract · Accepted to NeurIPS 2026; Takeshi Koshizuka and Lorenz Richter contributed equally

We study the numerical approximation of Schrödinger Bridges in the setting where samples from the target distribution are unavailable and only an unnormalized target density is given. In this regime, the widely used iterative proportional fitting (IPF) procedure (and its variants) often exhibits severe numerical instabilities, stemming from ill-conditioned underlying control problems and from the fact that the optimal solution may lie far from the initialization. To address these issues, we propose a trust region variant of IPF that constrains successive updates to remain at a fixed Kullback-Leibler divergence from the current iterate. This restriction significantly improves numerical stability. Moreover, we show that the resulting method admits an interpretation as a mirror descent scheme with an adaptively chosen step size. We demonstrate the effectiveness of our approach on several challenging sampling tasks.

0.38

Transition Path Sampling Using Koopman Operators and Exit-Time Optimal Control

eess.SY cs.LGstat.ML ·2026-10-07 ·Boya Hou, Shane Wang, Siddharth Ambekar, Maxim Raginsky, Olgica Milenkovic
similarity 0.56
Abstract · 30 pages, 6 figures

Sampling transitions between metastable states is a central problem in dynamical systems theory and molecular dynamics in particular. A key challenge is the existence of high free-energy barriers that separate the states, making transitions extremely rare. Recent machine learning-based methods cast transition path sampling (TPS) as an optimal stochastic control (OSC) problem over a fixed time horizon, and parameterize the drift bias via a neural network trained by simulation-in-the-loop, requiring repeated biased rollouts. To address computational and performance guarantee issues of these models, we propose a new approach for the problem based on Koopman operators. Because Koopman operators are linear, their leading eigenfunctions reveal the metastable sets and provide an estimate of the committor function with no transition path information required. Furthermore, we formulate TPS as an OSC problem up to an exit time. Our time horizon is the first hitting time of the target set, and our running cost penalizes time spent in nonreactive regions by encoding the estimated committor function. We derive the optimal controller in closed form and approximate it in a reproducing kernel Hilbert space (RKHS). This reduces the problem of constructing the optimal controller to solving a single equality-constrained quadratic program, whose solution can be characterized by a linear Karush-Kuhn-Tucker (KKT) system. On the two-channel double well and alanine dipeptide, our controller increases the fraction of trajectories reaching the target from 0% to 99.8% within 1000 steps, and from 0% to 93% within 1ps, respectively.

0.26

Trajectory Optimization via Schrödinger Bridge Sampling

eess.SY ·2026-09-07 ·Mattia Mosso, Yang Liu, Heng Yang
similarity 0.56
Abstract

We take a new look at the relation between finite-horizon trajectory optimization and Schrödinger bridge sampling. Viewed as inference, KL-regularized trajectory optimization is solved by sampling from a Gibbs--Boltzmann distribution whose energy is the trajectory cost, and the adjoint Schrödinger bridge sampler (ASBS) is a simulation-free diffusion sampler designed for exactly such unnormalized targets. Hard equality path and terminal constraints, by contrast, confine the admissible decision variables to a measure-zero feasibility manifold, on which the target must be redefined intrinsically. In particular: $(a)$ we analyze two complementary parametrizations; a rollout parametrization, in which the dynamics are eliminated and only the remaining constraints shape the manifold, and a double-shooting parametrization, in which states and controls are sampled jointly and the dynamics themselves become part of the manifold; $(b)$ we establish regularity conditions under which both admissible sets are smooth embedded manifolds; $(c)$ under compactness and path-connectedness assumptions, we sample from the resulting intrinsic Gibbs measures via Riemannian ASBS, treating strict inequalities through exponential slack variables. Experiments, including contact-rich locomotion and manipulation, demonstrate the effectiveness of both regimes.

0.21