Qualitative Analysis of $ω$-Regular Objectives on Robust MDPs

2025-05-07 · Ali Asadi, Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Mehrdad Karrabi, Ali Shafiee

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.

📄 PDF Abstract BibTeX arXiv:2505.04539

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

SET Dynamic Sparse Training method where weight mask is updated randomly periodically

Quantitative Analysis of $ω$-Regular Robust MDPs

2026-08-26 · Ali Asadi, Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Mehrdad Karrabi 외 arxiv

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…

Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives

2024-12-16 · Marius Belly, Nathanaël Fijalkow, Hugo Gimbert, Florian Horn 외

Partially observable Markov decision processes (POMDPs) form a prominent model for uncertainty in sequential decision making. We are interested in constructing algorithms with theoretical guarantees to determine whether …

Decision Making Sequential Decision Making

A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPs

2023-10-18 · Mateo Perez, Fabio Somenzi, Ashutosh Trivedi

Linear temporal logic (LTL) and omega-regular objectives -- a superset of LTL -- have seen recent use as a way to express non-Markovian objectives in reinforcement learning. We introduce a model-based probably approximat…

PAC learning reinforcement-learning

Reinforcement Learning for Omega-Regular Specifications on Continuous-Time MDP

2023-03-16 · Amin Falah, Shibashis Guha, Ashutosh Trivedi

Continuous-time Markov decision processes (CTMDPs) are canonical models to express sequential decision-making under dense-time and stochastic environments. When the stochastic evolution of the environment is only availab…

Decision Making reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+2

Optimal Control Synthesis of Markov Decision Processes for Efficiency with Surveillance Tasks

2024-03-27 · Yu Chen, Xuanyuan Yin, ShaoYuan Li, Xiang Yin

We investigate the problem of optimal control synthesis for Markov Decision Processes (MDPs), addressing both qualitative and quantitative objectives. Specifically, we require the system to fulfill a qualitative surveill…

Motion Planning