---
_id: '1820'
abstract:
- lang: eng
  text: '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.'
acknowledgement: ' The research was partly supported by Austrian Science Fund (FWF)
  Grant No P23499-N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307:
  Graph Games), and Microsoft faculty fellows award.'
alternative_title:
- Artifical Intelligence
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Martin
  full_name: Chmelik, Martin
  id: 3624234E-F248-11E8-B48F-1D18A9856A87
  last_name: Chmelik
- first_name: Raghav
  full_name: Gupta, Raghav
  last_name: Gupta
- first_name: Ayush
  full_name: Kanodia, Ayush
  last_name: Kanodia
citation:
  ama: 'Chatterjee K, Chmelik M, Gupta R, Kanodia A. Optimal cost almost-sure reachability
    in POMDPs. In: <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial
    Intelligence </i>. Vol 5. AAAI Press; 2015:3496-3502.'
  apa: 'Chatterjee, K., Chmelik, M., Gupta, R., &#38; Kanodia, A. (2015). Optimal
    cost almost-sure reachability in POMDPs. In <i>Proceedings of the Twenty-Ninth
    AAAI Conference on Artificial Intelligence </i> (Vol. 5, pp. 3496–3502). Austin,
    TX, USA: AAAI Press.'
  chicago: Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia.
    “Optimal Cost Almost-Sure Reachability in POMDPs.” In <i>Proceedings of the Twenty-Ninth
    AAAI Conference on Artificial Intelligence </i>, 5:3496–3502. AAAI Press, 2015.
  ieee: K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, “Optimal cost almost-sure
    reachability in POMDPs,” in <i>Proceedings of the Twenty-Ninth AAAI Conference
    on Artificial Intelligence </i>, Austin, TX, USA, 2015, vol. 5, pp. 3496–3502.
  ista: 'Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2015. Optimal cost almost-sure
    reachability in POMDPs. Proceedings of the Twenty-Ninth AAAI Conference on Artificial
    Intelligence . IAAI: Innovative Applications of Artificial Intelligence, Artifical
    Intelligence, vol. 5, 3496–3502.'
  mla: Chatterjee, Krishnendu, et al. “Optimal Cost Almost-Sure Reachability in POMDPs.”
    <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence
    </i>, vol. 5, AAAI Press, 2015, pp. 3496–502.
  short: K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, in:, Proceedings of the
    Twenty-Ninth AAAI Conference on Artificial Intelligence , AAAI Press, 2015, pp.
    3496–3502.
conference:
  end_date: 2015-01-30
  location: Austin, TX, USA
  name: 'IAAI: Innovative Applications of Artificial Intelligence'
  start_date: 2015-01-25
corr_author: '1'
date_created: 2018-12-11T11:54:11Z
date_published: 2015-06-01T00:00:00Z
date_updated: 2025-09-18T11:05:08Z
day: '01'
department:
- _id: KrCh
ec_funded: 1
external_id:
  arxiv:
  - '1411.3880'
  isi:
  - '000372683700002'
intvolume: '         5'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1411.3880
month: '06'
oa: 1
oa_version: Preprint
page: 3496-3502
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P 23499-N23
  name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
publication: 'Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence '
publication_status: published
publisher: AAAI Press
publist_id: '5286'
quality_controlled: '1'
related_material:
  record:
  - id: '1529'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Optimal cost almost-sure reachability in POMDPs
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 5
year: '2015'
...