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

$$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

$$\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

$$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

$$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

$$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<r_T$ and horizon $k$ before data collection, and run selection and inference at every endpoint on the same two halves with per-endpoint failure budget $\delta/T$ (so $\alpha=\beta=\delta/(2TK_t^2)$ at endpoint $r_t$, and the count conditions of Corollary 3 hold with $\delta/T$ in place of $\delta$). With probability at least $1-\delta$, every endpoint’s quotient is recovered exactly, simultaneously. Each trajectory contributes at most one block per endpoint, no independence across endpoints is used, and the gate grows additively in $\log T$: $m^*(\varepsilon,\delta/(2TK_t^2))=\lceil(8/\varepsilon^2)((d+1)\log2+ \log(2TK_t^2/\delta))\rceil$.

Proofs are in Appendix D.

Implementation checks

The repository contains two modes. The certified mode implements the data split, fixed endpoint, one block per inference trajectory, fixed alphabet, TV threshold, Bonferroni budget, and $m^*$ gate above. A separate exploratory mode scans overlapping windows and offers chi-square G-tests or kernel tests; it is not covered by Theorems 1–2.

Table 1 reports regression checks over 20 seeds per environment, each with $\varepsilon$ set below the environment’s known analytic gap. Tiger (Cassandra et al. 1994) uses an always-listen, history-independent policy, $r=1$, $k=L=1$, 20,000 episodes, selection threshold $q=10$, and $\varepsilon=0.45$; its two context laws are separated by exactly $(2a-1)^2=0.49$ at listen accuracy $a=0.85$. The 8-cycle uses its single action, $r=0$, $k=L=1$, 8,000 episodes, $q=100$, and $\varepsilon=0.5$ against an analytic gap of $0.7225$. The noisy depth-2 chain exercises the merge path: at $r=0$ and $k=1$ its three length-one contexts induce exactly two continuation laws (two contexts share one row of the transition table verbatim), so correct recovery requires a SAME verdict; it uses 16,000 episodes, $q=30$, and $\varepsilon=0.5$ against a gap of $0.7524$. All runs use a 50/50 split and $\delta=\beta=0.05$. Recovery is exact on all $3\times20$ runs with no abstention; the harness fails if any environment’s $\varepsilon$ exceeds its recorded analytic gap.

Implementation checks for the certified path, 20 seeds per row. “recovered” is the class count, identical across seeds (the checker fails otherwise); “Und.” is the maximum abstaining pair fraction over seeds. Class counts alone do not show that the partitions are right; Appendix G lists the full transition and observation specification of every environment and reports, for every seed, the recovered partition and its pair-level error against the exact truth (Table 2).

The power gate binding on the noisy 8-cycle (10 seeds per budget). With $K=8$ contexts, $d=8$, and $\alpha_0=\delta/(2K^2)$, the gate requires $m^*=451$ inference samples per context; per-context counts at budget $N$ concentrate near $N/16$, so abstention collapses from total to zero across $N\in[6{,}500,\,8{,}000]$. At every budget and seed the estimator reports all 8 classes—degradation is pure abstention, never an incorrect merge. The main-table budget $N=8{,}000$ sits just above this transition.

Figure 1 exercises the regime the abstention machinery exists for: a budget sweep on the 8-cycle in which the $m^*$ gate binds sharply. Across all 80 sweep runs no class pair is ever merged incorrectly; refusal is the only failure mode observed, as designed.

The same budget sweep on the noisy depth-2 chain at $r=0$, whose quotient genuinely merges two of its three contexts (10 seeds per budget, $\varepsilon=0.5$ against gap $0.7524$, $m^*=278$). Below the gate transition the required SAME verdict abstains and the report over-splits to three classes; above it the correct two classes are reported. The transition is bracketed in $N\in[2{,}000,\,2{,}400]$, matching the prediction $N\approx2{,}050$ from the gate and the per-context masses. Across all 80 runs no pair is merged incorrectly.

