2026-07-25T16:21:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20812 2024-08-29T05:40:58Z ddc:004 open_access

A PSPACE Algorithm for Almost-Sure Rabin Objectives in Multi-Environment MDPs Suilen, Marnix van der Vegt, Marck Junges, Sebastian Markov Decision Processes partial observability linear-time Objectives Markov Decision Processes (MDPs) model systems with uncertain transition dynamics. Multiple-environment MDPs (MEMDPs) extend MDPs. They intuitively reflect finite sets of MDPs that share the same state and action spaces but differ in the transition dynamics. The key objective in MEMDPs is to find a single strategy that satisfies a given objective in every associated MDP. The main result of this paper is PSPACE-completeness for almost-sure Rabin objectives in MEMDPs. This result clarifies the complexity landscape for MEMDPs and contrasts with results for the more general class of partially observable MDPs (POMDPs), where almost-sure reachability is already EXP-complete, and almost-sure Rabin objectives are undecidable. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marnix Suilen and Marck van der Vegt and Sebastian Junges 2024 Is Part Of LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2024.40 urn:nbn:de:0030-drops-208120 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2024.40 eng https://creativecommons.org/licenses/by/4.0/legalcode