arXiv:2512.17265cs.LG2025-12

提出跨MDP状态相似性度量GBSM,可严格量化不同环境间状态相似性。

A Theoretical Analysis of State Similarity Between Markov Decision Processes

  • 定义广义双模拟度量GBSM,具备对称性、三角不等式等数学性质
  • 在策略迁移、状态聚合等任务中给出比传统方法更紧的理论边界
  • 提供闭式样本复杂度公式,适用于多环境强化学习场景

双模拟度量(BSM)是分析马尔可夫决策过程(MDP)内状态相似性的有力工具,揭示了在BSM距离较近的状态具有更相似的最优值函数。尽管已在强化学习中用于状态表征学习与策略探索,但其在多个MDP之间的状态相似性分析仍具挑战。以往工作尝试将BSM扩展至多MDP对,但缺乏明确的数学性质限制了进一步理论分析。本文正式建立了广义双模拟度量(GBSM),用于衡量任意一对MDP间的状态相似性,并严格证明其具备三个基本度量性质:对称性、跨MDP三角不等式及相同空间下的距离有界性。基于这些性质,我们理论上分析了跨MDP的策略迁移、状态聚合与采样估计,获得了比传统基于标准BSM更紧的显式误差上界。此外,GBSM提供了闭式样本复杂度表达式,优于现有基于BSM的渐近结果。数值实验验证了理论结论,并展示了GBSM在多MDP场景中的有效性。

原文摘要 · Abstract (English)

The bisimulation metric (BSM) is a powerful tool for analyzing state similarities within a Markov decision process (MDP), revealing that states closer in BSM have more similar optimal value functions. While BSM has been successfully utilized in reinforcement learning (RL) for tasks like state representation learning and policy exploration, its application to state similarity between multiple MDPs remains challenging. Prior work has attempted to extend BSM to pairs of MDPs, but a lack of well-established mathematical properties has limited further theoretical analysis between MDPs. In this work, we formally establish a generalized bisimulation metric (GBSM) for measuring state similarity between arbitrary pairs of MDPs, which is rigorously proven with three fundamental metric properties, i.e., GBSM symmetry, inter-MDP triangle inequality, and a distance bound on identical spaces. Leveraging these properties, we theoretically analyze policy transfer, state aggregation, and sampling-based estimation across MDPs, obtaining explicit bounds that are strictly tighter than existing ones derived from the standard BSM. Additionally, GBSM provides a closed-form sample complexity for estimation, improving upon existing asymptotic results based on BSM. Numerical results validate our theoretical findings and demonstrate the effectiveness of GBSM in multi-MDP scenarios.

强化学习状态相似性理论分析多环境迁移

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。