Abstract
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 ℓ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.
Original language | English (US) |
---|---|
Pages (from-to) | 2384-2398 |
Number of pages | 15 |
Journal | Operations Research |
Volume | 70 |
Issue number | 4 |
DOIs | |
State | Published - Jul 1 2022 |
All Science Journal Classification (ASJC) codes
- Computer Science Applications
- Management Science and Operations Research
Keywords
- DC programming
- Markov model
- non-convex optimization
- rank constrained likelihood