  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.
