# Exact Distinguishability in Non-Markovian Decision Processes

arXiv: https://arxiv.org/abs/2610.01527 · HTML: https://mlsanity.com/paper/2610.01527/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 39 references that are in the map.
- First posted on arXiv 1 Oct 2026.

## Builds on (most cited first, 16 of 16)

- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [POPGym: Benchmarking Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2303.01859/) (2023)
- [Offline Reinforcement Learning with Instrumental Variables in Confounded Markov Decision Processes](https://mlsanity.com/paper/2209.08666/) (2022)
- [Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learning](https://mlsanity.com/paper/2107.04633/) (2021)
- [Learning and Solving Regular Decision Processes](https://mlsanity.com/paper/2003.01008/) (2020)
- [Markov Abstractions for PAC Reinforcement Learning in Non-Markov Decision Processes](https://mlsanity.com/paper/2205.01053/) (2022)
- [Online Learning of Non-Markovian Reward Models](https://mlsanity.com/paper/2009.12600/) (2020)
- [DeepDFA: Automata Learning through Neural Probabilistic Relaxations](https://mlsanity.com/paper/2408.08622/) (2024)
- [Learning Task Automata for Reinforcement Learning using Hidden Markov Models](https://mlsanity.com/paper/2208.11838/) (2022)
- [Generalizing Off-Policy Evaluation From a Causal Perspective For Sequential Decision-Making](https://mlsanity.com/paper/2201.08262/) (2022)
- [Pushdown Reward Machines for Reinforcement Learning](https://mlsanity.com/paper/2508.06894/) (2025)
- [Tractable Offline Learning of Regular Decision Processes](https://mlsanity.com/paper/2409.02747/) (2024)
- [Why Conclusions Diverge from the Same Observations: Formalizing World-Model Non-Identifiability via an Inference](https://mlsanity.com/paper/2605.12255/) (2026)
- [Exact test for Markov order](https://mlsanity.com/paper/1302.1500/) (2013)
- [Automata Cascades: Expressivity and Sample Complexity](https://mlsanity.com/paper/2211.14028/) (2022)
- [Bayesian Inverse Reinforcement Learning for Non-Markovian Rewards](https://mlsanity.com/paper/2406.13991/) (2024)

## Abstract (arXiv)

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.