Solving Relational MDPs with First-Order Machine Learning
Daniel S. Weld · 2004
We present a new formulation of Relational Markov Decision Processes (RMDPs) which is simpler than the situationcalculus approach of Boutilier, Reiter and Price. In addition, we describe our initial efforts developing a novel, machinelearning based method for computing an RMDP’s policy. Our technique instantiates the RMDP into a number of propositional MDPs, which are then solved for their value functions. First-order regression techniques are then used to learn a value function for the complete RMDP. This value function may then be used to produce a policy for huge decisiontheoretic planning problems, outputting compact solutions without actually requiring explicit state space enumeration. Finally, we extend our RMDP formalism to cover the case of a dynamic universe, i.e. in which action effects may create new objects or destroy existing ones.