Title




The complexity of graphbased reductions for reachability in Markov decision processes


Author






Abstract




We study the neverworse relation (NWR) for Markov decision processes with an infinitehorizon 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, regardless of the probabilities labelling the transitions. Extremalprobability 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 suboptimal states can be removed. We show that the natural decision problem associated to computing the NWR is coNPcomplete. Finally, we extend a previously known incomplete polynomialtime iterative algorithm to underapproximate the NWR. 


Language




English


Source (journal)




Lecture notes in computer science.  Berlin, 1973, currens


Source (book)




21st International Conference, FOSSACS 2018, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2018, April 1420, 2018, Thessaloniki, Greece / Baier, Christel [edit.]; et al.


Source (series)




Theoretical computer science and general issues (LNTCS) ; 10803


Publication




Cham
:
Springer
,
2018


ISBN




9783319893655
9783319893662


Volume/pages




10803
(2018)
, p. 367383


Full text (Publisher's DOI)






Full text (open access)





