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) 


  
