论文标题
可数MDP中奇偶校目标的策略复杂性
Strategy Complexity of Parity Objectives in Countable MDPs
论文作者
论文摘要
我们研究具有奇偶元目标的无限MDP。与有限的MDP不同，最佳策略不必存在，并且可能需要无限的内存。我们提供了$ \ varepsilon $ - 最佳策略（以及存在的最佳策略）的确切策略复杂性的完整图片。根据颜色的数量，MDP的分支程度，以及是否考虑$ \ varepsilon $ - 最佳的策略或最佳策略，MD策略，马尔可夫策略或1位马尔可夫策略是必要且足够的。特别是，对于$ \ varepsilon $ - 最佳（最佳）策略，1位马尔可夫策略对于一般奇偶校验目标是必要的，足以满足。
We study countably infinite MDPs with parity objectives. Unlike in finite MDPs, optimal strategies need not exist, and may require infinite memory if they do. We provide a complete picture of the exact strategy complexity of $\varepsilon$-optimal strategies (and optimal strategies, where they exist) for all subclasses of parity objectives in the Mostowski hierarchy. Either MD-strategies, Markov strategies, or 1-bit Markov strategies are necessary and sufficient, depending on the number of colors, the branching degree of the MDP, and whether one considers $\varepsilon$-optimal or optimal strategies. In particular, 1-bit Markov strategies are necessary and sufficient for $\varepsilon$-optimal (resp. optimal) strategies for general parity objectives.
