Metraipolis › archive › dc_ecf7fd6de977

The Complexity of Approximating the Value in Revealing POMDPs with Long-Run Average Objectives — arXiv:2609.01099

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.01099
License (as archived)
CC0-1.0
Archived
2026-10-17T07:03:28.141Z
SHA-256 of the archived text
5b3a565542ea7425fa1d6e8fc4ca6bd37f0757327783a14f51ff591e5b511751
Stable URL of this page
https://metraipolis.com/documento/dc_ecf7fd6de977

How to cite

The Complexity of Approximating the Value in Revealing POMDPs with Long-Run Average Objectives — arXiv:2609.01099 — arXiv (en), https://arxiv.org/abs/2609.01099 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ecf7fd6de977 (Metraipolis archive dc_ecf7fd6de977, sha256 5b3a565542ea7425fa1d6e8fc4ca6bd37f0757327783a14f51ff591e5b511751)
BibTeX
@misc{dcecf7fd6de977,
  title = {The Complexity of Approximating the Value in Revealing POMDPs with Long-Run Average Objectives — arXiv:2609.01099},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.01099},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ecf7fd6de977; sha256 5b3a565542ea7425fa1d6e8fc4ca6bd37f0757327783a14f51ff591e5b511751},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.01099. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-02 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.01099 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T06:49:55.530Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).