Distances for Markov chains from sample streams

Bisimulation metrics are powerful tools for measuring similarities between stochastic processes, and specifically Markov chains. Recent advances have uncovered that bisimulation metrics are, in fact, optimal-transport distances, which has enabled the development of fast algorithms for computing such metrics with provable accuracy and runtime guarantees. However, these recent methods, as well as all previously known methods, assume full knowledge of the transition dynamics. This is often an impractical assumption in most real-world scenarios, where typically only sample trajectories are available. In this work, we propose a stochastic optimization method that addresses this limitation and estimates bisimulation metrics based on sample access, without requiring explicit transition models. Our approach is derived from a new linear programming (LP) formulation of bisimulation metrics, which we solve using a stochastic primal-dual optimization method. We provide theoretical guarantees on the sample complexity of the algorithm and validate its effectiveness through a series of empirical evaluations.

39th Conference on Neural Information Processing Systems (NeurIPS 2025). and develop more efficient methods for computing bisimulation metrics. We refer to Appendix A of Calo et al. [2024] for more historical details on the two extensive lines of literature on bisimulation metrics and optimal transport for stochastic processes. In this paper, we extend this line of work and show that recasting bisimulation metrics as OT distances allows not only computational advances, but the development of a rigorous theory for statistical estimation of similarity metrics between stochastic processes. In particular, we build on the foundations laid down by Calo et al. [2024] and derive a new stochastic optimization algorithm for estimating bisimulation metrics based on sample observations only, and provide its complete computational and sample-complexity analysis for finite Markov chains. A core technical contribution is a new linear-program formulation of bisimulation metrics, which we solve via a stochastic saddlepoint optimization method. For two Markov chains with state spaces X and Y, the algorithm is guaranteed to return an ε-accurate estimate of the true similarity metric after O(|X | |Y| (|X | + |Y|)/ε 2 ) iterations, with each iteration making use of a single sample transition from each of the two chains, and costing Θ(|X | 2 |Y| 2 ) computation. This is the first result of its kind: no previous methods have successfully addressed this problem either in practice or in theory.

As mentioned above, the problem we study in this paper has been extensively studied in (at least) two major research communities. Within the optimal-transport community, the problem of computing distances between stochastic processes has been studied under the names "adapted", "causal" or "bicausal" optimal transport [