# Learning Mixtures of Markov Chains and MDPs

arXiv: https://arxiv.org/abs/2211.09403 · HTML: https://mlsanity.com/paper/2211.09403/

## Key facts

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

## Builds on (most cited first, 8 of 8)

- [RL for Latent MDPs: Regret Guarantees and a Lower Bound](https://mlsanity.com/paper/2102.04939/) (2021)
- [Sample Complexity of Multi-task Reinforcement Learning](https://mlsanity.com/paper/1309.6821/) (2013)
- [Toeplitz Inverse Covariance-Based Clustering of Multivariate Time Series Data](https://mlsanity.com/paper/1706.03161/) (2017)
- [Meta-learning for mixed linear regression](https://mlsanity.com/paper/2002.08936/) (2020)
- [Optimality of the Johnson-Lindenstrauss Lemma](https://mlsanity.com/paper/1609.02094/) (2016)
- [Learning Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2201.11211/) (2022)
- [Model-Free and Model-Based Policy Evaluation when Causality is Uncertain](https://mlsanity.com/paper/2204.00956/) (2022)
- [Coresets for Time Series Clustering](https://mlsanity.com/paper/2110.15263/) (2021)

## Built on by (most cited first, 12 of 12)

- [Offline Policy Evaluation and Optimization under Confounding](https://mlsanity.com/paper/2211.16583/) (2022)
- [RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation](https://mlsanity.com/paper/2406.01389/) (2024)
- [Test-Time Regret Minimization in Meta Reinforcement Learning](https://mlsanity.com/paper/2406.02282/) (2024)
- [Two-way Deconfounder for Off-policy Evaluation in Causal Reinforcement Learning](https://mlsanity.com/paper/2412.05783/) (2024)
- [Learning Mixtures of Markov Chains with Quality Guarantees](https://mlsanity.com/paper/2302.04680/) (2023)
- [ULTRA-MC: A Unified Approach to Learning Mixtures of Markov Chains via Hitting Times](https://mlsanity.com/paper/2405.15094/) (2024)
- [Multiple Choice Learning of Low-Rank Adapters for Language Modeling](https://mlsanity.com/paper/2507.10419/) (2025)
- [Joint Problems in Learning Multiple Dynamical Systems](https://mlsanity.com/paper/2311.02181/) (2023)
- [Markovletics: Methods and A Novel Application for Learning Continuous-Time Markov Chain Mixtures](https://mlsanity.com/paper/2402.17730/) (2024)
- [Near-Optimal Clustering in Mixture of Markov Chains](https://mlsanity.com/paper/2506.01324/) (2025)
- [Variational Markov chain mixtures with automatic component selection](https://mlsanity.com/paper/2406.04653/) (2024)
- [On Computing Total Variation Distance Between Mixtures of Product Distributions](https://mlsanity.com/paper/2605.03839/) (2026)

## 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).