Solving Relational MDPs with Exogenous Events and Additive Rewards
| Autor: | Joshi, S., Khardon, R., Tadepalli, P., Raghavan, A., Fern, A. |
|---|---|
| Rok vydání: | 2013 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: This is an extended version of our ECML/PKDD 2013 paper including all proofs. (v2 corrects typos and updates ref [10] to cite this report as the full version) |
| Databáze: | arXiv |
| Externí odkaz: |
|