# Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficiently arXiv: https://arxiv.org/abs/2406.04056 ยท HTML: https://mlsanity.com/paper/2406.04056/ ## Key facts - Cited by 6 papers in the map (data through 14 Oct 2026). - Builds on 32 of its 88 references that are in the map. - First posted on arXiv 6 Jun 2024. ## Builds on (most cited first, 30 of 32) - [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020) - [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013) - [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018) - [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015) - [Learning Invariant Representations for Reinforcement Learning without Reconstruction](https://mlsanity.com/paper/2006.10742/) (2020) - [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019) - [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017) - [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016) - [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017) - [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018) - [Diffusion Schr"odinger Bridge Matching](https://mlsanity.com/paper/2303.16852/) (2023) - [Scalable methods for computing state similarity in deterministic Markov Decision Processes](https://mlsanity.com/paper/1911.09291/) (2019) - [Contrastive Behavioral Similarity Embeddings for Generalization in Reinforcement Learning](https://mlsanity.com/paper/2101.05265/) (2021) - [COT-GAN: Generating Sequential Data via Causal Optimal Transport](https://mlsanity.com/paper/2006.08571/) (2020) - [Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks](https://mlsanity.com/paper/2210.01906/) (2022) - [Bisimulation Makes Analogies in Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2204.13060/) (2022) - [Learning Wasserstein Embeddings](https://mlsanity.com/paper/1710.07457/) (2017) - [Causal transport in discrete time and applications](https://mlsanity.com/paper/1606.04062/) (2016) - [Weisfeiler-Lehman meets Gromov-Wasserstein](https://mlsanity.com/paper/2202.02495/) (2022) - [Approximate Policy Iteration with Bisimulation Metrics](https://mlsanity.com/paper/2202.02881/) (2022) - [Computational methods for adapted optimal transport](https://mlsanity.com/paper/2203.05005/) (2022) - [Optimal Transport for Stationary Markov Chains via Policy Iteration](https://mlsanity.com/paper/2006.07998/) (2020) - [Optimistic Planning by Regularized Dynamic Programming](https://mlsanity.com/paper/2302.14004/) (2023) - [A Note on Loss Functions and Error Compounding in Model-based Reinforcement Learning](https://mlsanity.com/paper/2404.09946/) (2024) - [Mirror Sinkhorn: Fast Online Optimization on Transport Polytopes](https://mlsanity.com/paper/2211.10420/) (2022) - [On the Relationship between Bisimulation and Trace Equivalence in an Approximate Probabilistic Context (Extended Version)](https://mlsanity.com/paper/1701.04547/) (2017) - [A Kernel Perspective on Behavioural Metrics for Markov Decision Processes](https://mlsanity.com/paper/2310.19804/) (2023) - [On the Performance Bounds of some Policy Search Dynamic Programming Algorithms](https://mlsanity.com/paper/1306.0539/) (2013) - [Alignment and Comparison of Directed Networks via Transition Couplings of Random Walks](https://mlsanity.com/paper/2106.07106/) (2021) - [Distances for Markov Chains, and Their Differentiation](https://mlsanity.com/paper/2302.08621/) (2023) ## Built on by (most cited first, 6 of 6) - [The Myhill-Nerode Theorem for Bounded Interaction: Canonical Abstractions via Agent-Bounded Indistinguishability](https://mlsanity.com/paper/2603.21399/) (2026) - [Distances for Markov chains from sample streams](https://mlsanity.com/paper/2505.18005/) (2025) - [Near-Optimal Clustering in Mixture of Markov Chains](https://mlsanity.com/paper/2506.01324/) (2025) - [Compositional Transduction with Latent Analogies for Offline Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2605.20609/) (2026) - [Compositional Behavioral Semantics for State Abstraction in Reinforcement Learning](https://mlsanity.com/paper/2606.25357/) (2026) - [Differentiating Bisimulation Metrics: A Framework for Parametric Markov Chain Fitting via Bicausal Optimal Transport](https://mlsanity.com/paper/2609.37239/) (2026) ## Abstract (arXiv) We propose a new framework for formulating optimal transport distances between Markov chains. Previously known formulations studied couplings between the entire joint distribution induced by the chains, and derived solutions via a reduction to dynamic programming (DP) in an appropriately defined Markov decision process. This formulation has, however, not led to particularly efficient algorithms so far, since computing the associated DP operators requires fully solving a static optimal transport problem, and these operators need to be applied numerous times during the overall optimization process. In this work, we develop an alternative perspective by considering couplings between a flattened version of the joint distributions that we call discounted occupancy couplings, and show that calculating optimal transport distances in the full space of joint distributions can be equivalently formulated as solving a linear program (LP) in this reduced space. This LP formulation allows us to port several algorithmic ideas from other areas of optimal transport theory. In particular, our formulation makes it possible to introduce an appropriate notion of entropy regularization into the optimization problem, which in turn enables us to directly calculate optimal transport distances via a Sinkhorn-like method we call Sinkhorn Value Iteration (SVI). We show both theoretically and empirically that this method converges quickly to an optimal coupling, essentially at the same computational cost of running vanilla Sinkhorn in each pair of states. Along the way, we point out that our optimal transport distance exactly matches the common notion of bisimulation metrics between Markov chains, and thus our results also apply to computing such metrics, and in fact our algorithm turns out to be significantly more efficient than the best known methods developed so far for this purpose.