---
OA_place: repository
OA_type: green
_id: '21717'
abstract:
- lang: eng
  text: 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 ω-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.
acknowledgement: This work was supported by ERC CoG 863818 (ForMSMArt) and Austrian
  Science Fund (FWF) 10.55776/COE12. We also thank Hossein Zakerinia for his helpful
  feedback.
article_processing_charge: No
arxiv: 1
author:
- first_name: Ali
  full_name: Asadi, Ali
  id: 02d96aae-000e-11ec-b801-cadd0a5eefbb
  last_name: Asadi
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Ehsan
  full_name: Kafshdar Goharshadi, Ehsan
  id: 103b4fa0-896a-11ed-bdf8-87b697bef40d
  last_name: Kafshdar Goharshadi
  orcid: 0000-0002-8595-0587
- first_name: Mehrdad
  full_name: Karrabi, Mehrdad
  id: 67638922-f394-11eb-9cf6-f20423e08757
  last_name: Karrabi
  orcid: 0009-0007-5253-9170
- first_name: Ali
  full_name: Shafiee, Ali
  id: 2783031a-7378-11f0-b2d0-f17f1db2ebad
  last_name: Shafiee
citation:
  ama: 'Asadi A, Chatterjee K, Goharshady E, Karrabi M, Shafiee A. Qualitative analysis
    of ω-regular objectives on robust MDPs. In: <i>Proceedings of the 40th AAAI Conference
    on Artificial Intelligence</i>. Vol 40. Association for the Advancement of Artificial
    Intelligence; 2026:36137-36145. doi:<a href="https://doi.org/10.1609/aaai.v40i43.40931">10.1609/aaai.v40i43.40931</a>'
  apa: 'Asadi, A., Chatterjee, K., Goharshady, E., Karrabi, M., &#38; Shafiee, A.
    (2026). Qualitative analysis of ω-regular objectives on robust MDPs. In <i>Proceedings
    of the 40th AAAI Conference on Artificial Intelligence</i> (Vol. 40, pp. 36137–36145).
    Singapore, Singapore: Association for the Advancement of Artificial Intelligence.
    <a href="https://doi.org/10.1609/aaai.v40i43.40931">https://doi.org/10.1609/aaai.v40i43.40931</a>'
  chicago: Asadi, Ali, Krishnendu Chatterjee, Ehsan Goharshady, Mehrdad Karrabi, and
    Ali Shafiee. “Qualitative Analysis of ω-Regular Objectives on Robust MDPs.” In
    <i>Proceedings of the 40th AAAI Conference on Artificial Intelligence</i>, 40:36137–45.
    Association for the Advancement of Artificial Intelligence, 2026. <a href="https://doi.org/10.1609/aaai.v40i43.40931">https://doi.org/10.1609/aaai.v40i43.40931</a>.
  ieee: A. Asadi, K. Chatterjee, E. Goharshady, M. Karrabi, and A. Shafiee, “Qualitative
    analysis of ω-regular objectives on robust MDPs,” in <i>Proceedings of the 40th
    AAAI Conference on Artificial Intelligence</i>, Singapore, Singapore, 2026, vol.
    40, no. 43, pp. 36137–36145.
  ista: 'Asadi A, Chatterjee K, Goharshady E, Karrabi M, Shafiee A. 2026. Qualitative
    analysis of ω-regular objectives on robust MDPs. Proceedings of the 40th AAAI
    Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence
    vol. 40, 36137–36145.'
  mla: Asadi, Ali, et al. “Qualitative Analysis of ω-Regular Objectives on Robust
    MDPs.” <i>Proceedings of the 40th AAAI Conference on Artificial Intelligence</i>,
    vol. 40, no. 43, Association for the Advancement of Artificial Intelligence, 2026,
    pp. 36137–45, doi:<a href="https://doi.org/10.1609/aaai.v40i43.40931">10.1609/aaai.v40i43.40931</a>.
  short: A. Asadi, K. Chatterjee, E. Goharshady, M. Karrabi, A. Shafiee, in:, Proceedings
    of the 40th AAAI Conference on Artificial Intelligence, Association for the Advancement
    of Artificial Intelligence, 2026, pp. 36137–36145.
conference:
  end_date: 2026-01-27
  location: Singapore, Singapore
  name: 'AAAI: Conference on Artificial Intelligence'
  start_date: 2026-01-20
date_created: 2026-04-12T22:01:50Z
date_published: 2026-03-14T00:00:00Z
date_updated: 2026-05-04T11:38:56Z
day: '14'
department:
- _id: KrCh
- _id: GradSch
doi: 10.1609/aaai.v40i43.40931
ec_funded: 1
external_id:
  arxiv:
  - '2505.04539'
intvolume: '        40'
issue: '43'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2505.04539
month: '03'
oa: 1
oa_version: Preprint
page: 36137-36145
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the 40th AAAI Conference on Artificial Intelligence
publication_identifier:
  eissn:
  - 2374-3468
  issn:
  - 2159-5399
publication_status: published
publisher: Association for the Advancement of Artificial Intelligence
quality_controlled: '1'
scopus_import: '1'
status: public
title: Qualitative analysis of ω-regular objectives on robust MDPs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 40
year: '2026'
...