Abstraction Pathologies In Markov Decision Processes

Manel Tagorti 1 Bruno Scherrer 1 Olivier Buffet 1 Joerg Hoffmann 1, 2
1 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Abstract : Abstraction is a common method to compute lower bounds in classical planning, imposing an equivalence relation on the state space and deriving the lower bound from the quotient system. It is a trivial and well-known fact that refined abstractions can only improve the lower bound. Thus, when we embarked on applying the same technique in the probabilistic setting, our firm belief was to find the same behavior there. We were wrong. Indeed, there are cases where every direct refinement step (splitting one equivalence class into two) yields strictly worse bounds. We give a comprehensive account of the issues involved, for two wide-spread methods to define and use abstract MDPs.
Document type :
Conference papers
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/hal-00907315
Contributor : Olivier Buffet <>
Submitted on : Thursday, November 21, 2013 - 10:09:38 AM
Last modification on : Tuesday, December 18, 2018 - 4:40:21 PM
Long-term archiving on : Saturday, February 22, 2014 - 4:32:30 AM

File

hsdip13.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-00907315, version 1

Collections

Citation

Manel Tagorti, Bruno Scherrer, Olivier Buffet, Joerg Hoffmann. Abstraction Pathologies In Markov Decision Processes. ICAPS'13 workshop on Heuristics and Search for Domain-independent Planning (HSDIP), Jun 2013, Rome, Italy. ⟨hal-00907315⟩

Share

Metrics

Record views

278

Files downloads

178