Research map / Reinforcement learning / MDPs and planning
A Generalized Bisimulation Metric of State Similarity between Markov Decision Processes: From Theoretical Propositions to Applications
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Defines a generalized bisimulation metric (GBSM) between state pairs of two different MDPs, proves symmetry, inter-MDP triangle inequality and identical-space distance bounds, and uses them to derive tighter policy transfer, state aggregation and sampling-estimation bounds with closed-form sample complexity.
Problem
Bisimulation metrics are defined for a single MDP, and prior multi-MDP extensions lose metric properties, which limits theoretical analysis of policy transfer, state aggregation and sampling-based estimation across MDPs.
Approach
Extend the bisimulation metric to state pairs drawn from two MDPs via a Wasserstein-based recursion, prove it is symmetric and satisfies an inter-MDP triangle inequality and an identical-space TV-based bound, then use these properties to get tighter explicit error bounds than BSM-based analyses.
Key results
- GBSM-based policy transfer bound holds across 100 trials per gamma in {0.1,...,0.9}, whereas the disjoint-union BSM-based measure from prior work fails to bound the transfer regret.
- GBSM-based SSA and VFA bounds are reported as significantly tighter than BSM-based bounds (e.g., VFA bound tilde-sigma/(1-gamma) versus 2 tilde-sigma/(1-gamma)).
- Sampling-based estimation yields the closed-form sample complexity K >= -ln(alpha/2) gamma^2 Rbar^2 |S|^2 / (2 eps^2 (1-gamma)^4).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GBSM instead of the existing empirical MDP-similarity measure for policy transfer | Policy transfer between MDPs · Random Garnet MDPs | transfer regret bound validity | Helped |
| Use GBSM-based bounds instead of BSM-based bounds for state aggregation error | State similarity approximation (SSA) · Random Garnet MDPs | aggregation error bound: 2 σ_1 compared to 2\tilde{σ}_1 (2+γ)/(1-γ) | Helped |
| Use GBSM-based bounds instead of BSM-based bounds for sampling estimation error | State similarity approximation (SSA) · Random Garnet MDPs | estimation error bound: 2 \max_{s}d^{1\textnormal{-}\hat{1}}(s,s) compared to \frac{2 \gamma}{1\!- gamma}\max_{a,s} W_1( \hat{\mathbb{P}}(\cdot| | Helped |
| Use the GBSM-based value-function approximation bound instead of the BSM-based bound | Value function approximation under state aggregation · Random Garnet MDPs | value-function approximation error bound: \tilde{σ}_1/(1-γ) compared to 2\tilde{σ}_1/(1-γ) | Helped |
| Use GBSM to derive a closed-form sample complexity for estimation | Sampling-based estimation of state similarity · MDPs with state spaces of size |S_1| and |S_2| | sample complexity: K \geq -\ln(\alpha/2) \frac{\gamma^2\bar{R}^2|\mathcal{S}_{\cdot}|^2}{2\epsilon^2(1-\gamma)^4} | Helped |
Surprising findings
- The empirical metric from prior multi-MDP work fails to bound the transfer regret in the experiments.
Limitations
- Results rely on discounted reward; bounds diverge as gamma approaches 1, so average-reward MDPs are not covered.
- Experiments are limited to small randomly generated Garnet MDPs with no deep RL validation.
- Lax and on-policy extensions require additional assumptions (e.g., on the action mapping for lax transfer).
Experimental setup
Datasets: random Garnet MDPs (|S|=20, |A|=5, 50% branching)
Benchmarks: random Garnet MDPs
Metrics: regret bound tightness SSA error bound vs ground truth VFA error bound vs ground truth
Baselines: BSM-based SSA bound BSM-based VFA bound disjoint-union BSM policy transfer measure tabular Q-learning ground truth
Builds on: bisimulation metric (Ferns et al.) Kantorovich duality Knaster-Tarski fixed-point theorem Hoeffding inequality
Closest papers by meaning
- Distances for Markov chains from sample streams (NeurIPS 2025 · similarity 0.87)
- Bisimulation Metric for Model Predictive Control (ICLR 2025 · similarity 0.86)
- Building Minimal and Reusable Causal State Abstractions for Reinforcement Learning (AAAI 2024 · similarity 0.86)
- State Chrono Representation for Enhancing Generalization in Reinforcement Learning (NeurIPS 2024 · similarity 0.86)
- The Number of Trials Matters in Infinite-Horizon General-Utility Markov Decision Processes (ICML 2025 · similarity 0.86)
- Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficiently (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.