Limit-sure Reachability for Small Memory Policies in POMDPs is NP-complete

Ali Asadi, Krishnendu Chatterjee, Raimundo Saona, Ali Shafiee
Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence, PMLR 286:238-256, 2025.

Abstract

A standard model that arises in several applications in sequential decision-making is partially observable Markov decision processes (POMDPs) where a decision-making agent interacts with an uncertain environment. A basic objective in POMDPs is the reachability objective, where given a target set of states, the goal is to eventually arrive at one of them. The limit-sure problem asks whether reachability can be ensured with probability arbitrarily close to 1. In general, the limit-sure reachability problem for POMDPs is undecidable. However, in many practical cases, the most relevant question is the existence of policies with a small amount of memory. In this work, we study the limit-sure reachability problem for POMDPs with a fixed amount of memory. We establish that the computational complexity of the problem is NP-complete.

Cite this Paper

BibTeX
@InProceedings{pmlr-v286-asadi25b, title = {Limit-sure Reachability for Small Memory Policies in POMDPs is NP-complete}, author = {Asadi, Ali and Chatterjee, Krishnendu and Saona, Raimundo and Shafiee, Ali}, booktitle = {Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence}, pages = {238--256}, 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/asadi25b/asadi25b.pdf}, url = {https://proceedings.mlr.press/v286/asadi25b.html}, abstract = {A standard model that arises in several applications in sequential decision-making is partially observable Markov decision processes (POMDPs) where a decision-making agent interacts with an uncertain environment. A basic objective in POMDPs is the reachability objective, where given a target set of states, the goal is to eventually arrive at one of them. The limit-sure problem asks whether reachability can be ensured with probability arbitrarily close to 1. In general, the limit-sure reachability problem for POMDPs is undecidable. However, in many practical cases, the most relevant question is the existence of policies with a small amount of memory. In this work, we study the limit-sure reachability problem for POMDPs with a fixed amount of memory. We establish that the computational complexity of the problem is NP-complete.} }
Endnote
%0 Conference Paper %T Limit-sure Reachability for Small Memory Policies in POMDPs is NP-complete %A Ali Asadi %A Krishnendu Chatterjee %A Raimundo Saona %A Ali Shafiee %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-asadi25b %I PMLR %P 238--256 %U https://proceedings.mlr.press/v286/asadi25b.html %V 286 %X A standard model that arises in several applications in sequential decision-making is partially observable Markov decision processes (POMDPs) where a decision-making agent interacts with an uncertain environment. A basic objective in POMDPs is the reachability objective, where given a target set of states, the goal is to eventually arrive at one of them. The limit-sure problem asks whether reachability can be ensured with probability arbitrarily close to 1. In general, the limit-sure reachability problem for POMDPs is undecidable. However, in many practical cases, the most relevant question is the existence of policies with a small amount of memory. In this work, we study the limit-sure reachability problem for POMDPs with a fixed amount of memory. We establish that the computational complexity of the problem is NP-complete.
APA
Asadi, A., Chatterjee, K., Saona, R. & Shafiee, A.. (2025). Limit-sure Reachability for Small Memory Policies in POMDPs is NP-complete. Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 286:238-256 Available from https://proceedings.mlr.press/v286/asadi25b.html.

Related Material