Publication Details
Search and Explore: Symbiotic Policy Synthesis in POMDPs
Alexander Bork (RWTH)
Češka Milan, doc. RNDr., Ph.D. (DITS FIT BUT)
Junges Sebastian (RWTH Aachen University)
Katoen Joost-Pieter (RWTH)
Macák Filip, Ing. (DITS FIT BUT)
partially observable Markov decision processes, finite-state controllers, beliefs, inductive synthesis
This paper marries two state-of-the-art controller synthesis methods for partially observable Markov decision processes (POMDPs), a prominent model in sequential decision making under uncertainty. A central issue is to find a POMDP controller - that solely decides based on the observations seen so far - to achieve a total expected reward objective. As finding optimal controllers is undecidable, we concentrate on synthesising good finite-state controllers (FSCs). We do so by tightly integrating two modern, orthogonal methods for POMDP controller synthesis: a belief-based and an inductive approach. The former method obtains an FSC from a finite fragment of the so-called belief MDP, an MDP that keeps track of the probabilities of equally observable POMDP states. The latter is an inductive search technique over a set of FSCs, e.g., controllers with a fixed memory size. The key result of this paper is a symbiotic anytime algorithm that tightly integrates both approaches such that each profits from the controllers constructed by the other. Experimental results indicate a substantial improvement in the value of the controllers while significantly reducing the synthesis time and memory footprint.
@INPROCEEDINGS{FITPUB13041,
author = "Roman Andriushchenko and Bork Alexander and Milan \v{C}e\v{s}ka and Sebastian Junges and Joost-Pieter Katoen and Filip Mac\'{a}k",
title = "Search and Explore: Symbiotic Policy Synthesis in POMDPs",
pages = "113--135",
booktitle = "Computer Aided Verification",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
volume = 13966,
year = 2023,
location = "Cham, DE",
publisher = "Springer Verlag",
ISBN = "978-3-031-37708-2",
doi = "10.1007/978-3-031-37709-9\_6",
language = "english",
url = "https://www.fit.vut.cz/research/publication/13041"
}