# Learning Markov models via low-rank optimization

arXiv: https://arxiv.org/abs/1907.00113 · HTML: https://mlsanity.com/paper/1907.00113/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2019.

## Built on by (most cited first, 12 of 12)

- [From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformers](https://mlsanity.com/paper/2402.13512/) (2024)
- [Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning](https://mlsanity.com/paper/2310.06793/) (2023)
- [Low-Rank Contextual Reinforcement Learning from Heterogeneous Human Feedback](https://mlsanity.com/paper/2412.19436/) (2024)
- [Learning Good State and Action Representations via Tensor Decomposition](https://mlsanity.com/paper/2105.01136/) (2021)
- [Speed Up the Cold-Start Learning in Two-Sided Bandits with Many Arms](https://mlsanity.com/paper/2210.00340/) (2022)
- [Likelihood estimation of sparse topic distributions in topic models and its applications to Wasserstein document distance calculations](https://mlsanity.com/paper/2107.05766/) (2021)
- [ULTRA-MC: A Unified Approach to Learning Mixtures of Markov Chains via Hitting Times](https://mlsanity.com/paper/2405.15094/) (2024)
- [Low-Rank Tensors for Multi-Dimensional Markov Models](https://mlsanity.com/paper/2411.02098/) (2024)
- [A space-decoupling framework for optimization on bounded-rank matrices with orthogonally invariant constraints](https://mlsanity.com/paper/2501.13830/) (2025)
- [Tucker Diffusion Model for High-dimensional Tensor Generation](https://mlsanity.com/paper/2604.00481/) (2026)
- [Detection and Evaluation of Clusters within Sequential Data](https://mlsanity.com/paper/2210.01679/) (2022)
- [Estimating the number of clusters of a Block Markov Chain](https://mlsanity.com/paper/2407.18287/) (2024)

## Abstract (arXiv)

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 of 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.