Exact Distinguishability in Non-Markovian Decision Processes

Kabir Murjani; Nisarg Patel

cs.LGOct 1, 2026

Exact Distinguishability in Non-Markovian Decision Processes

Authors: Kabir Murjani, Nisarg Patel

Organizations: Nirma University Ahmedabad, India · Google Mountain View, CA

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.

Figures & tables

Figure 1: Cost of deciding identifiability, on log axes. (a) certifying

\pi

-equivalence against product size. (b) cost of deciding Assumption 2 of Cipollone et al. (2023) from its definition versus with Pec .

Environment	$T$	under $\pi$	under $\pi^{\prime}$	under $\pi$	under $\pi^{\prime}$	Assumption 2	Pec
		separating mass		$\mu_{0}$
T-maze	2	$\mathbf{0}$	$1/2$	$\mathbf{0}$	$1/2$	fails	equivalent
Rotating MAB	3	$\mathbf{0}$	$245/512$	$\mathbf{0}$	$1/4$	fails	equivalent
Cheat MAB	3	$\mathbf{0}$	$1/9$	$\mathbf{0}$	$1/24$	fails	equivalent
Rotating Maze	4	$\mathbf{0}$	$1/8$	–	$9/256$	holds (trivially)	equivalent

Table 1: Separating mass and the distinguishability parameter of Cipollone et al. (2023) on four environments, as exact rationals, against the verdict Pec returns on the same instance.

Environment	$\ell$	order	reversed	exhaustive
		greedy
T-maze	2	$1$	$1$	$1$
Rotating MAB	2	$1/2$	$1/4$	$3/4$
Cheat MAB	3	$\mathbf{0}$	$\mathbf{0}$	$1$
Rotating Maze	4	$\mathbf{0}$	$1$	$1$

Table 2: Separating mass achieved by each design rule, as exact rationals. The two greedy columns differ only in the order in which actions are enumerated for the tie-break, and

\ell

is the lookahead at which exhaustive design is run.

depth $d$	rand.	des.	ratio	rand.	des.	ratio
	budget 5			budget 25
2	$1.51$	$3.01$	$2.0\times$	$8.49$	$15.05$	$1.8\times$
4	$0.57$	$3.01$	$5.3\times$	$3.43$	$15.05$	$4.4\times$
6	$0.39$	$3.01$	$7.7\times$	$1.51$	$15.05$	$10.0\times$
8	$0.06$	$3.01$	$\mathbf{50.0\times}$	$0.39$	$15.05$	$\mathbf{38.5\times}$

Table 3: Mean

\log_{10}

Bayes factor over 10 seeds by corridor depth, at budgets of 5 and 25 trajectories.

Appendix figures & tables21 assets

Supplementary material from the paper’s appendix.

Appendix

Figure S1: The two hypotheses of the T-maze construction. Edges carry the action–observation pair that drives them, as in Definition 1 , with

\ast

standing for any element of the alphabet in that slot. Neither transition function consults the action, so every edge is labelled

\ast

there, and the

(\ast,\ast)

self-loops on

q_{\mathrm{L}}

q_{\mathrm{R}}

and

q_{\mathrm{b}}

are the ones the always-

\mathrm{wait}

policy traverses.

Panel of Figure 6 — Figure S2: Effect of description specificity and of misspecification on the posterior. Panel (a) plots all three sentences against the no-sentence baseline. Panel (b) plots the partial sentence “remembers, commits” alone, named on the axes, since the vague sentence is worth $1.3\times$ at its peak and the saturated one is a specification.

Panel of Figure 7 — Figure S3: Seed variation, prior sensitivity, and the small-data crossover.

Formalism	History-dependence in	Notes
Reward machines	reward only	dynamics stay Markov; mature literature
Regular Decision Processes	dynamics and reward	more general; less studied
MDP (incl. $L^{*}_{\mathrm{MDP}}$ setting)	none, state is Markov	structure learning $\neq$ non-Markovian dynamics
POMDP	latent state	more general, much less tractable
PSR / spectral	predictive state	learning-theoretic, different toolchain

Appendix

Table S1: Location of history-dependence across non-Markovian formalisms. MDP: Markov decision process; POMDP: partially observable MDP; PSR: predictive state representation.

