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

• URL: http://arxiv.org/abs/2608.06762v1
• Date: Fri, 07 Aug 2026 03:32:40 GMT
• Title: Sub-Quadratic Bisimulation Metrics via Approximate Nearest Neighbors: Coverage-Augmented Guarantees and Computable Two-Sided Certificates
• Abstract summary: We give a certificate-carrying sub-quadratic method for MDPs with bounded transition support.<n>An approximate-nearest-neighbor index selects the pairs updated by the exact restricted operator.<n>Local index quality alone cannot control global error.
• Score: 1.2891210250935148
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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 most $\max(ρ,\eop/(1-γ))$, and with exact covered backups the lower arm satisfies $\|\dann-d\|_\infty=ρ$. Because $ρ$ depends 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 $Ω(|\Scal|)$ 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 $|\Scal|=64$ benchmark, exact restricted refinement reaches the exact-metric skyline once retrieval covers roughly half of all pairs, while independently trained MICo and DBC baselines stay $22$-$33\times$ above that skyline at every retrieval budget. Taxi shows the certificate abstaining under an uninformative embedding, while a $2500$-state gridworld improves over a reward-only metric by $28.6\%$ using $12.8\%$ of one quadratic sweep.

Related papers

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs [28.99342075394145]
  We introduce CAST (Canonical Approximate Schur Tree), which replaces a dense Schur-complement clique with a weighted random spanning tree.<n>Every realization is connected and contains exactly d-1 edges, while reweighting each selected edge by the reciprocal of its tree-inclusion probability makes the update unbiased.<n>The resulting update remains unbiased and connected, can be sampled exactly in $O(d)$ time, and satisfies a $1/$ bound on the second moment of the normalized local Schur error.
  arXiv  Detail & Related papers  (2026-09-08T15:12:01Z)
• Memorization Is Not Extraction: Tight Differential-Privacy Bounds and Audit Blind Spots [9.539275654775706]
  Memorization in large language models is measured through a zoo of definitions whose formal relations are unknown.<n>We show that differential privacy (DP) is treated as a proxy against all of them at once.
  arXiv  Detail & Related papers  (2026-08-27T23:28:08Z)
• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty.<n>We study how many samples are necessary and sufficient to learn an $varepsilon$-optimal robust policy under the average-reward criterion.
  arXiv  Detail & Related papers  (2026-08-06T19:49:48Z)
• AI-Assisted Discovery of Convex Relaxations via Dual Agents [56.60366723277675]
  We show that a lower bound holds for every admissible function and follows from a convex relaxation giving stronger bounds.<n>A theory verifies each agent one and searches for counterexamples, and every reported bound is certified by an explicit dual-feasible point in the interval.
  arXiv  Detail & Related papers  (2026-06-30T06:10:25Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• The Security Budget of Code-LLM Prompt Hardening: Provable Limits Under Pass-Only Acceptance [0.0]
  We operationalize the floor as the emphTri-Audit Protocol, a two-axis reporting protocol that separates a prompt-side deductive registry attribute from a model-side empirical corollary.<n>A constrained best-of-family search over deterministic and guarded learned filters on CodeLlama-7B, Qwen2.5-Coder-7B/1.5B and DeepSeek-Coder-6.7B at $n=164$ yields the emphCross-Model Tri-Audit Invariance: of twenty-eight pass-preserving rows, twelve-changed-of-record learned-can
  arXiv  Detail & Related papers  (2026-06-02T08:22:14Z)
• A Closed-Form Persistence-Landmark Pipeline for Certified Point-Cloud and Graph Classification [0.0]
  PLACE (Persistence-Landmark Analytic Classification Engine) is a closed-form pipeline for classifying point clouds and graphs.<n>Three quantitative guarantees -- a margin-based excess-risk rate, a closed-form descriptor-selection rule, and a per-prediction certificate -- are derived from training labels alone.
  arXiv  Detail & Related papers  (2026-05-04T17:15:01Z)
• Correction and Corruption: A Two-Rate View of Error Flow in LLM Protocols [51.56484100374058]
  We propose a paired-outcome measurement interface for auditing a single protocol step on exact-match tasks.<n>For each instance, the interface records a baseline correctness bit and a post-step correctness bit.<n>These rates predict accuracy changes and define a reusable empirical interface testable across seeds, mixtures, and pipelines.
  arXiv  Detail & Related papers  (2026-04-20T13:25:40Z)
• Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm [31.539921770584005]
  We propose a Primal-Dual Natural Actor-Critic algorithm that adeptly manages constraints while ensuring a high convergence rate.<n>Our results match the theoretical lower bound for Markov Decision Processes and establish a new benchmark in the theoretical exploration of average reward CMDPs.
  arXiv  Detail & Related papers  (2025-05-21T05:49:11Z)
• MGDA Converges under Generalized Smoothness, Provably [27.87166415148172]
  Multi-objective optimization (MOO) is receiving more attention in various fields such as multi-task learning.<n>Recent works provide some effective algorithms with theoretical analysis but they are limited by the standard $L$-smooth or bounded-gradient assumptions.<n>We study a more general and realistic class of generalized $ell$-smooth loss functions, where $ell$ is a general non-decreasing function of gradient norm.
  arXiv  Detail & Related papers  (2024-05-29T18:36:59Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
  We consider the problem of partitioning a small data sample of size $n$ drawn from a mixture of 2 sub-gaussian distributions in $mathbbRp$.<n>We use semidefinite programming relaxations of an integer quadratic program that is formulated as finding the maximum cut on a graph.
  arXiv  Detail & Related papers  (2024-01-16T03:14:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.