The 8-cycle’s quotient has no equal pair, so its sweep cannot show what starvation does to a merge. Figure 2 repeats the sweep on the noisy depth-2 chain, where correct recovery requires a SAME verdict: an abstaining gate withholds exactly that verdict, so degradation appears as over-splitting — three reported classes instead of two — and never as an incorrect merge. The two sweeps together exhibit both directions of the refusal semantics.

Nested contexts at $L=2$.

Every row of Table 1 has $L=1$, where no context is a suffix of another and the one-count conditioning of Lemma 7 is never stressed. A separate check runs the noisy depth-2 chain at endpoint $r=1$ with $L=2$: twelve eligible contexts (three of length one, each the suffix of three length-two extensions), an analytic quotient of five classes, and minimal between-class TV $2/7\approx0.2857$ — attained by the nested pair $(0,)$ vs. $(0,0)$, so the binding decision is one a black-box two-sample tester could not certify (Corollary 5). With $\varepsilon=0.28$, $K=12$, $d=3$, and $m^*=1{,}167$, the rarest context (mass $\approx0.022$) needs the bulk of the budget: $140{,}000$ episodes yield roughly $1{,}500$ inference blocks for it. Recovery of the five-class nested partition is exact on all 20 seeds with zero abstention.

Head-to-head: pooling positions changes the estimand.

A binary chain whose transition kernel flips with the parity of the episode position makes the motivating failure concrete. At $r=0$ its two length-one contexts have continuation laws $\mathrm{Ber}(0.9)$ and $\mathrm{Ber}(0.1)$ — distinct classes at TV $0.8$ — while every observation is marginally uniform at every position, so the position-pooled continuation law after either context is exactly $\mathrm{Ber}(0.5)$. The certified arm uses 4,000 trajectories per seed, selection threshold $q=10$, and $\varepsilon=0.75$ against the analytic gap $0.8$; the exploratory arm scans overlapping windows on 400 trajectories of length up to 40, giving it several times more raw windows than the certified arm has blocks — an imbalance favoring the exploratory arm. On 10 seeds each, the certified path at $r=0$ recovers the two classes with no abstentions in 10/10 runs, while the exploratory overlapping-window mode merges the pair in 10/10 runs; because the pooled law is exactly $\mathrm{Ber}(0.5)$, that merge is budget-independent. The exploratory merge is not a calibration accident and does not vanish with more data: the scan consistently estimates the pooled law, a different estimand under which the merge is correct. This is precisely the sense in which an unstated sampling protocol turns a plausible clustering into an estimator of a different estimand than the one intended (Section 1). The exploratory arm is our own implementation of representative overlapping-window practice, labeled as such: we are not aware of a published implementation that instantiates the episode-position estimand (fixed endpoint, termination conditioning, one block per trajectory), so the comparison available on this target is against practice, not against a published system.

Two endpoints at once.

The position-flip chain also instantiates Corollary 6 at $T=2$: its parity-flipped kernel gives two endpoints $r\in\{0,1\}$ with analytic gap $0.8$ at each. One shared pool of $4{,}000$ trajectories per seed is processed at both endpoints on the same two halves, with the family budget split as $\delta/2$ per endpoint ($\varepsilon=0.75$, $m^*=112$). Both endpoint quotients are recovered exactly and simultaneously on 10/10 seeds with zero abstention — long trajectories reused across endpoints at union-bound cost, no mixing argument.

A nondegenerate stochastic policy.

