A Theory of Goal-Oriented MDPs with Dead Ends

Andrey Kolobov, Mausam, Daniel S. Weld

Abstract

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. In this paper, we propose three new MDP classes that admit dead ends under increasingly weaker assumptions. We present Value Iteration-based as well as the more efficient heuristic search algorithms for optimally solving each class, and explore theoretical relationships between these classes. We also conduct a preliminary empirical study comparing the performance of our algorithms on different MDP classes, especially on scenarios with unavoidable dead ends.

Introduction

In the field of probabilistic planning, the Stochastic Shortest Path (SSP) model has long served as the standard framework for goal-oriented agents. However, the utility of the classical SSP model is limited by a fundamental requirement: the "proper policy" assumption. This assumption mandates that there must exist at least one policy that reaches the goal state from every reachable state with a probability of 1.

In real-world applications, this assumption is frequently violated. Autonomous systems often operate in environments where catastrophic failures—or "dead ends"—are possible. A Mars rover might become permanently stuck in a crevice, or an aircraft might encounter weather conditions that lead to a crash. In these scenarios, the goal becomes unreachable. Standard SSP algorithms, such as Value Iteration (VI), fail to converge when dead ends are present. While practitioners have historically used ad-hoc penalties to bypass this, a rigorous theoretical foundation for optimizing behavior in the presence of unavoidable failure has been missing until now.

Proposed MDP Classes

To address these limitations, this research introduces three nested classes of MDPs that provide a principled approach to dead ends:

  1. SSPADE (Avoidable Dead Ends): This class acknowledges the existence of dead ends within the state space but assumes that the agent can still reach the goal with certainty. Specifically, there must be at least one policy that avoids all dead ends starting from the initial state $s_0$.
  2. fSSPUDE (Finite-penalty Unavoidable Dead Ends): In this model, dead ends may be unavoidable. The agent is assigned a finite penalty $D$ for failing to reach the goal. The objective is to minimize the total expected cost, which includes both the cost of actions and the potential penalty of hitting a dead end.
  3. iSSPUDE (Infinite-penalty Unavoidable Dead Ends): This class treats the cost of failure as infinite, making it suitable for safety-critical applications. The optimization follows a lexicographic (multi-objective) priority: first, the agent must maximize the probability of reaching the goal (MAXPROB); second, among all policies that achieve this maximum probability, the agent must choose the one that minimizes the expected cost.

Algorithmic Framework

The authors extend the FIND-AND-REVISE heuristic search framework to these new classes. A notable contribution is the Staged Heuristic Search (SHS) algorithm designed for iSSPUDE. SHS operates in two distinct stages: it first solves the MAXPROB problem to identify the maximum possible survival probability, and then solves an SSP on the resulting "safe" sub-graph to minimize the expected cost of reaching the goal.

Key Theoretical and Empirical Insights

The Semantic Paradox

A significant challenge in modeling fSSPUDE is the "Semantic Paradox." If a simple penalty $D$ is assigned to dead ends, an agent might find that the cost of reaching the goal from a specific state exceeds $D$. In such cases, the agent would rationally "prefer" to enter a dead end rather than attempt to reach the goal. To resolve this, the authors implement a cost-capping mechanism, ensuring that the value of any state never exceeds the penalty $D$.

Efficiency and the MAXPROB Bottleneck

Empirical evaluations using the Exploding Blocks World and Drive Domain benchmarks revealed a surprising efficiency gap. Solving the finite-penalty version (fSSPUDE) is often an order of magnitude faster than solving the infinite-penalty version (iSSPUDE), even when the penalty $D$ is set high enough that both models produce the same optimal policy.

This discrepancy is due to the MAXPROB bottleneck. To prove that a survival probability is optimal in iSSPUDE, the algorithm must often explore the entire reachable state space. In contrast, cost-based search in fSSPUDE can prune expensive paths much earlier in the process. Furthermore, the use of the "SixthSense" dead-end detection heuristic proved essential; without it, fSSPUDE algorithms struggle to "learn" that a dead end is undesirable, leading to significantly slower convergence.

Conclusion

This work provides the first comprehensive theoretical framework for goal-oriented MDPs with dead ends. By defining SSPADE, fSSPUDE, and iSSPUDE, the authors bridge the gap between theoretical SSP models and the practical realities of risky environments. While the choice of the penalty parameter $D$ remains a challenge for future research, the introduction of efficient heuristic search algorithms like SHS marks a significant step forward in robust probabilistic planning.

Summary updated

Abstract

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. In this paper, we propose three new MDP classes that admit dead ends under increasingly weaker assumptions. We present Value Iteration-based as well as the more efficient heuristic search algorithms for optimally solving each class, and explore theoretical relationships between these classes. We also conduct a preliminary empirical study comparing the performance of our algorithms on different MDP classes, especially on scenarios with unavoidable dead ends.
BibTeX
@inproceedings{kolobov2012theory,
  author = {Andrey Kolobov and Mausam and Daniel S. Weld},
  title = {{A Theory of Goal-Oriented MDPs with Dead Ends}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2012},
  url = {https://openreview.net/forum?id=JbS5QrwXEiN},
}
Figure