基于样本流估算马尔可夫链相似度，无需已知转移模型
Distances for Markov chains from sample streams
- 提出新的线性规划形式，用随机对偶优化求解
- 理论证明样本复杂度，实测验证算法有效
- 适合仅有轨迹数据、无转移模型的场景
双仿真度量是衡量随机过程（特别是马尔可夫链）相似性的有力工具。近期研究发现，双仿真度量本质上是最优传输距离，这使得快速计算具有可证明精度和运行时间保证的度量成为可能。然而，这些新方法以及此前所有方法均假设完全掌握转移动态，这在多数真实场景中不切实际，因为通常仅能获取样本轨迹。本文提出一种随机优化方法，仅依赖样本访问即可估计双仿真度量，无需显式转移模型。我们的方法基于双仿真度量的新线性规划（LP）形式，采用随机原始-对偶优化求解。我们提供了算法的样本复杂度理论保证，并通过一系列实证评估验证了其有效性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。