[{"year":"2023","date_updated":"2025-07-14T09:09:50Z","abstract":[{"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.","lang":"eng"}],"_id":"12676","publication_identifier":{"isbn":["9781611977554"]},"oa":1,"status":"public","ec_funded":1,"month":"02","publication_status":"published","conference":{"location":"Florence, Italy","end_date":"2023-01-25","name":"SODA: Symposium on Discrete Algorithms","start_date":"2023-01-22"},"doi":"10.1137/1.9781611977554.ch173","date_published":"2023-02-01T00:00:00Z","oa_version":"Published Version","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1137/1.9781611977554.ch173"}],"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.","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.","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>","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>."},"day":"01","acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant.","project":[{"grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020"}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"orcid":"0000-0002-1712-2165","first_name":"Tobias","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","last_name":"Meggendorfer","full_name":"Meggendorfer, Tobias"},{"full_name":"Saona Urmeneta, Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","last_name":"Saona Urmeneta","orcid":"0000-0001-5103-038X","first_name":"Raimundo J"},{"id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","last_name":"Svoboda","orcid":"0000-0002-1419-3267","first_name":"Jakub","full_name":"Svoboda, Jakub"}],"title":"Faster algorithm for turn-based stochastic games with bounded treewidth","publisher":"Society for Industrial and Applied Mathematics","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"4590-4605","date_created":"2023-02-24T12:20:47Z","publication":"Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms","language":[{"iso":"eng"}],"department":[{"_id":"GradSch"},{"_id":"KrCh"}],"type":"conference","article_processing_charge":"No","quality_controlled":"1"},{"ddc":["510","570"],"scopus_import":"1","file_date_updated":"2022-06-20T07:51:32Z","citation":{"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.","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>","short":"R.J. Saona Urmeneta, F. Kondrashov, K. Khudiakova, Bulletin of Mathematical Biology 84 (2022).","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>.","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>","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.","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>."},"intvolume":"        84","publication_status":"published","doi":"10.1007/s11538-022-01029-z","date_published":"2022-06-17T00:00:00Z","oa_version":"Published Version","publication_identifier":{"issn":["0092-8240"],"eissn":["1522-9602"]},"oa":1,"status":"public","ec_funded":1,"month":"06","year":"2022","date_updated":"2023-08-03T07:20:53Z","issue":"8","abstract":[{"lang":"eng","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."}],"_id":"11447","article_number":"74","article_type":"original","article_processing_charge":"Yes (via OA deal)","related_material":{"link":[{"relation":"erratum","url":"https://doi.org/10.1007/s11538-022-01118-z"}]},"external_id":{"isi":["000812509800001"]},"volume":84,"quality_controlled":"1","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"],"date_created":"2022-06-17T16:16:15Z","publication":"Bulletin of Mathematical Biology","has_accepted_license":"1","language":[{"iso":"eng"}],"department":[{"_id":"GradSch"},{"_id":"NiBa"},{"_id":"JaMa"}],"type":"journal_article","title":"Relation between the number of peaks and the number of reciprocal sign epistatic interactions","publisher":"Springer Nature","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"day":"17","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.","file":[{"relation":"main_file","content_type":"application/pdf","success":1,"file_size":463025,"date_updated":"2022-06-20T07:51:32Z","file_name":"2022_BulletinMathBiology_Saona.pdf","date_created":"2022-06-20T07:51:32Z","file_id":"11455","checksum":"05a1fe7d10914a00c2bca9b447993a65","creator":"dernst","access_level":"open_access"}],"project":[{"call_identifier":"H2020","name":"Characterizing the fitness landscape on population and global scales","grant_number":"771209","_id":"26580278-B435-11E9-9278-68D0E5697425"},{"name":"Evolutionary analysis of gene regulation","_id":"c098eddd-5a5b-11eb-8a69-abe27170a68f","grant_number":"I05127"}],"isi":1,"author":[{"id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","last_name":"Saona Urmeneta","first_name":"Raimundo J","orcid":"0000-0001-5103-038X","full_name":"Saona Urmeneta, Raimundo J"},{"full_name":"Kondrashov, Fyodor","last_name":"Kondrashov","id":"44FDEF62-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8243-4694","first_name":"Fyodor"},{"full_name":"Khudiakova, Kseniia","orcid":"0000-0002-6246-1465","first_name":"Kseniia","id":"4E6DC800-AE37-11E9-AC72-31CAE5697425","last_name":"Khudiakova"}]},{"doi":"10.1287/moor.2020.1116","publication_status":"published","date_published":"2022-02-01T00:00:00Z","oa_version":"Preprint","scopus_import":"1","main_file_link":[{"url":"https://arxiv.org/abs/1904.13360","open_access":"1"}],"intvolume":"        47","citation":{"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>.","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>.","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>","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.","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.","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>","short":"K. Chatterjee, R.J. Saona Urmeneta, B. Ziliotto, Mathematics of Operations Research 47 (2022) 100–119."},"year":"2022","issue":"1","arxiv":1,"abstract":[{"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. ","lang":"eng"}],"date_updated":"2023-09-05T13:16:11Z","_id":"9311","oa":1,"publication_identifier":{"issn":["0364-765X"],"eissn":["1526-5471"]},"status":"public","month":"02","publication":"Mathematics of Operations Research","page":"100-119","date_created":"2021-04-08T09:33:31Z","department":[{"_id":"GradSch"},{"_id":"KrCh"}],"language":[{"iso":"eng"}],"type":"journal_article","article_processing_charge":"No","article_type":"original","keyword":["Management Science and Operations Research","General Mathematics","Computer Science Applications"],"volume":47,"quality_controlled":"1","external_id":{"arxiv":["1904.13360"],"isi":["000731918100001"]},"day":"01","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","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"full_name":"Saona Urmeneta, Raimundo J","last_name":"Saona Urmeneta","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","orcid":"0000-0001-5103-038X","first_name":"Raimundo J"},{"last_name":"Ziliotto","first_name":"Bruno","full_name":"Ziliotto, Bruno"}],"isi":1,"project":[{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","call_identifier":"FWF","name":"Game Theory"}],"title":"Finite-memory strategies in POMDPs with long-run average objectives","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publisher":"Institute for Operations Research and the Management Sciences"},{"citation":{"short":"K. Chatterjee, M. Mohammadi, R.J. Saona Urmeneta, ArXiv (n.d.).","ieee":"K. Chatterjee, M. Mohammadi, and R. J. Saona Urmeneta, “Repeated prophet inequality with near-optimal bounds,” <i>arXiv</i>. .","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>","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>.","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>.","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>","ista":"Chatterjee K, Mohammadi M, Saona Urmeneta RJ. Repeated prophet inequality with near-optimal bounds. arXiv, 2209.14368."},"external_id":{"arxiv":["2209.14368"]},"article_processing_charge":"No","main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2209.14368","open_access":"1"}],"oa_version":"Preprint","type":"preprint","date_published":"2022-09-28T00:00:00Z","department":[{"_id":"GradSch"},{"_id":"KrCh"}],"language":[{"iso":"eng"}],"doi":"10.48550/ARXIV.2209.14368","publication_status":"submitted","publication":"arXiv","date_created":"2023-02-24T12:21:40Z","month":"09","ec_funded":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","oa":1,"title":"Repeated prophet inequality with near-optimal bounds","author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"last_name":"Mohammadi","id":"4363614d-b686-11ed-a7d5-ac9e4a24bc2e","first_name":"Mona","full_name":"Mohammadi, Mona"},{"orcid":"0000-0001-5103-038X","first_name":"Raimundo J","last_name":"Saona Urmeneta","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","full_name":"Saona Urmeneta, Raimundo J"}],"article_number":"2209.14368","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"_id":"12677","arxiv":1,"acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant.","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"}],"date_updated":"2025-07-14T09:09:51Z","year":"2022","day":"28"}]