Scalable methods for computing state similarity in deterministic Markov Decision Processes
This work addresses scalability issues in reinforcement learning for researchers and practitioners, offering incremental improvements by extending bisimulation metrics to deterministic MDPs with new approximation methods.
The paper tackles the problem of computing bisimulation metrics in Markov Decision Processes (MDPs), which are computationally expensive and impractical for large or continuous state spaces, by introducing new algorithms that approximate these metrics efficiently, including one that enables learning for continuous state MDPs for the first time.
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. We then present two new algorithms for approximating bisimulation metrics in large, deterministic MDPs. The first does so via sampling and is guaranteed to converge to the true metric. The second is a differentiable loss which allows us to learn an approximation even for continuous state MDPs, which prior to this work had not been possible.