mlsanityData to 14 Oct 2026

Exact Distinguishability in Non-Markovian Decision Processes

arXiv 2610.01527 ↗First posted 1 Oct 2026cs.LG cs.AI stat.MLcited by 0

Not on the map. Why?

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.

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

16 of 39 references.

References · 16

  1. 2020Reward Machines: Exploiting Reward Function Structure in Reinforcement Learningcited by 191
  2. 2023POPGym: Benchmarking Partially Observable Reinforcement Learningcited by 62
  3. 2022Offline Reinforcement Learning with Instrumental Variables in Confounded Markov Decision Processescited by 19
  4. 2021Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learningcited by 13
  5. 2020Learning and Solving Regular Decision Processescited by 11
  6. 2022Markov Abstractions for PAC Reinforcement Learning in Non-Markov Decision Processescited by 10
  7. 2020Online Learning of Non-Markovian Reward Modelscited by 9
  8. 2024DeepDFA: Automata Learning through Neural Probabilistic Relaxationscited by 8
  9. 2022Learning Task Automata for Reinforcement Learning using Hidden Markov Modelscited by 7
  10. 2022Generalizing Off-Policy Evaluation From a Causal Perspective For Sequential Decision-Makingcited by 4
  11. 2025Pushdown Reward Machines for Reinforcement Learningcited by 4
  12. 2024Tractable Offline Learning of Regular Decision Processescited by 3
4 more
  1. 2026Why Conclusions Diverge from the Same Observations: Formalizing World-Model Non-Identifiability via an Inferencecited by 2
  2. 2013Exact test for Markov ordercited by 1
  3. 2022Automata Cascades: Expressivity and Sample Complexitycited by 1
  4. 2024Bayesian Inverse Reinforcement Learning for Non-Markovian Rewardscited by 1

Built on by

Not cited yet.