You are here

Solving Relational MDPs with Exogenous Events and Additive Rewards

TitleSolving Relational MDPs with Exogenous Events and Additive Rewards
Publication TypeConference Paper
Year of Publication2013
AuthorsJoshi, S., R. Khardon, P. Tadepalli, A. Raghavan, and A. Fern
Conference NameEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECMLPKDD-2013)
Pagination178 - 193
Date Published09/2013
PublisherSpringer Berlin Heidelberg
Conference LocationPrague, Czech Republic
ISBN Number978-3-642-40988-2

We formalize a simple but natural subclass of service domains for relational planning problems with object-centered, independent exogenous events and additive rewards capturing, for example, problems in inventory control. Focusing on this subclass, we present a new symbolic planning algorithm which is the first algorithm that has explicit performance guarantees for relational MDPs with exogenous events. In particular, under some technical conditions, our planning algorithm provides a monotonic lower bound on the optimal value function. To support this algorithm we present novel evaluation and reduction techniques for generalized first order decision diagrams, a knowledge representation for real-valued functions over relational world states. Our planning algorithm uses a set of focus states, which serves as a training set, to simplify and approximate the symbolic solution, and can thus be seen to perform learning for planning. A preliminary experimental evaluation demonstrates the validity of our approach.