Multi-Cost-Bounded Reachability Analysis of POMDPs

Alexander Bork, Joost-Pieter Katoen, Tim Quatmann, Svenja Stein
Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence, PMLR 286:355-387, 2025.

Abstract

We consider multi-dimensional cost-bounded reachability probability objectives for partially observable Markov decision processes (POMDPs). The goal is to compute the maximal probability to reach a set of target states while simultaneously satisfying specified bounds on incurred costs. Such objectives generalise well-studied POMDP objectives by allowing multiple upper and lower bounds on different cost or reward measures, e.g. to naturally model scenarios where an agent acts under limited resources. We present a reduction of the multi-cost-bounded problem to unbounded reachability probabilities on an unfolding of the original POMDP. We employ a refined approach in case the agent is cost-aware-i.e., collected costs are fully observed-and also consider a setting where only partial information about the collected costs is known. Our approaches elegantly lift existing results from the fully observable MDP case to POMDPs. An empirical evaluation shows the potential of analysing POMDPs under multi-cost-bounded reachability objectives in practical settings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v286-bork25a, title = {Multi-Cost-Bounded Reachability Analysis of POMDPs}, author = {Bork, Alexander and Katoen, Joost-Pieter and Quatmann, Tim and Stein, Svenja}, booktitle = {Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence}, pages = {355--387}, year = {2025}, editor = {Chiappa, Silvia and Magliacane, Sara}, volume = {286}, series = {Proceedings of Machine Learning Research}, month = {21--25 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v286/main/assets/bork25a/bork25a.pdf}, url = {https://proceedings.mlr.press/v286/bork25a.html}, abstract = {We consider multi-dimensional cost-bounded reachability probability objectives for partially observable Markov decision processes (POMDPs). The goal is to compute the maximal probability to reach a set of target states while simultaneously satisfying specified bounds on incurred costs. Such objectives generalise well-studied POMDP objectives by allowing multiple upper and lower bounds on different cost or reward measures, e.g. to naturally model scenarios where an agent acts under limited resources. We present a reduction of the multi-cost-bounded problem to unbounded reachability probabilities on an unfolding of the original POMDP. We employ a refined approach in case the agent is cost-aware-i.e., collected costs are fully observed-and also consider a setting where only partial information about the collected costs is known. Our approaches elegantly lift existing results from the fully observable MDP case to POMDPs. An empirical evaluation shows the potential of analysing POMDPs under multi-cost-bounded reachability objectives in practical settings.} }
Endnote
%0 Conference Paper %T Multi-Cost-Bounded Reachability Analysis of POMDPs %A Alexander Bork %A Joost-Pieter Katoen %A Tim Quatmann %A Svenja Stein %B Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2025 %E Silvia Chiappa %E Sara Magliacane %F pmlr-v286-bork25a %I PMLR %P 355--387 %U https://proceedings.mlr.press/v286/bork25a.html %V 286 %X We consider multi-dimensional cost-bounded reachability probability objectives for partially observable Markov decision processes (POMDPs). The goal is to compute the maximal probability to reach a set of target states while simultaneously satisfying specified bounds on incurred costs. Such objectives generalise well-studied POMDP objectives by allowing multiple upper and lower bounds on different cost or reward measures, e.g. to naturally model scenarios where an agent acts under limited resources. We present a reduction of the multi-cost-bounded problem to unbounded reachability probabilities on an unfolding of the original POMDP. We employ a refined approach in case the agent is cost-aware-i.e., collected costs are fully observed-and also consider a setting where only partial information about the collected costs is known. Our approaches elegantly lift existing results from the fully observable MDP case to POMDPs. An empirical evaluation shows the potential of analysing POMDPs under multi-cost-bounded reachability objectives in practical settings.
APA
Bork, A., Katoen, J., Quatmann, T. & Stein, S.. (2025). Multi-Cost-Bounded Reachability Analysis of POMDPs. Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 286:355-387 Available from https://proceedings.mlr.press/v286/bork25a.html.

Related Material