requested depth	1	2	3	4	5	6	8
rooms	1	2	3	4	5	6	8
$\pi$ -equivalent	yes	yes	yes	yes	yes	yes	yes
horizon under $\pi$	$\bot$	$\bot$	$\bot$	$\bot$	$\bot$	$\bot$	$\bot$
horizon under deviation	1	2	3	4	5	6	8

Appendix

Table S2: Corridor depth against the measured separating horizon. A horizon of

\bot

means that Pec found no reachable disagreeing pair, so no finite horizon separates the two models and the entry is a certificate of

\pi

-equivalence.

depth $d$	$\ell=1$	$\ell=2$	$\ell=3$	$\ell=4$	$\ell=5$	$\ell=6$
$1$	$1$	$1$	–	–	–	–
$2$	$0$	$1$	$1$	–	–	–
$3$	$0$	$0$	$1$	$1$	–	–
$4$	$0$	$0$	$0$	$1$	$1$	–
$5$	$0$	$0$	$0$	$0$	$1$	$1$

Appendix

Table S3: Separating mass achieved by exhaustive design at lookahead

\ell

Environment	corpus	$\log_{10}$ BF	coverage	LL/step ∗
T-maze	under $\pi$	$\mathbf{0.00\pm 0.00}$	$16.2\pm 3.2$ %	$-0.6932\pm 0.0014$
	random	$300.91\pm 9.03$	$99.9\pm 0.3$ %	$-0.4303\pm 0.0449$
	designed	$300.91\pm 9.03$	$99.9\pm 0.3$ %	$-0.4303\pm 0.0449$
Rotating MAB	under $\pi$	$\mathbf{0.00\pm 0.00}$	$8.4\pm 1.7$ %	$-0.6932\pm 0.0008$
	random	$161.93\pm 20.04$	$100.0\pm 0.0$ %	$-0.6798\pm 0.0082$
	designed	$148.86\pm 17.89$	$29.5\pm 3.3$ %	$-0.6851\pm 0.0070$

Appendix

Table S4: One learner at a fixed budget on three corpora, as mean

\pm

half-range over ten seeds. BF is the Bayes factor and LL the log-likelihood. The zeros under

\pi

are exact rational zeros, so their spread is exactly zero by Theorem 6 .

Environment	States	Non-Markovian structure	$\log_{10}$ BF
T-maze	3	remember the initial cue	$35.06$
Rotating MAB	2	reward probabilities rotate on every reward	$8.03$
Cheat MAB	3	an action sequence unlocks max reward	$7.81$
Rotating Maze	6	orientation rotates every 3 moves	$9.84$

Appendix

Table S5: Log Bayes factor of the true automaton against a memoryless null.

Panel of Figure 13 — Figure S4: Rejection of memorylessness and structure recovery on the Tomita grammars.

Environment	Rows visited	Mean abs. err	Max abs. err	Min samples/row
T-maze	6/6	$0.031$	$0.060$	17
Rotating MAB	6/6	$0.030$	$0.067$	41
Cheat MAB	9/9	$0.051$	$0.167$	20
Rotating Maze	12/12	$0.077$	$0.365$	7

Appendix

Table S6: Posterior-mean emission probabilities against the truth.

Panel of Figure 15 — Figure S5: Scaling of evidence and emission error, averaged over five seeds.

Environment	$\log_{10}$ BF mean $\pm$ sd	min $\log_{10}$ BF over seeds	emission MAE mean $\pm$ sd
T-maze	$37.36\pm 2.07$	$34.82$	$0.044\pm 0.015$
Rotating MAB	$10.78\pm 3.09$	$6.27$	$0.045\pm 0.018$
Cheat MAB	$11.12\pm 3.29$	$6.37$	$0.051\pm 0.016$
Rotating Maze	$10.41\pm 1.99$	$8.47$	$0.065\pm 0.014$

Appendix

Table S7: Variation of the main quantities over 12 seeds. BF: Bayes factor; MAE: mean absolute error; sd: standard deviation.

Environment	Separating evidence is…	Reachability
T-maze, Rotating MAB	an action taken in an already-visited state	blind (score constant)
Cheat MAB, Rotating Maze	a state the policy never reaches	informative

Appendix

Table S8: Form of the separating evidence in each environment.

