Exact Distinguishability in Non-Markovian Decision Processes

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.

On Exact Dual and Mixed-Integer Reformulations for Finite Horizon Markov Decision Processes with Submodular Revenue Maximization
Jia-Yu Chen, Hsin-Yuan Huang, Tzu-Yang Teng +2
arXiv1 Nov 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Limit theorems for supercritical branching processes in Markovian environment with linear fractional offspring distributions
Yinna Ye, Quansheng Liu
arXiv23 Oct 2026PreprintCC BY-NC-ND 4.0Full textProbabilityarXiv
The Quantum Stochastic Limit for Non-Markovian Driving Processes
Tanner J. Reese
arXiv4 Nov 2026PreprintarXiv licenceFull textAnalysis & PDEs Mathematical physicsarXiv
Worst-Case Bayesian CVaR Regret Bounds for Episodic Markov Decision Processes
Raghav Bongole, Amirreza Zamani, Tobias J. Oechtering +1
arXiv20 Oct 2026PreprintCC BY 4.0Full textGeneral mathematicsarXiv
Dynamic Programming for Value-at-Risk Markov Decision Processes in Continuous Spaces
Xian Chen, Erick Delage, Weikai Wang
arXiv20 Oct 2026PreprintCC BY-NC-ND 4.0Full textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{murjani2026exact,
  title = {{Exact Distinguishability in Non-Markovian Decision Processes}},
  author = {Kabir Murjani and Nisarg Patel},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.01527},
  eprint = {2610.01527},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.01527},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Exact Distinguishability in Non-Markovian Decision Processes
AU  - Kabir Murjani
AU  - Nisarg Patel
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2610.01527
UR  - https://arxiv.org/abs/2610.01527
AB  - 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.
ER  -

Abstract

Related

Cite