Maximum Likelihood Tensor Decomposition of Markov Decision Process

Model reduction is critical to reinforcement learning in high dimensions. In this paper, we study how to learn a reduced model of an unknown Markov decision process (MDP) from empirical trajectories. We focus on estimating the tensor decomposition of an unknown MDP, where the factor matrices correspond to the state and action features. For this purpose, we develop a tensor-rank-constrained maximum likelihood estimator and prove statistical upper bounds of the Kullback-Leiber divergence error and the ℓ₂ error between the estimated model and true model. An information-theoretic lower bound for the estimation error is also provided and it nearly matches the upper bound. This estimator provides a statistically efficient approach for model compression and feature extraction in reinforcement learning.