Scalable Methods for Computing State Similarity in Deterministic Markov Decision Processes

Pablo Samuel Castro

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), determining the similarity between states is crucial for generalization and abstraction. Traditional methods often rely on superficial features like pixel distance, which fail to capture behavioral similarity. For instance, two visually distinct game screens might require identical action sequences to achieve a goal.

Bisimulation metrics represent the theoretical "gold standard" for behavioral similarity, defining states as similar if they yield identical rewards and transition to similar future states. However, their adoption has been limited by three major hurdles:

  1. Computational Complexity: Traditional calculations scale at $O(|A||S|^4)$, making them intractable for large state spaces.
  2. Tabular Constraints: They historically required a fixed table of all states, precluding use in continuous environments.
  3. Pessimism: Standard metrics consider all possible actions, even those irrelevant to an agent's actual policy.

Proposed Methods

To address these limitations, we introduce three key innovations designed to scale bisimulation metrics to modern RL challenges.

1. On-Policy Bisimulation ($\pi$-bisimulation)

We shift the focus from all possible actions to those taken under a specific policy $\pi$. This "on-policy" view ensures that states are considered similar if they behave identically under the agent's current strategy, making the metric more practical for tasks like policy transfer.

2. Sampling-based Computation

We propose an online algorithm that updates distance estimates using sampled transitions $(s, a, r, s')$. This avoids the need to iterate over the entire state-action space and is mathematically guaranteed to converge to the true metric.

3. Differentiable Bisimulation Loss

For continuous state spaces, we define a differentiable loss function that enables a neural network to learn the bisimulation metric. The network processes state representations and outputs a scalar distance. To stabilize training, we employ a "target network" architecture and a stability parameter $\beta$.

Neural network architecture for learning bisimulation metrics between state representations.

Experimental Evaluation

We evaluated our methods across several environments:

  • GridWorld (31-state & Continuous): Used to compare learned metrics against exact ground-truth values. In the continuous variant, Gaussian noise was added to test the network's robustness.
  • Atari 2600: We applied the metric to Space Invaders, Pong, and Asterix using internal representations from a pre-trained Rainbow RL agent.

Key Results

Our experiments demonstrate that the sampling-based approach successfully converges to the true bisimulation metric. In GridWorld tasks, the neural network achieved remarkably low absolute and normalized error rates.

Absolute and normalized metric errors over training steps in the GridWorld environment.

Qualitatively, the metric showed a deep "semantic understanding" of complex environments. In Space Invaders, it correctly identified that states where a life is lost are significantly distant from starting states, even when the background pixels are nearly identical—a distinction pixel-based metrics often miss.

Conclusion and Future Work

By introducing on-policy definitions and differentiable losses, we have made bisimulation metrics viable for large-scale and continuous MDPs. While our current neural network approach focuses on deterministic environments, future research will explore extending these scalable metrics to stochastic systems, potentially using the similarity metric as an auxiliary task to accelerate representation learning in RL agents.

Summary updated

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.
BibTeX
@inproceedings{castro2020scalable,
  author = {Pablo Samuel Castro},
  title = {{Scalable Methods for Computing State Similarity in Deterministic Markov Decision Processes}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=6AB7WN3QSE},
}

Loading related content...

Figure