Revealing POMDPs: Qualitative and quantitative analysis for parity objectives Asadi, Ali Chatterjee, Krishnendu ; https://orcid.org/0000-0002-4561-241X Lurie, David Saona Urmeneta, Raimundo J ; https://orcid.org/0000-0001-5103-038X 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. Association for the Advancement of Artificial Intelligence 2026 info:eu-repo/semantics/conferenceObject doc-type:conferenceObject text http://purl.org/coar/resource_type/c_5794 https://research-explorer.ista.ac.at/record/21722 Asadi A, Chatterjee K, Lurie D, Saona Urmeneta RJ. Revealing POMDPs: Qualitative and quantitative analysis for parity objectives. In: <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>. Vol 40. Association for the Advancement of Artificial Intelligence; 2026:36146-36154. doi:<a href="https://doi.org/10.1609/aaai.v40i43.40932">10.1609/aaai.v40i43.40932</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1609/aaai.v40i43.40932 info:eu-repo/semantics/altIdentifier/issn/2159-5399 info:eu-repo/semantics/altIdentifier/e-issn/2374-3468 info:eu-repo/semantics/altIdentifier/arxiv/2511.13134 info:eu-repo/semantics/closedAccess