We study the complexity of reductions for weighted reachability in parametric
Markov decision processes. That is, we say a state p is never worse than q if
for all valuations of the polynomial indeterminates it is the case that the
maximal expected weight that can be reached from p is greater than the same
value from q. In terms of computational complexity, we establish that
determining whether p is never worse than q is coETR-complete. On the positive
side, we give a polynomial-time algorithm to compute the equivalence classes of
the order we study for Markov chains. Additionally, we describe and implement
two inference rules to under-approximate the never-worse relation and
empirically show that it can be used as an efficient preprocessing step for the
analysis of large Markov decision processes.

本文章研究了参数化马尔可夫决策过程中、权重可达性问题的缩减复杂度。该问题的计算复杂度为 coETR-complete，但是我们在此研究中提出了一种多项式时间算法，可以计算马尔可夫链的 order 等价类，并且描述和实现了两个推断规则，用于近似评估该问题，并且证实此方法可以作为大型马尔可夫决策过程分析的有效预处理步骤。