The Complexity of POMDPs with Long-run Average Objectives.
Krishnendu Chatterjee, Raimundo Saona, Bruno Ziliotto · Base Institutionnelle de Recherche de l'université Paris-Dauphine (BIRD) (University Paris-Dauphine) · 2019
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.