Search papers, labs, and topics across Lattice.
This paper addresses the quantitative analysis of $(s,a)$-rectangular Robust Markov Decision Processes (RMDPs) with linearly defined uncertainty sets, focusing on parity objectives. The authors develop a polynomial-time algorithm that guarantees the satisfaction probability against adversarial environments and demonstrate that both agents and environments can achieve optimal pure memoryless policies. Experimental results indicate that their approach outperforms traditional methods that reduce the problem to stochastic games, highlighting the efficiency of their algorithm in practical scenarios.
Achieving optimal policies in robust MDPs is possible with a polynomial-time algorithm that guarantees satisfaction against adversarial environments.
Robust Markov Decision Processes (RMDPs) generalize classical MDPs by allowing uncertainty in transition probabilities and optimizing against their worst-case realization. We consider $(s,a)$-rectangular RMDPs with \emph{linearly defined} uncertainty sets and study parity objectives, which are a canonical representation of $\omega$-regular objectives. An uncertainty set is linearly defined if it is described by linear inequalities over the transition distribution together with auxiliary variables, which capture the standard $L_1$ and $L_\infty$ balls as well as general polytopic uncertainty sets. The quantitative value is the supremum, over all agent policies, of the satisfaction probability guaranteed against the adversarial environment. Previous work studied the qualitative analysis, namely the almost-sure (resp. positive) problem that asks whether a single agent policy guarantees satisfaction with probability one (resp. positive probability) against every environment policy. In this work, we solve the exact quantitative problem. Our contributions are threefold. First, we show that both the agent and the environment admit pure memoryless optimal policies. Second, we give a polynomial-time algorithm for quantitative parity on linearly defined robust Markov chains and use it as a subroutine in a policy-iteration algorithm for RMDPs. The algorithm combines quantitative one-step improvements with qualitative almost-sure improvements. Finally, we report experiments comparing our approach with the explicit reduction to stochastic games.
