mlsanityData to 14 Oct 2026

Near-Optimal Clustering in Mixture of Markov Chains

arXiv 2506.01324 ↗First posted 2 Jun 2025stat.ML cs.IT cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

We study the problem of clustering T trajectories of length H, each generated by one of K unknown ergodic Markov chains over a finite state space of size S. We derive an instance-dependent, high-probability lower bound on the clustering error rate, governed by the stationary-weighted KL divergence between transition kernels. We then propose a two-stage algorithm: Stage I applies spectral clustering via a new injective Euclidean embedding for ergodic Markov chains, a contribution of independent interest enabling sharp concentration results; Stage II refines clusters with a single likelihood-based reassignment step. We prove that our algorithm achieves near-optimal clustering error with high probability under reasonable requirements on T and H. Preliminary experiments support our approach, and we conclude with discussions of its limitations and extensions.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 36 of its 107 references that are in the map. First posted on arXiv 2 Jun 2025.

Builds on

36 of 107 references.

References · 36

  1. 2017Community Detection and Stochastic Block Modelscited by 319
  2. 2014Sketching as a Tool for Numerical Linear Algebracited by 288
  3. 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 79
  4. 2018An elementary introduction to information geometrycited by 76
  5. 2024RLHF from Heterogeneous Feedback via Personalization and Preference Aggregationcited by 74
  6. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 70
  7. 2016Statistical and Computational Guarantees of Lloyd's Algorithm and its Variantscited by 54
  8. 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 52
  9. 2019Optimality of Spectral Clustering in the Gaussian Mixture Modelcited by 42
  10. 2015Achieving Optimal Misclassification Proportion in Stochastic Block Modelcited by 35
  11. 2017Mixing time estimation in reversible Markov chains from a single sample pathcited by 27
  12. 2019Active Exploration in Markov Decision Processescited by 27
24 more
  1. 2019Estimating the Mixing Time of Ergodic Markov Chainscited by 25
  2. 2020Active Model Estimation in Markov Decision Processescited by 20
  3. 2015Optimal Cluster Recovery in the Labeled Stochastic Block Modelcited by 18
  4. 2013An Information-Theoretic Analysis of Hard and Soft Assignment Methods for Clusteringcited by 17
  5. 2014Accurate Community Detection in the Stochastic Block Model via Spectral Algorithmscited by 13
  6. 2015Recovering communities in the general stochastic block model without knowing the parameterscited by 13
  7. 2016Reinforcement Learning in Rich-Observation MDPs using Spectral Methodscited by 13
  8. 2022Learning Mixtures of Markov Chains and MDPscited by 12
  9. 2014Community Detection via Random and Adaptive Samplingcited by 7
  10. 2023Exact Recovery and Bregman Hard Clustering of Node-Attributed Stochastic Block Modelcited by 7
  11. 2024RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluationcited by 6
  12. 2024Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficientlycited by 6
  13. 2022Nearly Optimal Latent State Decoding in Block MDPscited by 5
  14. 2022Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexitycited by 5
  15. 2016Function-Specific Mixing Times and Concentration Away from Equilibriumcited by 4
  16. 2023Learning Mixtures of Markov Chains with Quality Guaranteescited by 4
  17. 2023Prospective Side Information for Latent MDPscited by 4
  18. 2024Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Modelscited by 3
  19. 2014Streaming, Memory Limited Algorithms for Community Detectioncited by 2
  20. 2019Empirical and Instance-Dependent Estimation of Markov Chain and Mixing Timecited by 2
  21. 2024ULTRA-MC: A Unified Approach to Learning Mixtures of Markov Chains via Hitting Timescited by 2
  22. 2025Distances for Markov chains from sample streamscited by 2
  23. 2024Markovletics: Methods and A Novel Application for Learning Continuous-Time Markov Chain Mixturescited by 1
  24. 2024Estimating the number of clusters of a Block Markov Chaincited by 1

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025Too Easily Fooled? Prompt Injection Breaks LLMs on Frustratingly Simple Multiple-Choice Questionscited by 4