Abstract
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.
Introduction
In Reinforcement Learning (RL), identifying behavioral equivalence between states is a powerful tool for generalization. If an agent recognizes that distinct observations lead to identical future outcomes, it can learn more efficiently. Bisimulation metrics provide a formal framework for this by defining a distance between states based on rewards and transition dynamics. However, traditional bisimulation metrics suffer from high computational costs—requiring tabular representations—and excessive pessimism, as they consider the worst-case across all possible actions.
Methods
To overcome these limitations, we propose three primary innovations:
- On-policy Bisimulation: We define a metric relative to a specific policy $\pi$, focusing on the transitions and rewards relevant to actual agent behavior rather than theoretical worst-case scenarios.
- Deterministic Simplification: In deterministic environments, the Wasserstein distance used in the metric calculation simplifies to the distance between unique next states, significantly reducing complexity.
- Differentiable Neural Network Loss: We formulate a loss function that enables neural networks to learn an approximation of the bisimulation metric, $\psi_\theta(s, t)$. This allows the metric to scale to continuous state spaces and generalize to unseen states.
Experimental Evaluation
We evaluated our methods on a 31-state discrete GridWorld, a continuous GridWorld with coordinate noise, and several Atari 2600 games (Space Invaders, Pong, Asterix) under deterministic conditions.
Key Results
Our sampling-based algorithm is theoretically guaranteed to converge to the true bisimulation metric. In practice, the neural network approximation closely tracks the exact metric in GridWorld environments. Notably, in continuous GridWorld experiments, adding noise to state representations appeared to act as a regularizer, improving the learning of the metric.
In Atari games, the learned metric captures semantic game events. For instance, in Space Invaders, the distance between states increases significantly during critical events like losing a life or destroying an enemy, demonstrating that the network learns behavioral features directly from raw pixels.
Conclusion and Future Work
By leveraging determinism and neural approximations, we have made bisimulation metrics applicable to complex, high-dimensional environments. While current methods rely on deterministic transitions, future research will focus on extending these efficiencies to stochastic systems. Additionally, integrating these learned metrics as auxiliary tasks could further enhance RL agent exploration and representation learning.
Summary updated