Research map / Learning theory and algorithms / Optimal transport
Distances for Markov chains from sample streams
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.
Proposes SOMCOT, a stochastic primal-dual (mirror descent / gradient ascent) method that estimates bisimulation metrics (Markov chain OT distances) from sample trajectories via a new LP formulation without transition kernels.
Problem
Computing bisimulation metrics / optimal-transport distances between finite Markov chains requires full knowledge of transition kernels, which is impractical when only sample trajectories are available.
Approach
A new LP formulation of bicausal occupancy couplings that eliminates transition kernels by using sampled state-next-state pairs from each chain, solved via stochastic primal-dual mirror descent / gradient ascent with averaged primal iterates.
Key results
- Theorem gives sample complexity O~(|X||Y|(|X|+|Y|)/eps^2) iterations, each with one sample transition per chain and Theta(|X|^2|Y|^2) computation.
- Block Markov chain experiment (n=10, B=5) recovers the block structure in encoder-decoder maps after sufficient samples (1e5).
- Model selection: estimated distance is minimized at the true model parameter theta=0.5 and at the true gravity g=9.8 for pendulum.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SOMCOT-estimated bisimulation distances to select among candidate block-Markov-chain models | SOMCOT · Block Markov chains | estimated distance | Helped |
| Use SOMCOT-estimated bisimulation distances to select among candidate pendulum dynamics | SOMCOT · Pendulum-v1 | estimated distance | Helped |
| Estimate encoder-decoder maps from sampled trajectories without prior structural knowledge | SOMCOT · Block Markov chains (n=10, B=5) | recovery of block structure | Helped |
Surprising findings
- Sample complexity scales with |X||Y|(|X|+|Y|) rather than the full decision dimension |X|^2|Y|^2.
Limitations
- Only finite state spaces; scaling to large or infinite state spaces left open.
- Per-iteration computation scales with full |X|^2|Y|^2 dimensionality.
- Primal variables (conditional distributions) hard to parametrize with neural networks while keeping theoretical guarantees.
Experimental setup
Datasets: block Markov chains (synthetic random walks) Pendulum-v1 discretized trajectories
Benchmarks: block Markov chains random walk model selection Pendulum-v1 model selection
Metrics: distance estimate error vs. number of samples model selection minimum at true model
Builds on: bisimulation metrics as optimal transport (Kao/Chen et al. LP formulation) bicausal optimal transport online mirror descent
Closest papers by meaning
- Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficiently (NeurIPS 2024 · similarity 0.92)
- A Generalized Bisimulation Metric of State Similarity between Markov Decision Processes: From Theoretical Propositions to Applications (NeurIPS 2025 · similarity 0.87)
- Multi-Marginal Couplings for Metropolis--Hastings (NeurIPS 2026 · similarity 0.85)
- Deep Learning for Computing Convergence Rates of Markov Chains (NeurIPS 2024 · similarity 0.84)
- Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis (ICLR 2025 · similarity 0.84)
- Chain of Log-Concave Markov Chains (ICLR 2024 · similarity 0.83)
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.