Bisimulation Metric

A bisimulation metric is a pseudometric on the state space of a Markov Decision Process (MDP). This means it satisfies three core axioms:

• Non-negativity: d(s1, s2) ≥ 0.
• Symmetry: d(s1, s2) = d(s2, s1).
• Triangle Inequality: d(s1, s3) ≤ d(s1, s2) + d(s2, s3).

Crucially, it is not a full metric because the identity of indiscernibles property (d(s1, s2) = 0 ⇒ s1 = s2) is relaxed. A distance of zero indicates states are behaviorally equivalent (bisimilar), but they may not be identical in their raw representation. This relaxation is essential for creating useful state abstractions.

The bisimulation metric is defined as the fixed point of a modified Bellman operator. Formally, it satisfies d = F(d), where F is a contraction mapping. This property guarantees:

• Existence and Uniqueness: A unique bisimulation metric exists for a given MDP.
• Computability: The metric can be approximated iteratively via dynamic programming or gradient-based methods, as repeated application of F converges to the fixed point.
• Stability: The distance between states is defined by the supremum over all possible policies or a specific policy, linking the metric directly to long-term value functions and ensuring states are close if they have similar future reward streams.

A core property is that bisimulation metrics induce policy-invariant state aggregations. If two states have a distance of zero (are bisimilar), they are behaviorally interchangeable under any policy. This means:

• Optimal Value Preservation: Aggregating bisimilar states into abstract states does not change the optimal value function. An optimal policy derived from the abstract MDP is also optimal for the original MDP.
• Robust Generalization: This invariance makes the metric powerful for state abstraction and transfer learning, as the learned representation is decoupled from a specific task's reward function and is instead grounded in the environment's dynamics.

The bisimulation distance between two states provides a tight upper bound on the difference in their optimal (or on-policy) values. Formally, for a discount factor γ, |V*(s1) - V*(s2)| ≤ d(s1, s2). This property has critical implications:

• Error Control: It guarantees that clustering states based on a small bisimulation distance will result in clusters with similar optimal values, controlling the loss from abstraction.
• Planning Guarantees: In model-based RL, using a dynamics model accurate under the bisimulation metric ensures that planned value estimates are accurate.
• It directly connects behavioral similarity (the metric) to decision-making quality (the value function).

Bisimulation metrics are theoretically linked to learning causal state representations. A representation is bisimulation-invariant if it maps behaviorally equivalent states to the same latent code. This property encourages the representation to discard noisy or irrelevant sensory information and retain only the features that causally influence future rewards. This leads to:

• Improved Generalization: Representations are robust to spurious correlations and changes in irrelevant parts of the observation space.
• Sample Efficiency: By focusing on causal features, RL agents can learn policies that transfer across different visual appearances or distractors.
• It provides a formal objective for representation learning in RL that goes beyond reconstruction error.

The exact bisimulation metric is often computationally intractable. In practice, several approximate variants are used, each with slightly relaxed properties:

• On-Policy Bisimulation: Measures similarity under a specific policy π, not all policies, making it easier to learn.
• π-Bisimulation: A common relaxation used in algorithms like DeepMind's DBC (Deep Bisimulation for Control).
• Lax Bisimulation: Allows for a small ε tolerance in the behavioral equivalence condition.
• Model-Based Approximation: The metric is approximated using a learned dynamics model and reward function. These approximations trade some theoretical guarantees for practical learnability from high-dimensional observations like images.

A Markov Decision Process (MDP) is the fundamental mathematical framework for modeling sequential decision-making. It is defined by a tuple (S, A, P, R, γ), where:

• S is a set of states.
• A is a set of actions.
• P is the state transition probability function.
• R is the reward function.
• γ is a discount factor.

The core Markov property states that the future state depends only on the current state and action, not the full history. A bisimulation metric is defined over the states S of an MDP, measuring distance based on the long-term behavioral consequences defined by P and R.

Model-Based Reinforcement Learning (MBRL) is a paradigm where an agent learns an explicit model of the environment's dynamics (and often its reward function). This learned world model can then be used for planning via simulation, such as with Monte Carlo Tree Search, or to generate synthetic experience for policy training.

Bisimulation metrics are a key tool in MBRL for learning compact and robust state representations. By embedding states into a metric space where distance corresponds to behavioral difference, the agent can generalize more effectively and its learned dynamics model can be more accurate and sample-efficient.

State representation is the process of transforming raw, high-dimensional observations (e.g., pixels from a camera) into a compact, informative encoding that is sufficient for decision-making. The goal is to discard irrelevant information while preserving what is necessary to predict future rewards and states.

A bisimulation metric provides a principled objective for learning such representations: the encoder is trained so that the distance between two latent states equals the bisimulation distance between the original observations. This results in a behaviorally-equivalent representation, which is invariant to nuisance factors and aligns with control objectives.

A world model is an agent's internal, learned simulation of its environment. It typically consists of a representation model (an encoder) and a dynamics model that predicts future representations and rewards. Famous examples include the Recurrent State-Space Model (RSSM) used in the Dreamer algorithm.

Bisimulation metrics are directly used to train the representation component of a world model. By enforcing that representationally similar states are also behaviorally similar, the world model learns a more coherent and predictable latent dynamics space, which in turn leads to more effective and stable planning.

Successor representations factor the classic value function into two components: a successor matrix that captures the expected future occupancy of states, and an immediate reward vector. Formally, the value of a state s under policy π is Vπ(s) = Mπ(s, ·) · r, where M is the successor representation.

This factorization is deeply connected to bisimulation. Bisimulation metrics can be computed using the difference in successor features between states. Furthermore, representations based on successor features are known to induce a form of behavioral similarity, making them a practical and theoretically grounded method for learning bisimulation-style embeddings.

A causal state representation aims to capture only the variables that have a causal influence on future outcomes, filtering out spurious correlations. This provides robustness to distributional shifts, as the representation focuses on invariant mechanisms.

Bisimulation metrics align closely with this causal perspective. Because the metric is defined by equality of future reward sequences under all policies, it inherently ignores features that do not causally affect long-term behavior. Therefore, learning a representation that is invariant under the bisimulation metric is a practical method for discovering causal state abstractions that generalize beyond the training data distribution.