# Optimal Transport for Stationary Markov Chains via Policy Iteration

arXiv: https://arxiv.org/abs/2006.07998 · HTML: https://mlsanity.com/paper/2006.07998/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jun 2020.

## Built on by (most cited first, 8 of 8)

- [Weisfeiler-Lehman meets Gromov-Wasserstein](https://mlsanity.com/paper/2202.02495/) (2022)
- [Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficiently](https://mlsanity.com/paper/2406.04056/) (2024)
- [Trade-off Between Dependence and Complexity for Nonparametric Learning -- an Empirical Process Approach](https://mlsanity.com/paper/2401.08978/) (2024)
- [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)
- [Distances for Markov chains from sample streams](https://mlsanity.com/paper/2505.18005/) (2025)
- [Generalized Schr"odinger Bridge on Graphs](https://mlsanity.com/paper/2602.04675/) (2026)
- [Estimation of Stationary Optimal Transport Plans](https://mlsanity.com/paper/2107.11858/) (2021)

## Abstract (arXiv)

We study the optimal transport problem for pairs of stationary finite-state Markov chains, with an emphasis on the computation of optimal transition couplings. Transition couplings are a constrained family of transport plans that capture the dynamics of Markov chains. Solutions of the optimal transition coupling (OTC) problem correspond to alignments of the two chains that minimize long-term average cost. We establish a connection between the OTC problem and Markov decision processes, and show that solutions of the OTC problem can be obtained via an adaptation of policy iteration. For settings with large state spaces, we develop a fast approximate algorithm based on an entropy-regularized version of the OTC problem, and provide bounds on its per-iteration complexity. We establish a stability result for both the regularized and unregularized algorithms, from which a statistical consistency result follows as a corollary. We validate our theoretical results empirically through a simulation study, demonstrating that the approximate algorithm exhibits faster overall runtime with low error. Finally, we extend the setting and application of our methods to hidden Markov models, and illustrate the potential use of the proposed algorithms in practice with an application to computer-generated music.