Methods for computing state similarity in Markov decision processes
Norm Ferns, Pablo Samuel Castro, Doina Precup, Prakash Panangaden · 2006
A popular approach to solving large probabilis-tic systems relies on aggregating states based on a measure of similarity. Many approaches in the literature are heuristic. A number of recent methods rely instead on metrics based on the no-tion of bisimulation, or behavioral equivalence between states (Givan et al., 2003; Ferns et al., 2004). An integral component of such metrics is the Kantorovich metric between probability dis-tributions. However, while this metric enables many satisfying theoretical properties, it is costly to compute in practice. In this paper, we use tech-niques from network optimization and statistical sampling to overcome this problem. We obtain in this manner a variety of distance functions for MDP state aggregation that differ in the trade-off between time and space complexity, as well as the quality of the aggregation. We provide an empirical evaluation of these tradeoffs. 1