The Complexity of Graph-Based Reductions for Reachability in Markov Decision Processes

Stephane Le Roux, Guillermo A. Perez

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 probab…