Scalable methods for computing state similarity in deterministic Markov Decision Processes

Understand

We present new algorithms for computing and approximating bisimulation metrics in Markov Decision Processes (MDPs).

• Bisimulation metrics are an elegant formalism that capture behavioral equivalence between states and provide strong theoretical guarantees on differences in optimal behaviour.
• Unfortunately, their computation is expensive and requires a tabular representation of the states, which has thus far rendered them impractical for large problems.
• In this paper we present a new version of the metric that is tied to a behavior policy in an MDP, along with an analysis of its theoretical properties.