Robust Markov Decision Processes (RMDPs) generalize classical MDPs that consider uncertainties in transition probabilities by defining a set of possible transition functions. An objective is a set of runs (or infinite trajectories) of the RMDP, and the value for an objective is the maximal probability that the agent can guarantee against the adversarial environment. We consider (a) reachability objectives, where given a target set of states, the goal is to eventually arrive at one of them; and (b) parity objectives, which are a canonical representation for $\omega$-regular objectives. The qualitative analysis problem asks whether the objective can be ensured with probability 1. In this work, we study the qualitative problem for reachability and parity objectives on RMDPs without making any assumption over the structures of the RMDPs, e.g., unichain or aperiodic. Our contributions are twofold. We first present efficient algorithms with oracle access to uncertainty sets that solve qualitative problems of reachability and parity objectives. We then report experimental results demonstrating the effectiveness of our oracle-based approach on classical RMDP examples from the literature scaling up to thousands of states.

本研究解决了鲁棒马尔可夫决策过程（RMDPs）中定性分析目标的问题，特别是在考虑不确定转移概率的情况下。通过提出高效的算法并进行实验验证，我们展示了针对可达性和奇偶性目标的定性问题可以在没有假设RMDPs结构的条件下得到有效解决。研究表明，所提出的基于oracle的方法在经典RMDP实例中表现出良好的效果，甚至在数千状态的情况下亦然。

鲁棒马尔可夫决策过程中的$ω$-正则目标的定性分析