Two states of a control system behave alike if they earn similar rewards and lead to similar futures. A bisimulation metric is a distance between states that measures exactly this. It is defined recursively: the distance between two states is their reward gap plus a discounted optimal-transport distance between their next-state distributions, where the transport cost is the metric itself. On finite systems the recursion can be computed in polynomial time with linear programs. On continuous systems the standard recipe is to sample next states and solve an assignment problem on the samples. That recipe inherits a basic problem with high dimensions: the empirical transport (Wasserstein) distance in $d$ dimensions converges only at rate $n^{-1/d}$ in the sample size $n$. With 20 or 60 state dimensions, a sampled bisimulation metric is therefore mostly noise. This is the main reason deep RL abandoned exact metrics for learned neural surrogates that carry no guarantee.
We propose to compute bisimulation metrics on continuous, high-dimensional states by replacing the full transport problem with its dual restricted to a small class of "witness" functions built from the current metric iterate. Concretely, the witnesses are the unit ball of a reproducing kernel Hilbert space whose kernel is $\exp(-d_k/\sigma)$ on the current distance $d_k$. Each step then has a closed form, costs polynomial time in the number of samples, and converges at a dimension-free $n^{-1/2}$ rate. The central question is what happens when these per-step errors are fed back through the recursion. We will answer it with an explicit non-asymptotic sample-and-iteration complexity, and then test empirically whether the predicted scaling actually appears.
Core Claim
Let $T_n$ denote one sampled step of the metric recursion using $n$ next-state samples per state pair, and let $c<1$ be the discount on the transport term. The step is built from three parts: the reward gap $|r(s)-r(t)|$; a witness class $\mathcal{F}_{d_k}$, meaning the kernel ball described above, scaled so that it lies inside the functions that are 1-Lipschitz under $d_k$; and an integral probability metric over $\mathcal{F}_{d_k}$, which measures the largest gap in expected value that any witness function can show between the two next-state distributions.
We claim that the error of the iterate after $K$ steps obeys
$$\|d_K - d^\star_{\mathcal{F}}\|_\infty \le c^K \|d_0 - d^\star_{\mathcal{F}}\|_\infty + \sum_{k<K} c^{K-1-k}\, \frac{C\sqrt{\log(|P|/\delta)}}{\sqrt{n_k}},$$
where $d^\star_{\mathcal{F}}$ is the fixed point of the restricted recursion, $|P|$ is the number of state pairs evaluated, $\delta$ is a failure probability, and $n_k$ is the sample budget at step $k$.
The first term is the usual contraction of a fixed-point iteration. The second term comes from a uniform concentration bound for a bounded kernel ball, and it does not depend on $d$. Choosing a geometric schedule $n_k \propto c^{-2k}$ yields error $\epsilon$ with roughly $\epsilon^{-2}(1-c)^{-2}$ total samples per pair, up to logarithmic factors. Naive sampled transport would need roughly $\epsilon^{-d}$. Because the witness class is smaller than all Lipschitz functions, the value-difference guarantee of Bisimulation Metrics for Continuous Markov Decision Processes holds only up to an approximation term: the distance from the scaled value function to $\mathcal{F}_{d}$. Measuring that term is part of the work, not something to hide.
Relation to Prior Work
The method comes from two sources. Quantifying the Empirical Wasserstein Distance to a Set of Measures shows that restricting the dual function class restores parametric rates in $d=20$. It treats a single static comparison, solves it with Newton iterations and random restarts, and never feeds the result back into itself. We apply the same restriction idea inside the recursion, and we pick a kernel class so that each step is closed-form rather than a nonconvex solve.
The recursion and its polynomial-time character come from the linear-programming reductions of Majumdar et al. and Bacci et al.. We use those exact solvers only to produce ground-truth metrics on finite systems.
Three papers motivate the gap. Ferns et al. prove almost-sure convergence of the sampled metric, with no rate, and test only on grid worlds. A Generalized Bisimulation Metric of State Similarity between Markov Decision Processes gives a sample complexity, but only for discrete synthetic Garnet MDPs, and its authors note that continuous and visual spaces need new algorithms. Data-driven Abstractions via Adaptive Refinements and a Kantorovich Metric refines partitions, assumes exact transition probabilities, and costs time exponential in the label horizon. We avoid partitioning altogether.
The deep line of work runs on pixels but gives up any certificate. That line includes Towards Robust Bisimulation Metric Learning, which documents embedding explosion and collapse, Bisimulation Metric for Model Predictive Control, and Revisiting Bisimulation Metric for Robust Representations in Reinforcement Learning. We do not claim to beat these methods at control. We claim to provide a metric whose error can be bounded and measured, at a sample cost that does not grow with dimension.
Research Program
The theory component proves the displayed bound. The main difficulty is that the witness class depends on the iterate $d_k$, so we must show that the map from $d$ to $\mathcal{F}_d$ is stable. We also need a uniform-in-$k$ concentration argument and a characterization of the approximation term. For the latter we will bound the distance from the scaled value function to $\mathcal{F}_d$ in terms of kernel bandwidth and value smoothness. We will also state when this term is not small, for example in tasks whose value depends on a single fine-grained coordinate.
The algorithm component is a GPU implementation. It holds anchor states and their next-state samples, computes the kernel distance between sample sets in $O(n^2)$ per pair, extends the metric to new states through the kernel, and follows the geometric sample schedule.
The empirical component is designed to falsify the claim. If the measured error slope against $n$ depends on $d$, or if the value-bound approximation term dominates on real tasks, the proposal fails, and we will report that.
Baselines
The naive reference point is the sampled metric of Ferns et al.: Monte Carlo next states with the Hungarian algorithm, run with the same anchor states, the same per-pair samples, and the same iteration count. Ferns et al. report that sampling needed 80Kb to 1.8Mb of memory, against up to 1.8Gb or crashes for exact linear programming on grid worlds. They report no accuracy-versus-dimension number, so beating this baseline means a smaller measured error at equal samples, together with an error slope that stays flat as $d$ grows while the Hungarian baseline's slope degrades.
The strongest exact method is the full linear program of Majumdar et al. on the underlying finite MDP. It defines ground truth wherever it fits in memory, and we do not expect to beat it on accuracy. The relevant comparison is the dimension and state count at which it stops running while our method still matches its rankings.
The strongest learned competitor is the revised MICo of Revisiting Bisimulation Metric. It reports a score of about 963 on DMC Reacher Hard, against about 307 for the original MICo. We will train it on the same transition data with its published hyperparameters and an equal tuning budget. Beating it on our primary question means lower error against ground truth and tighter value-difference bounds. On control return we aim only to roughly match it, within seed variance, when our metric is used as the same auxiliary target.
For GBSM on Garnet MDPs there is no reported numeric result on Lacuna, so we will rerun it.
Two ablations isolate the key ingredient. The first uses a fixed kernel on raw state coordinates instead of the metric-induced kernel. The second uses a constant sample schedule instead of the geometric one.
Why not just…?
Why not just keep sampled optimal transport and add more samples? The $n^{-1/d}$ rate discussed by Si et al. means that halving the error at $d=20$ costs about a millionfold more samples. Ferns et al. validated only on small grids. Our dimension sweep measures this slope directly. If sampled transport turns out to behave well on structured MDPs whose intrinsic dimension is low, the sweep will show it, and we will say so.
Why not just use a standard kernel distance on raw states? This is the real threat. It is cheap and also dimension-free, and we found no reported result on Lacuna for it in bisimulation. The difference is that a fixed raw-coordinate kernel ignores the recursive structure. It treats nuisance dimensions the same as reward-relevant ones, so its fixed point need not bound value differences. The fixed-kernel ablation tests exactly this. If it matches the metric-induced kernel on value-bound tightness when distractor dimensions are present, the adaptive kernel is unnecessary and the contribution shrinks to the rate analysis.
Why not just learn the metric with a deep encoder? Learned surrogates scale to pixels, and BS-MPC reports stable returns up to 8M-10M steps where TD-MPC crashes. However, Kemertas et al. show collapse and explosion that require heuristic fixes, and none of these methods provide an error bar on the metric. Our experiments measure the error of the learned metrics against exact ground truth. If the learned metrics are as accurate, the certificate is our only remaining advantage.
Proposed Experiments
The decisive test uses lifted Garnet MDPs. We take Garnet MDPs with 50 to 500 states and embed each state as a point in $\mathbb{R}^d$, with $d$ from 2 to 64. Transitions add Gaussian noise in the embedding, and some directions are reward-irrelevant distractors. Ground truth comes from the exact linear program on the base MDP. We plot sup-norm error and rank correlation against total samples for every $d$. The prediction is a slope of about $-1/2$ that does not depend on $d$ for our method, against slopes that degrade with $d$ for Hungarian sampling. We also track the empirical value-bound violation, defined as $|V(s)-V(t)|(1-c)$ minus the estimated distance, and report how it changes as $c\to1$.
The second test uses DMC state-based tasks from the DeepMind Control Suite, with policies and data from deep_ope, plus appended distractor dimensions. Exact ground truth is unavailable here, so we evaluate value-difference bound tightness against Monte Carlo returns and the error of state aggregation at a fixed number of clusters. Wall-clock time and memory are reported against every baseline.
The third test uses RRLS perturbations. We check whether the metric between nominal and perturbed dynamics tracks the measured drop in return.
The secondary downstream check uses our metric as the auxiliary target on Reacher Hard, against the reported score of about 963.
References
- Bisimulation Metrics for Continuous Markov Decision Processes
- Quantifying the Empirical Wasserstein Distance to a Set of Measures: Beating the Curse of Dimensionality
- Algorithms for Game Metrics
- On-the-Fly Computation of Bisimilarity Distances
- A Generalized Bisimulation Metric of State Similarity between Markov Decision Processes: From Theoretical Propositions to Applications
- Data-driven Abstractions via Adaptive Refinements and a Kantorovich Metric
- Towards Robust Bisimulation Metric Learning
- Bisimulation Metric for Model Predictive Control
- Revisiting Bisimulation Metric for Robust Representations in Reinforcement Learning
- DeepMind Control Suite