Efficient Solution Algorithms for Factored MDPs

Carlos Guestrin, Daphne Koller, Ronald Parr, Shobha Venkataraman

Abstract: This paper addresses the problem of planning under uncertainty in large Markov Decision Processes (MDPs). Factored MDPs represent a complex state space using state variables and the transition model using a dynamic Bayesian network. This representation often allows an exponential reduction in the representation size of structured MDPs, but the complexity of exact solution algorithms for such MDPs can grow exponentially in the representation size. In this paper, we present two approximate solution algorithms that exploit structure in factored MDPs. Both use an approximate value function represented as a linear combination of basis functions, where each basis function involves only a small subset of the domain variables. A key contribution of this paper is that it shows how the basic operations of both algorithms can be performed efficiently in closed form, by exploiting both additive and context-specific structure in a factored MDP. A central element of our algorithms is a novel linear program decomposition technique, analogous to variable elimination in Bayesian networks, which reduces an exponentially large LP to a provably equivalent, polynomial-sized one. One algorithm uses approximate linear programming, and the second approximate dynamic programming. Our dynamic programming algorithm is novel in that it uses an approximation based on max-norm, a technique that more directly minimizes the terms that appear in error bounds for approximate MDP algorithms. We provide experimental results on problems with over 10^40 states, demonstrating a promising indication of the scalability of our approach, and compare our algorithm to an existing state-of-the-art approach, showing, in some problems, exponential gains in computation time.

Introduction

Planning under uncertainty in complex environments is a fundamental challenge in artificial intelligence, often modeled using Markov Decision Processes (MDPs). However, standard MDP techniques suffer from the "curse of dimensionality," where the state space grows exponentially with the number of variables. This paper addresses this by focusing on Factored MDPs, which represent the state space using a set of variables and the transition model using a dynamic Bayesian network (DBN). While this allows for a compact model representation, the value function typically remains exponentially large, making exact solutions intractable.

A simple factored MDP with four machines (a) and its transition model represented as a dynamic Bayesian network (b).

Methodology: Exploiting Structure

The authors propose two approximate solution algorithms that leverage the structure of factored MDPs to avoid explicit state enumeration.

Linear Value Function Approximation

The core idea is to approximate the value function $V$ as a linear combination of basis functions: $V(s) = \sum_i w_i f_i(s)$. Each basis function $f_i$ depends only on a small subset of state variables. This reduces the problem from finding a value for every state to finding a small set of weights $w_i$.

Factored LP Decomposition

The primary technical contribution is a novel linear program (LP) decomposition technique. Standard approximate MDP algorithms require solving LPs with a constraint for every single state—an exponential number. The authors demonstrate that by exploiting the additive and context-specific structure of the factored model, these constraints can be compressed. Using a technique analogous to "variable elimination" in Bayesian networks, they reduce the exponentially large LP to a provably equivalent, polynomial-sized one.

Proposed Algorithms

  1. Approximate Linear Programming (ALP): Uses the factored LP trick to solve the MDP in a single optimization step.
  2. Approximate Policy Iteration (API) with Max-Norm Projection: A novel algorithm using max-norm ($L_\infty$) projection. Unlike standard $L_2$ projections, max-norm directly minimizes the terms appearing in MDP error bounds and can be computed efficiently using the factored LP decomposition.

Experimental Evaluation

The algorithms were tested on several simulated environments designed to challenge scalability and structural exploitation.

Various network topologies used in the SysAdmin problem to evaluate the scalability of the proposed algorithms.
  • SysAdmin: A network administrator problem where machines in various topologies (Ring, Star, Ring of Rings, etc.) randomly fail. The agent must decide which machine to reboot to maintain network health.
  • Process-SysAdmin: A more complex variant including running processes, testing the algorithms' ability to handle Context-Specific Independence (CSI).
  • Synthetic Benchmarks: The "Linear" and "Expon" problems were used to compare performance against existing tree-based MDP solvers.

Key Results and Insights

The experimental results demonstrate significant scalability, with the algorithms successfully solving problems with over $10^{40}$ states.

  • Polynomial Scaling: In the SysAdmin ring topology, computation time scaled at approximately $O(n^{1.5})$, where $n$ is the number of variables. This is a dramatic improvement over the exponential scaling of traditional methods.
  • Max-Norm Advantage: The use of $L_\infty$ projection in policy iteration provided better theoretical alignment with MDP error bounds and proved computationally efficient.
  • Superiority over Tree-Based Methods: On the "Expon" benchmark, the state-of-the-art Apricodd algorithm (which uses decision trees) suffered an exponential blowup. The authors' rule-based ALP approach solved it in polynomial time by capturing both additive and context-specific independence.
  • ALP vs. API: While Approximate Policy Iteration (API) has stronger theoretical guarantees, ALP was faster and more flexible in practice, allowing for more complex basis functions.

Conclusion and Future Work

This research provides a powerful framework for solving large-scale factored MDPs by converting exponential optimization problems into polynomial ones. The main limitation remains the need for manual feature engineering to define basis functions. Future work includes automated basis function discovery and the application of approximate inference techniques, such as loopy belief propagation, to handle even more densely connected variable networks.

Summary updated

Abstract

This paper addresses the problem of planning under uncertainty in large Markov Decision Processes (MDPs). Factored MDPs represent a complex state space using state variables and the transition model using a dynamic Bayesian network. This representation often allows an exponential reduction in the representation size of structured MDPs, but the complexity of exact solution algorithms for such MDPs can grow exponentially in the representation size. In this paper, we present two approximate solution algorithms that exploit structure in factored MDPs. Both use an approximate value function represented as a linear combination of basis functions, where each basis function involves only a small subset of the domain variables. A key contribution of this paper is that it shows how the basic operations of both algorithms can be performed efficiently in closed form, by exploiting both additive and context-specific structure in a factored MDP. A central element of our algorithms is a novel linear program decomposition technique, analogous to variable elimination in Bayesian networks, which reduces an exponentially large LP to a provably equivalent, polynomial-sized one. One algorithm uses approximate linear programming, and the second approximate dynamic programming. Our dynamic programming algorithm is novel in that it uses an approximation based on max-norm, a technique that more directly minimizes the terms that appear in error bounds for approximate MDP algorithms. We provide experimental results on problems with over 10^40 states, demonstrating a promising indication of the scalability of our approach, and compare our algorithm to an existing state-of-the-art approach, showing, in some problems, exponential gains in computation time.
BibTeX
@article{guestrin2003efficient,
  author = {Carlos Guestrin and Daphne Koller and Ronald Parr and Shobha Venkataraman},
  title = {{Efficient Solution Algorithms for Factored MDPs}},
  journal = {J. Artif. Intell. Res.},
  year = {2003},
  url = {https://openreview.net/forum?id=5J5KSqE7PXN},
}
Figure