Relational Markov Decision Processes: Promise and Prospects

Relational Markov Decision Processes (RMDPs) offer an elegant formalism that combines probabilistic and relational knowledge representations with the decision-theoretic notions of action and utility. In this paper we motivate RMDPs to address a variety of problems in AI, including open world planning, transfer learning, and relational inference. We describe a symbolic dynamic programming approach via the "template method" which addresses the problem of reasoning about exogenous events. We end with a discussion of the challenges involved and some promising future research directions.