Every row above fixes a degenerate policy (Tiger’s always-listen, the cycles’ single action). Rerunning Tiger at $r=1$, $k=1$ under the memoryless stochastic policy (listen $0.8$, open either door $0.1$ each) exercises the closed-loop framing. The timeline matters. The reset emits an uninformative $O_0$; action $A_0$ emits $O_1$, the context; action $A_1$ emits $O_2$, the continuation. A door opening ends the episode, but the uniform terminal draw it emits is recorded as that step’s observation. Hence the trajectory reaches $r+k=2$ if and only if $A_0=\mathrm{listen}$ (probability $p_\ell=0.8$); if $A_0$ opens a door, $O_1$ is recorded but no $O_2$ exists and the trajectory contributes no block. $A_1$ is unrestricted: with probability $p_\ell$ it is a listen and $O_2$ is the accuracy-$a$ draw ($a=0.85$), with probability $1-p_\ell$ it is a door opening and the recorded $O_2$ is uniform. Since the tiger state is fixed within the episode and $O_0$ is uninformative, conditioning on $\{O_1=\text{left},\ \text{reach}\}$ multiplies the prior $1/2$ by $p_\ell\,a$ for tiger-left and $p_\ell(1-a)$ for tiger-right, so

$$P_{\text{left}}(O_2{=}\text{left}) = p_\ell\bigl(a^2+(1-a)^2\bigr)+\tfrac{1-p_\ell}{2}=0.696,\qquad P_{\text{right}}(O_2{=}\text{left}) = p_\ell\,2a(1-a)+\tfrac{1-p_\ell}{2}=0.304 ,$$

and the survival factor $p_\ell$ from $A_0$ cancels, because it multiplies numerator and normalizer alike (each context has mass $\mu_h=p_\ell/2=0.4$). The gap is therefore $\mathop{\mathrm{TV}}=p_\ell\,(2a-1)^2=0.8\cdot0.49=0.392$: the always-listen gap shrunk by the probability that the second action $A_1$ is informative, not by the reaching event. Three computations agree on these numbers: this closed form, an exhaustive enumeration of the latent chain, and a $400{,}000$-episode Monte Carlo through the collection code (reach fraction $0.8006$; $0.698$ and $0.305$ for the two conditional laws; $\mathop{\mathrm{TV}}=0.393$; check_tiger_stochastic.py). With $\varepsilon=0.35$ (checked at runtime against the enumerated gap) and $8{,}000$ episodes, recovery against the enumerated ground truth is exact on 20/20 seeds with zero abstention, with $1{,}548$–$1{,}619$ inference blocks in the rarer context (per seed) against $m^*=468$. (Writing this check exposed a seeding defect in the collection routine: the policy generator shared its seed with the environment’s, coupling action draws to Tiger’s noise, so that the sampled stochastic-policy process had conditional laws $0.78$ and $0.22$ rather than the enumerated ones. The generators are now independent, a unit test pins the conditional law, and this check and its artifacts were regenerated after the fix; the other rows use a single action or a constant policy, whose actions cannot interact with the environment’s noise.)

A data-driven $\varepsilon$: a diagnostic, not a certificate.

Every configuration so far sets $\varepsilon$ below a gap known by construction. This last positive check leaves that regime, but it carries no certificate, and we do not count it as evidence for Theorem 2. The environment is a randomly parameterized three-state HMM whose instance was selected by a rule fixed before any estimator output (first Dirichlet draw with brute-force minimum pairwise TV at least $0.15$; the draw used has true minimum TV $0.3872$, computed only post hoc from the drawn matrices), and $\varepsilon$ is not supplied analytically: on the selection half only, the pairwise empirical-TV spectrum is sorted with $0$ prepended, and $\widehat\varepsilon$ is the midpoint of the largest gap whose lower edge lies below $0.5$, with an abstain-on-all-pairs fallback if that gap is smaller than $0.1$. Because $\widehat\varepsilon$ and the candidate set depend on the selection half alone, the inference half is independent of them, so conditionally on the selection half the pair test is exactly the fixed-$\varepsilon$ test of Theorem 1 run at $\varepsilon=\widehat\varepsilon$. The theorem’s conclusion, however, needs $\widehat\varepsilon$ to satisfy the gap model Eq. (2), that is, $\widehat\varepsilon\le$ the true minimum TV (and distinct classes at least $\widehat\varepsilon$ apart), and nothing in the paper bounds the probability that the recipe overshoots: the spectrum rule is a heuristic, and a certification argument would need a selection-half lower confidence bound on the minimum gap, which we do not provide. The check that $\widehat\varepsilon\le0.3872$ uses the true minimum TV, which a user would not have; it is a post hoc diagnostic of this one instance, not something the procedure can verify. What the run shows is limited accordingly: over 20 seeds at $30{,}000$ episodes no fallback fired, $\widehat\varepsilon\in[0.189,0.199]$ (all below the post hoc $0.3872$, so none violated the gap model here), and the three-class truth was recovered exactly on 20/20 seeds with zero abstention. We make no claim about how often the recipe is valid on other instances.

