---
res:
  bibo_abstract:
  - 'We consider partially observable Markov decision processes (POMDPs) with a set
    of target states and every transition is associated with an integer cost. The
    optimization objec- tive we study asks to minimize the expected total cost till
    the target set is reached, while ensuring that the target set is reached almost-surely
    (with probability 1). We show that for integer costs approximating the optimal
    cost is undecidable. For positive costs, our results are as follows: (i) we establish
    matching lower and upper bounds for the optimal cost and the bound is double exponential;
    (ii) we show that the problem of approximating the optimal cost is decidable and
    present ap- proximation algorithms developing on the existing algorithms for POMDPs
    with finite-horizon objectives. While the worst- case running time of our algorithm
    is double exponential, we present efficient stopping criteria for the algorithm
    and show experimentally that it performs well in many examples.@eng'
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Krishnendu
      foaf_name: Chatterjee, Krishnendu
      foaf_surname: Chatterjee
      foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-4561-241X
  - foaf_Person:
      foaf_givenName: Martin
      foaf_name: Chmelik, Martin
      foaf_surname: Chmelik
      foaf_workInfoHomepage: http://www.librecat.org/personId=3624234E-F248-11E8-B48F-1D18A9856A87
  - foaf_Person:
      foaf_givenName: Raghav
      foaf_name: Gupta, Raghav
      foaf_surname: Gupta
  - foaf_Person:
      foaf_givenName: Ayush
      foaf_name: Kanodia, Ayush
      foaf_surname: Kanodia
  bibo_volume: 5
  dct_date: 2015^xs_gYear
  dct_identifier:
  - UT:000372683700002
  dct_language: eng
  dct_publisher: AAAI Press@
  dct_title: Optimal cost almost-sure reachability in POMDPs@
...