Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Partitioned Linear Programming Approximations for MDPs
Branislav Kveton, Milos Hauskrecht
Approximate linear programming (ALP) is an efficient approach to solving large factored Markov decision processes (MDPs). The main idea of the method is to approximate the optimal value function by a set of basis functions and optimize their weights by linear programming (LP). This paper proposes a new ALP approximation. Comparing to the standard ALP formulation, we decompose the constraint space into a set of low-dimensional spaces. This structure allows for solving the new LP efficiently. In particular, the constraints of the LP can be satisfied in a compact form without an exponential dependence on the treewidth of ALP constraints. We study both practical and theoretical aspects of the proposed approach. Moreover, we demonstrate its scale-up potential on an MDP with more than 2^100 states.
Pages: 341-348
PS Link:
PDF Link: /papers/08/p341-kveton.pdf
AUTHOR = "Branislav Kveton and Milos Hauskrecht",
TITLE = "Partitioned Linear Programming Approximations for MDPs",
BOOKTITLE = "Proceedings of the Twenty-Fourth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-08)",
ADDRESS = "Corvallis, Oregon",
YEAR = "2008",
PAGES = "341--348"

hosted by DSL   •   site info   •   help