Finite-State Controllers of POMDPs using Parameter Synthesis

Sebastian Junges, Nils Jansen, Ralf Wimmer, Tim Quatmann, Leonore Winterer, Joost-Pieter Katoen, Bernd Becker
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:518-528, 2018.

Abstract

We study finite-state controllers (FSCs) for partially observable Markov decision processes (POMDPs) that are provably correct with respect to given specifications. The key insight is that computing (randomised) FSCs on POMDPs is equivalent to—and computationally as hard as—synthesis for parametric Markov chains (pMCs). This correspondence allows to use tools for synthesis in pMCs to compute correct-by-construction FSCs on POMDPs for a variety of specifications. Our experimental evaluation shows comparable performance to well-known POMDP solvers.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-junges18a, title = {Finite-State Controllers of POMDPs using Parameter Synthesis}, author = {Junges, Sebastian and Jansen, Nils and Wimmer, Ralf and Quatmann, Tim and Winterer, Leonore and Katoen, Joost-Pieter and Becker, Bernd}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {518--528}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/junges18a/junges18a.pdf}, url = {https://proceedings.mlr.press/r16/junges18a.html}, abstract = {We study finite-state controllers (FSCs) for partially observable Markov decision processes (POMDPs) that are provably correct with respect to given specifications. The key insight is that computing (randomised) FSCs on POMDPs is equivalent to—and computationally as hard as—synthesis for parametric Markov chains (pMCs). This correspondence allows to use tools for synthesis in pMCs to compute correct-by-construction FSCs on POMDPs for a variety of specifications. Our experimental evaluation shows comparable performance to well-known POMDP solvers.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Finite-State Controllers of POMDPs using Parameter Synthesis %A Sebastian Junges %A Nils Jansen %A Ralf Wimmer %A Tim Quatmann %A Leonore Winterer %A Joost-Pieter Katoen %A Bernd Becker %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-junges18a %I PMLR %P 518--528 %U https://proceedings.mlr.press/r16/junges18a.html %V R16 %X We study finite-state controllers (FSCs) for partially observable Markov decision processes (POMDPs) that are provably correct with respect to given specifications. The key insight is that computing (randomised) FSCs on POMDPs is equivalent to—and computationally as hard as—synthesis for parametric Markov chains (pMCs). This correspondence allows to use tools for synthesis in pMCs to compute correct-by-construction FSCs on POMDPs for a variety of specifications. Our experimental evaluation shows comparable performance to well-known POMDP solvers. %Z Reissued by PMLR on 04 October 2026.
APA
Junges, S., Jansen, N., Wimmer, R., Quatmann, T., Winterer, L., Katoen, J. & Becker, B.. (2018). Finite-State Controllers of POMDPs using Parameter Synthesis. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:518-528 Available from https://proceedings.mlr.press/r16/junges18a.html. Reissued by PMLR on 04 October 2026.

Related Material