Planning with Formal Reachability Guarantees in Goal-Oriented MDPs with Dead-Ends

Matisse Roche, Caroline P.C. Chanel, Yoko Watanabe
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:5731-5739, 2026.

Abstract

Goal-oriented {Markov} Decision Processes with unavoidable dead-ends pose a significant challenge to standard planning algorithms, as the goal cannot always be reached with probability $1$. In certain applications, it can be desirable to optimize efficiency only over successful trajectories while enforcing a lower bound on goal reachability, yet no existing method directly addresses this conditional formulation, whose non-linear structure makes direct optimization difficult. To overcome this, we introduce a tractable approximation. Working within an unconstrained utility-maximization framework, we derive an analytical formula that determines a value for the goal-reward parameter sufficient to guarantee that the optimal policy respects the requested reachability threshold. The proposed approach is evaluated on two common benchmark domains, Aircraft Routing and Exploding Blocksworld, and compared against state-of-the-art constrained optimization methods, specifically i-dual and Chance-Constrained. Results show that our method offers a compelling trade-off: it significantly reduces the expected cost compared to conservative lexicographic approaches (i.e. i-dual), while avoiding the failure-seeking bias inherent to methods modelling artificial zero-cost give-up action (i.e. Chance-Constrained).

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-roche26a, title = {Planning with Formal Reachability Guarantees in Goal-Oriented {MDPs} with Dead-Ends}, author = {Roche, Matisse and Chanel, Caroline P.C. and Watanabe, Yoko}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {5731--5739}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/roche26a/roche26a.pdf}, url = {https://proceedings.mlr.press/v337/roche26a.html}, abstract = {Goal-oriented {Markov} Decision Processes with unavoidable dead-ends pose a significant challenge to standard planning algorithms, as the goal cannot always be reached with probability $1$. In certain applications, it can be desirable to optimize efficiency only over successful trajectories while enforcing a lower bound on goal reachability, yet no existing method directly addresses this conditional formulation, whose non-linear structure makes direct optimization difficult. To overcome this, we introduce a tractable approximation. Working within an unconstrained utility-maximization framework, we derive an analytical formula that determines a value for the goal-reward parameter sufficient to guarantee that the optimal policy respects the requested reachability threshold. The proposed approach is evaluated on two common benchmark domains, Aircraft Routing and Exploding Blocksworld, and compared against state-of-the-art constrained optimization methods, specifically i-dual and Chance-Constrained. Results show that our method offers a compelling trade-off: it significantly reduces the expected cost compared to conservative lexicographic approaches (i.e. i-dual), while avoiding the failure-seeking bias inherent to methods modelling artificial zero-cost give-up action (i.e. Chance-Constrained).} }
Endnote
%0 Conference Paper %T Planning with Formal Reachability Guarantees in Goal-Oriented MDPs with Dead-Ends %A Matisse Roche %A Caroline P.C. Chanel %A Yoko Watanabe %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-roche26a %I PMLR %P 5731--5739 %U https://proceedings.mlr.press/v337/roche26a.html %V 337 %X Goal-oriented {Markov} Decision Processes with unavoidable dead-ends pose a significant challenge to standard planning algorithms, as the goal cannot always be reached with probability $1$. In certain applications, it can be desirable to optimize efficiency only over successful trajectories while enforcing a lower bound on goal reachability, yet no existing method directly addresses this conditional formulation, whose non-linear structure makes direct optimization difficult. To overcome this, we introduce a tractable approximation. Working within an unconstrained utility-maximization framework, we derive an analytical formula that determines a value for the goal-reward parameter sufficient to guarantee that the optimal policy respects the requested reachability threshold. The proposed approach is evaluated on two common benchmark domains, Aircraft Routing and Exploding Blocksworld, and compared against state-of-the-art constrained optimization methods, specifically i-dual and Chance-Constrained. Results show that our method offers a compelling trade-off: it significantly reduces the expected cost compared to conservative lexicographic approaches (i.e. i-dual), while avoiding the failure-seeking bias inherent to methods modelling artificial zero-cost give-up action (i.e. Chance-Constrained).
APA
Roche, M., Chanel, C.P. & Watanabe, Y.. (2026). Planning with Formal Reachability Guarantees in Goal-Oriented MDPs with Dead-Ends. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:5731-5739 Available from https://proceedings.mlr.press/v337/roche26a.html.

Related Material