The Complexity of Approximating the Value in Revealing POMDPs with Long-Run Average Objectives
Abstract
We study partially observable Markov decision processes (POMDPs) with long-run average objectives, where the payoff is defined as the limit inferior of the expected average rewards. We consider the computational problem of approximating the long-run average value of a POMDP. In general, the long-run average value of a POMDP is neither computable nor approximable. We therefore consider the subclass of revealing POMDPs. Informally, a POMDP is revealing when the controller observes the underlying state with positive probability at each stage of the process. Our main contributions are threefold. First, we illustrate the practical relevance of this class of POMDPs through an application in control and optimization. Second, we present an exponential-time algorithm for the value approximation problem. Third, we establish EXPTIME-hardness by a reduction from the problem of almost-sure safety in POMDPs. Together, these results show that the problem of approximating the long-run average value in revealing POMDPs is EXPTIME-complete.
Related
- Tight Heavy-Tailed Complexity Bounds for Optimizing Polyak--Łojasiewicz Objectives
- Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs
- Finite-Memory Control of POMDPs: Fundamental Limits and Efficient Design
- Approximating Distributions on Vertex Degrees in Random Hypergraphs via Stein's Method
- On the intractability of approximating the antiferromagnetic Ising model
BibTeX
@misc{asadi2026complexity,
title = {{The Complexity of Approximating the Value in Revealing POMDPs with Long-Run Average Objectives}},
author = {Ali Asadi and Krishnendu Chatterjee and David Lurie},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.01099},
eprint = {2609.01099},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.01099},
}
RIS
TY - UNPB
TI - The Complexity of Approximating the Value in Revealing POMDPs with Long-Run Average Objectives
AU - Ali Asadi
AU - Krishnendu Chatterjee
AU - David Lurie
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.01099
UR - https://arxiv.org/abs/2609.01099
AB - We study partially observable Markov decision processes (POMDPs) with long-run average objectives, where the payoff is defined as the limit inferior of the expected average rewards. We consider the computational problem of approximating the long-run average value of a POMDP. In general, the long-run average value of a POMDP is neither computable nor approximable. We therefore consider the subclass of revealing POMDPs. Informally, a POMDP is revealing when the controller observes the underlying state with positive probability at each stage of the process. Our main contributions are threefold. First, we illustrate the practical relevance of this class of POMDPs through an application in control and optimization. Second, we present an exponential-time algorithm for the value approximation problem. Third, we establish EXPTIME-hardness by a reduction from the problem of almost-sure safety in POMDPs. Together, these results show that the problem of approximating the long-run average value in revealing POMDPs is EXPTIME-complete.
ER -