The complexity of synchronizing Markov decision processes
From MaRDI portal
Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Applications of game theory (91A80) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)
Abstract: We consider Markov decision processes (MDP) as generators of sequences of probability distributions over states. A probability distribution is p-synchronizing if the probability mass is at least p in a single state, or in a given set of states. We consider four temporal synchronizing modes: a sequence of probability distributions is always p-synchronizing, eventually p-synchronizing, weakly p-synchronizing, or strongly p-synchronizing if, respectively, all, some, infinitely many, or all but finitely many distributions in the sequence are p-synchronizing. For each synchronizing mode, an MDP can be (i) sure winning if there is a strategy that produces a 1-synchronizing sequence; (ii) almost-sure winning if there is a strategy that produces a sequence that is, for all epsilon > 0, a (1-epsilon)-synchronizing sequence; (iii) limit-sure winning if for all epsilon > 0, there is a strategy that produces a (1-epsilon)-synchronizing sequence. We provide fundamental results on the expressiveness, decidability, and complexity of synchronizing properties for MDPs. For each synchronizing mode, we consider the problem of deciding whether an MDP is sure, almost-sure, or limit-sure winning, and we establish matching upper and lower complexity bounds of the problems: for all winning modes, we show that the problems are PSPACE-complete for eventually and weakly synchronizing, and PTIME-complete for always and strongly synchronizing. We establish the memory requirement for winning strategies, and we show that all winning modes coincide for always synchronizing, and that the almost-sure and limit-sure winning modes coincide for weakly and strongly synchronizing.
Recommendations
Cites work
- scientific article; zbMATH DE number 7228447 (Why is no real title available?)
- scientific article; zbMATH DE number 3545583 (Why is no real title available?)
- scientific article; zbMATH DE number 3555903 (Why is no real title available?)
- scientific article; zbMATH DE number 700091 (Why is no real title available?)
- scientific article; zbMATH DE number 1134975 (Why is no real title available?)
- scientific article; zbMATH DE number 1948170 (Why is no real title available?)
- scientific article; zbMATH DE number 6861928 (Why is no real title available?)
- scientific article; zbMATH DE number 918133 (Why is no real title available?)
- scientific article; zbMATH DE number 3222112 (Why is no real title available?)
- scientific article; zbMATH DE number 3371972 (Why is no real title available?)
- A game-based abstraction-refinement framework for Markov decision processes
- A note on emptiness for alternating finite automata with a one-letter alphabet
- A survey of stochastic \(\omega \)-regular games
- Alternation
- Approximate verification of the symbolic dynamics of Markov chains
- Automata, logics, and infinite games. A guide to current research
- Automata-Theoretic Model Checking Revisited
- Computation tree logic for synchronization properties
- Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
- Concurrent reachability games
- Controlling a population
- Directable nondeterministic automata
- Fast randomized consensus using shared memory
- Infinite Synchronizing Words for Probabilistic Automata
- Mean Field for Markov Decision Processes: From Discrete to Continuous Optimization
- Model checking of probabilistic and nondeterministic systems
- Multi-Objective Model Checking of Markov Decision Processes
- On Computing Fixpoints in Well-Structured Regular Model Checking, with Applications to Lossy Channel Systems
- On emptiness and counting for alternating finite automata
- On the probability of being synchronizable
- On the undecidability of probabilistic planning and related stochastic optimization problems
- Polynomial time decidability of weighted synchronization under partial observability
- Positivity problems for low-order linear recurrence sequences
- Probabilistic Bisimulation: Naturally on Distributions
- Probabilistic automata
- Probabilistic automata on finite words: decidable and undecidable problems
- Probabilistic ω-automata
- Reachability problems for Markov chains
- Sliding Window Abstraction for Infinite Markov Chains
- Synchronizing Automata and the Černý Conjecture
- Synchronizing Data Words for Register Automata
- Synchronizing Sequences for Probabilistic Automata
- Synchronizing automata over nested words
- Synchronizing strategies under partial observability
- Synchronizing weighted automata
- Synchronizing words for weighted and timed automata
- The complexity of probabilistic verification
- Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study
Cited in
(11)- Bounds for synchronizing Markov decision processes
- Markov decision processes with delays and asynchronous cost collection
- Stochastic games with synchronizing objectives
- Synchronizing words under \textsf{LTL} constraints
- Synchronizing automata with coinciding cycles
- MDPs as distribution transformers: affine invariant synthesis for safety objectives
- Limit synchronization in Markov decision processes
- Symblicit algorithms for mean-payoff and shortest path in monotonic Markov decision processes
- Robust Synchronization in Markov Decision Processes
- Some results concerning careful synchronization of partial automata and subset synchronization of DFA's
- Synchronization of Parikh automata
This page was built for publication: The complexity of synchronizing Markov decision processes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1740670)
