Finite-Memory Strategies in POMDPs with Long-Run Average Objectives
- 1 February 2022
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 47 (1) , 100-119
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.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Probabilistic ω-automataJournal of the ACM, 2012
- Uniform value in dynamic programmingJournal of the European Mathematical Society, 2010
- Concurrent games with tail objectivesTheoretical Computer Science, 2007
- On the undecidability of probabilistic planning and related stochastic optimization problemsArtificial Intelligence, 2003
- Blackwell optimality in Markov decision processes with partial observationThe Annals of Statistics, 2002
- On measurability and representation of strategic measures in Markov decision processes1996
- Discrete-Time Controlled Markov Processes with Average Cost Criterion: A SurveySIAM Journal on Control and Optimization, 1993
- Probabilistic automataJournal of Mathematical Sciences, 1980
- Probabilistic automataInformation and Control, 1963
- Discrete Dynamic ProgrammingThe Annals of Mathematical Statistics, 1962