
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
Type
Article accepté pour publication ou publiéDate
2022Journal name
Mathematics of Operations ResearchVolume
47Number
1Publisher
INFORMS - Institute for Operations Research and the Management Sciences
Published in
Paris
Pages
100-119
Publication identifier
Metadata
Show full item recordAbstract (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 systemsRelated items
Showing items related by title and author.
-
Chatterjee, Krishnendu; Saona, Raimundo; Ziliotto, Bruno (2022) Article accepté pour publication ou publié
-
Correa, José; Saona, Raimundo; Ziliotto, Bruno (2019) Communication / Conférence
-
Gignoux, Jérémie; Menéndez, Marta (2016) Article accepté pour publication ou publié
-
Menéndez, Marta; Gignoux, Jérémie (2012-02) Communication / Conférence
-
Corbier, Darius (2021-06-18)