Stochastic Bisimulation for MDPs Using Reachability Analysis

This paper presents how to improve model reduction, a technique that receives an MDP and returns a stochastic bisimulation, which is an equivalence relation represented as a partition of the MDP set of states. In this work, we use the initial state information to do a reachability analysis before the stochastic bisimulation computation. This combination enables to compute a model reduction over the reachable states from a given initial state and then solve a smaller MDP problem. We show that with such reduction we can have exact solutions of larger MDP problems of domains with sparse transition function.