Learning Mixtures of Markov Chains and MDPs
Learning Mixtures of Markov Chains and MDPs
复制标题
DOI：
10.48550/arxiv.2211.09403
复制
发表时间：
2022-11
期刊：
影响因子：
--
通讯作者：
Chinmaya Kausik;Kevin Tan;Ambuj Tewari
中科院分区：
文献类型：
--
作者：
Chinmaya Kausik;Kevin Tan;Ambuj Tewari
提出了一种从短的无标记轨迹中学习马尔可夫链和马尔可夫决策过程(MDP)的混合算法。具体地说，我们的方法通过经历一个多步骤的过程来处理具有可选控制输入的马尔可夫链的混合，包括(1)子空间估计步骤，(2)使用“成对距离估计器”对轨迹进行谱聚类，以及使用EM算法进行细化，(3)模型估计步骤，以及(4)用于预测新轨迹的标签的分类步骤。我们提供端到端的性能保证，其中我们只明确要求轨迹长度与状态数成线性，轨迹数与混合时间参数成线性。实验结果支持这些保证，在网格世界中，我们在两个MDP的混合上达到了96.6%的平均准确率，超过了随机初始化的EM算法(73.2%的平均准确率)。
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).