Approximate Linear Programming for First-order MDPs
This provides a domain-independent solution for FOMDPs with error bounds, which is incremental as it builds on existing linear programming methods.
The paper tackles the problem of solving first-order Markov decision processes (FOMDPs) by introducing an approximate linear programming technique that uses first-order basis functions and off-the-shelf software, and demonstrates its effectiveness in elevator scheduling by outperforming heuristic policies.
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.