What is decidable about partially observable Markov decision processes with \(\omega\)-regular objectives

DOI10.1016/j.jcss.2016.02.009zbMath1338.68166arXiv1309.2802OpenAlexW1522308973MaRDI QIDQ269509

Mathieu Tracol, Martin Chmelík, Krishnendu Chatterjee

Publication date: 18 April 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1309.2802

zbMATH Keywords

Markov decision processes\(\omega\)-regular conditionsfinite-memory strategiesparity objectivespartially observable Markov decision processes (POMDPs)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Markov and semi-Markov decision processes (90C40) Specification and verification (program logics, model checking, etc.) (68Q60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Scenario-Based Verification of Uncertain MDPs, Supervisor synthesis of POMDP via automata learning, Efficient sensor placement and online scheduling of bin collection

Uses Software

• Alpaga
• PRISM
• POMDP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of two-player games of incomplete information
• On the undecidability of probabilistic planning and related stochastic optimization problems
• POMDPs under probabilistic semantics
• Model checking of probabilistic and nondeterministic systems
• What is Decidable about Partially Observable Markov Decision Processes with omega-Regular Objectives.
• Randomness for Free
• Qualitative Analysis of Partially-Observable Markov Decision Processes
• Probabilistic Automata on Finite Words: Decidable and Undecidable Problems
• Algorithms for Omega-Regular Games with Imperfect Information
• The Complexity of Markov Decision Processes
• Biological Sequence Analysis
• The complexity of probabilistic verification
• Probabilistic Automata on Infinite Words: Decidability and Undecidability Results
• Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study
• Games with a Weak Adversary
• Probabilistic ω-automata
• Active Diagnosis for Probabilistic Systems
• The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies
• Markov Decision Processes with Multiple Objectives
• On Decision Problems for Probabilistic Büchi Automata
• Markov Decision Processes with Multiple Long-Run Average Objectives
• Probabilistic automata