Environment	Behaviour policy $\pi$	Action taken w.p. $p$	Remaining mass
T-maze	always $\mathrm{wait}$	$\mathrm{run}$	$\mathrm{wait}$ , w.p. $1-p$
Rotating MAB	always $\mathrm{arm0}$	$\mathrm{arm1}$	$\mathrm{arm0}$ , w.p. $1-p$
Cheat MAB	never $\mathrm{arm2}$	$\mathrm{arm2}$	$\mathrm{arm0},\mathrm{arm1}$ , w.p. $(1-p)/2$ each
Rotating Maze	always $\mathrm{stay}$	$\mathrm{move}$	$\mathrm{stay}$ , w.p. $1-p$

Appendix

Table S9: The deviation

\pi^{\prime}_{p}

in each environment. At

p=0

the deviation is the behaviour policy, and

p

is the probability of the named action at every step.

$p$	$0$	$1/8$	$1/4$	$3/8$	$1/2$	$5/8$	$3/4$	$7/8$	$1$
separating mass	$\mathbf{0}$	$7/128$	$3/32$	$15/128$	$\mathbf{1/8}$	$15/128$	$3/32$	$7/128$	$\mathbf{0}$

Appendix

Table S10: Separating mass on Cheat MAB against deviation strength

p

Panel of Figure 20 — Figure S6: Deviation strength swept from the behaviour policy to its opposite.

depth $d$	$\gamma$	$\eta$	window	$\tau=0$	$\tau$ in window
$2$	$1/2$	$0.072$	$(0.144,\,0.356)$	never certifies	all correct
$4$	$1/2$	$0.083$	$(0.167,\,0.333)$	never certifies	all correct
$6$	$1/2$	$0.098$	$(0.195,\,0.305)$	never certifies	all correct
$8$	$1/2$	$0.095$	$(0.190,\,0.310)$	never certifies	all correct

Appendix

Table S11: Pec on estimated emission tables, corridor family, 600 trajectories per candidate under a covering policy, five seeds.

\eta

is measured over the rows the procedure consults.

depth $d$	random walk	state prefix	designed	prefix / walk
$2$	$1/4$	$3/8$	$1$	$1.5\times$
$4$	$1/16$	$15/64$	$1$	$3.8\times$
$6$	$1/64$	$21/128$	$1$	$10.5\times$
$8$	$1/256$	$255/2048$	$1$	$\mathbf{31.9\times}$

Appendix

Table S12: Separating mass of each exploration strategy on the corridor family, as exact rationals.

	random walk	state prefix	designed
separating mass	$1/2$	$1/2$	$1$

Appendix

Table S13: The same strategies on the T-maze, where every automaton state is visited on the first step whatever the agent does.

depth $d$	$\mu_{0}$ under $\pi^{\prime}$	ratio to $d-1$	definition (s)	Pec (s)	speedup
$2$	$1/4$	–	$0.0005$	$0.00014$	$3.7\times$
$3$	$1/16$	$0.250$	$0.0024$	$0.00054$	$4.4\times$
$4$	$1/64$	$0.250$	$0.0100$	$0.00143$	$7.0\times$
$5$	$1/256$	$0.250$	$0.0408$	$0.00314$	$13.0\times$
$6$	$1/1024$	$0.250$	$0.1616$	$0.00567$	$28.5\times$
$7$	$1/4096$	$0.250$	$0.6536$	$0.00969$	$\mathbf{67.5\times}$

Appendix

Table S14: The corridor family:

\mu_{0}

under the deviation, and the cost of deciding Assumption 2 from the definition versus with Pec . Under

\pi

the assumption holds trivially at every depth while Pec certifies

\pi

-equivalence at every depth.

$\|Q\|$	$\|Q^{\prime}\|$	product	pairs explored	seconds	µs / pair
$10$	$11$	$110$	$110$	$0.0005$	$4.50$
$50$	$51$	$2{,}550$	$2{,}550$	$0.0111$	$4.36$
$100$	$101$	$10{,}100$	$10{,}100$	$0.0438$	$4.34$
$200$	$201$	$40{,}200$	$40{,}200$	$0.1777$	$4.42$
$500$	$501$	$250{,}500$	$250{,}500$	$1.1263$	$4.50$
$700$	$701$	$490{,}700$	$490{,}700$	$2.2282$	$4.54$

Appendix

