Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives (Extended Abstract)

Belly, Marius; Fijalkow, Nathanaël; Gimbert, Hugo; Horn, Florian; Perez, Guillermo A.; Vandenhove, Pierre

doi:10.24963/ijcai.2026/916

Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives (Extended Abstract)

Marius Belly, Nathanaël Fijalkow, Hugo Gimbert, Florian Horn, Guillermo A. Perez, Pierre Vandenhove

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Sister Conferences Best Papers. Pages 8221-8226.

https://doi.org/10.24963/ijcai.2026/916

Keywords

Planning and Scheduling: POMDPs
Agent-based and Multi-agent Systems: Formal verification, validation and synthesis

Abstract

Partially observable Markov decision processes (POMDPs) form a prominent model for uncertainty in sequential decision making. We are interested in constructing algorithms with theoretical guarantees to determine whether the agent has a strategy ensuring a given specification with probability 1. This well-studied problem is known to be undecidable already for very simple omega-regular objectives, because of the difficulty of reasoning on uncertain events.

We introduce a revelation mechanism which restricts information loss by requiring that, almost surely, the agent has eventually full information about the current state. Our main technical results are to construct exact algorithms for two classes of POMDPs called weakly and strongly revealing. Importantly, the decidable cases reduce to the analysis of a finite belief-support Markov decision process. This yields a conceptually simple and exact algorithm for a large class of POMDPs.

Marius Belly, Nathanaël Fijalkow, Hugo Gimbert, Florian Horn, Guillermo A. Perez, and Pierre Vandenhove. 2026. Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives (Extended Abstract). In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 8221–8226. https://doi.org/10.24963/ijcai.2026/916

@inproceedings{ijcai2026p916,
  title     = {Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives (Extended Abstract)},
  author    = {Belly, Marius and Fijalkow, Nathanaël and Gimbert, Hugo and Horn, Florian and Perez, Guillermo A. and Vandenhove, Pierre},
  booktitle = {Proceedings of the Thirty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-26}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Diego Calvanese},
  pages     = {8221--8226},
  year      = {2026},
  month     = {8},
  note      = {Sister Conferences Best Papers},
  doi       = {10.24963/ijcai.2026/916},
  url       = {https://doi.org/10.24963/ijcai.2026/916},
}

TY  - CPAPER
TI  - Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives (Extended Abstract)
AU  - Belly, Marius
AU  - Fijalkow, Nathanaël
AU  - Gimbert, Hugo
AU  - Horn, Florian
AU  - Perez, Guillermo A.
AU  - Vandenhove, Pierre
T2  - Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2026
SP  - 8221
EP  - 8226
DO  - 10.24963/ijcai.2026/916
UR  - https://doi.org/10.24963/ijcai.2026/916
ER  -