Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Approximate Linear Programming for First-order MDPs
Scott Sanner, Craig Boutilier
Abstract:
We introduce a new approximate solution technique for first-order Markov decision processes (FOMDPs). Representing the value function linearly w.r.t. a set of first-order basis functions, we compute suitable weights by casting the corresponding optimization as a first-order linear program and show how off-the-shelf theorem prover and LP software can be effectively used. This technique allows one to solve FOMDPs independent of a specific domain instantiation; furthermore, it allows one to determine bounds on approximation error that apply equally to all domain instantiations. We apply this solution technique to the task of elevator scheduling with a rich feature space and multi-criteria additive reward, and demonstrate that it outperforms a number of intuitive, heuristicallyguided policies.
Keywords:
Pages: 509-517
PS Link:
PDF Link: /papers/05/p509-sanner.pdf
BibTex:
@INPROCEEDINGS{Sanner05,
AUTHOR = "Scott Sanner and Craig Boutilier",
TITLE = "Approximate Linear Programming for First-order MDPs",
BOOKTITLE = "Proceedings of the Twenty-First Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-05)",
PUBLISHER = "AUAI Press",
ADDRESS = "Arlington, Virginia",
YEAR = "2005",
PAGES = "509--517"
}


hosted by DSL   •   site info   •   help