We study observation-based strategies for partially-observable Markov
decision processes (POMDPs) with omega-regular objectives. An observation-based
strategy relies on partial information about the history of a play, namely, on
the past sequence of observations. We consider the qualitative analysis
problem: given a POMDP with an omega-regular objective, whether there is an
observation-based strategy to achieve the objective with probability~1
(almost-sure winning), or with positive probability (positive winning). Our
main results are twofold. First, we present a complete picture of the
computational complexity of the qualitative analysis of POMDP s with parity
objectives (a canonical form to express omega-regular objectives) and its
subclasses. Our contribution consists in establishing several upper and lower
bounds that were not known in literature. Second, we present optimal bounds
(matching upper and lower bounds) on the memory required by pure and randomized
observation-based strategies for the qualitative analysis of POMDP s with
parity objectives and its subclasses.

本文针对部分可观察 Markov 决策过程（POMDPs）和 ω 正则目标，研究了基于观测的策略，并解决了定性分析问题的计算复杂度和最优内存界限。

部分可观察马尔可夫决策过程的定性分析

Qualitative Analysis of Partially-observable Markov Decision Processes

We study observation-based strategies for two-player turn-based games on
graphs with omega-regular objectives. An observation-based strategy relies on
imperfect information about the history of a play, namely, on the past sequence
of observations. Such games occur in the synthesis of a controller that does
not see the private state of the plant. Our main results are twofold. First, we
give a fixed-point algorithm for computing the set of states from which a
player can win with a deterministic observation-based strategy for any
omega-regular objective. The fixed point is computed in the lattice of
antichains of state sets. This algorithm has the advantages of being directed
by the objective and of avoiding an explicit subset construction on the game
graph. Second, we give an algorithm for computing the set of states from which
a player can win with probability 1 with a randomized observation-based
strategy for a Buechi objective. This set is of interest because in the absence
of perfect information, randomized strategies are more powerful than
deterministic ones. We show that our algorithms are optimal by proving matching
lower bounds.

本文研究了基于观察的策略在具有 ω- 正则目标的图上的两人回合制游戏中的应用。我们提出了计算状态集合的固定点算法，解决了玩家使用确定性和随机化观察策略进行游戏的问题。