A PSPACE algorithm for almost-sure rabin objectives in multi-environment MDPs

DOI10.4230/LIPICS.CONCUR.2024.40MaRDI QIDQ6859905zbMATH OpenFDO

Authors Marnix Suilen, Marck van der Vegt, Sebastian Junges

Publication date 10 February 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.CONCUR.2024.40

zbMATH Keywords

linear-time objectivesMarkov decision processespartial observability

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cites work

• A comprehensive survey on safe reinforcement learning
• A PSPACE algorithm for almost-sure rabin objectives in multi-environment MDPs
• Algorithms for Omega-Regular Games with Imperfect Information
• Automata, Languages and Programming
• Convex Optimization for Parameter Synthesis in MDPs
• Decidable problems for probabilistic automata on infinite words
• Deciding the value 1 problem for probabilistic leaktight automata
• Deciding the value 1 problem for probabilistic leaktight automata
• Enforcing almost-sure reachability in POMDPs
• scientific article; zbMATH DE number 700091 (Why is no real title available?)
• scientific article; zbMATH DE number 5585443 (Why is no real title available?)
• scientific article; zbMATH DE number 7650328 (Why is no real title available?)
• Multiple-environment Markov decision processes
• On Decision Problems for Probabilistic Büchi Automata
• On the Complexity of Reachability in Parametric Markov Decision Processes
• On the power of imperfect information
• Optimal cost almost-sure reachability in POMDPs
• Parameter synthesis in Markov models: a gentle survey
• Parameter-Independent Strategies for pMDPs via POMDPs
• Planning and acting in partially observable stochastic domains
• Probabilistic automata on finite words: decidable and undecidable problems
• Probabilistic ω-automata
• Qualitative analysis of partially-observable Markov decision processes
• Quantitative stochastic parity games
• Robust almost-sure reachability in multi-environment MDPs
• Robust Control of Markov Decision Processes with Uncertain Transition Matrices
• Robust Dynamic Programming
• The Complexity of Markov Decision Processes
• What is decidable about partially observable Markov decision processes with \(\omega\)-regular objectives

Cited in

(1)

• A PSPACE algorithm for almost-sure rabin objectives in multi-environment MDPs

This page was built for publication: A PSPACE algorithm for almost-sure rabin objectives in multi-environment MDPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6859905)