<?xml version="1.0" encoding="UTF-8"?>

<modsCollection xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://www.loc.gov/mods/v3" xsi:schemaLocation="http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-3.xsd">
<mods version="3.3">

<genre>conference paper</genre>

<titleInfo><title>Limit-sure reachability for small memory policies in POMDPs is NP-complete</title></titleInfo>

  
  
<titleInfo type="alternative">
  
  <title>PMLR</title>
</titleInfo>

<note type="publicationStatus">published</note>


<note type="qualityControlled">yes</note>

<name type="personal">
  <namePart type="given">Ali</namePart>
  <namePart type="family">Asadi</namePart>
  <role><roleTerm type="text">author</roleTerm> </role><identifier type="local">02d96aae-000e-11ec-b801-cadd0a5eefbb</identifier></name>
<name type="personal">
  <namePart type="given">Krishnendu</namePart>
  <namePart type="family">Chatterjee</namePart>
  <role><roleTerm type="text">author</roleTerm> </role><identifier type="local">2E5DCA20-F248-11E8-B48F-1D18A9856A87</identifier><description xsi:type="identifierDefinition" type="orcid">0000-0002-4561-241X</description></name>
<name type="personal">
  <namePart type="given">Raimundo J</namePart>
  <namePart type="family">Saona Urmeneta</namePart>
  <role><roleTerm type="text">author</roleTerm> </role><identifier type="local">BD1DF4C4-D767-11E9-B658-BC13E6697425</identifier><description xsi:type="identifierDefinition" type="orcid">0000-0001-5103-038X</description></name>
<name type="personal">
  <namePart type="given">Ali</namePart>
  <namePart type="family">Shafiee</namePart>
  <role><roleTerm type="text">author</roleTerm> </role><identifier type="local">2783031a-7378-11f0-b2d0-f17f1db2ebad</identifier></name>







<name type="corporate">
  <namePart></namePart>
  <identifier type="local">KrCh</identifier>
  <role>
    <roleTerm type="text">department</roleTerm>
  </role>
</name>

<name type="corporate">
  <namePart></namePart>
  <identifier type="local">GradSch</identifier>
  <role>
    <roleTerm type="text">department</roleTerm>
  </role>
</name>



<name type="conference">
  <namePart>UAI: Conference on Uncertainty in Artificial Intelligence</namePart>
</name>



<name type="corporate">
  <namePart>Formal Methods for Stochastic Models: Algorithms and Applications</namePart>
  <role><roleTerm type="text">project</roleTerm></role>
</name>
<name type="corporate">
  <namePart>Bilateral Artificial Intelligence (Chatterjee)</namePart>
  <role><roleTerm type="text">project</roleTerm></role>
</name>



<abstract lang="eng">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.

The 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.</abstract>

<relatedItem type="constituent">
  <location>
    <url displayLabel="2025_UAI_AsadiAli.pdf">https://research-explorer.ista.ac.at/download/20297/20315/2025_UAI_AsadiAli.pdf</url>
  </location>
  <physicalDescription><internetMediaType>application/pdf</internetMediaType></physicalDescription><accessCondition type="restrictionOnAccess">no</accessCondition>
</relatedItem>
<originInfo><publisher>ML Research Press</publisher><dateIssued encoding="w3cdtf">2025</dateIssued><place><placeTerm type="text">Rio de Janeiro, Brazil</placeTerm></place>
</originInfo>
<language><languageTerm authority="iso639-2b" type="code">eng</languageTerm>
</language>



<relatedItem type="host"><titleInfo><title>The 41st Conference on Uncertainty in Artificial Intelligence</title></titleInfo>
  <identifier type="eIssn">2640-3498</identifier>
  <identifier type="arXiv">2412.00941</identifier>
<part><detail type="volume"><number>286</number></detail><extent unit="pages">238-247</extent>
</part>
</relatedItem>


<extension>
<bibliographicCitation>
<mla>Asadi, Ali, et al. “Limit-Sure Reachability for Small Memory Policies in POMDPs Is NP-Complete.” &lt;i&gt;The 41st Conference on Uncertainty in Artificial Intelligence&lt;/i&gt;, vol. 286, ML Research Press, 2025, pp. 238–47.</mla>
<apa>Asadi, A., Chatterjee, K., Saona Urmeneta, R. J., &amp;#38; Shafiee, A. (2025). Limit-sure reachability for small memory policies in POMDPs is NP-complete. In &lt;i&gt;The 41st Conference on Uncertainty in Artificial Intelligence&lt;/i&gt; (Vol. 286, pp. 238–247). Rio de Janeiro, Brazil: ML Research Press.</apa>
<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 &lt;i&gt;The 41st Conference on Uncertainty in Artificial Intelligence&lt;/i&gt;, 286:238–47. ML Research Press, 2025.</chicago>
<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.</short>
<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.</ista>
<ama>Asadi A, Chatterjee K, Saona Urmeneta RJ, Shafiee A. Limit-sure reachability for small memory policies in POMDPs is NP-complete. In: &lt;i&gt;The 41st Conference on Uncertainty in Artificial Intelligence&lt;/i&gt;. Vol 286. ML Research Press; 2025:238-247.</ama>
<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 &lt;i&gt;The 41st Conference on Uncertainty in Artificial Intelligence&lt;/i&gt;, Rio de Janeiro, Brazil, 2025, vol. 286, pp. 238–247.</ieee>
</bibliographicCitation>
</extension>
<recordInfo><recordIdentifier>20297</recordIdentifier><recordCreationDate encoding="w3cdtf">2025-09-07T22:01:34Z</recordCreationDate><recordChangeDate encoding="w3cdtf">2026-09-16T07:03:02Z</recordChangeDate>
</recordInfo>
</mods>
</modsCollection>
