  This paper studies parametric Markov decision processes (pMDPs), an extension
to Markov decision processes (MDPs) where transitions probabilities are
described by polynomials over a finite set of parameters. Fixing values for all
parameters yields MDPs. In particular, this paper studies the complexity of
finding values for these parameters such that the induced MDP satisfies some
reachability constraints. We discuss different variants depending on the
comparison operator in the constraints and the domain of the parameter values.
We improve all known lower bounds for this problem, and notably provide
ETR-completeness results for distinct variants of this problem. Furthermore, we
provide insights in the functions describing the induced reachability
probabilities, and how pMDPs generalise concurrent stochastic reachability
games.
