Select Lab Publications


Solving Factored POMDPs with Linear Value Functions (2001)

By: Carlos Guestrin, Daphne Koller, and Ronald Parr

Abstract: Partially Observable Markov Decision Processes (POMDPs) provide a coherent mathematical framework for planning under uncertainty when the state of the system cannot be fully observed. However, the problem of finding an exact POMDP solution is intractable. Computing such solution requires the manipulation of a piecewise linear convex value function, which specifies a value for each possible belief state. This value function can be represented by a set of vectors, each one with dimension equal to the size of the state space. In nontrivial problems, however, these vectors are too large for such a representation to be feasible, preventing the use of exact POMDP algorithms. We propose an approximation scheme where each vector is represented as a l inear combination of basis functions to provide a compact approximation to the value fu nction. We also show that this representation can be exploited to allow for efficient computations in approximate value and policy iteration algorithms in the context of EMph{factored POMDPs}, where the transition model is specified using a dynamic Bayesian n etwork.

Download Information
Carlos Guestrin, Daphne Koller, and Ronald Parr (2001). "Solving Factored POMDPs with Linear Value Functions." IJCAI-01 workshop on Planning under Uncertainty and Incomplete Information (pp. 67-75). pdf   talk        
BibTeX citation

@inproceedings{Guestrin+al:ijcai-ws2001pomdps,
author = {Carlos Guestrin and Daphne Koller and Ronald Parr},
title = {Solving Factored POMDPs with Linear Value Functions},
booktitle = {IJCAI-01 workshop on Planning under Uncertainty and Incomplete Information},
pages = {67-75},
year = {2001},
address = {Seattle},
month = {August},
wwwfilebase = {ijcaiws2001-guestrin-koller-parr},
wwwtopic = {Factored MDPs}
}



full list