Misspecification probe: the regime outside the gap model.

The gap model is an assumption, and Section 4’s refusal semantics do not survive its failure; one check realizes that failure deliberately rather than leaving it hypothetical. A three-context chain is engineered with one pair at true TV $0.1$ and the others at $0.8$, and the certified machinery is run verbatim with $\varepsilon=0.5$ — above the sub-gap pair’s true distance, violating Eq. (2). On 10/10 seeds the sub-gap pair is silently merged under a confident SAME verdict: no abstention (the $m^*$ gate is comfortably passed), and no near-threshold flag (the per-pair artifact records every SAME edge’s TV margin to the threshold; the rule margin $<\varepsilon/8$ never fires, mean margin $0.14$). The separated pairs are all classified correctly; the report deletes one class. The honest price of resolving the engineered pair is stated by the theory itself: $\varepsilon=0.1$ requires $m^*=6{,}927$ blocks per context, roughly $42{,}000$ episodes at this layout versus the $2{,}600$ used. The probe’s artifacts are marked uncertified and are excluded from every certified table; what they exhibit is the boundary of the guarantee, not a result inside it.

All code, results, and the paper source are in the public repository https://github.com/npow/quotient-learning-papers, 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

$$\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$,

$$\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,

$$\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

$$\mathbb P\{m_h<M\mu_{\min}/2\} \le \exp(-M\mu_{\min}/8).$$

The first two terms of Eq. (5) make half the mean at least $q$ on the selection half and at least $m^*$ on the inference half. Union bounding Eq. (7) over $K$ contexts and both halves yields at most $\delta/2$ by the third term. On the complementary count event, all contexts are selected and all pairs are tested. Theorem 2 contributes at most the remaining $\delta/2$. Expanding Eq. (3) proves the order statement. 0◻

Lower bound

Let a context label $H\in\{0,1,\bot\}$ equal $1$ with probability $\mu$, $0$ with probability $\mu$, and $\bot$ otherwise, where $\bot$ denotes a trajectory that terminates before $r+k$ and therefore contributes no block (explicitly permitted by the data contract). The candidate universe is thus exactly $\{0,1\}$ with $\mu_h=\mu$ for both contexts, so the per-context visitation floor and the gap condition of Corollary 3 hold for every $\mu\le1/2$. Under model $M_0$, let the binary continuation be Bernoulli$(1/2)$ for both non-null contexts. Under $M_1$, keep the law after $H=0$ unchanged and use Bernoulli$(1/2+\varepsilon)$ after $H=1$. Thus $M_0$ has one class on $\{0,1\}$ and $M_1$ has two classes at TV separation $\varepsilon$.

For $\varepsilon\le1/4$, using $\mathrm{KL}\le\chi^2$,

$$\mathrm{KL}(M_1\|M_0) =\mu\,\mathrm{KL}(\mathrm{Ber}(1/2+\varepsilon)\|\mathrm{Ber}(1/2)) \le 4\mu\varepsilon^2.$$

For $N$ iid trajectories, tensorization and Pinsker’s inequality give

$$\mathop{\mathrm{TV}}(M_1^N,M_0^N)\le\sqrt{2N\mu\varepsilon^2}.$$

