Adaptive Low-Nonnegative-Rank Approximation for State Aggregation of Markov Chains

Yaqi Duan, Mengdi Wang, Zaiwen Wen, Yaxiang YuanSIAM J. Matrix Anal. Appl 2020 · OpenReview

TL;DR

This paper introduces a novel method for simplifying complex Markov chains by identifying a smaller, underlying "meta-state" structure. It achieves this by formulating a convex optimization problem that leverages an "atomic regularizer" to approximate the non-negative rank of the transition matrix, enabling efficient state aggregation.

What Problem Does This Paper Address?

Many real-world systems, like those in reinforcement learning or operations research, can be modeled as Markov chains. However, these chains can have an enormous number of states (high dimensionality), making them computationally intractable. The authors address the challenge of reducing this complexity by assuming that the high-dimensional states can be effectively represented by a much smaller set of "meta-states." This is akin to finding a compressed representation of the system's dynamics. The core difficulty lies in identifying this underlying structure when only observed trajectories of the system are available, and the desired representation requires non-negative factors.

Methods

The paper proposes an "adaptive low-nonnegative-rank approximation" method. The key innovation is the use of an atomic regularizer as a convex surrogate for the non-negative rank. This regularizer is then incorporated into a convex optimization problem. Since directly optimizing this convex problem is challenging, they reformulate it into a non-negative matrix factorization (NMF) problem. To tackle the non-convexity of NMF and escape local minima, they employ a proximal alternating linearized minimization (PALM) algorithm. Crucially, they introduce two adaptive strategies for adjusting the rank of the factorization: one involves appending new columns to the factor matrices (akin to a subgradient step), and the other reduces redundant dimensions through linear combinations. This iterative process aims to converge to a global optimum.

Datasets

  • Synthetic Data: The authors generate synthetic Markovian trajectories to test their algorithm's performance and statistical properties. They vary parameters like ambient dimension ($d$), intrinsic dimension ($r$), and sampling size ($n$) to analyze their impact.
  • Manhattan Transportation Data: A real-world dataset of NYC Yellow cab trips (1.1 × 10⁷ records) is used to demonstrate the algorithm's practical applicability in partitioning the Manhattan transportation network into distinct regions.

Key Insights and Ideas

  • Non-negative Rank as a Structural Indicator: The paper highlights that the "non-negative rank" of a Markov transition matrix is a crucial indicator of its underlying state aggregation structure.
  • Atomic Regularizer for Convexity: By introducing an atomic regularizer, the authors transform a non-convex problem (minimizing non-negative rank) into a convex optimization problem, making it amenable to standard optimization techniques.
  • Adaptive Rank Adjustment is Crucial: The proposed methods for adaptively adjusting the rank (appending columns and removing redundant dimensions) are essential for escaping local minima and ensuring convergence to a good solution.
  • State Aggregation for Real-World Problems: The application to the Manhattan taxi data demonstrates the practical utility of the method for understanding and simplifying complex spatio-temporal systems.

Key Results

  • Successful State Aggregation: The algorithm successfully identifies underlying state aggregation structures in synthetic data, often recovering the true intrinsic dimension.
  • Efficiency and Accuracy: Numerical experiments show that the method is efficient and achieves low recovery errors (relRE) when applied to both synthetic and real-world data, especially with appropriate regularization parameters.
  • Comparison with Existing Methods: On the Manhattan transportation data, the proposed method's zoning results are shown to be more aligned with geometric locations compared to an SVD-based method.
  • Statistical Properties: The paper investigates how parameters like dimension, sparsity, and sample size affect the recovery error, providing insights into the algorithm's behavior.

Limitations and Future Work

  • Regularization Parameter Tuning: The performance of the algorithm is sensitive to the choice of the regularization parameter ($\lambda$). While experiments explore various values, finding the optimal $\lambda$ for a given problem might require further investigation.
  • Computational Cost: Although the PALM algorithm is efficient, solving large-scale problems can still be computationally intensive.
  • Future Work: The authors suggest several avenues for future research:
  • Designing better regularization techniques beyond the atomic regularizer.
  • Developing faster methods for solving the factorized optimization model.
  • Conducting theoretical analysis on convergence to global solutions.
  • Applying the method to more complex real-world Markov decision processes.

Summary updated

Abstract

This paper develops a low-nonnegative-rank approximation method to identify the state aggregation structure of a finite-state Markov chain under an assumption that the state space can be mapped into a handful of metastates. The number of metastates is characterized by the nonnegative rank of the Markov transition matrix. Motivated by the success of the nuclear norm relaxation in low-rank minimization problems, we propose an atomic regularizer as a convex surrogate for the nonnegative rank and formulate a convex optimization problem. Because the atomic regularizer itself is not computationally tractable, we instead solve a sequence of problems involving a nonnegative factorization of the Markov transition matrices by using the proximal alternating linearized minimization method. Two methods for adjusting the rank of factorization are developed so that local minima are escaped. One is to append an additional column to the factorized matrices, which can be interpreted as an approximation of a negative subgradient step. The other is to reduce redundant dimensions by means of linear combinations. Overall, the proposed algorithm very likely converges to the global solution. The efficiency and statistical properties of our approach are illustrated on synthetic data. We also apply our state aggregation algorithm on a Manhattan transportation data set and make extensive comparisons with an existing method.
BibTeX
@article{duan2020adaptive,
  author = {Yaqi Duan and Mengdi Wang and Zaiwen Wen and Yaxiang Yuan},
  title = {{Adaptive Low-Nonnegative-Rank Approximation for State Aggregation of Markov Chains}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2020},
  url = {https://openreview.net/forum?id=QfXmQj0W0tC},
}
Figure