[{"intvolume":"        40","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2505.04539"}],"type":"conference","date_updated":"2026-05-04T11:38:56Z","quality_controlled":"1","oa":1,"month":"03","oa_version":"Preprint","publication_status":"published","date_created":"2026-04-12T22:01:50Z","publisher":"Association for the Advancement of Artificial Intelligence","publication_identifier":{"issn":["2159-5399"],"eissn":["2374-3468"]},"OA_place":"repository","title":"Qualitative analysis of ω-regular objectives on robust MDPs","abstract":[{"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.","lang":"eng"}],"citation":{"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>","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>","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.","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.","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.","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>.","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>."},"author":[{"full_name":"Asadi, Ali","last_name":"Asadi","first_name":"Ali","id":"02d96aae-000e-11ec-b801-cadd0a5eefbb"},{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"103b4fa0-896a-11ed-bdf8-87b697bef40d","first_name":"Ehsan","full_name":"Kafshdar Goharshadi, Ehsan","orcid":"0000-0002-8595-0587","last_name":"Kafshdar Goharshadi"},{"first_name":"Mehrdad","id":"67638922-f394-11eb-9cf6-f20423e08757","full_name":"Karrabi, Mehrdad","orcid":"0009-0007-5253-9170","last_name":"Karrabi"},{"id":"2783031a-7378-11f0-b2d0-f17f1db2ebad","first_name":"Ali","full_name":"Shafiee, Ali","last_name":"Shafiee"}],"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.","doi":"10.1609/aaai.v40i43.40931","external_id":{"arxiv":["2505.04539"]},"scopus_import":"1","issue":"43","status":"public","article_processing_charge":"No","conference":{"start_date":"2026-01-20","location":"Singapore, Singapore","name":"AAAI: Conference on Artificial Intelligence","end_date":"2026-01-27"},"publication":"Proceedings of the 40th AAAI Conference on Artificial Intelligence","page":"36137-36145","language":[{"iso":"eng"}],"volume":40,"department":[{"_id":"KrCh"},{"_id":"GradSch"}],"ec_funded":1,"date_published":"2026-03-14T00:00:00Z","_id":"21717","year":"2026","day":"14","OA_type":"green","arxiv":1,"project":[{"grant_number":"863818","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}]},{"date_published":"2026-03-14T00:00:00Z","_id":"21722","year":"2026","day":"14","OA_type":"green","arxiv":1,"project":[{"call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"status":"public","article_processing_charge":"No","conference":{"start_date":"2026-01-20","location":"Singapore, Singapore","name":"AAAI: Conference on Artificial Intelligence","end_date":"2026-01-27"},"publication":"Proceedings of the AAAI Conference on Artificial Intelligence","page":"36146-36154","language":[{"iso":"eng"}],"volume":40,"ec_funded":1,"department":[{"_id":"KrCh"}],"corr_author":"1","publication_identifier":{"issn":["2159-5399"],"eissn":["2374-3468"]},"publisher":"Association for the Advancement of Artificial Intelligence","OA_place":"repository","title":"Revealing POMDPs: Qualitative and quantitative analysis for parity objectives","citation":{"chicago":"Asadi, Ali, Krishnendu Chatterjee, David Lurie, and Raimundo J Saona Urmeneta. “Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives.” In <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, 40:36146–54. Association for the Advancement of Artificial Intelligence, 2026. <a href=\"https://doi.org/10.1609/aaai.v40i43.40932\">https://doi.org/10.1609/aaai.v40i43.40932</a>.","mla":"Asadi, Ali, et al. “Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives.” <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, vol. 40, no. 43, Association for the Advancement of Artificial Intelligence, 2026, pp. 36146–54, doi:<a href=\"https://doi.org/10.1609/aaai.v40i43.40932\">10.1609/aaai.v40i43.40932</a>.","ieee":"A. Asadi, K. Chatterjee, D. Lurie, and R. J. Saona Urmeneta, “Revealing POMDPs: Qualitative and quantitative analysis for parity objectives,” in <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, Singapore, Singapore, 2026, vol. 40, no. 43, pp. 36146–36154.","short":"A. Asadi, K. Chatterjee, D. Lurie, R.J. Saona Urmeneta, in:, Proceedings of the AAAI Conference on Artificial Intelligence, Association for the Advancement of Artificial Intelligence, 2026, pp. 36146–36154.","ama":"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>","apa":"Asadi, A., Chatterjee, K., Lurie, D., &#38; Saona Urmeneta, R. J. (2026). Revealing POMDPs: Qualitative and quantitative analysis for parity objectives. In <i>Proceedings of the AAAI Conference on Artificial Intelligence</i> (Vol. 40, pp. 36146–36154). Singapore, Singapore: Association for the Advancement of Artificial Intelligence. <a href=\"https://doi.org/10.1609/aaai.v40i43.40932\">https://doi.org/10.1609/aaai.v40i43.40932</a>","ista":"Asadi A, Chatterjee K, Lurie D, Saona Urmeneta RJ. 2026. Revealing POMDPs: Qualitative and quantitative analysis for parity objectives. Proceedings of the AAAI Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence vol. 40, 36146–36154."},"abstract":[{"text":"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.","lang":"eng"}],"acknowledgement":"This work was partially supported by the ANRT under the French CIFRE Ph.D program in collaboration between NyxAir and Paris-Dauphine University (Contract: CIFRE N° 2022/0513), by the French Agence Nationale de la Recherche (ANR) under reference ANR-21-CE40-\r\n0020 (CONVERGENCE project), by Austrian Science Fund (FWF) 10.55776/COE12, and by the ERC CoG 863818 (ForM-SMArt) grant.","author":[{"id":"02d96aae-000e-11ec-b801-cadd0a5eefbb","first_name":"Ali","last_name":"Asadi","full_name":"Asadi, Ali"},{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"id":"579a6c20-34cf-11f1-acbd-8c2f19cdb4da","first_name":"David","last_name":"Lurie","full_name":"Lurie, David"},{"first_name":"Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","full_name":"Saona Urmeneta, Raimundo J","orcid":"0000-0001-5103-038X","last_name":"Saona Urmeneta"}],"doi":"10.1609/aaai.v40i43.40932","scopus_import":"1","external_id":{"arxiv":["2511.13134"]},"issue":"43","intvolume":"        40","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2511.13134"}],"type":"conference","date_updated":"2026-05-04T11:44:14Z","quality_controlled":"1","month":"03","oa_version":"Preprint","publication_status":"published","date_created":"2026-04-12T22:01:52Z"},{"OA_type":"gold","arxiv":1,"license":"https://creativecommons.org/licenses/by/4.0/","project":[{"_id":"62781420-2b32-11ec-9570-8d9b63373d4d","call_identifier":"H2020","grant_number":"101020093","name":"Vigilant Algorithmic Monitoring of Software"}],"date_published":"2025-12-09T00:00:00Z","_id":"21281","year":"2025","day":"09","volume":360,"department":[{"_id":"KrCh"},{"_id":"GradSch"}],"ec_funded":1,"status":"public","conference":{"start_date":"2025-12-17","location":"Pilani, India","name":"FSTTCS: Conference on Foundations of Software Technology and Theoretical Computer Science","end_date":"2025-12-19"},"article_processing_charge":"Yes","publication":"45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science","page":"9:1-9:17","language":[{"iso":"eng"}],"external_id":{"arxiv":["2508.15356"]},"alternative_title":["LIPIcs"],"has_accepted_license":"1","file_date_updated":"2026-02-18T09:13:25Z","file":[{"file_name":"2025_FSTTCS_Asadi.pdf","date_created":"2026-02-18T09:13:25Z","file_size":1054007,"file_id":"21316","checksum":"a66343e3ccc4a9cc5bc699c03d5764ff","access_level":"open_access","success":1,"relation":"main_file","creator":"dernst","date_updated":"2026-02-18T09:13:25Z","content_type":"application/pdf"}],"OA_place":"publisher","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_identifier":{"isbn":["9783959774062"]},"corr_author":"1","abstract":[{"text":"A strategy profile in a multi-player game is a Nash equilibrium if no player can unilaterally deviate to achieve a strictly better payoff. A profile is an ε-Nash equilibrium if no player can gain more than ε by unilaterally deviating from their strategy. In this work, we use ε-Nash equilibria to approximate the computation of Nash equilibria. Specifically, we focus on turn-based, multiplayer stochastic games played on graphs, where players are restricted to stationary strategies - strategies that use randomness but not memory.\r\nThe problem of deciding the constrained existence of stationary Nash equilibria - where each player’s payoff must lie within a given interval - is known to be ∃ℝ-complete in such a setting (Hansen and Sølvsten, 2020). We extend this line of work to stationary ε-Nash equilibria and present an algorithm that solves the following promise problem: given a game with a Nash equilibrium satisfying the constraints, compute an ε-Nash equilibrium that ε-satisfies those same constraints - satisfies the constraints up to an ε additive error. Our algorithm runs in FNP^NP time.\r\nTo achieve this, we first show that if a constrained Nash equilibrium exists, then one exists where the non-zero probabilities are at least an inverse of a double-exponential in the input. We further prove that such a strategy can be encoded using floating-point representations, as in the work of Frederiksen and Miltersen (2013), which finally gives us our FNP^NP algorithm. \r\nWe further show that the decision version of the promise problem is NP-hard. Finally, we show a partial tightness result by proving a lower bound for such techniques: if a constrained Nash equilibrium exists, then there must be one where the probabilities in the strategies are double-exponentially small.","lang":"eng"}],"citation":{"apa":"Asadi, A., Brice, L., Chatterjee, K., &#38; Thejaswini, K. S. (2025). ε-stationary Nash equilibria in multi-player stochastic graph games. In <i>45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i> (Vol. 360, p. 9:1-9:17). Pilani, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/lipics.fsttcs.2025.9\">https://doi.org/10.4230/lipics.fsttcs.2025.9</a>","ama":"Asadi A, Brice L, Chatterjee K, Thejaswini KS. ε-stationary Nash equilibria in multi-player stochastic graph games. In: <i>45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>. Vol 360. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025:9:1-9:17. doi:<a href=\"https://doi.org/10.4230/lipics.fsttcs.2025.9\">10.4230/lipics.fsttcs.2025.9</a>","ista":"Asadi A, Brice L, Chatterjee K, Thejaswini KS. 2025. ε-stationary Nash equilibria in multi-player stochastic graph games. 45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science. FSTTCS: Conference on Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 360, 9:1-9:17.","short":"A. Asadi, L. Brice, K. Chatterjee, K.S. Thejaswini, in:, 45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, p. 9:1-9:17.","ieee":"A. Asadi, L. Brice, K. Chatterjee, and K. S. Thejaswini, “ε-stationary Nash equilibria in multi-player stochastic graph games,” in <i>45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Pilani, India, 2025, vol. 360, p. 9:1-9:17.","chicago":"Asadi, Ali, Leonard Brice, Krishnendu Chatterjee, and K. S. Thejaswini. “ε-Stationary Nash Equilibria in Multi-Player Stochastic Graph Games.” In <i>45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, 360:9:1-9:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/lipics.fsttcs.2025.9\">https://doi.org/10.4230/lipics.fsttcs.2025.9</a>.","mla":"Asadi, Ali, et al. “ε-Stationary Nash Equilibria in Multi-Player Stochastic Graph Games.” <i>45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, vol. 360, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, p. 9:1-9:17, doi:<a href=\"https://doi.org/10.4230/lipics.fsttcs.2025.9\">10.4230/lipics.fsttcs.2025.9</a>."},"title":"ε-stationary Nash equilibria in multi-player stochastic graph games","acknowledgement":"This work is a part of project VAMOS that has received funding from the European\r\nResearch Council (ERC), grant agreement No 101020093.\r\n","author":[{"id":"02d96aae-000e-11ec-b801-cadd0a5eefbb","first_name":"Ali","last_name":"Asadi","full_name":"Asadi, Ali"},{"first_name":"Leonard","last_name":"Brice","full_name":"Brice, Leonard"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"first_name":"K. S.","id":"3807fb92-fdc1-11ee-bb4a-b4d8a431c753","last_name":"Thejaswini","full_name":"Thejaswini, K. S."}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"doi":"10.4230/lipics.fsttcs.2025.9","month":"12","quality_controlled":"1","oa":1,"publication_status":"published","oa_version":"Published Version","date_created":"2026-02-17T08:27:14Z","intvolume":"       360","ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","date_updated":"2026-02-19T09:39:15Z"},{"date_updated":"2025-09-09T08:21:45Z","type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":"       286","ddc":["000"],"date_created":"2025-09-07T22:01:34Z","oa_version":"Published Version","publication_status":"published","month":"07","quality_controlled":"1","oa":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"author":[{"first_name":"Ali","id":"02d96aae-000e-11ec-b801-cadd0a5eefbb","full_name":"Asadi, Ali","last_name":"Asadi"},{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","first_name":"Raimundo J","full_name":"Saona Urmeneta, Raimundo J","orcid":"0000-0001-5103-038X","last_name":"Saona Urmeneta"},{"first_name":"Ali","id":"2783031a-7378-11f0-b2d0-f17f1db2ebad","full_name":"Shafiee, Ali","last_name":"Shafiee"}],"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.","citation":{"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.","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.","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.","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.","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.","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.","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."},"abstract":[{"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.","lang":"eng"}],"title":"Limit-sure reachability for small memory policies in POMDPs is NP-complete","OA_place":"publisher","publication_identifier":{"eissn":["2640-3498"]},"publisher":"ML Research Press","corr_author":"1","has_accepted_license":"1","file_date_updated":"2025-09-09T08:19:41Z","file":[{"content_type":"application/pdf","date_updated":"2025-09-09T08:19:41Z","creator":"dernst","relation":"main_file","success":1,"access_level":"open_access","file_id":"20315","checksum":"1a37ebe7ba73ab6985765bf0d17a0acc","file_size":307458,"date_created":"2025-09-09T08:19:41Z","file_name":"2025_UAI_AsadiAli.pdf"}],"alternative_title":["PMLR"],"external_id":{"arxiv":["2412.00941"]},"scopus_import":"1","language":[{"iso":"eng"}],"page":"238-247","publication":"The 41st Conference on Uncertainty in Artificial Intelligence","article_processing_charge":"No","conference":{"start_date":"2025-07-21","location":"Rio de Janeiro, Brazil","name":"UAI: Conference on Uncertainty in Artificial Intelligence","end_date":"2025-07-25"},"status":"public","ec_funded":1,"department":[{"_id":"KrCh"},{"_id":"GradSch"}],"volume":286,"day":"01","year":"2025","_id":"20297","date_published":"2025-07-01T00:00:00Z","project":[{"call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"arxiv":1,"OA_type":"diamond"},{"file_date_updated":"2025-09-09T06:27:59Z","has_accepted_license":"1","file":[{"file_id":"20313","checksum":"4180c81bb6ed3b4f5c7a8e48d06520c6","access_level":"open_access","file_name":"2025_UAI_Asadi.pdf","date_created":"2025-09-09T06:27:59Z","file_size":317097,"creator":"dernst","success":1,"relation":"main_file","date_updated":"2025-09-09T06:27:59Z","content_type":"application/pdf"}],"alternative_title":["PMLR"],"scopus_import":"1","external_id":{"arxiv":["2506.12254"]},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant and Austrian Science Fund (FWF) 10.55776/COE12.\r\n","author":[{"id":"02d96aae-000e-11ec-b801-cadd0a5eefbb","first_name":"Ali","last_name":"Asadi","full_name":"Asadi, Ali"},{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"full_name":"De Raaij, Jakob","last_name":"De Raaij","first_name":"Jakob"}],"abstract":[{"text":"Deterministic Markov Decision Processes (DMDPs) are a mathematical framework for decision-making where the outcomes and future possible actions are deterministically determined by the current action taken. DMDPs can be viewed as a finite directed weighted graph, where in each step, the controller chooses an outgoing edge. An objective is a measurable function on runs (or infinite trajectories) of the DMDP, and the value for an objective is the maximal cumulative reward (or weight) that the controller can guarantee. We consider the classical mean-payoff (aka limit-average) objective, which is a basic and fundamental objective.\r\n\r\nHoward's policy iteration algorithm is a popular method for solving DMDPs with mean-payoff objectives. Although Howard's algorithm performs well in practice, as experimental studies suggested, the best known upper bound is exponential and the current known lower bound is as follows: For the input size I, the algorithm requires (math formular) iterations, where (math formular) hides the poly-logarithmic factors, i.e., the current lower bound on iterations is sub-linear with respect to the input size. Our main result is an improved lower bound for this fundamental algorithm where we show that for the input size I, the algorithm requires (math formular) iterations.","lang":"eng"}],"citation":{"mla":"Asadi, Ali, et al. “Lower Bound on Howard Policy Iteration for Deterministic Markov Decision Processes.” <i>The 41st Conference on Uncertainty in Artificial Intelligence</i>, vol. 286, ML Research Press, 2025, pp. 223–32.","chicago":"Asadi, Ali, Krishnendu Chatterjee, and Jakob De Raaij. “Lower Bound on Howard Policy Iteration for Deterministic Markov Decision Processes.” In <i>The 41st Conference on Uncertainty in Artificial Intelligence</i>, 286:223–32. ML Research Press, 2025.","short":"A. Asadi, K. Chatterjee, J. De Raaij, in:, The 41st Conference on Uncertainty in Artificial Intelligence, ML Research Press, 2025, pp. 223–232.","ieee":"A. Asadi, K. Chatterjee, and J. De Raaij, “Lower bound on Howard policy iteration for deterministic Markov Decision Processes,” in <i>The 41st Conference on Uncertainty in Artificial Intelligence</i>, Rio de Janeiro, Brazil, 2025, vol. 286, pp. 223–232.","ista":"Asadi A, Chatterjee K, De Raaij J. 2025. Lower bound on Howard policy iteration for deterministic Markov Decision Processes. The 41st Conference on Uncertainty in Artificial Intelligence. UAI: Conference on Uncertainty in Artificial Intelligence, PMLR, vol. 286, 223–232.","apa":"Asadi, A., Chatterjee, K., &#38; De Raaij, J. (2025). Lower bound on Howard policy iteration for deterministic Markov Decision Processes. In <i>The 41st Conference on Uncertainty in Artificial Intelligence</i> (Vol. 286, pp. 223–232). Rio de Janeiro, Brazil: ML Research Press.","ama":"Asadi A, Chatterjee K, De Raaij J. Lower bound on Howard policy iteration for deterministic Markov Decision Processes. In: <i>The 41st Conference on Uncertainty in Artificial Intelligence</i>. Vol 286. ML Research Press; 2025:223-232."},"title":"Lower bound on Howard policy iteration for deterministic Markov Decision Processes","publication_identifier":{"eissn":["2640-3498"]},"OA_place":"publisher","publisher":"ML Research Press","corr_author":"1","date_created":"2025-09-07T22:01:34Z","oa_version":"Published Version","publication_status":"published","month":"01","oa":1,"quality_controlled":"1","date_updated":"2025-09-09T06:31:20Z","type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":"       286","ddc":["000"],"project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020"}],"arxiv":1,"OA_type":"diamond","day":"01","year":"2025","_id":"20299","date_published":"2025-01-01T00:00:00Z","department":[{"_id":"KrCh"},{"_id":"GradSch"}],"ec_funded":1,"volume":286,"language":[{"iso":"eng"}],"publication":"The 41st Conference on Uncertainty in Artificial Intelligence","page":"223-232","article_processing_charge":"No","conference":{"end_date":"2025-07-25","name":"UAI: Conference on Uncertainty in Artificial Intelligence","location":"Rio de Janeiro, Brazil","start_date":"2025-07-21"},"status":"public"},{"date_created":"2024-06-03T07:43:15Z","article_number":"6","publication_status":"published","oa_version":"Preprint","quality_controlled":"1","oa":1,"month":"07","date_updated":"2025-09-08T07:44:29Z","type":"conference","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2405.02479","open_access":"1"}],"isi":1,"scopus_import":"1","external_id":{"arxiv":["2405.02479"],"isi":["001275042100006"]},"doi":"10.1145/3661814.3662080","author":[{"first_name":"Ali","id":"02d96aae-000e-11ec-b801-cadd0a5eefbb","full_name":"Asadi, Ali","last_name":"Asadi"},{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"first_name":"Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","last_name":"Svoboda","full_name":"Svoboda, Jakub","orcid":"0000-0002-1419-3267"},{"id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","first_name":"Raimundo J","orcid":"0000-0001-5103-038X","full_name":"Saona Urmeneta, Raimundo J","last_name":"Saona Urmeneta"}],"acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant.\r\n","title":"Deterministic sub-exponential algorithm for discounted-sum games with unary weights","citation":{"short":"A. Asadi, K. Chatterjee, J. Svoboda, R.J. Saona Urmeneta, in:, 39th Annual ACM/IEEE Symposium on Logic in Computer Science, Association for Computing Machinery, 2024.","ieee":"A. Asadi, K. Chatterjee, J. Svoboda, and R. J. Saona Urmeneta, “Deterministic sub-exponential algorithm for discounted-sum games with unary weights,” in <i>39th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Tallinn, Estonia, 2024.","ista":"Asadi A, Chatterjee K, Svoboda J, Saona Urmeneta RJ. 2024. Deterministic sub-exponential algorithm for discounted-sum games with unary weights. 39th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 6.","ama":"Asadi A, Chatterjee K, Svoboda J, Saona Urmeneta RJ. Deterministic sub-exponential algorithm for discounted-sum games with unary weights. In: <i>39th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. Association for Computing Machinery; 2024. doi:<a href=\"https://doi.org/10.1145/3661814.3662080\">10.1145/3661814.3662080</a>","apa":"Asadi, A., Chatterjee, K., Svoboda, J., &#38; Saona Urmeneta, R. J. (2024). Deterministic sub-exponential algorithm for discounted-sum games with unary weights. In <i>39th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. Tallinn, Estonia: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3661814.3662080\">https://doi.org/10.1145/3661814.3662080</a>","mla":"Asadi, Ali, et al. “Deterministic Sub-Exponential Algorithm for Discounted-Sum Games with Unary Weights.” <i>39th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, 6, Association for Computing Machinery, 2024, doi:<a href=\"https://doi.org/10.1145/3661814.3662080\">10.1145/3661814.3662080</a>.","chicago":"Asadi, Ali, Krishnendu Chatterjee, Jakub Svoboda, and Raimundo J Saona Urmeneta. “Deterministic Sub-Exponential Algorithm for Discounted-Sum Games with Unary Weights.” In <i>39th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. Association for Computing Machinery, 2024. <a href=\"https://doi.org/10.1145/3661814.3662080\">https://doi.org/10.1145/3661814.3662080</a>."},"abstract":[{"text":"Turn-based discounted-sum games are two-player zero-sum games played on finite directed graphs. The vertices of the graph are partitioned between player 1 and player 2. Plays are infinite walks on the graph where the next vertex is decided by a player that owns the current vertex. Each edge is assigned an integer weight and the payoff of a play is the discounted-sum of the weights of the play. The goal of player 1 is to maximize the discounted-sum payoff against the adversarial player 2. These games lie in NP ∩ coNP and are among the rare combinatorial problems that belong to this complexity class and the existence of a polynomial-time algorithm is a major open question. Since breaking the general exponential barrier has been a challenging problem, faster parameterized algorithms have been considered. If the discount factor is expressed in unary, then discounted-sum games can be solved in polynomial time. However, if the discount factor is arbitrary (or expressed in binary), but the weights are in unary, none of the existing approaches yield a sub-exponential bound. Our main result is a new analysis technique for a classical algorithm (namely, the strategy iteration algorithm) that present a new runtime bound which is [EQUATION] for game graphs with n vertices and absolute weights of at most W. In particular, our result yields a deterministic sub-exponential bound for games with weights that are constant or represented in unary.","lang":"eng"}],"corr_author":"1","publication_identifier":{"isbn":["9798400706608"],"eissn":["1043-6871"]},"publisher":"Association for Computing Machinery","ec_funded":1,"department":[{"_id":"KrCh"}],"language":[{"iso":"eng"}],"publication":"39th Annual ACM/IEEE Symposium on Logic in Computer Science","conference":{"location":"Tallinn, Estonia","start_date":"2024-07-08","end_date":"2024-07-11","name":"LICS: Logic in Computer Science"},"article_processing_charge":"No","status":"public","project":[{"call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"arxiv":1,"day":"08","year":"2024","_id":"17098","date_published":"2024-07-08T00:00:00Z"},{"oa_version":"Published Version","publication_status":"published","article_number":"5","month":"12","quality_controlled":"1","oa":1,"date_created":"2024-06-03T07:44:27Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":"       323","ddc":["000"],"date_updated":"2025-12-02T13:40:52Z","type":"conference","isi":1,"alternative_title":["LIPIcs"],"external_id":{"arxiv":["2405.02486"],"isi":["001537516500005"]},"scopus_import":"1","file_date_updated":"2025-01-08T09:49:31Z","has_accepted_license":"1","file":[{"date_created":"2025-01-08T09:49:31Z","file_name":"2024_LIPIcs_Asadi.pdf","file_size":847960,"file_id":"18777","checksum":"5b544ab4692b93300b404435c036ddd4","access_level":"open_access","success":1,"relation":"main_file","creator":"dernst","date_updated":"2025-01-08T09:49:31Z","content_type":"application/pdf"}],"abstract":[{"lang":"eng","text":"We study two-player zero-sum concurrent stochastic games with finite state and action space played for an infinite number of steps. In every step, the two players simultaneously and independently choose an action. Given the current state and the chosen actions, the next state is obtained according to a stochastic transition function. An objective is a measurable function on plays (or infinite trajectories) of the game, and the value for an objective is the maximal expectation that the player can guarantee against the adversarial player. We consider: (a) stateful-discounted objectives, which are similar to the classical discounted-sum objectives, but states are associated with different discount factors rather than a single discount factor; and (b) parity objectives, which are a canonical representation for ω-regular objectives. For stateful-discounted objectives, given an ordering of the discount factors, the limit value is the limit of the value of the stateful-discounted objectives, as the discount factors approach zero according to the given order.\r\nThe computational problem we consider is the approximation of the value within an arbitrary\r\nadditive error. The above problem is known to be in EXPSPACE for the limit value of statefuldiscounted objectives and in PSPACE for parity objectives. The best-known algorithms for both the above problems are at least exponential time, with an exponential dependence on the number of states and actions. Our main results for the value approximation problem for the limit value of stateful-discounted objectives and parity objectives are as follows: (a) we establish TFNP[NP] complexity; and (b) we present algorithms that improve the dependency on the number of actions in the exponent from linear to logarithmic. In particular, if the number of states is constant, our algorithms run in polynomial time."}],"citation":{"mla":"Asadi, Ali, et al. “Concurrent Stochastic Games with Stateful-Discounted and Parity Objectives: Complexity and Algorithms.” <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, vol. 323, 5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5\">10.4230/LIPIcs.FSTTCS.2024.5</a>.","chicago":"Asadi, Ali, Krishnendu Chatterjee, Raimundo J Saona Urmeneta, and Jakub Svoboda. “Concurrent Stochastic Games with Stateful-Discounted and Parity Objectives: Complexity and Algorithms.” In <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Vol. 323. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5\">https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5</a>.","short":"A. Asadi, K. Chatterjee, R.J. Saona Urmeneta, J. Svoboda, in:, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","ieee":"A. Asadi, K. Chatterjee, R. J. Saona Urmeneta, and J. Svoboda, “Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms,” in <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Gujarat, India, 2024, vol. 323.","ista":"Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. 2024. Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 323, 5.","apa":"Asadi, A., Chatterjee, K., Saona Urmeneta, R. J., &#38; Svoboda, J. (2024). Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. In <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i> (Vol. 323). Gujarat, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5\">https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5</a>","ama":"Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. In: <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>. Vol 323. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5\">10.4230/LIPIcs.FSTTCS.2024.5</a>"},"title":"Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773553"]},"OA_place":"publisher","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","corr_author":"1","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"doi":"10.4230/LIPIcs.FSTTCS.2024.5","author":[{"first_name":"Ali","id":"02d96aae-000e-11ec-b801-cadd0a5eefbb","last_name":"Asadi","full_name":"Asadi, Ali"},{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"last_name":"Saona Urmeneta","full_name":"Saona Urmeneta, Raimundo J","orcid":"0000-0001-5103-038X","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","first_name":"Raimundo J"},{"first_name":"Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","last_name":"Svoboda","full_name":"Svoboda, Jakub","orcid":"0000-0002-1419-3267"}],"acknowledgement":"This research was partially supported by ERC CoG 863818 (ForM-SMArt), Austrian\r\nScience Fund (FWF) 10.55776/COE12, and French Agence Nationale de la Recherche (ANR)\r\nANR-21-CE40-0020 (CONVERGENCE project)","volume":323,"ec_funded":1,"department":[{"_id":"KrCh"}],"conference":{"end_date":"2024-12-18","name":"FSTTCS: Foundations of Software Technology and Theoretical Computer Science","location":"Gujarat, India","start_date":"2024-12-16"},"article_processing_charge":"No","status":"public","language":[{"iso":"eng"}],"publication":"44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science","arxiv":1,"OA_type":"gold","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"}],"_id":"17099","date_published":"2024-12-05T00:00:00Z","day":"05","year":"2024"}]