If $N\le1/(32\mu\varepsilon^2)$, this is at most $1/4$. Le Cam’s inequality then makes the sum of the two testing errors at least $3/4$, so their maximum is at least $3/8$. Any exact partition estimator induces such a test, proving Proposition 4.

Tester substitution and multi-endpoint proofs

Proof of Corollary 5.

Fix non-nested contexts $h,g$ at the shared endpoint. Contexts of equal length are distinct strings, and for lengths $\ell<\ell'$ a trajectory matching the longer context matches the shorter one iff the shorter is its suffix, which non-nestedness excludes; hence each trajectory contributes a block to at most one of $h,g$, and the per-trajectory type $T_i\in\{h,g,\text{neither}\}$ is well defined. Conditional on the type vector $(T_1,\dots,T_M)$, the blocks contributing to $h$ are iid $P_h$, those contributing to $g$ are iid $P_g$, and the two groups are independent, coming from disjoint sets of independent trajectories. The count pair $(m_h,m_g)$ is a function of the type vector alone, so the same description holds conditional on $\{m_h\ge m,\ m_g\ge m\}$; discarding blocks beyond the first $m$ of each group (a deterministic function of the type vector) hands the tester exactly the sample its guarantee assumes. With $m=n(d,\varepsilon,\delta/(2K^2))$, each error-with-verdict event has probability at most $\delta/(2K^2)$; union-bounding over the at most $K(K-1)/2$ pairs keeps the total test-error probability within the $\delta/4$ the recovery proof has to spare, and nested pairs keep the plug-in bound of Theorem 1; the recovery argument is otherwise unchanged.

For the amplification, run the tester at constant error $1/3$ on $\kappa=\lceil18\log(1/\gamma)\rceil$ disjoint batches of its constant-error sample size and take the majority verdict; by Hoeffding’s inequality the majority errs with probability at most $\exp(-2\kappa(1/2-1/3)^2)=\exp(-\kappa/18)\le\gamma$, at total cost $O\bigl((d^{2/3}/\varepsilon^{4/3}+d^{1/2}/\varepsilon^{2})\log(1/\gamma)\bigr)$.

The nested exclusion is forced, not chosen: if $h$ is a suffix of $g$, every trajectory contributing to $g$ contributes to $h$, and the block depends only on the endpoint, so $g$’s sample is verbatim a subset of $h$’s. A two-sample tester’s guarantee presumes independent samples from the two laws; here the samples overlap, and conditioning on both counts jointly biases the contributing blocks (Appendix A). Lemma 7 conditions on one count at a time, which is exactly the property a black-box tester does not offer. Separately, because $n(d,\varepsilon,\gamma)$ is available only up to unspecified constants, the substituted gate cannot be evaluated as a closed-form abstention rule; this, not any union-bound obstacle, is why the implementation retains the plug-in test.

Proof of Corollary 6.

Fix endpoint $r_t$. The selection half, inference half, candidate set, counts, and verdicts at $r_t$ are exactly the objects of Theorem 2 and Corollary 3 applied at that endpoint; no step of those proofs refers to any other endpoint, and within one endpoint the per-trajectory contribution indicators remain iid across trajectories. Instantiating Corollary 3 with failure budget $\delta/T$ bounds the probability that endpoint $r_t$ fails to return its exact quotient by $\delta/T$; a union bound over the $T$ endpoints bounds the probability that any endpoint fails by $\delta$. Dependence between blocks of one trajectory at different endpoints is never used — the union bound needs no independence. Substituting $\alpha=\beta=\delta/(2TK_t^2)$ into Eq. (3) gives the stated gate. 0◻

Scope, actions, and discretization

Proposition 8 (Policy dependence). Equality of latent posteriors at two histories does not by itself imply equal closed-loop future laws under a history-dependent policy. Equality does follow if the two histories have the same latent posterior and the policy’s future action kernels agree after every paired future observation sequence.

