Abstract
Factored Markov Decision Processes (FMDPs) provide a compact representation for complex environments but often suffer from the curse of dimensionality as the number of state features increases. Model minimization techniques mitigate this by grouping equivalent states into a reduced partition; however, traditional iterative splitting algorithms are often computationally expensive and lack a clear mathematical foundation. This paper introduces an analytic framework that characterizes the minimal model as a product of input features. By distinguishing between structural and numerical minimization, the authors derive a closed-form expression for the coarsest partition and propose a new "Merge" algorithm. This algorithm achieves linear complexity relative to the partition size, significantly outperforming the quadratic complexity of traditional state-splitting methods.
Introduction
In automated planning, Factored Markov Decision Processes (FMDPs) are the standard for representing environments where state spaces are defined by sets of variables or fluents. While FMDPs are more compact than explicit state-space models, they remain susceptible to the "curse of dimensionality," where the state space grows exponentially with the number of features.
To address this, researchers employ model minimization—a process of grouping states that behave identically under all actions (action-equivalence) to create a smaller, more manageable model. Historically, this has been achieved through iterative state-splitting algorithms. While effective, these methods are often viewed as "black boxes," making it difficult to predict the final model size or understand the direct relationship between input features and the resulting partition. This paper moves model minimization from a procedural, iterative process to a rigorous analytic framework.
Analytic Characterization of Minimization
The authors propose that model minimization should be viewed as a mathematical structure rather than a sequence of operations. This framework relies on three core pillars:
1. Partitions as Products
The research defines operations on partitions (sets of state formulas) and demonstrates that the minimized model can be expressed as a mathematical product of the input partitions. This allows the minimization problem to be treated algebraically.
2. Structural vs. Numerical Minimization
A key distinction is made between two types of equivalence:
- Structural Minimization: Based on the inherent logic and dependencies of the model's features.
- Numerical Minimization: Accounts for "accidental" mathematical coincidences where different probabilities or rewards happen to result in identical expected values.
3. Closed-Form Expression
The authors prove that the "coarsest structural partition"—the simplest possible version of the model—can be written as a closed-form formula. This theoretical breakthrough transforms minimization from a search problem into a direct calculation.
The Merge Algorithm
Leveraging these analytic results, the paper introduces Algorithm 4 (The Merge Algorithm). Traditional state-splitting methods (Algorithm 2) utilize a "local" approach, checking pairs of state blocks one by one to see if they remain stable. This often results in redundant checks across different parts of the state space.
In contrast, the Merge Algorithm performs checks on action-specific partitions "globally." By treating the partition as a global product, the algorithm can update the entire model simultaneously. If an action separates two states in one area of the model, the algorithm recognizes that it likely separates similar pairs elsewhere, avoiding the need to re-verify the same logic for every possible combination of variables.
Evaluation: The COFFEE Domain
The approach was evaluated using the COFFEE domain, a classic benchmark featuring a robot tasked with fetching coffee while staying dry. The scenario involves 6 state variables (Location, Wet, Umbrella, Raining, Robot-has-coffee, User-has-coffee) and 4 actions.
The COFFEE domain serves as a qualitative demonstration of the algorithm's efficiency. For instance, the algorithm identifies that "raining with an umbrella" is fundamentally different from "raining without an umbrella." Once this distinction is made, the Merge Algorithm applies it globally, whereas previous state-of-the-art methods would re-verify this fact repeatedly for every other variable state (e.g., whether the user already has coffee).
Complexity and Results
The primary contribution of this work is the formal reduction in computational complexity:
- Traditional Iterative Splitting: Operates with a complexity of $O(|P|^2)$ relative to the number of blocks in the final partition.
- The Merge Algorithm: Operates with linear complexity ($O(|P|)$) relative to the partition size.
This shift from quadratic to linear scaling allows the minimization process to remain viable even as the complexity of the FMDP increases.
Conclusion and Future Work
While this paper provides a robust theoretical foundation for exact model minimization, several avenues for future research remain. The current framework focuses on finding states that are perfectly identical; extending this to approximate partitioning—where states are "nearly" identical—is a critical next step for real-world applications. Additionally, while the analytic results are powerful, integrating them with modern approximate FMDP solvers could yield significant speedups for industrial-scale planning problems. By turning a procedural problem into an algebraic one, this work provides a clearer path toward efficient automated reasoning in complex, factored environments.
Summary updated