May, 2024

双仿真学习

PDF
TL;DR我们介绍了一种基于数据驱动的方法来计算具有非常大，可能是无限状态空间的状态转换系统的有限双模拟。我们的新技术计算确定性系统的阻塞不敏感的双模拟，我们将其描述为学习状态分类器与每个类的排名函数的问题。我们的方法从一个有限的样本状态数据集中学习候选状态分类器和候选排名函数；然后，它使用可满足性模理论求解检查这些是否推广到整个状态空间。如果得到肯定答案，该过程得出结论，该分类器构成了系统的有效阻塞不敏感的双模拟。如果得到否定答案，求解器会生成一个反例状态，该状态违反了该分类器的断言，将其添加到数据集中，并在反例引导的归纳合成循环中重复学习和检查，直到找到有效的双模拟。我们在反应性验证和软件模型检查的一系列基准测试中展示了我们的方法在实践中优于其他最先进的工具的更快验证结果。我们的方法产生简洁的抽象，使得能够有效地验证不包含下一个运算符的线性时态逻辑，并且对于系统诊断具有解释能力。
finite bisimulationsdata-driven approachstate transition systemsstutter-insensitive bisimulationscounterexample-guided inductive synthesis
发现论文，激发创造
  • 利用机器学习改进 MDPs 的概率双模拟

    我们提出了一种新技术，通过使用给定模型的 PRISM 程序构建一些模型的小版本并训练一个分类器，然后应用机器学习分类技术来近似相关分区，将分区结果作为标准双模拟技术的初始分区，以减少方法的运行时间。实验结果表明，该方法与最先进的工具相比，可以显著减少运行时间。

    Jul, 2023

  • 确定性马尔科夫决策过程中计算状态相似性的可扩展方法

    本文针对 MDPs 中 Bisimulation Metrics 的计算提出了新的算法，包括适用于连续状态 MDP 的可微损失函数，其中第一算法通过采样保证收敛性，第二算法通过学习实现了对大规模、确定性 MDP 的近似计算。

    Nov, 2019

  • 离线强化学习中基于双模拟的表示方法的缺陷及其解决方法

    通过分析发现，离线强化学习任务中缺失的状态转换对于等价关系原则特别有害，导致估计无效。同时，奖励缩放在界定等价度量和其引发的值误差的尺度方面起着至关重要的作用。基于这些发现，我们提出在离线强化学习环境中应用期望分为运算符进行表示学习，从而防止对不完整数据进行过拟合。与此同时，通过引入适当的奖励缩放策略，我们避免了表示空间中特征崩溃的风险。我们在两个最先进的基于等价关系的算法 MICo 和 SimSR 上实现了这些建议，并在两个基准套件 D4RL 和 Visual D4RL 上展示了性能提升。代码可在 https://github.com/zanghyu/Offline_Bisimulation 中找到。

    Oct, 2023

  • 学习不带重建的强化学习不变表示

    研究如何利用表示学习加速深度强化学习，学习能够为任务控制提供有效的潜在表示并具有与任务无关的不变性的表示方法，使用双模拟量度量在连续 MDP 状态之间的行为相似度，学习出能够仅编码来自观测的任务相关信息的健壮潜在表示，该方法通过训练编码器使潜在空间的距离等于状态空间中的双模拟距离，并在修改版的可视化 MuJoCo 任务中证明了其成功地去除任务无关信息且达到了先进技术的表现，测试了第一人称高速公路驾驶任务，其中方法学习了对云、天气和时间的不变性，最后提供了从双模拟度量的属性推导的泛化结果和与因果推断的联系。

    Jun, 2020

  • 利用不变性学习基于动作的表示

    使用动作双模拟编码，通过扩展单步可控性以递归的不变性约束，提出能捕捉长时序元素的多步可控性度量，通过在无奖励、均匀随机数据上进行预训练，提高了在多个环境中的样本效率，并展示了动作双模拟编码所捕捉到的信息。

    Mar, 2024

  • 游戏指标算法

    基于模拟和双模拟的指标可以用于系统验证和性能评估，适用于定量的 mu - 演算和相关概率逻辑，对于马尔可夫链，我们提供了一个 PSPACE 算法，以匹配最佳算法，并且这些算法可以通过二分搜索来逼近指标。

    Sep, 2008

  • 马尔可夫决策过程中计算状态相似性的方法

    本文运用网络优化和统计抽样技术，克服了计算 Kantorovich 度量在实践中的成本问题，提出了一系列用于 MDP 状态聚合的距离函数，这些函数在时间和空间复杂度以及聚合质量之间存在不同的权衡，并对这些权衡进行了实证评估。

    Jun, 2012

  • 强化学习中的观测转移泛化

    本文提出了一种基于 bisimulation 的模拟器学习方法，在考虑环境变化的情况下，使用备选观测来学习一个对观测变换不变的表示空间，以实现对测试阶段环境的适应，并在高维图像控制领域上进行实证分析。

    Jun, 2023

  • 双仿关系在目标条件强化学习中的应用

    提出了一种名为 Goal-conditioned bisimulation 的状态抽象形式来捕捉功能等变性，该方法可以让代理器在没有明确目标的情况下从先前的行为中学习新的目标，并且证明其可以适用于任何由纯状态奖励函数描述的下游任务

    Apr, 2022

  • 加权自动机的等价关系度量

    本文提出了一种基于 WFA 状态空间上的半范数的新型仿射（伪）度量，以线性算子集的谱性质为基础，研究了其连续性和应用于加权自动机谱学习的初步结果，并且发现其计算难度为不可判定问题。

    Feb, 2017