[{"publication_status":"published","intvolume":"        40","date_published":"2026-03-14T00:00:00Z","day":"14","type":"conference","page":"36146-36154","department":[{"_id":"KrCh"}],"publication":"Proceedings of the AAAI Conference on Artificial Intelligence","corr_author":"1","date_updated":"2026-05-04T11:44:14Z","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","last_name":"Asadi","full_name":"Asadi, Ali","first_name":"Ali"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"id":"579a6c20-34cf-11f1-acbd-8c2f19cdb4da","last_name":"Lurie","first_name":"David","full_name":"Lurie, David"},{"last_name":"Saona Urmeneta","orcid":"0000-0001-5103-038X","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","first_name":"Raimundo J","full_name":"Saona Urmeneta, Raimundo J"}],"publication_identifier":{"eissn":["2374-3468"],"issn":["2159-5399"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","arxiv":1,"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2511.13134"}],"date_created":"2026-04-12T22:01:52Z","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020","grant_number":"863818"}],"status":"public","issue":"43","citation":{"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.","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>","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.","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.","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>."},"month":"03","language":[{"iso":"eng"}],"volume":40,"OA_place":"repository","doi":"10.1609/aaai.v40i43.40932","_id":"21722","quality_controlled":"1","article_processing_charge":"No","external_id":{"arxiv":["2511.13134"]},"OA_type":"green","conference":{"end_date":"2026-01-27","name":"AAAI: Conference on Artificial Intelligence","start_date":"2026-01-20","location":"Singapore, Singapore"},"scopus_import":"1","ec_funded":1,"year":"2026","publisher":"Association for the Advancement of Artificial Intelligence","title":"Revealing POMDPs: Qualitative and quantitative analysis for parity objectives","abstract":[{"lang":"eng","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."}]},{"article_processing_charge":"No","_id":"21320","quality_controlled":"1","ddc":["000"],"conference":{"name":"ICALP: Automata, Languages and Programming","start_date":"2025-07-08","end_date":"2025-07-11","location":"Aarhus, Denmark"},"external_id":{"arxiv":["2407.11752"]},"OA_type":"gold","oa":1,"month":"06","citation":{"ieee":"G. Giambartolomei, F. Mallmann-Trenn, and R. J. Saona Urmeneta, “IID prophet inequality with random horizon: Going beyond increasing hazard rates,” in <i>52nd International Colloquium on Automata, Languages, and Programming</i>, Aarhus, Denmark, 2025, vol. 334.","mla":"Giambartolomei, Giordano, et al. “IID Prophet Inequality with Random Horizon: Going beyond Increasing Hazard Rates.” <i>52nd International Colloquium on Automata, Languages, and Programming</i>, vol. 334, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2025.87\">10.4230/LIPIcs.ICALP.2025.87</a>.","ama":"Giambartolomei G, Mallmann-Trenn F, Saona Urmeneta RJ. IID prophet inequality with random horizon: Going beyond increasing hazard rates. In: <i>52nd International Colloquium on Automata, Languages, and Programming</i>. Vol 334. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2025.87\">10.4230/LIPIcs.ICALP.2025.87</a>","apa":"Giambartolomei, G., Mallmann-Trenn, F., &#38; Saona Urmeneta, R. J. (2025). IID prophet inequality with random horizon: Going beyond increasing hazard rates. In <i>52nd International Colloquium on Automata, Languages, and Programming</i> (Vol. 334). Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2025.87\">https://doi.org/10.4230/LIPIcs.ICALP.2025.87</a>","short":"G. Giambartolomei, F. Mallmann-Trenn, R.J. Saona Urmeneta, in:, 52nd International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","ista":"Giambartolomei G, Mallmann-Trenn F, Saona Urmeneta RJ. 2025. IID prophet inequality with random horizon: Going beyond increasing hazard rates. 52nd International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 334.","chicago":"Giambartolomei, Giordano, Frederik Mallmann-Trenn, and Raimundo J Saona Urmeneta. “IID Prophet Inequality with Random Horizon: Going beyond Increasing Hazard Rates.” In <i>52nd International Colloquium on Automata, Languages, and Programming</i>, Vol. 334. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2025.87\">https://doi.org/10.4230/LIPIcs.ICALP.2025.87</a>."},"status":"public","date_created":"2026-02-18T10:44:14Z","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"OA_place":"publisher","doi":"10.4230/LIPIcs.ICALP.2025.87","volume":334,"language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"title":"IID prophet inequality with random horizon: Going beyond increasing hazard rates","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","abstract":[{"text":"Prophet inequalities are a central object of study in optimal stopping theory. In the iid model, a gambler sees values in an online fashion, sampled independently from a given distribution. Upon observing each value, the gambler either accepts it as a reward, or irrevocably rejects it and proceeds to observe the next value. The goal of the gambler, who cannot see the future, is to maximise the expected value of the reward while competing against the expectation of a prophet (the offline maximum). In other words, one seeks to maximise the gambler-to-prophet ratio of the expectations. \r\nThis model has been studied with infinite, finite and unknown number of values. When the gambler faces a random number of values, the model is said to have a random horizon. We consider the model in which the gambler is given a priori knowledge of the horizon’s distribution. Alijani et al. (2020) designed a single-threshold algorithm achieving a ratio of 1/2 when the random horizon has an increasing hazard rate and is independent of the values. We prove that with a single threshold, a ratio of 1/2 is actually achievable for several larger classes of horizon distributions, with the largest being known as the 𝒢 class in reliability theory. Moreover, we show that this does not extend to its dual, the  ̅𝒢 class (which includes the decreasing hazard rate class), while it can be extended to low-variance horizons. Finally, we construct the first example of a family of horizons, for which multiple thresholds are necessary to achieve a nonzero ratio. We establish that the Secretary Problem optimal stopping rule provides one such algorithm, paving the way towards the study of the model beyond single-threshold algorithms.","lang":"eng"}],"has_accepted_license":"1","ec_funded":1,"year":"2025","date_published":"2025-06-30T00:00:00Z","department":[{"_id":"KrCh"}],"type":"conference","day":"30","file_date_updated":"2026-02-19T07:41:55Z","file":[{"access_level":"open_access","file_size":876167,"file_name":"2025_ICALP_Giambartolomei.pdf","checksum":"960110956c26a5cefadde8e47888bfbe","creator":"dernst","file_id":"21331","content_type":"application/pdf","date_created":"2026-02-19T07:41:55Z","success":1,"relation":"main_file","date_updated":"2026-02-19T07:41:55Z"}],"alternative_title":["LIPIcs"],"intvolume":"       334","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"isbn":["9783959773720"]},"author":[{"last_name":"Giambartolomei","first_name":"Giordano","full_name":"Giambartolomei, Giordano"},{"last_name":"Mallmann-Trenn","full_name":"Mallmann-Trenn, Frederik","first_name":"Frederik"},{"first_name":"Raimundo J","full_name":"Saona Urmeneta, Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","last_name":"Saona Urmeneta","orcid":"0000-0001-5103-038X"}],"arxiv":1,"oa_version":"Published Version","publication":"52nd International Colloquium on Automata, Languages, and Programming","acknowledgement":"We would like to thank José Correa for his precious advice, Bruno Ziliotto and Vasilis Livanos for early conversations. Giambartolomei, Giordano: EPSRC grants EP/W005573/1 and EP/X021696/1. Mallmann-Trenn, Frederik: EPSRC grant EP/W005573/1. Saona, Raimundo: ERC grant CoG 863818 (ForM-SMArt), ANID Chile grant ACT210005, French Agence Nationale de la Recherche (ANR) grant ANR-21-CE40-0020 (CONVERGENCE), and Austrian Science Fund (FWF) grant 10.55776/COE12.","date_updated":"2026-02-19T07:43:29Z"},{"publication_identifier":{"issn":["2153-0785"],"eissn":["2153-0793"]},"author":[{"last_name":"Attia","first_name":"Luc","full_name":"Attia, Luc"},{"full_name":"Lichev, Lyuben","first_name":"Lyuben","last_name":"Lichev","id":"9aa8388e-d003-11ee-8458-c4c1d7447977"},{"last_name":"Mitsche","first_name":"Dieter","full_name":"Mitsche, Dieter"},{"id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","orcid":"0000-0001-5103-038X","last_name":"Saona Urmeneta","first_name":"Raimundo J","full_name":"Saona Urmeneta, Raimundo J"},{"last_name":"Ziliotto","full_name":"Ziliotto, Bruno","first_name":"Bruno"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_type":"original","oa_version":"Published Version","related_material":{"record":[{"relation":"dissertation_contains","id":"20234","status":"public"}]},"publication":"Dynamic Games and Applications","corr_author":"1","acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria). This work was supported by the French Agence Nationale de la Recherche (ANR) under references ANR-21-CE40-0020 (CONVERGENCE project) and ANR-20-CE40-0002 (GrHyDy), by Fondecyt grant 1220174, by ANID Chile grant ACT210005, and by the ERC CoG 863818 (ForM-SMArt) grant. This collaboration was mainly conducted during a 1-year visit of Bruno Ziliotto to the Center for Mathematical Modeling (CMM) at University of Chile in 2023, under the IRL program of CNRS. This work was supported by Fondation CFM pour la Recherche. This paper has also been funded by the Agence Nationale de la Recherche under grant ANR-17-EURE-0010 (Investissements d’Avenir program).","date_updated":"2026-04-07T12:31:21Z","date_published":"2025-11-01T00:00:00Z","file_date_updated":"2025-12-30T08:13:04Z","day":"01","PlanS_conform":"1","department":[{"_id":"MaKw"},{"_id":"KrCh"}],"isi":1,"type":"journal_article","page":"1517-1535","publication_status":"published","file":[{"relation":"main_file","date_updated":"2025-12-30T08:13:04Z","success":1,"date_created":"2025-12-30T08:13:04Z","file_id":"20891","content_type":"application/pdf","creator":"dernst","checksum":"b3a1b7eef40c9ac2acf3fef563081694","file_size":570994,"access_level":"open_access","file_name":"2025_DynGamesAppl_Attia.pdf"}],"intvolume":"        15","publisher":"Springer Nature","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"title":"Random zero-sum dynamic games on infinite directed graphs","abstract":[{"text":"We consider random two-player zero-sum dynamic games with perfect information on a class of infinite directed graphs. Starting from a fixed vertex, the players take turns to move a token along the edges of the graph. Every vertex is assigned a payoff known in advance by both players. Every time the token visits a vertex, Player 2 pays Player 1 the corresponding payoff. We consider a distribution over such games by assigning i.i.d. payoffs to the vertices. On the one hand, for acyclic directed graphs of bounded degree and sub-exponential expansion, we show that, when the duration of the game tends to infinity, the value converges almost surely to a constant at an exponential rate dominated in terms of the expansion. On the other hand, for the infinite d-ary tree (that does not fall into the previous class of graphs), we show convergence at a double-exponential rate.","lang":"eng"}],"ec_funded":1,"year":"2025","has_accepted_license":"1","scopus_import":"1","ddc":["000"],"article_processing_charge":"Yes (via OA deal)","_id":"19508","quality_controlled":"1","oa":1,"OA_type":"hybrid","external_id":{"isi":["001449708900001"]},"status":"public","date_created":"2025-04-06T22:01:32Z","project":[{"grant_number":"863818","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"month":"11","citation":{"short":"L. Attia, L. Lichev, D. Mitsche, R.J. Saona Urmeneta, B. Ziliotto, Dynamic Games and Applications 15 (2025) 1517–1535.","chicago":"Attia, Luc, Lyuben Lichev, Dieter Mitsche, Raimundo J Saona Urmeneta, and Bruno Ziliotto. “Random Zero-Sum Dynamic Games on Infinite Directed Graphs.” <i>Dynamic Games and Applications</i>. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/s13235-025-00636-4\">https://doi.org/10.1007/s13235-025-00636-4</a>.","ista":"Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. 2025. Random zero-sum dynamic games on infinite directed graphs. Dynamic Games and Applications. 15, 1517–1535.","ama":"Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. Random zero-sum dynamic games on infinite directed graphs. <i>Dynamic Games and Applications</i>. 2025;15:1517-1535. doi:<a href=\"https://doi.org/10.1007/s13235-025-00636-4\">10.1007/s13235-025-00636-4</a>","ieee":"L. Attia, L. Lichev, D. Mitsche, R. J. Saona Urmeneta, and B. Ziliotto, “Random zero-sum dynamic games on infinite directed graphs,” <i>Dynamic Games and Applications</i>, vol. 15. Springer Nature, pp. 1517–1535, 2025.","mla":"Attia, Luc, et al. “Random Zero-Sum Dynamic Games on Infinite Directed Graphs.” <i>Dynamic Games and Applications</i>, vol. 15, Springer Nature, 2025, pp. 1517–35, doi:<a href=\"https://doi.org/10.1007/s13235-025-00636-4\">10.1007/s13235-025-00636-4</a>.","apa":"Attia, L., Lichev, L., Mitsche, D., Saona Urmeneta, R. J., &#38; Ziliotto, B. (2025). Random zero-sum dynamic games on infinite directed graphs. <i>Dynamic Games and Applications</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s13235-025-00636-4\">https://doi.org/10.1007/s13235-025-00636-4</a>"},"volume":15,"language":[{"iso":"eng"}],"doi":"10.1007/s13235-025-00636-4","OA_place":"publisher"},{"ec_funded":1,"year":"2025","scopus_import":"1","title":"Linear equations with min and max operators: Computational complexity","publisher":"Association for the Advancement of Artificial Intelligence","abstract":[{"text":"We consider a class of optimization problems defined by a system of linear equations with min and max operators. This class of optimization problems has been studied under restrictive conditions, such as, (C1) the halting or stability condition; (C2) the non-negative coefficients condition; (C3) the sum upto 1 condition; and (C4) the only min or only max operator condition. Several seminal results in the literature focus on special cases. For example, turn-based stochastic games correspond to conditions C2 and C3; and Markov decision process to conditions C2, C3, and C4. However, the systematic computational complexity study of all the cases has not been explored, which we address in this work. Some highlights of our results are: with conditions C2 and C4, and with conditions C3 and C4, the problem is NP-complete, whereas with condition C1 only, the problem is in UP intersects coUP. Finally, we establish the computational complexity of the decision problem of checking the respective conditions.","lang":"eng"}],"month":"04","issue":"11","citation":{"ama":"Chatterjee K, Luo R, Saona Urmeneta RJ, Svoboda J. Linear equations with min and max operators: Computational complexity. In: <i>Proceedings of the 39th AAAI Conference on Artificial Intelligence</i>. Vol 39. Association for the Advancement of Artificial Intelligence; 2025:11150-11157. doi:<a href=\"https://doi.org/10.1609/aaai.v39i11.33212\">10.1609/aaai.v39i11.33212</a>","mla":"Chatterjee, Krishnendu, et al. “Linear Equations with Min and Max Operators: Computational Complexity.” <i>Proceedings of the 39th AAAI Conference on Artificial Intelligence</i>, vol. 39, no. 11, Association for the Advancement of Artificial Intelligence, 2025, pp. 11150–57, doi:<a href=\"https://doi.org/10.1609/aaai.v39i11.33212\">10.1609/aaai.v39i11.33212</a>.","ieee":"K. Chatterjee, R. Luo, R. J. Saona Urmeneta, and J. Svoboda, “Linear equations with min and max operators: Computational complexity,” in <i>Proceedings of the 39th AAAI Conference on Artificial Intelligence</i>, Philadelphia, PA, United States, 2025, vol. 39, no. 11, pp. 11150–11157.","apa":"Chatterjee, K., Luo, R., Saona Urmeneta, R. J., &#38; Svoboda, J. (2025). Linear equations with min and max operators: Computational complexity. In <i>Proceedings of the 39th AAAI Conference on Artificial Intelligence</i> (Vol. 39, pp. 11150–11157). Philadelphia, PA, United States: Association for the Advancement of Artificial Intelligence. <a href=\"https://doi.org/10.1609/aaai.v39i11.33212\">https://doi.org/10.1609/aaai.v39i11.33212</a>","short":"K. Chatterjee, R. Luo, R.J. Saona Urmeneta, J. Svoboda, in:, Proceedings of the 39th AAAI Conference on Artificial Intelligence, Association for the Advancement of Artificial Intelligence, 2025, pp. 11150–11157.","ista":"Chatterjee K, Luo R, Saona Urmeneta RJ, Svoboda J. 2025. Linear equations with min and max operators: Computational complexity. Proceedings of the 39th AAAI Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence vol. 39, 11150–11157.","chicago":"Chatterjee, Krishnendu, Ruichen Luo, Raimundo J Saona Urmeneta, and Jakub Svoboda. “Linear Equations with Min and Max Operators: Computational Complexity.” In <i>Proceedings of the 39th AAAI Conference on Artificial Intelligence</i>, 39:11150–57. Association for the Advancement of Artificial Intelligence, 2025. <a href=\"https://doi.org/10.1609/aaai.v39i11.33212\">https://doi.org/10.1609/aaai.v39i11.33212</a>."},"status":"public","date_created":"2025-05-11T22:02:40Z","project":[{"call_identifier":"H2020","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"OA_place":"repository","doi":"10.1609/aaai.v39i11.33212","volume":39,"language":[{"iso":"eng"}],"_id":"19669","article_processing_charge":"No","quality_controlled":"1","conference":{"name":"AAAI: Conference on Artificial Intelligence","start_date":"2025-02-25","end_date":"2025-03-04","location":"Philadelphia, PA, United States"},"external_id":{"arxiv":["2412.12228"]},"OA_type":"green","oa":1,"publication":"Proceedings of the 39th AAAI Conference on Artificial Intelligence","acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant and the Austrian Science Fund (FWF) 10.55776/COE12 grant.","date_updated":"2025-05-12T09:42:09Z","corr_author":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["2159-5399"],"eissn":["2374-3468"]},"author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"id":"b391db08-1ffe-11ee-8b67-d18ddcfb5a14","last_name":"Luo","full_name":"Luo, Ruichen","first_name":"Ruichen"},{"full_name":"Saona Urmeneta, Raimundo J","first_name":"Raimundo J","last_name":"Saona Urmeneta","orcid":"0000-0001-5103-038X","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425"},{"id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","last_name":"Svoboda","orcid":"0000-0002-1419-3267","first_name":"Jakub","full_name":"Svoboda, Jakub"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2412.12228"}],"oa_version":"Preprint","arxiv":1,"intvolume":"        39","publication_status":"published","date_published":"2025-04-11T00:00:00Z","department":[{"_id":"KrCh"}],"page":"11150-11157","type":"conference","day":"11"},{"doi":"10.1007/978-3-031-90653-4_11","OA_place":"publisher","volume":15697,"language":[{"iso":"eng"}],"month":"05","citation":{"ista":"Chatterjee K, Jafariraviz M, Saona Urmeneta RJ, Svoboda J. 2025. Value iteration with guessing for Markov chains and Markov decision processes. 31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems. TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 15697, 217–236.","chicago":"Chatterjee, Krishnendu, Mahdi Jafariraviz, Raimundo J Saona Urmeneta, and Jakub Svoboda. “Value Iteration with Guessing for Markov Chains and Markov Decision Processes.” In <i>31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, 15697:217–36. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-031-90653-4_11\">https://doi.org/10.1007/978-3-031-90653-4_11</a>.","short":"K. Chatterjee, M. Jafariraviz, R.J. Saona Urmeneta, J. Svoboda, in:, 31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Springer Nature, 2025, pp. 217–236.","apa":"Chatterjee, K., Jafariraviz, M., Saona Urmeneta, R. J., &#38; Svoboda, J. (2025). Value iteration with guessing for Markov chains and Markov decision processes. In <i>31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i> (Vol. 15697, pp. 217–236). Hamilton, ON, Canada: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-90653-4_11\">https://doi.org/10.1007/978-3-031-90653-4_11</a>","ieee":"K. Chatterjee, M. Jafariraviz, R. J. Saona Urmeneta, and J. Svoboda, “Value iteration with guessing for Markov chains and Markov decision processes,” in <i>31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, Hamilton, ON, Canada, 2025, vol. 15697, pp. 217–236.","mla":"Chatterjee, Krishnendu, et al. “Value Iteration with Guessing for Markov Chains and Markov Decision Processes.” <i>31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, vol. 15697, Springer Nature, 2025, pp. 217–36, doi:<a href=\"https://doi.org/10.1007/978-3-031-90653-4_11\">10.1007/978-3-031-90653-4_11</a>.","ama":"Chatterjee K, Jafariraviz M, Saona Urmeneta RJ, Svoboda J. Value iteration with guessing for Markov chains and Markov decision processes. In: <i>31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>. Vol 15697. Springer Nature; 2025:217-236. doi:<a href=\"https://doi.org/10.1007/978-3-031-90653-4_11\">10.1007/978-3-031-90653-4_11</a>"},"status":"public","date_created":"2025-05-25T22:17:06Z","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020","grant_number":"863818"}],"conference":{"location":"Hamilton, ON, Canada","end_date":"2025-05-08","name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","start_date":"2025-05-03"},"OA_type":"hybrid","external_id":{"arxiv":["2505.06769"]},"oa":1,"_id":"19740","article_processing_charge":"No","quality_controlled":"1","ddc":["000"],"ec_funded":1,"year":"2025","has_accepted_license":"1","scopus_import":"1","abstract":[{"lang":"eng","text":"Two standard models for probabilistic systems are Markov chains (MCs) and Markov decision processes (MDPs). Classic objectives for such probabilistic models for control and planning problems are reachability and stochastic shortest path. The widely studied algorithmic approach for these problems is the Value Iteration (VI) algorithm which iteratively applies local updates called Bellman updates. There are many practical approaches for VI in the literature but they all require exponentially many Bellman updates for MCs in the worst case. A preprocessing step is an algorithm that is discrete, graph-theoretical, and requires linear space. An important open question is whether, after a polynomial-time preprocessing, VI can be achieved with sub-exponentially many Bellman updates. In this work, we present a new approach for VI based on guessing values. Our theoretical contributions are twofold. First, for MCs, we present an almost-linear-time preprocessing algorithm after which, along with guessing values, VI requires only subexponentially many Bellman updates. Second, we present an improved analysis of the speed of convergence of VI for MDPs. Finally, we present a practical algorithm for MDPs based on our new approach. Experimental results show that our approach provides a considerable improvement over existing VI-based approaches on several benchmark examples from the literature."}],"title":"Value iteration with guessing for Markov chains and Markov decision processes","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"publisher":"Springer Nature","file":[{"file_name":"2025_TACAS_Chatterjee.pdf","access_level":"open_access","file_size":557481,"creator":"dernst","checksum":"45da6efbcbed20aada16c48c8e55e2d6","content_type":"application/pdf","file_id":"19767","date_created":"2025-06-02T07:31:12Z","success":1,"date_updated":"2025-06-02T07:31:12Z","relation":"main_file"}],"alternative_title":["LNCS"],"intvolume":"     15697","publication_status":"published","department":[{"_id":"KrCh"}],"type":"conference","page":"217-236","day":"01","file_date_updated":"2025-06-02T07:31:12Z","date_published":"2025-05-01T00:00:00Z","acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant and Austrian Science Fund (FWF) 10.55776/COE12 grant.","date_updated":"2025-06-02T07:35:06Z","corr_author":"1","publication":"31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems","arxiv":1,"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"isbn":["9783031906527"],"eissn":["1611-3349"],"issn":["0302-9743"]},"author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"last_name":"Jafariraviz","full_name":"Jafariraviz, Mahdi","first_name":"Mahdi"},{"full_name":"Saona Urmeneta, Raimundo J","first_name":"Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","orcid":"0000-0001-5103-038X","last_name":"Saona Urmeneta"},{"full_name":"Svoboda, Jakub","first_name":"Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","orcid":"0000-0002-1419-3267","last_name":"Svoboda"}]},{"department":[{"_id":"KrCh"},{"_id":"GradSch"}],"page":"238-247","type":"conference","file_date_updated":"2025-09-09T08:19:41Z","day":"01","date_published":"2025-07-01T00:00:00Z","file":[{"relation":"main_file","date_updated":"2025-09-09T08:19:41Z","date_created":"2025-09-09T08:19:41Z","success":1,"creator":"dernst","checksum":"1a37ebe7ba73ab6985765bf0d17a0acc","content_type":"application/pdf","file_id":"20315","file_size":307458,"access_level":"open_access","file_name":"2025_UAI_AsadiAli.pdf"}],"intvolume":"       286","alternative_title":["PMLR"],"publication_status":"published","oa_version":"Published Version","arxiv":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Asadi, Ali","first_name":"Ali","id":"02d96aae-000e-11ec-b801-cadd0a5eefbb","last_name":"Asadi"},{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"first_name":"Raimundo J","full_name":"Saona Urmeneta, Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","orcid":"0000-0001-5103-038X","last_name":"Saona Urmeneta"},{"last_name":"Shafiee","id":"2783031a-7378-11f0-b2d0-f17f1db2ebad","first_name":"Ali","full_name":"Shafiee, Ali"}],"publication_identifier":{"eissn":["2640-3498"]},"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.","date_updated":"2025-09-09T08:21:45Z","corr_author":"1","publication":"The 41st Conference on Uncertainty in Artificial Intelligence","conference":{"location":"Rio de Janeiro, Brazil","end_date":"2025-07-25","start_date":"2025-07-21","name":"UAI: Conference on Uncertainty in Artificial Intelligence"},"OA_type":"diamond","external_id":{"arxiv":["2412.00941"]},"oa":1,"_id":"20297","article_processing_charge":"No","quality_controlled":"1","ddc":["000"],"OA_place":"publisher","volume":286,"language":[{"iso":"eng"}],"month":"07","citation":{"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.","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.","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.","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.","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."},"status":"public","project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"date_created":"2025-09-07T22:01:34Z","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."}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"title":"Limit-sure reachability for small memory policies in POMDPs is NP-complete","publisher":"ML Research Press","ec_funded":1,"year":"2025","has_accepted_license":"1","scopus_import":"1"},{"project":[{"grant_number":"S11407","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory"},{"grant_number":"863818","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"date_created":"2025-08-27T14:00:13Z","status":"public","citation":{"ama":"Saona Urmeneta RJ. Robustness of solutions in game theory : Values and strategies in partially observable, perturbed, stochastic, and infinite games. 2025. doi:<a href=\"https://doi.org/10.15479/AT-ISTA-20234\">10.15479/AT-ISTA-20234</a>","ieee":"R. J. Saona Urmeneta, “Robustness of solutions in game theory : Values and strategies in partially observable, perturbed, stochastic, and infinite games,” Institute of Science and Technology Austria, 2025.","mla":"Saona Urmeneta, Raimundo J. <i>Robustness of Solutions in Game Theory : Values and Strategies in Partially Observable, Perturbed, Stochastic, and Infinite Games</i>. Institute of Science and Technology Austria, 2025, doi:<a href=\"https://doi.org/10.15479/AT-ISTA-20234\">10.15479/AT-ISTA-20234</a>.","apa":"Saona Urmeneta, R. J. (2025). <i>Robustness of solutions in game theory : Values and strategies in partially observable, perturbed, stochastic, and infinite games</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT-ISTA-20234\">https://doi.org/10.15479/AT-ISTA-20234</a>","short":"R.J. Saona Urmeneta, Robustness of Solutions in Game Theory : Values and Strategies in Partially Observable, Perturbed, Stochastic, and Infinite Games, Institute of Science and Technology Austria, 2025.","chicago":"Saona Urmeneta, Raimundo J. “Robustness of Solutions in Game Theory : Values and Strategies in Partially Observable, Perturbed, Stochastic, and Infinite Games.” Institute of Science and Technology Austria, 2025. <a href=\"https://doi.org/10.15479/AT-ISTA-20234\">https://doi.org/10.15479/AT-ISTA-20234</a>.","ista":"Saona Urmeneta RJ. 2025. Robustness of solutions in game theory : Values and strategies in partially observable, perturbed, stochastic, and infinite games. Institute of Science and Technology Austria."},"month":"08","language":[{"iso":"eng"}],"degree_awarded":"PhD","doi":"10.15479/AT-ISTA-20234","OA_place":"publisher","ddc":["519"],"supervisor":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"}],"_id":"20234","article_processing_charge":"No","oa":1,"has_accepted_license":"1","ec_funded":1,"year":"2025","publisher":"Institute of Science and Technology Austria","title":"Robustness of solutions in game theory : Values and strategies in partially observable, perturbed, stochastic, and infinite games","abstract":[{"text":"Game Theory is the mathematical formalization of social dynamics - systems where agents interact over time and the evolution of the state of the system depends on the decisions of every player. \r\nThis thesis takes the perspective of a single player and focuses on what they can guarantee in the worst case over the behavior of other players.\r\nIn other words, we consider that the objective of every other player in the game is exactly the opposite to the player.\r\nWe focus on sustained interactions over time, where the players repeatedly obtain quantitative rewards over time, and they are interested in maximizing their long-term performance.\t\r\nFormally, this thesis focuses on zero-sum games with the liminf average objective.\r\nTwo fundamental questions that Game Theory aims to answer are the following.\r\n\r\n1. How much can a player guarantee to obtain after the interaction?\r\n\r\n2. How to act in order to obtain the previously mentioned guarantee?\r\n\r\nThese questions are formalized by the concepts of \"value\" and \"optimal strategies\". \t\r\nWe study their properties on games that exhibit one or more of the following properties. \r\n\r\n1. Partial Observation: \r\nthe players can not perfectly observe the current state of the system during the game. We consider the model of (finite) Partially Observable Markov Decision Processes and prove that finite-memory strategies are sufficient to approximately guarantee the value.\r\n\r\n2. Perturbed Description: \r\nthe formal description of the game is perturbed by a small parameter.\r\nWe consider the model of (finite) Perturbed Matrix Games, and provide algorithms to check various robustness properties and to compute the parameterized value and optimal strategies.\r\n\r\n3. Stochastic Transitions: \r\nthe actions of the players determine the behavior of the evolution of the system, described as a probability distribution over the next state.\r\nWe consider the model of (finite) Perturbed Stochastic Games and provide formulas for the marginal value.\r\n\r\n4. Infinite States: \r\nthe system can be in infinitely many states.\r\nWe consider the model of Random Dynamic Games on a class of infinite graphs, prove the existence of the value, and quantify the concentration of finite-horizon values.","lang":"eng"}],"publication_status":"published","alternative_title":["ISTA Thesis"],"file":[{"checksum":"394a651f7de7085e509ef856ffe7bd97","creator":"rsaonaur","content_type":"application/pdf","file_id":"20240","access_level":"open_access","file_size":1503623,"file_name":"2025_Saona_Raimundo_Thesis.pdf","relation":"main_file","date_updated":"2025-08-28T14:47:07Z","date_created":"2025-08-28T14:47:07Z","success":1},{"file_name":"2025_Saona_Raimundo_Thesis.zip","file_size":622747,"access_level":"closed","content_type":"application/zip","file_id":"20241","creator":"rsaonaur","checksum":"09fb2633e66aac80433d373f4180c5b4","date_created":"2025-08-28T14:47:12Z","date_updated":"2025-08-28T14:47:12Z","relation":"source_file"}],"date_published":"2025-08-27T00:00:00Z","file_date_updated":"2025-08-28T14:47:12Z","day":"27","page":"125","type":"dissertation","department":[{"_id":"GradSch"},{"_id":"KrCh"}],"related_material":{"record":[{"status":"public","id":"9311","relation":"part_of_dissertation"},{"status":"public","id":"18266","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","id":"19508","status":"public"},{"relation":"part_of_dissertation","id":"17037","status":"public"}]},"corr_author":"1","date_updated":"2026-07-22T06:37:12Z","acknowledgement":"Funding sources The works included in this thesis were partially supported by:\r\n• Austrian Science Fund (FWF), grants 10.55776/COE12 and No RiSE/SHiNE S11407,\r\n• French Agence Nationale de la Recherche (ANR), grants ANR-21-CE40-0020 (CONVERGENCE) and ANR-20-CE40-0002 (GrHyDy),\r\n• Fondation Mathématique Jaques Hadamard, grant PGMO RSG 2018-0031H,\r\n• European Research Council (ERC), Consolidator grant 863818 (ForM-SMArt),\r\n• Agencia Nacional de Investigación y Desarrollo (ANID Chile), grant ACT210005,\r\n• Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt Chile), grant 1220174,\r\n• Comisión Nacional de Investigación Científica y Tecnológica (CONICYT Chile), grant\r\nPII 20150140,\r\n• Evaluation-orientation de la Coopération Scientifique and Comisión Nacional de Investigación Científica y Tecnológica (ECOS-CONICYT), grant C15E03,\r\n• European Cooperation in Science and Technology (E-COST), grants CA16228 - European\r\nNetwork for Game Theory (GAMENET) and E-COST-GRANT-CA16228-c5a69859.\r\n","publication_identifier":{"issn":["2663-337X"]},"author":[{"first_name":"Raimundo J","full_name":"Saona Urmeneta, Raimundo J","last_name":"Saona Urmeneta","orcid":"0000-0001-5103-038X","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425"}],"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","oa_version":"Published Version"},{"OA_type":"closed access","external_id":{"isi":["001184648000001"]},"_id":"17037","quality_controlled":"1","article_processing_charge":"No","volume":50,"language":[{"iso":"eng"}],"doi":"10.1287/moor.2023.0297","das_tickbox":"1","status":"public","date_created":"2024-05-22T11:41:14Z","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"month":"02","issue":"1","citation":{"ama":"Attia L, Oliu-Barton M, Saona Urmeneta RJ. Marginal values of a stochastic game. <i>Mathematics of Operations Research</i>. 2025;50(1):482-505. doi:<a href=\"https://doi.org/10.1287/moor.2023.0297\">10.1287/moor.2023.0297</a>","mla":"Attia, Luc, et al. “Marginal Values of a Stochastic Game.” <i>Mathematics of Operations Research</i>, vol. 50, no. 1, Institute for Operations Research and the Management Sciences, 2025, pp. 482–505, doi:<a href=\"https://doi.org/10.1287/moor.2023.0297\">10.1287/moor.2023.0297</a>.","ieee":"L. Attia, M. Oliu-Barton, and R. J. Saona Urmeneta, “Marginal values of a stochastic game,” <i>Mathematics of Operations Research</i>, vol. 50, no. 1. Institute for Operations Research and the Management Sciences, pp. 482–505, 2025.","apa":"Attia, L., Oliu-Barton, M., &#38; Saona Urmeneta, R. J. (2025). Marginal values of a stochastic game. <i>Mathematics of Operations Research</i>. Institute for Operations Research and the Management Sciences. <a href=\"https://doi.org/10.1287/moor.2023.0297\">https://doi.org/10.1287/moor.2023.0297</a>","short":"L. Attia, M. Oliu-Barton, R.J. Saona Urmeneta, Mathematics of Operations Research 50 (2025) 482–505.","chicago":"Attia, Luc, Miquel Oliu-Barton, and Raimundo J Saona Urmeneta. “Marginal Values of a Stochastic Game.” <i>Mathematics of Operations Research</i>. Institute for Operations Research and the Management Sciences, 2025. <a href=\"https://doi.org/10.1287/moor.2023.0297\">https://doi.org/10.1287/moor.2023.0297</a>.","ista":"Attia L, Oliu-Barton M, Saona Urmeneta RJ. 2025. Marginal values of a stochastic game. Mathematics of Operations Research. 50(1), 482–505."},"abstract":[{"lang":"eng","text":"Zero-sum stochastic games are parameterized by payoffs, transitions, and possibly a discount rate. In this article, we study how the main solution concepts, the discounted and undiscounted values, vary when these parameters are perturbed. We focus on the marginal values, introduced by Mills in 1956 in the context of matrix games—that is, the directional derivatives of the value along any fixed perturbation. We provide a formula for the marginal values of a discounted stochastic game. Further, under mild assumptions on the perturbation, we provide a formula for their limit as the discount rate vanishes and for the marginal values of an undiscounted stochastic game. We also show, via an example, that the two latter differ in general."}],"publisher":"Institute for Operations Research and the Management Sciences","title":"Marginal values of a stochastic game","ec_funded":1,"year":"2025","scopus_import":"1","day":"01","department":[{"_id":"GradSch"},{"_id":"KrCh"}],"type":"journal_article","isi":1,"page":"482-505","date_published":"2025-02-01T00:00:00Z","publication_status":"published","intvolume":"        50","article_type":"original","oa_version":"None","publication_identifier":{"eissn":["1526-5471"],"issn":["0364-765X"]},"author":[{"full_name":"Attia, Luc","first_name":"Luc","last_name":"Attia"},{"last_name":"Oliu-Barton","full_name":"Oliu-Barton, Miquel","first_name":"Miquel"},{"id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","orcid":"0000-0001-5103-038X","last_name":"Saona Urmeneta","first_name":"Raimundo J","full_name":"Saona Urmeneta, Raimundo J"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"This work was supported by Fondation CFM pour la Recherche; the European Research Council [Grant ERC-CoG-863818 (ForM-SMArt)]; and Agence Nationale de la Recherche [Grant ANR-21-CE40-0020].","date_updated":"2026-07-22T06:37:13Z","related_material":{"record":[{"id":"20234","status":"public","relation":"dissertation_contains"}]},"publication":"Mathematics of Operations Research"},{"publication_status":"published","isi":1,"type":"conference","department":[{"_id":"KrCh"}],"day":"08","date_published":"2024-07-08T00:00:00Z","date_updated":"2025-09-08T07:44:29Z","acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant.\r\n","corr_author":"1","publication":"39th Annual ACM/IEEE Symposium on Logic in Computer Science","oa_version":"Preprint","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2405.02479","open_access":"1"}],"arxiv":1,"article_number":"6","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication_identifier":{"eissn":["1043-6871"],"isbn":["9798400706608"]},"author":[{"id":"02d96aae-000e-11ec-b801-cadd0a5eefbb","last_name":"Asadi","full_name":"Asadi, Ali","first_name":"Ali"},{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","last_name":"Svoboda","orcid":"0000-0002-1419-3267","first_name":"Jakub","full_name":"Svoboda, Jakub"},{"orcid":"0000-0001-5103-038X","last_name":"Saona Urmeneta","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","full_name":"Saona Urmeneta, Raimundo J","first_name":"Raimundo J"}],"doi":"10.1145/3661814.3662080","language":[{"iso":"eng"}],"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.","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.","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>.","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>.","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.","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>"},"month":"07","project":[{"grant_number":"863818","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"date_created":"2024-06-03T07:43:15Z","status":"public","external_id":{"arxiv":["2405.02479"],"isi":["001275042100006"]},"conference":{"location":"Tallinn, Estonia","end_date":"2024-07-11","start_date":"2024-07-08","name":"LICS: Logic in Computer Science"},"oa":1,"_id":"17098","article_processing_charge":"No","quality_controlled":"1","scopus_import":"1","ec_funded":1,"year":"2024","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"}],"title":"Deterministic sub-exponential algorithm for discounted-sum games with unary weights","publisher":"Association for Computing Machinery"},{"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."}],"title":"Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","has_accepted_license":"1","year":"2024","ec_funded":1,"scopus_import":"1","conference":{"start_date":"2024-12-16","name":"FSTTCS: Foundations of Software Technology and Theoretical Computer Science","end_date":"2024-12-18","location":"Gujarat, India"},"OA_type":"gold","external_id":{"isi":["001537516500005"],"arxiv":["2405.02486"]},"oa":1,"_id":"17099","article_processing_charge":"No","quality_controlled":"1","ddc":["000"],"OA_place":"publisher","doi":"10.4230/LIPIcs.FSTTCS.2024.5","volume":323,"language":[{"iso":"eng"}],"month":"12","citation":{"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.","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.","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>.","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>","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>.","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.","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>"},"status":"public","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","call_identifier":"H2020"}],"date_created":"2024-06-03T07:44:27Z","arxiv":1,"oa_version":"Published Version","article_number":"5","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773553"]},"author":[{"first_name":"Ali","full_name":"Asadi, Ali","id":"02d96aae-000e-11ec-b801-cadd0a5eefbb","last_name":"Asadi"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"last_name":"Saona Urmeneta","orcid":"0000-0001-5103-038X","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","full_name":"Saona Urmeneta, Raimundo J","first_name":"Raimundo J"},{"orcid":"0000-0002-1419-3267","last_name":"Svoboda","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","first_name":"Jakub","full_name":"Svoboda, Jakub"}],"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)","date_updated":"2025-12-02T13:40:52Z","corr_author":"1","publication":"44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science","department":[{"_id":"KrCh"}],"isi":1,"type":"conference","day":"05","file_date_updated":"2025-01-08T09:49:31Z","date_published":"2024-12-05T00:00:00Z","file":[{"access_level":"open_access","file_size":847960,"file_name":"2024_LIPIcs_Asadi.pdf","checksum":"5b544ab4692b93300b404435c036ddd4","creator":"dernst","file_id":"18777","content_type":"application/pdf","date_created":"2025-01-08T09:49:31Z","success":1,"relation":"main_file","date_updated":"2025-01-08T09:49:31Z"}],"intvolume":"       323","alternative_title":["LIPIcs"],"publication_status":"published"},{"doi":"10.48550/arXiv.2401.16252","language":[{"iso":"eng"}],"month":"01","citation":{"short":"L. Attia, L. Lichev, D. Mitsche, R.J. Saona Urmeneta, B. Ziliotto, ArXiv (n.d.).","ista":"Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. Zero-sum random games on directed graphs. arXiv, 2401.16252.","chicago":"Attia, Luc, Lyuben Lichev, Dieter Mitsche, Raimundo J Saona Urmeneta, and Bruno Ziliotto. “Zero-Sum Random Games on Directed Graphs.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/arXiv.2401.16252\">https://doi.org/10.48550/arXiv.2401.16252</a>.","mla":"Attia, Luc, et al. “Zero-Sum Random Games on Directed Graphs.” <i>ArXiv</i>, 2401.16252, doi:<a href=\"https://doi.org/10.48550/arXiv.2401.16252\">10.48550/arXiv.2401.16252</a>.","ieee":"L. Attia, L. Lichev, D. Mitsche, R. J. Saona Urmeneta, and B. Ziliotto, “Zero-sum random games on directed graphs,” <i>arXiv</i>. .","ama":"Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. Zero-sum random games on directed graphs. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/arXiv.2401.16252\">10.48550/arXiv.2401.16252</a>","apa":"Attia, L., Lichev, L., Mitsche, D., Saona Urmeneta, R. J., &#38; Ziliotto, B. (n.d.). Zero-sum random games on directed graphs. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/arXiv.2401.16252\">https://doi.org/10.48550/arXiv.2401.16252</a>"},"status":"public","publication_status":"submitted","date_created":"2024-06-03T07:45:22Z","department":[{"_id":"KrCh"}],"type":"preprint","external_id":{"arxiv":["2401.16252"]},"day":"29","oa":1,"article_processing_charge":"No","_id":"17101","date_published":"2024-01-29T00:00:00Z","year":"2024","acknowledgement":"This work was supported by the French Agence Nationale de la Recherche (ANR) under references ANR-21-CE40-0020 (CONVERGENCE project) and ANR-20-CE40-0002 (GrHyDy), and by Fondecyt grant 1220174. This collaboration was mainly conducted during a 1-year visit of Bruno Ziliotto to the Center for Mathematical Modeling (CMM) at University of Chile in 2023,\r\nunder the IRL program of CNRS.","date_updated":"2024-06-03T07:50:29Z","publication":"arXiv","oa_version":"Preprint","arxiv":1,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2401.16252"}],"article_number":"2401.16252","abstract":[{"lang":"eng","text":"This paper considers a class of two-player zero-sum games on directed graphs whose vertices are equipped with random payoffs of bounded support known by both players.\r\nStarting from a fixed vertex, players take turns to move a token along the edges of the graph.\r\nOn the one hand, for acyclic directed graphs of bounded degree and sub-exponential expansion, we show that the value of the game converges almost surely to a constant at an exponential rate dominated in terms of the expansion.\r\nOn the other hand, for the infinite d-ary tree that does not fall into the previous class of graphs, we show convergence at a double-exponential rate in terms of the expansion."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Zero-sum random games on directed graphs","author":[{"last_name":"Attia","full_name":"Attia, Luc","first_name":"Luc"},{"first_name":"Lyuben","full_name":"Lichev, Lyuben","last_name":"Lichev"},{"first_name":"Dieter","full_name":"Mitsche, Dieter","last_name":"Mitsche"},{"orcid":"0000-0001-5103-038X","last_name":"Saona Urmeneta","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","first_name":"Raimundo J","full_name":"Saona Urmeneta, Raimundo J"},{"last_name":"Ziliotto","first_name":"Bruno","full_name":"Ziliotto, Bruno"}]},{"publication_status":"published","intvolume":"        50","day":"01","page":"2433-3282","type":"journal_article","isi":1,"department":[{"_id":"GradSch"},{"_id":"KrCh"}],"date_published":"2024-10-01T00:00:00Z","corr_author":"1","date_updated":"2026-04-07T12:31:21Z","acknowledgement":"This research was supported by Fondation CFM pour la Recherche, the H2020 European Research Council [Grant ERC-CoG-863818 (ForM-SMArt)], the Austrian Science Fund [Grant 10.55776/COE12], ANID Chile [Grant ACT210005], and Agence Nationale de la Recherche [Grant ANR-21-CE40-0020].","related_material":{"record":[{"relation":"dissertation_contains","id":"20234","status":"public"}]},"publication":"Mathematics of Operations Research","article_type":"original","oa_version":"None","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"first_name":"Miquel","full_name":"Oliu-Barton, Miquel","last_name":"Oliu-Barton"},{"full_name":"Saona Urmeneta, Raimundo J","first_name":"Raimundo J","last_name":"Saona Urmeneta","orcid":"0000-0001-5103-038X","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425"}],"publication_identifier":{"issn":["0364-765X"],"eissn":["1526-5471"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"volume":50,"doi":"10.1287/moor.2022.0332","date_created":"2024-10-09T07:02:20Z","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"status":"public","issue":"4","citation":{"chicago":"Chatterjee, Krishnendu, Miquel Oliu-Barton, and Raimundo J Saona Urmeneta. “Value-Positivity for Matrix Games.” <i>Mathematics of Operations Research</i>. Institute for Operations Research and the Management Sciences, 2024. <a href=\"https://doi.org/10.1287/moor.2022.0332\">https://doi.org/10.1287/moor.2022.0332</a>.","ista":"Chatterjee K, Oliu-Barton M, Saona Urmeneta RJ. 2024. Value-positivity for matrix games. Mathematics of Operations Research. 50(4), 2433–3282.","short":"K. Chatterjee, M. Oliu-Barton, R.J. Saona Urmeneta, Mathematics of Operations Research 50 (2024) 2433–3282.","apa":"Chatterjee, K., Oliu-Barton, M., &#38; Saona Urmeneta, R. J. (2024). Value-positivity for matrix games. <i>Mathematics of Operations Research</i>. Institute for Operations Research and the Management Sciences. <a href=\"https://doi.org/10.1287/moor.2022.0332\">https://doi.org/10.1287/moor.2022.0332</a>","mla":"Chatterjee, Krishnendu, et al. “Value-Positivity for Matrix Games.” <i>Mathematics of Operations Research</i>, vol. 50, no. 4, Institute for Operations Research and the Management Sciences, 2024, pp. 2433–3282, doi:<a href=\"https://doi.org/10.1287/moor.2022.0332\">10.1287/moor.2022.0332</a>.","ieee":"K. Chatterjee, M. Oliu-Barton, and R. J. Saona Urmeneta, “Value-positivity for matrix games,” <i>Mathematics of Operations Research</i>, vol. 50, no. 4. Institute for Operations Research and the Management Sciences, pp. 2433–3282, 2024.","ama":"Chatterjee K, Oliu-Barton M, Saona Urmeneta RJ. Value-positivity for matrix games. <i>Mathematics of Operations Research</i>. 2024;50(4):2433-3282. doi:<a href=\"https://doi.org/10.1287/moor.2022.0332\">10.1287/moor.2022.0332</a>"},"month":"10","external_id":{"isi":["001328875900001"]},"OA_type":"closed access","quality_controlled":"1","_id":"18266","article_processing_charge":"No","scopus_import":"1","year":"2024","ec_funded":1,"abstract":[{"lang":"eng","text":"Matrix games are the most basic model in game theory, and yet robustness with respect to small perturbations of the matrix entries is not fully understood. In this paper, we introduce value positivity and uniform value positivity, two properties that refine the notion of optimality in the context of polynomially perturbed matrix games. The first concept captures how the value depends on the perturbation parameter, and the second consists of the existence of a fixed strategy that guarantees the value of the unperturbed matrix game for every sufficiently small positive parameter. We provide polynomial-time algorithms to check whether a polynomially perturbed matrix game satisfies these properties. We further provide the functional form for a parameterized optimal strategy and the value function. Finally, we translate our results to linear programming and stochastic games, where value positivity is related to the existence of robust solutions."}],"publisher":"Institute for Operations Research and the Management Sciences","title":"Value-positivity for matrix games"},{"date_published":"2023-02-01T00:00:00Z","day":"01","page":"4590-4605","type":"conference","department":[{"_id":"GradSch"},{"_id":"KrCh"}],"publication_status":"published","publication_identifier":{"isbn":["9781611977554"]},"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","orcid":"0000-0002-1712-2165","last_name":"Meggendorfer","full_name":"Meggendorfer, Tobias","first_name":"Tobias"},{"first_name":"Raimundo J","full_name":"Saona Urmeneta, Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","last_name":"Saona Urmeneta","orcid":"0000-0001-5103-038X"},{"first_name":"Jakub","full_name":"Svoboda, Jakub","orcid":"0000-0002-1419-3267","last_name":"Svoboda","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1137/1.9781611977554.ch173"}],"oa_version":"Published Version","publication":"Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms","corr_author":"1","date_updated":"2026-06-18T17:28:38Z","acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant.","ddc":["000"],"quality_controlled":"1","_id":"12676","article_processing_charge":"No","oa":1,"conference":{"location":"Florence, Italy","end_date":"2023-01-25","start_date":"2023-01-22","name":"SODA: Symposium on Discrete Algorithms"},"project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"date_created":"2023-02-24T12:20:47Z","status":"public","citation":{"ama":"Chatterjee K, Meggendorfer T, Saona Urmeneta RJ, Svoboda J. Faster algorithm for turn-based stochastic games with bounded treewidth. In: <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2023:4590-4605. doi:<a href=\"https://doi.org/10.1137/1.9781611977554.ch173\">10.1137/1.9781611977554.ch173</a>","ieee":"K. Chatterjee, T. Meggendorfer, R. J. Saona Urmeneta, and J. Svoboda, “Faster algorithm for turn-based stochastic games with bounded treewidth,” in <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Florence, Italy, 2023, pp. 4590–4605.","mla":"Chatterjee, Krishnendu, et al. “Faster Algorithm for Turn-Based Stochastic Games with Bounded Treewidth.” <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2023, pp. 4590–605, doi:<a href=\"https://doi.org/10.1137/1.9781611977554.ch173\">10.1137/1.9781611977554.ch173</a>.","apa":"Chatterjee, K., Meggendorfer, T., Saona Urmeneta, R. J., &#38; Svoboda, J. (2023). Faster algorithm for turn-based stochastic games with bounded treewidth. In <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 4590–4605). Florence, Italy: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611977554.ch173\">https://doi.org/10.1137/1.9781611977554.ch173</a>","short":"K. Chatterjee, T. Meggendorfer, R.J. Saona Urmeneta, J. Svoboda, in:, Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2023, pp. 4590–4605.","ista":"Chatterjee K, Meggendorfer T, Saona Urmeneta RJ, Svoboda J. 2023. Faster algorithm for turn-based stochastic games with bounded treewidth. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 4590–4605.","chicago":"Chatterjee, Krishnendu, Tobias Meggendorfer, Raimundo J Saona Urmeneta, and Jakub Svoboda. “Faster Algorithm for Turn-Based Stochastic Games with Bounded Treewidth.” In <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 4590–4605. Society for Industrial and Applied Mathematics, 2023. <a href=\"https://doi.org/10.1137/1.9781611977554.ch173\">https://doi.org/10.1137/1.9781611977554.ch173</a>."},"month":"02","language":[{"iso":"eng"}],"doi":"10.1137/1.9781611977554.ch173","publisher":"Society for Industrial and Applied Mathematics","title":"Faster algorithm for turn-based stochastic games with bounded treewidth","abstract":[{"lang":"eng","text":"Turn-based stochastic games (aka simple stochastic games) are two-player zero-sum games played on directed graphs with probabilistic transitions. The goal of player-max is to maximize the probability to reach a target state against the adversarial player-min. These games lie in NP ∩ coNP and are among the rare combinatorial problems that belong to this complexity class for which the existence of polynomial-time algorithm is a major open question. While randomized sub-exponential time algorithm exists, all known deterministic algorithms require exponential time in the worst-case. An important open question has been whether faster algorithms can be obtained parametrized by the treewidth of the game graph. Even deterministic sub-exponential time algorithm for constant treewidth turn-based stochastic games has remain elusive. In this work our main result is a deterministic algorithm to solve turn-based stochastic games that, given a game with n states, treewidth at most t, and the bit-complexity of the probabilistic transition function log D, has running time O ((tn2 log D)t log n). In particular, our algorithm is quasi-polynomial time for games with constant or poly-logarithmic treewidth."}],"ec_funded":1,"year":"2023"},{"oa":1,"day":"08","external_id":{"arxiv":["2304.04024"]},"type":"preprint","department":[{"_id":"KrCh"}],"_id":"17100","date_published":"2023-04-08T00:00:00Z","article_processing_charge":"No","language":[{"iso":"eng"}],"doi":"10.48550/arXiv.2304.04024","project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"date_created":"2024-06-03T07:44:54Z","publication_status":"submitted","status":"public","citation":{"mla":"Giambartolomei, Giordano, et al. “Prophet Inequalities: Separating Random Order from Order Selection.” <i>ArXiv</i>, 2304.04024, doi:<a href=\"https://doi.org/10.48550/arXiv.2304.04024\">10.48550/arXiv.2304.04024</a>.","ieee":"G. Giambartolomei, F. M.-T. Frederik Mallmann-Trenn, and R. J. Saona Urmeneta, “Prophet inequalities: Separating random order from order selection,” <i>arXiv</i>. .","ama":"Giambartolomei G, Frederik Mallmann-Trenn FM-T, Saona Urmeneta RJ. Prophet inequalities: Separating random order from order selection. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/arXiv.2304.04024\">10.48550/arXiv.2304.04024</a>","apa":"Giambartolomei, G., Frederik Mallmann-Trenn, F. M.-T., &#38; Saona Urmeneta, R. J. (n.d.). Prophet inequalities: Separating random order from order selection. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/arXiv.2304.04024\">https://doi.org/10.48550/arXiv.2304.04024</a>","short":"G. Giambartolomei, F.M.-T. Frederik Mallmann-Trenn, R.J. Saona Urmeneta, ArXiv (n.d.).","chicago":"Giambartolomei, Giordano, Frederik Mallmann-Trenn Frederik Mallmann-Trenn, and Raimundo J Saona Urmeneta. “Prophet Inequalities: Separating Random Order from Order Selection.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/arXiv.2304.04024\">https://doi.org/10.48550/arXiv.2304.04024</a>.","ista":"Giambartolomei G, Frederik Mallmann-Trenn FM-T, Saona Urmeneta RJ. Prophet inequalities: Separating random order from order selection. arXiv, 2304.04024."},"month":"04","article_number":"2304.04024","abstract":[{"lang":"eng","text":"Prophet inequalities are a central object of study in optimal stopping theory. A gambler is sent values online, sampled from an instance of independent distributions, in an adversarial, random or selected order, depending on the model. When observing each value, the gambler either accepts it as a reward or irrevocably rejects it and proceeds to observe the next value. The goal of the gambler, who cannot see the future, is maximising the expected value of the reward while competing against the expectation of a prophet (the offline maximum). In other words, one seeks to maximise the gambler-to-prophet ratio of the expectations.\r\nThe model, in which the gambler selects the arrival order first, and then observes the values, is known as Order Selection. In this model a ratio of 0.7251 has been proved to be attainable for any instance. In very recent work, this has been improved up to 0.7258. If the gambler chooses the arrival order (uniformly) at random, we obtain the Random Order model. The worst case ratio over all possible instances has been extensively studied for at least 40 years. In the recent work aforementioned, through simulations, this ratio has been shown to be at most 0.7254 for the Random Order model, thus establishing for the first time that carefully choosing the order, instead of simply taking it at random, benefits the gambler. We give an alternative, more rigorous proof of this fact, by showing mathematically that in the Random Order model, no algorithm can achieve a ratio larger than 0.7235. This sets a new state-of-the-art hardness for this model, and establishes more formally that there is a real benefit in choosing the order."}],"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2304.04024","open_access":"1"}],"oa_version":"Preprint","arxiv":1,"author":[{"last_name":"Giambartolomei","full_name":"Giambartolomei, Giordano","first_name":"Giordano"},{"last_name":"Frederik Mallmann-Trenn","full_name":"Frederik Mallmann-Trenn, Frederik Mallmann-Trenn","first_name":"Frederik Mallmann-Trenn"},{"last_name":"Saona Urmeneta","orcid":"0000-0001-5103-038X","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","full_name":"Saona Urmeneta, Raimundo J","first_name":"Raimundo J"}],"title":"Prophet inequalities: Separating random order from order selection","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2025-04-14T07:52:47Z","ec_funded":1,"acknowledgement":"This research was partially supported by the EPSRC grant EP/W005573/1, the ERC CoG 863818 (ForM-SMArt) grant, and the ANID Chile grant ACT210005. We would like to thank Jos´e Correa and Bruno Zilotto for their precious advice, and Mona Mohammadi and Roodabeh Safavi for early conversations.","year":"2023","publication":"arXiv"},{"abstract":[{"text":"Empirical essays of fitness landscapes suggest that they may be rugged, that is having multiple fitness peaks. Such fitness landscapes, those that have multiple peaks, necessarily have special local structures, called reciprocal sign epistasis (Poelwijk et al. in J Theor Biol 272:141–144, 2011). Here, we investigate the quantitative relationship between the number of fitness peaks and the number of reciprocal sign epistatic interactions. Previously, it has been shown (Poelwijk et al. in J Theor Biol 272:141–144, 2011) that pairwise reciprocal sign epistasis is a necessary but not sufficient condition for the existence of multiple peaks. Applying discrete Morse theory, which to our knowledge has never been used in this context, we extend this result by giving the minimal number of reciprocal sign epistatic interactions required to create a given number of peaks.","lang":"eng"}],"keyword":["Computational Theory and Mathematics","General Agricultural and Biological Sciences","Pharmacology","General Environmental Science","General Biochemistry","Genetics and Molecular Biology","General Mathematics","Immunology","General Neuroscience"],"title":"Relation between the number of peaks and the number of reciprocal sign epistatic interactions","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"publisher":"Springer Nature","ec_funded":1,"has_accepted_license":"1","year":"2022","scopus_import":"1","pmid":1,"external_id":{"isi":["000812509800001"],"pmid":["35713756"]},"oa":1,"_id":"11447","quality_controlled":"1","article_processing_charge":"Yes (via OA deal)","ddc":["510","570"],"doi":"10.1007/s11538-022-01029-z","volume":84,"language":[{"iso":"eng"}],"month":"06","issue":"8","citation":{"ista":"Saona Urmeneta RJ, Kondrashov F, Khudiakova K. 2022. Relation between the number of peaks and the number of reciprocal sign epistatic interactions. Bulletin of Mathematical Biology. 84(8), 74.","chicago":"Saona Urmeneta, Raimundo J, Fyodor Kondrashov, and Kseniia Khudiakova. “Relation between the Number of Peaks and the Number of Reciprocal Sign Epistatic Interactions.” <i>Bulletin of Mathematical Biology</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s11538-022-01029-z\">https://doi.org/10.1007/s11538-022-01029-z</a>.","short":"R.J. Saona Urmeneta, F. Kondrashov, K. Khudiakova, Bulletin of Mathematical Biology 84 (2022).","apa":"Saona Urmeneta, R. J., Kondrashov, F., &#38; Khudiakova, K. (2022). Relation between the number of peaks and the number of reciprocal sign epistatic interactions. <i>Bulletin of Mathematical Biology</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s11538-022-01029-z\">https://doi.org/10.1007/s11538-022-01029-z</a>","ama":"Saona Urmeneta RJ, Kondrashov F, Khudiakova K. Relation between the number of peaks and the number of reciprocal sign epistatic interactions. <i>Bulletin of Mathematical Biology</i>. 2022;84(8). doi:<a href=\"https://doi.org/10.1007/s11538-022-01029-z\">10.1007/s11538-022-01029-z</a>","mla":"Saona Urmeneta, Raimundo J., et al. “Relation between the Number of Peaks and the Number of Reciprocal Sign Epistatic Interactions.” <i>Bulletin of Mathematical Biology</i>, vol. 84, no. 8, 74, Springer Nature, 2022, doi:<a href=\"https://doi.org/10.1007/s11538-022-01029-z\">10.1007/s11538-022-01029-z</a>.","ieee":"R. J. Saona Urmeneta, F. Kondrashov, and K. Khudiakova, “Relation between the number of peaks and the number of reciprocal sign epistatic interactions,” <i>Bulletin of Mathematical Biology</i>, vol. 84, no. 8. Springer Nature, 2022."},"status":"public","project":[{"call_identifier":"H2020","grant_number":"771209","_id":"26580278-B435-11E9-9278-68D0E5697425","name":"Characterizing the fitness landscape on population and global scales"},{"grant_number":"I05127","_id":"34e076d6-11ca-11ed-8bc3-aec76c41a181","name":"Evolutionary analysis of gene regulation"}],"date_created":"2022-06-17T16:16:15Z","oa_version":"Published Version","article_type":"original","article_number":"74","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["0092-8240"],"eissn":["1522-9602"]},"author":[{"first_name":"Raimundo J","full_name":"Saona Urmeneta, Raimundo J","last_name":"Saona Urmeneta","orcid":"0000-0001-5103-038X","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425"},{"orcid":"0000-0001-8243-4694","last_name":"Kondrashov","id":"44FDEF62-F248-11E8-B48F-1D18A9856A87","first_name":"Fyodor","full_name":"Kondrashov, Fyodor"},{"full_name":"Khudiakova, Kseniia","first_name":"Kseniia","id":"4E6DC800-AE37-11E9-AC72-31CAE5697425","last_name":"Khudiakova","orcid":"0000-0002-6246-1465"}],"acknowledgement":"We are grateful to Herbert Edelsbrunner and Jeferson Zapata for helpful discussions. Open access funding provided by Austrian Science Fund (FWF). Partially supported by the ERC Consolidator (771209–CharFL) and the FWF Austrian Science Fund (I5127-B) grants to FAK.","date_updated":"2026-06-12T12:43:34Z","corr_author":"1","publication":"Bulletin of Mathematical Biology","related_material":{"record":[{"status":"public","id":"21918","relation":"dissertation_contains"}],"link":[{"relation":"erratum","url":"https://doi.org/10.1007/s11538-022-01118-z"}]},"department":[{"_id":"GradSch"},{"_id":"NiBa"},{"_id":"JaMa"}],"isi":1,"type":"journal_article","file_date_updated":"2022-06-20T07:51:32Z","day":"17","date_published":"2022-06-17T00:00:00Z","file":[{"creator":"dernst","checksum":"05a1fe7d10914a00c2bca9b447993a65","content_type":"application/pdf","file_id":"11455","file_name":"2022_BulletinMathBiology_Saona.pdf","file_size":463025,"access_level":"open_access","date_updated":"2022-06-20T07:51:32Z","relation":"main_file","date_created":"2022-06-20T07:51:32Z","success":1}],"intvolume":"        84","publication_status":"published"},{"language":[{"iso":"eng"}],"doi":"10.48550/ARXIV.2209.14368","status":"public","project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"date_created":"2023-02-24T12:21:40Z","publication_status":"submitted","month":"09","citation":{"apa":"Chatterjee, K., Mohammadi, M., &#38; Saona Urmeneta, R. J. (n.d.). Repeated prophet inequality with near-optimal bounds. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/ARXIV.2209.14368\">https://doi.org/10.48550/ARXIV.2209.14368</a>","ama":"Chatterjee K, Mohammadi M, Saona Urmeneta RJ. Repeated prophet inequality with near-optimal bounds. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/ARXIV.2209.14368\">10.48550/ARXIV.2209.14368</a>","mla":"Chatterjee, Krishnendu, et al. “Repeated Prophet Inequality with Near-Optimal Bounds.” <i>ArXiv</i>, 2209.14368, doi:<a href=\"https://doi.org/10.48550/ARXIV.2209.14368\">10.48550/ARXIV.2209.14368</a>.","ieee":"K. Chatterjee, M. Mohammadi, and R. J. Saona Urmeneta, “Repeated prophet inequality with near-optimal bounds,” <i>arXiv</i>. .","chicago":"Chatterjee, Krishnendu, Mona Mohammadi, and Raimundo J Saona Urmeneta. “Repeated Prophet Inequality with Near-Optimal Bounds.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/ARXIV.2209.14368\">https://doi.org/10.48550/ARXIV.2209.14368</a>.","ista":"Chatterjee K, Mohammadi M, Saona Urmeneta RJ. Repeated prophet inequality with near-optimal bounds. arXiv, 2209.14368.","short":"K. Chatterjee, M. Mohammadi, R.J. Saona Urmeneta, ArXiv (n.d.)."},"day":"28","oa":1,"department":[{"_id":"GradSch"},{"_id":"KrCh"}],"type":"preprint","external_id":{"arxiv":["2209.14368"]},"date_published":"2022-09-28T00:00:00Z","_id":"12677","article_processing_charge":"No","corr_author":"1","year":"2022","acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant.","ec_funded":1,"date_updated":"2025-04-14T07:52:48Z","publication":"arXiv","article_number":"2209.14368","abstract":[{"text":"In modern sample-driven Prophet Inequality, an adversary chooses a sequence of n items with values v1,v2,…,vn to be presented to a decision maker (DM). The process follows in two phases. In the first phase (sampling phase), some items, possibly selected at random, are revealed to the DM, but she can never accept them. In the second phase, the DM is presented with the other items in a random order and online fashion. For each item, she must make an irrevocable decision to either accept the item and stop the process or reject the item forever and proceed to the next item. The goal of the DM is to maximize the expected value as compared to a Prophet (or offline algorithm) that has access to all information. In this setting, the sampling phase has no cost and is not part of the optimization process. However, in many scenarios, the samples are obtained as part of the decision-making process.\r\nWe model this aspect as a two-phase Prophet Inequality where an adversary chooses a sequence of 2n items with values v1,v2,…,v2n and the items are randomly ordered. Finally, there are two phases of the Prophet Inequality problem with the first n-items and the rest of the items, respectively. We show that some basic algorithms achieve a ratio of at most 0.450. We present an algorithm that achieves a ratio of at least 0.495. Finally, we show that for every algorithm the ratio it can achieve is at most 0.502. Hence our algorithm is near-optimal.","lang":"eng"}],"oa_version":"Preprint","arxiv":1,"main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2209.14368"}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"first_name":"Mona","full_name":"Mohammadi, Mona","id":"4363614d-b686-11ed-a7d5-ac9e4a24bc2e","last_name":"Mohammadi"},{"last_name":"Saona Urmeneta","orcid":"0000-0001-5103-038X","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","first_name":"Raimundo J","full_name":"Saona Urmeneta, Raimundo J"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Repeated prophet inequality with near-optimal bounds"},{"abstract":[{"lang":"eng","text":"Partially observable Markov decision processes (POMDPs) are standard models for dynamic systems with probabilistic and nondeterministic behaviour in uncertain environments. We prove that in POMDPs with long-run average objective, the decision maker has approximately optimal strategies with finite memory. This implies notably that approximating the long-run value is recursively enumerable, as well as a weak continuity property of the value with respect to the transition function. "}],"keyword":["Management Science and Operations Research","General Mathematics","Computer Science Applications"],"title":"Finite-memory strategies in POMDPs with long-run average objectives","publisher":"Institute for Operations Research and the Management Sciences","year":"2022","scopus_import":"1","external_id":{"arxiv":["1904.13360"],"isi":["000731918100001"]},"oa":1,"quality_controlled":"1","_id":"9311","article_processing_charge":"No","doi":"10.1287/moor.2020.1116","volume":47,"language":[{"iso":"eng"}],"month":"02","citation":{"short":"K. Chatterjee, R.J. Saona Urmeneta, B. Ziliotto, Mathematics of Operations Research 47 (2022) 100–119.","chicago":"Chatterjee, Krishnendu, Raimundo J Saona Urmeneta, and Bruno Ziliotto. “Finite-Memory Strategies in POMDPs with Long-Run Average Objectives.” <i>Mathematics of Operations Research</i>. Institute for Operations Research and the Management Sciences, 2022. <a href=\"https://doi.org/10.1287/moor.2020.1116\">https://doi.org/10.1287/moor.2020.1116</a>.","ista":"Chatterjee K, Saona Urmeneta RJ, Ziliotto B. 2022. Finite-memory strategies in POMDPs with long-run average objectives. Mathematics of Operations Research. 47(1), 100–119.","ama":"Chatterjee K, Saona Urmeneta RJ, Ziliotto B. Finite-memory strategies in POMDPs with long-run average objectives. <i>Mathematics of Operations Research</i>. 2022;47(1):100-119. doi:<a href=\"https://doi.org/10.1287/moor.2020.1116\">10.1287/moor.2020.1116</a>","mla":"Chatterjee, Krishnendu, et al. “Finite-Memory Strategies in POMDPs with Long-Run Average Objectives.” <i>Mathematics of Operations Research</i>, vol. 47, no. 1, Institute for Operations Research and the Management Sciences, 2022, pp. 100–19, doi:<a href=\"https://doi.org/10.1287/moor.2020.1116\">10.1287/moor.2020.1116</a>.","ieee":"K. Chatterjee, R. J. Saona Urmeneta, and B. Ziliotto, “Finite-memory strategies in POMDPs with long-run average objectives,” <i>Mathematics of Operations Research</i>, vol. 47, no. 1. Institute for Operations Research and the Management Sciences, pp. 100–119, 2022.","apa":"Chatterjee, K., Saona Urmeneta, R. J., &#38; Ziliotto, B. (2022). Finite-memory strategies in POMDPs with long-run average objectives. <i>Mathematics of Operations Research</i>. Institute for Operations Research and the Management Sciences. <a href=\"https://doi.org/10.1287/moor.2020.1116\">https://doi.org/10.1287/moor.2020.1116</a>"},"issue":"1","status":"public","project":[{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","call_identifier":"FWF","name":"Game Theory"}],"date_created":"2021-04-08T09:33:31Z","arxiv":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1904.13360"}],"oa_version":"Preprint","article_type":"original","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"first_name":"Raimundo J","full_name":"Saona Urmeneta, Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","last_name":"Saona Urmeneta","orcid":"0000-0001-5103-038X"},{"last_name":"Ziliotto","full_name":"Ziliotto, Bruno","first_name":"Bruno"}],"publication_identifier":{"eissn":["1526-5471"],"issn":["0364-765X"]},"acknowledgement":"Partially supported by Austrian Science Fund (FWF) NFN Grant No RiSE/SHiNE S11407, by CONICYT Chile through grant PII 20150140, and by ECOS-CONICYT through grant C15E03.\r\n","date_updated":"2026-04-07T12:31:21Z","publication":"Mathematics of Operations Research","related_material":{"record":[{"id":"20234","status":"public","relation":"dissertation_contains"}]},"department":[{"_id":"GradSch"},{"_id":"KrCh"}],"type":"journal_article","page":"100-119","isi":1,"day":"01","date_published":"2022-02-01T00:00:00Z","intvolume":"        47","publication_status":"published"}]