用近似最近邻加速马尔可夫决策过程的相似性度量计算，兼顾精度与效率。
Sub-Quadratic Bisimulation Metrics via Approximate Nearest Neighbors: Coverage-Augmented Guarantees and Computable Two-Sided Certificates
- 基于近似最近邻索引选择需更新的状态对，实现亚二次计算复杂度。
- 通过上下界夹逼保证结果精度，覆盖率达一半时即可逼近最优解。
- 适合大规模MDP场景，尤其适用于状态空间大但转移支持有限的问题。
双模拟度量用于量化马尔可夫决策过程中的行为相似性，但其Wasserstein不动点更新需处理每对状态，计算复杂度为二次型。本文提出一种携带验证证书的亚二次方法，适用于转移支持有界的MDP及低维索引表示：近似最近邻索引筛选出由精确受限算子更新的状态对，单调的上下界迭代可全程包络真实度量。主要分析结果为覆盖率增强的任意时间界：局部索引质量无法单独控制全局误差，因未覆盖对仍保持初始差距。极限误差不超过 $\max(ρ, \eop/(1-γ))$，且在完全覆盖更新下，下界满足 $\|\dann-d\|_\infty=ρ$。由于 $ρ$ 依赖于未知真实度量，算法返回可观测的夹层宽度；上下界聚类一致则表明已精确恢复覆盖聚合。奖励无关下界表明，仅靠亚二次索引首选无法消除覆盖率项；独立自适应下界要求至少 $Ω(|\Scal|)$ 对状态评估。精确算子实验验证每轮初始化下恒等与包络关系，时序实验确认在廉价与完整Wasserstein备份下均实现二次与亚二次缩放。在 $|\Scal|=64$ 分组基准上，精确受限细化在检索覆盖约一半状态对时达到真实度量最优，而独立训练的MICo与DBC基线始终高出最优值 $22$-$33\times$。Taxi任务显示嵌入无信息时证书会主动放弃，而在 $2500$ 状态网格世界中，使用 $12.8\%$ 的一次二次扫描开销，相比仅基于奖励的度量提升 $28.6\%$。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。