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