Metraipolis › archive › dc_caa6286322d8
Exact Distinguishability in Non-Markovian Decision Processes — arXiv:2610.01527
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.01527
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-06T12:14:08.605Z
- SHA-256 of the archived text
8178e6954ade41f540f3dac8f32822913d8049ac03c6330112bc74d9b96cce54- Stable URL of this page
https://metraipolis.com/documento/dc_caa6286322d8
How to cite
Exact Distinguishability in Non-Markovian Decision Processes — arXiv:2610.01527 — arXiv (en), https://arxiv.org/abs/2610.01527 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_caa6286322d8 (Metraipolis archive dc_caa6286322d8, sha256 8178e6954ade41f540f3dac8f32822913d8049ac03c6330112bc74d9b96cce54)
BibTeX
@misc{dccaa6286322d8,
title = {Exact Distinguishability in Non-Markovian Decision Processes — arXiv:2610.01527},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.01527},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_caa6286322d8; sha256 8178e6954ade41f540f3dac8f32822913d8049ac03c6330112bc74d9b96cce54},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.01527. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-10-02 in cs.AI). Categorie arXiv: Machine Learning (cs.LG) ; Artificial Intelligence (cs.AI); Machine Learning (stat.ML). Pagina del lavoro: https://arxiv.org/abs/2610.01527 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-06T10:21:28.192Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-10-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).