• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

The Complexity of POMDPs with Long-run Average Objectives

Chatterjee, Krishnendu; Saona, Raimundo; Ziliotto, Bruno (2022), The Complexity of POMDPs with Long-run Average Objectives, Mathematics of Operations Research, 47, 1, p. 100-119. 10.1287/moor.2020.1116

View/Open
ziliotto.pdf (187.3Kb)
Type
Article accepté pour publication ou publié
Date
2022
Journal name
Mathematics of Operations Research
Volume
47
Number
1
Publisher
INFORMS - Institute for Operations Research and the Management Sciences
Published in
Paris
Pages
100-119
Publication identifier
10.1287/moor.2020.1116
Metadata
Show full item record
Author(s)
Chatterjee, Krishnendu
Saona, Raimundo
Ziliotto, Bruno
Abstract (EN)
We study the problem of approximation of optimal values in partially-observable Markov decision processes (POMDPs) with long-run average objectives. POMDPs are a standard model for dynamic systems with probabilistic and nondeterministic behavior in uncertain environments. In long-run average objectives rewards are associated with every transition of the POMDP and the payoff is the long-run average of the rewards along the executions of the POMDP. We establish strategy complexity and computational complexity results. Our main result shows that finite-memory strategies suffice for approximation of optimal values, and the related decision problem is recursively enumerable complete.
Subjects / Keywords
POMDPs; dynamic systems

Related items

Showing items related by title and author.

  • Thumbnail
    Finite-Memory Strategies in POMDPs with Long-Run Average Objectives 
    Chatterjee, Krishnendu; Saona, Raimundo; Ziliotto, Bruno (2022) Article accepté pour publication ou publié
  • Thumbnail
    Prophet Secretary Through Blind Strategies 
    Correa, José; Saona, Raimundo; Ziliotto, Bruno (2019) Communication / Conférence
  • Thumbnail
    Benefit in the wake of disaster: Long-run effects of earthquakes on welfare in rural Indonesia 
    Gignoux, Jérémie; Menéndez, Marta (2016) Article accepté pour publication ou publié
  • Thumbnail
    Critical periods and the long-run effects of income shocks on education: evidence from Indonesia 
    Menéndez, Marta; Gignoux, Jérémie (2012-02) Communication / Conférence
  • Thumbnail
    Les effets macroéconomiques des politiques de transition énergétique sur le long terme en France (horizon 2035) 
    Corbier, Darius (2021-06-18)
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo