EUVIMEDEUVIMED entdecken
Crossref

Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives

Ali Asadi, Krishnendu Chatterjee, David Lurie, Raimundo Saona

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (43) · 36146-36154

DOI: 10.1609/aaai.v40i43.40932 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Ali Asadi und 3 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Partially observable Markov decision processes (POMDPs) are a central model for uncertainty in sequential decision making. The most basic objective is the reachability objective, where a target set must be eventually visited, and the more general parity objectives can model all omega-regular specifications. For such objectives, the computational analysis problems are the following: (a) qualitative analysis that asks whether the objective can be satisfied with probability 1 (almost-sure winning) or probability arbitrarily close to 1 (limit-sure winning); and (b) quantitative analysis that asks for the approximation of the optimal probability of satisfying the objective. For general POMDPs, almost-sure analysis for reachability objectives is EXPTIME-complete, but limit-sure and quantitative analyses for reachability objectives are undecidable; almost-sure, limit-sure, and quantitative analyses for parity objectives are all undecidable. A special class of POMDPs, called revealing POMDPs, has been studied recently in several works, and for this subclass the almost-sure analysis for parity objectives was shown to be EXPTIME-complete. In this work, we show that for revealing POMDPs the limit-sure analysis for parity objectives is EXPTIME-complete, and even the quantitative analysis for parity objectives can be achieved in EXPTIME.

Zitieren

APA

Asadi, A., Chatterjee, K., Lurie, D., & Saona, R. (2026). Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives. Proceedings of the AAAI Conference on Artificial Intelligence, 40(43), 36146-36154. https://doi.org/10.1609/aaai.v40i43.40932

Vancouver

Asadi A, Chatterjee K, Lurie D, Saona R. Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(43):36146-36154. doi:10.1609/aaai.v40i43.40932

BibTeX
@article{Asadi2026,
  author = {Asadi, Ali and Chatterjee, Krishnendu and Lurie, David and Saona, Raimundo},
  title = {Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {43},
  pages = {36146--36154},
  doi = {10.1609/aaai.v40i43.40932}
}
Kostenlos starten →