[{"oa":1,"article_processing_charge":"No","isi":1,"publication":"Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence ","fulldoi":"https://doi.org/10.1609/aaai.v29i1.9683","main_file_link":[{"url":"http://arxiv.org/abs/1411.3880","open_access":"1"}],"scopus_import":"1","month":"06","day":"01","publist_id":"5286","department":[{"_id":"KrCh"}],"publication_status":"published","abstract":[{"text":"We consider partially observable Markov decision processes (POMDPs) with a set of target states and every transition is associated with an integer cost. The optimization objec- tive we study asks to minimize the expected total cost till the target set is reached, while ensuring that the target set is reached almost-surely (with probability 1). We show that for integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost and the bound is double exponential; (ii) we show that the problem of approximating the optimal cost is decidable and present ap- proximation algorithms developing on the existing algorithms for POMDPs with finite-horizon objectives. While the worst- case running time of our algorithm is double exponential, we present efficient stopping criteria for the algorithm and show experimentally that it performs well in many examples.","lang":"eng"}],"type":"conference","arxiv":1,"_id":"1820","author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin","last_name":"Chmelik","first_name":"Martin"},{"full_name":"Gupta, Raghav","last_name":"Gupta","first_name":"Raghav"},{"full_name":"Kanodia, Ayush","first_name":"Ayush","last_name":"Kanodia"}],"acknowledgement":" The research was partly supported by Austrian Science Fund (FWF) Grant No P23499-N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"3496-3502","volume":5,"citation":{"ieee":"K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, “Optimal cost almost-sure reachability in POMDPs,” in <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence </i>, Austin, TX, USA, 2015, vol. 5, pp. 3496–3502.","mla":"Chatterjee, Krishnendu, et al. “Optimal Cost Almost-Sure Reachability in POMDPs.” <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence </i>, vol. 5, AAAI Press, 2015, pp. 3496–502, doi:<a href=\"https://doi.org/10.1609/aaai.v29i1.9683\">10.1609/aaai.v29i1.9683</a>.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. “Optimal Cost Almost-Sure Reachability in POMDPs.” In <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence </i>, 5:3496–3502. AAAI Press, 2015. <a href=\"https://doi.org/10.1609/aaai.v29i1.9683\">https://doi.org/10.1609/aaai.v29i1.9683</a>.","short":"K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, in:, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence , AAAI Press, 2015, pp. 3496–3502.","apa":"Chatterjee, K., Chmelik, M., Gupta, R., &#38; Kanodia, A. (2015). Optimal cost almost-sure reachability in POMDPs. In <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence </i> (Vol. 5, pp. 3496–3502). Austin, TX, USA: AAAI Press. <a href=\"https://doi.org/10.1609/aaai.v29i1.9683\">https://doi.org/10.1609/aaai.v29i1.9683</a>","ama":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. Optimal cost almost-sure reachability in POMDPs. In: <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence </i>. Vol 5. AAAI Press; 2015:3496-3502. doi:<a href=\"https://doi.org/10.1609/aaai.v29i1.9683\">10.1609/aaai.v29i1.9683</a>","ista":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2015. Optimal cost almost-sure reachability in POMDPs. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence . IAAI: Innovative Applications of Artificial Intelligence, Artifical Intelligence, vol. 5, 3496–3502."},"alternative_title":["Artifical Intelligence"],"intvolume":"         5","year":"2015","ec_funded":1,"status":"public","quality_controlled":"1","language":[{"iso":"eng"}],"publisher":"AAAI Press","conference":{"name":"IAAI: Innovative Applications of Artificial Intelligence","end_date":"2015-01-30","start_date":"2015-01-25","location":"Austin, TX, USA"},"related_material":{"record":[{"status":"public","id":"1529","relation":"later_version"}]},"doi":"10.1609/aaai.v29i1.9683","date_published":"2015-06-01T00:00:00Z","corr_author":"1","external_id":{"arxiv":["1411.3880"],"isi":["000372683700002"]},"title":"Optimal cost almost-sure reachability in POMDPs","date_updated":"2026-08-19T09:31:47Z","oa_version":"Preprint","date_created":"2018-12-11T11:54:11Z","project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"}]},{"article_number":"e1002299","oa":1,"file":[{"file_id":"4723","file_name":"IST-2016-468-v1+1_journal.pbio.1002299.pdf","relation":"main_file","date_created":"2018-12-12T10:09:00Z","content_type":"application/pdf","access_level":"open_access","date_updated":"2020-07-14T12:45:07Z","file_size":1387760,"checksum":"0e82e3279f50b15c6c170c042627802b","creator":"system"}],"file_date_updated":"2020-07-14T12:45:07Z","isi":1,"publication":"PLoS Biology","article_processing_charge":"No","fulldoi":"https://doi.org/10.1371/journal.pbio.1002299","scopus_import":"1","publist_id":"5547","has_accepted_license":"1","day":"18","month":"11","issue":"11","department":[{"_id":"ToBo"}],"publication_status":"published","abstract":[{"lang":"eng","text":"The emergence of drug resistant pathogens is a serious public health problem. It is a long-standing goal to predict rates of resistance evolution and design optimal treatment strategies accordingly. To this end, it is crucial to reveal the underlying causes of drug-specific differences in the evolutionary dynamics leading to resistance. However, it remains largely unknown why the rates of resistance evolution via spontaneous mutations and the diversity of mutational paths vary substantially between drugs. Here we comprehensively quantify the distribution of fitness effects (DFE) of mutations, a key determinant of evolutionary dynamics, in the presence of eight antibiotics representing the main modes of action. Using precise high-throughput fitness measurements for genome-wide Escherichia coli gene deletion strains, we find that the width of the DFE varies dramatically between antibiotics and, contrary to conventional wisdom, for some drugs the DFE width is lower than in the absence of stress. We show that this previously underappreciated divergence in DFE width among antibiotics is largely caused by their distinct drug-specific dose-response characteristics. Unlike the DFE, the magnitude of the changes in tolerated drug concentration resulting from genome-wide mutations is similar for most drugs but exceptionally small for the antibiotic nitrofurantoin, i.e., mutations generally have considerably smaller resistance effects for nitrofurantoin than for other drugs. A population genetics model predicts that resistance evolution for drugs with this property is severely limited and confined to reproducible mutational paths. We tested this prediction in laboratory evolution experiments using the “morbidostat”, a device for evolving bacteria in well-controlled drug environments. Nitrofurantoin resistance indeed evolved extremely slowly via reproducible mutations—an almost paradoxical behavior since this drug causes DNA damage and increases the mutation rate. Overall, we identified novel quantitative characteristics of the evolutionary landscape that provide the conceptual foundation for predicting the dynamics of drug resistance evolution."}],"type":"journal_article","_id":"1619","pubrep_id":"468","author":[{"full_name":"Chevereau, Guillaume","id":"424D78A0-F248-11E8-B48F-1D18A9856A87","last_name":"Chevereau","first_name":"Guillaume"},{"full_name":"Dravecka, Marta","id":"4342E402-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2519-8004","last_name":"Dravecka","first_name":"Marta"},{"full_name":"Batur, Tugce","last_name":"Batur","first_name":"Tugce"},{"full_name":"Guvenek, Aysegul","first_name":"Aysegul","last_name":"Guvenek"},{"full_name":"Ayhan, Dilay","first_name":"Dilay","last_name":"Ayhan"},{"last_name":"Toprak","first_name":"Erdal","full_name":"Toprak, Erdal"},{"orcid":"0000-0003-4398-476X","full_name":"Bollenbach, Mark Tobias","id":"3E6DB97A-F248-11E8-B48F-1D18A9856A87","first_name":"Mark Tobias","last_name":"Bollenbach"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","volume":13,"citation":{"ama":"Chevereau G, Lukacisinova M, Batur T, et al. Quantifying the determinants of evolutionary dynamics leading to drug resistance. <i>PLoS Biology</i>. 2015;13(11). doi:<a href=\"https://doi.org/10.1371/journal.pbio.1002299\">10.1371/journal.pbio.1002299</a>","apa":"Chevereau, G., Lukacisinova, M., Batur, T., Guvenek, A., Ayhan, D., Toprak, E., &#38; Bollenbach, M. T. (2015). Quantifying the determinants of evolutionary dynamics leading to drug resistance. <i>PLoS Biology</i>. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pbio.1002299\">https://doi.org/10.1371/journal.pbio.1002299</a>","short":"G. Chevereau, M. Lukacisinova, T. Batur, A. Guvenek, D. Ayhan, E. Toprak, M.T. Bollenbach, PLoS Biology 13 (2015).","chicago":"Chevereau, Guillaume, Marta Lukacisinova, Tugce Batur, Aysegul Guvenek, Dilay Ayhan, Erdal Toprak, and Mark Tobias Bollenbach. “Quantifying the Determinants of Evolutionary Dynamics Leading to Drug Resistance.” <i>PLoS Biology</i>. Public Library of Science, 2015. <a href=\"https://doi.org/10.1371/journal.pbio.1002299\">https://doi.org/10.1371/journal.pbio.1002299</a>.","mla":"Chevereau, Guillaume, et al. “Quantifying the Determinants of Evolutionary Dynamics Leading to Drug Resistance.” <i>PLoS Biology</i>, vol. 13, no. 11, e1002299, Public Library of Science, 2015, doi:<a href=\"https://doi.org/10.1371/journal.pbio.1002299\">10.1371/journal.pbio.1002299</a>.","ieee":"G. Chevereau <i>et al.</i>, “Quantifying the determinants of evolutionary dynamics leading to drug resistance,” <i>PLoS Biology</i>, vol. 13, no. 11. Public Library of Science, 2015.","ista":"Chevereau G, Lukacisinova M, Batur T, Guvenek A, Ayhan D, Toprak E, Bollenbach MT. 2015. Quantifying the determinants of evolutionary dynamics leading to drug resistance. PLoS Biology. 13(11), e1002299."},"intvolume":"        13","year":"2015","quality_controlled":"1","status":"public","ec_funded":1,"publisher":"Public Library of Science","language":[{"iso":"eng"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"related_material":{"record":[{"id":"9711","relation":"research_data","status":"public"},{"id":"9765","relation":"research_data","status":"public"},{"status":"public","relation":"dissertation_contains","id":"6263"}]},"date_published":"2015-11-18T00:00:00Z","doi":"10.1371/journal.pbio.1002299","external_id":{"isi":["000365898900011"]},"corr_author":"1","title":"Quantifying the determinants of evolutionary dynamics leading to drug resistance","ddc":["570"],"date_updated":"2026-11-04T23:30:54Z","project":[{"grant_number":"RGP0042/2013","name":"Revealing the fundamental limits of cell growth","_id":"25EB3A80-B435-11E9-9278-68D0E5697425"},{"_id":"25E9AF9E-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Revealing the mechanisms underlying drug interactions","grant_number":"P27201-B22"},{"name":"Optimality principles in responses to antibiotics","_id":"25E83C2C-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"303507"}],"date_created":"2018-12-11T11:53:04Z","oa_version":"Published Version"}]