DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2024.40

A PSPACE Algorithm for Almost-Sure Rabin Objectives in Multi-Environment MDPs

Authors: Marnix Suilen, Marck van der Vegt, and Sebastian Junges

Published in: LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024)

Abstract

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.

Cite as

Marnix Suilen, Marck van der Vegt, and Sebastian Junges. A PSPACE Algorithm for Almost-Sure Rabin Objectives in Multi-Environment MDPs. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{suilen_et_al:LIPIcs.CONCUR.2024.40,
  author =	{Suilen, Marnix and van der Vegt, Marck and Junges, Sebastian},
  title =	{{A PSPACE Algorithm for Almost-Sure Rabin Objectives in Multi-Environment MDPs}},
  booktitle =	{35th International Conference on Concurrency Theory (CONCUR 2024)},
  pages =	{40:1--40:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-339-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{311},
  editor =	{Majumdar, Rupak and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2024.40},
  URN =		{urn:nbn:de:0030-drops-208120},
  doi =		{10.4230/LIPIcs.CONCUR.2024.40},
  annote =	{Keywords: Markov Decision Processes, partial observability, linear-time Objectives}
}

Search Results

Documents authored by van der Vegt, Marck

A PSPACE Algorithm for Almost-Sure Rabin Objectives in Multi-Environment MDPs

Abstract

Cite as

Thanks for your feedback!

Could not send message