论文标题
同步马尔可夫决策过程的范围
Bounds for Synchronizing Markov Decision Processes
论文作者
论文摘要
我们认为马尔可夫决策过程具有同步目标，这些过程要求$1-ε$的概率质量累积在指定的目标状态集中，无论是一次，始终，无限，无限的频率，或从某个点上开始，其中$ε= 0 $确定同步，而$ε\ to $ε\ to $ε\至0 $，用于几乎是纯净和限制的同步。 我们介绍了两种新的定性同步模式，其中概率质量应为正，或者从$ 0 $限制。它们可以看作是双重同步目标。 我们提出了决定马尔可夫决策过程是正面还是有界同步的问题，我们提出了算法和严格的复杂性结果，并且我们在所有同步模式中都提供了$ε$的明确界限。特别是，我们表明，从某个点上始终确定正面和有限的同步是综合的。
We consider Markov decision processes with synchronizing objectives, which require that a probability mass of $1-ε$ accumulates in a designated set of target states, either once, always, infinitely often, or always from some point on, where $ε= 0$ for sure synchronizing, and $ε\to 0$ for almost-sure and limit-sure synchronizing. We introduce two new qualitative modes of synchronizing, where the probability mass should be either positive, or bounded away from $0$. They can be viewed as dual synchronizing objectives. We present algorithms and tight complexity results for the problem of deciding if a Markov decision process is positive, or bounded synchronizing, and we provide explicit bounds on $ε$ in all synchronizing modes. In particular, we show that deciding positive and bounded synchronizing always from some point on, is coNP-complete.
