mlsanityData to 7 Oct 2026

Learning Mixtures of Markov Chains and MDPs

arXiv 2211.09403 ↗First posted 17 Nov 2022stat.ML cs.LGcited by 12

Not on the map. Why?

Abstract (arXiv)

We present an algorithm for learning mixtures of Markov chains and Markov decision processes (MDPs) from short unlabeled trajectories. Specifically, our method handles mixtures of Markov chains with optional control input by going through a multi-step process, involving (1) a subspace estimation step, (2) spectral clustering of trajectories using "pairwise distance estimators," along with refinement using the EM algorithm, (3) a model estimation step, and (4) a classification step for predicting labels of new trajectories. We provide end-to-end performance guarantees, where we only explicitly require the length of trajectories to be linear in the number of states and the number of trajectories to be linear in a mixing time parameter. Experimental results support these guarantees, where we attain 96.6% average accuracy on a mixture of two MDPs in gridworld, outperforming the EM algorithm with random initialization (73.2% average accuracy).

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 8 of its 28 references that are in the map. First posted on arXiv 17 Nov 2022.

Builds on

8 of 28 references.

References · 8

  1. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
  2. 2013Sample Complexity of Multi-task Reinforcement Learningcited by 58
  3. 2017Toeplitz Inverse Covariance-Based Clustering of Multivariate Time Series Datacited by 47
  4. 2020Meta-learning for mixed linear regressioncited by 44
  5. 2016Optimality of the Johnson-Lindenstrauss Lemmacited by 41
  6. 2022Learning Mixtures of Linear Dynamical Systemscited by 15
  7. 2022Model-Free and Model-Based Policy Evaluation when Causality is Uncertaincited by 12
  8. 2021Coresets for Time Series Clusteringcited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 2; 2024: 6; 2025: 2; 2026: 1.

12 papers.

  1. 2022Offline Policy Evaluation and Optimization under Confoundingcited by 12
  2. 2024RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluationcited by 5
  3. 2024Test-Time Regret Minimization in Meta Reinforcement Learningcited by 5
  4. 2024Two-way Deconfounder for Off-policy Evaluation in Causal Reinforcement Learningcited by 5
  5. 2023Learning Mixtures of Markov Chains with Quality Guaranteescited by 4
  6. 2024ULTRA-MC: A Unified Approach to Learning Mixtures of Markov Chains via Hitting Timescited by 2
  7. 2025Multiple Choice Learning of Low-Rank Adapters for Language Modelingcited by 2
  8. 2023Joint Problems in Learning Multiple Dynamical Systemscited by 1
  9. 2024Markovletics: Methods and A Novel Application for Learning Continuous-Time Markov Chain Mixturescited by 1
  10. 2025Near-Optimal Clustering in Mixture of Markov Chainscited by 1
  11. 2024Variational Markov chain mixtures with automatic component selectioncited by 0
  12. 2026On Computing Total Variation Distance Between Mixtures of Product Distributionscited by 0