A popular approach to solving large probabilistic 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 notion of bisimulation, or behavioral equivalence between states
(Givan et al, 2001, 2003; Ferns et al, 2004). An integral component of such
metrics is the Kantorovich metric between probability distributions. However,
while this metric enables many satisfying theoretical properties, it is costly
to compute in practice. In this paper, we use techniques from network
optimization and statistical sampling to overcome this problem. We obtain in
this manner a variety of distance functions for MDP state aggregation, which
differ in the tradeoff between time and space complexity, as well as the
quality of the aggregation. We provide an empirical evaluation of these
trade-offs.

本文运用网络优化和统计抽样技术，克服了计算 Kantorovich 度量在实践中的成本问题，提出了一系列用于 MDP 状态聚合的距离函数，这些函数在时间和空间复杂度以及聚合质量之间存在不同的权衡，并对这些权衡进行了实证评估。