The complexity of graph-based reductions for reachability in Markov decision processes

DOI10.1007/978-3-319-89366-2_20MaRDI QIDQ1652999zbMATH OpenOpenAlexFDO

Authors Stéphane Le Roux, G. A. Pérez

Publication date 17 July 2018

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Markov and semi-Markov decision processes (90C40)

Abstract: We study the never-worse relation (NWR) for Markov decision processes with an infinite-horizon reachability objective. A state q is never worse than a state p if the maximal probability of reaching the target set of states from p is at most the same value from q, regard- less of the probabilities labelling the transitions. Extremal-probability states, end components, and essential states are all special cases of the equivalence relation induced by the NWR. Using the NWR, states in the same equivalence class can be collapsed. Then, actions leading to sub- optimal states can be removed. We show the natural decision problem associated to computing the NWR is coNP-complete. Finally, we ex- tend a previously known incomplete polynomial-time iterative algorithm to under-approximate the NWR.

Recommendations

• Reachability in MDPs: refining convergence of value iteration
• Reachability problems for Markov chains
• Reachability in recursive Markov decision processes
• scientific article; zbMATH DE number 1786649
• Equivalence notions and model minimization in Markov decision processes

Cited in

(2)

• The state reduction and related algorithms and their applications to the study of Markov chains, graph theory, and the optimal stopping problem
• Are parametric Markov chains monotonic?

This page was built for publication: The complexity of graph-based reductions for reachability in Markov decision processes

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