---
_id: '9311'
abstract:
- lang: eng
  text: 'Partially observable Markov decision processes (POMDPs) are standard models
    for dynamic systems with probabilistic and nondeterministic behaviour in uncertain
    environments. We prove that in POMDPs with long-run average objective, the decision
    maker has approximately optimal strategies with finite memory. This implies notably
    that approximating the long-run value is recursively enumerable, as well as a
    weak continuity property of the value with respect to the transition function. '
acknowledgement: "Partially supported by Austrian Science Fund (FWF) NFN Grant No
  RiSE/SHiNE S11407, by CONICYT Chile through grant PII 20150140, and by ECOS-CONICYT
  through grant C15E03.\r\n"
article_processing_charge: No
article_type: original
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: 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: Bruno
  full_name: Ziliotto, Bruno
  last_name: Ziliotto
citation:
  ama: Chatterjee K, Saona Urmeneta RJ, Ziliotto B. Finite-memory strategies in POMDPs
    with long-run average objectives. <i>Mathematics of Operations Research</i>. 2022;47(1):100-119.
    doi:<a href="https://doi.org/10.1287/moor.2020.1116">10.1287/moor.2020.1116</a>
  apa: Chatterjee, K., Saona Urmeneta, R. J., &#38; Ziliotto, B. (2022). Finite-memory
    strategies in POMDPs with long-run average objectives. <i>Mathematics of Operations
    Research</i>. Institute for Operations Research and the Management Sciences. <a
    href="https://doi.org/10.1287/moor.2020.1116">https://doi.org/10.1287/moor.2020.1116</a>
  chicago: Chatterjee, Krishnendu, Raimundo J Saona Urmeneta, and Bruno Ziliotto.
    “Finite-Memory Strategies in POMDPs with Long-Run Average Objectives.” <i>Mathematics
    of Operations Research</i>. Institute for Operations Research and the Management
    Sciences, 2022. <a href="https://doi.org/10.1287/moor.2020.1116">https://doi.org/10.1287/moor.2020.1116</a>.
  ieee: K. Chatterjee, R. J. Saona Urmeneta, and B. Ziliotto, “Finite-memory strategies
    in POMDPs with long-run average objectives,” <i>Mathematics of Operations Research</i>,
    vol. 47, no. 1. Institute for Operations Research and the Management Sciences,
    pp. 100–119, 2022.
  ista: Chatterjee K, Saona Urmeneta RJ, Ziliotto B. 2022. Finite-memory strategies
    in POMDPs with long-run average objectives. Mathematics of Operations Research.
    47(1), 100–119.
  mla: Chatterjee, Krishnendu, et al. “Finite-Memory Strategies in POMDPs with Long-Run
    Average Objectives.” <i>Mathematics of Operations Research</i>, vol. 47, no. 1,
    Institute for Operations Research and the Management Sciences, 2022, pp. 100–19,
    doi:<a href="https://doi.org/10.1287/moor.2020.1116">10.1287/moor.2020.1116</a>.
  short: K. Chatterjee, R.J. Saona Urmeneta, B. Ziliotto, Mathematics of Operations
    Research 47 (2022) 100–119.
date_created: 2021-04-08T09:33:31Z
date_published: 2022-02-01T00:00:00Z
date_updated: 2023-09-05T13:16:11Z
day: '01'
department:
- _id: GradSch
- _id: KrCh
doi: 10.1287/moor.2020.1116
external_id:
  arxiv:
  - '1904.13360'
  isi:
  - '000731918100001'
intvolume: '        47'
isi: 1
issue: '1'
keyword:
- Management Science and Operations Research
- General Mathematics
- Computer Science Applications
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1904.13360
month: '02'
oa: 1
oa_version: Preprint
page: 100-119
project:
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
publication: Mathematics of Operations Research
publication_identifier:
  eissn:
  - 1526-5471
  issn:
  - 0364-765X
publication_status: published
publisher: Institute for Operations Research and the Management Sciences
quality_controlled: '1'
scopus_import: '1'
status: public
title: Finite-memory strategies in POMDPs with long-run average objectives
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 47
year: '2022'
...