Krishnendu Chatterjee ; Laurent Doyen - Stochastic Processes with Expected Stopping Time

lmcs:9700 - Logical Methods in Computer Science, November 12, 2024, Volume 20, Issue 4 - https://doi.org/10.46298/lmcs-20(4:11)2024
Stochastic Processes with Expected Stopping TimeArticle

Authors: Krishnendu Chatterjee ; Laurent Doyen

    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.


    Volume: Volume 20, Issue 4
    Published on: November 12, 2024
    Accepted on: September 3, 2024
    Submitted on: June 14, 2022
    Keywords: Computer Science - Logic in Computer Science

    Consultation statistics

    This page has been seen 431 times.
    This article's PDF has been downloaded 251 times.