Distances for Markov chains from sample streams

2025/05/23 by Sergio Calo, Calo, Sergio, Anders Jonsson +7 · 1 voice · 1 citation
Computer Science · Mathematics · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.2505.18005

Abstract

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.

Citations

• Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficiently
• High Rank Path Development: an approach of learning the filtration of stochastic processes
• A Note on Loss Functions and Error Compounding in Model-based Reinforcement Learning
• Dealing with unbounded gradients in stochastic saddle-point optimization
• Distances for Markov Chains, and Their Differentiation
• Computational methods for adapted optimal transport
• Approximate Policy Iteration with Bisimulation Metrics
• Minibatch optimal transport distances; analysis and applications
• Bicausal Optimal Transport for Markov Chains via Dynamic Programming
• Learning Invariant Representations for Reinforcement Learning without Reconstruction
• COT-GAN: Generating Sequential Data via Causal Optimal Transport
• Optimal Transport for Stationary Markov Chains via Policy Iteration
• Stochastic Optimization for Regularized Wasserstein Estimators
• Online Learning: A Modern Introduction Using Convex Optimization
• Scalable methods for computing state similarity in deterministic Markov\n Decision Processes
• Mastering Atari, Go, chess and shogi by planning with a learned model
• Learning with minibatch Wasserstein : asymptotic and gradient properties
• Provably efficient RL with Rich Observations via Latent State Decoding
• Empirical Regularized Optimal Transport: Statistical Theory and\n Applications
• Optimal Transport for structured data with application on graphs
• Large-Scale Optimal Transport and Mapping Estimation
• Learning Generative Models with Sinkhorn Divergences
• Causal transport in discrete time and applications
• Stochastic Optimization for Large-scale Optimal Transport
• On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities
• Continuous control with deep reinforcement learning
• Causal transference plans and their Monge-Kantorovich problems
• Metrics for Finite Markov Decision Processes
• Gymnasium: A Standard Interface for Reinforcement Learning Environments

Cited by

• Near-Optimal Clustering in Mixture of Markov Chains

Discussions

• i generally think this work uncovers a space of ideas with huge potential impact, and many beautiful intellectual challenges to address. check out the paper for more details if you also find it intere [bsky, 4 points, 0 comments]

Related

• Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficiently
• Robust Probabilistic Bisimilarity for Labelled Markov Chains
• Scalable methods for computing state similarity in deterministic Markov\n Decision Processes
• Online Sinkhorn: Optimal Transport distances from sample streams
• Linear Distances between Markov Chains