[{"isi":1,"title":"Stochastic processes with expected stopping time","_id":"10004","status":"public","abstract":[{"lang":"eng","text":"Markov chains are the de facto finite-state model for stochastic dynamical systems, and Markov decision processes (MDPs) extend Markov chains by incorporating non-deterministic behaviors. Given an MDP and rewards on states, a classical optimization criterion is the maximal expected total reward where the MDP stops after T steps, which can be computed by a simple dynamic programming algorithm. We consider a natural generalization of the problem where the stopping times can be chosen according to a probability distribution, such that the expected stopping time is T, to optimize the expected total reward. Quite surprisingly we establish inter-reducibility of the expected stopping-time problem for Markov chains with the Positivity problem (which is related to the well-known Skolem problem), for which establishing either decidability or undecidability would be a major breakthrough. Given the hardness of the exact problem, we consider the approximate version of the problem: we show that it can be solved in exponential time for Markov chains and in exponential space for MDPs."}],"oa":1,"date_created":"2021-09-12T22:01:25Z","oa_version":"Preprint","scopus_import":"1","date_updated":"2026-08-12T06:39:27Z","conference":{"start_date":"2021-06-29","location":"Rome, Italy","name":"LICS: Logic in Computer Science","end_date":"2021-07-02"},"project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020"}],"year":"2021","publication_status":"published","page":"1-13","type":"conference","external_id":{"arxiv":["2104.07278"],"isi":["000947350400036"]},"doi":"10.1109/LICS52264.2021.9470595","publication_identifier":{"eisbn":["978-1-6654-4895-6"],"isbn":["978-1-6654-4896-3"],"issn":["1043-6871"]},"quality_controlled":"1","month":"07","author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"first_name":"Laurent","last_name":"Doyen","full_name":"Doyen, Laurent"}],"ec_funded":1,"related_material":{"record":[{"id":"18630","status":"public","relation":"later_version"}]},"acknowledgement":"We are grateful to the anonymous reviewers of LICS 2021 and of a previous version of this paper for insightful comments that helped improving the presentation. This research was partially supported by the grant ERC CoG 863818 (ForM-SMArt).","department":[{"_id":"KrCh"}],"publication":"Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"arxiv":1,"keyword":["Computer science","Heuristic algorithms","Memory management","Automata","Markov processes","Probability distribution","Complexity theory"],"publisher":"IEEE","citation":{"short":"K. Chatterjee, L. Doyen, in:, Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2021, pp. 1–13.","ista":"Chatterjee K, Doyen L. 2021. Stochastic processes with expected stopping time. Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 1–13.","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Stochastic Processes with Expected Stopping Time.” In <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, 1–13. IEEE, 2021. <a href=\"https://doi.org/10.1109/LICS52264.2021.9470595\">https://doi.org/10.1109/LICS52264.2021.9470595</a>.","ieee":"K. Chatterjee and L. Doyen, “Stochastic processes with expected stopping time,” in <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Rome, Italy, 2021, pp. 1–13.","ama":"Chatterjee K, Doyen L. Stochastic processes with expected stopping time. In: <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. IEEE; 2021:1-13. doi:<a href=\"https://doi.org/10.1109/LICS52264.2021.9470595\">10.1109/LICS52264.2021.9470595</a>","apa":"Chatterjee, K., &#38; Doyen, L. (2021). Stochastic processes with expected stopping time. In <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i> (pp. 1–13). Rome, Italy: IEEE. <a href=\"https://doi.org/10.1109/LICS52264.2021.9470595\">https://doi.org/10.1109/LICS52264.2021.9470595</a>","mla":"Chatterjee, Krishnendu, and Laurent Doyen. “Stochastic Processes with Expected Stopping Time.” <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, IEEE, 2021, pp. 1–13, doi:<a href=\"https://doi.org/10.1109/LICS52264.2021.9470595\">10.1109/LICS52264.2021.9470595</a>."},"date_published":"2021-07-07T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/2104.07278","open_access":"1"}],"day":"07","article_processing_charge":"No"}]