Proof. For the counterexample, use one latent state, two histories, and a policy that chooses different deterministic actions after them; let the next observation copy the action. The posterior is identical but the next-observation laws are disjoint. Under equality of future action kernels, expand the joint future law as the common posterior times identical alternating policy and POMDP kernels and marginalize the latent path. ◻

For action-aware continuations $((A_r,O_{r+1}),\ldots,(A_{r+k-1},O_{r+k}))$, the full discrete alphabet is $(\mathcal A\times\mathcal O)^k$ and therefore has $|\mathcal A|^k|\mathcal O|^k$ elements. Structural zeros may reduce the known support, but the support must be supplied independently of the tested counts.

Proposition 9 (Window-measurable return preservation). Let $\rho:\mathcal C\to\mathbb R$ be any function of the $k$-step continuation and define the window return $G=\rho(C)$ — for instance any discounted sum $\sum_{j=1}^{k}\gamma^{j}g(O_{r+j})$ of per-step rewards that are functions of the observation. If $P_h=P_g$, then the conditional law of $G$ given $\{H=h,\ Z$ reaches $r+k\}$ equals its conditional law given $\{H=g,\ Z$ reaches $r+k\}$; hence every functional of that law (mean, variance, quantiles, conditional value at risk) is identical across merged contexts. For action-aware continuations the same statement holds with $\rho$ defined on $(\mathcal A\times\mathcal O)^k$.

Proof. $G$ is the pushforward of $C$ under $\rho$, and equal laws have equal pushforwards; the action-aware case is identical with $C\in(\mathcal A\times\mathcal O)^k$. ◻

The proposition is exactly as strong as the estimand and no stronger: no preservation is claimed for rewards that depend on the latent state, on observations beyond position $r+k$, or on the policy’s internal state except through recorded actions. It gives the recovered quotient a downstream currency — merged contexts are exchangeable for evaluating any window-measurable return under the behavior policy — while planning-loss guarantees in the sense of approximate information states (Subramanian et al. 2022) remain out of scope.

Induced state map for nested contexts.

The quotient is an equivalence over context strings; a realized history at endpoint $r$ matches every eligible suffix length simultaneously. Following prediction-suffix-tree leaf semantics (Ron et al. 1996), define the induced state of a history to be the class of its longest eligible context in $\mathcal H$. The map is well defined: the longest matching suffix is unique, and its class under the recovered partition is a function of the history alone. A history none of whose eligible suffixes lies in the selected $\mathcal H$ receives no assignment — the map abstains, consistent with the estimator’s refusal semantics. (Under the count event of Corollary 3, $\mathcal H$ is the full eligible universe and the map is total.) Distinct nested contexts may land in different classes; the induced map then simply prefers the most specific one, exactly as a suffix tree routes a sequence to a leaf. No claim is made that the induced map is measurable with respect to a coarser context set than $\mathcal H$ itself.

What continuation law the routed class carries.

The partition equates the laws $P_h$ of Eq. (1), which condition on the event $E_h=\{H_{\ell(h)}=h\}$ that the length-$\ell(h)$ suffix equals $h$, whatever the longer suffix is. Routing by the longest context restricts that event: $h$ receives only the histories in $R_h=E_h\setminus\bigcup_{g\in G_h}E_g$, where $G_h\subseteq\mathcal H$ is the set of contexts having $h$ as a proper suffix. So the law of the continuation given “routed to $h$ and reaching $r+k$”, call it $Q_h$, need not equal $P_h$. What is guaranteed is the exact decomposition below.

Proposition 10 (Routed laws). *Write $\lambda_g=\mathbb P(\text{routed to }g,\ Z\text{ reaches }r+k)$. Convention: $Q_g$ is defined only when $\lambda_g>0$, 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$,

$$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 https://github.com/npow/quotient-learning-papers, 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)$,

$$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.

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.

References

