Abstract
Many large Markov decision processes (MDPs) can be represented compactly using a structured representation such as a dynamic Bayesian network. Unfortunately, the compact representation does not help standard MDP algorithms, because the value function for the MDP does not retain the structure of the process description. We argue that in many such MDPs, structure is approximately retained. That is, the value functions are nearly additive: closely approximated by a linear function over factors associated with small subsets of problem features. Based on this idea, we present a convergent, approximate value determination algorithm for structured MDPs. The algorithm maintains an additive value function, alternating dynamic programming steps with steps that project the result back into the restricted space of additive functions. We show that both the dynamic programming and the projection steps can be computed efficiently, despite the fact that the number of states is exponential in the number of state variables.
Introduction
Markov Decision Processes (MDPs) are the standard mathematical framework for planning under uncertainty. However, they suffer from a massive scaling problem known as the "curse of dimensionality": as you add more variables to a state, the number of possible states grows exponentially. While "Factored MDPs" use Dynamic Bayesian Networks (DBNs) to represent transitions and rewards compactly, the resulting value functions—the maps of how "good" every state is—usually explode in complexity. In most cases, every variable eventually influences every other variable, forcing the value function to be represented as a giant, unmanageable table.
Koller and Parr address this by proposing that value functions in many real-world tasks are nearly additive. They introduce a method to compute these functions by restricting the solution to a linear combination of local "basis functions," providing a mathematically sound way to compute approximations efficiently without enumerating the full state space.
Methodology: Constrained Value Determination
The authors introduce a Constrained Value Determination algorithm. Instead of finding the exact value function $V$, they restrict $V$ to a space of functions that are linear combinations of local basis functions: $V(s) = \sum_{i} w_i \cdot h_i(s)$. The algorithm follows a two-step iterative loop:
- Backprojection (DP Step): The current approximate value function is passed through the standard Bellman equation to compute the "next" value.
- Projection Step: Because the result of the DP step likely falls outside the restricted space, the algorithm "projects" it back, finding the closest function within the allowed linear combination.
To ensure convergence, the authors use a weighted Euclidean distance for the projection. The weights are determined by the stationary distribution of the policy—representing how often an agent visits each state. To maintain efficiency, they leverage the Boyen-Koller (BK) algorithm, which allows for approximating these weights and performing global calculations using only local computations on small clusters of variables.
Experimental Setup: The 6-Machine Factory
The paper evaluates the algorithm using a synthetic 64-state MDP representing a factory environment. In this model, machines are interconnected, and failures can cause cascades through the production line. The goal is to evaluate the value of different maintenance policies, such as "reliable-first" (fixing the most reliable machines first) versus "resilient-first."
Results and Analysis
The algorithm successfully converged in all factory experiments. A key finding was that the choice of weighting in the projection step is critical; the weighted version (using the stationary distribution) consistently outperformed unweighted least-squares in terms of both stability and accuracy.
As shown in the experimental data, increasing the complexity of the basis functions (e.g., including correlated pairs of machines like $h(M_2, M_1)$) significantly reduces the error. In the 64-state factory model, the authors achieved a very low error (RMS error < 0.141) using only 10 parameters, a massive compression compared to the 64 parameters required for an exact table. Qualitatively, the approximate value functions correctly maintained the "dominance" of better policies, proving the approximation is sufficient for effective decision-making.
Conclusion
This work demonstrates that additive structure is a natural and powerful way to approximate value functions in structured MDPs. By exploiting the locality of interactions through DBNs and the BK algorithm, it is possible to perform complex global projections efficiently. While the current focus is on value determination for a fixed policy, this approach provides a foundation for more complex factored planning and reinforcement learning algorithms in high-dimensional spaces.
Summary updated