Policy Iteration Based on Stochastic Factorization

André da Motta Salles Barreto, Joelle Pineau, Doina Precup

Abstract

Markov Decision Processes (MDPs) are a cornerstone of sequential decision-making, yet they are plagued by the "curse of dimensionality." Standard Policy Iteration (PI) algorithms exhibit a cubic computational dependence on the number of states ($O(|S|^3)$), rendering them impractical for large-scale real-world applications. This paper introduces Policy Iteration Based on Stochastic Factorization (PISF), an algorithm designed to achieve linear complexity relative to the state space size. By decomposing the transition matrix into two smaller stochastic matrices and solving the MDP in a compressed "artificial" state space, PISF maintains high performance while drastically reducing computational overhead.

Introduction

Sequential decision-making under uncertainty is typically modeled using MDPs. However, as the state space $S$ grows—often reaching millions or billions of states in complex systems like power grids or maintenance logistics—exact solutions via dynamic programming become computationally infeasible. Traditional approximations often rely on local sampling or rigid state aggregation, which can be slow to converge or lose vital structural information.

The authors propose exploiting the underlying structural regularity of the transition model. The goal is to create a compact, accurate representation that allows for rapid solving without sacrificing the fundamental dynamics of the system.

Methods: Stochastic Factorization

The core of the PISF algorithm is the stochastic-factorization trick. This approach approximates a large, sparse transition matrix $P$ by decomposing it into two smaller stochastic matrices, $D$ and $K$.

  1. Factorization ($P \approx DK$): The matrix $D$ maps the original states to a smaller set of $m$ "artificial states," while $K$ maps these artificial states back to the original state space.
  2. The Swap ($\bar{P} = KD$): By reversing the order of the factors, the authors derive a much smaller transition matrix $\bar{P}$ of size $m \times m$. This compressed matrix retains the essential topological properties of the original process, such as recurrence and periodicity.
  3. PISF Algorithm: Instead of performing value function updates on the full state space, PISF operates on the compressed artificial state space. The value function of the small model is then mapped back to the original space to derive the policy.
Overview of stochastic factorization: The original transition matrix $P$ is decomposed into $D$ and $K$, which are then swapped to form the compressed matrix $\bar{P}$.

This factorization allows each iteration of PISF to run in linear time $O(|S|)$, provided the number of artificial states $m$ is small. The authors also provide a greedy heuristic to compute this factorization efficiently using state-action features.

Experimental Evaluation

The PISF algorithm was evaluated on a Multicomponent-Replacement Decision Task, a large-scale maintenance simulation involving assets with multiple deteriorating components. The objective is to minimize long-term costs by balancing setup costs against failure penalties.

The experiments scaled up to 39,916,800 states and 128 actions, totaling over 5 billion state-action pairs. PISF was compared against standard PI, industry-standard threshold policies, and UCT (a Monte Carlo Tree Search algorithm).

Key Results

  • Computational Efficiency: In a 5-component scenario, PISF was 37 times faster than standard PI, representing a 97% reduction in compute time.
  • Scalability: PISF solved the 40-million-state problem in under 5 hours. Standard PI was estimated to require over 8 days on the same hardware.
  • Performance: PISF consistently outperformed industry heuristics. Furthermore, when compared to UCT under the same time budget, PISF produced superior policies by leveraging the global model structure rather than relying on local trajectory sampling.

Discussion and Conclusion

PISF represents a significant advancement in solving large-scale MDPs by treating stochastic factorization as a form of "soft" state aggregation. Unlike hard aggregation, states can have fractional membership in multiple artificial states, allowing for a more nuanced representation.

The algorithm is theoretically sound, with guaranteed termination and formal bounds on performance degradation relative to factorization quality. Future work includes extending this framework to Reinforcement Learning, where the factors $D$ and $K$ could be learned directly from transition data, and integrating it with factored MDP approaches to further exploit system structure.

Summary updated

Abstract

When a transition probability matrix is represented as the product of two stochastic matrices, one can swap the factors of the multiplication to obtain another transition matrix that retains some fundamental characteristics of the original. Since the derived matrix can be much smaller than its precursor, this property can be exploited to create a compact version of a Markov decision process (MDP), and hence to reduce the computational cost of dynamic programming. Building on this idea, this paper presents an approximate policy iteration algorithm called policy iteration based on stochastic factorization, or PISF for short. In terms of computational complexity, PISF replaces standard policy iteration's cubic dependence on the size of the MDP with a function that grows only linearly with the number of states in the model. The proposed algorithm also enjoys nice theoretical properties: it always terminates after a finite number of iterations and returns a decision policy whose performance only depends on the quality of the stochastic factorization. In particular, if the approximation error in the factorization is sufficiently small, PISF computes the optimal value function of the MDP. The paper also discusses practical ways of factoring an MDP and illustrates the usefulness of the proposed algorithm with an application involving a large-scale decision problem of real economical interest.
BibTeX
@article{barreto2014policy,
  author = {André da Motta Salles Barreto and Joelle Pineau and Doina Precup},
  title = {{Policy Iteration Based on Stochastic Factorization}},
  journal = {J. Artif. Intell. Res.},
  year = {2014},
  doi = {10.1613/jair.4301},
}
Figure