Finite-Sample Recovery of Predictive History Quotients from Independent POMDP Trajectories
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.