Efficient Solution Algorithms for Factored MDPs

By Carlos Guestrin, Daphne Koller, Ronald E. Parr, Shobha Venkataraman. 2003

570 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Reinforcement Learning, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Reinforcement Learning

In Optimization & Training

Citations in the corpus

Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation (2016, methodology): “Their representation is similar to that of Guestrin et al.[16], who describe an object-based representation in the context of planning.”
MAVEN: Multi-Agent Variational Exploration (2019, background): “To tackle computational intractability from exponential blow-up of state-action space, Guestrin et al. [16, 17] use coordination graphs to factor large MDPs for multi-agent systems and propose inter-agent communication arising from message passing on the graphs.”
The Representational Capacity of Action-Value Networks for Multi-Agent Reinforcement Learning (2019, background): “To overcome these difficulties and be able to learn useful representations while not incurring excessive costs, a middle ground is to learn factored Q-value functions [7, 8], which represent the joint value but decompose it as the sum of a number of local components, each involving only a subset of ”
Optimal and Approximate Q-value Functions for Decentralized POMDPs (2008, background): “In the last decades, the Markov decision process (MDP) framework has gained in popularity in the AI community as a model for planning under uncertainty (Boutilier, Dean, & Hanks, 1999; Guestrin, Koller, Parr, & Venkataraman, 2003 ).”
Schema Networks: Zero-shot Transfer with a Generative Causal Model of Intuitive Physics (2017, positive): “However, neither OO-MDPs nor R-MDPs deﬁne a transition function with an explicit OR of possible causes, and traditionally transition functions have not been learned in these models.”
Near-optimal Reinforcement Learning in Factored MDPs (2014, background): “M L ] 1 5 M ar 2 Any learning algorithm over Markov decision processes (MDPs) will have worst-case regret Ω( √”
Composable Planning with Attributes (2018, background): “Factored MDP and Relational MDP Our approach is closely related to factored MDP (Boutilier et al., 1995; 2000; Guestrin et al., 2003b).”
Learning the structure of Factored Markov Decision Processes in reinforcement learning problems (2006, methodology): “, 2000) or techniques based on Linear Programming algorithms (Guestrin et al., 2003).”
Fairness in Multi-Agent Sequential Decision-Making (2014, methodology): “Existing approaches to solving factored multi-agent MDPs [4] have focused on the utilitarian solution criterion, i.”
Context-Specific Representation Abstraction for Deep Option Learning (2021, background): “In this work, we further assume that the environment structure can be modeled as a factored MDP in which the state space S is factored into n variables: S = {S1, . . . ,Sn}, where each Si takes on values in a finite domain and i∈{1, . . . , n} (Guestrin et al. 2003).”
Probabilistic inference for solving discrete and continuous state Markov Decision Processes (2006, methodology): “For instance, in the ﬁeld of planning, they include work on Factored Markov Decision Processes (Boutilier et al., 1995; Koller & Parr, 1999; Guestrin et al., 2003; Kve-ton & Hauskrecht, 2005) or abstractions (Hauskrecht Appearing in Proceedings of the 23 rd International Conference on Machine Learni”
Proto-value Functions: A Laplacian Framework for Learning Representation and Control in Markov Decision Processes (2007, methodology): “However, most approaches (with notable exceptions discussed below) are based on a fixed parametric architecture, and a parameter estimation method is used to approximate value functions, such as temporal-difference learning (Sutton and Barto, 1998; Tsitsiklis and Van Roy, 1997), least squares projec”
Value-Function-Based Transfer for Reinforcement Learning Using Structure Mapping (2006, methodology): “…and actions and thus the transfer functional automatically, using domain knowledge represented as QDBNs. Prior work considering transfer using DBN models (Guestrin et al., 2003a; Mausam & Weld, 2003) assumes that the source task is a planning problem represented as DBNs (thus with probabilities).”
Action understanding as inverse planning. (2009, background): “Our computational framework formalizes action understanding as Bayesian inverse planning: the Bayesian inversion of models of probabilistic planning in Markov decision problems (MDPs).”