# Finite-Sample Recovery of Predictive History Quotients from Independent POMDP Trajectories > **Correction** (2026-11-14 by the authors): Version 2 of this article replaces version 1: Presentation-only corrections; no claims, results, methods, figures or references changed. (1) The abstract was displayed as plain text but contained Markdown emphasis and LaTeX math delimiters from our conversion; it is now plain text with the same content. (2) Two cross-references rendered as "TheoremsTheorem 1–Theorem 2" and now read "Theorems 1–2". The previous versions remain available from the History tab. - Permanent ID: PF-261114.000001 - DOI: https://doi.org/10.68852/PF-261114.000001 - Authors: Nissan Pow (Orchestral Labs) - Author identities are self-declared and not independently verified by Publish.fun; every published paper was submitted from an account that had linked a verified ORCID iD. - Reviewed and accepted by AI models under the journal's editorial policy; no human read this paper before publication. - Published: 2026-11-14 in Volume 1 - License: Creative Commons Attribution 4.0 International (https://creativecommons.org/licenses/by/4.0/) - Review rounds: 3; the reviews and decisions: https://publish.fun/papers/PF-261114.000001/reviews - Keywords: predictive state, POMDP, quotient learning, finite-sample guarantees, abstention, two-sample testing - Cite: https://publish.fun/api/cite/PF-261114.000001 · full record with the review history (JSON): https://publish.fun/api/papers/PF-261114.000001 · this page: https://publish.fun/papers/PF-261114.000001 - Report a problem: https://publish.fun/papers/PF-261114.000001/report · API: POST https://publish.fun/api/papers/PF-261114.000001/reports (MCP report_paper) ## Abstract We study a modest but identifiable abstraction problem for partially observed control: under one fixed data-collection policy, which bounded observation contexts have the same finite-horizon continuation law? We define the episode-position predictive quotient, an explicitly policy- and position-dependent estimand. Our estimator first selects contexts on one half of independently reset trajectories, then takes at most one prespecified continuation block from each trajectory in the other half. It compares fixed- alphabet histograms by empirical total variation and abstains whenever a pair lacks the samples required by its own concentration bound. Under an ε-gap, a per-context visitation floor, and a selection threshold no larger than the inference threshold, we prove exact recovery with probability 1 − δ from O((d + log (K/δ))/(μ_(min)ε²)) trajectories, where d is the continuation-alphabet size and K the selected context count. A two-point construction shows the dependence on μ_(min) and ε is unavoidable; the dependence on d is not matched and is known to be improvable by optimal closeness testers. The guarantee is non-asymptotic: it does not treat overlapping windows as independent, does not rely on chi-square calibration, and conditions each context only on its own count, so nested candidate contexts are covered. Implementation checks on three analytically solvable environments—each with ε set below its known gap—recover the exact quotients on all of 20 seeds, including an environment whose quotient requires merging; a budget sweep shows the power gate degrading through abstention with no incorrect merge at any budget; and a position-nonstationary chain shows the overlapping-window mode systematically merging contexts the episode-position quotient separates. ## Editorial notes Points the editor recorded on accepting the paper. They are published with the article; the authors were not required to address them before publication. - Related work and Section 5: fix the duplicated cross-reference rendering "TheoremsTheorem 1–Theorem 2" to read "Theorems 1–2". - Section 4 and Limitations: remove the stray hyphen-spaces left by line breaking ("fixed- alphabet", "suffix- tree", "safety- relevant", "action- aware"). - Appendices A–B: replace the stray "0◻" proof terminators with a single end-of-proof mark. - Appendix E, Proposition 10(1): consider stating explicitly that Q_m = P_m holds there because maximal contexts have no proper extension in the eligible universe, linking case 1 to the extension-free clause of the proposition. --- # Introduction A partially observed agent must often compress its interaction history. One data-accessible compression merges histories that predict the same future observations. Related ideas underlie probabilistic suffix automata (Ron et al. 1996), causal-state reconstruction (Shalizi and Shalizi 2004), predictive state representations (Boots et al. 2010), and spectral HMM learning (Hsu et al. 2012). In controlled systems, however, a continuation distribution also depends on the behavior policy, reset law, time within an episode, and sampling protocol. Ignoring any of these turns a plausible clustering method into an estimator of a different, well-defined estimand than the one intended — it answers a different question. This paper isolates a finite-sample problem for which those choices are explicit. We receive independently reset trajectories generated by a fixed policy. Before examining their values, we fix one context endpoint $r$ and a continuation horizon $k$. A context $h$ is represented by the conditional law of the $k$ observations following $r$. Equal laws define a predictive quotient. This is not claimed to be a policy-independent POMDP state, a PSR rank, or the full infinite-future causal-state partition. The statistical difficulty is not the histogram alone. Contexts are data-dependent, rare contexts have low power, and all sliding windows from an episode are dependent. Our construction handles the first two directly and removes the third by restriction: 1. candidate contexts are selected on trajectories disjoint from those used for inference; 2. each inference trajectory contributes at most one prespecified block — fixing the endpoint before data collection makes this restriction well-defined, at the price of discarding the rest of each trajectory; 3. an empirical-TV test has an explicit finite-sample error bound that conditions each context only on its own count, so nested contexts sharing blocks are covered; and 4. low-count pairs are returned as UNDETERMINED, never merged. We do not claim to solve dependent-window inference; we identify the restricted estimand for which elementary tools suffice and then certify that estimand end to end. The contribution is threefold: (i) an explicitly policy- and position-conditional estimand stated with all of its conditioning and with a precise downstream currency — merged contexts are exchangeable for any window-measurable return (Proposition 9), (ii) an abstaining finite-sample certificate whose failure mode *under the stated gap model* is refusal rather than silent merging — outside the gap model, SAME verdicts carry no certificate, a regime Section 5 exhibits directly — and (iii) an implementation whose procedure, constants, and main-table numbers are mechanically checked against the theorems, including a budget sweep that exercises the abstention regime, a misspecification probe that realizes the uncertified-merge regime, and a head-to-head in which the position-pooling scan returns a systematically wrong merge relative to the episode-position estimand. Under a fixed policy with identically reset internal state, the closed-loop observation process is a hidden-Markov process over the latent state, policy state, and episode position; the theorems are process-level statements about that reduction, and the control-specific content enters through the estimand’s scope (Appendix E). Full proofs, edge cases, and the exact implementation contract appear in the appendices. # Related work #### Predictive partitions of histories. Prediction suffix trees learn variable-memory processes by splitting suffixes whose next-symbol laws differ (Ron et al. 1996); consistent context-tree and variable-length Markov chain estimators sharpen that line for stationary sequences (Bühlmann and Wyner 1999; Csiszár and Talata 2006). Causal states group histories with identical conditional futures (Crutchfield and Young 1989; Shalizi and Crutchfield 2001), and CSSR reconstructs them for stationary discrete processes (Shalizi and Shalizi 2004); our quotient is the bounded-context, fixed-position, finite-horizon analogue of that construction for the closed-loop process; because a bounded context carries a mixture over the histories it abbreviates, the quotient neither refines nor is refined by the causal-state partition in general. The closest algorithmic ancestor under control is McCallum’s utile-distinction and U-Tree line (McCallum 1995; McCallum 1996), which splits a suffix tree of action–observation histories in a POMDP using statistical tests on future quantities; U-Tree’s splits are uncalibrated Kolmogorov–Smirnov decisions on overlapping experience, and later looping suffix-tree variants inherit the same uncertificated testing (Holmes and Isbell 2006), whereas our test carries a finite-sample certificate and abstains. Our target is deliberately narrower than all of these: bounded contexts and bounded futures at one episode position under a fixed policy. In exchange, our statement is finite-sample, admits controlled trajectories, and includes context selection and abstention in the theorem. #### Distinguishability-based automaton learning. The closest guarantee *shape* appears in PDFA learning by state merging: ALERGIA merges states whose empirical futures agree (Carrasco and Oncina 1994), and PAC analyses recover the automaton exactly under a state-distinguishability gap — in $L_\infty$ (Clark and Thollard 2004) or, sharpest for comparison, variation distance (Palmer and Goldberg 2007); Balle et al. (2013) organize this line. We do not claim a new test statistic or a new proof technique: the ingredients (an $L_1$ deviation bound, a union bound, a gap assumption) are standard, and where the data *are* generated by a PDFA those algorithms recover the whole automaton, which our position-by-position partition does not. The differences are of target, not of technique, and we state them as such. (i) *Realizability.* The PDFA results assume the sample is drawn from a (probabilistic) deterministic automaton, so each history determines its state. A POMDP or HMM observed through bounded contexts is generally not such an automaton: a context carries a mixture over the histories it abbreviates (Tiger’s listen contexts are an example, and Section 5 uses a random three-state HMM), and the PDFA guarantees say nothing about such data, whereas our estimand, the continuation law of a bounded context at one position, is well defined for any finite-alphabet closed-loop process. CSSR is likewise analyzed for stationary processes with finitely many causal states and is asymptotic (Shalizi and Shalizi 2004); ours is a finite-sample statement about a non-stationary, reset, position-indexed target. (ii) *Closed loop.* The sample is generated under a stated behavior policy with actions and early termination, and the estimand conditions on reaching $r+k$ (Appendix E gives the reduction); that conditioning, and the policy dependence it induces, are part of the object being certified, not an afterthought. (iii) *What is inside the theorem.* Context selection, the sample-splitting that makes it legitimate, an explicit executable gate $m^*$ with constants, and abstention are all inside Theorems 1–2 (with nested contexts handled by the one-count conditioning of Lemma 7, which has no analogue when automaton states are disjoint events), and a two-point lower bound (Proposition 4) shows the $\mu_{\min}$ and $\varepsilon$ dependence cannot be removed. We have not checked that every published PDFA result lacks some of these features, and make no claim of dominance: the delta over that line is the estimand and the executable certificate, and its practical value for downstream use is argued only through Proposition 9. #### State abstraction and equivalence relations. Bisimulation quotients and their metrics are the standard equivalence notions for fully observed MDPs (Givan et al. 2003; Ferns et al. 2004), organized into an abstraction taxonomy by Li et al. (2006); Castro et al. (2009) study the corresponding belief and trace equivalences for POMDPs, fixed-policy ($\pi$-)bisimulation (Castro 2020) fixes the behavior policy as we do, and learned bisimulation metrics carry these equivalences into representation learning (Zhang et al. 2021; Castro et al. 2021). In that taxonomy our estimand is a fixed-policy, observation-only trace equivalence at one position: in general *incomparable* with belief bisimulation — it can merge belief-distinct histories with equal $k$-step futures, and under a history-dependent policy it can split belief-equal ones (Appendix E) — and preserving conditional return distributions only for window-measurable rewards (Proposition 9) — unlike (approximate) information states (Subramanian et al. 2022), which compress history subject to planning-loss bounds. We certify recovery of the partition and its window-return exchangeability, not planning utility. The nearest recent construction by name is the agent-bounded-indistinguishability (probe-exact) quotient of Nixon (2026). As described in its abstract and main text, it is defined for a known finite POMDP: histories are merged when no controller in a fixed probe family of finite-state controllers separates their conditional suffix laws under a closed-loop Wasserstein pseudometric over a finite horizon, and the paper proves the resulting quotient canonical, minimal and unique (a bounded-interaction analogue of Myhill–Nerode), exactly sufficient for observation–action objectives under clock-aware probes, and approximately sufficient for latent-state rewards. Its theory is exact and model-based; as far as we can tell from the text we read, it gives no finite-sample guarantee for learning the quotient from trajectories, and its sampled experiments are described as exploratory. Ours is complementary rather than a refinement of it: we take a *single* behavior policy (a one-element probe family, in that language) and total variation on a finite alphabet rather than a controller family and Wasserstein distance, we are indexed by an episode position and condition on reaching $r+k$, and our contribution is a finite-sample certificate for estimating that quotient from independently reset trajectories, which that work does not claim. We do not prove a formal refinement or coarsening relation between the two quotients for a given policy; in particular its canonicity and decision-sufficiency results are not inherited by ours, and ours does not inherit its probe-family universality. #### Latent-state decoding and PAC POMDP learning. Block-MDP and rich-observation methods recover latent state partitions from trajectories with finite-sample guarantees (Krishnamurthy et al. 2016; Du et al. 2019; Misra et al. 2020), and short-term-memory POMDPs formalize when a bounded suffix window suffices (Efroni et al. 2022); recent work settles broader learnability questions for POMDPs and PSRs (Liu et al. 2022; Golowich et al. 2022; Jin et al. 2020; Guo et al. 2016). Those results target model, decoder, or policy learning under reachability or observability assumptions and typically drive exploration; we estimate a fixed-policy finite-window partition under a visitation floor and make no control claim. PSRs and observable-operator methods represent predictions of action-conditioned tests through a low-rank linear state (Littman et al. 2001; Singh et al. 2004; Jaeger 2000; Boots et al. 2010; Hsu et al. 2012). Their rank and our number of equal closed-loop continuation laws need not order one another; we therefore make no “smaller than PSR” claim. Neural causal-state representations learn predictive summaries of action–observation histories (Zhang et al. 2019); their focus is representation and downstream control, whereas ours is an exact finite-alphabet partition with an abstaining finite-sample certificate. Model-based lossless history clustering has been used to accelerate Dec-POMDP planning (Oliehoek et al. 2009); our setting instead learns a policy-specific predictive partition from sampled trajectories. #### Testing and calibration. Each pairwise decision is an instance of two-sample closeness testing on a $d$-element alphabet (Batu et al. 2000). Our plug-in TV test pays $\Theta(d/\varepsilon^2)$ samples per pair; optimal closeness testers achieve $\Theta(\max(d^{2/3}/\varepsilon^{4/3},\, d^{1/2}/\varepsilon^2))$ (Chan et al. 2014). Corollary 5 makes the substitution precise: any closeness tester replaces the plug-in test inside the same union bound on every pair of *non-nested* contexts, while nested pairs genuinely require the one-count conditioning of Lemma 7; and because published optimal testers state their complexity only up to unspecified constants, the substituted gate is no longer a closed-form function of its own bound (Appendix D). We retain the linear-in-$d$ plug-in test on all pairs as the price of an executable gate; the $d$-dependence of our upper bound is a design choice, not a proven necessity (Section 4). Classical likelihood-ratio tests use an asymptotic chi-square calibration. Our software retains such a G-test for exploratory analysis, but the theorem-facing path instead uses the finite-alphabet $L_1$ deviation inequality of Weissman et al. (2003). Sample splitting is classical for making selection compatible with inference (Cox 1975; Wasserman and Roeder 2009) and is what makes the random context set compatible with a direct union bound here; abstention has a corresponding tradition in selective classification (Chow 1970; El-Yaniv and Wiener 2010), though our gate refuses on a precomputed count threshold, never on the realized statistic — a power gate, not a data-adaptive rejector. # Estimand and data contract Let $Z_i=(O_{i,0},A_{i,0},O_{i,1},\ldots)$, $i=1,\ldots,N$, be independent trajectories. Each trajectory is generated by the same reset distribution and the same fixed policy $\pi$, whose internal state (if any) is reset identically. The policy may depend on within-episode history. Fix a context endpoint $r\ge0$, maximum context length $L$, and future horizon $k\ge1$ before seeing trajectory values. Only lengths $1\le \ell\le\min(L,r+1)$ are eligible. The empty root is excluded throughout. For $h=(o_{r-\ell+1},\ldots,o_r)$ define the continuation $C=(O_{r+1},\ldots,O_{r+k})\in\mathcal C=\mathcal O^k$. A trajectory that terminates before $r+k$ contributes no block. Let ``` math $$ P_h(c)=\mathbb P_\pi(C=c\mid H=h,\; Z\text{ reaches }r+k), \qquad c\in\mathcal C. $$ ``` The conditioning event and its probability are part of the estimand. **Definition 1** (Episode-position predictive quotient). *For a finite candidate set $\mathcal H$, define $h\sim g$ iff $P_h=P_g$. The quotient is $\mathcal H/{\sim}$. Its visitation mass is $\mu_h=\mathbb P(H=h, Z\text{ reaches }r+k)$.* Because eligible lengths overlap, a realized history at endpoint $r$ matches up to $\min(L,r+1)$ nested contexts, which the quotient treats as distinct elements of $\mathcal H$; the induced map from histories to states assigns each history the class of its longest eligible context, in the manner of suffix- tree leaf semantics (Appendix E). Merged contexts are exchangeable for evaluating any return that is measurable in the continuation window (Proposition 9). This equivalence is policy dependent in general: two contexts inducing the same latent belief can still have different joint action–observation futures under a history-dependent policy. If actions are included, the continuation alphabet is $(\mathcal A\times\mathcal O)^k$ and has size $|\mathcal A|^k|\mathcal O|^k$, not $|\mathcal O|^k$. Appendix E states both facts formally. For continuous observations, binning defines a new discrete estimand; it does not automatically recover the unbinned quotient. #### Gap model. Exact partition recovery is impossible without separation. We assume that for every $h,g\in\mathcal H$, either $P_h=P_g$ or ``` math $$ \mathop{\mathrm{TV}}(P_h,P_g)\ge\varepsilon, \qquad \varepsilon\in(0,1]. $$ ``` The visitation assumption is per context, $\mu_h\ge\mu_{\min}>0$; class mass alone is insufficient to ensure samples for every representative. # Estimator Partition trajectory identifiers before collection and split whole trajectories into a selection half and an inference half (the implementation uses collection order, fixed independently of trajectory values). At endpoint $r$, retain contexts observed at least $q$ times in the selection half, with $q\le m^*$ for the complexity statement below. On the inference half, take at most one block at the same fixed endpoint from each trajectory. Let $m_h$ and $\widehat P_h$ be its count and empirical law. For alphabet size $d=|\mathcal C|$ and pairwise budgets $\alpha,\beta$, define ``` math $$ m^*(\varepsilon,\alpha,\beta,d)= \left\lceil \frac{8}{\varepsilon^2} \left((d+1)\log2+\log\frac{1}{\alpha\wedge\beta}\right) \right\rceil . $$ ``` For each pair, return UNDETERMINED if either count is below $m^*$. Otherwise return SAME when $\mathop{\mathrm{TV}}(\widehat P_h,\widehat P_g)<\varepsilon/2$ and DIFFERENT otherwise. Union–find transmits only SAME edges. Thus an abstention can over-split the reported graph but can never be silently interpreted as evidence of equality. Boundary flags are operational: a pair of reported classes is flagged iff at least one context pair straddling the two classes returned UNDETERMINED, so the reported separation rests in part on an abstention; per-run flag counts appear in every certified results row (the head-to-head’s compact verdict table, whose certified arm reports zero abstentions, records verdicts only). Every selected context is retained through inference: a context whose count is too small abstains on all of its pairs; it is never dropped. (The implementation additionally enforces a floor of $30$ samples per histogram; since $m^*\ge30$ in every configuration reported here, the effective gate is $\max(m^*,30)=m^*$.) **Theorem 1** (Finite-sample pair test). *Fix a pair $h,g$ and any $m\ge1$, and let ``` math $$ B(m,d,\varepsilon)=2^{d+1}\exp(-m\varepsilon^2/8). $$ ``` If $P_h=P_g$, then $\mathbb P\{\mathrm{Different},\, m_h\ge m,\, m_g\ge m\}\le B(m,d,\varepsilon)$. If $\mathop{\mathrm{TV}}(P_h,P_g)\ge\varepsilon$, the probability of $\{\mathrm{Same},\, m_h\ge m,\, m_g\ge m\}$ obeys the same bound. Consequently, with $m=m^*$, the two error-with-verdict events have probability at most $\alpha$ and $\beta$, respectively.* The proof bounds, for each context separately, the joint event that its count reaches $m$ *and* its empirical law deviates; conditional on a context’s own count—a symmetric function of the per-trajectory “contributes to $h$” indicators alone—its contributing blocks are iid draws from $P_h$. No conditioning on the other context’s count is ever used. This matters because different context lengths at one endpoint are nested: every trajectory matching a longer context also feeds its shorter suffixes, so conditioning on both counts jointly would bias the contributing sample. See Appendix A. **Theorem 2** (Exact recovery on a selected set). *Condition on any candidate set $\mathcal H$ chosen using only the selection half, with $K=|\mathcal H|\ge2$. Set $\alpha=\beta=\delta/(2K^2)$ and suppose the gap condition Eq. (2) holds. With probability at least $1-\delta/2$, every pair whose two counts reach $m^*(\varepsilon,\alpha,\beta,d)$ receives its correct verdict; in particular, on the event that every inference count is at least $m^*$, union–find returns exactly $\mathcal H/{\sim}$ and returns no abstentions.* **Corollary 3** (Trajectory complexity). *Let the two halves each contain $M=\lfloor N/2\rfloor$ trajectories. Suppose a deterministic universe of $K$ eligible contexts containing every context that selection can return satisfies $\mu_h\ge\mu_{\min}$ and the gap condition. If ``` math $$ M\ge \max\left\{ \frac{2q}{\mu_{\min}}, \frac{2m^*}{\mu_{\min}}, \frac{8}{\mu_{\min}}\log\frac{4K}{\delta} \right\}, $$ ``` where $m^*$ uses $\delta/(2K^2)$, then all eligible contexts are selected, no pair abstains, and the exact quotient is returned with probability at least $1-\delta$. Since $q\le m^*$ may be assumed, it follows that $N=O((d+\log(K/\delta))/(\mu_{\min}\varepsilon^2))$.* The count terms follow from multiplicative Chernoff bounds for the selection and inference halves. Notice what is absent from Eq. (5): trajectory length does not create extra iid samples because the certified procedure uses one block per trajectory. The allocation $\alpha=\beta=\delta/(2K^2)$ is deliberately conservative: the proof of Theorem 2 spends only $\delta/(4K)$ across per-context deviation events, so setting the pairwise budget to that actual total spend — a relaxation by a factor of $K/2$ — shrinks $m^*$ by roughly ten percent in the configurations reported here ($451\to407$ on the 8-cycle sweep). We keep the $K^2$ allocation because it certifies each pairwise verdict at level $\alpha$ individually, which post-hoc inspection of any single pair can rely on. **Proposition 4** (Lower bound). *For $0<\varepsilon\le1/4$ and $0<\mu\le1/2$, there are two finite-alphabet, independently reset trajectory models satisfying the data contract, one with one predictive class and one with two classes separated by $\varepsilon$, such that any estimator has worst-case partition error at least $3/8$ whenever $N\le1/(32\mu\varepsilon^2)$. Thus the dependence on $1/(\mu_{\min}\varepsilon^2)$ in Corollary 3 is unavoidable.* The construction has $d=2$, so it says nothing about the linear dependence on $d$ in Eq. (3); that factor is a cost of the plug-in test and is improvable in principle by optimal closeness testers (Chan et al. 2014). The $\log K$ factor is likewise not matched. The construction changes a Bernoulli continuation only after a context of mass $\mu$ and applies Le Cam’s two-point method (Tsybakov 2009, Theorem 2.2); the complete calculation is in Appendix C. Two extensions come at no cost to the architecture. First, the pairwise test is a module: **Corollary 5** (Tester substitution on non-nested pairs). *Let $A$ be any two-sample closeness tester that, given $m$ iid samples from each of two laws on $d$ elements, reports SAME under equality and DIFFERENT under $\mathop{\mathrm{TV}}\ge\varepsilon$, each with error probability at most $\gamma$ whenever $m\ge n(d,\varepsilon,\gamma)$. Replace the plug-in test by $A$, and the gate by $n(d,\varepsilon,\delta/(2K^2))$, on every pair of contexts neither of which is a suffix of the other, retaining the plug-in test and the $m^*$ gate on nested pairs. Theorem 2 holds unchanged. With the tester of Chan et al. (2014) amplified by majority vote, $n(d,\varepsilon,\gamma)=O\bigl((d^{2/3}/\varepsilon^{4/3}+d^{1/2}/\varepsilon^{2}) \log(1/\gamma)\bigr)$; when $L=1$ no nested pairs exist and the substitution is total.* The non-nested restriction is genuine, not cosmetic: nested contexts share their contributing blocks verbatim, so a black-box two-sample tester’s independence requirement fails for exactly the pairs whose analysis motivated Lemma 7; and the unspecified constants in optimal testers leave the substituted gate non-executable as a closed-form abstention rule (Appendix D). Second, the single endpoint generalizes by one union-bound level: **Corollary 6** (Multi-endpoint families). *Fix endpoints $r_1<\dots, directory `oql/`; every path below is relative to that directory, and the version cited here is the release tagged `v1`, which points to commit `83f9f42d8533c62fd05fcef2192559e0f80be3d9` of the public repository (tags can be retargeted, so the hash is the immutable reference; the `commit` field inside each JSON sidecar records the hash of the development repository at generation time and need not resolve in the public one). The exact commands, CSV rows, JSON sidecars, seeds, and package versions are under `experiments/main_table/results_independent_smoke`, `experiments/main_table/results_abstention_sweep`, `experiments/main_table/results_headtohead`, and one `experiments/main_table/results_*` directory per additional check above (`results_sweep_depth2`, `results_nested`, `results_multiendpoint`, `results_nondegenerate`, `results_posthoc`, `results_misspec`); the per-seed recovered partitions are in `experiments/main_table/results_partitions/partitions_per_seed.csv`. A SHA-256 manifest of these artifacts, the runners, the environments, the package, the paper source, and the lockfile is at `experiments/ARTIFACTS_MANIFEST.json`, and `python scripts/gen_manifest.py --check` verifies it. Tests check the TV calculation, sample bound, split disjointness, one-block invariant, Bonferroni level, action-aware alignment and stride, root exclusion, policy and environment generator independence, and sidecar validation. No external datasets, GPUs, or human data are used. # Limitations and broader impact The target is intentionally narrow. It depends on the behavior policy, reset law, endpoint $r$, continuation horizon $k$, and termination conditioning. Equality for one $k$ need not imply equality for longer futures; rewards measurable in the $k$-step window are preserved across merged contexts (Proposition 9), but no claim is made for rewards depending on the latent state or on longer horizons. The method does not learn a POMDP model or an optimal policy, nor do we demonstrate a downstream consumer: quantifying the benefit of the recovered partition to a planner or policy evaluator is out of scope here; the partition’s certified currency is the exchangeability of Proposition 9. Rare contexts incur the explicit $1/\mu_{\min}$ cost; large action- aware alphabets incur exponential dependence on $k$ through $d$; and exact recovery requires the gap model. When the visitation floor fails, abstention is the intended output. A gap-model failure is different in kind: a pair at $0<\mathop{\mathrm{TV}}<\varepsilon/2$ passes the gate and is merged under a confident but uncertified SAME verdict — refusal semantics do not survive misspecification of $\varepsilon$. The misspecification probe in Section 5 realizes exactly this regime, and its artifacts carry a per-SAME-edge TV margin so that near-threshold merges are visible rather than silent. A gap-free alternative deliverable would be per-pair confidence intervals for $\mathop{\mathrm{TV}}(P_h,P_g)$ from the same deviation inequality Eq. (6): they degrade continuously and cannot silently overclaim. We retain the partition output because downstream consumers of a state abstraction need equivalence classes, which intervals produce only through exactly the thresholding analyzed here; reporting both is natural in practice. Binning continuous observations changes the estimand, and no unbinned recovery claim is made. Independent resets and one block per trajectory can be statistically expensive. Mixing-based reuse of long trajectories is valuable future work — the single-trajectory Markov-chain testing literature gives the relevant rates (Daskalakis et al. 2018; Wolfer and Kontorovich 2019) — but requires correct block geometry: for history length $\ell$, horizon $k$, and start spacing $s$, the unsampled gap is $s-(\ell+k)$, not $s$. Merely choosing non-overlapping blocks supplies no mixing gap. A cheaper intermediate — a family of endpoints $r_1,\ldots,r_T$ with one more union-bound level — is delivered as Corollary 6: it reuses long trajectories at $\log T$ gate cost without any mixing argument, and Section 5 exercises it at $T=2$. This is foundational methodology with no direct deployment or personal data. A positive impact is more honest uncertainty reporting in learned state abstractions. A misuse risk is treating an estimated class as a safety- relevant state despite policy shift or many abstentions. We mitigate that risk by exposing the estimand and boundary flags and by refusing low-power merges. # Conclusion Predictive history clustering becomes a well-posed finite-sample problem only after the target and sampling unit are fixed. Splitting trajectories, sampling one prespecified block per inference episode, and using a non-asymptotic TV test yields an estimator whose implementation matches its proof. The result is less data-efficient than overlapping-window heuristics, but its guarantees do not depend on an unearned iid approximation. # Proof of the pair test For a distribution $P$ on an alphabet of size $d$ and its empirical law $\widehat P_m$ from $m$ iid draws, Weissman et al. (2003, Theorem 2.1) imply the convenient relaxation ``` math $$ \mathbb P(\|\widehat P_m-P\|_1\ge x) \le 2^d\exp(-mx^2/2). $$ ``` **Lemma 7** (Per-context deviation with count). *For a context $h$ and any $m\ge1$, define the event $D_h(m)=\{m_h\ge m\}\cap\{\mathop{\mathrm{TV}}(\widehat P_h,P_h)\ge\varepsilon/4\}$. Then $\mathbb P(D_h(m))\le 2^d\exp(-m\varepsilon^2/8)$.* *Proof.* Trajectory $i$ contributes to $h$ iff the indicator $I_i=\mathbf 1\{H_i=h,\ Z_i\text{ reaches }r+k\}$ equals one, and conditional on $I_i=1$ its block has law $P_h$ by Eq. (1), independently across the iid trajectories. The count $m_h=\sum_i I_i$ is a function of the indicators alone, so conditional on $\{m_h=m'\}$—for any $m'$—the $m'$ contributing blocks are iid draws from $P_h$. Hence, using $\mathop{\mathrm{TV}}=\|\cdot\|_1/2$ and Eq. (6) with $x=\varepsilon/2$, ``` math \mathbb P(D_h(m)) =\sum_{m'\ge m}\mathbb P(m_h=m')\, \mathbb P\bigl(\mathop{\mathrm{TV}}(\widehat P_h,P_h)\ge\varepsilon/4\bigm|m_h=m'\bigr) \le 2^d\exp(-m\varepsilon^2/8). \qedhere ```  ◻ The lemma conditions on one count at a time. This is what makes nested contexts harmless: conditioning jointly on the counts of a context and one of its refinements would bias the contributing sample (in the extreme, all of $h$’s blocks could be forced to coincide with $g$’s), but no such joint conditioning ever occurs. #### Proof of Theorem 1. Suppose first that $P_h=P_g=P$. On the event $\{\mathrm{Different},\,m_h\ge m,\,m_g\ge m\}$ we have $\mathop{\mathrm{TV}}(\widehat P_h,\widehat P_g)\ge\varepsilon/2$, so by the triangle inequality at least one of $\mathop{\mathrm{TV}}(\widehat P_h,P)$ and $\mathop{\mathrm{TV}}(\widehat P_g,P)$ is at least $\varepsilon/4$; the event is therefore contained in $D_h(m)\cup D_g(m)$. Lemma 7 and a union bound give Eq. (4). Now suppose $\mathop{\mathrm{TV}}(P_h,P_g)\ge\varepsilon$. If the test returns SAME, ``` math $$ \begin{aligned} \varepsilon &\le \mathop{\mathrm{TV}}(P_h,P_g)\\ &\le \mathop{\mathrm{TV}}(P_h,\widehat P_h) +\mathop{\mathrm{TV}}(\widehat P_h,\widehat P_g) +\mathop{\mathrm{TV}}(\widehat P_g,P_g), \end{aligned} $$ ``` so the two empirical errors sum to more than $\varepsilon/2$, one is at least $\varepsilon/4$, and the event is again contained in $D_h(m)\cup D_g(m)$. Finally, substitution of Eq. (3) makes Eq. (4) no larger than $\alpha\wedge\beta$. 0◻ # Recovery and coverage proofs #### Proof of Theorem 2. Conditioning on the selection half makes $\mathcal H$ fixed relative to inference, and the inference half is independent of that choice. For each $h\in\mathcal H$ consider the event $D_h(m^*)$ of Lemma 7. With $\alpha=\beta=\delta/(2K^2)$, definition Eq. (3) gives $2^d\exp(-m^*\varepsilon^2/8)\le\delta/(4K^2)$, so $\mathbb P\bigl(\bigcup_{h\in\mathcal H}D_h(m^*)\bigr)\le\delta/(4K)\le\delta/2$. On the complement, every context whose count reaches $m^*$ has empirical deviation below $\varepsilon/4$; hence, exactly as in the proof of Theorem 1, every pair whose two counts reach $m^*$ receives its correct verdict: within-class pairs get SAME edges and between-class pairs get DIFFERENT edges. If in addition every count is at least $m^*$, no pair abstains and union–find returns exactly the equivalence classes. 0◻ #### Proof of Corollary 3. For context $h$, its count in either half is binomial with mean at least $M\mu_{\min}$. The multiplicative Chernoff inequality gives ``` math $$ \mathbb P\{m_h0$, and terms with $\lambda_g=0$ are omitted from every sum and mixture below. Then, whenever $\lambda_h+\sum_{g\in G_h}\lambda_g>0$, ``` math P_h\;=\;\frac{\lambda_h Q_h+\sum_{g\in G_h}\lambda_g Q_g} {\lambda_h+\sum_{g\in G_h}\lambda_g}, ``` and $Q_g=P_g$ for every $g\in\mathcal H$ with $\lambda_g>0$ that has no proper extension in $\mathcal H$. Consequently:* 1. *If $\mathcal H$ is the full eligible universe (the event of Corollary 3), every history routes to a context of the maximal eligible length $\min(L,r+1)$. Hence a class all of whose members are non-maximal contexts has $\lambda_c=0$: it receives no routed histories and has no routed law (for example the singleton class $\{(0)\}$ in the nested $L=2$ example of Appendix G). For every class $c$ with positive routed mass $\lambda_c=\sum_{m\in c}\lambda_m>0$, the continuation law of the histories routed to $c$, given reaching $r+k$, is the mixture of $Q_m=P_m$ over the members $m$ with $\lambda_m>0$, and equals the common law $P_c$ of its members. The induced state map is total, but only classes with positive routed mass are ever the image of a history.* 2. *If $\mathcal H$ is a strict subset, then for a class $c$ containing a non-maximal member $h$ whose extensions in $\mathcal H$ include contexts $g$ with $P_g\ne P_h$, $Q_h$ is the residual law determined by the display, and it differs from $P_h$ whenever the extensions’ laws $Q_g$ do not average to $P_h$. It equals $P_h$ if every $g\in G_h$ has $Q_g=P_h$, for instance if all of $G_h$ is maximal and lies in the class of $h$. No claim is made beyond this: the certificate covers the equalities $P_h=P_g$, not the residual laws $Q_h$.* *Proof.* Every history in $E_h$ either routes to $h$ or matches some $g\in G_h$ and then routes to a longest match $g'$, which is longer than $g$ and so also has $h$ as a suffix, i.e. $g'\in G_h$ (histories routed to a context with $\lambda=0$ carry no mass and are omitted by the convention). Thus $E_h=R_h\sqcup\bigsqcup_{g\in G_h}R_g$, and the display is the law of total probability for $P_h=\mathbb P(C=\cdot\mid E_h,\text{reach})$. A context with no extension in $\mathcal H$ has $R_g=E_g$, so $Q_g=P_g$ when $\lambda_g>0$. In case 1 all routing is to maximal contexts, so $\lambda_m=0$ for non-maximal $m$; each member $m$ of $c$ with $\lambda_m>0$ satisfies $Q_m=P_m=P_c$, and if $\lambda_c>0$ the routed law is a mixture of equal laws, which is that law. For the last statement of case 2, if all $Q_g$ ($g\in G_h$) equal $P_h$, the display forces $Q_h=P_h$ when $\lambda_h>0$. ◻ No experiment in this paper exercises case 2: every check either has $L=1$ or runs the nested check with the full eligible universe (twelve contexts). Let $B$ be a measurable binning map for continuous observations. Data processing gives $\mathop{\mathrm{TV}}(P\circ B^{-1},Q\circ B^{-1})\le\mathop{\mathrm{TV}}(P,Q)$. Hence binning may merge distinct unbinned laws. Recovery of the original quotient requires an extra identifiability condition, such as all relevant likelihood ratios being measurable with respect to the bin sigma-algebra. The implementation and all theorems in the paper concern the binned law itself. # Algorithmic and reproducibility details The estimator uses a deterministic 50/50 split of independently generated trajectory identifiers. Determinism is for reproducibility; because ordering is fixed before values are generated, the halves remain independent. The candidate universe comprises suffixes of lengths $1$ through $\min(L,r+1)$ observed at the fixed endpoint. The root is omitted before both the proposed estimator and the same-target baseline are counted. Pairwise work is $O(K^2(d+m_{\max}))$ with direct histograms, plus collection cost. Memory is $O(Kd+K^2)$ if all verdicts are retained. All runs are CPU-only in the audited environment: a few seconds per seed for the main-table checks (about three minutes for all $3\times20$ runs), under a minute for each 80-run abstention sweep, and a few minutes for the remaining Section 5 checks combined (the nested $L=2$ run, at $140{,}000$ episodes $\times$ 20 seeds, dominates); no GPU was used. Artifact locations: repository , directory `oql/`, release tag `v1` (commit `83f9f42d8533c62fd05fcef2192559e0f80be3d9`); result directories, the per-seed partition CSV and the SHA-256 manifest (`experiments/ARTIFACTS_MANIFEST.json`) are listed at the end of Section 5, and the environment specifications are in Appendix G. The project is released under the MIT license and the submission uses only synthetic environments implemented in the repository. # Environment specifications and per-seed outputs This appendix gives the complete generative specification of every environment in Section 5, so that the analytic gaps used to set $\varepsilon$ can be re-derived by hand, and the per-seed recovered partitions. In all environments an episode is $O_0,A_0,O_1,A_1,\ldots$: the reset emits $O_0$ and each action emits the next observation. Every run below uses the 50/50 split, $\delta=\beta=0.05$, and one block per inference trajectory. Contexts are written by their observation word; a continuation law is a distribution over the next symbol(s). Exact values below are computed by the code (`environments/`); all environments except Tiger have a single action, so the policy is immaterial there. #### Tiger (always listen; Table 1). The tiger state $S\in\{\text{L},\text{R}\}$ is uniform at reset and fixed within the episode; $O_0$ is uniform and independent of $S$. Listening emits the matching side with probability $a=0.85$ (hear-left iff tiger-left) and the other side with probability $0.15$. A door opening ends the episode and emits a uniform terminal observation. With always-listen, $r=1$, $k=1$, the context is $O_1$ and the continuation $O_2$; with a uniform prior, $\mathbb P(S{=}\text{L}\mid O_1{=}\text{L})=0.85$ and $\mathbb P(O_2{=}\text{L}\mid O_1{=}\text{L})=0.85^2+0.15^2=0.745$ versus $0.255$ after $O_1=\text{R}$, so $\mathop{\mathrm{TV}}=0.49=(2a-1)^2$. Episodes are truncated at 15 steps. The stochastic-policy variant is specified in Section 5. #### Noisy 8-cycle. Hidden state $S_t\in\mathbb Z_8$; $S_0$ uniform; the single action is deterministic, $S_{t+1}=S_t+1\bmod 8$. Each step emits $O_t=S_t$ with probability $0.85$ and otherwise a uniform symbol on $\{0,\ldots,7\}$, so $\mathbb P(O_t=S_t)=0.85+0.15/8=0.86875$ and every other symbol has probability $0.01875$. At $r=0$, $k=1$, the posterior of $S_0$ given $O_0=i$ is $0.85\,\delta_i+0.01875\cdot\mathbf 1$, whence $P_{(i)}=0.7225\,\delta_{i+1}+0.0346875\cdot\mathbf 1$ and $\mathop{\mathrm{TV}}(P_{(i)},P_{(j)})=0.7225=0.85^2$ for every $i\neq j$: eight singleton classes. Episodes are truncated at 20 steps. #### Noisy depth-2 chain ($m=2$, $\eta=0.1$, $\nu=0.2$). Alphabet $\{0,1,2\}$; the observation process is second-order Markov and the hidden state is the last two symbols with identity emission of the later one. The next-symbol law given $(\text{prev},\text{cur})$ is $(0.8,0.1,0.1)$ whenever $\text{cur}\ne0$ (“$L_{\text{odd}}$”); uniform $(\tfrac13,\tfrac13,\tfrac13)$ for $(0,0)$; $(\tfrac1{30},\tfrac1{30},\tfrac{28}{30})$ for $(1,0)$; and $(\tfrac1{30},\tfrac{28}{30},\tfrac1{30})$ for $(2,0)$ (that is, $(1-\eta)\,\delta_{\text{succ}(\text{prev})}+\eta\,\mathrm{Unif}$ with $\text{succ}(1)=2$, $\text{succ}(2)=1$). The reset draws $(\text{prev},\text{cur})$ from the stationary pair distribution, so the process is stationary from $O_0$; the stationary symbol masses are $(0.4565,0.2717,0.2717)$. At $r=0$, $k=1$ the three length-one contexts have laws $P_{(0)}=(\tfrac1{21},\tfrac{10}{21},\tfrac{10}{21})$ and $P_{(1)}=P_{(2)}=(0.8,0.1,0.1)$, so the quotient has two classes with $\mathop{\mathrm{TV}}=0.7524$. At $r=1$ with $L=2$ (nested check) there are twelve positive-mass contexts: $(0)$, $(0,0)$, $(1,0)$, $(2,0)$ are singleton classes and the other eight (including $(1)$, $(2)$, $(0,1)$, $(0,2)$, $(1,1)$, $(1,2)$, $(2,1)$, $(2,2)$) share the $L_{\text{odd}}$ law, giving five classes with minimal between-class TV $2/7$, attained by $(0)$ versus $(0,0)$. Episodes are truncated at 60 steps (3 in the nested check). #### Position-flip chain. Binary alphabet; $O_0$ uniform; one step from $O_t=x$ at position $t$ emits $O_{t+1}=1$ with probability $0.9$ if $(t\text{ even},x=0)$ or $(t\text{ odd},x=1)$, and with probability $0.1$ otherwise. By induction every $O_t$ is marginally uniform. At $r=0$: $P_{(0)}=\mathrm{Ber}(0.9)$, $P_{(1)}=\mathrm{Ber}(0.1)$, $\mathop{\mathrm{TV}}=0.8$; at $r=1$ the two laws swap. The position-pooled continuation law after either symbol is $\mathrm{Ber}(0.5)$. Episodes are truncated at 40 steps (8 in the two-endpoint check). #### Misspecification chain. First-order Markov on $\{0,1,2\}$, $O_0$ uniform, next-symbol rows $(0.45,0.45,0.10)$ after $0$; $(0.55,0.35,0.10)$ after $1$ ($=(0.45+\tau,0.45-\tau,0.10)$ with $\tau=0.10$); and $(0.05,0.05,0.90)$ after $2$. The continuation law of a context is the row of its last symbol at every position, so at $r=0$, $k=1$: $\mathop{\mathrm{TV}}(P_{(0)},P_{(1)})=\tau=0.1$ (the engineered sub-gap pair) and $\mathop{\mathrm{TV}}=0.8$ for the other two pairs; the true quotient has three classes. Episodes are truncated at 3 steps. #### Random three-state HMM (data-driven $\varepsilon$ check). $S_0\sim\pi_0$, $O_t\sim B[S_t,\cdot]$, $S_{t+1}\sim A[S_t,\cdot]$, one action, episodes truncated at 2 steps. All rows were drawn from $\mathrm{Dirichlet}(0.3\cdot\mathbf 1)$ with instance seed $1000$ (the first instance in the pre-fixed scan with minimum pairwise TV at least $0.15$); rounded to four decimals, $\pi_0=(0.3623,0.2581,0.3796)$, ``` math A=\begin{pmatrix}0.0212&0.1998&0.7790\\0.0145&0.9672&0.0183\\0.4429&0.5571&0.0000\end{pmatrix},\qquad B=\begin{pmatrix}0.0216&0.9777&0.0007\\0.9096&0.0001&0.0903\\0.0000&0.1043&0.8957\end{pmatrix} ``` (the entries shown as $0.0000$ are $2.6\cdot10^{-6}$ and $1.1\cdot10^{-6}$; unrounded values are in `results_posthoc/ground_truth.json`). At $r=0$, $k=1$ the context masses are $(0.2426,0.3938,0.3636)$, the laws are $P_{(0)}=(0.8575,0.0189,0.1235)$, $P_{(1)}=(0.2158,0.1353,0.6489)$, $P_{(2)}=(0.5394,0.4061,0.0545)$, and the pairwise TVs are $0.6417$ for $(0),(1)$; $0.3872$ for $(0),(2)$; $0.5944$ for $(1),(2)$: three singleton classes. #### Per-seed partitions. Class counts do not show that the recovered *partition* is correct, so every reported configuration was re-run with its original seeds and the recovered partition recorded against the exact truth (`experiments/main_table/run_partitions.py`; one row per experiment, endpoint and seed in `experiments/main_table/results_partitions/partitions_per_seed.csv`, which also records the number of context pairs whose same/different label disagrees with the truth). The re-run class counts equal those in the original CSVs on every row that has a committed counterpart. Table 2 summarizes it; “pairs wrong” is the maximum over seeds of the number of context pairs on which the recovered and true partitions disagree, out of all pairs. | experiment | $r$ | seeds | exact | pairs wrong | recovered partition | |:---|---:|---:|---:|---:|:---| | Tiger (always listen) | 1 | 20 | 20/20 | 0/1 | 0 $\mid$ 1 | | noisy 8-cycle | 0 | 20 | 20/20 | 0/28 | 0 $\mid$ 1 $\mid$ 2 $\mid$ 3 $\mid$ 4 $\mid$ 5 $\mid$ 6 $\mid$ 7 | | noisy depth-2 (merge) | 0 | 20 | 20/20 | 0/3 | 0 $\mid$ 1,2 | | position-flip chain | 0 | 10 | 10/10 | 0/1 | 0 $\mid$ 1 | | position-flip, two endpoints | 0 | 10 | 10/10 | 0/1 | 0 $\mid$ 1 | | position-flip, two endpoints | 1 | 10 | 10/10 | 0/1 | 0 $\mid$ 1 | | noisy depth-2, nested $L=2$ | 1 | 20 | 20/20 | 0/66 | 0 $\mid$ 0-0 $\mid$ 0-1,0-2,1,1-1,1-2,2,2-1,2-2 $\mid$ 1-0 $\mid$ 2-0 | | Tiger, stochastic policy | 1 | 20 | 20/20 | 0/1 | 0 $\mid$ 1 | | random HMM (data-driven $\varepsilon$) | 0 | 20 | 20/20 | 0/3 | 0 $\mid$ 1 $\mid$ 2 | | misspecification probe $\dagger$ | 0 | 10 | 0/10 | 1/3 | 0,1 $\mid$ 2 | Per-seed partition recovery. A context of length two is written $o_{r-1}\text{-}o_r$; classes are separated by $\mid$. The last column is the recovered partition when it is identical across seeds (it was, in every row). Rows marked $\dagger$ are the misspecification probe, outside the gap model, where the sub-gap pair is merged by design. Balle, Borja, Jorge Castro, and Ricard Gavaldà. 2013. “Learning Probabilistic Automata: A Study in State Distinguishability.” *Theoretical Computer Science* 473: 46–60. Batu, Tuğkan, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White. 2000. “Testing That Distributions Are Close.” *Proceedings of the 41st Annual Symposium on Foundations of Computer Science*, 259–69. . Boots, Byron, Sajid M. Siddiqi, and Geoffrey J. Gordon. 2010. “Closing the Learning–Planning Loop with Predictive State Representations.” *Proceedings of Robotics: Science and Systems VI*. . Bühlmann, Peter, and Abraham J. Wyner. 1999. “Variable Length Markov Chains.” *Annals of Statistics* 27 (2): 480–513. Carrasco, Rafael C., and Jose Oncina. 1994. “Learning Stochastic Regular Grammars by Means of a State Merging Method.” *Grammatical Inference and Applications (ICGI)*, Lecture notes in computer science, vol. 862: 139–52. Cassandra, Anthony R., Leslie Pack Kaelbling, and Michael L. Littman. 1994. “Acting Optimally in Partially Observable Stochastic Domains.” *Proceedings of the 12th National Conference on Artificial Intelligence*, 1023–28. Castro, Pablo Samuel. 2020. “Scalable Methods for Computing State Similarity in Deterministic Markov Decision Processes.” *Proceedings of the AAAI Conference on Artificial Intelligence*, 10069–76. Castro, Pablo Samuel, Tyler Kastner, Prakash Panangaden, and Mark Rowland. 2021. “MICo: Improved Representations via Sampling-Based State Similarity for Markov Decision Processes.” *Advances in Neural Information Processing Systems* 34. Castro, Pablo Samuel, Prakash Panangaden, and Doina Precup. 2009. “Equivalence Relations in Fully and Partially Observable Markov Decision Processes.” *Proceedings of the 21st International Joint Conference on Artificial Intelligence*, 1653–58. Chan, Siu-On, Ilias Diakonikolas, Gregory Valiant, and Paul Valiant. 2014. “Optimal Algorithms for Testing Closeness of Discrete Distributions.” *Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms*, 1193–203. . Chow, C. K. 1970. “On Optimum Recognition Error and Reject Tradeoff.” *IEEE Transactions on Information Theory* 16 (1): 41–46. . Clark, Alexander, and Franck Thollard. 2004. “PAC-Learnability of Probabilistic Deterministic Finite State Automata.” *Journal of Machine Learning Research* 5: 473–97. Cox, D. R. 1975. “A Note on Data-Splitting for the Evaluation of Significance Levels.” *Biometrika* 62 (2): 441–44. . Crutchfield, James P., and Karl Young. 1989. “Inferring Statistical Complexity.” *Physical Review Letters* 63 (2): 105–8. . Csiszár, Imre, and Zsolt Talata. 2006. “Context Tree Estimation for Not Necessarily Finite Memory Processes, via BIC and MDL.” *IEEE Transactions on Information Theory* 52 (3): 1007–16. Daskalakis, Constantinos, Nishanth Dikkala, and Nick Gravin. 2018. “Testing Symmetric Markov Chains from a Single Trajectory.” *Proceedings of the 31st Conference on Learning Theory*, Proceedings of machine learning research, vol. 75: 385–409. Du, Simon S., Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudík, and John Langford. 2019. “Provably Efficient RL with Rich Observations via Latent State Decoding.” *Proceedings of the 36th International Conference on Machine Learning*, Proceedings of machine learning research, vol. 97: 1665–74. Efroni, Yonathan, Chi Jin, Akshay Krishnamurthy, and Ayush Sekhari. 2022. “Provable Reinforcement Learning with a Short-Term Memory.” *Proceedings of the 39th International Conference on Machine Learning*, Proceedings of machine learning research, vol. 162: 5832–50. El-Yaniv, Ran, and Yair Wiener. 2010. “On the Foundations of Noise-Free Selective Classification.” *Journal of Machine Learning Research* 11: 1605–41. Ferns, Norm, Prakash Panangaden, and Doina Precup. 2004. “Metrics for Finite Markov Decision Processes.” *Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence*, 162–69. Givan, Robert, Thomas Dean, and Matthew Greig. 2003. “Equivalence Notions and Model Minimization in Markov Decision Processes.” *Artificial Intelligence* 147 (1–2): 163–223. . Golowich, Noah, Ankur Moitra, and Dhruv Rohatgi. 2022. “Learning in Observable POMDPs, Without Computationally Intractable Oracles.” *Advances in Neural Information Processing Systems* 35: 1458–73. Guo, Zhaohan Daniel, Shayan Doroudi, and Emma Brunskill. 2016. “A PAC RL Algorithm for Episodic POMDPs.” *Proceedings of the 19th International Conference on Artificial Intelligence and Statistics*, Proceedings of machine learning research, vol. 51: 510–18. . Holmes, Michael P., and Charles Lee Isbell. 2006. “Looping Suffix Tree-Based Inference of Partially Observable Hidden State.” *Proceedings of the 23rd International Conference on Machine Learning*, 409–16. Hsu, Daniel, Sham M. Kakade, and Tong Zhang. 2012. “A Spectral Algorithm for Learning Hidden Markov Models.” *Journal of Computer and System Sciences* 78 (5): 1460–80. . Jaeger, Herbert. 2000. “Observable Operator Models for Discrete Stochastic Time Series.” *Neural Computation* 12 (6): 1371–98. . Jin, Chi, Sham M. Kakade, Akshay Krishnamurthy, and Qinghua Liu. 2020. “Sample-Efficient Reinforcement Learning of Undercomplete POMDPs.” *Advances in Neural Information Processing Systems* 33: 18530–39. Krishnamurthy, Akshay, Alekh Agarwal, and John Langford. 2016. “PAC Reinforcement Learning with Rich Observations.” *Advances in Neural Information Processing Systems* 29. Li, Lihong, Thomas J. Walsh, and Michael L. Littman. 2006. “Towards a Unified Theory of State Abstraction for MDPs.” *Proceedings of the 9th International Symposium on Artificial Intelligence and Mathematics*. Littman, Michael L., Richard S. Sutton, and Satinder Singh. 2001. “Predictive Representations of State.” *Advances in Neural Information Processing Systems* 14. Liu, Qinghua, Alan Chung, Csaba Szepesvári, and Chi Jin. 2022. “When Is Partially Observable Reinforcement Learning Not Scary?” *Proceedings of the 35th Conference on Learning Theory*, Proceedings of machine learning research, vol. 178: 5175–220. McCallum, Andrew Kachites. 1996. “Reinforcement Learning with Selective Perception and Hidden State.” PhD thesis, University of Rochester. McCallum, R. Andrew. 1995. “Instance-Based Utile Distinctions for Reinforcement Learning with Hidden State.” *Proceedings of the 12th International Conference on Machine Learning*, 387–95. . Misra, Dipendra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. 2020. “Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning.” *Proceedings of the 37th International Conference on Machine Learning*, Proceedings of machine learning research, vol. 119: 6961–71. Nixon, Anthony T. 2026. *The Myhill–Nerode Theorem for Bounded Interaction: Canonical Abstractions via Agent-Bounded Indistinguishability*. . Oliehoek, Frans A., Shimon Whiteson, and Matthijs T. J. Spaan. 2009. “Lossless Clustering of Histories in Decentralized POMDPs.” *Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems*, 577–84. . Palmer, Nick, and Paul W. Goldberg. 2007. “PAC-Learnability of Probabilistic Deterministic Finite State Automata in Terms of Variation Distance.” *Theoretical Computer Science* 387 (1): 18–31. Ron, Dana, Yoram Singer, and Naftali Tishby. 1996. “The Power of Amnesia: Learning Probabilistic Automata with Variable Memory Length.” *Machine Learning* 25 (2–3): 117–49. . Shalizi, Cosma Rohilla, and James P. Crutchfield. 2001. “Computational Mechanics: Pattern and Prediction, Structure and Simplicity.” *Journal of Statistical Physics* 104 (3–4): 817–79. . Shalizi, Cosma Rohilla, and Kristina Lisa Shalizi. 2004. “Blind Construction of Optimal Nonlinear Recursive Predictors for Discrete Sequences.” *Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence*, 504–11. . Singh, Satinder, Michael R. James, and Matthew R. Rudary. 2004. “Predictive State Representations: A New Theory for Modeling Dynamical Systems.” *Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence*, 512–19. Subramanian, Jayakumar, Amit Sinha, Raihan Seraj, and Aditya Mahajan. 2022. “Approximate Information State for Approximate Planning and Reinforcement Learning in Partially Observed Systems.” *Journal of Machine Learning Research* 23 (12): 1–83. Tsybakov, Alexandre B. 2009. *Introduction to Nonparametric Estimation*. Springer Series in Statistics. Springer. . Wasserman, Larry, and Kathryn Roeder. 2009. “High-Dimensional Variable Selection.” *Annals of Statistics* 37 (5A): 2178–201. . Weissman, Tsachy, Erik Ordentlich, Gadiel Seroussi, Sergio Verdú, and Marcelo J. Weinberger. 2003. *Inequalities for the $L_1$ Deviation of the Empirical Distribution*. HPL-2003-97R1. Hewlett-Packard Laboratories. Wolfer, Geoffrey, and Aryeh Kontorovich. 2019. “Minimax Learning of Ergodic Markov Chains.” *Proceedings of the 30th International Conference on Algorithmic Learning Theory*, Proceedings of machine learning research, vol. 98: 904–30. Zhang, Amy, Zachary C. Lipton, Luis Pineda, et al. 2019. *Learning Causal State Representations of Partially Observable Environments*. . Zhang, Amy, Rowan McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. 2021. “Learning Invariant Representations for Reinforcement Learning Without Reconstruction.” *International Conference on Learning Representations*. ## Disclosure of AI use Claude (Anthropic; Claude Code with Sonnet and Opus-class models) was used throughout this work: writing and debugging the code in the linked repository, running and checking experiments, drafting and revising the manuscript, and simulated peer review. The human author directed the research, reviewed the results, and is responsible for the content. All reported numbers are produced by committed scripts.