A Theory of Goal-Oriented MDPs with Dead Ends

Understand

Stochastic Shortest Path (SSP) MDPs is a problem class widely studied in AI, especially in probabilistic planning.

• They describe a wide range of scenarios but make the restrictive assumption that the goal is reachable from any state, i.e., that dead-end states do not exist.
• Because of this, SSPs are unable to model various scenarios that may have catastrophic events (e.g., an airplane possibly crashing if it flies into a storm).
• Even though MDP algorithms have been used for solving problems with dead ends, a principled theory of SSP extensions that would allow dead ends, including theoretically sound algorithms for solving such MDPs, has been lacking.