Research map / Learning theory and algorithms / Optimal transport
Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficiently
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that bisimulation metrics equal bicausal optimal transport distances between Markov chains, reformulates the problem as a finite-dimensional LP over occupancy couplings, and proposes Sinkhorn Value Iteration (SVI) to compute them efficiently.
Problem
Computing optimal transport distances between infinite-horizon Markov chains (equivalently bisimulation metrics) has been inefficient because the Bellman operators require solving a full static OT problem per state pair at every iteration.
Approach
Reformulates bicausal OT distances between Markov chains as an LP over occupancy couplings (a finite projection of joint path laws), shows bisimulation metrics coincide with these OT distances under cost (1-γ)|r(x)-r(y)|, and adapts entropy-regularized Mirror Sinkhorn to this LP, yielding Sinkhorn Value Iteration that costs about one vanilla Sinkhorn per state pair.
Key results
- Theorem: SVI with K >= 324||c||^2 log(|X||Y|)/((1-γ)^5 ε^2) iterations gives an ε-accurate estimate of the bisimulation/OT distance from above.
- In 4-rooms experiments, SVI and SPI converge to the true distance at a rate largely unaffected by the number of inner projection steps m, with m=1 remaining competitive.
- The paper claims SVI is significantly more efficient than the best prior methods for computing bisimulation metrics, at roughly the cost of vanilla Sinkhorn per state pair.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| vary the value-iteration update count m (ablation) | SVI and SPI · 4-rooms | convergence rate to the true distance | No clear effect |
| use m=1 (ablation) | SVI and SPI · 4-rooms | convergence to the true distance | No clear effect |
| use SPI instead of SVI (ablation) | Sinkhorn Value Iteration · 4-rooms | convergence to the optimum | Mixed |
| use SPI instead of SVI (ablation) | Sinkhorn Value Iteration · reported experiments | performance | No clear effect |
| use Sinkhorn Value Iteration | computing bisimulation metrics · Markov chains | computational efficiency | Helped |
Surprising findings
- Inner projection steps can be reduced to m=1 without noticeably hurting convergence, contrary to the theory which requires m=infinity.
Limitations
- Theoretical guarantees only hold for perfect projection steps (m=infinity), not for the finite-m variants used in practice.
- Assumes known transition kernels; no learning from interaction data is developed.
- Experiments are limited to small, simple gridworld environments.
Experimental setup
Datasets: 4-rooms gridworld environment nine-state gridworld
Benchmarks: 4-rooms environment gridworld distance comparison
Metrics: estimated transport cost convergence over iterations
Baselines: Sinkhorn policy iteration (Calo et al.) network simplex per state pair (Chen & Hansen-style LP) approximate policy iteration with Sinkhorn
Builds on: Mirror Sinkhorn Sinkhorn algorithm bisimulation metrics (Ferns et al.) entropy-regularized MDPs
Closest papers by meaning
- Distances for Markov chains from sample streams (NeurIPS 2025 · similarity 0.92)
- A Scalable Constant-Factor Approximation Algorithm for $W_p$ Optimal Transport (ICLR 2026 · similarity 0.87)
- Scalable Methods for Computing State Similarity in Deterministic Markov Decision Processes (AAAI 2020 · similarity 0.87)
- Low-Rank Optimal Transport through Factor Relaxation with Latent Coupling (NeurIPS 2024 · similarity 0.86)
- A Generalized Bisimulation Metric of State Similarity between Markov Decision Processes: From Theoretical Propositions to Applications (NeurIPS 2025 · similarity 0.85)
- A Combinatorial Algorithm for the Semi-Discrete Optimal Transport Problem (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.