Distinguishing decision models in non-Markovian environments exactly and efficiently
Exact Distinguishability in Non-Markovian Decision Processes
Machine LearningArtificial Intelligence
Summary
This paper studies how to tell apart two possible decision-making models that depend on past actions rather than just the current state. The authors found that sometimes no amount of data can help tell these models apart, even under policies that explore all states. They mathematically prove this and create an efficient algorithm to check when two models can be distinguished using the collected data. Their tests show that widely used assumptions about being able to distinguish models do not hold in many cases, but their algorithm can identify how to fix this.
What this means in practice
- •For reinforcement learning engineers: Verify whether collected data can uniquely identify environment models to improve offline policy evaluation reliability.
- •For software verification teams: Use the PEC algorithm to check model equivalence in systems modeled by automata to avoid ambiguous interpretations of behavior.
Tested on simulated data.
Authors
Kabir Murjani, Nisarg Patel
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.