arXiv：cs.LG（机器学习，全量分类）· Kabir Murjani, Nisarg Patel·· 14 小时前AI 评分34
非马尔可夫决策过程中的精确可区分性研究
Exact Distinguishability in Non-Markovian Decision Processes
AI 导读
研究证明，在固定行为策略下收集的数据中，两个观测等价的 RDP 候选模型的后验几率在任何样本量下都等于先验几率，即使策略访问了每个自动机状态，并在 Lean 4 中形式化验证。团队精确刻画了这种等价关系，提出 PEC 算法可在乘积自动机规模线性时间内判定等价性。在先前的可区分性假设失效的三个测试环境中，PEC 识别出的实验均恢复了该假设。
正文
Abstract:Non-Markovian environments are often modeled as Regular Decision Processes (RDPs), where dynamics depend on the interaction history through a finite automaton. Existing offline guarantees for RDPs rely on a distinguishability assumption on the behaviour policy but provide no means of verifying it. When the assumption is violated, distinct models may explain the data equally well. We study when data collected under a fixed behaviour policy can distinguish two candidate RDPs. We prove that the posterior odds between observationally equivalent candidates remain equal to the prior odds at every sample size, even when the policy visits every automaton state, and verify both results formally in Lean 4. We then characterize this equivalence exactly and derive PEC, an algorithm that decides it in time linear in the size of the product automaton. The distinguishability assumption of prior work fails on three of our four test environments, and the experiment identified by PEC restores it in each case.
| Comments: | 26 pages, 7 figures. Code and Lean 4 proofs: this https URL |
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Machine Learning (stat.ML) |
| Cite as: | arXiv:2610.01527 [cs.LG] |
| (or arXiv:2610.01527v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.01527 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Kabir Murjani [view email]
[v1]
Thu, 1 Oct 2026 12:04:44 UTC (210 KB)
来源：arXiv：cs.LG（机器学习，全量分类） · arxiv.org