Table S15: Pec certifying

\pi

-equivalence. Every pair of the product is reachable, so the procedure explores all of it before answering.

Explore similar work

Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions
Aug 6, 2026Yuepeng Yang, Yuxin Chen, Yuejie ChiMarkov Decision Processes Optimal Policies
*Department of Statistics and Data Science, Yale University. · †Department of Statistics and Data Science, the Wharton School, University of Pennsylvania.
Sample-Efficient Learning of Probabilistic Causes for Reachability in Markov Decision Processes with Probabilistic Guarantees
Jun 29, 2026Ryohei Oura, Georgios Fainekos, Hideki Okamoto +1Markov Decision Processes Reachability
Toyota Research Institute of North America, Toyota Motor North America · Frontier Research Center, Toyota Motor Corporation
Optimal Posterior Sampling for Policy Identification in Tabular Markov Decision Processes
May 5, 2026Cyrille Kone, Kevin JamiesonOptimal Policies Markov Decision Processes
Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189-CRIStAL, F-59000 Lille, France · University of Washington, Seattle, USA

Aug 6, 2026, cs.LGJ/K move · Enter open · S save

Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

Yuepeng Yang, Yuxin Chen, Yuejie Chi

*Department of Statistics and Data Science, Yale University. · †Department of Statistics and Data Science, the Wharton School, University of Pennsylvania.

Markov Decision Processes Optimal Policies Optimal Learner Sample Complexity Decisions

Open paper AskPDF arXiv

Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty. We study how many samples are necessary and sufficient to learn an

\varepsilon

-optimal robust policy under the average-reward criterion. A generative model provides samples from the nominal transition kernel, whereas policy performance is evaluated over

(s,a)

-rectangular total-variation uncertainty sets of radius at most

σ

. Let

H_0

and

H_σ

denote the nominal and robust optimal bias spans, respectively. We identify

σH_0

as the perturbation scale separating high- and low-tolerance regimes. Our matching upper and lower bounds show that, up to logarithmic factors, the minimax total sample complexity is

NSA \asymp \frac{SA}{\varepsilon^2}\begin{cases} \min\{H_0,H_σ\}, & \varepsilon\gtrsimσH_0,\\ \min\{H_0,H_σ\}+σH_σ^2, & \varepsilon\lesssimσH_0. \end{cases}

Here

S

and

A

are the numbers of states and actions, and

N

is the number of samples per state-action pair. The sample complexity consists of a linear-span term that resembles the nominal AMDP results and a robustness-specific term that appears only in the low-tolerance regime. We attain these rates using reduction-based plug-in procedures that select the reduction---nominal or robust---and its discount factor: a span-informed procedure that makes these choices using known span parameters, and a span-agnostic procedure that calibrates both choices from data.

depth $d$	$\ell=1$	$\ell=2$	$\ell=3$	$\ell=4$	$\ell=5$	$\ell=6$
$1$	$1$	$1$	–	–	–	–
$2$	$0$	$1$	$1$	–	–	–
$3$	$0$	$0$	$1$	$1$	–	–
$4$	$0$	$0$	$0$	$1$	$1$	–
$5$	$0$	$0$	$0$	$0$	$1$	$1$

depth $d$	$\ell=1$	$\ell=2$	$\ell=3$	$\ell=4$	$\ell=5$	$\ell=6$
$1$	$1$	$1$	–	–	–	–
$2$	$0$	$1$	$1$	–	–	–
$3$	$0$	$0$	$1$	$1$	–	–
$4$	$0$	$0$	$0$	$1$	$1$	–
$5$	$0$	$0$	$0$	$0$	$1$	$1$

Abstract

Explore similar work

Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

Sample-Efficient Learning of Probabilistic Causes for Reachability in Markov Decision Processes with Probabilistic Guarantees

Optimal Posterior Sampling for Policy Identification in Tabular Markov Decision Processes

depth $d$	$\ell=1$	$\ell=2$	$\ell=3$	$\ell=4$	$\ell=5$	$\ell=6$
$1$	$1$	$1$	–	–	–	–
$2$	$0$	$1$	$1$	–	–	–
$3$	$0$	$0$	$1$	$1$	–	–
$4$	$0$	$0$	$0$	$1$	$1$	–
$5$	$0$	$0$	$0$	$0$	$1$	$1$