Generalized Schrödinger Bridge on Graphs
This addresses the challenge of transportation on graphs for domains requiring actionable policies, offering a novel scalable solution that generalizes across sparse topologies and scales with graph size and time horizon.
The paper tackles the problem of learning executable controlled continuous-time Markov chain policies on arbitrary graphs under state cost augmented dynamics, introducing Generalized Schrödinger Bridge on Graphs (GSBoG) as a scalable data-driven framework that learns accurate, topology-respecting policies while optimizing application-specific intermediate state costs.
Transportation on graphs is a fundamental challenge across many domains, where decisions must respect topological and operational constraints. Despite the need for actionable policies, existing graph-transport methods lack this expressivity. They rely on restrictive assumptions, fail to generalize across sparse topologies, and scale poorly with graph size and time horizon. To address these issues, we introduce Generalized Schrödinger Bridge on Graphs (GSBoG), a novel scalable data-driven framework for learning executable controlled continuous-time Markov chain (CTMC) policies on arbitrary graphs under state cost augmented dynamics. Notably, GSBoG learns trajectory-level policies, avoiding dense global solvers and thereby enhancing scalability. This is achieved via a likelihood optimization approach, satisfying the endpoint marginals, while simultaneously optimizing intermediate behavior under state-dependent running costs. Extensive experimentation on challenging real-world graph topologies shows that GSBoG reliably learns accurate, topology-respecting policies while optimizing application-specific intermediate state costs, highlighting its broad applicability and paving new avenues for cost-aware dynamical transport on general graphs.