Finite-Memory Strategies in POMDPs with Long-Run Average Objectives
Published Online:6 Apr 2021https://doi.org/10.1287/moor.2020.1116
Abstract
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.
