Efficient Solution Algorithms for Factored MDPs

Carlos Guestrin, Daphne Koller, Ronald Parr, Shobha Venkataraman

TL;DR

Factored Markov Decision Processes (MDPs) can represent massive stochastic systems compactly via Dynamic Bayesian Networks, but standard solution algorithms quickly choke on the exponential state space. This paper introduces a linear programming (LP) decomposition technique—inspired by variable elimination in graphical models—that converts exponentially large constraint sets into compact, polynomial-sized linear systems. Leveraging this insight, the authors develop practical Approximate Linear Programming (ALP) and Approximate Policy Iteration (API) algorithms that scale to factored MDPs with over $10^{40}$ states.

What Problem Does This Paper Address?

Sequential decision-making under uncertainty is classically modeled via MDPs, but real-world planning problems suffer from the curse of dimensionality: an environment described by $n$ state variables has an exponential state space ($|X| = 2^n$).

Factored MDPs represent the system's dynamics compactly using Dynamic Bayesian Networks (DBNs) and decompose rewards into localized sums. However, compact transition graphs do not guarantee compact optimal value functions. Standard exact methods (Value Iteration, Policy Iteration, LP) must enumerate every single state, becoming computationally intractable beyond ~10–15 variables. While prior work attempted function approximation, methods either relied on state partitioning (trees/decision diagrams that scale poorly when value functions have many distinct values) or least-squares projections that lack theoretical compatibility with max-norm Bellman error bounds.

Methods

The paper approximates the value function as a linear combination of localized basis functions: $V(x) = \sum_j w_j h_j(x)$, where each $h_j$ only depends on a small subset of variables.

  • LP Constraint Decomposition via Variable Elimination: Standard ALP and Chebyshev ($L_\infty$) projection formulations require checking constraints across all states: $\phi \ge \max_x \sum_i w_i c_i(x) - b(x)$. Instead of enumerating states, the authors embed cost-network variable elimination directly into the LP: intermediate functions generated during elimination are represented by auxiliary LP variables and local linear inequalities. This provably reduces an exponential number of constraints to a polynomial number proportional to the induced tree-width of the factor graph.
  • Factored Approximate Linear Programming (ALP): Formulates planning as a single compact LP. It requires neither explicit policy enumeration nor restricted action effects, making it fast and broadly applicable.
  • Factored Approximate Policy Iteration (API) with Max-Norm Projection: Introduces the first dynamic programming scheme for factored MDPs using an $L_\infty$-norm projection instead of $L_2$ regression, directly minimizing the error term that governs theoretical policy-loss bounds. Under a "default action" model (actions only affect a small set of variables), greedy policies are represented compactly as decision lists.
  • Exploiting Context-Specific Independence (CSI): Extends both the backprojection and LP decomposition techniques from tabular factor representations to rule-based representations, avoiding variable-splitting when conditional probabilities collapse under specific contexts.

Datasets

The authors evaluated their algorithms on several synthetic and structured benchmark planning environments:

  • SysAdmin: A network management problem where $m$ interconnected computers fail stochastically and impact their neighbors; an administrator reboots at most one machine per step. Topologies include Ring, Bidirectional Ring, Star, Ring-of-Rings, and 3-Legs (evaluated up to $m = 40$, or $\approx 10^{12}$ states).
  • Process-SysAdmin: An extended SysAdmin benchmark where each machine has three state variables (Load, Status, Selector), scaling to over $10^{40}$ states across Star, Ring, and Reverse-Star topologies.
  • Linear and Expon Benchmarks: Standard factored benchmarks designed by Boutilier et al. (2000) representing best-case and worst-case scenarios for algebraic decision diagrams (ADDs).

Key Insights and Ideas

  • Internalizing Variable Elimination in LPs: Rather than iteratively checking constraints or sampling them, the maximization step over the state space can be compiled directly into the constraint matrix in closed form using dynamic programming principles.
  • $L_\infty$ Projection Resolves "Norm Incompatibility": Theoretical bounds on value iteration and policy loss rely on max-norm contraction. Minimizing $L_\infty$ error via linear programming produces tighter, monotonically decaying a posteriori error bounds than Euclidean ($L_2$) projections.
  • Linear Value Functions Beat Leaf Agglomeration: Decision-tree and ADD methods (e.g., APRICODD) partition the state space, meaning $k$ leaves represent at most $k$ distinct values. A factored linear combination of $k$ basis functions can represent up to $2^k$ distinct values, preventing the severe policy degradation seen in tree methods when the true value function varies smoothly across states.
  • ALP Practically Outperforms API: Even though API provides stronger theoretical max-norm convergence bounds, Factored ALP is significantly simpler and faster per solve. In practice, computation time saved by ALP can be invested into using richer basis functions, delivering superior final policies.

Key Results

  • Scalability: Solved instances of Process-SysAdmin with over $10^{40}$ states. On the SysAdmin ring topology, runtimes scaled empirically as $O((n \cdot |A|)^{1.5})$ with variable count $n$, in contrast to the $O(2^n)$ scaling of tabular algorithms.
  • Comparison to $L_2$-Projection: Factored API with max-norm projection yielded lower relative error to $V^*$ and lower policy loss than the $L_2$-projection algorithm of Koller & Parr (2000) on all solvable instances.
  • CSI Speedup: On the "Reverse Star" Process-SysAdmin domain—a worst-case for table-based elimination—the rule-based CSI approach prevented an exponential factor blowup, reducing exponential runtimes to polynomial time.
  • Comparison to APRICODD (ADDs): On the Expon problem, APRICODD blew up exponentially due to the need for exponentially many leaves, while Factored ALP solved it optimally in polynomial time using $n+1$ basis functions.

Limitations and Future Work

  • Induced Width Bottleneck: The size of the factored LP depends exponentially on the induced width (tree-width) of the cost network. For problems with dense, highly looped connectivity graphs, the exact decomposition becomes intractable.
  • Manual Feature Selection: Unlike tree-based algorithms that discover partitions automatically, the designer must specify basis functions upfront.
  • Policy Representation Restrictions: Factored API requires actions to have localized effects ("default action model") to represent policies as compact decision lists.
  • Proposed Future Directions: Developing automatic basis selection methods (e.g., using localized Bellman error peaks to spawn new features), incorporating approximate inference techniques such as loopy belief propagation when tree-width is high, and extending to factored POMDPs and multiagent systems.

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},
}

Loading related content...

Figure