arXiv cs.AI· S Akshay, Suguman Bansal, Gaurav Mahla·· 3 天前AI 评分19
如何在未知 MDP 中验证几乎必然可达性：基于采样的 RSM 证书学习
Certifying Almost-Sure Reachability in Unknown MDPs
AI 导读
针对未知 MDP 中策略是否满足几乎必然可达性，研究证明在无额外信息时既无法学习也无法验证 RSM 证书；但在已知非零转移概率下界 p_min 的温和限制下，可借助采样以 PAC 式保证学习到正确证书。实验显示该 p_min 充分条件虽可靠但偏保守，条件失效时学到的证书在真实 MDP 上往往仍有效。
正文 · AI 翻译
摘要：{\em 规范引导强化学习（RL）}主要关注在未知{\em 马尔可夫决策过程（MDP）}中针对形式化规范\emph{学习}最优策略。我们研究其对偶问题。给定一个已有的策略，能否仅通过采样访问，在未知 MDP 中\emph{验证}其相对于形式化规范的正确性？这一问题在安全关键系统中自然出现。我们针对{\em 几乎必然可达性性质}展开研究，其正确性由{\em 秩超鞅（RSM）}证书见证。我们的第一个发现是负面的。在没有任何关于 MDP 的进一步信息的情况下，既无法学习这样的证书，也无法以概率保证验证候选证书。在积极的一面，我们表明，在一个温和的限制下，即已知非零转移概率的下界 $p_{\min}$，正确的证书\emph{可以}以 PAC 风格的保证被学习。据我们所知，这是首个仅从采样访问中学习并验证未知 MDP 中几乎必然可达性证书的研究。最后，我们的实验表明，基于 $p_{\min}$ 的充分条件虽然可靠，但偏保守：即使该条件不成立，学习到的证书在真实 MDP 上往往仍然有效。
| 主题： | 计算机科学中的逻辑（cs.LO）；人工智能（cs.AI） |
| 引用为： | arXiv:2610.18119 [cs.LO] |
| （或 arXiv:2610.18119v1 [cs.LO] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2610.18119 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Suguman Bansal [查看电子邮件]
[v1]
2026年10月13日星期二 10:33:58 UTC（43 KB）
来源：arXiv cs.AI · arxiv.org