Learning Markov Models Via Low-Rank Optimization

• 成果类型: Article
• 署名作者: Zhu, Ziwei; Li, Xudong; Wang, Mengdi; Zhang, Anru
• 署名单位: University of Michigan System; University of Michigan; Fudan University; Fudan University; Princeton University; Princeton University; University of Wisconsin System; University of Wisconsin Madison; Duke University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2021.2115
• 发表日期: 2022
• 关键词: Markov model; DC programming; non-convex optimization; rank constrained likelihood

摘要

Modeling unknown systems from data is a precursor of system optimization and sequential decision making. In this paper, we focus on learning a Markov model from a single trajectory of states. Suppose that the transition model has a small rank despite having a large state space, meaning that the system admits a low-dimensional latent structure. We show that one can estimate the full transition model accurately using a trajectory of length that is proportional to the total number of states. We propose two maximum likelihood estimation methods: a convex approach with nuclear norm regularization and a nonconvex approach with rank constraint. We explicitly derive the statistical rates of both estimators in terms of the Kullback-Leiber divergence and the l(2) error and also establish a minimax lower bound to assess the tightness of these rates. For computing the nonconvex estimator, we develop a novel DC (difference of convex function) programming algorithm that starts with the convex M-estimator and then successively refines the solution till convergence. Empirical experiments demonstrate consistent superiority of the nonconvex estimator over the convex one.