论文标题
参数马尔可夫决策过程中可及性的复杂性
The Complexity of Reachability in Parametric Markov Decision Processes
论文作者
论文摘要
本文介绍了参数马尔可夫决策过程（PMDP）的可及性决策问题的复杂性，这是马尔可夫决策过程（MDPS）的扩展，其中多项式对有限的参数介绍了过渡概率。特别是，我们研究了找到这些参数值的复杂性，以便诱导的MDP满足某些最大或最小的可及性概率约束。我们讨论了不同的变体，具体取决于参数值的约束和域中的比较运算符。我们改善了此问题的所有已知下限，并尤其为该问题的不同变体提供了ETR完整性结果。
This article presents the complexity of reachability decision problems for 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. In particular, we study the complexity of finding values for these parameters such that the induced MDP satisfies some maximal or minimal reachability probability 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.
