---
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'
...
---
OA_place: publisher
OA_type: diamond
_id: '20297'
abstract:
- lang: eng
  text: "A standard model that arises in several applications in sequential decision-making
    is partially observable Markov decision processes (POMDPs) where a decision-making
    agent interacts with an uncertain environment. A basic objective in POMDPs is
    the reachability objective, where given a target set of states, the goal is to
    eventually arrive at one of them.\r\n\r\nThe limit-sure problem asks whether reachability
    can be ensured with probability arbitrarily close to 1. In general, the limit-sure
    reachability problem for POMDPs is undecidable. However, in many practical cases,
    the most relevant question is the existence of policies with a small amount of
    memory. In this work, we study the limit-sure reachability problem for POMDPs
    with a fixed amount of memory. We establish that the computational complexity
    of the problem is NP-complete."
acknowledgement: This research was partially supported by Austrian Science Fund (FWF)
  10.55776/COE12, the support of the French Agence Nationale de la Recherche (ANR)
  under reference ANR-21-CE40-0020 (CONVERGENCE project), and the ERC CoG 863818 (ForM-SMArt)
  grant.
alternative_title:
- PMLR
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: Raimundo J
  full_name: Saona Urmeneta, Raimundo J
  id: BD1DF4C4-D767-11E9-B658-BC13E6697425
  last_name: Saona Urmeneta
  orcid: 0000-0001-5103-038X
- first_name: Ali
  full_name: Shafiee, Ali
  id: 2783031a-7378-11f0-b2d0-f17f1db2ebad
  last_name: Shafiee
citation:
  ama: 'Asadi A, Chatterjee K, Saona Urmeneta RJ, Shafiee A. Limit-sure reachability
    for small memory policies in POMDPs is NP-complete. In: <i>The 41st Conference
    on Uncertainty in Artificial Intelligence</i>. Vol 286. ML Research Press; 2025:238-247.'
  apa: 'Asadi, A., Chatterjee, K., Saona Urmeneta, R. J., &#38; Shafiee, A. (2025).
    Limit-sure reachability for small memory policies in POMDPs is NP-complete. In
    <i>The 41st Conference on Uncertainty in Artificial Intelligence</i> (Vol. 286,
    pp. 238–247). Rio de Janeiro, Brazil: ML Research Press.'
  chicago: Asadi, Ali, Krishnendu Chatterjee, Raimundo J Saona Urmeneta, and Ali Shafiee.
    “Limit-Sure Reachability for Small Memory Policies in POMDPs Is NP-Complete.”
    In <i>The 41st Conference on Uncertainty in Artificial Intelligence</i>, 286:238–47.
    ML Research Press, 2025.
  ieee: A. Asadi, K. Chatterjee, R. J. Saona Urmeneta, and A. Shafiee, “Limit-sure
    reachability for small memory policies in POMDPs is NP-complete,” in <i>The 41st
    Conference on Uncertainty in Artificial Intelligence</i>, Rio de Janeiro, Brazil,
    2025, vol. 286, pp. 238–247.
  ista: 'Asadi A, Chatterjee K, Saona Urmeneta RJ, Shafiee A. 2025. Limit-sure reachability
    for small memory policies in POMDPs is NP-complete. The 41st Conference on Uncertainty
    in Artificial Intelligence. UAI: Conference on Uncertainty in Artificial Intelligence,
    PMLR, vol. 286, 238–247.'
  mla: Asadi, Ali, et al. “Limit-Sure Reachability for Small Memory Policies in POMDPs
    Is NP-Complete.” <i>The 41st Conference on Uncertainty in Artificial Intelligence</i>,
    vol. 286, ML Research Press, 2025, pp. 238–47.
  short: A. Asadi, K. Chatterjee, R.J. Saona Urmeneta, A. Shafiee, in:, The 41st Conference
    on Uncertainty in Artificial Intelligence, ML Research Press, 2025, pp. 238–247.
conference:
  end_date: 2025-07-25
  location: Rio de Janeiro, Brazil
  name: 'UAI: Conference on Uncertainty in Artificial Intelligence'
  start_date: 2025-07-21
corr_author: '1'
date_created: 2025-09-07T22:01:34Z
date_published: 2025-07-01T00:00:00Z
date_updated: 2025-09-09T08:21:45Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
- _id: GradSch
ec_funded: 1
external_id:
  arxiv:
  - '2412.00941'
file:
- access_level: open_access
  checksum: 1a37ebe7ba73ab6985765bf0d17a0acc
  content_type: application/pdf
  creator: dernst
  date_created: 2025-09-09T08:19:41Z
  date_updated: 2025-09-09T08:19:41Z
  file_id: '20315'
  file_name: 2025_UAI_AsadiAli.pdf
  file_size: 307458
  relation: main_file
  success: 1
file_date_updated: 2025-09-09T08:19:41Z
has_accepted_license: '1'
intvolume: '       286'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '07'
oa: 1
oa_version: Published Version
page: 238-247
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: The 41st Conference on Uncertainty in Artificial Intelligence
publication_identifier:
  eissn:
  - 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Limit-sure reachability for small memory policies in POMDPs is NP-complete
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 286
year: '2025'
...