Show simple item record

dc.contributor.authorChatterjee, Krishnendu
dc.contributor.authorSaona, Raimundo
dc.contributor.authorZiliotto, Bruno
dc.date.accessioned2020-04-24T10:25:42Z
dc.date.available2020-04-24T10:25:42Z
dc.date.issued2022
dc.identifier.issn0364-765X
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20659
dc.language.isoenen
dc.subjectPOMDPs
dc.subjectdynamic systems
dc.subject.ddc515en
dc.titleThe Complexity of POMDPs with Long-run Average Objectives
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe 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.
dc.publisher.cityParisen
dc.relation.isversionofjnlnameMathematics of Operations Research
dc.relation.isversionofjnlvol47
dc.relation.isversionofjnlissue1
dc.relation.isversionofjnldate2022
dc.relation.isversionofjnlpages100-119
dc.relation.isversionofdoi10.1287/moor.2020.1116
dc.relation.isversionofjnlpublisherINFORMS - Institute for Operations Research and the Management Sciences
dc.subject.ddclabelAnalyseen
dc.description.ssrncandidatenon
dc.description.halcandidatenon
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2023-01-20T14:38:14Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record