Estimation of Markov Chain via Rank-Constrained Likelihood

Abstract

This paper studies the estimation of low-rank Markov chains from empirical trajectories. We propose a non-convex estimator based on rank-constrained likelihood maximization. Statistical upper bounds are provided for the Kullback-Leiber divergence and the ${\ell }_2$ risk between the estimator and the true transition matrix. The estimator reveals a compressed state space of the Markov chain. We also develop a novel DC (difference of convex function) programming algorithm to tackle the rank-constrained non-smooth optimization problem. Convergence results are established. Experiments show that the proposed estimator achieves better empirical performance than other popular approaches.

arXiv commentAccepted at ICML 2018

Cited by in corpus (3)

• State Aggregation Learning from Markov Transition Data
• Spectral State Compression of Markov Processes
• Can Agents Learn by Analogy? An Inferable Model for PAC Reinforcement Learning