Best Paper Award at CONCUR'24

04-Dec-2024

The paper “A PSPACE Algorithm for Almost-Sure Rabin-Objectives in Multi-Environment MDPs” by Marnix Suilen, Marck van der Vegt, Sebastian Junges has won the best paper award at CONCUR 2024.

What is the paper about?

Markov decision processes (MDPs) are an easy and elegant algorithm to describe sequential decision making, but the world is partially observable, and thus one should model systems with partially observable MDPs (POMDPs). However, reasoning on POMDPs is intractable and many simple decision problems on POMDPs are already undecidable. Among them are decision problems relating to Rabin objectives, which are important if one wants to verify POMDPs against linear temporal logic specifications. Luckily, there is room between MDPs and POMDPs, e.g., in terms of multi-environment MDPs. Multi-environment MDPs (MEMDPs) describe the situation where there is a fixed set of possible scenarios in which one must act, but one does not know which of these scenarios is the true one. Think minesweeper or freecell. In this paper, Marnix Suilen, Marck van der Vegt, and Sebastian Junges demonstrate that it is reasonably tractable to decide whether MEMDPs satisfy Rabin Objectives.