1. Balle, Borja, Jorge Castro, and Ricard Gavaldà. 2013. “Learning Probabilistic Automata: A Study in State Distinguishability.” Theoretical Computer Science 473: 46–60.
2. 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. https://doi.org/10.1109/SFCS.2000.892113.
3. 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. https://doi.org/10.15607/RSS.2010.VI.036.
4. Bühlmann, Peter, and Abraham J. Wyner. 1999. “Variable Length Markov Chains.” Annals of Statistics 27 (2): 480–513.
5. 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.
6. 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.
7. 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.
8. 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.
9. 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.
10. 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. https://doi.org/10.1137/1.9781611973402.88.
11. Chow, C. K. 1970. “On Optimum Recognition Error and Reject Tradeoff.” IEEE Transactions on Information Theory 16 (1): 41–46. https://doi.org/10.1109/TIT.1970.1054406.
12. Clark, Alexander, and Franck Thollard. 2004. “PAC-Learnability of Probabilistic Deterministic Finite State Automata.” Journal of Machine Learning Research 5: 473–97.
13. Cox, D. R. 1975. “A Note on Data-Splitting for the Evaluation of Significance Levels.” Biometrika 62 (2): 441–44. https://doi.org/10.1093/biomet/62.2.441.
14. Crutchfield, James P., and Karl Young. 1989. “Inferring Statistical Complexity.” Physical Review Letters 63 (2): 105–8. https://doi.org/10.1103/PhysRevLett.63.105.
15. 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.
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.
17. 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.
18. 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.
19. El-Yaniv, Ran, and Yair Wiener. 2010. “On the Foundations of Noise-Free Selective Classification.” Journal of Machine Learning Research 11: 1605–41.
20. 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.
21. Givan, Robert, Thomas Dean, and Matthew Greig. 2003. “Equivalence Notions and Model Minimization in Markov Decision Processes.” Artificial Intelligence 147 (1–2): 163–223. https://doi.org/10.1016/S0004-3702(02)00376-4.
22. 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.
23. 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. https://proceedings.mlr.press/v51/guo16b.html.
24. 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.
25. 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. https://doi.org/10.1016/j.jcss.2011.12.025.
26. Jaeger, Herbert. 2000. “Observable Operator Models for Discrete Stochastic Time Series.” Neural Computation 12 (6): 1371–98. https://doi.org/10.1162/089976600300015411.
27. 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.
28. Krishnamurthy, Akshay, Alekh Agarwal, and John Langford. 2016. “PAC Reinforcement Learning with Rich Observations.” Advances in Neural Information Processing Systems 29.
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.
30. Littman, Michael L., Richard S. Sutton, and Satinder Singh. 2001. “Predictive Representations of State.” Advances in Neural Information Processing Systems 14.
31. 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.
32. McCallum, Andrew Kachites. 1996. “Reinforcement Learning with Selective Perception and Hidden State.” PhD thesis, University of Rochester.
33. 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. https://doi.org/10.1016/B978-1-55860-377-6.50055-4.
34. 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.
35. Nixon, Anthony T. 2026. The Myhill–Nerode Theorem for Bounded Interaction: Canonical Abstractions via Agent-Bounded Indistinguishability. https://arxiv.org/abs/2603.21399.
36. 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. https://www.ifaamas.org/Proceedings/aamas2009/pdf/01_Full%20Papers/09_49_FP_0366.pdf.
37. 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.
38. 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. https://doi.org/10.1007/BF00114008.
39. 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. https://doi.org/10.1023/A:1010388907793.
40. 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. https://arxiv.org/abs/cs/0406011.
41. 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.
42. 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.
43. Tsybakov, Alexandre B. 2009. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer. https://doi.org/10.1007/b13794.
44. Wasserman, Larry, and Kathryn Roeder. 2009. “High-Dimensional Variable Selection.” Annals of Statistics 37 (5A): 2178–201. https://doi.org/10.1214/08-AOS646.
45. 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.
46. 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.
47. Zhang, Amy, Zachary C. Lipton, Luis Pineda, et al. 2019. Learning Causal State Representations of Partially Observable Environments. https://arxiv.org/abs/1906.10437.
48. 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.