[{"day":"14","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"This work was supported by ERC CoG 863818 (ForMSMArt) and Austrian Science Fund (FWF) 10.55776/COE12. We also thank Hossein Zakerinia for his helpful feedback.","publication_status":"published","external_id":{"arxiv":["2505.04539"]},"publisher":"Association for the Advancement of Artificial Intelligence","status":"public","_id":"21717","oa_version":"Preprint","project":[{"call_identifier":"H2020","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"citation":{"mla":"Asadi, Ali, et al. “Qualitative Analysis of ω-Regular Objectives on Robust MDPs.” <i>Proceedings of the 40th AAAI Conference on Artificial Intelligence</i>, vol. 40, no. 43, Association for the Advancement of Artificial Intelligence, 2026, pp. 36137–45, doi:<a href=\"https://doi.org/10.1609/aaai.v40i43.40931\">10.1609/aaai.v40i43.40931</a>.","short":"A. Asadi, K. Chatterjee, E. Goharshady, M. Karrabi, A. Shafiee, in:, Proceedings of the 40th AAAI Conference on Artificial Intelligence, Association for the Advancement of Artificial Intelligence, 2026, pp. 36137–36145.","ista":"Asadi A, Chatterjee K, Goharshady E, Karrabi M, Shafiee A. 2026. Qualitative analysis of ω-regular objectives on robust MDPs. Proceedings of the 40th AAAI Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence vol. 40, 36137–36145.","chicago":"Asadi, Ali, Krishnendu Chatterjee, Ehsan Goharshady, Mehrdad Karrabi, and Ali Shafiee. “Qualitative Analysis of ω-Regular Objectives on Robust MDPs.” In <i>Proceedings of the 40th AAAI Conference on Artificial Intelligence</i>, 40:36137–45. Association for the Advancement of Artificial Intelligence, 2026. <a href=\"https://doi.org/10.1609/aaai.v40i43.40931\">https://doi.org/10.1609/aaai.v40i43.40931</a>.","ieee":"A. Asadi, K. Chatterjee, E. Goharshady, M. Karrabi, and A. Shafiee, “Qualitative analysis of ω-regular objectives on robust MDPs,” in <i>Proceedings of the 40th AAAI Conference on Artificial Intelligence</i>, Singapore, Singapore, 2026, vol. 40, no. 43, pp. 36137–36145.","ama":"Asadi A, Chatterjee K, Goharshady E, Karrabi M, Shafiee A. Qualitative analysis of ω-regular objectives on robust MDPs. In: <i>Proceedings of the 40th AAAI Conference on Artificial Intelligence</i>. Vol 40. Association for the Advancement of Artificial Intelligence; 2026:36137-36145. doi:<a href=\"https://doi.org/10.1609/aaai.v40i43.40931\">10.1609/aaai.v40i43.40931</a>","apa":"Asadi, A., Chatterjee, K., Goharshady, E., Karrabi, M., &#38; Shafiee, A. (2026). Qualitative analysis of ω-regular objectives on robust MDPs. In <i>Proceedings of the 40th AAAI Conference on Artificial Intelligence</i> (Vol. 40, pp. 36137–36145). Singapore, Singapore: Association for the Advancement of Artificial Intelligence. <a href=\"https://doi.org/10.1609/aaai.v40i43.40931\">https://doi.org/10.1609/aaai.v40i43.40931</a>"},"OA_place":"repository","title":"Qualitative analysis of ω-regular objectives on robust MDPs","conference":{"name":"AAAI: Conference on Artificial Intelligence","end_date":"2026-01-27","location":"Singapore, Singapore","start_date":"2026-01-20"},"quality_controlled":"1","ec_funded":1,"abstract":[{"lang":"eng","text":"Robust Markov Decision Processes (RMDPs) generalize classical MDPs that consider uncertainties in transition probabilities by defining a set of possible transition functions. An objective is a set of runs (or infinite trajectories) of the RMDP, and the value for an objective is the maximal probability that the agent can guarantee against the adversarial environment. We consider (a) reachability objectives, where given a target set of states, the goal is to eventually arrive at one of them; and (b) parity objectives, which are a canonical representation for ω-regular objectives. The qualitative analysis problem asks whether the objective can be ensured with probability 1. In this work, we study the qualitative problem for reachability and parity objectives on RMDPs without making any assumption over the structures of the RMDPs, e.g., unichain or aperiodic. Our contributions are twofold. We first present efficient algorithms with oracle access to uncertainty sets that solve qualitative problems of reachability and parity objectives. We then report experimental results demonstrating the effectiveness of our oracle-based approach on classical RMDP examples from the literature scaling up to thousands of states."}],"intvolume":"        40","publication":"Proceedings of the 40th AAAI Conference on Artificial Intelligence","type":"conference","arxiv":1,"OA_type":"green","scopus_import":"1","date_published":"2026-03-14T00:00:00Z","article_processing_charge":"No","date_updated":"2026-05-04T11:38:56Z","oa":1,"volume":40,"doi":"10.1609/aaai.v40i43.40931","issue":"43","month":"03","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2505.04539"}],"page":"36137-36145","language":[{"iso":"eng"}],"date_created":"2026-04-12T22:01:50Z","department":[{"_id":"KrCh"},{"_id":"GradSch"}],"author":[{"full_name":"Asadi, Ali","last_name":"Asadi","first_name":"Ali","id":"02d96aae-000e-11ec-b801-cadd0a5eefbb"},{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"id":"103b4fa0-896a-11ed-bdf8-87b697bef40d","first_name":"Ehsan","orcid":"0000-0002-8595-0587","last_name":"Kafshdar Goharshadi","full_name":"Kafshdar Goharshadi, Ehsan"},{"id":"67638922-f394-11eb-9cf6-f20423e08757","first_name":"Mehrdad","orcid":"0009-0007-5253-9170","last_name":"Karrabi","full_name":"Karrabi, Mehrdad"},{"full_name":"Shafiee, Ali","last_name":"Shafiee","first_name":"Ali","id":"2783031a-7378-11f0-b2d0-f17f1db2ebad"}],"year":"2026","publication_identifier":{"eissn":["2374-3468"],"issn":["2159-5399"]}},{"conference":{"end_date":"2025-07-25","name":"UAI: Conference on Uncertainty in Artificial Intelligence","start_date":"2025-07-21","location":"Rio de Janeiro, Brazil"},"quality_controlled":"1","abstract":[{"lang":"eng","text":"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.\r\n\r\nThe 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."}],"ec_funded":1,"intvolume":"       286","corr_author":"1","ddc":["000"],"publication":"The 41st Conference on Uncertainty in Artificial Intelligence","arxiv":1,"type":"conference","OA_type":"diamond","scopus_import":"1","date_published":"2025-07-01T00:00:00Z","article_processing_charge":"No","date_updated":"2025-09-09T08:21:45Z","oa":1,"volume":286,"month":"07","file":[{"content_type":"application/pdf","file_size":307458,"success":1,"creator":"dernst","checksum":"1a37ebe7ba73ab6985765bf0d17a0acc","date_created":"2025-09-09T08:19:41Z","relation":"main_file","file_name":"2025_UAI_AsadiAli.pdf","date_updated":"2025-09-09T08:19:41Z","access_level":"open_access","file_id":"20315"}],"page":"238-247","date_created":"2025-09-07T22:01:34Z","department":[{"_id":"KrCh"},{"_id":"GradSch"}],"language":[{"iso":"eng"}],"author":[{"first_name":"Ali","id":"02d96aae-000e-11ec-b801-cadd0a5eefbb","full_name":"Asadi, Ali","last_name":"Asadi"},{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","first_name":"Raimundo J","last_name":"Saona Urmeneta","orcid":"0000-0001-5103-038X","full_name":"Saona Urmeneta, Raimundo J"},{"id":"2783031a-7378-11f0-b2d0-f17f1db2ebad","first_name":"Ali","last_name":"Shafiee","full_name":"Shafiee, Ali"}],"year":"2025","publication_identifier":{"eissn":["2640-3498"]},"alternative_title":["PMLR"],"day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"This research was partially supported by Austrian Science Fund (FWF) 10.55776/COE12, the support of the French Agence Nationale de la Recherche (ANR) under reference ANR-21-CE40-0020 (CONVERGENCE project), and the ERC CoG 863818 (ForM-SMArt) grant.","publication_status":"published","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"external_id":{"arxiv":["2412.00941"]},"license":"https://creativecommons.org/licenses/by/4.0/","publisher":"ML Research Press","status":"public","has_accepted_license":"1","oa_version":"Published Version","_id":"20297","project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"citation":{"ista":"Asadi A, Chatterjee K, Saona Urmeneta RJ, Shafiee A. 2025. Limit-sure reachability for small memory policies in POMDPs is NP-complete. The 41st Conference on Uncertainty in Artificial Intelligence. UAI: Conference on Uncertainty in Artificial Intelligence, PMLR, vol. 286, 238–247.","ieee":"A. Asadi, K. Chatterjee, R. J. Saona Urmeneta, and A. Shafiee, “Limit-sure reachability for small memory policies in POMDPs is NP-complete,” in <i>The 41st Conference on Uncertainty in Artificial Intelligence</i>, Rio de Janeiro, Brazil, 2025, vol. 286, pp. 238–247.","chicago":"Asadi, Ali, Krishnendu Chatterjee, Raimundo J Saona Urmeneta, and Ali Shafiee. “Limit-Sure Reachability for Small Memory Policies in POMDPs Is NP-Complete.” In <i>The 41st Conference on Uncertainty in Artificial Intelligence</i>, 286:238–47. ML Research Press, 2025.","short":"A. Asadi, K. Chatterjee, R.J. Saona Urmeneta, A. Shafiee, in:, The 41st Conference on Uncertainty in Artificial Intelligence, ML Research Press, 2025, pp. 238–247.","mla":"Asadi, Ali, et al. “Limit-Sure Reachability for Small Memory Policies in POMDPs Is NP-Complete.” <i>The 41st Conference on Uncertainty in Artificial Intelligence</i>, vol. 286, ML Research Press, 2025, pp. 238–47.","apa":"Asadi, A., Chatterjee, K., Saona Urmeneta, R. J., &#38; Shafiee, A. (2025). Limit-sure reachability for small memory policies in POMDPs is NP-complete. In <i>The 41st Conference on Uncertainty in Artificial Intelligence</i> (Vol. 286, pp. 238–247). Rio de Janeiro, Brazil: ML Research Press.","ama":"Asadi A, Chatterjee K, Saona Urmeneta RJ, Shafiee A. Limit-sure reachability for small memory policies in POMDPs is NP-complete. In: <i>The 41st Conference on Uncertainty in Artificial Intelligence</i>. Vol 286. ML Research Press; 2025:238-247."},"OA_place":"publisher","file_date_updated":"2025-09-09T08:19:41Z","title":"Limit-sure reachability for small memory policies in POMDPs is NP-complete"}]