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