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).