Earlier Version
Stochastic processes with expected stopping time
Download (ext.)
Conference Paper
| Published
| English
Scopus indexed
Author
Chatterjee, KrishnenduISTA
;
Doyen, Laurent

Department
Abstract
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.
Keywords
Publishing Year
Date Published
2021-07-07
Proceedings Title
Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science
Publisher
Institute of Electrical and Electronics Engineers
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).
Page
1-13
Conference
LICS: Logic in Computer Science
Conference Location
Rome, Italy
Conference Date
2021-06-29 – 2021-07-02
ISBN
ISSN
IST-REx-ID
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level

Export
Marked PublicationsOpen Data ISTA Research Explorer
Web of Science
View record in Web of Science®Sources
arXiv 2104.07278