Sub-Quadratic Bisimulation Metrics via Approximate Nearest Neighbors: Coverage-Augmented Guarantees and Computable Two-Sided Certificates

# Sub-Quadratic Bisimulation Metrics via Approximate Nearest Neighbors: Coverage-Augmented Guarantees and Computable Two-Sided Certificates
Source: [https://arxiv.org/html/2608.06762](https://arxiv.org/html/2608.06762)
###### Abstract

Bisimulation metrics quantify behavioral similarity in Markov decision processes, but their Wasserstein fixed\-point operator updates every state pair and incurs quadratic pairwise work\. We give a certificate\-carrying sub\-quadratic method for MDPs with bounded transition support and a useful low\-dimensional indexing representation: an approximate\-nearest\-neighbor index selects the pairs updated by the exact restricted operator, while monotone lower and upper runs enclose the exact metric at every sweep\. The main analytical result is a coverage\-augmented anytime bound: local index quality alone cannot control global error, because uncovered pairs retain their initialization gap\. The limiting error is at mostmax⁡\(ρ,εop/\(1−γ\)\)\\max\(\\rho,\\varepsilon\_\{\\mathrm\{op\}\}/\(1\-\\gamma\)\), and with exact covered backups the lower arm satisfies‖d^−d‖∞=ρ\\\|\\hat\{d\}\-d\\\|\_\{\\infty\}=\\rho\. Becauseρ\\rhodepends on the unknown exact metric, the algorithm returns the observable sandwich width instead; agreement of the induced lower and upper clusterings certifies exact recovery of the covered aggregation\. A reward\-oblivious lower bound shows sub\-quadratic index\-first coverage cannot remove the coverage term, while a separate adaptive lower bound requiresΩ​\(\|𝒮\|\)\\Omega\(\|\\mathcal\{S\}\|\)pair evaluations\. Exact\-operator experiments verify the identity and enclosure in every seeded run, and timing experiments recover quadratic versus sub\-quadratic scaling under both cheap and full Wasserstein backups\. On the grouped\|𝒮\|=64\|\\mathcal\{S\}\|=64benchmark, exact restricted refinement reaches the exact\-metric skyline once retrieval covers roughly half of all pairs, while independently trained MICo and DBC baselines stay2222–33×33\\timesabove that skyline at every retrieval budget\. Taxi shows the certificate abstaining under an uninformative embedding, while a25002500\-state gridworld improves over a reward\-only metric by28\.6%28\.6\\%using12\.8%12\.8\\%of one quadratic sweep\.

## Introduction

A reinforcement learning agent that treats two behaviorally identical states as identical can generalize across them and learn from fewer samples; the bisimulation metric is the formal device licensing this\. Introduced for finite MDPs byFernset al\.\([2004](https://arxiv.org/html/2608.06762#bib.bib3)\)and extended to continuous and infinite spaces byFernset al\.\([2011](https://arxiv.org/html/2608.06762#bib.bib4)\), the metricddis small exactly when two states are behaviorally interchangeable: the fixed point of an operator coupling immediate\-reward difference with Wasserstein distance between next\-state distributions\. States at distance zero are bisimilar in the sense ofLarsen and Skou \([1989](https://arxiv.org/html/2608.06762#bib.bib1)\); Givanet al\.\([2003](https://arxiv.org/html/2608.06762#bib.bib2)\); the metric degrades gracefully between equivalence classes, useful for state abstraction\(Liet al\.[2006](https://arxiv.org/html/2608.06762#bib.bib17); Ravindran[2004](https://arxiv.org/html/2608.06762#bib.bib18)\)and representation learning\(Zhanget al\.[2021](https://arxiv.org/html/2608.06762#bib.bib26); Geladaet al\.[2019](https://arxiv.org/html/2608.06762#bib.bib27); Castroet al\.[2021](https://arxiv.org/html/2608.06762#bib.bib24)\)\.

The price is quadratic: each application visitsΘ​\(\|𝒮\|2\)\\Theta\(\|\\mathcal\{S\}\|^\{2\}\)pairs and solves an optimal\-transport problem per pair, prohibitive at the Atari\-scale state spaces motivating deep representation learning\(Bellemareet al\.[2013](https://arxiv.org/html/2608.06762#bib.bib52); Mnihet al\.[2015](https://arxiv.org/html/2608.06762#bib.bib53)\)\. The standard response abandons the exact metric for a sampled surrogate folded into a learned embedding\(Castro[2020](https://arxiv.org/html/2608.06762#bib.bib23); Castroet al\.[2021](https://arxiv.org/html/2608.06762#bib.bib24); Zhanget al\.[2021](https://arxiv.org/html/2608.06762#bib.bib26)\), trading guarantees for scalability\. We ask instead whether the metric can be computed sub\-quadratically, keeping a provable,*checkable*relation to the exact object\.

The opportunity arises in MDPs whose bisimulation geometry admits a low\-dimensional Euclidean representation: metric\-embedding theory and landmark MDS\(Bourgain[1985](https://arxiv.org/html/2608.06762#bib.bib43); Linialet al\.[1994](https://arxiv.org/html/2608.06762#bib.bib44); Cox and Cox[2001](https://arxiv.org/html/2608.06762#bib.bib45)\)give a practical index, and given‖ϕ​\(s\)−ϕ​\(s′\)‖≈d​\(s,s′\)\\left\\lVert\\phi\(s\)\-\\phi\(s^\{\\prime\}\)\\right\\rVert\\approx d\(s,s^\{\\prime\}\), approximate\-nearest\-neighbor search retrieves candidates sub\-linearly\(Indyk and Motwani[1998](https://arxiv.org/html/2608.06762#bib.bib32); Andoni and Indyk[2008](https://arxiv.org/html/2608.06762#bib.bib33); Malkov and Yashunin[2020](https://arxiv.org/html/2608.06762#bib.bib37)\), restricting the sweep toO​\(\|𝒮\|​k′\)O\(\|\\mathcal\{S\}\|k^\{\\prime\}\)pairs \(Figure[1](https://arxiv.org/html/2608.06762#Sx1.F1)\)\. This isn’t assumed universally: a poor embedding still leaves the certificate valid, exposing rather than hiding failure\. Theorem[1](https://arxiv.org/html/2608.06762#Thmtheorem1)makes the complexity precise; the harder question is what error sparse coverage necessarily leaves\.

MDP\(𝒮,𝒜,P,R,γ\)\(\\mathcal\{S\},\\mathcal\{A\},P,R,\\gamma\)embedϕ\\phidistortionη\\etaANN indexN​\(s\)N\(s\), recallrrtwo restricted runsft−↑f\_\{t\}^\{\-\}\\\!\\uparrow;ft\+↓f\_\{t\}^\{\+\}\\\!\\downarrowsandwichft−≤d≤ft\+f\_\{t\}^\{\-\}\\leq d\\leq f\_\{t\}^\{\+\}uncovered pairs frozen: gapρ=max\(s,s′\)∉𝒞⁡\(d​\(s,s′\)−d0​\(s,s′\)\)\\rho=\\max\\limits\_\{\(s,s^\{\\prime\}\)\\notin\\mathcal\{C\}\}\\big\(d\(s,s^\{\\prime\}\)\-d\_\{0\}\(s,s^\{\\prime\}\)\\big\); lower arm‖d^−d‖∞=ρ\\left\\lVert\\hat\{d\}\-d\\right\\rVert\_\{\\infty\}=\\rho\(Cor\.[3](https://arxiv.org/html/2608.06762#Thmtheorem3)\)Figure 1:Certified sub\-quadratic bisimulation via ANN\. An ANN index over embeddingϕ\\phifixes covered pairs𝒞\\mathcal\{C\}; two monotone restricted iterations encloseddat every sweep \(Cor\.[6](https://arxiv.org/html/2608.06762#Thmtheorem6)\)\. Uncovered pairs freeze at gapρ\\rho, which the lower arm’s global error*equals*\(Cor\.[3](https://arxiv.org/html/2608.06762#Thmtheorem3)\)\.The difficulty is the error\. An ANN sweep seems to cost only two local, per\-step quantities, the embedding distortionη\\etaand recall missrr, amplified by1/\(1−γ\)1/\(1\-\\gamma\)into a clean bound‖d^−d‖∞≤ε/\(1−γ\)\\left\\lVert\\hat\{d\}\-d\\right\\rVert\_\{\\infty\}\\leq\\varepsilon/\(1\-\\gamma\)forε=η\+L​r\\varepsilon=\\eta\+Lr\.*Every bound of this form is false*, not because of the constant: a top\-kkindex touches onlyO​\(\|𝒮\|​k\)O\(\|\\mathcal\{S\}\|k\)of the\(\|𝒮\|2\)\\binom\{\|\\mathcal\{S\}\|\}\{2\}pairs per iteration, and without re\-seeding still misses aΘ​\(\|𝒮\|2\)\\Theta\(\|\\mathcal\{S\}\|^\{2\}\)fraction entirely; those pairs are never updated and incur their full initialization gap as error, invisible to per\-step index quality\. Proposition[4](https://arxiv.org/html/2608.06762#Thmtheorem4)makes the refutation unconditional, constructing two reward\-oblivious instances with zero distortion and recall miss, indistinguishable on every evaluated pair yet differing by a constant on an uncovered one\. The random\-MDP grid instead verifies the corrected identity, covered\-pair bound, and two\-sided enclosure under an exact Kantorovich backup\.

In this paper, we replace the conjecture with a*coverage\-augmented*guarantee\. Our contributions are as follows\.

- •We give a certificate\-carrying sub\-quadratic algorithm: an ANN index over a low\-dimensional embedding selects the pairs, and the exact Kantorovich operator updates those alone \(Algorithm[1](https://arxiv.org/html/2608.06762#alg1), Theorem[1](https://arxiv.org/html/2608.06762#Thmtheorem1)\)\.
- •We prove an anytime error bound \(Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)\): afterttsweeps the global error is at mostmax⁡\(ρ,εop/\(1−γ\)\)\+γt​Δ0\\max\(\\rho,\\varepsilon\_\{\\mathrm\{op\}\}/\(1\-\\gamma\)\)\+\\gamma^\{t\}\\Delta\_\{0\}, for coverage gapρ\\rho, backup perturbationεop\\varepsilon\_\{\\mathrm\{op\}\}, and initialization gapΔ0\\Delta\_\{0\}; for the exact backup it sharpens to the equality‖d^−d‖∞=ρ\\left\\lVert\\hat\{d\}\-d\\right\\rVert\_\{\\infty\}=\\rho\(Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3)\), so the frozen block does not bound the error, it*is*the error, however good the index\.
- •Sinceρ\\rhois unobservable, we pair that iteration with an over\-estimating twin, proving a computable anytime sandwichft−≤d≤ft\+f\_\{t\}^\{\-\}\\leq d\\leq f\_\{t\}^\{\+\}\(Corollary[6](https://arxiv.org/html/2608.06762#Thmtheorem6)\) whose width bounds per\-pair error and whose induced clusterings, on agreement, recover the exact covered aggregation without computingdd\.
- •We prove matching lower bounds \(Proposition[4](https://arxiv.org/html/2608.06762#Thmtheorem4)\): a quadratic obstruction for reward\-oblivious index\-first selection andΩ​\(\|𝒮\|\)\\Omega\(\|\\mathcal\{S\}\|\)evaluations for fully adaptive selection, leaving the super\-linear case open\.
- •We verify the analysis without surrogates, using an exact Kantorovich operator, a real MDS embedding, and a real LSH index, and we measure wall\-clock scaling against the exact sweep, compare against independently trained MICo and DBC, and run the pipeline on Taxi and a25002500\-state gridworld\.

## Setup and Related Work

We consider a finite Markov decision process\(𝒮,𝒜,P,R,γ\)\(\\mathcal\{S\},\\mathcal\{A\},P,R,\\gamma\)with states𝒮\\mathcal\{S\}, actions𝒜\\mathcal\{A\}, transition kernelP\(⋅∣s,a\)P\(\\cdot\\mid s,a\), rewardR:𝒮×𝒜→\[0,L\]R:\\mathcal\{S\}\\times\\mathcal\{A\}\\to\[0,L\], and discountγ∈\[0,1\)\\gamma\\in\[0,1\)\(Puterman[1994](https://arxiv.org/html/2608.06762#bib.bib49); Sutton and Barto[2018](https://arxiv.org/html/2608.06762#bib.bib50)\)\. Throughout, metrics are symmetric functions on unordered pairs with zero diagonal, andDγ:=L/\(1−γ\)D\_\{\\gamma\}:=L/\(1\-\\gamma\)denotes the a\-priori diameter bound \(d≤Dγd\\leq D\_\{\\gamma\}pointwise for every metric considered here\)\. The bisimulation metric ofFernset al\.\([2004](https://arxiv.org/html/2608.06762#bib.bib3)\)is the fixed pointd=T​dd=Tdof the operator

\(Tf\)\(s,s′\)=maxa∈𝒜\[\|R​\(s,a\)−R​\(s′,a\)\|\+γW1f\(P\(⋅∣s,a\),P\(⋅∣s′,a\)\)\],\\begin\{split\}\(Tf\)\(s,s^\{\\prime\}\)=\\max\_\{a\\in\\mathcal\{A\}\}\\Big\[\\,&\|R\(s,a\)\-R\(s^\{\\prime\},a\)\|\\\\ &\+\\gamma\\,W\_\{1\}^\{f\}\\big\(P\(\\cdot\\mid s,a\),P\(\\cdot\\mid s^\{\\prime\},a\)\\big\)\\Big\],\\end\{split\}\(1\)whereW1fW\_\{1\}^\{f\}is the Kantorovich–Wasserstein\-1 distance under ground costff\(Villani[2009](https://arxiv.org/html/2608.06762#bib.bib46)\)\. The operator is aγ\\gamma\-contraction in the sup\-norm‖f‖∞=maxs,s′⁡\|f​\(s,s′\)\|\\left\\lVert f\\right\\rVert\_\{\\infty\}=\\max\_\{s,s^\{\\prime\}\}\|f\(s,s^\{\\prime\}\)\|, monotone in its ground cost \(Lemma[9](https://arxiv.org/html/2608.06762#Thmtheorem9)\), soddexists, is unique, and is the limit ofTn​0T^\{n\}0\(Comaniciet al\.[2015](https://arxiv.org/html/2608.06762#bib.bib13)\)\. Each application evaluates \([1](https://arxiv.org/html/2608.06762#Sx2.E1)\) at every one of the\(\|𝒮\|2\)\\binom\{\|\\mathcal\{S\}\|\}\{2\}pairs and solves an optimal\-transport problem per pair\-action, theΘ​\(\|𝒮\|2\)\\Theta\(\|\\mathcal\{S\}\|^\{2\}\)cost we attack\.

Probabilistic bisimulation originates withLarsen and Skou \([1989](https://arxiv.org/html/2608.06762#bib.bib1)\)and, for labelled Markov processes,Desharnaiset al\.\([1999](https://arxiv.org/html/2608.06762#bib.bib7),[2004](https://arxiv.org/html/2608.06762#bib.bib8)\); the quantitative refinement is due toFernset al\.\([2004](https://arxiv.org/html/2608.06762#bib.bib3),[2011](https://arxiv.org/html/2608.06762#bib.bib4)\), extended to infinite spaces\(Fernset al\.[2005](https://arxiv.org/html/2608.06762#bib.bib5)\), with domain\-theoretic treatments\(van Breugel and Worrell[2005](https://arxiv.org/html/2608.06762#bib.bib9),[2001](https://arxiv.org/html/2608.06762#bib.bib10)\)\.Ferns and Precup \([2014](https://arxiv.org/html/2608.06762#bib.bib6)\)connect the metric to value functions,Comanici and Precup \([2011](https://arxiv.org/html/2608.06762#bib.bib12)\)to basis\-function discovery,Tayloret al\.\([2009](https://arxiv.org/html/2608.06762#bib.bib11)\); Ravindran and Barto \([2003](https://arxiv.org/html/2608.06762#bib.bib19)\)to lax and homomorphism variants\. As the fixed point of a contraction\(Bertsekas and Tsitsiklis[1996](https://arxiv.org/html/2608.06762#bib.bib51); Puterman[1994](https://arxiv.org/html/2608.06762#bib.bib49)\), an iterative solver is natural; its asynchronous convergence theory\(Bertsekas and Tsitsiklis[1996](https://arxiv.org/html/2608.06762#bib.bib51)\)is what our re\-seeded pipeline \(Corollary[7](https://arxiv.org/html/2608.06762#Thmtheorem7)\) invokes, and monotone two\-sided enclosures, classical in numerical dynamic programming, are what we adapt\. Exact and on\-the\-fly algorithms\(Bacciet al\.[2013a](https://arxiv.org/html/2608.06762#bib.bib14),[b](https://arxiv.org/html/2608.06762#bib.bib15)\)and complexity results\(Chenet al\.[2012](https://arxiv.org/html/2608.06762#bib.bib16)\)remain quadratic; model minimization\(Givanet al\.[2003](https://arxiv.org/html/2608.06762#bib.bib2); Deanet al\.[1997](https://arxiv.org/html/2608.06762#bib.bib20)\)and approximate abstraction\(Liet al\.[2006](https://arxiv.org/html/2608.06762#bib.bib17); Abelet al\.[2016](https://arxiv.org/html/2608.06762#bib.bib21); Jianget al\.[2015](https://arxiv.org/html/2608.06762#bib.bib22)\)inherit this cost when the metric must be computed rather than assumed\.

The scalable line of work sidesteps the cost by learning rather than computing:Castro \([2020](https://arxiv.org/html/2608.06762#bib.bib23)\)gives sampling\-based methods for deterministic MDPs,Castroet al\.\([2021](https://arxiv.org/html/2608.06762#bib.bib24)\)the MICo distance \(kernel and continuity analyses:Castroet al\.\([2023](https://arxiv.org/html/2608.06762#bib.bib25)\); Le Lanet al\.\([2021](https://arxiv.org/html/2608.06762#bib.bib29)\)\), andZhanget al\.\([2021](https://arxiv.org/html/2608.06762#bib.bib26)\); Geladaet al\.\([2019](https://arxiv.org/html/2608.06762#bib.bib27)\); Kemertas and Aumentado\-Armstrong \([2021](https://arxiv.org/html/2608.06762#bib.bib28)\); Agarwalet al\.\([2021](https://arxiv.org/html/2608.06762#bib.bib30)\); Le Lanet al\.\([2022](https://arxiv.org/html/2608.06762#bib.bib31)\)learn embeddings tracking a bisimulation\-like distance\. We are complementary: we accelerate the metric’s computation rather than replace it, using an embedding only as an index for ANN queries, not the final representation\.

The acceleration draws on sub\-linear near\-neighbor search via locality\-sensitive hashing\(Indyk and Motwani[1998](https://arxiv.org/html/2608.06762#bib.bib32); Dataret al\.[2004](https://arxiv.org/html/2608.06762#bib.bib34)\), near\-optimal and random\-hyperplane hashing\(Andoni and Indyk[2008](https://arxiv.org/html/2608.06762#bib.bib33); Andoniet al\.[2018](https://arxiv.org/html/2608.06762#bib.bib36); Charikar[2002](https://arxiv.org/html/2608.06762#bib.bib35)\), product quantization\(Jégouet al\.[2011](https://arxiv.org/html/2608.06762#bib.bib39); Johnsonet al\.[2021](https://arxiv.org/html/2608.06762#bib.bib38)\), graph indices\(Malkov and Yashunin[2020](https://arxiv.org/html/2608.06762#bib.bib37)\), and surveys\(Wanget al\.[2014](https://arxiv.org/html/2608.06762#bib.bib40); Liet al\.[2020](https://arxiv.org/html/2608.06762#bib.bib41); Aumülleret al\.[2020](https://arxiv.org/html/2608.06762#bib.bib42)\)\. The bridge from a metric to a Euclidean index is metric embedding\(Bourgain[1985](https://arxiv.org/html/2608.06762#bib.bib43); Linialet al\.[1994](https://arxiv.org/html/2608.06762#bib.bib44)\), realized by landmark MDS\(Cox and Cox[2001](https://arxiv.org/html/2608.06762#bib.bib45)\); the Wasserstein term is the object of computational optimal transport\(Villani[2009](https://arxiv.org/html/2608.06762#bib.bib46); Peyré and Cuturi[2019](https://arxiv.org/html/2608.06762#bib.bib47); Cuturi[2013](https://arxiv.org/html/2608.06762#bib.bib48)\)\. No prior work runs the bisimulation fixed\-point iteration through an ANN index, to our knowledge; the coverage phenomenon and its computable certificate are our theory\-side contribution\.

## Algorithms: a Certified Pipeline and Its Analyzed Core

Two objects organize the paper\. Algorithm[1](https://arxiv.org/html/2608.06762#alg1)is the*deliverable*: a re\-seeded, two\-armed pipeline maintaining a monotone lower iterated^\\hat\{d\}and upper iterated^\+\\hat\{d\}^\{\+\}that enclose the exact metric at every sweep and stop when the observable width meets tolerance\. Algorithm[2](https://arxiv.org/html/2608.06762#alg2)is its*analyzed core*: a single\-build restricted iteration whose guarantees \(Theorems[1](https://arxiv.org/html/2608.06762#Thmtheorem1)–[2](https://arxiv.org/html/2608.06762#Thmtheorem2), Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3)\) compose across re\-seed rounds into the pipeline’s certificate \(Corollaries[6](https://arxiv.org/html/2608.06762#Thmtheorem6),[7](https://arxiv.org/html/2608.06762#Thmtheorem7)\), and isolates the coverage phenomenon in its pure form\.

Algorithm 1Certified sub\-quadratic bisimulation \(pipeline\)1:input:MDP; embedding dim

kk; neighbor budget

k′k^\{\\prime\}; sweeps per round

EE; uniform exploration count

u≥1u\\geq 1; tolerance

tol\\mathrm\{tol\}\(or threshold

τ\\tau\)

2:

d^←dR\\hat\{d\}\\leftarrow d\_\{R\}\(implicit lazy under\-estimate\);

d^\+←Dγ\\hat\{d\}^\{\+\}\\leftarrow D\_\{\\gamma\}off\-diagonal;

𝒞←∅\\mathcal\{C\}\\leftarrow\\emptyset
3:repeat

4:

ϕ←\\phi\\leftarrowlandmark\-MDS embedding of the current

d^\\hat\{d\}
5:build the ANN index with fresh randomness and query every state

6:

𝒞←𝒞∪\{ANN\-retrieved unordered pairs\}\\mathcal\{C\}\\leftarrow\\mathcal\{C\}\\cup\\\{\\text\{ANN\-retrieved unordered pairs\}\\\}
7:foreach

s∈𝒮s\\in\\mathcal\{S\}and

j=1,…,uj=1,\\ldots,udo

8:draw

v∼Unif​\(𝒮∖\{s\}\)v\\sim\\mathrm\{Unif\}\(\\mathcal\{S\}\\setminus\\\{s\\\}\)and add

\{s,v\}\\\{s,v\\\}to

𝒞\\mathcal\{C\}
9:endfor

10:for

EEsweepsdo

11:exact restricted backup of

d^\\hat\{d\}and

d^\+\\hat\{d\}^\{\+\}on every pair in

𝒞\\mathcal\{C\}⊳\\trianglerightAlg\.[2](https://arxiv.org/html/2608.06762#alg2), line[9](https://arxiv.org/html/2608.06762#alg2.l9)

12:endfor

13:untilwidth meets tolerance, or

Πτ\+=Πτ−\\Pi^\{\+\}\_\{\\tau\}=\\Pi^\{\-\}\_\{\\tau\}\(Cor\.[6](https://arxiv.org/html/2608.06762#Thmtheorem6)\(d\)\)

14:return

d^,d^\+,𝒞\\hat\{d\},\\hat\{d\}^\{\+\},\\mathcal\{C\}

Algorithm 2Single\-build restricted iteration \(analyzed core\)1:input:MDP;

kk;

k′k^\{\\prime\}; sweeps

KK; initialization

d0≤dd\_\{0\}\\leq d\(default:

dRd\_\{R\}, implicit\) or upper freeze

DγD\_\{\\gamma\}
2:

d^←d0\\hat\{d\}\\leftarrow d\_\{0\}⊳\\trianglerightlazy; un\-updated entries read asd0d\_\{0\}

3:

ϕ←\\phi\\leftarrowlandmark\-MDS embedding of

d0d\_\{0\}into

ℝk\\mathbb\{R\}^\{k\}
4:build ANN index over

\{ϕ​\(s\)\}\\\{\\phi\(s\)\\\}; for each

ss:

N​\(s\)←k′N\(s\)\\leftarrow k^\{\\prime\}retrieved neighbors

5:

𝒞←\{\(s,s′\):s′∈N​\(s\)​or​s∈N​\(s′\)\}\\mathcal\{C\}\\leftarrow\\\{\(s,s^\{\\prime\}\):s^\{\\prime\}\\in N\(s\)\\ \\text\{or\}\\ s\\in N\(s^\{\\prime\}\)\\\}
6:for

t=1,…,Kt=1,\\dots,Kdo

7:

g←d^g\\leftarrow\\hat\{d\}⊳\\trianglerightJacobi update: freeze the previous sweep

8:foreach

\(s,s′\)∈𝒞\(s,s^\{\\prime\}\)\\in\\mathcal\{C\}do

9:

d^\(s,s′\)←maxa\[\|R\(s,a\)−R\(s′,a\)\|\+γW1g\(P\(⋅\|s,a\),P\(⋅\|s′,a\)\)\]\\hat\{d\}\(s,s^\{\\prime\}\)\\leftarrow\\max\_\{a\}\\big\[\\,\|R\(s,a\)\-R\(s^\{\\prime\},a\)\|\+\\gamma\\,W\_\{1\}^\{g\}\(P\(\\cdot\|s,a\),P\(\\cdot\|s^\{\\prime\},a\)\)\\big\]
10:endfor

11:endfor

12:return

d^\\hat\{d\}and

𝒞\\mathcal\{C\}

The deployment pipeline mixes geometry\-aware ANN retrieval with a small amount of uniform coverage exploration\. Withu=1u=1, an unordered pair\{s,s′\}\\\{s,s^\{\\prime\}\\\}is selected in a re\-seed round with probabilityp\|𝒮\|=1−\(1−1\|𝒮\|−1\)2≥1\|𝒮\|−1p\_\{\|\\mathcal\{S\}\|\}=1\-\(1\-\\tfrac\{1\}\{\|\\mathcal\{S\}\|\-1\}\)^\{2\}\\geq\\tfrac\{1\}\{\|\\mathcal\{S\}\|\-1\}, so by the second Borel–Cantelli lemma every pair is selected infinitely often almost surely, converting the eventual\-coverage premise of Corollary[7](https://arxiv.org/html/2608.06762#Thmtheorem7)into a design guarantee; the extrau​\|𝒮\|u\|\\mathcal\{S\}\|proposals per round are linear and leave the sub\-quadratic complexity unchanged for fixeduu\.

Both algorithms share three components, the first two run once per build: an initialization \(lower arm at an under\-estimated0≤dd\_\{0\}\\leq d, either0or the reward pseudo\-metricdR​\(s,s′\):=maxa⁡\|R​\(s,a\)−R​\(s′,a\)\|≤d​\(s,s′\)d\_\{R\}\(s,s^\{\\prime\}\):=\\max\_\{a\}\|R\(s,a\)\-R\(s^\{\\prime\},a\)\|\\leq d\(s,s^\{\\prime\}\); upper arm atDγD\_\{\\gamma\}; both*implicit*, computed on demand inO​\(\|𝒜\|\)O\(\|\\mathcal\{A\}\|\)orO​\(1\)O\(1\)\); an embeddingϕ:𝒮→ℝk\\phi:\\mathcal\{S\}\\to\\mathbb\{R\}^\{k\}by landmark MDS\(Cox and Cox[2001](https://arxiv.org/html/2608.06762#bib.bib45)\)\(Corollary[8](https://arxiv.org/html/2608.06762#Thmtheorem8)\) with an ANN index over\{ϕ​\(s\)\}\\\{\\phi\(s\)\\\}\(random\-hyperplane LSH\(Charikar[2002](https://arxiv.org/html/2608.06762#bib.bib35); Indyk and Motwani[1998](https://arxiv.org/html/2608.06762#bib.bib32)\), equally a product\-quantization or graph index\(Jégouet al\.[2011](https://arxiv.org/html/2608.06762#bib.bib39); Malkov and Yashunin[2020](https://arxiv.org/html/2608.06762#bib.bib37)\)\), one query per state fixingN​\(s\)N\(s\)and hence𝒞\\mathcal\{C\}; and the restricted iteration itself, updating only covered pairs by the exact backup \([1](https://arxiv.org/html/2608.06762#Sx2.E1)\) under the current iterate\.

Index quality is two measured quantities: the additive distortion

η:=maxs,s′⁡\|‖ϕ​\(s\)−ϕ​\(s′\)‖−d​\(s,s′\)\|,\\eta\\;:=\\;\\max\_\{s,s^\{\\prime\}\}\\big\|\\,\\left\\lVert\\phi\(s\)\-\\phi\(s^\{\\prime\}\)\\right\\rVert\-d\(s,s^\{\\prime\}\)\\,\\big\|,\(2\)and the recall missrr, the fraction of a state’s truek′k^\{\\prime\}nearest embedded neighbors the index fails to return\. Under the exact backup these affect*only which pairs are covered*, not covered\-value accuracy \(Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)\(D\)\); they enter the error bound only for index\-side backups that read costs off the embedding \(Assumption[2](https://arxiv.org/html/2608.06762#Thmassumption2), Lemma[12](https://arxiv.org/html/2608.06762#Thmtheorem12)\)\.

The sweep is synchronous, matching Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)’s recursion \(a Gauss–Seidel variant needs a separate asynchronous argument, not analyzed here\); the returned table need not satisfy the triangle inequality under partial coverage, so all guarantees are stated through the exact\-metric enclosure rather than by treating it as a metric in its own right\. Pairs outside𝒞\\mathcal\{C\}retain their frozen value: a top\-k′k^\{\\prime\}index covers at most\|𝒮\|​k′\|\\mathcal\{S\}\|k^\{\\prime\}of\(\|𝒮\|2\)\\binom\{\|\\mathcal\{S\}\|\}\{2\}pairs per build, and the uncovered pairs are an error source unrelated to covered\-pair accuracy, one the two\-armed enclosure makes*visible*\.

## Guarantees

###### Assumption 1\(Bounded transition support\)\.

\|suppP\(⋅∣s,a\)\|≤m\|\\mathrm\{supp\}\\,P\(\\cdot\\mid s,a\)\|\\leq mfor every\(s,a\)\(s,a\), withmmindependent of\|𝒮\|\|\\mathcal\{S\}\|\.

Assumption[1](https://arxiv.org/html/2608.06762#Thmassumption1)is what makes even a*single*exact backup cheap: the transport LP at a covered pair may be solved on the union of the two supports, which is provably identical to the dense\|𝒮\|×\|𝒮\|\|\\mathcal\{S\}\|\\times\|\\mathcal\{S\}\|program \(Lemma[10](https://arxiv.org/html/2608.06762#Thmtheorem10)\) and costscm=O​\(m3​log⁡m\)c\_\{m\}=O\(m^\{3\}\\log m\), independent of\|𝒮\|\|\\mathcal\{S\}\|\. Without it, one dense Kantorovich solve is already super\-linear in\|𝒮\|\|\\mathcal\{S\}\|and no restriction of the*pair sweep*can rescue sub\-quadratic time\.

###### Theorem 1\(Sub\-quadratic complexity\)\.

Suppose Assumption[1](https://arxiv.org/html/2608.06762#Thmassumption1)holds and the ANN index answers ak′k^\{\\prime\}\-neighbor query over\|𝒮\|\|\\mathcal\{S\}\|points in amortized timeq​\(\|𝒮\|\)q\(\|\\mathcal\{S\}\|\)after anO~​\(\|𝒮\|\)\\widetilde\{O\}\(\|\\mathcal\{S\}\|\)build \(LSH and graph\-index instantiations ofqq, Appendix[A](https://arxiv.org/html/2608.06762#A1)\)\. Then Algorithm[2](https://arxiv.org/html/2608.06762#alg2)spendsO​\(\|𝒮\|​\(poly​\(k\)\+q​\(\|𝒮\|\)\)\)O\\\!\\big\(\|\\mathcal\{S\}\|\(\\mathrm\{poly\}\(k\)\+q\(\|\\mathcal\{S\}\|\)\)\\big\)once on lines[3](https://arxiv.org/html/2608.06762#alg2.l3)–[4](https://arxiv.org/html/2608.06762#alg2.l4), andO​\(\|𝒮\|​k′​cm\)O\(\|\\mathcal\{S\}\|\\,k^\{\\prime\}\\,c\_\{m\}\)per sweep thereafter; by Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2),K=O​\(log⁡\(Δ0/ϵ\)/\(1−γ\)\)K=O\\\!\\big\(\\log\(\\Delta\_\{0\}/\\epsilon\)/\(1\-\\gamma\)\\big\)sweeps reach covered\-set accuracyϵ\\epsilon\(beyond the coverage floor\), for total time

O​\(\|𝒮\|​\(poly​\(k\)\+q​\(\|𝒮\|\)\)\+\|𝒮\|​k′​cm1−γ​log⁡Δ0ϵ\),O\\\!\\Big\(\|\\mathcal\{S\}\|\\big\(\\mathrm\{poly\}\(k\)\+q\(\|\\mathcal\{S\}\|\)\\big\)\\;\+\\;\\tfrac\{\|\\mathcal\{S\}\|\\,k^\{\\prime\}\\,c\_\{m\}\}\{1\-\\gamma\}\\log\\tfrac\{\\Delta\_\{0\}\}\{\\epsilon\}\\Big\),which isO~​\(\|𝒮\|1\+ρLSH\+\|𝒮\|/\(1−γ\)\)\\widetilde\{O\}\\\!\\big\(\|\\mathcal\{S\}\|^\{1\+\\rho\_\{\\mathrm\{LSH\}\}\}\+\|\\mathcal\{S\}\|/\(1\-\\gamma\)\\big\)under LSH andO~​\(\|𝒮\|/\(1−γ\)\)\\widetilde\{O\}\\\!\\big\(\|\\mathcal\{S\}\|/\(1\-\\gamma\)\\big\)under a polylogarithmic query oracle: sub\-quadratic in\|𝒮\|\|\\mathcal\{S\}\|in either case, against theΘ​\(\|𝒮\|2​cm\)\\Theta\(\|\\mathcal\{S\}\|^\{2\}\\,c\_\{m\}\)per sweep of the exact algorithm\. Algorithm[1](https://arxiv.org/html/2608.06762#alg1)runs two arms andRRre\-seed rounds, remaining sub\-quadratic for anyR=o​\(\|𝒮\|/q​\(\|𝒮\|\)\)R=o\\big\(\|\\mathcal\{S\}\|/q\(\|\\mathcal\{S\}\|\)\\big\); driving the certificate width to zero*globally*forcesR=Ω​\(\|𝒮\|/k′\)R=\\Omega\(\|\\mathcal\{S\}\|/k^\{\\prime\}\), i\.e\. quadratic total work \(Corollary[7](https://arxiv.org/html/2608.06762#Thmtheorem7)\(d\), full accounting Appendix[A](https://arxiv.org/html/2608.06762#A1)\), which is why the pipeline uses early stopping at a certified tolerance\.

*Proof in Appendix[A](https://arxiv.org/html/2608.06762#A1)\.*

Fix the persistent covered set𝒞\\mathcal\{C\}of Algorithm[2](https://arxiv.org/html/2608.06762#alg2)and an initializationd0≤dd\_\{0\}\\leq d\. Define the*initialization gap*and the*coverage gap*

Δ0:=‖d0−d‖∞,ρ:=max\(s,s′\)∉𝒞⁡\(d​\(s,s′\)−d0​\(s,s′\)\),\\Delta\_\{0\}:=\\left\\lVert d\_\{0\}\-d\\right\\rVert\_\{\\infty\},\\qquad\\rho\\;:=\\;\\max\_\{\(s,s^\{\\prime\}\)\\notin\\mathcal\{C\}\}\\big\(d\(s,s^\{\\prime\}\)\-d\_\{0\}\(s,s^\{\\prime\}\)\\big\),\(3\)the largest initialization error over never\-retrieved pairs \(d0=dRd\_\{0\}=d\_\{R\}provably shrinksρ\\rhorelative tod0=0d\_\{0\}=0\)\.ρ\\rhois defined through the unknown metric and hence*not observable*; the theorems below characterize the error in terms of it, and Corollary[6](https://arxiv.org/html/2608.06762#Thmtheorem6)supplies the computable surrogate\. The naive conjecture‖d^−d‖∞≤ε/\(1−γ\)\\left\\lVert\\hat\{d\}\-d\\right\\rVert\_\{\\infty\}\\leq\\varepsilon/\(1\-\\gamma\)for a per\-step index\-quality termε\\varepsilonignoresρ\\rho, and Proposition[4](https://arxiv.org/html/2608.06762#Thmtheorem4)shows it is false for*every*suchε\\varepsilon\.

The covered\-pair update need not be exact; we allow any backup that approximates one application ofTTuniformly\.

###### Assumption 2\(εop\\varepsilon\_\{\\mathrm\{op\}\}\-approximate covered backup\)\.

There isεop≥0\\varepsilon\_\{\\mathrm\{op\}\}\\geq 0such that the covered\-pair backupBBsatisfies\|B​f​\(s,s′\)−T​f​\(s,s′\)\|≤εop\|Bf\(s,s^\{\\prime\}\)\-Tf\(s,s^\{\\prime\}\)\|\\leq\\varepsilon\_\{\\mathrm\{op\}\}for every\(s,s′\)∈𝒞\(s,s^\{\\prime\}\)\\in\\mathcal\{C\}and every symmetricffwith‖f‖∞≤Dγ\+εop/\(1−γ\)\\left\\lVert f\\right\\rVert\_\{\\infty\}\\leq D\_\{\\gamma\}\+\\varepsilon\_\{\\mathrm\{op\}\}/\(1\-\\gamma\)\. The exact backup of line[9](https://arxiv.org/html/2608.06762#alg2.l9)satisfies this withεop=0\\varepsilon\_\{\\mathrm\{op\}\}=0\.

An index\-side backup that reads costs off the embedding instantiatesεop\\varepsilon\_\{\\mathrm\{op\}\}concretely \(Lemma[12](https://arxiv.org/html/2608.06762#Thmtheorem12), Appendix[B](https://arxiv.org/html/2608.06762#A2)\): perturbing ground\-cost entries by at mostη\\etaand omitting at most anrr\-fraction of probability mass givesεop≤γ​\(η\+r​Dγ\)\\varepsilon\_\{\\mathrm\{op\}\}\\leq\\gamma\(\\eta\+rD\_\{\\gamma\}\), a bound immaterial to the refutation below since Proposition[4](https://arxiv.org/html/2608.06762#Thmtheorem4)\(i\)’s construction hasη=r=0\\eta=r=0while the error isρ0\\rho\_\{0\}\.

###### Theorem 2\(Coverage\-augmented approximation error, anytime form\)\.

Letf0=d0≤df\_\{0\}=d\_\{0\}\\leq dandft\+1=B​ftf\_\{t\+1\}=Bf\_\{t\}on𝒞\\mathcal\{C\},ft\+1=d0f\_\{t\+1\}=d\_\{0\}off𝒞\\mathcal\{C\}, under Assumption[2](https://arxiv.org/html/2608.06762#Thmassumption2)\. Writeet:=max\(s,s′\)∈𝒞⁡\|ft​\(s,s′\)−d​\(s,s′\)\|e\_\{t\}:=\\max\_\{\(s,s^\{\\prime\}\)\\in\\mathcal\{C\}\}\|f\_\{t\}\(s,s^\{\\prime\}\)\-d\(s,s^\{\\prime\}\)\|\. Then for everyt≥0t\\geq 0:

1. *\(A\)**\(covered\)*et≤max⁡\(εop1−γ,εop\+γ​ρ\)\+γt​Δ0\\;e\_\{t\}\\;\\leq\\;\\max\\\!\\Big\(\\dfrac\{\\varepsilon\_\{\\mathrm\{op\}\}\}\{1\-\\gamma\},\\ \\varepsilon\_\{\\mathrm\{op\}\}\+\\gamma\\rho\\Big\)\\;\+\\;\\gamma^\{t\}\\,\\Delta\_\{0\};
2. *\(B\)**\(global\)*‖ft−d‖∞≤max⁡\(ρ,εop1−γ\)\+γt​Δ0\\;\\left\\lVert f\_\{t\}\-d\\right\\rVert\_\{\\infty\}\\;\\leq\\;\\max\\\!\\Big\(\\rho,\\ \\dfrac\{\\varepsilon\_\{\\mathrm\{op\}\}\}\{1\-\\gamma\}\\Big\)\\;\+\\;\\gamma^\{t\}\\,\\Delta\_\{0\}, and every limit pointd^\\hat\{d\}of\(ft\)\(f\_\{t\}\)satisfies‖d^−d‖∞≤max⁡\(ρ,εop/\(1−γ\)\)\\left\\lVert\\hat\{d\}\-d\\right\\rVert\_\{\\infty\}\\leq\\max\\\!\\big\(\\rho,\\ \\varepsilon\_\{\\mathrm\{op\}\}/\(1\-\\gamma\)\\big\);
3. *\(C\)**\(full coverage\)*if𝒞=𝒮×𝒮\\mathcal\{C\}=\\mathcal\{S\}\\times\\mathcal\{S\}thenρ=0\\rho=0and*\(B\)*reads‖ft−d‖∞≤εop/\(1−γ\)\+γt​Δ0\\left\\lVert f\_\{t\}\-d\\right\\rVert\_\{\\infty\}\\leq\\varepsilon\_\{\\mathrm\{op\}\}/\(1\-\\gamma\)\+\\gamma^\{t\}\\Delta\_\{0\};
4. *\(D\)**\(exact backup\)*ifBBis the exact backup of line[9](https://arxiv.org/html/2608.06762#alg2.l9)andd0∈\{0,dR\}d\_\{0\}\\in\\\{0,d\_\{R\}\\\}\(any sub\-solution,B​d0≥d0Bd\_\{0\}\\geq d\_\{0\}on𝒞\\mathcal\{C\}\), thenftf\_\{t\}increases monotonically to the unique fixed pointd^\\hat\{d\}of the restricted iteration \(Lemma[11](https://arxiv.org/html/2608.06762#Thmtheorem11)\), withd0≤d^≤dd\_\{0\}\\leq\\hat\{d\}\\leq dpointwise andmax𝒞⁡\|d^−d\|≤γ​ρ\\;\\max\_\{\\mathcal\{C\}\}\|\\hat\{d\}\-d\|\\leq\\gamma\\rho: index quality affects only*which*pairs are covered, never the accuracy of covered values\.

*Proof in Appendix[B](https://arxiv.org/html/2608.06762#A2)\.*The exact\-backup case admits an identity, not merely a bound; it shows the global bound in \(B\) is*tight*, and it is what the experiments verify to machine precision\.

###### Corollary 3\(Exact coverage identity\)\.

Under Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)\(D\),‖d^−d‖∞=ρ\\;\\left\\lVert\\hat\{d\}\-d\\right\\rVert\_\{\\infty\}=\\rho\.

*Proof in Appendix[B](https://arxiv.org/html/2608.06762#A2)\.*The identity cuts two ways: the frozen block does not merely bound the error, it*is*the error, however good the index; yet becauseρ\\rhois defined through the unknowndd, it*characterizes*the error without*certifying*it, which is what Corollary[6](https://arxiv.org/html/2608.06762#Thmtheorem6)’s two\-sided construction is for \(why per\-step bounds alone cannot capture this: §[Discussion](https://arxiv.org/html/2608.06762#Sx6)\)\. The following lower bound shows theρ\\rhoterm is not loose slack but*necessary*for the index\-first class Algorithm[2](https://arxiv.org/html/2608.06762#alg2)belongs to, and that adaptivity buys at most a quadratic\-to\-linear reduction, not exemption\.

###### Proposition 4\(The coverage gap is unavoidable\)\.

Work in the pair\-evaluation model: evaluating a pair\(s,t\)\(s,t\)reveals the per\-action reward differences\{\|R​\(s,a\)−R​\(t,a\)\|\}a\\\{\|R\(s,a\)\-R\(t,a\)\|\\\}\_\{a\}and the transported costs for that pair \(all kernels identical in the constructions below, so every transported cost is0regardless of ground cost or transport convention\)\. Fix anyρ0∈\(0,L\]\\rho\_\{0\}\\in\(0,L\]\.

1. *\(i\)**\(Oblivious coverage\.\)*Let the evaluated pair setQQbe selected without access to the reward function \(fixed in advance, or computed from transition/embedding data; randomization allowed\), with𝔼​\|Q\|=o​\(\|𝒮\|2\)\\mathbb\{E\}\|Q\|=o\(\|\\mathcal\{S\}\|^\{2\}\)\. Then there are two MDPs, indistinguishable on every evaluated quantity, whose exact metrics differ byρ0\\rho\_\{0\}on an unevaluated pair; any output computable from the evaluations errs by at leastρ0/2\\rho\_\{0\}/2on one of them \(\(1−o​\(1\)\)​ρ0/2\(1\-o\(1\)\)\\,\\rho\_\{0\}/2in expectation under randomization\), regardless of how unevaluated pairs are assigned\.
2. *\(ii\)**\(Adaptive coverage\.\)*There is a family of MDPs with\|𝒜\|=⌊\|𝒮\|/2⌋\|\\mathcal\{A\}\|=\\lfloor\|\\mathcal\{S\}\|/2\\rflooractions on which*every*algorithm \(adaptive and randomized\) that performs fewer than⌊\|𝒮\|/2⌋\\lfloor\|\\mathcal\{S\}\|/2\\rfloorpair evaluations suffers𝔼​‖d^−d‖∞≥ρ0/2\\mathbb\{E\}\\,\\left\\lVert\\hat\{d\}\-d\\right\\rVert\_\{\\infty\}\\geq\\rho\_\{0\}/2\.

Consequently theρ\\rhoterm of Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)\(B\) cannot be removed for oblivious coverage, and Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3)shows it is achieved with equality; adaptive schemes needΩ​\(\|𝒮\|\)\\Omega\(\|\\mathcal\{S\}\|\)evaluations even on this family, with the known adaptive route to exactness degenerating to quadratic work through dependency closure \(§[Discussion](https://arxiv.org/html/2608.06762#Sx6)\); a super\-linear adaptive lower bound remains open\. Since the two instances of \(i\) are indistinguishable, no computable certificate can be tight on unevaluated pairs: the certificate of Corollary[6](https://arxiv.org/html/2608.06762#Thmtheorem6)is exact in its*validity*while its*width*there honestly reports the full prior interval\.

*Proof in Appendix[C](https://arxiv.org/html/2608.06762#A3)\.*We verify construction \(i\) directly \(Appendix[C](https://arxiv.org/html/2608.06762#A3), Table[3](https://arxiv.org/html/2608.06762#A3.T3)\): the realized global error equals the planted gap exactly \(correlation1\.01\.0\), and at fixed budgetk′=8k^\{\\prime\}=8it stays pinned atρ0\\rho\_\{0\}as coverage falls from42%42\\%at\|𝒮\|=20\|\\mathcal\{S\}\|=20to5%5\\%at\|𝒮\|=160\|\\mathcal\{S\}\|=160, while full coverage drives it to0\.

### Two\-Sided Certificates and Downstream Aggregation

Sinceρ\\rhois unobservable \(Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)\(B\), Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3)\), is the metric still useful for state abstraction\(Fernset al\.[2004](https://arxiv.org/html/2608.06762#bib.bib3); Liet al\.[2006](https://arxiv.org/html/2608.06762#bib.bib17)\)\(merge states belowτ\\tau, solve the aggregated MDP\)? Far pairs drivingρ\\rhoshould never be merged, but this holds only under an*upper\-bound*treatment of un\-retrieved pairs; under the lower arm’s under\-estimate, a frozen pair reads as near\-identical instead\. The upper arm repairs this; pairing both yields the computable certificate\.

###### Proposition 5\(The upper arm: over\-estimation and conservative aggregation\)\.

Run the restricted iteration with the exact backup, initializing*all*entries at the constant upper boundU:=Dγ=L/\(1−γ\)U:=D\_\{\\gamma\}=L/\(1\-\\gamma\)and freezing un\-retrieved pairs atUU\(UUcomputable inO​\(1\)O\(1\),U≥dU\\geq dpointwise, no quadratic diameter computation needed\)\. Writeft\+f\_\{t\}^\{\+\}for the iterates,d^\+\\hat\{d\}^\{\+\}for the limit, andρ\+:=max\(s,s′\)∉𝒞⁡\(U−d​\(s,s′\)\)\\rho^\{\+\}:=\\max\_\{\(s,s^\{\\prime\}\)\\notin\\mathcal\{C\}\}\(U\-d\(s,s^\{\\prime\}\)\)\. Then:

1. *\(i\)*the iterates decrease monotonically and every iterate, henced^\+\\hat\{d\}^\{\+\}, is a pointwise*over*\-estimate:ft\+≥d^\+≥df\_\{t\}^\{\+\}\\geq\\hat\{d\}^\{\+\}\\geq deverywhere;
2. *\(ii\)*for anyτ<U\\tau<U, every directly linked pair \(d^\+​\(s,s′\)≤τ\\hat\{d\}^\{\+\}\(s,s^\{\\prime\}\)\\leq\\tau, necessarily covered\) hasd​\(s,s′\)≤τd\(s,s^\{\\prime\}\)\\leq\\tau, so the single\-linkage clustering ofd^\+\\hat\{d\}^\{\+\}atτ\\tau*refines*the exact metric’s: everyd^\+\\hat\{d\}^\{\+\}\-cluster lies in add\-cluster;
3. *\(iii\)*so any value\-loss certificate monotone in within\-cluster diameter\(Liet al\.[2006](https://arxiv.org/html/2608.06762#bib.bib17); Ferns and Precup[2014](https://arxiv.org/html/2608.06762#bib.bib6)\)certifies a loss ford^\+\\hat\{d\}^\{\+\}\-aggregation no larger than for exact\-metric aggregation atτ\\tau;
4. *\(iv\)**\(mirror of Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)\(D\) and Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3)\)*at the fixed point,max𝒞⁡\(d^\+−d\)≤γ​ρ\+\\max\_\{\\mathcal\{C\}\}\(\\hat\{d\}^\{\+\}\-d\)\\leq\\gamma\\rho^\{\+\}and‖d^\+−d‖∞=ρ\+\\left\\lVert\\hat\{d\}^\{\+\}\-d\\right\\rVert\_\{\\infty\}=\\rho^\{\+\}\.

*Proof in Appendix[D](https://arxiv.org/html/2608.06762#A4)\.*

The two arms are complementary, the lower under\-estimating with errorρ\\rhoand the upper over\-estimating withρ\+\\rho^\{\+\}, neither observable alone; run together, they observe each other\.

###### Corollary 6\(Anytime two\-sided certificate\)\.

Run the lower arm \(ft−f\_\{t\}^\{\-\}: exact backup, initializationd0∈\{0,dR\}d\_\{0\}\\in\\\{0,d\_\{R\}\\\}, Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)\(D\)\) and upper arm \(ft\+f\_\{t\}^\{\+\}: Proposition[5](https://arxiv.org/html/2608.06762#Thmtheorem5)\) on the same covered sets, including under Corollary[7](https://arxiv.org/html/2608.06762#Thmtheorem7)’s re\-seeded schedule where𝒞\\mathcal\{C\}grows\. Then:

1. *\(a\)**\(anytime sandwich\)*ft−≤d≤ft\+f\_\{t\}^\{\-\}\\leq d\\leq f\_\{t\}^\{\+\}pointwise for everytt, withft−f\_\{t\}^\{\-\}nondecreasing andft\+f\_\{t\}^\{\+\}nonincreasing, so\[ft−​\(p\),ft\+​\(p\)\]\[f\_\{t\}^\{\-\}\(p\),f\_\{t\}^\{\+\}\(p\)\]is a valid, shrinking interval ford​\(p\)d\(p\)at every sweep and pair;
2. *\(b\)**\(computable certificate\)*the widthwt:=ft\+−ft−≥0w\_\{t\}:=f\_\{t\}^\{\+\}\-f\_\{t\}^\{\-\}\\geq 0is computable from the two runs, with\|ft±​\(p\)−d​\(p\)\|≤wt​\(p\)\|f\_\{t\}^\{\\pm\}\(p\)\-d\(p\)\|\\leq w\_\{t\}\(p\)for everypp; on uncovered pairswt​\(p\)=U−d0​\(p\)w\_\{t\}\(p\)=U\-d\_\{0\}\(p\)exactly, so the coverage frontier is visible in the certificate itself;
3. *\(c\)**\(limit width on covered pairs\)*at the fixed points,w∞​\(p\)≤γ​\(ρ\+ρ\+\)w\_\{\\infty\}\(p\)\\leq\\gamma\(\\rho\+\\rho^\{\+\}\)for everyp∈𝒞p\\in\\mathcal\{C\}, by Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)\(D\) and Proposition[5](https://arxiv.org/html/2608.06762#Thmtheorem5)\(iv\);
4. *\(d\)**\(certified aggregation\)*forτ<U\\tau<U, the single\-linkage clusteringsΠτ\+,Πτ−\\Pi^\{\+\}\_\{\\tau\},\\Pi^\{\-\}\_\{\\tau\}offt\+,ft−f\_\{t\}^\{\+\},f\_\{t\}^\{\-\}over covered pairs bracketΠτ𝒞\\Pi^\{\\mathcal\{C\}\}\_\{\\tau\}\(the exact metric’s covered clustering\):Πτ\+\\Pi^\{\+\}\_\{\\tau\}refinesΠτ𝒞\\Pi^\{\\mathcal\{C\}\}\_\{\\tau\}, which refinesΠτ−\\Pi^\{\-\}\_\{\\tau\}; ifΠτ\+=Πτ−\\Pi^\{\+\}\_\{\\tau\}=\\Pi^\{\-\}\_\{\\tau\}, both equalΠτ𝒞\\Pi^\{\\mathcal\{C\}\}\_\{\\tau\}, recovering it*with certainty*without computingdd\. Under re\-seeding,𝒞→𝒮×𝒮\\mathcal\{C\}\\to\\mathcal\{S\}\\times\\mathcal\{S\}andΠτ𝒞\\Pi^\{\\mathcal\{C\}\}\_\{\\tau\}becomes the full exact clustering\.

*Proof in Appendix[D](https://arxiv.org/html/2608.06762#A4)\.*This turns Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3)’s identity into an operational tool: Algorithm[1](https://arxiv.org/html/2608.06762#alg1)re\-seeds until the width meets tolerance orΠτ\+=Πτ−\\Pi^\{\+\}\_\{\\tau\}=\\Pi^\{\-\}\_\{\\tau\}\(Corollary[7](https://arxiv.org/html/2608.06762#Thmtheorem7)guarantees both eventually\), at the price of a factor of two in sweep cost and an honesty on uncovered pairs Proposition[4](https://arxiv.org/html/2608.06762#Thmtheorem4)shows cannot be tightened\.

###### Corollary 7\(Anytime refinement via re\-seeding\)\.

Let Algorithm[1](https://arxiv.org/html/2608.06762#alg1)rebuild the index with fresh randomness, re\-embed the lower iterate everyEEsweeps, retain cumulative coverage, run both exact\-backup arms, with any fixed exploration countu≥1u\\geq 1\. Then: \(a\) lower iterates remain monotone nondecreasing and bounded bydd, upper iterates monotone nonincreasing and bounded below bydd, so Corollary[6](https://arxiv.org/html/2608.06762#Thmtheorem6)\(a\)’s sandwich holds at every step; \(b\) every pair is retrieved infinitely often almost surely, so both limits equal the exact metric by asynchronous fixed\-point convergence for monotone sup\-norm contractions\(Bertsekas and Tsitsiklis[1996](https://arxiv.org/html/2608.06762#bib.bib51)\); \(c\) at every finite horizon, Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2), Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3), and Proposition[5](https://arxiv.org/html/2608.06762#Thmtheorem5)\(iv\) apply to the cumulative set𝒞t\\mathcal\{C\}\_\{t\}and its nonincreasing gapsρt,ρt\+\\rho\_\{t\},\\rho^\{\+\}\_\{t\}; and \(d\) zero global width still requires\(\|𝒮\|2\)\\binom\{\|\\mathcal\{S\}\|\}\{2\}cumulative retrievals, henceΩ​\(\|𝒮\|2\)\\Omega\(\|\\mathcal\{S\}\|^\{2\}\)total work\.

Re\-seeding ablations at\|𝒮\|=18\|\\mathcal\{S\}\|=18confirm part \(b\): pure\-LSH alone saturates below full coverage \(near\-neighbor bias misses the far pairs settingρ\\rho\), while adding one uniform partner per state reaches full coverage andΠτ\+=Πτ−\\Pi^\{\+\}\_\{\\tau\}=\\Pi^\{\-\}\_\{\\tau\}within ten rounds \(Appendix[G](https://arxiv.org/html/2608.06762#A7)\)\.

## Experiments

The experiments validate Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2), Corollaries[3](https://arxiv.org/html/2608.06762#Thmtheorem3)and[6](https://arxiv.org/html/2608.06762#Thmtheorem6), and Proposition[4](https://arxiv.org/html/2608.06762#Thmtheorem4)where every named quantity is exactly measurable, and exhibit the naive bound’s coverage failure\. Bound\-validation instances are small and CPU\-only of necessity, since the exact Wasserstein LP per pair\-action is an optimal\-transport problem: random MDPs with\|𝒮\|∈\{10,18\}\|\\mathcal\{S\}\|\\in\\\{10,18\\\},\|𝒜\|=3\|\\mathcal\{A\}\|=3,γ=0\.7\\gamma=0\.7, rewards rescaled soL=1L=1,1010seeds per configuration,95%95\\%confidence intervals; a separate timing study reaches\|𝒮\|\|\\mathcal\{S\}\|up to16001600\(cheap cost\) and400400\(fullW1W\_\{1\}\), and Taxi and a25002500\-state gridworld exercise the full pipeline\. Appendix[J](https://arxiv.org/html/2608.06762#A10.SSx1)details infrastructure, seeding, and the number of runs behind every reported result\.

Each component is implemented exactly as stated, with no surrogate: a*true*Wasserstein\-1 backup by Kantorovich LP under the current iterate \(εop=0\\varepsilon\_\{\\mathrm\{op\}\}=0, so Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)\(D\), Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3), Proposition[5](https://arxiv.org/html/2608.06762#Thmtheorem5)\(iv\) apply\), a real MDS embedding with distortionη\\etameasured pairwise, and a real random\-hyperplane LSH index with recall missrrmeasured against true nearest neighbors \(full protocol, Appendix[E](https://arxiv.org/html/2608.06762#A5)\)\. Across the eight\-configuration grid, mean distortion isη=0\.107\\eta=0\.107and coverage gap averagesρ=1\.16\\rho=1\.16underd0=0d\_\{0\}=0, shrinking to0\.730\.73\(ratio0\.630\.63\) underd0=dRd\_\{0\}=d\_\{R\}, as predicted\.

The per\-step\-only conjecture is already refuted unconditionally by Proposition[4](https://arxiv.org/html/2608.06762#Thmtheorem4)\(i\) withη=r=0\\eta=r=0; Table[1](https://arxiv.org/html/2608.06762#Sx5.T1)audits the conventional quantity\(η\+L​r\)/\(1−γ\)\(\\eta\+Lr\)/\(1\-\\gamma\)on eight configurations \(L=1L=1,γ=0\.7\\gamma=0\.7\)\. Two rows \(\|𝒮\|=10,k′=6\|\\mathcal\{S\}\|=10,k^\{\\prime\}=6\) violate it \(naive0\.803,1\.0610\.803,1\.061against realized error1\.10,1\.141\.10,1\.14, since1313and1010of4545pairs are never updated\); across the full8080\-run grid it fails in11/8011/80\(13\.75%13\.75\\%\), while the corrected bound, the exact identity‖d^−d‖∞=ρ\\left\\lVert\\hat\{d\}\-d\\right\\rVert\_\{\\infty\}=\\rho, and the sandwich enclosure hold in*every*run, the identity to machine precision, covered error never exceedingγ​ρ\\gamma\\rho\(largest row mean0\.330\.33\)\. Figures[3](https://arxiv.org/html/2608.06762#A6.F3)–[4](https://arxiv.org/html/2608.06762#A6.F4)\(Appendix[F](https://arxiv.org/html/2608.06762#A6)\) plot these values from the table below\.

Table 1:Synchronized exact\-operator audit \(1010seeds per configuration,8080runs\)\. “pl\.” is the number of LSH hyperplanes; “never” counts uncovered unordered pairs; “work” isk′/\|𝒮\|k^\{\\prime\}/\|\\mathcal\{S\}\|; “naive” is\(η\+L​r\)/\(1−γ\)\(\\eta\+Lr\)/\(1\-\\gamma\)withL=1L=1andγ=0\.7\\gamma=0\.7; and “corrected” ismax⁡\{ρ,naive\}\\max\\\{\\rho,\\text\{naive\}\\\}\. The two\|𝒮\|=10,k′=6\|\\mathcal\{S\}\|=10,k^\{\\prime\}=6rows violate the naive expression but satisfy the corrected bound\. Global error equalsρ\\rhoin every row, and covered error remains belowγ​ρ\\gamma\\rho\. Figures[3](https://arxiv.org/html/2608.06762#A6.F3)and[4](https://arxiv.org/html/2608.06762#A6.F4)use this exact row order\.The restricted sweep’s work ratiok′/\|𝒮\|k^\{\\prime\}/\|\\mathcal\{S\}\|ranges0\.170\.17–0\.600\.60\(Table[1](https://arxiv.org/html/2608.06762#Sx5.T1)\), matching Theorem[1](https://arxiv.org/html/2608.06762#Thmtheorem1); on these small instances the exact LP dominates runtime, so operation count, not wall clock, is relevant\. A dedicated timing study isolates pair\-visit scaling directly \(Table[2](https://arxiv.org/html/2608.06762#Sx5.T2)\): cheap ground cost across\|𝒮\|∈\{50,…,1600\}\|\\mathcal\{S\}\|\\in\\\{50,\\dots,1600\\\}gives log\-log exponents1\.911\.91exact versus1\.411\.41ANN, speedup1\.2×→7\.2×1\.2\\times\\to 7\.2\\times\(Figure[2](https://arxiv.org/html/2608.06762#A1.F2), Appendix[A](https://arxiv.org/html/2608.06762#A1)\); the full exact\-Wasserstein operator across\|𝒮\|∈\{50,…,400\}\|\\mathcal\{S\}\|\\in\\\{50,\\dots,400\\\}\(union\-support LP, Lemma[10](https://arxiv.org/html/2608.06762#Thmtheorem10), gap0\.00\.0\) gives exponents2\.022\.02versus1\.001\.00, speedup3\.1×→25\.5×3\.1\\times\\to 25\.5\\times, covered\-pair error bounded byγ​ρ\\gamma\\rhothroughout \(realized≤0\.006\\leq 0\.006\), as Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3)predicts\.

Table 2:Wall\-clock per\-sweep cost, exact all\-pairs versus ANN top\-k′k^\{\\prime\}\. “cheap cost” uses a fixed shared ground cost so the pair\-visit count alone drives runtime; “fullW1W\_\{1\}” solves the exact Kantorovich transport LP per pair\-action on the union of supports, identical to the dense LP by Lemma[10](https://arxiv.org/html/2608.06762#Thmtheorem10)\(verified numerically, gap0\.00\.0\), withk′=8k^\{\\prime\}=8\. Covered\-pair error is bounded byγ​ρ\\gamma\\rhothroughout \(Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)\(D\)\)\.On the same eight configurations, the two\-arm sandwich holds \(ft−≤d≤ft\+f\_\{t\}^\{\-\}\\leq d\\leq f\_\{t\}^\{\+\}in80/8080/80runs\), both one\-sided identities hold to machine precision, andΠτ\+=Πτ−\\Pi^\{\+\}\_\{\\tau\}=\\Pi^\{\-\}\_\{\\tau\}is rare at a single build \(9/2409/240,3\.7%3\.7\\%\) but reached under re\-seeding in two of three seeds within1010rounds \(Appendix[G](https://arxiv.org/html/2608.06762#A7)\)\. The full pipeline \(re\-seeding everyE=3E=3sweeps,3232configurations\) matches or beats the one\-shot variant in32/3232/32runs \(mean error0\.220\.22vs1\.181\.18\), trackingmax⁡\(ρt,et\)\\max\(\\rho\_\{t\},e\_\{t\}\)exactly as Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3)predicts \(Appendix[G](https://arxiv.org/html/2608.06762#A7)\)\. A budget\-matched random\-coverage baseline gives a nearly identical coverage gap to ANN \(ρ\\rhoratio1\.041\.04\), confirmingρ\\rhois a property of the budget, not the index; with the upper arm, ANN’s near\-neighbor bias still cuts mean\-pair error2\.5×2\.5\\timesover random \(0\.54→0\.210\.54\\to 0\.21\)\. At larger scale \(\|𝒮\|∈\{50,100,200\}\|\\mathcal\{S\}\|\\in\\\{50,100,200\\\}, Appendix[H](https://arxiv.org/html/2608.06762#A8)\) the identity again holds in30/3030/30runs, while the naive bound, never violated there, is merely*vacuous*: with fixed embedding dimension,η\\etagrows with\|𝒮\|\|\\mathcal\{S\}\|, pushing the naive expression past the metric diameter\. At\|𝒮\|=120\|\\mathcal\{S\}\|=120\(Appendix[H](https://arxiv.org/html/2608.06762#A8)\), the upper\-arm ANN metric matches exact\-metric aggregation statistically \(loss0\.022±0\.0080\.022\\pm 0\.008against0\.022±0\.0080\.022\\pm 0\.008, mean12\.812\.8clusters against1212\), while under\-estimate and reward\-only baselines collapse to one cluster \(loss1\.47±0\.551\.47\\pm 0\.55\)\.

On Gymnasium Taxi\-v3 \(\|𝒮\|=500\|\\mathcal\{S\}\|=500, deterministic,γ=0\.9\\gamma=0\.9\), the post\-hoc lower\-arm identity givesρ=180\.4\\rho=180\.4, close to the exact diameter200\.5200\.5, unavailable at run time; the observable sandwich stays wide \(coverage only5%5\\%–20%20\\%\), so the conservative upper arm certifies no unsupported merges and the pipeline abstains, while an uncertified diagnostic on the raw embedding collapses to one cluster \(loss45\.945\.9against15\.815\.8exact; exact computation takes0\.70\.7s\)\. At a scale where the exact sweep is genuinely prohibitive \(\|𝒮\|=2500\|\\mathcal\{S\}\|=2500,\(25002\)≈3\.12\\binom\{2500\}\{2\}\\approx 3\.12M pairs,2525planted rooms, learnedℝ8\\mathbb\{R\}^\{8\}embedding\),88upper\-freeze sweeps atk′=20k^\{\\prime\}=20\(12\.8%12\.8\\%of one sweep,≈1200\\approx 1200s\) recover254254–284284over\-fragmented clusters with mean loss2\.272\.27against a reward\-only baseline’s3\.183\.18, a28\.6%28\.6\\%improvement \(full detail, Appendix[I](https://arxiv.org/html/2608.06762#A9)\)\.

#### Comparison to learned surrogates \(MICo, DBC\)\.

MICo\(Castroet al\.[2021](https://arxiv.org/html/2608.06762#bib.bib24)\)and DBC\(Zhanget al\.[2021](https://arxiv.org/html/2608.06762#bib.bib26)\)are trained independently with their published objectives on grouped MDPs \(\|𝒮\|=64\|\\mathcal\{S\}\|=64, eight planted groups,\|𝒜\|=3\|\\mathcal\{A\}\|=3,γ=0\.9\\gamma=0\.9\); our method uses their encoder only as an ANN index, then applies the exact restricted backup, so the comparison is independently trained surrogates versus exact\-operator refinement, not three methods sharing one distance\.

Sweeping retrieval budget over four seeds per point \(Table[5](https://arxiv.org/html/2608.06762#A10.T5), Appendix[J](https://arxiv.org/html/2608.06762#A10)\): atk′=8k^\{\\prime\}=8\(25%25\\%coverage\) our loss is0\.0560\.056, reaching the exact\-metric skyline \(0\.0130\.013\) once coverage passes half \(k′≥16k^\{\\prime\}\\geq 16\), while MICo and DBC stay2222–33×33\\timesworse \(0\.2920\.292,0\.4260\.426\) at every budget, and the two\-arm interval encloses the exact metric in all1616runs, which neither surrogate provides\.

The claim is benchmark\-scoped: a larger check at\|𝒮\|∈\{60,120\}\|\\mathcal\{S\}\|\\in\\\{60,120\\\}shows the same coverage percentage need not give the same loss across state counts and geometries \(loss1\.081\.08against a0\.0260\.026skyline at\|𝒮\|=120\|\\mathcal\{S\}\|=120, below the coverage that reaches it\), and a finer sweep at fixed\|𝒮\|=60\|\\mathcal\{S\}\|=60confirms the same half\-of\-pairs crossover \(53\.5%53\.5\\%\) while MICo and DBC stay flat, never enclosing the exact metric \(full detail, Appendix[J](https://arxiv.org/html/2608.06762#A10)\)\.

## Discussion

#### Why the naive bound is so tempting, and so wrong\.

The clean boundε/\(1−γ\)\\varepsilon/\(1\-\\gamma\)mechanically combines per\-step perturbations with the contraction, correct exactly where the contraction acts \(Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)’sεop/\(1−γ\)\\varepsilon\_\{\\mathrm\{op\}\}/\(1\-\\gamma\)branch, collapsing toγ​ρ\\gamma\\rhoon covered pairs for the exact backup\)\. It forgets the operator never touches uncovered pairs: unlike the usual approximation\-error story where every coordinate updates imperfectly, here aΘ​\(\|𝒮\|2\)\\Theta\(\|\\mathcal\{S\}\|^\{2\}\)block is frozen, and Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3)shows that block does not merely bound the error, it*is*the error\. Any scheme restricting a global fixed point to a sparse retrieved set must account for un\-retrieved coordinates separately from retrieved quality; a monotone two\-sided enclosure \(Corollary[6](https://arxiv.org/html/2608.06762#Thmtheorem6)\) is the generic repair wherever the operator is monotone with known sub\- and super\-solutions\.

#### What the guarantee does and does not say\.

Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)bounds iterate and metric error against the exact metric, not downstream value or policy error, though Proposition[5](https://arxiv.org/html/2608.06762#Thmtheorem5)composes it with standard abstraction certificates\(Ferns and Precup[2014](https://arxiv.org/html/2608.06762#bib.bib6); Liet al\.[2006](https://arxiv.org/html/2608.06762#bib.bib17)\)\.ρ\\rhois*characterized*exactly \(Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3)\) but*not observable*, so the pipeline exposes the sandwich width instead; derivingρ\\rhofrom index parameters under a distributional embedding assumption remains open\. The complexity result is a worst\-case count under an explicit query oracleq​\(⋅\)q\(\\cdot\), inheriting the chosen index’s recall\-speed trade\-off, unoptimized here\. Proposition[4](https://arxiv.org/html/2608.06762#Thmtheorem4)’s adaptive side is deliberately modest:Ω​\(\|𝒮\|\)\\Omega\(\|\\mathcal\{S\}\|\)evaluations are necessary even adaptively, the obliviousΘ​\(\|𝒮\|2\)\\Theta\(\|\\mathcal\{S\}\|^\{2\}\)barrier is real for the index\-first class, and the fully adaptive super\-linear question is open\.

#### The choice of index and the recall–coverage distinction\.

Recallrris*per\-state*, driven down by a better index \(more hyperplanes, a graph structure\(Malkov and Yashunin[2020](https://arxiv.org/html/2608.06762#bib.bib37)\), product quantization\(Jégouet al\.[2011](https://arxiv.org/html/2608.06762#bib.bib39)\)\); coverage is*global and cumulative*: a top\-k′k^\{\\prime\}scheme proposes at mostk′k^\{\\prime\}per state, so even perfect recall covers onlyO​\(\|𝒮\|​k′\)O\(\|\\mathcal\{S\}\|k^\{\\prime\}\)pairs, leaving a quadratic remainder frozen\. Under the exact backup the separation is total: Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)\(D\) says index quality affects only coverage, so only the retrieval policy, not the index, can fix the error floor \(Corollary[7](https://arxiv.org/html/2608.06762#Thmtheorem7)\)\. Our verification fixes the index family \(LSH\) and varies granularity: recall miss ranges0\.540\.54to0\.220\.22while global error stays pinned atρ≈1\.16\\rho\\approx 1\.16\.

#### Relation to learned surrogates\.

Scalable methods\(Castro[2020](https://arxiv.org/html/2608.06762#bib.bib23); Castroet al\.[2021](https://arxiv.org/html/2608.06762#bib.bib24); Zhanget al\.[2021](https://arxiv.org/html/2608.06762#bib.bib26)\)replace the metric with a learned distance, accepting it may not be the true one; we keep the exact operator and approximate only the sweep, controlling error relative to the true metric\. The two are complementary: a learned embedding of the kind those methods produce is precisely the index we need, and feeding it into Algorithm[1](https://arxiv.org/html/2608.06762#alg1)recovers a metric certifiably \(Corollary[6](https://arxiv.org/html/2608.06762#Thmtheorem6)\) related to the true one, not merely empirically useful; as Taxi shows, the certificate also flags uninformative embeddings at run time\. The kernel perspectives ofCastroet al\.\([2023](https://arxiv.org/html/2608.06762#bib.bib25)\); Le Lanet al\.\([2021](https://arxiv.org/html/2608.06762#bib.bib29),[2022](https://arxiv.org/html/2608.06762#bib.bib31)\)suggest such embeddings are often low\-distortion in Corollary[8](https://arxiv.org/html/2608.06762#Thmtheorem8)’s sense, so cheap\-embedding regimes are ones those methods already occupy\.

#### On\-demand exactness degenerates to quadratic\.

The on\-the\-fly exact method ofBacciet al\.\([2013a](https://arxiv.org/html/2608.06762#bib.bib14),[b](https://arxiv.org/html/2608.06762#bib.bib15)\)computes the metric on a query setQQvia dependency closure \(BFS fromQQthrough transition supports to convergence\), the natural*adaptive*competitor of Proposition[4](https://arxiv.org/html/2608.06762#Thmtheorem4)\(ii\)\. On sparse\-support MDPs \(\|𝒮\|∈\{50,100\}\|\\mathcal\{S\}\|\\in\\\{50,100\\\}, support44,k′=12k^\{\\prime\}=12\) the closure saturates to100%100\\%of all pairs from a few hundred queries, since random supports mix every pair in within a few BFS steps \(425425–452452s versus1313–1717s for ANN,2525–33×33\\times\)\. The trade is exactness for time: on\-demand is exact onQQ, the ANN lower arm exactlyρ\\rho\(Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3)\); once a transition graph mixes, as any connected tabular MDP does, the closure propagates everywhere and on\-demand exactness degenerates to the full quadratic sweep\. Algorithm[1](https://arxiv.org/html/2608.06762#alg1)escapes this by*not*chasing exactness on unvisited pairs, a price Proposition[4](https://arxiv.org/html/2608.06762#Thmtheorem4)\(i\)\-\(ii\) shows unavoidable for index\-first and \(linearly\) adaptive selection alike, made visible by the certificate\.

## Conclusion

Bisimulation metrics admit sub\-quadratic, certificate\-carrying approximation: a low\-dimensional index selects pairs, and the exact restricted operator runs from both sides\. Coverage, not index quality, bounds global error: skipped pairs set the anytime limitmax⁡\(ρ,εop/\(1−γ\)\)\\max\(\\rho,\\varepsilon\_\{\\mathrm\{op\}\}/\(1\-\\gamma\)\), an equality under exact backups, and the sandwich width certifies per\-pair uncertainty and the covered clustering\. Lower bounds are quadratic for reward\-oblivious index\-first coverage,Ω​\(\|𝒮\|\)\\Omega\(\|\\mathcal\{S\}\|\)for fully adaptive evaluation \(super\-linear open\)\. Experiments confirm identity and enclosure in every seed, sub\-quadratic wall\-clock scaling \(to25\.5×25\.5\\times\), MICo and DBC2222–33×33\\timesabove the skyline we reach at half coverage, abstention on Taxi’s weak embedding, and28\.6%28\.6\\%lower value loss at\|𝒮\|=2500\|\\mathcal\{S\}\|=2500for12\.8%12\.8\\%of one sweep\.

## References

- D\. Abel, D\. E\. Hershkowitz, and M\. L\. Littman \(2016\)Near optimal behavior via approximate state abstraction\.InInternational Conference on Machine Learning \(ICML\),pp\. 2915–2923\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1)\.
- R\. Agarwal, M\. C\. Machado, P\. S\. Castro, and M\. G\. Bellemare \(2021\)Contrastive behavioral similarity embeddings for generalization in reinforcement learning\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p3.1)\.
- A\. Andoni, P\. Indyk, and I\. Razenshteyn \(2018\)Approximate nearest neighbor search in high dimensions\.Proceedings of the International Congress of Mathematicians \(ICM\)\.Note:arXiv:1806\.09823Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p4.1)\.
- A\. Andoni and P\. Indyk \(2008\)Near\-optimal hashing algorithms for approximate nearest neighbor in high dimensions\.Communications of the ACM51\(1\),pp\. 117–122\.Cited by:[Appendix A](https://arxiv.org/html/2608.06762#A1.SS0.SSS0.Px1.p1.16),[Introduction](https://arxiv.org/html/2608.06762#Sx1.p3.2),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p4.1)\.
- M\. Aumüller, E\. Bernhardsson, and A\. Faithfull \(2020\)ANN\-Benchmarks: a benchmarking tool for approximate nearest neighbor algorithms\.Information Systems87,pp\. 101374\.Cited by:[Appendix A](https://arxiv.org/html/2608.06762#A1.SS0.SSS0.Px1.p1.16),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p4.1)\.
- G\. Bacci, G\. Bacci, K\. G\. Larsen, and R\. Mardare \(2013a\)Computing behavioral distances, compositionally\.InInternational Symposium on Mathematical Foundations of Computer Science \(MFCS\),pp\. 74–85\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1),[On\-demand exactness degenerates to quadratic\.](https://arxiv.org/html/2608.06762#Sx6.SSx1.SSS0.Px5.p1.14)\.
- G\. Bacci, G\. Bacci, K\. G\. Larsen, and R\. Mardare \(2013b\)On\-the\-fly exact computation of bisimilarity distances\.InInternational Conference on Tools and Algorithms for the Construction and Analysis of Systems \(TACAS\),pp\. 1–15\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1),[On\-demand exactness degenerates to quadratic\.](https://arxiv.org/html/2608.06762#Sx6.SSx1.SSS0.Px5.p1.14)\.
- M\. G\. Bellemare, Y\. Naddaf, J\. Veness, and M\. Bowling \(2013\)The arcade learning environment: an evaluation platform for general agents\.Journal of Artificial Intelligence Research47,pp\. 253–279\.Cited by:[Introduction](https://arxiv.org/html/2608.06762#Sx1.p2.1)\.
- D\. P\. Bertsekas and J\. N\. Tsitsiklis \(1996\)Neuro\-dynamic programming\.Athena Scientific\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1),[Corollary 7](https://arxiv.org/html/2608.06762#Thmtheorem7.p1.8.8)\.
- J\. Bourgain \(1985\)On Lipschitz embedding of finite metric spaces in Hilbert space\.Israel Journal of Mathematics52\(1–2\),pp\. 46–52\.Cited by:[Introduction](https://arxiv.org/html/2608.06762#Sx1.p3.2),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p4.1),[Corollary 8](https://arxiv.org/html/2608.06762#Thmtheorem8.p1.8.8)\.
- P\. S\. Castro, T\. Kastner, P\. Panangaden, and M\. Rowland \(2021\)MICo: improved representations via sampling\-based state similarity for Markov decision processes\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[Introduction](https://arxiv.org/html/2608.06762#Sx1.p1.1),[Introduction](https://arxiv.org/html/2608.06762#Sx1.p2.1),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p3.1),[Comparison to learned surrogates \(MICo, DBC\)\.](https://arxiv.org/html/2608.06762#Sx5.SSx1.SSS0.Px1.p1.3),[Relation to learned surrogates\.](https://arxiv.org/html/2608.06762#Sx6.SSx1.SSS0.Px4.p1.1)\.
- P\. S\. Castro, T\. Kastner, P\. Panangaden, and M\. Rowland \(2023\)A kernel perspective on behavioural metrics for Markov decision processes\.InTransactions on Machine Learning Research \(TMLR\),Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p3.1),[Relation to learned surrogates\.](https://arxiv.org/html/2608.06762#Sx6.SSx1.SSS0.Px4.p1.1)\.
- P\. S\. Castro \(2020\)Scalable methods for computing state similarity in deterministic Markov decision processes\.InAAAI Conference on Artificial Intelligence,pp\. 10069–10076\.Cited by:[Introduction](https://arxiv.org/html/2608.06762#Sx1.p2.1),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p3.1),[Relation to learned surrogates\.](https://arxiv.org/html/2608.06762#Sx6.SSx1.SSS0.Px4.p1.1)\.
- M\. S\. Charikar \(2002\)Similarity estimation techniques from rounding algorithms\.InACM Symposium on Theory of Computing \(STOC\),pp\. 380–388\.Cited by:[Appendix A](https://arxiv.org/html/2608.06762#A1.SS0.SSS0.Px1.p1.16),[Appendix E](https://arxiv.org/html/2608.06762#A5.p1.14),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p4.1),[Algorithms: a Certified Pipeline and Its Analyzed Core](https://arxiv.org/html/2608.06762#Sx3.p3.10)\.
- D\. Chen, F\. van Breugel, and J\. Worrell \(2012\)On the complexity of computing probabilistic bisimilarity\.InInternational Conference on Foundations of Software Science and Computational Structures \(FoSSaCS\),pp\. 437–451\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1)\.
- G\. Comanici, P\. Panangaden, and D\. Precup \(2015\)On the convergence of bisimulation metrics\.InHorizons of the Mind\. A Tribute to Prakash Panangaden,pp\. 115–137\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p1.17)\.
- G\. Comanici and D\. Precup \(2011\)Basis function discovery using spectral clustering and bisimulation metrics\.InAAAI Conference on Artificial Intelligence,pp\. 325–330\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1)\.
- T\. F\. Cox and M\. A\. A\. Cox \(2001\)Multidimensional scaling\.2nd edition,Chapman & Hall/CRC\.Cited by:[Appendix A](https://arxiv.org/html/2608.06762#A1.SS0.SSS0.Px1.p1.16),[Appendix E](https://arxiv.org/html/2608.06762#A5.p1.14),[Introduction](https://arxiv.org/html/2608.06762#Sx1.p3.2),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p4.1),[Algorithms: a Certified Pipeline and Its Analyzed Core](https://arxiv.org/html/2608.06762#Sx3.p3.10),[Corollary 8](https://arxiv.org/html/2608.06762#Thmtheorem8.p1.8.8)\.
- M\. Cuturi \(2013\)Sinkhorn distances: lightspeed computation of optimal transport\.InAdvances in Neural Information Processing Systems \(NeurIPS\),pp\. 2292–2300\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p4.1)\.
- M\. Datar, N\. Immorlica, P\. Indyk, and V\. S\. Mirrokni \(2004\)Locality\-sensitive hashing scheme based onpp\-stable distributions\.InACM Symposium on Computational Geometry \(SoCG\),pp\. 253–262\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p4.1)\.
- T\. Dean, R\. Givan, and S\. Leach \(1997\)Model reduction techniques for computing approximately optimal solutions for Markov decision processes\.Conference on Uncertainty in Artificial Intelligence \(UAI\),pp\. 124–131\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1)\.
- J\. Desharnais, V\. Gupta, R\. Jagadeesan, and P\. Panangaden \(1999\)Metrics for labelled Markov systems\.InInternational Conference on Concurrency Theory \(CONCUR\),pp\. 258–273\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1)\.
- J\. Desharnais, V\. Gupta, R\. Jagadeesan, and P\. Panangaden \(2004\)Metrics for labelled Markov processes\.Theoretical Computer Science318\(3\),pp\. 323–354\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1)\.
- N\. Ferns, P\. S\. Castro, D\. Precup, and P\. Panangaden \(2005\)Metrics for Markov decision processes with infinite state spaces\.InConference on Uncertainty in Artificial Intelligence \(UAI\),pp\. 201–208\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1)\.
- N\. Ferns, P\. Panangaden, and D\. Precup \(2004\)Metrics for finite Markov decision processes\.InConference on Uncertainty in Artificial Intelligence \(UAI\),pp\. 162–169\.Cited by:[Introduction](https://arxiv.org/html/2608.06762#Sx1.p1.1),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p1.9),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1),[Two\-Sided Certificates and Downstream Aggregation](https://arxiv.org/html/2608.06762#Sx4.SSx1.p1.3)\.
- N\. Ferns, P\. Panangaden, and D\. Precup \(2011\)Bisimulation metrics for continuous Markov decision processes\.SIAM Journal on Computing40\(6\),pp\. 1662–1714\.Cited by:[Introduction](https://arxiv.org/html/2608.06762#Sx1.p1.1),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1)\.
- N\. Ferns and D\. Precup \(2014\)Bisimulation metrics are optimal value functions\.InConference on Uncertainty in Artificial Intelligence \(UAI\),pp\. 210–219\.Cited by:[Appendix D](https://arxiv.org/html/2608.06762#A4.SS0.SSS0.Px2.p3.13),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1),[item*\(iii\)*](https://arxiv.org/html/2608.06762#Sx4.I4.ix3.p1.2),[What the guarantee does and does not say\.](https://arxiv.org/html/2608.06762#Sx6.SSx1.SSS0.Px2.p1.5)\.
- C\. Gelada, S\. Kumar, J\. Buckman, O\. Nachum, and M\. G\. Bellemare \(2019\)DeepMDP: learning continuous latent space models for representation learning\.InInternational Conference on Machine Learning \(ICML\),pp\. 2170–2179\.Cited by:[Introduction](https://arxiv.org/html/2608.06762#Sx1.p1.1),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p3.1)\.
- R\. Givan, T\. Dean, and M\. Greig \(2003\)Equivalence notions and model minimization in Markov decision processes\.Artificial Intelligence147\(1–2\),pp\. 163–223\.Cited by:[Introduction](https://arxiv.org/html/2608.06762#Sx1.p1.1),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1)\.
- P\. Indyk and R\. Motwani \(1998\)Approximate nearest neighbors: towards removing the curse of dimensionality\.InACM Symposium on Theory of Computing \(STOC\),pp\. 604–613\.Cited by:[Appendix A](https://arxiv.org/html/2608.06762#A1.SS0.SSS0.Px1.p1.16),[Introduction](https://arxiv.org/html/2608.06762#Sx1.p3.2),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p4.1),[Algorithms: a Certified Pipeline and Its Analyzed Core](https://arxiv.org/html/2608.06762#Sx3.p3.10)\.
- H\. Jégou, M\. Douze, and C\. Schmid \(2011\)Product quantization for nearest neighbor search\.IEEE Transactions on Pattern Analysis and Machine Intelligence33\(1\),pp\. 117–128\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p4.1),[Algorithms: a Certified Pipeline and Its Analyzed Core](https://arxiv.org/html/2608.06762#Sx3.p3.10),[The choice of index and the recall–coverage distinction\.](https://arxiv.org/html/2608.06762#Sx6.SSx1.SSS0.Px3.p1.7)\.
- N\. Jiang, A\. Kulesza, and S\. Singh \(2015\)Abstraction selection in model\-based reinforcement learning\.InInternational Conference on Machine Learning \(ICML\),pp\. 179–188\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1)\.
- J\. Johnson, M\. Douze, and H\. Jégou \(2021\)Billion\-scale similarity search with GPUs\.IEEE Transactions on Big Data7\(3\),pp\. 535–547\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p4.1)\.
- M\. Kemertas and T\. Aumentado\-Armstrong \(2021\)Towards robust bisimulation metric learning\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p3.1)\.
- K\. G\. Larsen and A\. Skou \(1989\)Bisimulation through probabilistic testing\.InACM Symposium on Principles of Programming Languages \(POPL\),pp\. 344–352\.Cited by:[Introduction](https://arxiv.org/html/2608.06762#Sx1.p1.1),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1)\.
- C\. Le Lan, M\. G\. Bellemare, and P\. S\. Castro \(2021\)Metrics and continuity in reinforcement learning\.InAAAI Conference on Artificial Intelligence,pp\. 8261–8269\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p3.1),[Relation to learned surrogates\.](https://arxiv.org/html/2608.06762#Sx6.SSx1.SSS0.Px4.p1.1)\.
- C\. Le Lan, S\. Tu, A\. Oberman, R\. Agarwal, and M\. G\. Bellemare \(2022\)On the generalization of representations in reinforcement learning\.InInternational Conference on Artificial Intelligence and Statistics \(AISTATS\),Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p3.1),[Relation to learned surrogates\.](https://arxiv.org/html/2608.06762#Sx6.SSx1.SSS0.Px4.p1.1)\.
- L\. Li, T\. J\. Walsh, and M\. L\. Littman \(2006\)Towards a unified theory of state abstraction for MDPs\.InInternational Symposium on Artificial Intelligence and Mathematics \(ISAIM\),Cited by:[Appendix D](https://arxiv.org/html/2608.06762#A4.SS0.SSS0.Px2.p3.13),[Introduction](https://arxiv.org/html/2608.06762#Sx1.p1.1),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1),[item*\(iii\)*](https://arxiv.org/html/2608.06762#Sx4.I4.ix3.p1.2),[Two\-Sided Certificates and Downstream Aggregation](https://arxiv.org/html/2608.06762#Sx4.SSx1.p1.3),[What the guarantee does and does not say\.](https://arxiv.org/html/2608.06762#Sx6.SSx1.SSS0.Px2.p1.5)\.
- W\. Li, Y\. Zhang, Y\. Sun, W\. Wang, M\. Li, W\. Zhang, and X\. Lin \(2020\)Approximate nearest neighbor search on high dimensional data — experiments, analyses, and improvement\.IEEE Transactions on Knowledge and Data Engineering32\(8\),pp\. 1475–1488\.Cited by:[Appendix A](https://arxiv.org/html/2608.06762#A1.SS0.SSS0.Px1.p1.16),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p4.1)\.
- N\. Linial, E\. London, and Y\. Rabinovich \(1994\)The geometry of graphs and some of its algorithmic applications\.InIEEE Symposium on Foundations of Computer Science \(FOCS\),pp\. 577–591\.Cited by:[Introduction](https://arxiv.org/html/2608.06762#Sx1.p3.2),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p4.1),[Corollary 8](https://arxiv.org/html/2608.06762#Thmtheorem8.p1.8.8)\.
- Y\. A\. Malkov and D\. A\. Yashunin \(2020\)Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs\.IEEE Transactions on Pattern Analysis and Machine Intelligence42\(4\),pp\. 824–836\.Cited by:[Appendix A](https://arxiv.org/html/2608.06762#A1.SS0.SSS0.Px1.p1.16),[Introduction](https://arxiv.org/html/2608.06762#Sx1.p3.2),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p4.1),[Algorithms: a Certified Pipeline and Its Analyzed Core](https://arxiv.org/html/2608.06762#Sx3.p3.10),[The choice of index and the recall–coverage distinction\.](https://arxiv.org/html/2608.06762#Sx6.SSx1.SSS0.Px3.p1.7)\.
- V\. Mnih, K\. Kavukcuoglu, D\. Silver,et al\.\(2015\)Human\-level control through deep reinforcement learning\.Nature518\(7540\),pp\. 529–533\.Cited by:[Introduction](https://arxiv.org/html/2608.06762#Sx1.p2.1)\.
- G\. Peyré and M\. Cuturi \(2019\)Computational optimal transport\.Foundations and Trends in Machine Learning\.Cited by:[Appendix A](https://arxiv.org/html/2608.06762#A1.SS0.SSS0.Px2.p1.5),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p4.1)\.
- M\. L\. Puterman \(1994\)Markov decision processes: discrete stochastic dynamic programming\.John Wiley & Sons\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p1.9),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1)\.
- B\. Ravindran and A\. G\. Barto \(2003\)SMDP homomorphisms: an algebraic approach to abstraction in semi\-Markov decision processes\.InInternational Joint Conference on Artificial Intelligence \(IJCAI\),pp\. 1011–1016\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1)\.
- B\. Ravindran \(2004\)An algebraic approach to abstraction in reinforcement learning\.Ph\.D\. Thesis,University of Massachusetts Amherst\.Cited by:[Introduction](https://arxiv.org/html/2608.06762#Sx1.p1.1)\.
- R\. S\. Sutton and A\. G\. Barto \(2018\)Reinforcement learning: an introduction\.2nd edition,MIT Press\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p1.9)\.
- J\. Taylor, D\. Precup, and P\. Panangaden \(2009\)Bounding performance loss in approximate MDP homomorphisms\.InAdvances in Neural Information Processing Systems \(NeurIPS\),pp\. 1649–1656\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1)\.
- F\. van Breugel and J\. Worrell \(2001\)An algorithm for quantitative verification of probabilistic transition systems\.InInternational Conference on Concurrency Theory \(CONCUR\),pp\. 336–350\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1)\.
- F\. van Breugel and J\. Worrell \(2005\)Domain theory, testing and simulation for labelled Markov processes\.Theoretical Computer Science333\(1–2\),pp\. 171–197\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p2.1)\.
- C\. Villani \(2009\)Optimal transport: old and new\.Springer\.Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p1.17),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p4.1)\.
- J\. Wang, H\. T\. Shen, J\. Song, and J\. Ji \(2014\)Hashing for similarity search: a survey\.arXiv preprint\.Note:arXiv:1408\.2927Cited by:[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p4.1)\.
- A\. Zhang, R\. McAllister, R\. Calandra, Y\. Gal, and S\. Levine \(2021\)Learning invariant representations for reinforcement learning without reconstruction\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[Introduction](https://arxiv.org/html/2608.06762#Sx1.p1.1),[Introduction](https://arxiv.org/html/2608.06762#Sx1.p2.1),[Setup and Related Work](https://arxiv.org/html/2608.06762#Sx2.p3.1),[Comparison to learned surrogates \(MICo, DBC\)\.](https://arxiv.org/html/2608.06762#Sx5.SSx1.SSS0.Px1.p1.3),[Relation to learned surrogates\.](https://arxiv.org/html/2608.06762#Sx6.SSx1.SSS0.Px4.p1.1)\.

## Technical Appendix \(Supplementary Material\)

## Appendix AComplexity Details for Theorem[1](https://arxiv.org/html/2608.06762#Thmtheorem1)

#### One\-time costs\.

\(i\)*Embedding\.*Landmark MDS withmlm=O​\(poly​\(k\)\)m\_\{\\mathrm\{lm\}\}=O\(\\mathrm\{poly\}\(k\)\)landmarks reads themlmm\_\{\\mathrm\{lm\}\}landmark columns ofd0d\_\{0\}; each entry ofd0∈\{0,dR\}d\_\{0\}\\in\\\{0,d\_\{R\}\\\}is computable on demand inO​\(\|𝒜\|\)O\(\|\\mathcal\{A\}\|\), so forming the landmark distances costsO​\(\|𝒮\|​mlm​\|𝒜\|\)O\(\|\\mathcal\{S\}\|\\,m\_\{\\mathrm\{lm\}\}\\,\|\\mathcal\{A\}\|\)and the eigen\-step and out\-of\-sample projections costO​\(mlm3\+\|𝒮\|​mlm​k\)O\(m\_\{\\mathrm\{lm\}\}^\{3\}\+\|\\mathcal\{S\}\|\\,m\_\{\\mathrm\{lm\}\}k\)\(Cox and Cox[2001](https://arxiv.org/html/2608.06762#bib.bib45)\), i\.e\.O​\(\|𝒮\|​poly​\(k\)\)O\(\|\\mathcal\{S\}\|\\,\\mathrm\{poly\}\(k\)\)overall for fixed\|𝒜\|\|\\mathcal\{A\}\|\. Classical MDS from the full matrix isΘ​\(\|𝒮\|2\)\\Theta\(\|\\mathcal\{S\}\|^\{2\}\)and is never invoked\. \(ii\)*Index build:*O~​\(\|𝒮\|\)\\widetilde\{O\}\(\|\\mathcal\{S\}\|\)for LSH and standard graph indices\(Charikar[2002](https://arxiv.org/html/2608.06762#bib.bib35); Malkov and Yashunin[2020](https://arxiv.org/html/2608.06762#bib.bib37); Liet al\.[2020](https://arxiv.org/html/2608.06762#bib.bib41)\)\. \(iii\)*Queries:*\|𝒮\|\|\\mathcal\{S\}\|queries at amortizedq​\(\|𝒮\|\)q\(\|\\mathcal\{S\}\|\); for LSH,q​\(\|𝒮\|\)=O​\(\|𝒮\|ρLSH\)q\(\|\\mathcal\{S\}\|\)=O\(\|\\mathcal\{S\}\|^\{\\rho\_\{\\mathrm\{LSH\}\}\}\)withρLSH<1\\rho\_\{\\mathrm\{LSH\}\}<1set by the approximation ratio\(Indyk and Motwani[1998](https://arxiv.org/html/2608.06762#bib.bib32); Andoni and Indyk[2008](https://arxiv.org/html/2608.06762#bib.bib33)\); graph indices give polylogarithmicqqempirically but without worst\-case guarantees\(Malkov and Yashunin[2020](https://arxiv.org/html/2608.06762#bib.bib37); Aumülleret al\.[2020](https://arxiv.org/html/2608.06762#bib.bib42)\), which is why the theorem is stated relative to an explicit oracle\.

#### Per\-sweep cost\.

\|𝒞\|≤\|𝒮\|​k′\|\\mathcal\{C\}\|\\leq\|\\mathcal\{S\}\|k^\{\\prime\}exact backups, each solving\|𝒜\|\|\\mathcal\{A\}\|transport problems on the union of two supports of size at mostmm\(Assumption[1](https://arxiv.org/html/2608.06762#Thmassumption1)\), identical in value to the dense program by Lemma[10](https://arxiv.org/html/2608.06762#Thmtheorem10); a network\-simplex or specialized solver runs incm=O​\(m3​log⁡m\)c\_\{m\}=O\(m^\{3\}\\log m\)\(Peyré and Cuturi[2019](https://arxiv.org/html/2608.06762#bib.bib47)\), independent of\|𝒮\|\|\\mathcal\{S\}\|\. The two\-armed pipeline doubles this constant\.

#### Sweep count\.

By Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2), the transient term isγt​Δ0\\gamma^\{t\}\\Delta\_\{0\}, so covered\-set accuracyϵ\\epsilonbeyond the coverage floor is reached att≥log⁡\(Δ0/ϵ\)/log⁡\(1/γ\)t\\geq\\log\(\\Delta\_\{0\}/\\epsilon\)/\\log\(1/\\gamma\), andlog⁡\(1/γ\)≥1−γ\\log\(1/\\gamma\)\\geq 1\-\\gammagivesK=O​\(log⁡\(Δ0/ϵ\)/\(1−γ\)\)K=O\\\!\\big\(\\log\(\\Delta\_\{0\}/\\epsilon\)/\(1\-\\gamma\)\\big\); the upper arm obeys the same recursion withΔ0\+:=‖U−d‖∞≤Dγ\\Delta\_\{0\}^\{\+\}:=\\left\\lVert U\-d\\right\\rVert\_\{\\infty\}\\leq D\_\{\\gamma\}\.

#### Totals\.

Summing, the total time isO​\(\|𝒮\|​\(poly​\(k\)\+q​\(\|𝒮\|\)\)\)\+O​\(\|𝒮\|​k′​cm​log⁡\(Δ0/ϵ\)/\(1−γ\)\)O\\\!\\big\(\|\\mathcal\{S\}\|\(\\mathrm\{poly\}\(k\)\+q\(\|\\mathcal\{S\}\|\)\)\\big\)\+O\\\!\\big\(\|\\mathcal\{S\}\|k^\{\\prime\}c\_\{m\}\\log\(\\Delta\_\{0\}/\\epsilon\)/\(1\-\\gamma\)\\big\): under LSH,O~​\(\|𝒮\|1\+ρLSH\+\|𝒮\|/\(1−γ\)\)\\widetilde\{O\}\(\|\\mathcal\{S\}\|^\{1\+\\rho\_\{\\mathrm\{LSH\}\}\}\+\|\\mathcal\{S\}\|/\(1\-\\gamma\)\); under a polylogarithmic oracle,O~​\(\|𝒮\|/\(1−γ\)\)\\widetilde\{O\}\(\|\\mathcal\{S\}\|/\(1\-\\gamma\)\)\. Both are sub\-quadratic; the exact sweep costsΘ​\(\|𝒮\|2​cm\)\\Theta\(\|\\mathcal\{S\}\|^\{2\}c\_\{m\}\)per application\. The re\-seeded pipeline adds the one\-time block once per round: forRRrounds the total isO~​\(R​\|𝒮\|​q​\(\|𝒮\|\)\+R​E​\|𝒮\|​k′​cm\)\\widetilde\{O\}\\\!\\big\(R\\,\|\\mathcal\{S\}\|\\,q\(\|\\mathcal\{S\}\|\)\+R\\,E\\,\|\\mathcal\{S\}\|k^\{\\prime\}c\_\{m\}\\big\), sub\-quadratic forR=o​\(\|𝒮\|/q​\(\|𝒮\|\)\)R=o\(\|\\mathcal\{S\}\|/q\(\|\\mathcal\{S\}\|\)\), while zero global width forcesR=Ω​\(\|𝒮\|/k′\)R=\\Omega\(\|\\mathcal\{S\}\|/k^\{\\prime\}\)\(Corollary[7](https://arxiv.org/html/2608.06762#Thmtheorem7)\(d\)\) and hence quadratic total work, consistent with Proposition[4](https://arxiv.org/html/2608.06762#Thmtheorem4)\.

![Refer to caption](https://arxiv.org/html/2608.06762v1/x1.png)Figure 2:Measured per\-sweep wall\-clock time against\|𝒮\|\|\\mathcal\{S\}\|on log–log axes, for the cheap ground\-cost rows of Table[2](https://arxiv.org/html/2608.06762#Sx5.T2)\. Fitted slopes are1\.911\.91for the exact all\-pairs sweep and1\.411\.41for the ANN top\-k′k^\{\\prime\}sweep, the quadratic versus sub\-quadratic separation of Theorem[1](https://arxiv.org/html/2608.06762#Thmtheorem1)\. Both sweeps share the identical inner kernel and differ only in which pairs they visit, so the slope gap measures pair\-visit scaling alone\.###### Corollary 8\(Embedding does not dominate\)\.

WithO​\(poly​\(k\)\)O\(\\mathrm\{poly\}\(k\)\)landmarks, landmark MDS\(Cox and Cox[2001](https://arxiv.org/html/2608.06762#bib.bib45)\)readsO​\(\|𝒮\|​poly​\(k\)\)O\(\|\\mathcal\{S\}\|\\,\\mathrm\{poly\}\(k\)\)entries ofd0d\_\{0\}\(each computable on demand inO​\(\|𝒜\|\)O\(\|\\mathcal\{A\}\|\)\) and costsO​\(\|𝒮\|​poly​\(k\)\)O\(\|\\mathcal\{S\}\|\\,\\mathrm\{poly\}\(k\)\)time, once; classical MDS from the full distance matrix would costΘ​\(\|𝒮\|2\)\\Theta\(\|\\mathcal\{S\}\|^\{2\}\)and is never used\. When the bisimulation metric has low intrinsic dimension, so a smallkkachieves distortionη=o​\(1\)\\eta=o\(1\)\(Bourgain[1985](https://arxiv.org/html/2608.06762#bib.bib43); Linialet al\.[1994](https://arxiv.org/html/2608.06762#bib.bib44)\), the one\-time embedding cost is dominated by the query\-and\-backup cost of Theorem[1](https://arxiv.org/html/2608.06762#Thmtheorem1)\.

## Appendix BProof of Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)and Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3)

#### Setup\.

Let𝒫\\mathcal\{P\}be the unordered off\-diagonal pairs of𝒮\\mathcal\{S\}andℬ​\(𝒫\)\\mathcal\{B\}\(\\mathcal\{P\}\)the bounded symmetric functions on𝒫\\mathcal\{P\}\(extended by0on the diagonal\) with‖f‖∞=maxp∈𝒫⁡\|f​\(p\)\|\\left\\lVert f\\right\\rVert\_\{\\infty\}=\\max\_\{p\\in\\mathcal\{P\}\}\|f\(p\)\|\. The operatorTTis \([1](https://arxiv.org/html/2608.06762#Sx2.E1)\); recallDγ=L/\(1−γ\)D\_\{\\gamma\}=L/\(1\-\\gamma\)and‖d‖∞≤Dγ\\left\\lVert d\\right\\rVert\_\{\\infty\}\\leq D\_\{\\gamma\}\(fromd=limnTn​0d=\\lim\_\{n\}T^\{n\}0and‖Tn​0‖∞≤L​∑i<nγi\\left\\lVert T^\{n\}0\\right\\rVert\_\{\\infty\}\\leq L\\sum\_\{i<n\}\\gamma^\{i\}\)\.

###### Lemma 9\(Basic properties ofTT\)\.

For allf,g∈ℬ​\(𝒫\)f,g\\in\\mathcal\{B\}\(\\mathcal\{P\}\)and all distributionsμ,ν\\mu,\\nuon𝒮\\mathcal\{S\}: \(a\)\|W1f​\(μ,ν\)−W1g​\(μ,ν\)\|≤‖f−g‖∞\|W\_\{1\}^\{f\}\(\\mu,\\nu\)\-W\_\{1\}^\{g\}\(\\mu,\\nu\)\|\\leq\\left\\lVert f\-g\\right\\rVert\_\{\\infty\}; \(b\) iff≤gf\\leq gentrywise thenW1f​\(μ,ν\)≤W1g​\(μ,ν\)W\_\{1\}^\{f\}\(\\mu,\\nu\)\\leq W\_\{1\}^\{g\}\(\\mu,\\nu\); \(c\)‖T​f−T​g‖∞≤γ​‖f−g‖∞\\left\\lVert Tf\-Tg\\right\\rVert\_\{\\infty\}\\leq\\gamma\\left\\lVert f\-g\\right\\rVert\_\{\\infty\}; \(d\)f≤gf\\leq gimpliesT​f≤T​gTf\\leq Tg; \(e\)dR≤T​f≤L\+γ​‖f‖∞d\_\{R\}\\leq Tf\\leq L\+\\gamma\\left\\lVert f\\right\\rVert\_\{\\infty\}wheneverf≥0f\\geq 0, wheredR​\(s,s′\)=maxa⁡\|R​\(s,a\)−R​\(s′,a\)\|d\_\{R\}\(s,s^\{\\prime\}\)=\\max\_\{a\}\|R\(s,a\)\-R\(s^\{\\prime\},a\)\|; \(f\) iff≥g−cf\\geq g\-centrywise for somec≥0c\\geq 0, thenT​f≥T​g−γ​cTf\\geq Tg\-\\gamma c\.

###### Proof\.

\(a\) Letπ\\pibe an optimal coupling forW1gW\_\{1\}^\{g\}\. Its cost underffexceeds its cost underggby at most‖f−g‖∞\\left\\lVert f\-g\\right\\rVert\_\{\\infty\}becauseπ\\pihas unit mass; henceW1f≤W1g\+‖f−g‖∞W\_\{1\}^\{f\}\\leq W\_\{1\}^\{g\}\+\\left\\lVert f\-g\\right\\rVert\_\{\\infty\}, and symmetrically\. \(b\) Every coupling costs no more underffthan undergg; take the infimum\. \(c\) The reward term is cost\-independent,W1⋅W\_\{1\}^\{\\cdot\}moves by at most‖f−g‖∞\\left\\lVert f\-g\\right\\rVert\_\{\\infty\}by \(a\), andmaxa\\max\_\{a\}is nonexpansive\. \(d\) By \(b\) and monotonicity ofmaxa\\max\_\{a\}\. \(e\)W1f≥0W\_\{1\}^\{f\}\\geq 0gives the lower bound;W1f≤‖f‖∞W\_\{1\}^\{f\}\\leq\\left\\lVert f\\right\\rVert\_\{\\infty\}\(unit mass, entries bounded\) gives the upper\. \(f\) Apply \(b\) withg−c≤fg\-c\\leq f, then \(a\)\-style shift:W1f≥W1g−c≥W1g−cW\_\{1\}^\{f\}\\geq W\_\{1\}^\{g\-c\}\\geq W\_\{1\}^\{g\}\-c, and the reward term is unchanged\. ∎

###### Lemma 10\(Union\-support transport\)\.

For distributionsμ,ν\\mu,\\nuwith supportsA,B⊆𝒮A,B\\subseteq\\mathcal\{S\}and any ground costcc, the Kantorovich LP restricted toA×BA\\times Bhas the same value as the LP over𝒮×𝒮\\mathcal\{S\}\\times\\mathcal\{S\}\.

###### Proof\.

Every coupling of\(μ,ν\)\(\\mu,\\nu\)places mass only onA×BA\\times B, so the two feasible sets coincide after deleting identically\-zero variables\. ∎

#### The restricted iteration and its boundedness\.

Fix the persistent covered set𝒞\\mathcal\{C\}, the initializationd0≤dd\_\{0\}\\leq d, and a covered backupBBsatisfying Assumption[2](https://arxiv.org/html/2608.06762#Thmassumption2)\. The iterates aref0=d0f\_\{0\}=d\_\{0\}and

ft\+1​\(p\)=\{B​ft​\(p\),p∈𝒞,d0​\(p\),p∉𝒞\.f\_\{t\+1\}\(p\)=\\begin\{cases\}Bf\_\{t\}\(p\),&p\\in\\mathcal\{C\},\\\\ d\_\{0\}\(p\),&p\\notin\\mathcal\{C\}\.\\end\{cases\}By Lemma[9](https://arxiv.org/html/2608.06762#Thmtheorem9)\(e\) and\|B​f−T​f\|≤εop\|Bf\-Tf\|\\leq\\varepsilon\_\{\\mathrm\{op\}\},‖ft\+1‖∞≤max⁡\(‖d0‖∞,L\+γ​‖ft‖∞\+εop\)\\left\\lVert f\_\{t\+1\}\\right\\rVert\_\{\\infty\}\\leq\\max\\big\(\\left\\lVert d\_\{0\}\\right\\rVert\_\{\\infty\},\\,L\+\\gamma\\left\\lVert f\_\{t\}\\right\\rVert\_\{\\infty\}\+\\varepsilon\_\{\\mathrm\{op\}\}\\big\); the ball‖f‖∞≤\(L\+εop\)/\(1−γ\)=Dγ\+εop/\(1−γ\)\\left\\lVert f\\right\\rVert\_\{\\infty\}\\leq\(L\+\\varepsilon\_\{\\mathrm\{op\}\}\)/\(1\-\\gamma\)=D\_\{\\gamma\}\+\\varepsilon\_\{\\mathrm\{op\}\}/\(1\-\\gamma\)is invariant and containsf0f\_\{0\}\(as0≤d0≤d≤Dγ0\\leq d\_\{0\}\\leq d\\leq D\_\{\\gamma\}\), so Assumption[2](https://arxiv.org/html/2608.06762#Thmassumption2)applies at every iterate\.

###### Lemma 11\(Well\-posedness of the exact restricted iteration\)\.

Let𝒜:=\{f∈ℬ​\(𝒫\):f=d0​off​𝒞\}\\mathcal\{A\}:=\\\{f\\in\\mathcal\{B\}\(\\mathcal\{P\}\):f=d\_\{0\}\\text\{ off \}\\mathcal\{C\}\\\}and letT^\\hat\{T\}act asTTon𝒞\\mathcal\{C\}and as the identity off𝒞\\mathcal\{C\}\. ThenT^\\hat\{T\}maps𝒜\\mathcal\{A\}to itself and is aγ\\gamma\-contraction on\(𝒜,∥⋅∥∞\)\(\\mathcal\{A\},\\left\\lVert\\cdot\\right\\rVert\_\{\\infty\}\); it has a unique fixed pointd^∈𝒜\\hat\{d\}\\in\\mathcal\{A\}, and the exact iterates converge to it geometrically\.

###### Proof\.

Forf,g∈𝒜f,g\\in\\mathcal\{A\}the difference vanishes off𝒞\\mathcal\{C\}, and on𝒞\\mathcal\{C\},\|T^​f−T^​g\|=\|T​f−T​g\|≤γ​‖f−g‖∞\|\\hat\{T\}f\-\\hat\{T\}g\|=\|Tf\-Tg\|\\leq\\gamma\\left\\lVert f\-g\\right\\rVert\_\{\\infty\}by Lemma[9](https://arxiv.org/html/2608.06762#Thmtheorem9)\(c\); note the sup on the right runs over*all*pairs, which is exactly why the frozen boundary must agree, as it does within𝒜\\mathcal\{A\}\. Banach’s theorem on the closed set𝒜\\mathcal\{A\}concludes\. ∎

#### Proof of Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)\.

*Uncovered pairs\.*For everyttandp∉𝒞p\\notin\\mathcal\{C\},ft​\(p\)=d0​\(p\)f\_\{t\}\(p\)=d\_\{0\}\(p\), so\|ft​\(p\)−d​\(p\)\|=d​\(p\)−d0​\(p\)∈\[0,ρ\]\|f\_\{t\}\(p\)\-d\(p\)\|=d\(p\)\-d\_\{0\}\(p\)\\in\[0,\\rho\]with maximum exactlyρ\\rhoby definition \([3](https://arxiv.org/html/2608.06762#Sx4.E3)\)\.

*Covered recursion\.*Writeet=maxp∈𝒞⁡\|ft​\(p\)−d​\(p\)\|e\_\{t\}=\\max\_\{p\\in\\mathcal\{C\}\}\|f\_\{t\}\(p\)\-d\(p\)\|\. Forp∈𝒞p\\in\\mathcal\{C\},

\|ft\+1​\(p\)−d​\(p\)\|=\|B​ft​\(p\)−T​d​\(p\)\|≤\|B​ft​\(p\)−T​ft​\(p\)\|⏟≤εop\+\|T​ft​\(p\)−T​d​\(p\)\|⏟≤γ​‖ft−d‖∞,\\begin\{split\}\|f\_\{t\+1\}\(p\)\-d\(p\)\|&=\|Bf\_\{t\}\(p\)\-Td\(p\)\|\\\\ &\\leq\\underbrace\{\|Bf\_\{t\}\(p\)\-Tf\_\{t\}\(p\)\|\}\_\{\\leq\\,\\varepsilon\_\{\\mathrm\{op\}\}\}\+\\underbrace\{\|Tf\_\{t\}\(p\)\-Td\(p\)\|\}\_\{\\leq\\,\\gamma\\left\\lVert f\_\{t\}\-d\\right\\rVert\_\{\\infty\}\},\\end\{split\}using Assumption[2](https://arxiv.org/html/2608.06762#Thmassumption2)\(legitimate by the boundedness invariant\) and Lemma[9](https://arxiv.org/html/2608.06762#Thmtheorem9)\(c\)\. Since‖ft−d‖∞=max⁡\(et,maxp∉𝒞⁡\(d−d0\)​\(p\)\)≤max⁡\(et,ρ\)\\left\\lVert f\_\{t\}\-d\\right\\rVert\_\{\\infty\}=\\max\(e\_\{t\},\\max\_\{p\\notin\\mathcal\{C\}\}\(d\-d\_\{0\}\)\(p\)\)\\leq\\max\(e\_\{t\},\\rho\), we obtainet\+1≤ψ​\(et\)e\_\{t\+1\}\\leq\\psi\(e\_\{t\}\)withψ​\(x\):=εop\+γ​max⁡\(x,ρ\)\\psi\(x\):=\\varepsilon\_\{\\mathrm\{op\}\}\+\\gamma\\max\(x,\\rho\)\.

*Solving the recursion\.*ψ\\psiis nondecreasing andγ\\gamma\-Lipschitz onℝ≥0\\mathbb\{R\}\_\{\\geq 0\}, hence has a unique fixed pointx⋆x^\{\\star\}\. Case analysis: ifx≥ρx\\geq\\rho, the fixed\-point equation readsx=εop\+γ​xx=\\varepsilon\_\{\\mathrm\{op\}\}\+\\gamma x, i\.e\.x=εop/\(1−γ\)x=\\varepsilon\_\{\\mathrm\{op\}\}/\(1\-\\gamma\), consistent iffεop/\(1−γ\)≥ρ\\varepsilon\_\{\\mathrm\{op\}\}/\(1\-\\gamma\)\\geq\\rho; ifx≤ρx\\leq\\rhoit readsx=εop\+γ​ρx=\\varepsilon\_\{\\mathrm\{op\}\}\+\\gamma\\rho, consistent iffεop\+γ​ρ≤ρ\\varepsilon\_\{\\mathrm\{op\}\}\+\\gamma\\rho\\leq\\rho, i\.e\.εop≤\(1−γ\)​ρ\\varepsilon\_\{\\mathrm\{op\}\}\\leq\(1\-\\gamma\)\\rho\. The two consistency conditions are complementary, and in both regimesx⋆=max⁡\(εop/\(1−γ\),εop\+γ​ρ\)x^\{\\star\}=\\max\\big\(\\varepsilon\_\{\\mathrm\{op\}\}/\(1\-\\gamma\),\\ \\varepsilon\_\{\\mathrm\{op\}\}\+\\gamma\\rho\\big\): whenεop≥\(1−γ\)​ρ\\varepsilon\_\{\\mathrm\{op\}\}\\geq\(1\-\\gamma\)\\rho,εop/\(1−γ\)−\(εop\+γ​ρ\)=γ​\(εop/\(1−γ\)−ρ\)≥0\\varepsilon\_\{\\mathrm\{op\}\}/\(1\-\\gamma\)\-\(\\varepsilon\_\{\\mathrm\{op\}\}\+\\gamma\\rho\)=\\gamma\\big\(\\varepsilon\_\{\\mathrm\{op\}\}/\(1\-\\gamma\)\-\\rho\\big\)\\geq 0; otherwise the inequality reverses\. By monotonicity,et≤ψt​\(e0\)e\_\{t\}\\leq\\psi^\{t\}\(e\_\{0\}\), and by the Lipschitz bound\|ψt​\(e0\)−x⋆\|≤γt​\|e0−x⋆\|\|\\psi^\{t\}\(e\_\{0\}\)\-x^\{\\star\}\|\\leq\\gamma^\{t\}\|e\_\{0\}\-x^\{\\star\}\|, soet≤x⋆\+γt​e0≤x⋆\+γt​Δ0e\_\{t\}\\leq x^\{\\star\}\+\\gamma^\{t\}e\_\{0\}\\leq x^\{\\star\}\+\\gamma^\{t\}\\Delta\_\{0\}\(ase0=max𝒞⁡\|d0−d\|≤Δ0e\_\{0\}=\\max\_\{\\mathcal\{C\}\}\|d\_\{0\}\-d\|\\leq\\Delta\_\{0\}\)\. This is \(A\)\.

*Global bound\.*‖ft−d‖∞=max⁡\(et,ρ\)≤max⁡\(x⋆,ρ\)\+γt​Δ0\\left\\lVert f\_\{t\}\-d\\right\\rVert\_\{\\infty\}=\\max\(e\_\{t\},\\rho\)\\leq\\max\(x^\{\\star\},\\rho\)\+\\gamma^\{t\}\\Delta\_\{0\}\. Ifεop≤\(1−γ\)​ρ\\varepsilon\_\{\\mathrm\{op\}\}\\leq\(1\-\\gamma\)\\rhothenεop\+γ​ρ≤ρ\\varepsilon\_\{\\mathrm\{op\}\}\+\\gamma\\rho\\leq\\rhoandεop/\(1−γ\)≤ρ\\varepsilon\_\{\\mathrm\{op\}\}/\(1\-\\gamma\)\\leq\\rho, somax⁡\(x⋆,ρ\)=ρ\\max\(x^\{\\star\},\\rho\)=\\rho; otherwiseεop\+γ​ρ<εop/\(1−γ\)\\varepsilon\_\{\\mathrm\{op\}\}\+\\gamma\\rho<\\varepsilon\_\{\\mathrm\{op\}\}/\(1\-\\gamma\)andmax⁡\(x⋆,ρ\)=εop/\(1−γ\)\\max\(x^\{\\star\},\\rho\)=\\varepsilon\_\{\\mathrm\{op\}\}/\(1\-\\gamma\)\. In both casesmax⁡\(x⋆,ρ\)=max⁡\(ρ,εop/\(1−γ\)\)\\max\(x^\{\\star\},\\rho\)=\\max\\big\(\\rho,\\ \\varepsilon\_\{\\mathrm\{op\}\}/\(1\-\\gamma\)\\big\), giving \(B\); the limit\-point statement follows by lettingt→∞t\\to\\inftyalong a convergent subsequence\. If𝒞=𝒮×𝒮\\mathcal\{C\}=\\mathcal\{S\}\\times\\mathcal\{S\}the uncovered maximum is over the empty set,ρ=0\\rho=0by convention, and the recursion iset\+1≤εop\+γ​ete\_\{t\+1\}\\leq\\varepsilon\_\{\\mathrm\{op\}\}\+\\gamma e\_\{t\}, giving \(C\)\.

*Exact backup \(D\)\.*HereB=TB=Ton𝒞\\mathcal\{C\}, so the iteration isT^\\hat\{T\}of Lemma[11](https://arxiv.org/html/2608.06762#Thmtheorem11)\.T^\\hat\{T\}is monotone \(Lemma[9](https://arxiv.org/html/2608.06762#Thmtheorem9)\(d\) on𝒞\\mathcal\{C\}; identity off𝒞\\mathcal\{C\}\)\. Sub\-solution: ford0∈\{0,dR\}d\_\{0\}\\in\\\{0,d\_\{R\}\\\}, Lemma[9](https://arxiv.org/html/2608.06762#Thmtheorem9)\(e\) givesT​d0≥dR≥d0Td\_\{0\}\\geq d\_\{R\}\\geq d\_\{0\}on𝒞\\mathcal\{C\}, sof1≥f0f\_\{1\}\\geq f\_\{0\}, and monotonicity propagatesft\+1≥ftf\_\{t\+1\}\\geq f\_\{t\}for alltt\. Upper invariance: iff≤df\\leq dthenT^​f≤T^​d≤d\\hat\{T\}f\\leq\\hat\{T\}d\\leq d\(on𝒞\\mathcal\{C\},T​f≤T​d=dTf\\leq Td=d; off𝒞\\mathcal\{C\},d0≤dd\_\{0\}\\leq d\), soft≤df\_\{t\}\\leq dthroughout\. A monotone bounded sequence on a finite pair set converges pointwise; the limit lies in𝒜\\mathcal\{A\}, is a fixed point ofT^\\hat\{T\}by continuity, and equals the uniqued^\\hat\{d\}of Lemma[11](https://arxiv.org/html/2608.06762#Thmtheorem11), withd0≤d^≤dd\_\{0\}\\leq\\hat\{d\}\\leq d\. Finally, forp∈𝒞p\\in\\mathcal\{C\},

d​\(p\)−d^​\(p\)=T​d​\(p\)−T​d^​\(p\)≤γ​‖d−d^‖∞=γ​max⁡\(e∞,maxq∉𝒞⁡\(d−d0\)​\(q\)\)≤γ​max⁡\(e∞,ρ\)\.\\begin\{split\}d\(p\)\-\\hat\{d\}\(p\)&=Td\(p\)\-T\\hat\{d\}\(p\)\\leq\\gamma\\left\\lVert d\-\\hat\{d\}\\right\\rVert\_\{\\infty\}\\\\ &=\\gamma\\max\\big\(e\_\{\\infty\},\\ \\max\_\{q\\notin\\mathcal\{C\}\}\(d\-d\_\{0\}\)\(q\)\\big\)\\\\ &\\leq\\gamma\\max\(e\_\{\\infty\},\\rho\)\.\\end\{split\}If the inner maximum weree∞e\_\{\\infty\}we would gete∞≤γ​e∞e\_\{\\infty\}\\leq\\gamma e\_\{\\infty\}, i\.e\.e∞=0≤γ​ρe\_\{\\infty\}=0\\leq\\gamma\\rho; otherwisee∞≤γ​ρe\_\{\\infty\}\\leq\\gamma\\rhodirectly\. Either waye∞≤γ​ρe\_\{\\infty\}\\leq\\gamma\\rho, which is \(D\)\.∎

#### Proof of Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3)\.

Under \(D\),d^=d0\\hat\{d\}=d\_\{0\}off𝒞\\mathcal\{C\}, so the uncovered error attains its maximumρ\\rhoat the argmax pair of \([3](https://arxiv.org/html/2608.06762#Sx4.E3)\); the covered error is at mostγ​ρ≤ρ\\gamma\\rho\\leq\\rho\. Hence‖d^−d‖∞=max⁡\(e∞,ρ\)=ρ\\left\\lVert\\hat\{d\}\-d\\right\\rVert\_\{\\infty\}=\\max\(e\_\{\\infty\},\\rho\)=\\rho\(and=0=0when𝒞\\mathcal\{C\}covers all pairs\)\.∎

###### Lemma 12\(Index\-side instantiation\)\.

Suppose the covered backup evaluates \([1](https://arxiv.org/html/2608.06762#Sx2.E1)\) with each ground\-cost entry perturbed by at mostη\\eta\(e\.g\. read off the embedding\) and with a coupling that omits at most anrr\-fraction of probability mass, re\-routed at per\-unit cost error at mostDγD\_\{\\gamma\}\. Then Assumption[2](https://arxiv.org/html/2608.06762#Thmassumption2)holds withεop≤γ​\(η\+r​Dγ\)\\varepsilon\_\{\\mathrm\{op\}\}\\leq\\gamma\(\\eta\+rD\_\{\\gamma\}\)\.

#### Proof of Lemma[12](https://arxiv.org/html/2608.06762#Thmtheorem12)\.

Fixffin the invariant ball and a covered pair\. Perturbing each ground\-cost entry by at mostη\\etamoves the transport value by at mostη\\eta\(the argument of Lemma[9](https://arxiv.org/html/2608.06762#Thmtheorem9)\(a\) applied to the perturbed cost\)\. Omitting anrr\-fraction of mass and re\-routing it at per\-unit cost error at mostDγD\_\{\\gamma\}moves the value by at mostr​DγrD\_\{\\gamma\}\. The reward term is exact andmaxa\\max\_\{a\}is nonexpansive, so the backup differs fromT​fTfby at mostγ​\(η\+r​Dγ\)\\gamma\(\\eta\+rD\_\{\\gamma\}\), i\.e\. Assumption[2](https://arxiv.org/html/2608.06762#Thmassumption2)holds withεop≤γ​\(η\+r​Dγ\)\\varepsilon\_\{\\mathrm\{op\}\}\\leq\\gamma\(\\eta\+rD\_\{\\gamma\}\)\.∎

#### Why the naive bound fails\.

Any per\-step boundε/\(1−γ\)\\varepsilon/\(1\-\\gamma\)silently assumes𝒞=𝒮×𝒮\\mathcal\{C\}=\\mathcal\{S\}\\times\\mathcal\{S\}, i\.e\. that the contraction acts on every coordinate\. A top\-k′k^\{\\prime\}index coversO​\(\|𝒮\|​k′\)O\(\|\\mathcal\{S\}\|k^\{\\prime\}\)of the\(\|𝒮\|2\)\\binom\{\|\\mathcal\{S\}\|\}\{2\}pairs; without re\-seeding the complement isΘ​\(\|𝒮\|2\)\\Theta\(\|\\mathcal\{S\}\|^\{2\}\)and frozen, soρ\>0\\rho\>0generically and, by Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3), the realized error is exactlyρ\\rho, however smallε\\varepsilonis\. Proposition[4](https://arxiv.org/html/2608.06762#Thmtheorem4)\(i\) makes this unconditional with a construction on which every per\-step quantity is zero\. The verification of §[Experiments](https://arxiv.org/html/2608.06762#Sx5)exhibits the failure on generic instances under the conventional accounting \(e\.g\. at\|𝒮\|=10\|\\mathcal\{S\}\|=10,k′=6k^\{\\prime\}=6, coverage gapρ≈1\.10\\rho\\approx 1\.10against per\-step term≈0\.80\\approx 0\.80\)\.

## Appendix CProof of Proposition[4](https://arxiv.org/html/2608.06762#Thmtheorem4)

Throughout, all transition kernels are identical across states and instances \(sayP\(⋅∣s,a\)=Unif\(𝒮\)P\(\\cdot\\mid s,a\)=\\mathrm\{Unif\}\(\\mathcal\{S\}\)\), so for any ground cost the transported cost between any two states’ next\-state distributions is0; the pair\-evaluation answers are therefore the per\-action reward differences together with zeros, whatever transport convention the model adopts, and the exact metric isd​\(s,t\)=maxa⁡\|R​\(s,a\)−R​\(t,a\)\|d\(s,t\)=\\max\_\{a\}\|R\(s,a\)\-R\(t,a\)\|\. All constructions place rewards in\[0,ρ0\]⊆\[0,L\]\[0,\\rho\_\{0\}\]\\subseteq\[0,L\]after adding the constantρ0/2\\rho\_\{0\}/2, which changes no difference\.

#### Part \(i\): oblivious coverage\.

Given an unordered pair\(i,j\)\(i,j\)and a signb∈\{\+1,−1\}b\\in\\\{\+1,\-1\\\}, define the instanceMi,j,bM\_\{i,j,b\}byR​\(x,a\)=0R\(x,a\)=0forx∉\{i,j\}x\\notin\\\{i,j\\\},R​\(i,a\)=ρ0/2R\(i,a\)=\\rho\_\{0\}/2, andR​\(j,a\)=b​ρ0/2R\(j,a\)=b\\,\\rho\_\{0\}/2, for everyaa\. Thend​\(i,j\)=ρ0⋅𝟏​\[b=−1\]d\(i,j\)=\\rho\_\{0\}\\cdot\\mathbf\{1\}\[b=\-1\], while for every other pair the answers arebb\-independent:\|R​\(i,a\)−R​\(x,a\)\|=\|R​\(j,a\)−R​\(x,a\)\|=ρ0/2\|R\(i,a\)\-R\(x,a\)\|=\|R\(j,a\)\-R\(x,a\)\|=\\rho\_\{0\}/2and\|R​\(x,a\)−R​\(y,a\)\|=0\|R\(x,a\)\-R\(y,a\)\|=0forx,y∉\{i,j\}x,y\\notin\\\{i,j\\\}\.

Let the coverage rule selectQQwithout access toRR\(obliviousness\); its distribution is therefore independent of\(i,j,b\)\(i,j,b\)\. Deterministic case:\|Q\|=o​\(\|𝒮\|2\)<\(\|𝒮\|2\)\|Q\|=o\(\|\\mathcal\{S\}\|^\{2\}\)<\\binom\{\|\\mathcal\{S\}\|\}\{2\}, so some pair\(i,j\)∉Q\(i,j\)\\notin Q; plant there\. Every evaluated quantity is identical inMi,j,\+1M\_\{i,j,\+1\}andMi,j,−1M\_\{i,j,\-1\}, so any output computable from the evaluations \(including any embedding built from them and any value interpolated in that embedding\) takes the same valuevvfor\(i,j\)\(i,j\)in both instances, andmaxb⁡\|v−db​\(i,j\)\|≥\(\|v−0\|\+\|v−ρ0\|\)/2≥ρ0/2\\max\_\{b\}\|v\-d\_\{b\}\(i,j\)\|\\geq\\big\(\|v\-0\|\+\|v\-\\rho\_\{0\}\|\\big\)/2\\geq\\rho\_\{0\}/2\. Randomized case: draw\(i,j\)\(i,j\)uniformly from all pairs andbbuniformly, independently of the rule’s randomness;Pr⁡\[\(i,j\)∈Q\]≤𝔼​\|Q\|/\(\|𝒮\|2\)=o​\(1\)\\Pr\[\(i,j\)\\in Q\]\\leq\\mathbb\{E\}\|Q\|/\\binom\{\|\\mathcal\{S\}\|\}\{2\}=o\(1\), and conditioned on\(i,j\)∉Q\(i,j\)\\notin Qthe transcript isbb\-independent, so𝔼​‖d^−d‖∞≥𝔼​\[\|v\(i,j\)−db​\(i,j\)\|\|\(i,j\)∉Q\]​Pr⁡\[\(i,j\)∉Q\]≥\(1−o​\(1\)\)​ρ0/2\\mathbb\{E\}\\left\\lVert\\hat\{d\}\-d\\right\\rVert\_\{\\infty\}\\geq\\mathbb\{E\}\\big\[\\,\|v\_\{\(i,j\)\}\-d\_\{b\}\(i,j\)\|\\;\\big\|\\;\(i,j\)\\notin Q\\big\]\\Pr\[\(i,j\)\\notin Q\]\\geq\(1\-o\(1\)\)\\,\\rho\_\{0\}/2\.

*Why obliviousness is needed\.*A reward\-adaptive prober defeats any single planted pair: evaluating\(1,x\)\(1,x\)for allxxreturnsρ0/2\\rho\_\{0\}/2exactly whenx∈\{i,j\}x\\in\\\{i,j\\\}\(or reveals1∈\{i,j\}1\\in\\\{i,j\\\}\), soO​\(\|𝒮\|\)O\(\|\\mathcal\{S\}\|\)evaluations locate the pair, and one more reads it\. Part \(ii\) therefore hidesΘ​\(\|𝒮\|\)\\Theta\(\|\\mathcal\{S\}\|\)independent bits, each readable only at its own pair\.

#### Part \(ii\): adaptive coverage\.

Let\|𝒮\|=n\|\\mathcal\{S\}\|=nbe even, group states into partner pairsPℓ=\{2​ℓ−1,2​ℓ\}P\_\{\\ell\}=\\\{2\\ell\-1,2\\ell\\\}forℓ≤n/2\\ell\\leq n/2, and take\|𝒜\|=n/2\|\\mathcal\{A\}\|=n/2actionsa1,…,an/2a\_\{1\},\\dots,a\_\{n/2\}\. Draw independent uniform bitssℓ∈\{\+1,−1\}s\_\{\\ell\}\\in\\\{\+1,\-1\\\}and setR​\(2​ℓ−1,aℓ\)=ρ0/2R\(2\\ell\-1,a\_\{\\ell\}\)=\\rho\_\{0\}/2,R​\(2​ℓ,aℓ\)=sℓ​ρ0/2R\(2\\ell,a\_\{\\ell\}\)=s\_\{\\ell\}\\rho\_\{0\}/2, andR​\(x,am\)=0R\(x,a\_\{m\}\)=0otherwise\. The evaluation of a partner pairPℓP\_\{\\ell\}returns, in coordinateaℓa\_\{\\ell\},ρ02​\|1−sℓ\|∈\{0,ρ0\}\\tfrac\{\\rho\_\{0\}\}\{2\}\|1\-s\_\{\\ell\}\|\\in\\\{0,\\rho\_\{0\}\\\}, revealingsℓs\_\{\\ell\}; henced​\(Pℓ\)∈\{0,ρ0\}d\(P\_\{\\ell\}\)\\in\\\{0,\\rho\_\{0\}\\\}according tosℓs\_\{\\ell\}\. The evaluation of any non\-partner pair\{u,v\}\\\{u,v\\\}returns, in each coordinateama\_\{m\}, the valueρ0/2\\rho\_\{0\}/2if exactly one ofu,vu,vlies inPmP\_\{m\}and0otherwise, independent of every bit, since\|sm​ρ0/2−0\|=ρ0/2\|s\_\{m\}\\rho\_\{0\}/2\-0\|=\\rho\_\{0\}/2regardless ofsms\_\{m\}\.

Consequently, after any sequence of evaluations, the transcript is a deterministic function of the queries and of the bits of the partner pairs evaluated so far; by the principle of deferred decisions, conditioned on the transcriptτ\\tau, the bits of unevaluated partner pairs remain independent and uniform\. Suppose the algorithm \(adaptive; randomized, by additionally conditioning on its random string\) performsQ<n/2Q<n/2evaluations\. At mostQQpartner pairs are evaluated, so the transcript\-measurable set of unevaluated partner pairs is nonempty; letp⋆​\(τ\)p^\{\\star\}\(\\tau\)be the one of smallest index\. The output valuevp⋆v\_\{p^\{\\star\}\}isτ\\tau\-measurable, whiled​\(p⋆\)∈\{0,ρ0\}d\(p^\{\\star\}\)\\in\\\{0,\\rho\_\{0\}\\\}is uniform givenτ\\tau, so𝔼​\[‖d^−d‖∞\|τ\]≥𝔼​\[\|vp⋆−d​\(p⋆\)\|\|τ\]≥ρ0/2\\mathbb\{E\}\\big\[\\left\\lVert\\hat\{d\}\-d\\right\\rVert\_\{\\infty\}\\,\\big\|\\,\\tau\\big\]\\geq\\mathbb\{E\}\\big\[\\,\|v\_\{p^\{\\star\}\}\-d\(p^\{\\star\}\)\|\\,\\big\|\\,\\tau\\big\]\\geq\\rho\_\{0\}/2; taking expectation overτ\\taugives the claim\.∎

planted gapρ0\\rho\_\{0\}0\.10\.10\.40\.40\.80\.81\.21\.2realized global error0\.10\.10\.40\.40\.80\.81\.21\.2Table 3:Matching lower bound, construction \(i\) of Proposition[4](https://arxiv.org/html/2608.06762#Thmtheorem4)\(reward\-oblivious coverage; correlation between planted gap and realized error is1\.01\.0\)\. The realized global error of a bounded\-coverage oblivious algorithm equals the planted hidden\-pair distanceρ0\\rho\_\{0\}exactly; the hidden pair uses identical kernels, so embedding distortion and recall are irrelevant by construction\. At fixed budgetk′=8k^\{\\prime\}=8the error is independent of\|𝒮\|\|\\mathcal\{S\}\|as coverage→0\\to 0\(falling from42%42\\%at\|𝒮\|=20\|\\mathcal\{S\}\|=20to5%5\\%at\|𝒮\|=160\|\\mathcal\{S\}\|=160\), and full coverage drives it to0\.

## Appendix DThe Upper Arm and the Sandwich: Proofs and Verification

#### Mechanism\.

Under the lower arm’s under\-estimate freeze, an un\-retrieved pair reads as its initialization \(ford0=0d\_\{0\}=0, as*identical*\), so a threshold rule merges states that were never compared; worse, theW1W\_\{1\}backup at a covered pair transports against a cost matrix whose un\-retrieved entries are under\-estimates, dragging covered values down as well \(Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)\(D\) bounds, but does not eliminate, this one\-sided effect\)\. Both pressures push distinct states into one cluster\. Freezing un\-retrieved pairs at an upper bound reverses the sign of every error, which is what makes aggregation safe and the two\-armed enclosure possible\.

###### Lemma 13\(Constant super\-solution\)\.

LetU≡Dγ=L/\(1−γ\)U\\equiv D\_\{\\gamma\}=L/\(1\-\\gamma\)off\-diagonal \(0on the diagonal\)\. ThenU≥dU\\geq dpointwise andT​U≤UTU\\leq Uon every pair\.

###### Proof\.

d≤Dγd\\leq D\_\{\\gamma\}pointwise \(Appendix[B](https://arxiv.org/html/2608.06762#A2), setup\)\. For the second claim,W1U​\(μ,ν\)≤‖U‖∞=DγW\_\{1\}^\{U\}\(\\mu,\\nu\)\\leq\\left\\lVert U\\right\\rVert\_\{\\infty\}=D\_\{\\gamma\}for anyμ,ν\\mu,\\nu\(unit mass\), soT​U≤L\+γ​Dγ=Dγ=UTU\\leq L\+\\gamma D\_\{\\gamma\}=D\_\{\\gamma\}=U\. ∎

#### Proof of Proposition[5](https://arxiv.org/html/2608.06762#Thmtheorem5)\.

*\(i\)\.*Initializef0\+=Uf\_\{0\}^\{\+\}=Ueverywhere and freezeft\+=Uf\_\{t\}^\{\+\}=Uoff𝒞\\mathcal\{C\}\. By Lemma[13](https://arxiv.org/html/2608.06762#Thmtheorem13),f1\+=T^​f0\+≤f0\+f\_\{1\}^\{\+\}=\\hat\{T\}f\_\{0\}^\{\+\}\\leq f\_\{0\}^\{\+\}\(on𝒞\\mathcal\{C\},T​U≤UTU\\leq U; off𝒞\\mathcal\{C\}, equality\), and monotonicity ofT^\\hat\{T\}\(Lemma[9](https://arxiv.org/html/2608.06762#Thmtheorem9)\(d\)\) propagatesft\+1\+≤ft\+f\_\{t\+1\}^\{\+\}\\leq f\_\{t\}^\{\+\}\. Lower invariance:f0\+=U≥df\_\{0\}^\{\+\}=U\\geq d, and iff≥df\\geq dthen on𝒞\\mathcal\{C\},T​f≥T​d=dTf\\geq Td=d, while off𝒞\\mathcal\{C\},U≥dU\\geq d; henceft\+≥df\_\{t\}^\{\+\}\\geq dfor alltt\. A monotone bounded sequence on finitely many pairs converges tod^\+≥d\\hat\{d\}^\{\+\}\\geq d, the unique fixed point ofT^\\hat\{T\}on\{f=U​off​𝒞\}\\\{f=U\\text\{ off \}\\mathcal\{C\}\\\}\(the argument of Lemma[11](https://arxiv.org/html/2608.06762#Thmtheorem11)verbatim\)\.

*\(ii\)\.*Ifd^\+​\(s,s′\)≤τ<U\\hat\{d\}^\{\+\}\(s,s^\{\\prime\}\)\\leq\\tau<Uthen\(s,s′\)∈𝒞\(s,s^\{\\prime\}\)\\in\\mathcal\{C\}\(uncovered entries equalUU\) andd​\(s,s′\)≤d^\+​\(s,s′\)≤τd\(s,s^\{\\prime\}\)\\leq\\hat\{d\}^\{\+\}\(s,s^\{\\prime\}\)\\leq\\tauby \(i\)\. For refinement, lets∼d^\+s′s\\sim\_\{\\hat\{d\}^\{\+\}\}s^\{\\prime\}at thresholdτ\\tau, i\.e\. there is a chains=u0,u1,…,uk=s′s=u\_\{0\},u\_\{1\},\\dots,u\_\{k\}=s^\{\\prime\}withd^\+​\(ui−1,ui\)≤τ\\hat\{d\}^\{\+\}\(u\_\{i\-1\},u\_\{i\}\)\\leq\\taufor eachii; every link satisfiesd​\(ui−1,ui\)≤τd\(u\_\{i\-1\},u\_\{i\}\)\\leq\\tau, so the same chain witnessess∼ds′s\\sim\_\{d\}s^\{\\prime\}\. Hence each single\-linkage cluster ofd^\+\\hat\{d\}^\{\+\}is contained in a cluster ofddat the sameτ\\tau\.

*\(iii\)\.*If clusterKKofd^\+\\hat\{d\}^\{\+\}is contained in clusterK′K^\{\\prime\}ofdd, thenmaxs,s′∈K⁡d​\(s,s′\)≤maxs,s′∈K′⁡d​\(s,s′\)\\max\_\{s,s^\{\\prime\}\\in K\}d\(s,s^\{\\prime\}\)\\leq\\max\_\{s,s^\{\\prime\}\\in K^\{\\prime\}\}d\(s,s^\{\\prime\}\), so the maximum within\-cluster exact\-metric diameter underd^\+\\hat\{d\}^\{\+\}\-aggregation is at most that underdd\-aggregation at the sameτ\\tau\. The optimal value function is11\-Lipschitz indd\(Ferns and Precup[2014](https://arxiv.org/html/2608.06762#bib.bib6)\), so value variation within any cluster is at most itsdd\-diameter, and the approximate\-abstraction value\-loss bounds ofLiet al\.\([2006](https://arxiv.org/html/2608.06762#bib.bib17)\)\(for a fixed within\-cluster weighting\) are nondecreasing functions of the within\-cluster discrepancy\. Any such certificate therefore assignsd^\+\\hat\{d\}^\{\+\}\-aggregation a loss bound no larger than exact\-metric aggregation at the same threshold\. This is a comparison of*certificates*, which is the object a practitioner can compute; it implies nothing weaker than the exact\-metric guarantee at the sameτ\\tau\.

*\(iv\)\.*Uncovered pairs sit atUUfor everytt, so their error isU−d∈\[0,ρ\+\]U\-d\\in\[0,\\rho^\{\+\}\]with maximum exactlyρ\+\\rho^\{\+\}by definition\. On covered pairs, at the fixed point and usingd^\+≥d\\hat\{d\}^\{\+\}\\geq d,

d^\+​\(p\)−d​\(p\)=T​d^\+​\(p\)−T​d​\(p\)≤γ​‖d^\+−d‖∞=γ​max⁡\(e∞\+,ρ\+\),\\begin\{split\}\\hat\{d\}^\{\+\}\(p\)\-d\(p\)=T\\hat\{d\}^\{\+\}\(p\)\-Td\(p\)&\\leq\\gamma\\left\\lVert\\hat\{d\}^\{\+\}\-d\\right\\rVert\_\{\\infty\}\\\\ &=\\gamma\\max\\big\(e^\{\+\}\_\{\\infty\},\\ \\rho^\{\+\}\\big\),\\end\{split\}wheree∞\+:=max𝒞⁡\(d^\+−d\)e^\{\+\}\_\{\\infty\}:=\\max\_\{\\mathcal\{C\}\}\(\\hat\{d\}^\{\+\}\-d\); if the inner maximum weree∞\+e^\{\+\}\_\{\\infty\}we would gete∞\+≤γ​e∞\+=0≤γ​ρ\+e^\{\+\}\_\{\\infty\}\\leq\\gamma e^\{\+\}\_\{\\infty\}=0\\leq\\gamma\\rho^\{\+\}, otherwisee∞\+≤γ​ρ\+e^\{\+\}\_\{\\infty\}\\leq\\gamma\\rho^\{\+\}directly\. Hencee∞\+≤γ​ρ\+≤ρ\+e^\{\+\}\_\{\\infty\}\\leq\\gamma\\rho^\{\+\}\\leq\\rho^\{\+\}and‖d^\+−d‖∞=max⁡\(e∞\+,ρ\+\)=ρ\+\\left\\lVert\\hat\{d\}^\{\+\}\-d\\right\\rVert\_\{\\infty\}=\\max\(e^\{\+\}\_\{\\infty\},\\rho^\{\+\}\)=\\rho^\{\+\}, the mirror of Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)\(D\) and Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3)\.∎

#### Proof of Corollary[6](https://arxiv.org/html/2608.06762#Thmtheorem6)\.

*\(a\) with growing coverage\.*Let𝒞0⊆𝒞1⊆⋯\\mathcal\{C\}\_\{0\}\\subseteq\\mathcal\{C\}\_\{1\}\\subseteq\\cdotsbe the cumulative covered sets of the pipeline and consider the lower arm \(the upper arm is the mirror image with all inequalities reversed andUUin place ofd0d\_\{0\}\)\. We prove by induction thatft\+1−≥ft−f\_\{t\+1\}^\{\-\}\\geq f\_\{t\}^\{\-\}andft−≤df\_\{t\}^\{\-\}\\leq dpointwise for alltt\. Both hold att=0t=0\. For the upper invariant: iff≤df\\leq dthen every backup valueT​f​\(p\)≤T​d​\(p\)=d​\(p\)Tf\(p\)\\leq Td\(p\)=d\(p\)\(Lemma[9](https://arxiv.org/html/2608.06762#Thmtheorem9)\(d\)\) and every frozen value isd0​\(p\)≤d​\(p\)d\_\{0\}\(p\)\\leq d\(p\), soft\+1−≤df\_\{t\+1\}^\{\-\}\\leq d\. For monotonicity, take any pairpp\. Ifp∉𝒞t\+1p\\notin\\mathcal\{C\}\_\{t\+1\}thenft\+1−​\(p\)=d0​\(p\)=ft−​\(p\)f\_\{t\+1\}^\{\-\}\(p\)=d\_\{0\}\(p\)=f\_\{t\}^\{\-\}\(p\)\. Ifp∈𝒞tp\\in\\mathcal\{C\}\_\{t\}thenft\+1−​\(p\)=T​ft−​\(p\)≥T​ft−1−​\(p\)=ft−​\(p\)f\_\{t\+1\}^\{\-\}\(p\)=Tf\_\{t\}^\{\-\}\(p\)\\geq Tf\_\{t\-1\}^\{\-\}\(p\)=f\_\{t\}^\{\-\}\(p\)by the induction hypothesis and Lemma[9](https://arxiv.org/html/2608.06762#Thmtheorem9)\(d\)\. Ifppis newly covered \(p∈𝒞t\+1∖𝒞tp\\in\\mathcal\{C\}\_\{t\+1\}\\setminus\\mathcal\{C\}\_\{t\}\), thenft−​\(p\)=d0​\(p\)f\_\{t\}^\{\-\}\(p\)=d\_\{0\}\(p\)andft\+1−​\(p\)=T​ft−​\(p\)≥dR​\(p\)≥d0​\(p\)f\_\{t\+1\}^\{\-\}\(p\)=Tf\_\{t\}^\{\-\}\(p\)\\geq d\_\{R\}\(p\)\\geq d\_\{0\}\(p\)by Lemma[9](https://arxiv.org/html/2608.06762#Thmtheorem9)\(e\): the newly covered entry leaves its frozen value in the monotone direction\. Henceft−f\_\{t\}^\{\-\}is nondecreasing and≤d\\leq d; the upper arm is nonincreasing and≥d\\geq d\(usingT​U≤UTU\\leq U, Lemma[13](https://arxiv.org/html/2608.06762#Thmtheorem13), at newly covered entries\), giving the sandwichft−≤d≤ft\+f\_\{t\}^\{\-\}\\leq d\\leq f\_\{t\}^\{\+\}at everytt\.

*\(b\)\.*Immediate from \(a\):d​\(p\)∈\[ft−​\(p\),ft\+​\(p\)\]d\(p\)\\in\[f\_\{t\}^\{\-\}\(p\),f\_\{t\}^\{\+\}\(p\)\], so both endpoint errors are at most the width; off the current covered set both arms sit at their initializations, sowt​\(p\)=U−d0​\(p\)w\_\{t\}\(p\)=U\-d\_\{0\}\(p\)there\.

*\(c\)\.*At the fixed points on a common final covered set,w∞​\(p\)=\(d^\+−d\)​\(p\)\+\(d−d^\)​\(p\)≤γ​ρ\+\+γ​ρw\_\{\\infty\}\(p\)=\(\\hat\{d\}^\{\+\}\-d\)\(p\)\+\(d\-\\hat\{d\}\)\(p\)\\leq\\gamma\\rho^\{\+\}\+\\gamma\\rhoforp∈𝒞p\\in\\mathcal\{C\}, by Proposition[5](https://arxiv.org/html/2608.06762#Thmtheorem5)\(iv\) and Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)\(D\)\.

*\(d\)\.*Over covered pairs, \(a\) gives the edge\-set inclusions\{p∈𝒞:ft\+​\(p\)≤τ\}⊆\{p∈𝒞:d​\(p\)≤τ\}⊆\{p∈𝒞:ft−​\(p\)≤τ\}\\\{p\\in\\mathcal\{C\}:f\_\{t\}^\{\+\}\(p\)\\leq\\tau\\\}\\subseteq\\\{p\\in\\mathcal\{C\}:d\(p\)\\leq\\tau\\\}\\subseteq\\\{p\\in\\mathcal\{C\}:f\_\{t\}^\{\-\}\(p\)\\leq\\tau\\\}\. Connected components coarsen as edges are added, soΠτ\+\\Pi^\{\+\}\_\{\\tau\}refinesΠτ𝒞\\Pi^\{\\mathcal\{C\}\}\_\{\\tau\}, which refinesΠτ−\\Pi^\{\-\}\_\{\\tau\}\. If the two ends of a refinement chain coincide, every intermediate partition coincides with them; henceΠτ\+=Πτ−\\Pi^\{\+\}\_\{\\tau\}=\\Pi^\{\-\}\_\{\\tau\}forces all three equal, certifyingΠτ𝒞\\Pi^\{\\mathcal\{C\}\}\_\{\\tau\}exactly\. Under re\-seeding with every pair eventually covered,Πτ𝒞\\Pi^\{\\mathcal\{C\}\}\_\{\\tau\}is eventually the clustering of the exact metric over all pairs\.∎

#### Verification\.

On MDPs with planted behavioral groups \(within\-group distanceO​\(ε\)O\(\\varepsilon\), cross\-groupΘ​\(1\)\\Theta\(1\)\), we aggregate at thresholds between the two bands, solve the aggregated MDP, lift the greedy policy, and measure normalized value loss againstV⋆V^\{\\star\}\(Table[4](https://arxiv.org/html/2608.06762#A4.T4)\)\. In the operating regime \(thresholds at which exact\-metric aggregation is itself faithful\), upper\-arm aggregation matches exact\-metric aggregation to within0\.00\.0mean absolute value loss over eight seeds, with a positive over\-estimation bias \(\+0\.33\+0\.33\) on covered cross\-group pairs exactly as Proposition[5](https://arxiv.org/html/2608.06762#Thmtheorem5)\(i\) predicts, while the under\-estimate freeze collapses every instance to a single cluster \(value loss2\.862\.86versus0\.030\.03for exact\)\. Past the operating regime, where the exact metric’s own single\-linkage begins to over\-merge, the upper arm is no worse than exact, consistent with the refinement of \(ii\)\. The sandwich checks on the same instances: enclosure at every sweep in all8080runs, and the refinement chainΠτ\+⪯Πτ𝒞⪯Πτ−\\Pi^\{\+\}\_\{\\tau\}\\preceq\\Pi^\{\\mathcal\{C\}\}\_\{\\tau\}\\preceq\\Pi^\{\-\}\_\{\\tau\}in all8080; the certifying equalityΠτ\+=Πτ−\\Pi^\{\+\}\_\{\\tau\}=\\Pi^\{\-\}\_\{\\tau\}is rare at the single\-build budget \(3\.7%3\.7\\%of threshold–configuration triples\) because generic random MDPs do not exhibit a clean distance margin at arbitrary thresholds\. On the planted\-group benchmark, the threshold lies between separated within\- and cross\-group bands, so the same squeeze is much easier and holds in8/88/8seeds at\|𝒮\|=120\|\\mathcal\{S\}\|=120\. Re\-seeding with a uniform\-exploration component drives generic coverage to100%100\\%and closes the remaining ambiguity in two of three seeds within1010rounds \(Corollary[6](https://arxiv.org/html/2608.06762#Thmtheorem6)\(d\)\)\. The coverage gap is thus benign for the downstream task precisely when the metric is maintained as an upper bound, and jointly with the lower arm it is*certifiably*benign wherever the two arms agree\.

Table 4:Downstream value loss of the lifted greedy policy \(normalized,↓\\downarrowbetter; eight seeds,\|𝒮\|=30\|\\mathcal\{S\}\|=30, six planted groups\)\. In the operating regime \(bands0\.250\.25–0\.50\.5\) upper\-arm aggregation matches exact\-metric aggregation, as Proposition[5](https://arxiv.org/html/2608.06762#Thmtheorem5)certifies, whereas the under\-estimate freeze over\-merges to one cluster\. Beyond the regime the upper arm is no worse than exact, consistent with refinement\.

## Appendix EExperimental Protocol and Implementation

Each component the theory refers to is implemented exactly as the algorithms state, with no surrogate\. The bisimulation backup \([1](https://arxiv.org/html/2608.06762#Sx2.E1)\) uses a*true*Wasserstein\-1 term solved by Kantorovich linear program under ground cost equal to the current iterate \(the exact backup of line[9](https://arxiv.org/html/2608.06762#alg2.l9);εop=0\\varepsilon\_\{\\mathrm\{op\}\}=0, so Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)\(D\), Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3), and Proposition[5](https://arxiv.org/html/2608.06762#Thmtheorem5)\(iv\) apply\); the embeddingϕ\\phiis a real multidimensional\-scaling embedding intoℝ6\\mathbb\{R\}^\{6\}\(Cox and Cox[2001](https://arxiv.org/html/2608.06762#bib.bib45)\), with the additive distortionη\\etaof \([2](https://arxiv.org/html/2608.06762#Sx3.E2)\)*measured*pairwise; and the index is a real random\-hyperplane LSH index\(Charikar[2002](https://arxiv.org/html/2608.06762#bib.bib35)\)overϕ\\phi, built*once per run*\(persistent coverage\), with the recall missrr*measured*against the true embedding nearest neighbors\. No product\-coupling surrogate, fixed\-embedding shortcut, or exact\-sort stand\-in for the ANN index is used\. The bound\-validation arm initializes atd0=0d\_\{0\}=0\(worst case, for which Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3)predicts the largest identity value\); the deployment arm atd0=dRd\_\{0\}=d\_\{R\}\(implicit\)\. Across the synchronized eight\-configuration grid, the row\-mean distortions averageη=0\.107\\eta=0\.107and the coverage gap averagesρ=1\.16\\rho=1\.16\(underd0=0d\_\{0\}=0\); withd0=dRd\_\{0\}=d\_\{R\}the gap shrinks to0\.730\.73\(ratio0\.630\.63\), as the reward pseudo\-metric provably reduces it\.

## Appendix FThe Bound Audit: Full Figures

Figures[3](https://arxiv.org/html/2608.06762#A6.F3)and[4](https://arxiv.org/html/2608.06762#A6.F4)are generated directly from Table[1](https://arxiv.org/html/2608.06762#Sx5.T1)in the main text and use its exact row order\.

112233445566778800\.50\.511configuration index \(rows of Table[1](https://arxiv.org/html/2608.06762#Sx5.T1)\)valueglobal error=ρ=\\rho\(Cor\.[3](https://arxiv.org/html/2608.06762#Thmtheorem3)\)covered\-submetric errorFigure 3:Realized error on covered pairs \(blue\) versus globally \(red\), in the row order of Table[1](https://arxiv.org/html/2608.06762#Sx5.T1)\. The covered error stays below the exact\-backup boundγ​ρ\\gamma\\rhoof Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)\(D\), while the global error equals the coverage gapρ\\rhoset by the never\-retrieved pairs \(Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3)\): the index updates its neighbors accurately but cannot reach the rest\.112233445566778801122configuration index \(Table[1](https://arxiv.org/html/2608.06762#Sx5.T1)\)global error / boundrealized global errornaive per\-step expressioncoverage\-augmented boundFigure 4:Synchronized bound audit in the row order of Table[1](https://arxiv.org/html/2608.06762#Sx5.T1)\. The naive expression falls below realized error in configurations33and44\. The corrected series is computed asmax⁡\{ρ,\(η\+L​r\)/\(1−γ\)\}\\max\\\{\\rho,\(\\eta\+Lr\)/\(1\-\\gamma\)\\\}from the same table and is therefore valid in every row; configuration22illustrates why the maximum must be evaluated rather than rounded independently\.
## Appendix GCertificate Verification and Re\-Seeding

#### The sandwich certificate, verified\.

On the eight configurations of Table[1](https://arxiv.org/html/2608.06762#Sx5.T1)\(1010seeds,8080runs\) we run the upper arm alongside the lower arm and check Corollary[6](https://arxiv.org/html/2608.06762#Thmtheorem6): the enclosureft−≤d≤ft\+f\_\{t\}^\{\-\}\\leq d\\leq f\_\{t\}^\{\+\}holds at every sweep in80/8080/80runs; the lower and upper identities‖f−−d‖∞=ρ\\left\\lVert f^\{\-\}\-d\\right\\rVert\_\{\\infty\}=\\rhoand‖d^\+−d‖∞=ρ\+\\left\\lVert\\hat\{d\}^\{\+\}\-d\\right\\rVert\_\{\\infty\}=\\rho^\{\+\}\(Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3), Proposition[5](https://arxiv.org/html/2608.06762#Thmtheorem5)\(iv\)\) each hold to machine precision in80/8080/80; the limit covered width never exceedsγ​\(ρ\+ρ\+\)\\gamma\(\\rho\+\\rho^\{\+\}\)\(80/8080/80; realized mean covered width0\.800\.80against the mean bound2\.702\.70\); and on uncovered pairs the width equalsU−d0U\-d\_\{0\}exactly, i\.e\. the certificate itself displays the coverage frontier\. The refinement chainΠτ\+⪯Πτ𝒞⪯Πτ−\\Pi^\{\+\}\_\{\\tau\}\\preceq\\Pi^\{\\mathcal\{C\}\}\_\{\\tau\}\\preceq\\Pi^\{\-\}\_\{\\tau\}of Corollary[6](https://arxiv.org/html/2608.06762#Thmtheorem6)\(d\) holds in80/8080/80, but the*equality*that certifies the exact covered clustering is rare at the single\-build budget \(Πτ\+=Πτ−\\Pi^\{\+\}\_\{\\tau\}=\\Pi^\{\-\}\_\{\\tau\}in only99of240240threshold\-configuration\-seed cases,3\.7%3\.7\\%\): a single index leaves too many covered links undecided between the arms\. Re\-seeding with fresh hyperplanes is the intended remedy, but pure LSH re\-seeding saturates at≈82\\approx 82–84%84\\%coverage \(its near\-neighbor bias never draws the far pairs that setρ\\rho\), so equality is reached only on the covered portion \(one of three seeds\)\. Adding a single uniform\-random pair per state per round, which makes every pair retrieved infinitely often \(the hypothesis of Corollary[7](https://arxiv.org/html/2608.06762#Thmtheorem7)\), drives coverage to100%100\\%in all three seeds and reaches full\-clustering equalityΠτ\+=Πτ−\\Pi^\{\+\}\_\{\\tau\}=\\Pi^\{\-\}\_\{\\tau\}in two of three within1010rounds\. The certificate’s honesty on uncovered pairs is thus not a defect but the coverage frontier made visible, and closing it provably requires the exploration that Proposition[4](https://arxiv.org/html/2608.06762#Thmtheorem4)shows is unavoidable\.

#### Re\-seeding ablations \(Corollary[7](https://arxiv.org/html/2608.06762#Thmtheorem7)\)\.

In an evolving\-embedding run at\|𝒮\|=18\|\\mathcal\{S\}\|=18andk′=3k^\{\\prime\}=3, fresh pure\-LSH rebuilds eventually reached full coverage after275275re\-seeds because re\-embedding changed the bucket geometry over time\. In a frozen\-embedding ablation, pure\-LSH re\-seeding saturated at8282–84%84\\%coverage because the same far pairs remained unlikely under every hash rebuild\. The mixed policy in Algorithm[1](https://arxiv.org/html/2608.06762#alg1)does not depend on either empirical behavior: adding one uniform partner per state reached full coverage in all three reported\|𝒮\|=18\|\\mathcal\{S\}\|=18runs and producedΠτ\+=Πτ−\\Pi^\{\+\}\_\{\\tau\}=\\Pi^\{\-\}\_\{\\tau\}in two of three within ten rounds\. The terminal covered error0\.0550\.055in the long pure\-LSH run is a finite\-schedule transient, not a distortion floor, and continued mixed re\-seeding drives it to zero by Corollary[7](https://arxiv.org/html/2608.06762#Thmtheorem7)\(b\)\.

#### The certified pipeline end\-to\-end \(Algorithm[1](https://arxiv.org/html/2608.06762#alg1)\)\.

The bound validation above embeds the converged exact metric to measureη\\etaagainst ground truth; a practitioner cannot do this\. We therefore run Algorithm[1](https://arxiv.org/html/2608.06762#alg1)as stated: initialize implicitly atd0=dRd\_\{0\}=d\_\{R\}andUU, embeddRd\_\{R\}by landmark MDS, build LSH, and re\-seed everyE=3E=3sweeps until the certificate meets tolerance\. Across3232seeded configurations \(\|𝒮\|∈\{10,18\}\|\\mathcal\{S\}\|\\in\\\{10,18\\\},k′∈\{3,6\}k^\{\\prime\}\\in\\\{3,6\\\},88seeds\), the pipeline matches or beats the one\-shot variant in32/3232/32runs \(mean global error0\.220\.22vs1\.181\.18\): successive re\-seeds grow cumulative coverage toward100%100\\%and collapseρt\\rho\_\{t\}from1\.181\.18to0\.100\.10\. At every checkpoint the realized global error equalsmax⁡\(ρt,et\)\\max\(\\rho\_\{t\},\\,e\_\{t\}\), whereete\_\{t\}is the covered transient: early onρt\\rho\_\{t\}dominates and the error tracks it exactly \(the per\-horizon identity of Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3)\); late in the run the transient dominates \(final error0\.220\.22againstρfinal=0\.10\\rho\_\{\\mathrm\{final\}\}=0\.10\), and continued sweeps decay it geometrically per Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)\. The observable counterpart is the two\-arm certificate of Corollary[6](https://arxiv.org/html/2608.06762#Thmtheorem6), verified separately in80/8080/80runs to encloseddat every sweep with covered width at mostγ​\(ρ\+ρ\+\)\\gamma\(\\rho\+\\rho^\{\+\}\)\. The measured distortion falls monotonically across re\-embed rounds \(0\.61→0\.200\.61\\to 0\.20\), tracking convergence of the iterate towarddd\(Corollary[7](https://arxiv.org/html/2608.06762#Thmtheorem7)\(b\)\)\. The pipeline is thus non\-circular, empirically superior to one\-shot, and self\-certifying\.

#### Statistical replication and baselines\.

The eight\-configuration study of Table[1](https://arxiv.org/html/2608.06762#Sx5.T1)is replicated over1010seeds per configuration \(8080runs\)\. The naive bound is violated in11/8011/80runs \(13\.75%13\.75\\%\), all at\|𝒮\|=10\|\\mathcal\{S\}\|=10where the coverage gap is large relative to the per\-step term; the corrected global bound holds in80/8080/80, the identity of Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3)holds in80/8080/80, and the covered error respectsγ​ρ\\gamma\\rhoin80/8080/80\. As a budget\-matched baseline, replacing ANN top\-k′k^\{\\prime\}selection with uniformly random pair coverage \(same budget per sweep\) yields a nearly identical coverage gap \(ρ\\rhoratio ANN/random=1\.04=1\.04\), confirming thatρ\\rhois a property of the budget, not the index quality\. However, ANN coverage combined with the upper arm of Proposition[5](https://arxiv.org/html/2608.06762#Thmtheorem5)cuts the mean\-pair global error2\.5×2\.5\\times\(0\.54→0\.210\.54\\to 0\.21\), because ANN deliberately covers*near*pairs, so far pairs frozen atUUsit close to their true values: structure\-aware coverage plus upper\-bound freezing is strictly better than random coverage under any freeze\.

## Appendix HValidation at Scale

#### Bound validation at scale\.

The same checks are run at\|𝒮\|∈\{50,100,200\}\|\\mathcal\{S\}\|\\in\\\{50,100,200\\\}on sparse\-support MDPs \(Assumption[1](https://arxiv.org/html/2608.06762#Thmassumption1); transport on the union of supports, Lemma[10](https://arxiv.org/html/2608.06762#Thmtheorem10)\), withk′∈\{8,16\}k^\{\\prime\}\\in\\\{8,16\\\}and55seeds per cell \(3030runs\)\. The corrected global bound and the identity hold in30/3030/30; the global error equalsρ\\rhoexactly in every run\. Two scale effects sharpen the paper’s message\. First, coverage collapses as\|𝒮\|\|\\mathcal\{S\}\|grows at fixedk′k^\{\\prime\}\(from21%21\\%of pairs at\|𝒮\|=50\|\\mathcal\{S\}\|=50to5%5\\%at\|𝒮\|=200\|\\mathcal\{S\}\|=200fork′=8k^\{\\prime\}=8\), so at scale the error is governed entirely by coverage, precisely the term the naive analysis omits\. Second, the naive bound is never violated at these sizes, but only because it becomes*vacuous*: with the embedding dimension held fixed while\|𝒮\|\|\\mathcal\{S\}\|grows, the measured distortion rises to0\.950\.95–1\.131\.13, pushing\(η\+L​r\)/\(1−γ\)\(\\eta\+Lr\)/\(1\-\\gamma\)to4\.74\.7–5\.55\.5, beyond the metric diameter2\.02\.0–2\.22\.2, so it can no longer be falsified by any metric\. A bound that survives only by exceeding the diameter certifies nothing;ρ\\rhois the quantity that actually predicts, indeed equals, the error\. The small\-\|𝒮\|\|\\mathcal\{S\}\|study, whereη\\etais small and the naive bound is falsifiable, is where its violations are observable; at scale it degenerates to vacuity instead\. Either way it is the wrong instrument, and Theorem[2](https://arxiv.org/html/2608.06762#Thmtheorem2)\(B\) with Corollary[3](https://arxiv.org/html/2608.06762#Thmtheorem3)holds everywhere\.

#### Downstream RL at scale \(state aggregation\)\.

At\|𝒮\|=120\|\\mathcal\{S\}\|=120\(plantedK=12K=12behavioral groups,\|𝒜\|=3\|\\mathcal\{A\}\|=3,γ=0\.9\\gamma=0\.9,k′=12k^\{\\prime\}=12, threshold between the within\- and cross\-group distance bands, eight seeds\): the ANN metric with the upper arm of Proposition[5](https://arxiv.org/html/2608.06762#Thmtheorem5)matches exact\-metric aggregation statistically \(value loss0\.022±0\.0080\.022\\pm 0\.008against0\.022±0\.0080\.022\\pm 0\.008;1212–1414clusters, mean12\.812\.8, against the exact metric’s1212\); the under\-estimate freeze over\-merges to a single cluster in all seeds \(loss1\.47±0\.551\.47\\pm 0\.55\), confirming at four times the scale the failure mode of §[Two\-Sided Certificates and Downstream Aggregation](https://arxiv.org/html/2608.06762#Sx4.SSx1); budget\-matched random coverage with the upper freeze under\-merges \(2525–4646clusters; loss0\.017±0\.0090\.017\\pm 0\.009; sound but conservative, splitting true groups, exactly the refinement direction Proposition[5](https://arxiv.org/html/2608.06762#Thmtheorem5)\(ii\) permits\); and the reward\-only pseudo\-metric and a budget\-matched single\-sweep sampled metric both collapse to one cluster \(loss1\.47±0\.551\.47\\pm 0\.55\): with matched rewards across groups, only transition information separates them, and neither baseline propagates it\. The upper\-freeze ANN metric is the only sub\-quadratic method in the comparison that recovers the planted structure at this scale, and the certified squeezeΠτ\+=Πτ−\\Pi^\{\+\}\_\{\\tau\}=\\Pi^\{\-\}\_\{\\tau\}of Corollary[6](https://arxiv.org/html/2608.06762#Thmtheorem6)\(d\) holds at the operating threshold in8/88/8seeds at the single\-build budget\.

## Appendix ITaxi\-v3 and the 2500\-State Gridworld

#### The certificate flags failure: Gymnasium Taxi\-v3\.

We run the pipeline on Taxi\-v3, a real MDP with\|𝒮\|=500\|\\mathcal\{S\}\|=500,\|𝒜\|=6\|\\mathcal\{A\}\|=6, deterministic transitions, andγ=0\.9\\gamma=0\.9\. Because the exact metric is inexpensive in this deterministic instance, we compute it only for post\-hoc evaluation; it has diameter200\.5200\.5\. The DBC\-style representation is trained on100,000100\{,\}000random\-policy transitions, and LSH is evaluated atk′∈\{20,40,80\}k^\{\\prime\}\\in\\\{20,40,80\\\}\. Post hoc, the lower\-arm identity holds in every configuration and givesρ=180\.4\\rho=180\.4, close to the exact diameter\. This validates the theory but is not information the runtime algorithm can observe\.

The observable warning is the sandwich itself\. Coverage remains only5%5\\%–20%20\\%, and on the80%80\\%–95%95\\%uncovered pairs the width equalsU−dRU\-d\_\{R\}by construction\. The conservative upper partition therefore certifies essentially no unsupported merges and the pipeline abstains from a coarse abstraction\. For contrast, the uncertified diagnostic that clusters the raw learned embedding at the original threshold collapses to one cluster and incurs value loss45\.945\.9, against15\.815\.8for exact\-metric aggregation\. That number is not an upper\-arm result: labeling it as such would contradict Proposition[5](https://arxiv.org/html/2608.06762#Thmtheorem5)\(ii\)\. Taxi therefore serves as a failure\-detection case, not a speed benchmark; the exact metric itself takes only0\.70\.7seconds\.

#### Scale: a50×5050\\times 50gridworld \(\|𝒮\|=2500\|\\mathcal\{S\}\|=2500\)\.

To demonstrate the pipeline at a scale where the exact all\-pairs sweep is genuinely prohibitive \(\(25002\)=3,123,750\\binom\{2500\}\{2\}=3\{,\}123\{,\}750pairs per sweep\), we construct a50×5050\\times 50gridworld with44actions and2525planted rooms \(10×1010\\times 10blocks of behaviorally similar states sharing base rewards and transition structure up toε\\varepsilon\-noise\), and train a DBC\-style embedding intoℝ8\\mathbb\{R\}^\{8\}from150,000150\{,\}000random\-policy transitions \(22seeds\)\. Withk′=20k^\{\\prime\}=20, each sweep visits\|𝒮\|​k′=50,000\|\\mathcal\{S\}\|k^\{\\prime\}=50\{,\}000pairs \(1\.6%1\.6\\%of the3\.123\.12M\), and88upper\-freeze sweeps \(cumulative≈400,000\\approx 400\{,\}000pair visits,12\.8%12\.8\\%of*one*exact sweep\) complete in≈1200\\approx 1200s on CPU\. Aggregation on the upper\-freeze metric finds254254–284284clusters \(over\-fragmenting the2525rooms into sub\-regions, since low coverage prevents distant within\-room pairs from being linked, exactly the refinement direction Proposition[5](https://arxiv.org/html/2608.06762#Thmtheorem5)\(ii\) permits\), with mean value loss2\.272\.27against the ground\-truthV⋆V^\{\\star\}\(mean8\.58\.5\), while a budget\-matched reward\-only baseline \(dRd\_\{R\}clustering at the same threshold\) collapses to11cluster with mean value loss3\.183\.18: a28\.6%28\.6\\%improvement from transition\-informed structure at the same budget\. This is an honest partial success: the single\-build coverage is too low to recover the rooms cleanly, and re\-seeding to the certificate \(Corollary[6](https://arxiv.org/html/2608.06762#Thmtheorem6)\(d\)\) would close the gap at the quadratic total work Corollary[7](https://arxiv.org/html/2608.06762#Thmtheorem7)quantifies\. But at a fixed sub\-quadratic budget the sub\-quadratic metric is strictly and measurably better than any reward\-only alternative, which is the operational claim\.

## Appendix JCoverage Sweeps against MICo and DBC

Table 5:Downstream value loss on the\|𝒮\|=64\|\\mathcal\{S\}\|=64, eight\-group benchmark at matched compression \(four seeds per budget\)\. MICo and DBC are independently trained and clustered on their own learned distances; our method uses the DBC\-style representation only for retrieval and then runs the exact restricted operator\. “pairs” is cumulative coverage\. Atk′≥16k^\{\\prime\}\\geq 16, our loss reaches the exact skyline on this benchmark, while MICo and DBC are2222–33×33\\timesworse\. Only the proposed two\-arm method supplies an interval enclosing the exact metric\.A larger\-scale robustness check at\|𝒮\|∈\{60,120\}\|\\mathcal\{S\}\|\\in\\\{60,120\\\}uses1616instances and fixedk′=12k^\{\\prime\}=12\. Coverage is approximately41%41\\%at\|𝒮\|=60\|\\mathcal\{S\}\|=60and19%19\\%at\|𝒮\|=120\|\\mathcal\{S\}\|=120, rather than a common value\. The two\-arm certificate is valid on every instance, while neither learned surrogate encloses the exact metric\. At the\|𝒮\|=120\|\\mathcal\{S\}\|=120operating point, our downstream loss is1\.081\.08rather than the0\.0260\.026exact skyline\. This does not contradict Table[5](https://arxiv.org/html/2608.06762#A10.T5): coverage percentage alone does not determine error across different state counts and geometries; the location of uncovered pairs and the resulting certificate width matter\.

To confirm the skyline transition is not an artifact of the\|𝒮\|=64\|\\mathcal\{S\}\|=64benchmark, we repeat the coverage sweep at\|𝒮\|=60\|\\mathcal\{S\}\|=60\(K=6K=6planted groups, four seeds\) over the finer budget gridk′∈\{6,10,14,20,28,40\}k^\{\\prime\}\\in\\\{6,10,14,20,28,40\\\}, holding the state count fixed so that only coverage varies\. The downstream loss falls monotonically in coverage and reaches the exact skyline \(0\.0160\.016\) once the index covers roughly half the pairs: means1\.14,0\.72,0\.81,0\.61,0\.016,0\.0161\.14,0\.72,0\.81,0\.61,0\.016,0\.016at coverage13%,21%,29%,38%,54%,73%13\\%,21\\%,29\\%,38\\%,54\\%,73\\%, so the crossover to the skyline occurs at53\.5%53\.5\\%coverage, the same half\-of\-pairs threshold\. MICo \(1\.821\.82\) and DBC \(0\.930\.93\) are flat across every budget and never enclose the exact metric, and our two\-arm certificate is valid at all six points\. The skyline claim is thus coverage\-controlled and stable in the state count, while the fixed low\-budget\|𝒮\|=120\|\\mathcal\{S\}\|=120operating point above is simply a point below that threshold; the abstract restricts the skyline claim to this grouped coverage\-sweep benchmark\.

### Reproducibility

All experiments are CPU\-only, run on an Apple M5 with 16 GB of unified memory under macOS 26\.5\.1, in Python 3\.11\.13 with NumPy 1\.26\.4, SciPy 1\.12\.0, and Matplotlib 3\.9\.0\. Randomness is drawn from NumPy’sdefault\_rng, seeded per run by composite integer offsets built from a base seed index and the run’s own parameters \(the LSH hyperplane draw combines the seed index with\|𝒮\|\|\\mathcal\{S\}\|and the plane count\); the re\-seed corollary’s fresh\-hyperplane rounds \(Corollary[7](https://arxiv.org/html/2608.06762#Thmtheorem7)\) are the only intentional source of run\-to\-run variation\. The default is1010seeds per configuration \(8080runs, Table[1](https://arxiv.org/html/2608.06762#Sx5.T1)\); the scale study uses55seeds \(3030runs\), the downstream and coverage\-sweep studies88and44seeds respectively, and the gridworld embedding22\. The fixed\-point iteration converges to tolerance10−910^\{\-9\}\. Reproduction is exact modulo library\-version differences in the LP and eigendecomposition routines each result depends on\.