New Method Speeds Up Bisimulation Metrics for MDPs

This research presents a novel technique to accelerate the computation of bisimulation metrics, which are crucial for quantifying behavioral similarity in Markov Decision Processes (MDPs). Traditionally, these calculations involve a quadratic amount of work for every state pair. The new method leverages approximate nearest neighbor (ANN) indexing to selectively update only relevant state pairs, drastically cutting down the computational overhead. The core innovation lies in using an ANN index to identify which pairs need updating by a restricted operator, while simultaneously employing monotone lower and upper bounds to enclose the exact metric. The paper provides a coverage-augmented anytime bound, demonstrating that while local index quality is important, global error is also influenced by uncovered pairs. The algorithm returns an observable "sandwich width" to certify the exact recovery of covered aggregations.