Paper deep dive
The Myhill-Nerode Theorem for Bounded Interaction: Canonical Abstractions via Agent-Bounded Indistinguishability
Anthony T. Nixon
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 93%
Last extracted: 3/26/2026, 2:27:51 AM
Summary
The paper introduces a bounded-interaction analogue of the Myhill-Nerode theorem for finite POMDPs. It defines a canonical, minimal, and unique quotient POMDP induced by a fixed family of finite-state controller (FSC) probes. The framework uses a closed-loop Wasserstein pseudometric to measure indistinguishability between observation histories, providing exact decision sufficiency for clock-aware probes and an observation-Lipschitz approximation bound for latent-state rewards.
Entities (6)
Relation Signals (3)
Finite-State Controller → induces → Wasserstein pseudometric
confidence 95% · A fixed probe family of finite-state controllers induces a closed-loop Wasserstein pseudometric on observation histories
Wasserstein pseudometric → defines → Canonical Quotient
confidence 90% · The resulting quotient is canonical, minimal, and unique—a bounded-interaction analogue of the Myhill–Nerode theorem.
Canonical Quotient → preserves → Observation Laws
confidence 90% · the probe-exact quotient is the unique minimal abstraction preserving all future observation laws visible to that family.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Any capacity-limited observer induces a canonical quotient on its environment: two situations that no bounded agent can distinguish are, for that agent, the same. We formalise this for finite POMDPs. A fixed probe family of finite-state controllers induces a closed-loop Wasserstein pseudometric on observation histories and a probe-exact quotient merging histories that no controller in the family can distinguish. The quotient is canonical, minimal, and unique-a bounded-interaction analogue of the Myhill-Nerode theorem. For clock-aware probes, it is exactly decision-sufficient for objectives that depend only on the agent's observations and actions; for latent-state rewards, we use an observation-Lipschitz approximation bound. The main theorem object is the clock-aware quotient; scalable deterministic-stationary experiments study a tractable coarsening with gap measured on small exact cases and explored empirically at larger scale. We validate theorem-level claims on Tiger and GridWorld. We also report operational case studies on Tiger, GridWorld, and RockSample as exploratory diagnostics of approximation behavior and runtime, not as theorem-facing evidence when no exact cross-family certificate is available; heavier stress tests are archived in the appendix and artifact package.
Tags
Links
- Source: https://arxiv.org/abs/2603.21399v1
- Canonical: https://arxiv.org/abs/2603.21399v1
Trouble viewing inline? Open PDF directly →
Full Text
162,620 characters extracted from source content.
Expand or collapse full text
The Myhill–Nerode Theorem for Bounded Interaction: Canonical Abstractions via Agent-Bounded Indistinguishability Anthony T Nixon DefSig. Correspondence: anthony@defsig.com. Abstract Any capacity-limited observer induces a canonical quotient on its environment: two situations that no bounded agent can distinguish are, for that agent, the same. We formalise this principle for finite POMDPs. A fixed probe family of finite-state controllers induces a closed-loop Wasserstein pseudometric on observation histories and a probe-exact quotient that merges histories no controller in the family can distinguish. The resulting quotient is canonical, minimal, and unique—a bounded-interaction analogue of the Myhill–Nerode theorem. For clock-aware probes, the quotient is exactly decision-sufficient for agent-accessible objectives measurable with respect to the joint observation-action trajectory; for latent-state rewards, we instead rely on the observation-Lipschitz approximation bound. The framework also suggests a reusable discrete template for a few neighboring finite or discretised settings; we record those illustrative analogies in the appendix rather than treating them as central contributions of the paper. The exact theorem object is the clock-aware quotient; the scalable deterministic-stationary experiments study a tractable coarsening whose gap is quantified on small exact cases and treated empirically at larger scale. We validate the theorem-level claims on Tiger and GridWorld and report operational case studies of the tractable coarsening on Tiger, GridWorld, and RockSample; these uncertified case studies are included as exploratory diagnostics of approximation behaviour and runtime, not as part of the paper’s theorem-facing claim set once the exact cross-family certificate is unavailable. Heavier operational stress tests are archived separately in the appendix and artifact package. 1 Introduction When are two environments “the same”? The answer depends on who is asking. Two situations that no bounded observer can distinguish are, for that observer, the same; the right abstraction is therefore matched to the observer’s capacity. This paper makes this principle precise for the finite discrete case and shows that the resulting quotient is canonical, minimal, and unique—a bounded-interaction analogue of the Myhill–Nerode theorem from formal language theory. We use the word analogue deliberately: the classical suffix-test theorem is the motivating template, but our object lives on histories under closed-loop bounded control rather than as a literal restatement of the DFA setting. The analogy is structural—canonical minimal quotient under a finite equivalence relation—rather than algorithmic: unlike the classical DFA result, we do not claim a polynomial-time exact construction algorithm, and exact computation and scalable approximation are handled separately through the operational toolkit developed later in the paper. Planning under partial observability is hard because both the history tree and the belief process explode with horizon. A natural response is to ask a bounded question: which distinctions in the environment matter to a bounded agent? If two histories induce the same closed-loop future behavior for every controller in a bounded probe class, then no controller in that class can exploit the distinction. The right abstraction target is therefore not the full belief space, but the quotient induced by bounded-agent indistinguishability. In classical Myhill–Nerode terms, two prefixes are merged when no admissible future continuation can separate them; here the continuation is closed-loop and restricted to what a bounded controller can actually do. This point of view yields a canonical-form result. For a fixed probe family, the probe-exact quotient (exact for the stated probe family) is the unique minimal abstraction preserving all future observation laws visible to that family. We emphasize the use case that makes this object compelling: for objectives measurable with respect to what the bounded agent actually sees and does, the clock-aware exact quotient is decision-sufficient, not merely compressive. For latent-state rewards, the theory falls back to the approximate value-loss bound rather than exact sufficiency, and we make that limitation explicit in the abstract, experiments, and discussion. This paper also makes a clean separation between theory and computation. The theorem-level results are stated for the clock-aware controller class Πm,Tclk ^clk_m,T, where stage indexing prevents parameter reuse across time and therefore restores deterministic witness sufficiency. The experiments, by contrast, use the tractable operational family Πm,Top=Πm,Tdet,stat ^op_m,T= ^det,stat_m,T unless stated otherwise. The operational quotient Qm,TopQ^op_m,T is a coarsening of the theorem object Qm,TclkQ^clk_m,T; Section 7 first quantifies that gap on small clock-aware exact cases and then reports operational case studies of Qm,TopQ^op_m,T at larger scales. When that cross-family gap is measured on a tractable exact case, Theorem 4.12 turns it into an additive value-transfer certificate. When no such certificate is available, the larger tables are included only as empirical evidence about the tractable surrogate Qm,TopQ^op_m,T, not as direct empirical validation of the full clock-aware theorem object. This paper makes the following contributions: (i) A probe-family-parametrized closed-loop pseudometric on finite POMDPs, together with an observation-Lipschitz value-loss bound for partition-based approximate quotients (§3; Theorem 3.6). (i) A bounded-interaction Myhill–Nerode theorem: for a fixed probe family, the probe-exact quotient is canonical, minimal, and unique up to isomorphism (§4; Theorem 4.4). (i) A clock-aware exact sufficiency theorem: for every objective in obsG_obs measurable with respect to the joint observation-action trajectory, the clock-aware quotient Qm,TclkQ^clk_m,T preserves expected return exactly and therefore preserves optimal value over Πm,Tclk ^clk_m,T. (iv) A witness boundary: deterministic sufficiency holds for clock-aware bounded controllers, while deterministic stationary controllers are shown explicitly to be insufficient in general. (v) A formal bridge from theorem to computation on measured exact cases: if one probe family is contained in another, its quotient is a coarsening, and a measured cross-family probe gap yields an additive value-transfer bound on that same bounded regime. In particular, Qm,TopQ^op_m,T is a tractable coarsening of Qm,TclkQ^clk_m,T, with value loss controlled by ε+δclk + _clk only when the clock-aware/operational gap δclk _clk is explicitly measured for the benchmark and horizon under discussion. (vi) A companion operational toolkit built from controller-subset certificates, sampling-based probe estimation, layered horizon decomposition, and observation coarsening, together with exact small-case alignment for Qm,TclkQ^clk_m,T (Section 7.2; Table 3) and exact-for-family deterministic-stationary certificates on small benchmarks (Table 5). These certified strata participate in the paper’s claim-evidence chain. Additional medium-scale case studies on GridWorld, random POMDPs, and RockSample are reported later as exploratory diagnostics of the tractable surrogate Qm,TopQ^op_m,T, not as further theorem-facing contribution claims. Heavier scale-up and long-horizon stress tests are reported separately as appendix-only archival evidence. Accordingly, whenever we use the phrase exact decision sufficiency below, it refers only to objectives in obsG_obs measurable on the joint observation-action trajectory; latent-state rewards are covered only by the approximate observation-Lipschitz bound. Likewise, whenever we invoke the cross-family transfer guarantee below, it refers only to the tractable exact cases where the corresponding δclk _clk is explicitly reported; no larger operational scaling row is claimed to inherit that certificate unless the matching gap measurement is shown for that same bounded regime. The paper’s theorem-facing evidence set is therefore exhausted by the theorem statements themselves, the clock-aware exact tables, and the deterministic-stationary rows carrying an explicit subset or cross-family certificate; larger uncertified operational tables are included only as exploratory diagnostics of Qm,TopQ^op_m,T. At the witness boundary, deterministic sufficiency holds for the clock-aware FSC class of Theorem 4.9, but Proposition 4.10 shows that this cannot be extended to stationary looping FSCs in general. The framework’s parametrisation by (m,T,δO)(m,T, _O) makes the observer-capacity mismatch explicit without requiring a commitment to any broader operational reduction outside the finite POMDP setting. Proof roadmap. The main proof structure is short. The pseudometric theorem is the Wasserstein triangle inequality plus maximisation over bounded closed-loop controllers. The value bound is a per-stage observation-Lipschitz transfer summed over horizon. The quotient theorem then combines right-invariance of history equivalence, induction on preserved observation laws, and a universal-object argument for minimality and uniqueness. The same ingredients are reused in the approximate and layered variants later in the paper. Related work. State abstraction and bisimulation. State abstraction in MDPs has a rich theory: Li et al. [29] provide a taxonomy, Abel et al. [1] introduce agent-aware abstraction, and Abel [2] offers a comprehensive account grounded in category theory. Bisimulation metrics [17, 18] provide a continuous alternative to exact equivalence; Calo et al. [8] recently showed these are optimal-transport distances, and Kemertas and Aumentado-Armstrong [27] extended metric learning to robust settings. Deep bisimulation methods [20, 50, 12] scale these ideas to high dimensions via learned encoders; our model-based framework provides a complementary theoretical target (Appendix C). POMDP equivalences and predictive representations. For POMDPs, Castro [10] formalized exact bisimulation, and Dean and Givan [14] introduced homogeneous partitions. Two nearby traditions are worth separating. Restricting probes to open-loop action strings or constant-action FSCs recovers a notion approaching Castro-style conditional observation-sequence equivalence; probabilistic testing equivalence in the Larsen–Skou lineage [28] is close in spirit, but the tests there are external experiments on labelled stochastic processes, whereas ours are embodied as finite-memory controllers interacting with a controlled partially observable environment. The new ingredient is a closed-loop bounded-observer equivalence that is explicitly parameterized by controller capacity and materialized as a quotient POMDP. Predictive state representations, observable operator models, and their controlled or spectral variants [30, 25, 7, 4] define state through predictions of future observations, but through open-loop tests or Hankel-style predictive structure rather than closed-loop, bounded-capacity FSC probes. Our quotient is a closed-loop bounded-observer analogue of that predictive-state philosophy, with controller capacity (m,T,δO)(m,T, _O) replacing predictive rank as the organizing parameter. The comparison with controlled PSRs—which already incorporate actions—is structural rather than order-theoretic: PSR-style low-rank structure captures linear predictive redundancy, while our anchor-rank condition captures the stronger max-preserving redundancy needed for quotient construction (Appendix B). Positioning. FSCs as policy representations are due to Poupart and Boutilier, Hansen, and Amato et al. [41, 22, 3]; we repurpose them as probes determining abstraction granularity. Our indistinguishability criterion is related in spirit to comparison-of-experiments ideas [6, 49], but the signal structure is closed-loop and policy-dependent. Relative to exact POMDP bisimulation, the object here is history-based and explicitly parametrised by controller capacity (m,T,δO)(m,T, _O); relative to agent-aware abstraction, it yields a canonical minimal quotient preserving the full closed-loop observation law rather than a single value function. Conceptually, the pseudometric is a history-space bounded-agent analogue of Wasserstein bisimulation metrics: the lineage is direct, but DTΠD_T compares finite-horizon observation-sequence laws and restricts the supremum to a prescribed bounded controller family. The novelty claim is the bounded-family quotient and its exact/approximate sufficiency consequences, not the mere use of Wasserstein distance. Extended discussion and additional references are in Appendix C. (a) Universal schemaHiddenStateObservationChannelBounded Observer(m,T,δO)(m,T, _O)CanonicalQuotient(b) POMDP instantiationHistoriesO≤TO^≤ TFSC ProbesΠm,T _m,T1W_1 DistanceMatrixε -ClusteringQuotientPOMDPmax over π linkageThm 3.6: |Vπ−V~π|≤LRTε|V^π- V^π|≤ L_RT Figure 1: (a) Any system with hidden state, an observation channel, and a bounded observer (m,T,δO)(m,T, _O) admits a canonical quotient—a minimal equivalence over situations the observer cannot distinguish. (b) The POMDP instantiation: observation histories are probed by all bounded FSCs; pairwise 1W_1 distances (maximised over policies) are clustered; the quotient POMDP preserves all observation laws with certified value loss. 2 Preliminaries Definition 2.1 (Finite POMDP). A finite POMDP is a tuple M=⟨S,A,O,P,Z,R,b0⟩M= S,A,O,P,Z,R,b_0 where S is a finite state set, A a finite action set, O a finite observation set, P:S×A→Δ(S)P S× A→ (S) a transition kernel, Z:S×A→Δ(O)Z S× A→ (O) an observation kernel, R:S×A→ℝR S× A a reward function, and b0∈Δ(S)b_0∈ (S) an initial belief. Definition 2.2 (Stochastic Finite-State Controller). A stochastic FSC is a tuple π=⟨N,α,β,n0⟩π= N,α,β,n_0 where N is a finite set of internal nodes with |N|≤m|N|≤ m, α:N→Δ(A)α N→ (A) is an action-selection function, β:N×O→Δ(N)β N× O→ (N) is an internal-transition function, and n0∈Nn_0∈ N is the initial node. Fix a memory bound m and horizon T. We distinguish two probe families. • Clock-aware probes Πm,Tclk ^clk_m,T: FSCs with stage-indexed maps (ατ,βτ)τ=0T−1( _τ, _τ)_τ=0^T-1. Equivalently, these are FSCs on node space N×0,…,T−1N×\0,…,T-1\, where the external horizon clock does not count against the internal memory budget. • Operational probes Πm,Top ^op_m,T: deterministic stationary FSCs with at most m internal nodes. The fully enumerated large-scale experiments use this deterministic-stationary family as a tractable operational restriction. Practically, a clock-aware FSC may change its action and node-update rule with the time index even if it revisits the same internal node, whereas a stationary FSC must reuse the same rule whenever that node is revisited. For example, a one-node clock-aware controller may “listen” at stage 1 and “open” at stage 2 while remaining in the same internal node; a one-node stationary controller cannot express that time-indexed switch without enlarging its state. This is why clock-awareness restores deterministic witness sufficiency in the theorem, while the stationary family is a stricter operational restriction. We therefore use Πm,Tclk ^clk_m,T as a gold-standard bounded-observer family: it is partly proof-motivated, but it also models bounded agents whose internal logic can legitimately depend on a known stage or deadline (for example countdown-style or phase-based controllers). The stationary family Πm,Top ^op_m,T is the stricter operational deployment model when such external clocking is unavailable or intentionally disallowed. For any fixed probe family Π , a policy π∈Ππ∈ interacting with POMDP M induces a distribution PMπP_M^π over observation sequences (o1,…,oT)∈OT(o_1,…,o_T)∈ O^T and conditional suffix laws PMπ(Ot+1:T∣h)P_M^π(O_t+1:T h). 3 Bounded Indistinguishability and the Wasserstein Pseudometric Total variation is topologically brittle for model comparison [17]: it treats all non-identical observations as equally distant. When observations carry ordinal or spatial structure, TV forces overly fine partitions. The 1-Wasserstein distance 1W_1 exploits a ground metric dOd_O on O and degrades gracefully under perturbations. Let dO:O×O→ℝ≥0d_O O× O _≥ 0 be a ground metric on observations, extended to sequences via dOT((o1,…,oT),(o1′,…,oT′))=∑t=1TdO(ot,ot′)d_O^T((o_1,…,o_T),(o_1 ,…,o_T ))= _t=1^Td_O(o_t,o_t ). Definition 3.1 (Closed-loop Wasserstein pseudometric). For two POMDPs M and N sharing (A,O)(A,O) and a fixed probe family Π : DTΠ(M,N):=supπ∈Π1(PMπ,PNπ).D_T (M,N):= _π∈ W_1 (P_M^π,P_N^π ). (1) When Π=Πm,Tclk = ^clk_m,T or Π=Πm,Top = ^op_m,T, we write Dm,TclkD_m,T^clk or Dm,TopD_m,T^op respectively. Proposition 3.2. DTΠD_T is a pseudometric on POMDPs sharing (A,O)(A,O), with DTΠ(M,N)=0D_T (M,N)=0 iff PMπ=PNπP_M^π=P_N^π for all π∈Ππ∈ . Proof. For each fixed π∈Ππ∈ , the quantity 1(PMπ,PNπ)W_1(P_M^π,P_N^π) is a metric on laws over OTO^T. Non-negativity and symmetry therefore hold pointwise. For the triangle inequality, for any third model K and every π∈Ππ∈ , 1(PMπ,PKπ)≤1(PMπ,PNπ)+1(PNπ,PKπ),W_1(P_M^π,P_K^π) _1(P_M^π,P_N^π)+W_1(P_N^π,P_K^π), and taking the supremum over π gives DTΠ(M,K)≤DTΠ(M,N)+DTΠ(N,K)D_T (M,K)≤ D_T (M,N)+D_T (N,K). Finally, DTΠ(M,N)=0D_T (M,N)=0 iff every term in the supremum is zero, equivalently PMπ=PNπP_M^π=P_N^π for all π∈Ππ∈ . ∎ Remark 3.3 (Relation to bisimulation metrics). The conceptual lineage to Wasserstein bisimulation metrics is intentional. Both constructions use optimal-transport distances to quantify behavioral distinguishability. The difference is where the supremum lives and what object is being compared. State-based bisimulation metrics compare one-step transition kernels and reward terms through a fixed-point recursion over all actions. Our DTΠD_T instead compares finite-horizon observation-sequence laws after concrete histories and takes the supremum only over a prescribed bounded controller family. In that sense DTΠD_T is best viewed as a history-space, bounded-agent analogue of bisimulation metrics; the new contribution is that this bounded-family pseudometric induces canonical quotients and exact sufficiency statements for the chosen observer class. Definition 3.4 (LRL_R-observation-Lipschitz reward). A reward function R is LRL_R-observation-Lipschitz if, for all equal-length histories h,h′h,h and all π in the relevant fixed probe family, |R¯(h,π)−R¯(h′,π)|≤LR⋅1(PMπ(O|h|+1:T∣h),PMπ(O|h|+1:T∣h′))| R(h,π)- R(h ,π)|≤ L_R·W_1 (P_M^π(O_|h|+1:T h),\,P_M^π(O_|h|+1:T h ) ), where R¯(h,π)≔∑sbh(s)∑aπ(a∣h)R(s,a) R(h,π) _sb_h(s) _aπ(a h)\,R(s,a). Constant rewards satisfy LR=0L_R=0; the standard Tiger reward (listen =−1=-1, correct open =+10=+10, incorrect open =−100=-100) satisfies LR≤110L_R≤ 110 (the reward range Rmax−RminR_ -R_ ); the synthetic 1-Lipschitz observation score used in the value-bound experiments (§7) has LR=1L_R=1. Remark 3.5 (When is LRL_R small?). Observation-based rewards R(s,a)=r(os)R(s,a)=r(o_s) for some function r:O→ℝr O satisfy LR≤Lip(r)L_R (r), the Lipschitz constant of r under dOd_O. When r is bounded and dOd_O is normalized to [0,1][0,1], this gives LR≤Rmax−RminL_R≤ R_ -R_ —the reward range. More generally, any reward depending on the state only through the observation posterior has bounded LRL_R; rewards that depend on fine-grained latent state distinctions invisible to observations can have arbitrarily large LRL_R. The value bound LRTεL_RT is thus most informative for observation-aligned reward structures—precisely the setting where bounded agents are effective. Note that LRL_R depends on the choice of probe family through the conditional observation laws PMπ(Ot+1:T∣h)P_M^π(O_t+1:T h); a richer probe family may expose reward differences that a poorer one cannot, changing the effective Lipschitz constant. In general, the reward range Rmax−RminR_ -R_ is a valid (but often vacuous) upper bound on LRL_R under the discrete observation metric dO(o,o′)=o≠o′d_O(o,o )=1_o≠ o , since 1W_1 under the summed discrete metric upper-bounds total variation. Theorem 3.6 (Value-function error bound). Let M~ M be the quotient POMDP (Definition 4.3) constructed from a partition of histories into classes with pairwise probe-distance at most ε under a fixed probe family Π , with beliefs aggregated within each class. If R is LRL_R-observation-Lipschitz, then for any π∈Ππ∈ : |VMπ−VM~π|≤LR⋅T⋅ε. |V_M^π-V_ M^π |≤ L_R· T· . (2) Proof. Fix π∈Ππ∈ and let HtH_t denote the random history up to time t. For each stage define Δt(Ht):=1(PMπ(Ot+1:T∣Ht),PM~π(Ot+1:T∣Ht)). _t(H_t):=W_1\! (P_M^π(O_t+1:T H_t),\,P_ M^π(O_t+1:T H_t) ). The observation-Lipschitz assumption gives an almost-sure stagewise bound |R¯M(Ht,π)−R¯M~(Ht,π)|≤LRΔt(Ht). | R_M(H_t,π)- R_ M(H_t,π) |≤ L_R\, _t(H_t). By hypothesis, the quotient M~ M partitions histories into classes of pairwise probe-distance at most ε . Hence the quotient’s conditional law PM~π(Ot+1:T∣Ht)P_ M^π(O_t+1:T H_t) is a convex combination (via the belief-aggregation weights) of conditional laws PMπ(Ot+1:T∣h′):h′∈[Ht]\P_M^π(O_t+1:T h ):h ∈[H_t]\, each of which satisfies 1(PMπ(⋅∣Ht),PMπ(⋅∣h′))≤εW_1(P_M^π(· H_t),P_M^π(· h ))≤ . Because 1W_1 is convex (as a supremum of linear functionals), the mixture satisfies Δt(Ht)≤εa.s. for each t. _t(H_t)≤ .s. for each t. Taking expectations and summing the T stagewise differences yields |VMπ−VM~π|≤LR∑t=1T[Δt(Ht)]≤LRTε, |V_M^π-V_ M^π |≤ L_R _t=1^TE[ _t(H_t)]≤ L_R\,T\, , which is exactly (2). ∎ The bound is most informative when rewards align with the observation structure. For Tiger’s standard latent-state reward (LR=110L_R=110), the ±100±100 penalty depends on which door hides the tiger—a latent distinction invisible to observation sequences—making the bound explicitly vacuous. For observation-aligned rewards (LR≤Rmax−RminL_R≤ R_ -R_ ), the bound is tight, and the exact quotient preserves value perfectly (Theorem 4.6). Corollary 3.7 (Sim-to-real regret). Under the same hypotheses as Theorem 3.6, let πM~∗∈argmaxπ∈ΠVM~π^*_ M∈ *arg\,max_π∈ V_ M^π. Then the regret of the quotient-optimal policy on the original model satisfies VMπM∗−VMπM~∗≤2LR⋅T⋅ε.V_M^π^*_M-V_M^π^*_ M≤ 2\,L_R· T· . Proof. By the triangle inequality: VMπM∗−VMπM~∗≤(VMπM∗−VM~πM∗)+(VM~πM~∗−VMπM~∗)≤2LRTεV_M^π^*_M-V_M^π^*_ M≤(V_M^π^*_M-V_ M^π^*_M)+(V_ M^π^*_ M-V_M^π^*_ M)≤ 2\,L_RT . ∎ 4 Equivalence on Histories and the Quotient POMDP 4.1 Quotient Construction Definition 4.1 (Bounded indistinguishability). Fix a probe family Π . For equal-length histories h,h′∈Oth,h ∈ O^t, define the history-level probe distance dΠ(h,h′):=supπ∈Π1(PMπ(Ot+1:T∣h),PMπ(Ot+1:T∣h′)).d (h,h ):= _π∈ W_1(P_M^π(O_t+1:T h),P_M^π(O_t+1:T h )). Two histories are Π -equivalent, written h≡Πh′h≡ h , if dΠ(h,h′)=0.d (h,h )=0. For the two main families we write ≡m,Tclk≡^clk_m,T and ≡m,Top≡^op_m,T, and dm,Tclk(h,h′)d^clk_m,T(h,h ), dm,Top(h,h′)d^op_m,T(h,h ) for the corresponding history-level distances. Proposition 4.2 (Properties of ≡m,T _m,T). For every fixed probe family Π , the relation ≡Π≡ is (a) an equivalence relation, (b) right-invariant: h≡Πh′h≡ h implies h⋅z≡Πh′⋅zh· z≡ h · z, and (c) of finite index. Proof. Reflexivity and symmetry are immediate from the definition. For transitivity, if h≡Πh′h≡ h and h′≡Πh′h ≡ h , then for every π∈Ππ∈ the triangle inequality for 1W_1 gives zero distance between the conditional suffix laws from h and h′h . For right-invariance, fix z∈Oz∈ O. Zero Wasserstein distance between the suffix laws from h and h′h implies equality of those conditional laws on every cylinder event, hence the same probability of seeing z next and the same law of the remaining suffix after conditioning on that common event. Therefore h⋅zh\!·\!z and h′⋅zh \!·\!z induce identical continuation laws for every controller in Π , so h⋅z≡Πh′⋅zh· z≡ h · z. Finite index holds because at each depth t there are only finitely many histories in OtO^t. ∎ Definition 4.3 (Quotient POMDP). For a fixed probe family Π , the quotient QΠ(M)Q (M) has state space [h]Π:h∈Ot\[h]_ :h∈ O^t\ at time t, initial state [ϵ]Π[ε]_ , and transition P¯([h],a,[h⋅z])=∑s′Z(s′,a,z)∑sP(s,a,s′)b¯[h](s) P([h],a,[h· z])= _s Z(s ,a,z) _sP(s,a,s )\, b_[h](s), where b¯[h] b_[h] is the aggregated belief state of the class (any convex combination of member beliefs; by Theorem 4.4(i), the quotient transition is independent of this choice in the exact case). The quotient is a finite-horizon controlled process with time-varying state space; equivalently, one can augment the state with the time index t to obtain a stationary representation. Theorem 4.4 (Bounded-Interaction Myhill–Nerode). Let QΠ(M)Q (M) be the quotient under probe-exact equivalence for a fixed probe family Π . Then: (i) Well-definedness. The quotient transition kernel is independent of the choice of representative and aggregation weights. (i) Soundness. PMπ(OT)=PQΠ(M)π(OT)P_M^π(O^T)=P_Q (M)^π(O^T) for every π∈Ππ∈ . (i) Universality. Any POMDP N with PNπ=PMπP_N^π=P_M^π for all π∈Ππ∈ admits a POMDP morphism ϕ:N↠QΠ(M)φ N Q (M). (iv) Minimality. QΠ(M)Q (M) has the fewest history classes (equivalence classes of the observation-history tree) among all history-based POMDPs satisfying (i). (v) Uniqueness. QΠ(M)Q (M) is unique up to isomorphism. Proof sketch. The invariant is: two representatives of the same class induce the same family of probe suffix laws after every continuation. Well-definedness follows because probe-exact equivalence forces identical one-step observation laws for all histories in a class; in particular, constant-action FSCs already imply equality of the one-step kernels needed to define P¯([h],a,⋅) P([h],a,·), so the quotient transition is representative-independent. Soundness is then an induction on the realized history length: if the current quotient class matches the original history’s probe law at time t, the common one-step kernel preserves that match after observing z and moving to h⋅zh\!·\!z. For universality, any POMDP N reproducing the same probe laws determines a canonical map sending each history of N to the unique quotient class with the same family of suffix laws; the same representative-independence argument verifies the morphism identities. Minimality and uniqueness are the usual universal-object consequence: every competing exact model surjects onto QΠ(M)Q (M), and two minimal such objects therefore surject onto one another and are isomorphic. □ 4.2 Structural Properties Definition 4.5 (Agent-accessible objectives). Let obsG_obs be the class of bounded measurable functionals G:(O×A)T→ℝG (O× A)^T defined on the joint observation-action trajectory. This is the natural class for bounded agents whose costs depend on what they sense and do: sensorimotor penalties, action budgets, tracking objectives defined on filtered observations, or other control costs measurable from the observation–action trace itself. When the reward depends on latent state variables that are not measurable from that trace, exact preservation is no longer available and the paper deliberately falls back to the observation-Lipschitz approximation story. Theorem 4.6 (Exact sufficiency for agent-accessible objectives). For every π∈Πm,Tclkπ∈ ^clk_m,T and every G∈obsG _obs, Mπ[G(O1:T,A1:T)]=Qm,Tclk(M)π[G(O1:T,A1:T)].E_M^π[G(O_1:T,A_1:T)]=E_Q^clk_m,T(M)^π[G(O_1:T,A_1:T)]. Proof sketch. The argument proceeds in three stages: observation-law preservation, action-law transfer, and functional integration. Stage 1 (Observation law). By the soundness part of Theorem 4.4, Qm,Tclk(M)Q^clk_m,T(M) reproduces the full observation law PMπ(O1:T)P_M^π(O_1:T) for every π∈Πm,Tclkπ∈ ^clk_m,T. In particular, for every history h=(o1,…,ot)h=(o_1,…,o_t) and every π, the conditional future-observation law PMπ(Ot+1:T∣h)=PQm,Tclk(M)π(Ot+1:T∣h)P_M^π(O_t+1:T h)=P_Q^clk_m,T(M)^π(O_t+1:T h). Stage 2 (Action law). Each clock-aware policy π∈Πm,Tclkπ∈ ^clk_m,T selects its stage-t action as a deterministic (or stochastic) function of the observation history o1:to_1:t and the current internal state, which itself evolves deterministically from o1:to_1:t. The action at stage t is therefore measurable with respect to the observation history up to time t. Since Stage 1 guarantees identical conditional observation laws at every stage under π, an induction on t=1,…,Tt=1,…,T shows that the joint marginals PMπ(O1:t,A1:t)P_M^π(O_1:t,A_1:t) and PQm,Tclk(M)π(O1:t,A1:t)P_Q^clk_m,T(M)^π(O_1:t,A_1:t) agree at every stage: at the inductive step, the common observation law at stage t+1t+1 and the common policy mapping together fix At+1A_t+1. Stage 3 (Functional integration). Because G∈obsG _obs is a bounded measurable functional on (O×A)T(O× A)^T, the expectation π[G(O1:T,A1:T)]E^π[G(O_1:T,A_1:T)] depends only on the joint law established in Stage 2. Since that law is identical in M and Qm,Tclk(M)Q^clk_m,T(M), exact preservation follows. □ Corollary 4.7 (Optimal value preservation on obsG_obs). For every G∈obsG _obs, supπ∈Πm,TclkMπ[G]=supπ∈Πm,TclkQm,Tclk(M)π[G]. _π∈ ^clk_m,TE_M^π[G]= _π∈ ^clk_m,TE_Q^clk_m,T(M)^π[G]. Remark 4.8 (Refinement and bisimulation recovery). The quotient family still forms a refinement lattice indexed by probe capacity, horizon, and approximation level, and the classical bisimulation quotient is recovered in the unbounded limit. The key point is different: the theorem object is the clock-aware quotient Qm,TclkQ^clk_m,T, while the deterministic-stationary family used operationally in the experiments is a deliberate coarsening rather than a theorem-certified substitute. Theorem 4.9 (Witness for clock-aware bounded agents). If two histories h,h′h,h are distinguishable by some stochastic clock-aware FSC π∈Πm,Tclkπ∈ _m,T^clk, then there exists a deterministic clock-aware FSC π∗∈Πm,Tclkπ^*∈ _m,T^clk with PMπ∗(⋅∣h)≠PMπ∗(⋅∣h′)P_M^π^*(· h)≠ P_M^π^*(· h ). Proof sketch. For the clock-aware class, the probability of any fixed future observation sequence is multilinear in the stage-indexed FSC parameters; stage indexing prevents any parameter from being reused at two different times. By a vertex lemma on the corresponding product of simplices, non-vanishing at any interior point implies non-vanishing at a vertex, i.e. a deterministic clock-aware FSC. Proposition 4.10 shows that this argument does not extend to stationary looping FSCs; the experiments use deterministic stationary FSCs as an operational probe family only. □ Proposition 4.10 (Deterministic stationary FSCs do not suffice in general). There exists a finite POMDP and histories h,h′h,h such that some stochastic stationary 11-node FSC distinguishes h and h′h , while every deterministic stationary 11-node FSC induces the same future observation law from h and h′h . Proof sketch. Appendix A gives an explicit m=1m=1, T=3T=3 construction with actions A,B\A,B\ and observations L,R,U,X,Y\L,R,U,X,Y\. After histories L and R, the two deterministic stationary controllers (always-A and always-B) both induce the same suffix law, but the stochastic controller with α(A)=α(B)=1/2α(A)=α(B)=1/2 yields suffix laws UU:3/4,UX:1/4\U:3/4,UX:1/4\ and UU:3/4,UY:1/4\U:3/4,UY:1/4\ respectively, whose 1W_1 distance under the discrete metric is 1/41/4. □ The construction uses m=1m=1; analogous counterexamples exist for general m≥1m≥ 1 by embedding the same branching structure within a larger node space, since the additional nodes cannot compensate for the loss of stochasticity when the branching occurs at the single active node. Proposition 4.11 (Smaller probe classes induce coarser quotients). Let Π1⊆Π2 _1 _2 be two probe families. Then for every pair of histories, dΠ1(h,h′)≤dΠ2(h,h′).d _1(h,h )≤ d _2(h,h ). Consequently, h≡Π2h′⟹h≡Π1h′,h≡ _2h h≡ _1h , so the quotient QΠ1(M)Q _1(M) is a coarsening of QΠ2(M)Q _2(M). In particular, because Πm,Top⊂Πm,Tclk ^op_m,T⊂ ^clk_m,T, the operational quotient Qm,TopQ^op_m,T used in the experiments is a tractable coarsening of the theorem-level quotient Qm,TclkQ^clk_m,T. Theorem 4.12 (Cross-family value transfer). Let Π1⊆Π2 _1 _2 be probe families, and define the cross-family gap δ1,2:=suph,h′(dΠ2(h,h′)−dΠ1(h,h′))=‖dΠ2−dΠ1‖∞. _1,2:= _h,h (d _2(h,h )-d _1(h,h ) )=\|d _2-d _1\|_∞. Let M~1 M_1 be the ε -quotient built under Π1 _1. Then for every LRL_R-observation-Lipschitz reward and every π∈Π2π∈ _2, |VMπ−VM~1π|≤LRT(ε+δ1,2). |V_M^π-V_ M_1^π |≤ L_R\,T\,( + _1,2). Proof. If dΠ1(h,h′)≤εd _1(h,h )≤ , then by definition of δ1,2 _1,2, dΠ2(h,h′)≤dΠ1(h,h′)+δ1,2≤ε+δ1,2.d _2(h,h )≤ d _1(h,h )+ _1,2≤ + _1,2. Hence the partition built under Π1 _1 has pairwise Π2 _2-diameter at most ε+δ1,2 + _1,2. Applying Theorem 3.6 with probe family Π2 _2 and merge threshold ε+δ1,2 + _1,2 gives the result. ∎ Corollary 4.13 (Operational-to-clock-aware transfer). Let δclk:=‖dm,Tclk−dm,Top‖∞. _clk:=\|d^clk_m,T-d^op_m,T\|_∞. Then for every LRL_R-observation-Lipschitz reward and every π∈Πm,Tclkπ∈ ^clk_m,T, |VMπ−VQm,Top(M)π|≤LRT(ε+δclk) |V_M^π-V_Q^op_m,T(M)^π |≤ L_R\,T\,( + _clk) whenever Qm,Top(M)Q^op_m,T(M) is constructed as an ε -quotient under Πm,Top ^op_m,T and the gap δclk _clk is measured for that same bounded regime. Corollary 4.14 (Subset plus cross-family transfer). Let dS(h,h′):=supπ∈S1(PMπ(Ot+1:T∣h),PMπ(Ot+1:T∣h′))d_S(h,h ):= _π∈ SW_1(P_M^π(O_t+1:T h),P_M^π(O_t+1:T h )) be the subset probe envelope for S⊆Π1S _1, and let δS:=‖dΠ1−dS‖∞ _S:=\|d _1-d_S\|_∞. Then for every LRL_R-observation-Lipschitz reward and every π∈Π2π∈ _2, |VMπ−VM~Sπ|≤LRT(ε+δS+δ1,2). |V_M^π-V_ M_S^π |≤ L_R\,T\,( + _S+ _1,2). Proof. If dS(h,h′)≤εd_S(h,h )≤ , then dΠ1(h,h′)≤ε+δSd _1(h,h )≤ + _S and therefore dΠ2(h,h′)≤dΠ1(h,h′)+δ1,2≤ε+δS+δ1,2.d _2(h,h )≤ d _1(h,h )+ _1,2≤ + _S+ _1,2. Applying Theorem 3.6 with probe family Π2 _2 and merge threshold ε+δS+δ1,2 + _S+ _1,2 yields the bound. ∎ 66 cls88 cls1010 cls1414 cls1616 cls3131 clsε=0 =0ε=0.3 =0.3ε=0.5 =0.5m=1m=1m=2m=2 Figure 2: Refinement lattice for Tiger (T=4T=4). Solid arrows: increasing ε coarsens the quotient (Definition 5.1). Dashed arrows: increasing m refines the quotient (Proposition 4.11—larger probe class ⇒ finer partition). Data from operational capacity sweep. 5 ε -Quotients and Data-Processing Monotonicity Exact indistinguishability is often overly restrictive; we relax the framework to ε -approximate quotients. We write Dm,T:=DTΠD_m,T^W:=D_T when the probe family Π and the ground metric are clear from context, to emphasize the Wasserstein dependence. Definition 5.1 (ε -equivalence). M∼m,TεNM _m,T N if Dm,T(M,N)≤εD_m,T^W(M,N)≤ . An ε -quotient of M is a reduced POMDP M~ M with Dm,T(M,M~)≤εD_m,T^W(M, M)≤ . In the approximate setting, the canonical object is the partition of histories. Materializing a quotient POMDP additionally requires a belief-aggregation rule inside each class; Proposition A.1 fixes the uniform canonical choice used throughout the experiments and bounds. Definition 5.2 (Wrapper). A wrapper W maps a POMDP M to W(M)W(M) via an action remapping g:A′→Δ(A)g A → (A) and an observation channel C:O→Δ(O′)C O→ (O ) with Lipschitz constant LC:=maxo≠o′1(C(o),C(o′);dO′)/dO(o,o′)L_C:= _o≠ o W_1(C(o),C(o );\,d_O )/d_O(o,o ). Theorem 5.3 (Data-Processing Monotonicity). Let M,NM,N be POMDPs sharing (A,O)(A,O), W a wrapper with Lipschitz constant LCL_C, and assume the probe family Π is closed under pullback through W (i.e., for every π′∈Ππ ∈ on the wrapped observation–action space, the induced controller π on the original space belongs to Π ; this holds for any family containing all m-bounded stochastic FSCs, in particular for Πm,Tclk ^clk_m,T). Then: Dm,T(W(M),W(N))≤LC⋅Dm,T(M,N).D_m,T^W (W(M),W(N) )≤ L_C· D_m,T^W(M,N). (3) In particular, equivalent models remain equivalent after wrapping. Proof sketch. The wrapper post-processes observation sequences through C⊗TC T. By Kantorovich–Rubinstein duality and the Lipschitz property, 1W_1 contracts by factor LCL_C. Taking the same supremum over the bounded controller family on both sides preserves that contraction, so equivalence is stable under wrapping. □ Definition 5.4 (δO _O-coarsened agent class). Given a ground metric dOd_O on observations and resolution δO≥0 _O≥ 0, let Oδ⊆O_δ O be a minimal δO _O-covering: every o∈Oo∈ O satisfies mino′∈OδdO(o,o′)≤δO _o ∈ O_δd_O(o,o )≤ _O. The δO _O-coarsened agent class Πm,T,δ _m,T,δ consists of FSCs whose node-transition function factors through the quantization map qδ:O→Oδq_δ O→ O_δ defined by qδ(o)=argmino′∈OδdO(o,o′)q_δ(o)= *arg\,min_o ∈ O_δd_O(o,o ). Proposition 5.5 (Observation-resolution bounds). Let Qm,T,δQ_m,T,δ denote the ε -quotient under Πm,T,δ _m,T,δ. (a) Distance bound: Dm,T,δ(M,M~)≤Dm,T(M,M~)+T⋅δOD_m,T,δ^W(M, M)≤ D_m,T^W(M, M)+T· _O. (b) Partition size: Qm,T,δQ_m,T,δ has at most ∑t=0T|Oδ|t _t=0^T|O_δ|^t equivalence classes. (c) Value error: |VMπ−VQm,T,δπ|≤LR⋅T⋅(ε+TδO)|V_M^π-V_Q_m,T,δ^π|≤ L_R· T·( +T _O) for all π∈Πm,T,δπ∈ _m,T,δ. Proof sketch. Part (a): replacing each observation by its δO _O-nearest representative shifts the per-step 1W_1 by at most δO _O; summing over T steps gives the additive TδOT _O term. Part (b): the coarsened history space has |Oδ|t|O_δ|^t histories at depth t. Part (c): the partition under Πm,T,δ _m,T,δ has Πm,T,δ _m,T,δ-diameter at most ε ; the same per-step δO _O shift from part (a) applies at the history level to conditional suffix distances, so the partition has Πm,T _m,T-diameter at most ε+TδO +T _O. Theorem 3.6 then applies with merge threshold ε+TδO +T _O. □ Theorem 5.6 (Compositional horizon-scaling bound). Let T be the end-to-end horizon. Let reference models (Mi)i=1L+1(M_i)_i=1^L+1, approximate models (M~i)i=1L+1( M_i)_i=1^L+1, and wrappers WiW_i with Lipschitz constants LiL_i satisfy Γ1:=Dm,T(M1,M~1),Mi+1=Wi(Mi),Dm,T(Wi(M~i),M~i+1)≤εi(i=1,…,L). _1:=D_m,T^W(M_1, M_1), M_i+1=W_i(M_i), D_m,T^W\! (W_i( M_i), M_i+1 )≤ _i (i=1,…,L). (4) Define Γi:=Dm,T(Mi,M~i) _i:=D_m,T^W(M_i, M_i). Then the cumulative distortion obeys Γi+1≤LiΓi+εi,i=1,…,L, _i+1≤ L_i _i+ _i, i=1,…,L, (5) and hence the final-layer distortion satisfies ΓL+1≤(∏j=1LLj)Γ1+∑i=1L(∏j=i+1LLj)εi. _L+1≤ ( _j=1^LL_j ) _1+ _i=1^L ( _j=i+1^LL_j ) _i. (6) In the common zero-initialization case M~1=M1 M_1=M_1, one has Γ1=0 _1=0 and only the weighted sum of the per-layer residuals remains. Proof sketch. The first term comes from propagating the previous layer’s discrepancy through the wrapper, and the second from the fresh approximation introduced at the new layer. Apply Theorem 5.3 and the triangle inequality to obtain (5), then unroll the recursion by induction. □ Corollary 5.7 (Layered value bound). If additionally M~L+1 M_L+1 is a partition-based quotient of ML+1M_L+1 with class diameter at most ΓL+1 _L+1 (i.e., the partition is chosen so that its pairwise probe-distance does not exceed the propagated bound from Theorem 5.6), and the reward on the final observation space is LRL_R-observation-Lipschitz, then for any π∈Πm,Tπ∈ _m,T: |VML+1π−VM~L+1π|≤LR⋅T⋅[(∏j=1LLj)Γ1+∑i=1L(∏j=i+1LLj)εi.] |V_M_L+1^π-V_ M_L+1^π |≤ L_R· T· [ ( _j=1^LL_j ) _1+ _i=1^L ( _j=i+1^LL_j ) _i. ] (7) Proof sketch. Theorem 5.6 bounds ΓL+1 _L+1; Theorem 3.6 applied with merge threshold ΓL+1 _L+1 gives the result. □ Proposition 5.8 (Layered construction complexity). For fixed m and uniform segment horizon τ with T=LτT=Lτ, monolithic computation has complexity O(|O|T+1−1|O|−1⋅|A|mm|O|⋅T|S|2|O|),O\! ( |O|^T+1-1|O|-1·|A|^mm^m|O|· T S ^2|O| ), (8) while layered construction costs O(L⋅|O|τ+1−1|O|−1⋅|A|mm|O|⋅τ|S|2|O|).O\! (L· |O|^τ+1-1|O|-1·|A|^mm^m|O|·τ S ^2|O| ). (9) Hence layering replaces the exponential history term in T by a linear factor in L times an exponential in τ. In the Options framework [47], wrappers correspond to hierarchy layers: macro-actions are action remappings, abstract observations are channels. Theorem 5.6 gives the corresponding multi-layer error accumulation rule and Proposition 5.8 gives the associated horizon-scaling tradeoff. 6 Operational Approximation Machinery This section is operational rather than theorem-level. Greedy subset selection gives a practical way to compress the deterministic-stationary probe class, but by itself it only optimizes a coverage objective. The role of δS _S is to turn a chosen subset into an a posteriori operational certificate: once computed from the full deterministic-stationary FSC tensor on operational exact-for-family benchmarks, it measures how much probe-envelope information the subset misses and therefore whether the value guarantee survives the compression. Algorithm 1 Approximate Partition Refinement for ε -Quotient 1:POMDP M, bounds m,Tm,T, tolerance ε>0 >0 2:ε -quotient Q~ Q 3:Enumerate deterministic FSCs Πmdet _m^det 4:Initialize partition ←Ot:0≤t≤TP←\O^t:0≤ t≤ T\ ⊳ group by length 5:repeat 6: for each block B∈B do 7: Split B by maxπ1(PMπ(⋅∣h),PMπ(⋅∣h′))≤ε _πW_1 (P_M^π(· h),\,P_M^π(· h ) )≤ 8: end for 9:until P is stable 10:return quotient POMDP with canonical beliefs b¯[h] b_[h] Worst-case complexity is O(|O|T+1−1|O|−1⋅|A|m⋅m|O|⋅T|S|2|O|)O\! ( |O|^T+1-1|O|-1·|A|^m· m^m|O|· T S ^2|O| )—polynomial in |S||S| for fixed m,Tm,T. This probe-exact procedure has cost exponential in the horizon parameter T, because it expands a depth-T history tree and evaluates depth-T bounded-controller behavior explicitly; whether the problem itself requires exponential time remains open (Appendix F). Structural vs. operational role. The classical Myhill–Nerode theorem for DFAs yields an O(nlogn)O(n n) minimization algorithm [23]; our bounded-interaction analogue does not currently come with a comparable polynomial-time algorithm for the probe-exact quotient, and the explicit procedure above remains exponential in the horizon parameter. The paper’s main scientific claim is therefore structural: it identifies the canonical bounded-observer target and proves its uniqueness, minimality, and value-preservation properties. The operational machinery is the companion computational layer. It explains how tractable coarsenings such as Qm,TopQ^op_m,T can be studied in practice through subset certificates, sampling, layering, and observation coarsening, but those operational studies only support theorem-level statements when an explicit subset or cross-family certificate is reported for the same bounded regime. Otherwise they should be read as empirical case studies of a tractable surrogate rather than as additional theorem validation, and the uncertified medium-scale tables should not be read as part of the paper’s core contribution claims. Appendix B records a stricter structural sufficient condition via anchor families. Practical tractability. The four complexity factors—histories (|O|T|O|^T), FSCs (|A|mm|O||A|^mm^m|O|), belief propagation (|S|2|S|^2), and observation-alphabet size (|O||O|)—are addressed by complementary techniques. (1) The history bottleneck is mitigated by layered horizon decomposition (Theorem 5.6, Proposition 5.8): replacing one T-step computation by L short segments of length τ changes the dominant history factor from |O|T|O|^T to L|O|τL|O|^τ. (2) The FSC bottleneck is mitigated by greedy controller-subset selection (Algorithm 2): on the operational exact-for-family Tiger and GridWorld benchmarks, small subsets recover the full probe envelope after explicit a posteriori checking (δS=0 _S=0; Table 5), while the same heuristic also underlies the appendix-only archival stress tracks for larger-m regimes (Appendix G.3). (3) Sampling-based 1W_1 estimation decouples the per-history cost from |S||S|: each trajectory simulation costs O(T)O(T) per step after an O(|S|)O(|S|) belief sample, enabling operational case studies up to |S|=100|S|=100 in 0.300.30 s (Table 6). (4) The observation-alphabet bottleneck is reduced by δO _O-coarsening (Proposition 5.5): replacing |O||O| by |Oδ|≤|O||O_δ|≤|O| reduces the history factor from |O|T|O|^T to |Oδ|T|O_δ|^T at the cost of an additive LRT2δOL_RT^2 _O term in the value bound. Together, these techniques make the operational core experiments practical on a single CPU core, while the heavier long-horizon and larger-m stress tracks are reported separately in Appendix G.3. Greedy controller-subset selection. The FSC distance tensor D(i,j),p=1(PMπp(⋅∣hi),PMπp(⋅∣hj))D_(i,j),p=W_1(P_M _p(· h_i),P_M _p(· h_j)) is operationally compressible: distinguishing power often concentrates on a small number of high-coverage controllers. We therefore select FSCs by maximizing the monotone submodular coverage objective f(S)=∑(i,j)maxp∈SD(i,j),pf(S)= _(i,j) _p∈ SD_(i,j),p via greedy selection. Algorithm 2 Greedy Controller-Subset Selection 1:Distinguishing matrix ∈ℝ(n2)×PD n2× P, budget k 2:Index set S⊆1,…,PS \1,…,P\ with |S|=k|S|=k 3:S←∅S← ; d(i,j)∗←0d^*_(i,j)← 0 for all (i,j)(i,j) 4:for t=1,…,kt=1,…,k do 5: p∗←argmaxp∉S∑(i,j)max(0,D(i,j),p−d(i,j)∗)p^*← *arg\,max_p∉ S _(i,j) (0,\,D_(i,j),p-d^*_(i,j)) 6: S←S∪p∗S← S∪\p^*\ 7: d(i,j)∗←max(d(i,j)∗,D(i,j),p∗)d^*_(i,j)← (d^*_(i,j),\,D_(i,j),p^*) for all (i,j)(i,j) 8:end for 9:return S Proposition 6.1 (Submodular guarantee). The greedy selection achieves f(Sk)≥(1−1/e)⋅f(Sk∗)f(S_k)≥(1-1/e)· f(S_k^*) [35]. This (1−1/e)(1-1/e) guarantee is a coverage guarantee only: by itself it does not imply operational exact-partition recovery or value preservation. Those stronger claims require measured small probe-envelope gap δS _S, and Table 5 is empirical-plus-certified only because δS=0 _S=0 is explicitly checked from the full deterministic-stationary FSC tensor. Operational certificate for controller subsets. Let U:=(i,j):history pairsU:=\(i,j):history pairs\ index the rows of the distance tensor, and write d(u):=maxpDu,pd(u):= _pD_u,p for the full probe envelope and dS(u):=maxp∈SDu,pd_S(u):= _p∈ SD_u,p for the subset probe envelope under a selected controller subset S. Define the probe-envelope gap of S by δS:=‖d−dS‖∞. _S:=\|d-d_S\|_∞. Theorem 6.2 (Uniform probe approximation). The ε -quotient built from S satisfies |VMπ−VM~Sπ|≤LRT(ε+δS)∀π∈Πm,T.|V_M^π-V_ M_S^π|≤ L_R\,T\,( + _S) ∀\,π∈ _m,T. Proof. Since dS(u)≤d(u)d_S(u)≤ d(u) for every u, any pair merged by the full-family ε -quotient is also merged by the subset-based ε -quotient. Conversely, if dS(u)≤εd_S(u)≤ , then d(u)≤dS(u)+δS≤ε+δSd(u)≤ d_S(u)+ _S≤ + _S, so the subset-built partition has full-family diameter at most ε+δS + _S. Applying Theorem 3.6 with merge threshold ε+δS + _S gives the result. ∎ Appendix B gives a stricter structural sufficient condition for why a small controller subset may achieve small δS _S: a δ-anchor controller family guarantees small probe-envelope error. We keep that result separate from the main flow because the experiments certify the operational quantity δS _S directly, not anchor-family membership. 7 Experiments This section separates theorem-aligned clock-aware exact experiments from operational results and then marks the heaviest scale-up rows as archival stress tests. The clock-aware exact experiments use deterministic clock-aware open-loop probes for tractable m=1m=1 cases, which coincide with the theorem object for that bounded regime. The larger-scale deterministic-stationary experiments remain operational results for Qm,TopQ^op_m,T and are included to characterise the behaviour of that tractable surrogate, not to extend the theorem’s claim surface. Only the clock-aware exact tables and the deterministic-stationary tables with an explicit δS=0 _S=0 certificate should be read as exact-for-family evidence; the larger scaling tables are intentionally presented as empirical operational demonstrations. Unless stated otherwise, theorem-aligned tables are exhaustive over the stated bounded deterministic clock-aware probe family, while operational scaling tables use deterministic-stationary probes. The new point is quantitative but local: when the cross-family gap δclk _clk is measured on a tractable exact case, Theorem 4.12 upgrades that measured case to an additive value-transfer certificate for the theorem-level family. Where no such δclk _clk measurement is available, the scaling tables remain operational evidence about Qm,TopQ^op_m,T, not direct empirical verification of Qm,TclkQ^clk_m,T, not part of the evidence for contribution (v), and not part of the paper’s theorem-facing claim set. Sampling-based runs use 500500 trajectories per history-policy pair, report 1,0001,000-resample bootstrap confidence intervals for maxh,h′1 _h,h W_1, and include dedicated convergence and seed-stability checks (five replications for convergence, ten seeds for stability); benchmark definitions, expanded tables, parameter grids, and the command-to-table mapping are collected in Appendix G. All runtimes are single-core wall-clock measurements on a MacBook Pro with an Apple M3 Pro chip (12 cores, 36 GB RAM), macOS 26.3.1, and Python 3.11.14; no GPU was used. Table 1 is the evidence contract for the remainder of the section. It separates theorem-level validation, operational exact-for-family certification, and operational empirical stress tests. The paper’s theorem claims are supported only by Tier I and, where applicable, Tier I rows; Tier I rows are reported as scalability evidence about the tractable operational quotient and should not be read as theorem validation unless an explicit cross-family or subset certificate is reported for that benchmark. Table 1: Evidence tiers used in the experiments section. This is the claim-to-evidence contract for the empirical narrative. Tier Representative results What the tier supports Certificate type Tier I: theorem-aligned exact Tables 2, 3, 4 Theorem-level statements about Qm,TclkQ^clk_m,T on the stated bounded exact cases, including measured cross-family transfer on tractable exact instances Exhaustive clock-aware enumeration on the stated finite benchmark and horizon Tier I: operational exact-for-family Table 5 Exact statements about the operational family Qm,TopQ^op_m,T and controller-subset certification within that family Full deterministic-stationary FSC tensor together with reported δS _S certificate Tier I: operational empirical scaling Tables 6, 13, 10, 11 Compression, stability, and runtime evidence for the tractable operational quotient Qm,TopQ^op_m,T; not theorem validation for Qm,TclkQ^clk_m,T unless an explicit bridge is reported Sampling confidence intervals, ARI checks, runtime reporting, and explicit disclosure when no theorem-level certificate is available 7.1 Clock-Aware vs. Operational Probe Families Table 2 compares the theorem-level clock-aware quotient Qm,TclkQ^clk_m,T with the operational deterministic-stationary quotient Qm,TopQ^op_m,T on tractable clock-aware exact cases. The key point is formal rather than numerical: Proposition 4.11 predicts that Qm,TopQ^op_m,T is a coarsening of Qm,TclkQ^clk_m,T, and the small clock-aware exact benchmarks quantify that gap directly. In these tractable rows, the reported column max|dclk−dop| |d^clk-d^op| is exactly the measured cross-family gap δclk _clk entering Theorem 4.12. Table 2: Exact comparison between the theorem-level clock-aware quotient and the operational deterministic-stationary quotient. The stationary witness row is the didactic separation guaranteed by Proposition 4.10. The column max|dclk−dop| |d^clk-d^op| reports the largest absolute pairwise 1W_1 difference (unnormalized); values exceeding 11 arise because the sequence-level metric sums contributions over T time steps. Benchmark T |Qop||Q^op| |Qclk||Q^clk| ARI maxh,h′|dclk−dop| _h,h |d^clk-d^op| Obs. value changed? Tiger 2 4 4 1.000 0.490 No Tiger 4 11 16 0.961 1.315 No Tiger 6 22 64 0.953 2.077 No Tiger 8 37 256 0.956 2.795 No Tiger 10 56 1024 0.959 3.499 No GridWorld 3x3 2 6 6 1.000 0.347 No GridWorld 3x3 3 22 22 1.000 0.549 No GridWorld 5x5 2 6 6 1.000 0.355 No Stationary witness 3 9 10 0.957 1.000 No Three points matter. First, the operational family is not uniformly too weak: on GridWorld 3×33×3 (including T=3T=3) and GridWorld 5×55×5 (|S|=25|S|=25, T=2T=2), it agrees with the theorem object exactly (ARI=1.0=1.0, identical class counts). Second, the gap is not merely philosophical: the stationary witness benchmark shows that Qm,TopQ^op_m,T can merge histories that Qm,TclkQ^clk_m,T must keep separate, and the reported pseudometric gap makes that mismatch quantitative. Third, the measured gap δclk _clk grows with horizon on Tiger (from 0.490.49 at T=2T=2 to 3.503.50 at T=10T=10) yet never changes the observation-value decision, confirming that the operational coarsening is conservative in practice even when the pseudometric gap is large. By Theorem 4.12, that same measured gap is a value-transfer certificate on these tractable exact cases: an operational ε -quotient is also a valid (ε+δclk)( + _clk)-quotient for the clock-aware family. Multi-node probes (m=2m=2). Moving beyond open-loop (m=1m=1) controllers, we enumerate all 1,2961,296 deterministic clock-aware FSCs with m=2m=2 nodes for Tiger at T=2T=2 (Definition 2.2, Section 2), compared to 147147 deterministic stationary m≤2m≤2 FSCs. Despite the ≈9×≈9× richer clock-aware family, both produce identical probe-exact partitions (44 classes, ARI=1.0=1.0, max|dclk−dop|=0 |d^clk-d^op|=0). This indicates that for Tiger at short horizons, the stationary family already saturates the discriminative power of the full clock-aware family—consistent with the intuition that Tiger’s symmetric belief dynamics limit the additional resolution that stage-dependent parameters can provide. 7.2 Decision Sufficiency for Bounded Planning The central theorem-level claim is not exact preservation for arbitrary rewards, but exact preservation for objectives in obsG_obs measurable on the joint observation-action trajectory. Table 3 verifies that claim on the clock-aware exact cases—Tiger (horizons up to T=10T=10), GridWorld 3×33×3 (T≤3T≤3), and GridWorld 5×55×5 (T=2T=2, |S|=25|S|=25)—using observation-only and action-observation objectives. In every row, the quotient-selected policy matches the original-model optimum in value, as Theorem 4.6 predicts. Table 3: Exact preservation of bounded observation-action objectives under the clock-aware quotient Qm,TclkQ^clk_m,T. Benchmark Obj. T Hist. Cls. torigt_orig tQclkt_Q^clk Policy VorigV_orig VQclkV_Q^clk Regret Tiger Obs score 2 7 4 0.000 0.000 L L 1.000 1.000 0.000 Tiger Action+obs score 2 7 4 0.000 0.000 OL OL 1.000 1.000 0.000 Tiger Obs score 4 31 16 0.001 0.003 L L L L 2.000 2.000 0.000 Tiger Action+obs score 4 31 16 0.001 0.003 OL OL OL OL 2.000 2.000 0.000 Tiger Obs score 6 127 64 0.008 0.132 L L L L L L 3.000 3.000 0.000 Tiger Action+obs score 6 127 64 0.009 0.139 OL OL OL OL OL OL 3.000 3.000 0.000 Tiger Obs score 8 511 256 0.104 9.993 L L L L L OL L L 4.000 4.000 0.000 Tiger Action+obs score 8 511 256 0.100 10.023 OL OL OL OL OL OL OL OL 4.000 4.000 0.000 Tiger Obs score 10 2047 1024 1.132 1200.886 L L L L L L L L L L 5.000 5.000 0.000 Tiger Action+obs score 10 2047 1024 1.099 1194.791 OL OL OL OL OL OL OL OL OL OL 5.000 5.000 0.000 GridWorld 3x3 Obs score 2 21 6 0.001 0.000 D D 1.120 1.120 0.000 GridWorld 3x3 Action+obs score 2 21 6 0.000 0.000 U U 0.968 0.968 0.000 GridWorld 3x3 Obs score 3 85 22 0.006 0.008 D D R 1.787 1.787 0.000 GridWorld 3x3 Action+obs score 3 85 22 0.006 0.008 L U U 1.562 1.562 0.000 GridWorld 5x5 Obs score 2 21 6 0.000 0.000 D D 1.072 1.072 0.000 GridWorld 5x5 Action+obs score 2 21 6 0.000 0.000 U U 0.805 0.805 0.000 7.3 Latent-State Planning on Exact Clock-Aware Quotients The approximate-value story remains relevant for latent-state rewards that are not measurable with respect to the observation-action trajectory. Table 4 therefore reports the clock-aware exact m=1m=1 planning study for Tiger’s standard reward and a goal-reward GridWorld. These rows use the theorem object Qm,TclkQ^clk_m,T, but only the approximate latent-state narrative applies. Table 4: Latent-state planning impact on clock-aware exact cases. Values are reported on the original model; regret is relative to the original-model optimum. Benchmark Reward T Hist. Cls. torigt_orig tQclkt_Q^clk Policy VorigV_orig VQclk→MV_Q^clk→ M Regret Tiger Tiger reward 2 7 4 0.000 0.000 L L -2.000 -2.000 0.000 Tiger Tiger reward 4 31 16 0.000 0.009 L L L L -4.000 -4.000 0.000 Tiger Tiger reward 6 127 64 0.005 0.386 L L L L L L -6.000 -6.000 0.000 Tiger Tiger reward 8 511 256 0.061 19.515 L L L L L L L L -8.000 -8.000 0.000 Tiger Tiger reward 10 2047 1024 0.663 1549.370 L L L L L L L L L L -10.000 -10.000 0.000 GridWorld 3x3 Goal reward 2 21 6 0.000 0.001 D U 0.311 0.311 0.000 GridWorld 3x3 Goal reward 3 85 22 0.000 0.023 D R U 0.671 0.671 0.000 7.4 Operational Controller Subsets and A Posteriori Certification Table 5 reports partition agreement and the a posteriori probe-envelope certificate δS=‖d−dS‖∞ _S=\|d-d_S\|_∞ for greedy controller-subset selection (Algorithm 2) on the operational deterministic-stationary m=2m=2 benchmarks. Because δS _S is computed from the full deterministic-stationary FSC tensor, this certification is available only on the operational exact-for-family benchmarks in this subsection. On Tiger (147147 FSCs), k=5k=5 yields δS=0 _S=0 and operational exact-partition recovery for all tested ε . On GridWorld 3×33×3 (6,4056,405 FSCs), k=5k=5 likewise yields δS=0 _S=0; in fact k=3k=3 already closes the probe gap to numerical precision. As a descriptive spectral summary, the GridWorld 99%99\% effective rank (number of singular values capturing 99%99\% of total variance) is 55, so less than 0.1%0.1\% of FSCs capture 99%99\% of distinguishing variance. Reporting δS _S sharpens the empirical story: for example, on GridWorld at ε=0.3 =0.3, k=1k=1 already gives a high ARI, but its nonzero probe gap explains why the subset is not yet operationally certified by Theorem 6.2. Table 5: Operational partition recovery and probe-envelope certification on the deterministic-stationary m=2m=2 benchmarks. Here δS:=‖d−dS‖∞ _S:=\|d-d_S\|_∞ is an a posteriori certificate computed from the full deterministic-stationary FSC tensor. Benchmark ε k δS _S Op. exact classes Approx. classes ARI Tiger (T=4T=4) 0.0 1 0.980 16 11 0.961 Tiger (T=4T=4) 0.0 3 0.245 16 15 0.994 Tiger (T=4T=4) 0.0 5 0.000 16 16 1.000 GridWorld 3×33×3 (T=2T=2) 0.3 1 0.233 6 4 0.981 GridWorld 3×33×3 (T=2T=2) 0.3 3 0.000 6 6 1.000 GridWorld 3×33×3 (T=2T=2) 0.3 5 0.000 6 6 1.000 7.5 Larger-Scale and Sensitivity Results Operational exact-for-family computation (|S|≤36|S|≤ 36). On the 5×55×5 GridWorld (|S|=25|S|=25, T=3T=3), 2222 operational exact classes reduce to 55 at ε=0.6 =0.6 (94%94\% compression). Random POMDPs (|S|=20|S|=20, T=3T=3) show 2222 operational exact classes reducing to 44 at ε≥0.1 ≥ 0.1. Scaling from |S|=9|S|=9 to |S|=36|S|=36 increases runtime from 0.030.03 s to 0.070.07 s (mildly growing over the tested range 9≤|S|≤369≤|S|≤ 36, where FSC enumeration dominates; the per-entry O(|S|2)O(|S|^2) belief propagation cost will dominate at larger |S||S|). Operational sampling-based case studies up to |S|=100|S|=100. Using sampling-based 1W_1 estimation (500500 trajectories per history-policy pair), we study the operational quotient Qm,TopQ^op_m,T on POMDPs with |S||S| up to 100100 (Table 6). On the 10×1010×10 GridWorld (|S|=100|S|=100), the quotient produces 66 operational exact classes at ε=0 =0, compressing to 44 at ε=0.25 =0.25 and 33 at ε≥0.45 ≥ 0.45—the same qualitative pattern as smaller grids, with cache construction in 0.300.30 s. Random structured POMDPs with |S|=100|S|=100 collapse rapidly to 33 classes at ε≥0.1 ≥ 0.1. Convergence analysis on GridWorld 3×33×3 (where operational exact-for-family computation is feasible) confirms that 500500 trajectories achieve mean ARI=0.998=0.998 (min 0.970.97, 55 replications) versus the operational exact partition; even 5050 trajectories yield mean ARI=0.99=0.99. Furthermore, partition class counts are perfectly stable across 1010 independent random seeds at 500500 trajectories (std=0=0 at all ε ), indicating that the sampling noise is well below the clustering threshold. Bootstrap confidence intervals (1,0001,000 resamples) on the maximum pairwise 1W_1 distance confirm tight estimation: CI widths are ≤0.10≤0.10 for all benchmarks at 500500 trajectories (Table 6), well below the coarsest ε=0.45 =0.45 threshold that drives the clustering. These medium-scale results belong to the paper’s operational case-study tier rather than the appendix-only archival stress tier: all rows use deterministic-stationary m=1m=1 probes, horizon T=2T=2, and the stated 500500-trajectory / 1,0001,000-bootstrap protocol. They should be read as evidence about the tractable coarsening Qm,TopQ^op_m,T and its approximation behaviour, not as direct validation of the clock-aware theorem object Qm,TclkQ^clk_m,T. Table 6: Operational quotient class counts (m=1m=1, T=2T=2, sampling-based, 500500 trajectories). The 95% CI column reports the bootstrap confidence interval on maxh,h′1 _h,h W_1 (1,0001,000 resamples). Total histories are ∑d=0T|O|d _d=0^T|O|^d: 2121 for |O|=4|O|=4 benchmarks, 1313 for |O|=3|O|=3 (RockSample). Benchmark |S||S| ε=0 =0 ε=0.1 =0.1 ε=0.25 =0.25 ε=0.45 =0.45 Cache (s) 95% CI on max1 _1 GridWorld 8×88×8 64 6 6 4 3 0.28 [0.32, 0.41][0.32,\,0.41] GridWorld 10×1010×10 100 6 6 4 3 0.30 [0.33, 0.42][0.33,\,0.42] RockSample(4,4)(4,4) 257 5 5 4 3 0.48 [0.35, 0.47][0.35,\,0.47] Random |S|=50|S|=50 50 6 3 3 3 0.22 [0.02, 0.11][0.02,\,0.11] Random |S|=100|S|=100 100 6 3 3 3 0.35 [0.02, 0.11][0.02,\,0.11] RockSample(4,4)(4,4): a semi-realistic benchmark. To move beyond grid navigation, we evaluate on the RockSample(4,4)(4,4) POMDP (|S|=257|S|=257, 99 actions, 33 observations), a standard planning benchmark where an agent must navigate a 4×44×4 grid, check rock quality via noisy distance-dependent sensors, and sample good rocks for reward. At m=1m=1 and T=2T=2, the quotient produces 55 probe-exact classes at ε=0 =0, compressing to 44 at ε=0.25 =0.25 and 33 at ε≥0.45 ≥ 0.45 (Table 6). The same monotonic compression pattern holds as on smaller benchmarks, confirming that the framework applies to structured domains beyond toy grids. Cache construction completes in 0.480.48 s, consistent with the O(|S|2)O(|S|^2) scaling. Appendix-only archival stress tracks. Appendix G.3 records the optional long-horizon, large-state, and higher-memory operational stress tests. We keep those rows out of the core validation narrative because they are computationally heavier, rely on heuristic calibrated subsets or sampling at the largest scales, and are not required to verify the theorem-aligned claims in the main paper. For inspection without rerunning the heaviest jobs, the repository includes a precomputed Tier I package under artifacts/tier3/ together with verify_tier3_artifacts.py; the intent is that reviewers can audit the reported rows without treating multi-hour reruns as part of the paper’s default verification target. Data-processing monotonicity validation. We experimentally validate Theorem 5.3 by coarsening GridWorld observations from 44 (NW/NE/SW/SE) to 22 (North/South), merging NW++NE and SW++SE. On 3×33×3: the original maxD1,2=0.343 D_1,2^W=0.343 reduces to 0.1670.167 after coarsening; on 5×55×5: 0.3540.354 reduces to 0.1750.175. The deterministic merging has Lipschitz constant LC=1L_C=1, and monotonicity D(coarsened)≤LC⋅D(original)D^W(coarsened)≤ L_C· D^W(original) holds at all 1313 tested ε values for both grids, confirming Theorem 5.3. This 4→24→ 2 merging is a special case of δO _O-coarsening (Definition 5.4) with δO=0.5 _O=0.5 under the geometric observation metric, confirming Proposition 5.5(a). Sensitivity and additional benchmarks. Effective dimension (deff=exp(H(b))d_eff= (H(b)), where H(b)H(b) is the Shannon entropy of the belief) is substantially smaller than |S||S| in structured benchmarks, yielding 1.8×1.8×–3.0×3.0× tighter worst-case bounds (though the canonical Prop A.1 bound remains vacuous at moderate ε , reaching 17×17× the empirical error at ε=0.5 =0.5; see Table 16); observation noise sensitivity is detailed in Appendix G. Two additional benchmarks—Hallway (1D corridor, |S|≤20|S|≤ 20) and Network Monitoring (factored binary-failure nodes, |S|=2n|S|=2^n)—confirm the same monotonicity patterns with compression ratios comparable to Tiger and GridWorld. Downstream planning with real rewards. We test whether quotient compression preserves planning quality by exhaustive policy search using the actual POMDP reward function (via VMπV^π_M and VM¯πV^π_ M from Theorem 3.6). On Tiger (m∈1,2m∈\1,2\, up to 147 FSCs) and a goal-reward GridWorld (3×33×3, |S|=9|S|=9, m=1m=1, 5 FSCs), we select the best policy on the quotient and evaluate it on the original. GridWorld at T=3T=3 compresses 85 histories to 4 classes (95% reduction at ε=1.0 =1.0) with zero value gap: the quotient-selected policy is optimal on the original in all 30 configurations tested. In the single case where a different policy is selected (ε=0.25 =0.25, T=3T=3), it achieves the same value, illustrating that bounded-agent indistinguishability merges histories without discarding decision-relevant information. 1W_1 vs. TV: metric structure matters. To demonstrate that the Wasserstein pseudometric leverages observation-space structure, we compare 1W_1 (with the geometric ground metric) against total variation (the discrete 0/10/1 metric) on GridWorld 5×55×5 at m=1m=1, T=2T=2. At ε=0 =0 both metrics yield 66 equivalence classes, as expected. At ε=0.3 =0.3, 1W_1 produces 44 classes while TV still yields 66: the Wasserstein metric recognizes that adjacent quadrant observations are spatially close, merging histories that TV treats as maximally separated. This confirms the practical benefit of structured observation metrics motivated in Section 3: when observations carry geometric meaning, 1W_1 achieves strictly more compression at the same tolerance. Appendix Table 18 reports the broader small-benchmark baseline sweep against truncation, random partitions, belief-distance clustering, and a bisimulation baseline. We keep that fuller comparison in the appendix because it is useful for positioning, but not part of the theorem-facing evidence chain in the main paper. Quotient-accelerated planning. We test whether the materialized quotient POMDP can accelerate downstream planning by comparing point-based value iteration [PBVI; 40] on the original and quotient models (Table 7). On all benchmarks, the quotient preserves the optimal value with zero or near-zero value gap. RockSample(4,4)(4,4) (|S|=257|S|=257) achieves the most dramatic compression, reducing from 257257 states to 33–55 quotient states. Table 7: PBVI planning on original vs. quotient POMDPs (m=1m=1, T=3T=3, ε=0.5 =0.5). Speedup is measured as original PBVI time divided by total quotient pipeline time (partition + build + quotient PBVI). Benchmark |S||S| Quotient |S||S| PBVI orig (s) PBVI quot (s) Speedup Value gap Tiger 2 3 0.001 0.001 ∼1× 1× 0.00 GridWorld 3×33×3 9 6 0.003 0.002 1.9×1.9× 0.00 GridWorld 5×55×5 25 5 0.008 0.003 2.4×2.4× 0.00 Net. Monitor (n=4n=4) 16 4 0.005 0.002 2.1×2.1× 0.00 RockSample(4,4)(4,4) 257 3 0.092 0.004 15×15× 0.00 8 Discussion and Conclusion Limitations. Four limitations are explicit. First, the observation-Lipschitz value bound (Theorem 3.6) is the right fallback for latent-state objectives, but it can be loose—the bound achieves a 50% tightness ratio on an exact construction (inspection-choice POMDP) and is within 4×4× on Tiger (Table 16), confirming the LR⋅T⋅εL_R· T· form is structurally correct. For observation-measurable rewards, the exact quotient preserves value perfectly (Theorem 4.6). For latent-state rewards with large LRL_R (e.g. Tiger’s standard LR=110L_R=110), the bound is explicitly vacuous but structurally correct in T and ε ; GridWorld’s moderate LR≈2L_R≈ 2 yields an informative bound (Table 16, Panels B–C). Tighter bounds likely require exploiting belief concentration or reward structure. Second, the distinguishability lower bound remains open; Appendix F records this as an unresolved complexity question rather than a theorem claim. Third, worst-case scaling at larger m remains challenging; the |O|T|O|^T bottleneck from larger observation alphabets is only partially addressable through δO _O-coarsening (Proposition 5.5). Fourth, the framework assumes a known generative model (T,Z,R)(T,Z,R); the graceful degradation result (|D(M^)−D(M)|≤4Tδ|D^W( M)-D^W(M)|≤ 4Tδ for per-entry error δ) provides robustness but formal sample-complexity guarantees for the full pipeline remain open. Computationally, the 1W_1 linear programs dominate runtime: on the m=1m=1 benchmarks, the distance cache accounts for >99%>99\% of wall-clock time (Appendix, Table 24), confirming that LP solves are the bottleneck for scaling to larger state spaces. The operational story is deliberately weaker than the theorem and the paper’s formal claims stop at the certified part of it. Deterministic stationary probes are enumerable, admit subset certificates, and scale through layering and sampling. Proposition 4.11 and Theorem 4.12 make their relation to the theorem object quantitative on tractable exact cases: Qm,TopQ^op_m,T is a tractable coarsening of Qm,TclkQ^clk_m,T, and the measured gap δclk _clk certifies the extra additive value-transfer penalty. That is the only theorem-facing use we make of the operational pipeline. Where δclk _clk or δS _S is reported, the corresponding rows inherit a formal guarantee for the theorem-level family or for the stated operational family. Where no such measurement is available, the larger tables are outside the paper’s central claim set and are included only as exploratory diagnostics of Qm,TopQ^op_m,T itself: compression patterns, runtime, stability under sampling, and the practical cost of richer probe families. The role of Qm,TclkQ^clk_m,T is therefore not to be the scalable algorithmic object on every benchmark, but to serve as the canonical gold standard for the bounded-observer question itself. It pins down exactly what is preserved, proves uniqueness and minimality for that target, and supplies the reference object against which tractable coarsenings such as Qm,TopQ^op_m,T can be calibrated. Without that theorem object, the operational pipeline would be a heuristic compression procedure with no principled answer to what it is approximating. A practical reading of the clock-aware/stationary gap is now possible. We expect the gap to stay small on structured short-horizon problems when the same bounded controller state need not implement qualitatively different stage-dependent behaviours; that is exactly what the small exact benchmarks suggest. We expect it to matter when stage indexing itself carries strategic content, as in Proposition 4.10, or when revisiting the same controller state should trigger different actions at different times. Typical examples are finite-horizon countdown tasks, staged sensing-then-commit problems, or phase-based controllers whose intended behaviour changes near a deadline even when the internal memory node is revisited. For new domains, an engineering workflow is to start from the smallest (m,T)(m,T) that can express the policy class of interest, enlarge m or T only until partition statistics or downstream value stabilise, and, whenever a tractable exact instance is available, use the measured δclk _clk or δS _S certificate as the stopping criterion rather than raw size alone. This workflow guidance is heuristic rather than theorem-level: without those explicit certificates, the larger operational tables remain exploratory evidence about Qm,TopQ^op_m,T only. A central next step is now narrower: not to define the theory-to-operation gap, but to predict or upper-bound δclk _clk a priori without explicitly computing the clock-aware family, and to combine that with controller-subset or layering certificates at larger scales. Initial-belief dependence. The quotient partition depends on the initial belief b0b_0 through the belief posteriors bhb_h that determine conditional observation laws. Under a different initial belief b0′b_0 , the equivalence classes may change: histories indistinguishable under b0b_0 could become distinguishable under b0′b_0 if the posteriors shift enough to alter observation-law ordering. We validate experimentally that the partition is stable under moderate perturbations of b0b_0 (see supplementary experiments), consistent with the continuity of bhb_h in b0b_0. Future directions. These limitations point to a clear research program: closing the gap between worst-case bounds and empirical behavior. The operational exact-for-family benchmark results partially close this gap operationally: on Tiger and GridWorld 3×33×3, greedy-selected subsets achieve δS=0 _S=0, so Theorem 6.2 applies directly. What remains open is predicting or bounding small δS _S without constructing the full deterministic-stationary FSC tensor, using cheaper surrogates such as submodular coverage, anchor rank, or Hankel rank, with effective-rank summaries treated only as possible descriptive surrogates rather than the target quantity itself. Conjecture 8.1 (Operational subset rank and predictive complexity). Let renv(M,m,T,δ):=min|S|:S⊆Πm,Tdet,‖d−dS‖∞≤δr_env(M,m,T,δ):= \|S|:S _m,T^det,\ \|d-d_S\|_∞≤δ \ be the minimum controller-subset size achieving probe-envelope error at most δ. For POMDPs with low intrinsic predictive complexity, renv(M,m,T,δ)r_env(M,m,T,δ) is polynomially controlled by open-loop predictive structure, such as the Hankel rank rH(M,T)r_H(M,T), together with (m,|A|,δ−1)(m,|A|,δ^-1). Evidence. On Tiger and GridWorld 3×33×3, greedy selection attains renv(M,m,T,0)≤5r_env(M,m,T,0)≤ 5 on the operational exact-for-family m=2m=2 benchmarks (Table 5). On GridWorld 3×33×3, the open-loop Hankel rank computed from the observation kernels is 33, consistent with a small gap between predictive complexity and operational subset size. Anchor rank remains a stricter structural sufficient notion: any δ-anchor family of size r implies renv(M,m,T,δ)≤r_env(M,m,T,δ)≤ r, but the present experiments do not certify anchor-family membership. Toward tighter latent-state bounds. The observation-Lipschitz value bound (Theorem 3.6) with the reward-range upper bound on LRL_R is intentionally conservative for latent-state objectives, and the exact sufficiency guarantee (Theorem 4.6) applies only to agent-accessible objectives in obsG_obs. Four avenues could tighten the latent-state story without abandoning the bounded-agent perspective. First, reward-aware probe families—enriching the probe class with controllers whose action-selection explicitly depends on the reward-relevant partition of observations—could reduce the effective LRL_R by aligning the pseudometric with reward-relevant distinctions rather than observation-level ones. Second, a hybrid exact/approximate decomposition could split the reward into an observation-measurable component (handled exactly by Theorem 4.6) and a latent residual (bounded by the Lipschitz term), yielding a strictly tighter composite bound whenever the observation-measurable component is nonzero. Third, belief concentration results that exploit specific POMDP structure (e.g., posterior convergence under informative observations) could sharpen the per-stage observation-Lipschitz constant beyond the worst-case LRL_R. Fourth, dual-side bounding via retention capacity: the current bound takes LRL_R as the worst-case reward sensitivity over all policies in the probe family, but an agent with finite retention ρ cannot sustain the full policy space and therefore cannot exploit the fine distinctions that drive LRL_R to its worst case. Restricting the sup in the Lipschitz constant to the sustainable policy subset could yield an effective LReff(ρ)<LRL_R^eff(ρ)<L_R, potentially making the bound non-vacuous in regimes where the full-family bound is not. This direction is developed in companion work on sustainable quotients. Three paths extend this model-based framework toward settings with unknown dynamics. First, when a model M M is learned from data with per-entry errors δT,δZ≤δ _T, _Z≤δ, a telescoping argument yields |Dm,T(M^)−Dm,T(M)|≤4Tδ|D_m,T^W( M)-D_m,T^W(M)|≤ 4Tδ, so the quotient degrades gracefully under model estimation error. Second, the sampling-based distance cache (Algorithm 1) already operates on trajectories rather than explicit transition matrices; in principle, these trajectories could come from a real environment or simulator rather than a known model, yielding a model-free variant at the cost of sample complexity. Third, the canonical quotient suggests a representation-learning objective: an encoder that maps observation histories into a space preserving the bounded-interaction pseudometric would recover the quotient’s equivalence classes, connecting this framework to deep bisimulation methods. Further natural extensions include infinite-horizon discounted POMDPs and PAC-Bayes bounds for bounded agents. More broadly, this work offers a principled vocabulary for reasoning about when two environments are the same from a bounded agent’s perspective. The canonical quotient gives the theory object; the operational coarsening shows how much of that object survives contact with tractability. Dual-side bounding and retention capacity. The quotient developed here bounds from the world side: it reduces the state space to what a (m,T)(m,T)-bounded agent can distinguish. A symmetric reduction applies from the policy side. An agent with finite retention—modelled by a learning-forgetting ratio ρ=λ+/λ−ρ=λ^+/λ^-, where λ+λ^+ is the rate of acquiring new distinctions and λ−λ^- the rate of losing them—cannot sustain all policies available to an (m,T)(m,T)-agent with perfect memory; the effective policy space is a ρ-dependent subset. The resulting sustainable quotient Qm,T,ρQ_m,T,ρ is the canonical abstraction for an agent bounded on both sides, with the static quotient Qm,TQ_m,T recovered as the ρ→∞ρ→∞ limit. This extension, including a dynamic Myhill–Nerode theorem, the birth-death dynamics of quotient evolution under learning and forgetting, and applications to multi-agent coordination under communication constraints, is developed in companion work. Broader impact. This work is a foundational theoretical contribution to POMDP abstraction and does not introduce new algorithms deployed in safety-critical systems. The framework could improve the efficiency of planning under partial observability in robotics, autonomous systems, and resource-constrained agents, where principled abstraction reduces computational cost while providing formal guarantees on information loss. As with any model-compression technique, there is a dual-use potential: abstraction that simplifies planning for beneficial agents could equally simplify planning for adversarial ones, though the bounded-agent assumption limits the scope of such concerns. We foresee no direct negative societal impacts from this work. Reproducibility. Code and experiments are available at https://github.com/alch3mistdev/finite-pomdp-abstraction. Appendix G records benchmark definitions, parameter grids, convergence checks, timing tables, an explicit command-to-table mapping, and a three-tier reproduction contract (Table 9). The pinned software stack is the repository’s requirements.txt (numpy, scipy, pandas, matplotlib); all timed tables use the serial configuration (--no-parallel) so that runtimes are directly comparable across machines, even though the experiment driver can optionally launch process-level parallel workers for non-timing runs. Tier 1 reruns the theorem tables and the operational core tables through Table 6; on the reported hardware, that verification target completes in under 3 minutes. Tier 2 adds the long-horizon package (Tables 10 and 11) and takes roughly 10 minutes serial from the reported row totals. Tier 3 contains the heaviest operational stress rows, including the largest configurations in Table 14, which can require up to 2 hours and are reported as optional archival stress tests rather than prerequisites for the theorem claims. For those Tier 3 rows, artifact-level inspection through the precomputed package under artifacts/tier3/ is the intended default verification path; the repository includes CSV transcriptions of the reported stress-track rows, a runtime/certificate crosswalk, and a lightweight verifier script (python artifacts/tier3/verify_tier3_artifacts.py) that confirms the archived rows match the paper’s reported values in under one second. All reported runtimes were measured on a MacBook Pro with an Apple M3 Pro chip (12 cores, 36 GB RAM) running macOS 26.3.1. On machines with different CPUs, Tier 1 runtimes should scale roughly with single-core throughput; we expect 1.5×1.5×–3×3× variation relative to the M3 Pro baseline on contemporary x86 and ARM hardware. Tier 3 runtimes depend more on LP solver performance in SciPy’s HiGHS backend and may show wider variation. References [1] Abel, D., Hershkowitz, D. E., and Littman, M. L. (2016). Near optimal behavior via approximate state abstraction. In ICML, p. 2915–2923. [2] Abel, D. (2022). A Theory of Abstraction in Reinforcement Learning. PhD thesis, Brown University. [3] Amato, C., Bernstein, D. S., and Zilberstein, S. (2010). Optimizing fixed-size stochastic controllers for POMDPs and decentralized POMDPs. Autonomous Agents and Multi-Agent Systems, 21(3):293–320. [4] Balle, B., Hamilton, W. L., and Pineau, J. (2014). Methods of moments for learning stochastic languages. In ICML, p. 1386–1394. [5] Berger, T. (1971). Rate Distortion Theory. Prentice-Hall. [6] Blackwell, D. (1953). Equivalent comparisons of experiments. Ann. Math. Stat., 24(2):265–272. [7] Boots, B., Siddiqi, S. M., and Gordon, G. J. (2011). Closing the learning-planning loop with predictive state representations. IJRR, 30(7):954–966. [8] Calo, A., Anders, C. J., Schulz, S., and Müller, K.-R. (2024). Bisimulation metrics are optimal transport distances, and can be computed efficiently. In NeurIPS. [9] Carr, S., Jansen, N., and Topcu, U. (2023). Simplifying POMDP verification with bisimulation-based abstractions. In AAAI, p. 6162–6170. [10] Castro, P. S. (2009). Equivalence Notions and Model Minimization in MDPs. PhD thesis, McGill University. [11] Castro, P. S. and Precup, D. (2010). Using bisimulation for policy transfer in MDPs. In AAAI, p. 1065–1070. [12] Castro, P. S. (2020). Scalable methods for computing state similarity in deterministic MDPs. In AAAI, p. 10069–10076. [13] Crutchfield, J. P. and Young, K. (1989). Inferring statistical complexity. Phys. Rev. Lett., 63(2):105–108. [14] Dean, T. and Givan, R. (1997). Model minimization in Markov decision processes. In AAAI, p. 106–111. [15] Desharnais, J., Gupta, V., Jagadeesan, R., and Panangaden, P. (2004). Metrics for labelled Markov processes. TCS, 318(3):323–354. [16] Even-Dar, E., Kakade, S. M., and Mansour, Y. (2007). The value of observation for monitoring dynamic systems. In IJCAI, p. 2474–2479. [17] Ferns, N., Panangaden, P., and Precup, D. (2004). Metrics for finite Markov decision processes. In UAI, p. 162–169. [18] Ferns, N., Panangaden, P., and Precup, D. (2011). Bisimulation metrics for continuous Markov decision processes. SIAM J. Comput., 40(6):1662–1714. [19] Ferns, N., Castro, P. S., Precup, D., and Panangaden, P. (2012). Methods for computing state similarity in MDPs. In UAI, p. 174–183. [20] Gelada, C., Kumar, S., Buckman, J., Nachum, O., and Bellemare, M. G. (2019). DeepMDP: Learning continuous latent space models. In ICML, p. 2170–2179. [21] Genewein, T., Leibfried, F., Grau-Moya, J., and Braun, D. A. (2015). Bounded rationality, abstraction, and hierarchical decision-making. Frontiers in Robotics and AI, 2:27. [22] Hansen, E. A. (1998). Solving POMDPs by searching in policy space. In UAI, p. 211–219. [23] Hopcroft, J. E. and Ullman, J. D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. [24] Hsu, D., Kakade, S. M., and Zhang, T. (2012). A spectral algorithm for learning hidden Markov models. J. Comput. Syst. Sci., 78(5):1460–1480. [25] Jaeger, H. (2000). Observable operator models for discrete stochastic time series. Neural Computation, 12(6):1371–1398. [26] Kaelbling, L. P., Littman, M. L., and Cassandra, A. R. (1998). Planning and acting in partially observable stochastic domains. Artif. Intell., 101(1–2):99–134. [27] Kemertas, M. and Aumentado-Armstrong, T. (2022). Towards robust bisimulation metric learning. In NeurIPS. [28] Larsen, K. G. and Skou, A. (1991). Bisimulation through probabilistic testing. Inf. Comput., 94(1):1–28. [29] Li, L., Walsh, T. J., and Littman, M. L. (2006). Towards a unified theory of state abstraction for MDPs. In AI&M, p. 531–539. [30] Littman, M. L., Sutton, R. S., and Singh, S. (2001). Predictive representations of state. In NeurIPS, p. 1555–1561. [31] Liu, M., Zhu, Z., and Jha, S. (2023). Partially observable RL with B-stability: unified structural conditions and efficient algorithms. In NeurIPS. [32] Madani, O., Hanks, S., and Condon, A. (2003). On the undecidability of probabilistic planning. Artif. Intell., 147(1–2):5–34. [33] Massey, J. L. (1990). Causality, feedback and directed information. In ISITA, p. 303–305. [34] Myhill, J. (1957). Finite automata and the representation of events. WADD Tech. Rep., 57–624. [35] Nemhauser, G. L., Wolsey, L. A., and Fisher, M. L. (1978). An analysis of approximations for maximizing submodular set functions—I. Math. Program., 14(1):265–294. [36] Nerode, A. (1958). Linear automaton transformations. Proc. AMS, 9(4):541–544. [37] Panangaden, P. (2009). Labelled Markov Processes. Imperial College Press. [38] Papadimitriou, C. H. and Tsitsiklis, J. N. (1987). The complexity of Markov decision processes. Math. Oper. Res., 12(3):441–450. [39] Paz, A. (1971). Introduction to Probabilistic Automata. Academic Press. [40] Pineau, J., Gordon, G., and Thrun, S. (2003). Point-based value iteration: An anytime algorithm for POMDPs. In IJCAI, p. 1025–1032. [41] Poupart, P. and Boutilier, C. (2003). Bounded finite state controllers. In NeurIPS, p. 823–830. [42] Rutten, J. J. M. M. (2000). Universal coalgebra: A theory of systems. TCS, 249(1):3–80. [43] Shalizi, C. R. and Crutchfield, J. P. (2001). Computational mechanics: Pattern and prediction, structure and simplicity. J. Stat. Phys., 104(3/4):817–879. [44] Shannon, C. E. (1959). Coding theorems for a discrete source with a fidelity criterion. IRE Natl. Conv. Rec., 7(4):142–163. [45] Sims, C. A. (2003). Implications of rational inattention. J. Monet. Econ., 50(3):665–690. [46] Smallwood, R. D. and Sondik, E. J. (1973). The optimal control of partially observable Markov processes over a finite horizon. Oper. Res., 21(5):1071–1088. [47] Sutton, R. S., Precup, D., and Singh, S. (1999). Between MDPs and semi-MDPs: Temporal abstraction in RL. Artif. Intell., 112(1–2):181–211. [48] Tatikonda, S. and Mitter, S. K. (2000). Control under communication constraints. In IEEE CDC, p. 269–274. [49] Torgersen, E. (1991). Comparison of Statistical Experiments. Cambridge Univ. Press. [50] Zhang, A., McAllister, R., Calandra, R., Gal, Y., and Levine, S. (2021). Learning invariant representations for RL without reconstruction. In ICLR. [51] Tishby, N., Pereira, F. C., and Bialek, W. (1999). The information bottleneck method. In Proceedings of the 37th Annual Allerton Conference on Communication, Control, and Computing, p. 368–377. [52] Yao, A. C.-C. (1979). Some complexity questions related to distributive computing (preliminary report). In Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC), p. 209–213. [53] Miller, G. A. (1956). The magical number seven, plus or minus two: Some limits on our capacity for processing information. Psychological Review, 63(2):81–97. [54] Cowan, N. (2001). The magical number 4 in short-term memory: A reconsideration of mental storage capacity. Behavioral and Brain Sciences, 24(1):87–114. [55] Fournier, N. and Guillin, A. (2015). On the rate of convergence in Wasserstein distance of the empirical measure. Probability Theory and Related Fields, 162(3–4):707–738. Supplementary Material Appendix A Full Proofs A.1 Proof of Proposition 3.2 Proof. Non-negativity and symmetry are inherited from 1W_1. The triangle inequality follows from Dm,T(M,L)=supπ1(PMπ,PLπ)≤supπ[1(PMπ,PNπ)+1(PNπ,PLπ)]≤Dm,T(M,N)+Dm,T(N,L).D_m,T^W(M,L)= _πW_1(P_M^π,P_L^π)\\ ≤ _π [W_1(P_M^π,P_N^π)+W_1(P_N^π,P_L^π) ]≤ D_m,T^W(M,N)+D_m,T^W(N,L). The equivalence Dm,T(M,N)=0⇔PMπ=PNπD_m,T^W(M,N)=0 P_M^π=P_N^π for all π follows because 1(P,Q)=0⇔P=QW_1(P,Q)=0 P=Q on finite spaces. ∎ A.2 Proof of Theorem 3.6 (Value-function error bound) Proof. Fix π∈Ππ∈ . The value function decomposes per-step as VMπ=∑t=0T−1Mπ[R¯(ht,π)]V_M^π= _t=0^T-1E_M^π[ R(h_t,π)], where ht∈Oth_t∈ O^t is the random observation history at depth t and R¯(h,π)≔∑sbh(s)∑aπ(a∣h)R(s,a) R(h,π) _sb_h(s) _aπ(a h)\,R(s,a). By hypothesis, the quotient M~ M is constructed from a partition with pairwise probe-distance at most ε . By the observation-Lipschitz condition (Definition 3.4), the per-step expected reward difference at any history h satisfies |R¯M(h,π)−R¯M~(h,π)|≤LR⋅1(PMπ(Ot+1:T∣h),PM~π(Ot+1:T∣h))| R_M(h,π)- R_ M(h,π)|≤ L_R·W_1(P_M^π(O_t+1:T h),\,P_ M^π(O_t+1:T h)). The quotient model’s conditional suffix law at h is a convex combination of the conditional laws of h’s class members, all of which have pairwise distance at most ε under every π. By convexity of 1W_1, the cross-model conditional discrepancy satisfies 1(PMπ(Ot+1:T∣h),PM~π(Ot+1:T∣h))≤εW_1(P_M^π(O_t+1:T h),P_ M^π(O_t+1:T h))≤ . Summing over T steps yields |VMπ−VM~π|≤LR⋅T⋅ε|V_M^π-V_ M^π|≤ L_R· T· . For the canonical quotient QcanQ^can of Proposition A.1, the partition has pairwise probe-distance at most ε , so the bound is |VMπ−VQcanπ|≤LR⋅T⋅ε|V_M^π-V_Q^can^π|≤ L_R· T· . ∎ A.3 Proof of Proposition 4.2 Proof. (a) Reflexivity: 1(P,P)=0W_1(P,P)=0. Symmetry: 1(P,Q)=1(Q,P)W_1(P,Q)=W_1(Q,P). Transitivity: if 1(PMπ(⋅∣h),PMπ(⋅∣h′))=0W_1(P_M^π(· h),P_M^π(· h ))=0 and 1(PMπ(⋅∣h′),PMπ(⋅∣h′))=0W_1(P_M^π(· h ),P_M^π(· h ))=0 for all π, then by the triangle inequality for 1W_1, 1(PMπ(⋅∣h),PMπ(⋅∣h′))=0W_1(P_M^π(· h),P_M^π(· h ))=0 for all π. (b) Appending observation z to equivalent histories h,h′h,h : fix π∈Πm,Tπ∈ _m,T and write μhπ(z′,x) _h^π(z ,x) :=PMπ(Ot+1=z′,Ot+2:T=x∣h), :=P_M^π(O_t+1=z ,\,O_t+2:T=x h), μh′π(z′,x) _h ^π(z ,x) :=PMπ(Ot+1=z′,Ot+2:T=x∣h′). :=P_M^π(O_t+1=z ,\,O_t+2:T=x h ). Since h≡m,Th′h _m,Th , these joint laws on O×OT−t−1O× O^T-t-1 are identical: μhπ=μh′π _h^π= _h ^π. On a finite space, this common joint law admits a regular conditional kernel Kπ(x∣z′)K_π(x z ) for the suffix given the next observation, with any zero-mass z′z handled by an arbitrary common choice (the choice is immaterial: zero-mass observations contribute zero weight to expectations and Wasserstein computations, so the conclusion is convention-independent). Therefore PMπ(Ot+2:T=x∣h⋅z)=Kπ(x∣z)=PMπ(Ot+2:T=x∣h′⋅z)P_M^π(O_t+2:T=x h· z)=K_π(x z)=P_M^π(O_t+2:T=x h · z) for all suffixes x. Since π was arbitrary, h⋅z≡m,Th′⋅zh· z _m,Th · z. (c) Finiteness: O and T are finite, so the number of histories ∑t=0T|O|t _t=0^T|O|^t is finite. ∎ A.4 Proof of Theorem 4.4 (Myhill–Nerode) Proof. (i) Well-definedness. Under ε=0 =0, the observation law PMπ(Ot+1:T∣h)P_M^π(O_t+1:T h) is identical for all h∈[h]h∈[h] and all π. Constant-action FSCs (always play action a) are in Πm,T _m,T for any m≥1m≥ 1, so equivalence under all policies implies per-action agreement of one-step observation probabilities. For any h,h′∈[h]h,h ∈[h], action a, and observation z: ∑s′Z(s′,a,z)∑sP(s,a,s′)bh(s)=∑s′Z(s′,a,z)∑sP(s,a,s′)bh′(s) _s Z(s ,a,z) _sP(s,a,s )b_h(s)= _s Z(s ,a,z) _sP(s,a,s )b_h (s), since both equal PMπ(Ot+1=z∣h,a)P_M^π(O_t+1=z h,a) under the constant-a policy. Any convex combination b¯[h] b_[h] therefore yields the same P¯([h],a,[h⋅z]) P([h],a,[h· z]), as the linear map b↦P¯b P takes a common value. Proposition 4.2(b) then ensures successor classes are well-defined. (i) Soundness. By induction on t. Base: PMπ(ϵ)=PQπ(ϵ)=1P_M^π(ε)=P_Q^π(ε)=1. Step: PMπ(o1,…,ot+1)=PMπ(o1,…,ot)⋅PMπ(ot+1∣ht,at)P_M^π(o_1,…,o_t+1)=P_M^π(o_1,…,o_t)· P_M^π(o_t+1 h_t,a_t). By well-definedness, PMπ(ot+1∣ht,at)=P¯([ht],at,[ht⋅ot+1])P_M^π(o_t+1 h_t,a_t)= P([h_t],a_t,[h_t· o_t+1]). The FSC state depends on the observation sequence identically in both systems, so the induction extends. (i) Universality. Let ≡m,TN≡^N_m,T be the probe-exact bounded-agent equivalence on histories of N and write [h]N[h]_N for its classes. Let Q=Qm,T(M)Q=Q_m,T(M) and write [h]M[h]_M for the quotient classes of M. Since PNπ(OT)=PMπ(OT)P_N^π(O^T)=P_M^π(O^T) for every π, all cylinder probabilities PNπ(hx)P_N^π(hx) and PMπ(hx)P_M^π(hx) agree, hence on the finite history space their conditional future laws PNπ(Ot+1:T∣h)P_N^π(O_t+1:T h) and PMπ(Ot+1:T∣h)P_M^π(O_t+1:T h) agree as well (with the same arbitrary convention on zero-probability histories). Define ϕ([h]N):=[h]M.φ([h]_N):=[h]_M. This is well-defined: if [h]N=[h′]N[h]_N=[h ]_N, then by definition of ≡m,TN≡^N_m,T the conditional future laws from h and h′h coincide in N, hence also in M, so h≡m,Th′h _m,Th and therefore [h]M=[h′]M[h]_M=[h ]_M. Surjectivity is immediate because every class [h]M[h]_M has the preimage [h]N[h]_N. We now verify the morphism axioms explicitly. • (M1). ϕ([ϵ]N)=[ϵ]Mφ([ε]_N)=[ε]_M by definition. • (M2). For any class C=[h]NC=[h]_N and policy π, PNπ(Ot+1:T∣C) P_N^π(O_t+1:T C) =PNπ(Ot+1:T∣h)=PMπ(Ot+1:T∣h) =P_N^π(O_t+1:T h)=P_M^π(O_t+1:T h) =PQπ(Ot+1:T∣[h]M)=PQπ(Ot+1:T∣ϕ(C)), =P_Q^π(O_t+1:T [h]_M)=P_Q^π(O_t+1:T φ(C)), where the first equality uses that C is an ≡m,TN≡^N_m,T-class, the middle equality is the conditional-law transfer above, and the fourth equality is soundness of Q. • (M3). By Proposition 4.2(b), right-appending observations respects both equivalence relations, so for any class C=[h]NC=[h]_N, ϕ(δN(C,a,z))=ϕ([h⋅z]N)=[h⋅z]M=δQ([h]M,a,z)=δQ(ϕ(C),a,z).φ( _N(C,a,z))=φ([h· z]_N)=[h· z]_M= _Q([h]_M,a,z)= _Q(φ(C),a,z). (iv) Minimality. Universality gives a surjection ϕ:ℋN↠ℋQφ _N _Q, so |ℋN|≥|ℋQ||H_N|≥|H_Q|. (v) Uniqueness. If Q′Q also satisfies (i)–(iv), universality yields morphisms ϕ:Q′↠Qφ:Q Q and ψ:Q↠Q′ψ:Q Q . Both compositions are surjective endomorphisms on finite sets, hence bijections. ∎ A.5 Proof of Theorem 4.6 (Exact sufficiency) Proof. We show by induction on t that for every π∈Πm,Tclkπ∈ ^clk_m,T, PMπ(O1:t,A1:t)=PQm,Tclk(M)π(O1:t,A1:t),t=0,1,…,T.P_M^π(O_1:t,A_1:t)=P_Q^clk_m,T(M)^π(O_1:t,A_1:t), t=0,1,…,T. Base case (t=0t=0). Both sides equal 11 (the empty trajectory has probability 11). Inductive step. Assume PMπ(O1:t,A1:t)=PQm,Tclk(M)π(O1:t,A1:t)P_M^π(O_1:t,A_1:t)=P_Q^clk_m,T(M)^π(O_1:t,A_1:t) for all realizations. By the soundness property of Theorem 4.4, the conditional observation law satisfies PMπ(Ot+1∣ht,at)=PQm,Tclk(M)π(Ot+1∣[ht],at)P_M^π(O_t+1 h_t,a_t)=P_Q^clk_m,T(M)^π(O_t+1 [h_t],a_t) for every history hth_t and action ata_t. The policy π∈Πm,Tclkπ∈ ^clk_m,T is a clock-aware bounded controller: its internal state qt+1q_t+1 evolves deterministically via qt+1=βt(qt,ot+1)q_t+1= _t(q_t,o_t+1) and its action is selected via at+1=αt+1(qt+1)a_t+1= _t+1(q_t+1) (deterministic case) or at+1∼αt+1(⋅∣qt+1)a_t+1 _t+1(· q_t+1) (stochastic case). In either case, the action at stage t+1t+1 is a measurable function of (o1:t+1,q1)(o_1:t+1,q_1), hence of the observation history alone (since q1q_1 is fixed). The joint law at stage t+1t+1 decomposes as Pπ(O1:t+1,A1:t+1)=Pπ(O1:t,A1:t)⋅Pπ(Ot+1∣ht,at)⋅Pπ(At+1∣o1:t+1).P^π(O_1:t+1,A_1:t+1)=P^π(O_1:t,A_1:t)· P^π(O_t+1 h_t,a_t)· P^π(A_t+1 o_1:t+1). All three factors on the right are equal in M and Qm,Tclk(M)Q^clk_m,T(M): the first by the inductive hypothesis, the second by soundness, and the third because π applies the same deterministic mapping to the same observation history. At t=Tt=T, we obtain PMπ(O1:T,A1:T)=PQm,Tclk(M)π(O1:T,A1:T)P_M^π(O_1:T,A_1:T)=P_Q^clk_m,T(M)^π(O_1:T,A_1:T). For any bounded measurable G∈obsG _obs, Mπ[G(O1:T,A1:T)] _M^π[G(O_1:T,A_1:T)] =∑(o,a)∈(O×A)TG(o,a)PMπ(o,a) = _(o,a)∈(O× A)^TG(o,a)\,P_M^π(o,a) =∑(o,a)∈(O×A)TG(o,a)PQm,Tclk(M)π(o,a)=Qm,Tclk(M)π[G(O1:T,A1:T)].∎ = _(o,a)∈(O× A)^TG(o,a)\,P_Q^clk_m,T(M)^π(o,a)=E_Q^clk_m,T(M)^π[G(O_1:T,A_1:T)]. A.6 Proof of Theorem 4.9 (Clock-aware witness theorem) Proof. By assumption, there exists stochastic clock-aware πθ∈Πm,Tclk _θ∈ _m,T^clk with PMπθ(⋅∣h)≠PMπθ(⋅∣h′)P_M _θ(· h)≠ P_M _θ(· h ). Hence for some suffix x∈OT−tx∈ O^T-t, f(θ):=PMπθ(x∣h)−PMπθ(x∣h′)≠0.f(θ):=P_M _θ(x h)-P_M _θ(x h )≠ 0. Multilinear vertex lemma: Let f:∏i=1kΔ(Xi)→ℝf _i=1^k (X_i) be multilinear with f(θ)≠0f(θ)≠ 0 for some θ. Writing θi=∑xθi(x)δx _i= _x _i(x) _x and expanding by multilinearity: f(θ)=∑x1,…,xkθ1(x1)⋯θk(xk)f(δx1,…,δxk)f(θ)= _x_1,…,x_k _1(x_1)·s _k(x_k)f( _x_1,…, _x_k). If all vertex values vanished, f would be identically zero. Hence some vertex θ∗θ^* has f(θ∗)≠0f(θ^*)≠ 0. Let θ collect the stage-indexed controller parameters θ=(α0,β0,…,αT−t−1,βT−t−1)∈Θm,Tclk.θ=( _0, _0,…, _T-t-1, _T-t-1)∈ _m,T^clk. For a fixed suffix x, each trajectory contributing to PMπθ(x∣h)P_M _θ(x h) uses exactly one action simplex and one node-transition simplex at each stage, so no parameter from stage τ is reused at a different time. Therefore f(θ)f(θ) is multilinear in the stage-indexed clock-aware FSC parameters. By the lemma, there exists a vertex θ∗θ^* with f(θ∗)≠0f(θ^*)≠ 0, i.e. a deterministic clock-aware FSC π∗π^* satisfying PMπ∗(x∣h)≠PMπ∗(x∣h′).P_M^π^*(x h)≠ P_M^π^*(x h ). ∎ A.7 Proof of Proposition 4.10 Proof. Consider the POMDP with states pL,pR,x0,y0,x1,y1,dU,dX,dY,\p_L,p_R,x_0,y_0,x_1,y_1,d_U,d_X,d_Y\, actions A,B\A,B\, observations L,R,U,X,Y\L,R,U,X,Y\, and initial belief b0=12δpL+12δpRb_0= 12 _p_L+ 12 _p_R. The transition/observation structure is: • from pLp_L (resp. pRp_R), either action moves to x0x_0 (resp. y0y_0) and emits L (resp. R); • from x0,y0x_0,y_0, action A moves to x1,y1x_1,y_1 and emits U, while action B moves to dUd_U from either branch and emits U; • from x1,y1x_1,y_1, action A moves to dUd_U from either branch and emits U, while action B moves to dXd_X from x1x_1 and to dYd_Y from y1y_1, emitting X and Y respectively; • dU,dX,dYd_U,d_X,d_Y are absorbing, with dUd_U always emitting U. For deterministic stationary 11-node FSCs there are only two controllers: always-A and always-B. Under always-A, after either history L or R the remaining suffix is deterministically UU. Under always-B, after either history L or R the remaining suffix is again deterministically UU. Hence every deterministic stationary 11-node FSC yields identical suffix laws from L and R, so the maximal distinguishing distance is 0. Now consider the stochastic stationary 11-node FSC with α(A)=α(B)=1/2α(A)=α(B)=1/2 and the unique node looping to itself after every observation. Conditioned on history L, with probability 1/21/2 the first post-history action is B, giving suffix UU, and with probability 1/21/2 it is A, which reaches x1x_1 and then yields UU with probability 1/21/2 and UXUX with probability 1/21/2. Therefore P(O2:3=UU∣L)=34,P(O2:3=UX∣L)=14.P(O_2:3=U L)= 34, P(O_2:3=UX L)= 14. Symmetrically, P(O2:3=UU∣R)=34,P(O2:3=UY∣R)=14.P(O_2:3=U R)= 34, P(O_2:3=UY R)= 14. Under the discrete observation metric, the induced sequence metric assigns distance 11 between UXUX and UYUY, so the 1-Wasserstein distance between these two suffix laws is 14 14. Thus a stochastic stationary 11-node FSC distinguishes L and R, while no deterministic stationary 11-node FSC does. ∎ A.8 Proof of Theorem 5.3 (Data-processing monotonicity) Proof. Let π′π be any FSC on (A′,O′)(A ,O ). The wrapper induces an FSC π on (A,O)(A,O) by composing through g and C. The observation sequence under π′π in W(M)W(M) is the pushforward of π’s observation sequence in M through C⊗TC T. By Kantorovich–Rubinstein duality and the Lipschitz property of C: 1(C#⊗TP,C#⊗TQ)≤LC⋅1(P,Q)W_1(C T_\#P,C T_\#Q)≤ L_C·W_1(P,Q). Taking the supremum over π′π yields the result. ∎ A.9 Proof of Proposition 5.5 (Observation-resolution bounds) Proof. (a) Under δO _O-coarsening, each observation o is replaced by qδ(o)q_δ(o) with dO(o,qδ(o))≤δOd_O(o,q_δ(o))≤ _O. At each time step t, the per-step contribution to 1W_1 shifts by at most δO _O due to the triangle inequality for dOd_O. Summing over T steps: Dm,T,δ≤Dm,T+T⋅δOD_m,T,δ^W≤ D_m,T^W+T· _O. (b) The coarsened history space has |Oδ|t|O_δ|^t histories at depth t, so at most ∑t=0T|Oδ|t _t=0^T|O_δ|^t classes. (c) The partition under Πm,T,δ _m,T,δ has Πm,T,δ _m,T,δ-diameter at most ε . At the history level, the same per-step δO _O shift from part (a) applies to conditional suffix laws: for any two histories h,h′h,h in the same class, dΠm,T(h,h′)≤dΠm,T,δ(h,h′)+TδO≤ε+TδOd _m,T(h,h )≤ d _m,T,δ(h,h )+T _O≤ +T _O. Hence the partition has Πm,T _m,T-diameter at most ε+TδO +T _O. Applying Theorem 3.6 with merge threshold ε+TδO +T _O: |VMπ−VQm,T,δπ|≤LR⋅T⋅(ε+TδO)|V_M^π-V_Q_m,T,δ^π|≤ L_R· T·( +T _O). ∎ A.10 Proof of Theorem 5.6 and Corollary 5.7 Proof. Define Γi:=Dm,T(Mi,M~i) _i:=D_m,T^W(M_i, M_i). For each layer i, the triangle inequality gives Dm,T(Mi+1,M~i+1)≤Dm,T(Wi(Mi),Wi(M~i))+Dm,T(Wi(M~i),M~i+1).D_m,T^W(M_i+1, M_i+1)≤ D_m,T^W\! (W_i(M_i),W_i( M_i) )+D_m,T^W\! (W_i( M_i), M_i+1 ). (10) Apply Theorem 5.3 to the first term and the assumed residual bound to the second: Γi+1≤LiΓi+εi. _i+1≤ L_i _i+ _i. (11) Unrolling this recursion by induction yields ΓL+1≤(∏j=1LLj)Γ1+∑i=1L(∏j=i+1LLj)εi, _L+1≤ ( _j=1^LL_j ) _1+ _i=1^L ( _j=i+1^LL_j ) _i, (12) which is exactly (6). For Corollary 5.7, apply Theorem 3.6 to the terminal partition-based quotient M~L+1 M_L+1 with merge threshold ΓL+1 _L+1: |VML+1π−VM~L+1π|≤LR⋅T⋅ΓL+1, |V_M_L+1^π-V_ M_L+1^π |≤ L_R· T· _L+1, (13) then substitute the layered bound on ΓL+1 _L+1 from above. ∎ A.11 Proof of Proposition 5.8 Proof. The monolithic term is the complexity of Algorithm 1 at horizon T: O(|O|T+1−1|O|−1⋅|A|mm|O|⋅T|S|2|O|).O\! ( |O|^T+1-1|O|-1·|A|^mm^m|O|· T|S|^2|O| ). (14) For layered construction with L segments of horizon τ, each segment costs O(|O|τ+1−1|O|−1⋅|A|mm|O|⋅τ|S|2|O|),O\! ( |O|^τ+1-1|O|-1·|A|^mm^m|O|·τ|S|^2|O| ), (15) and summing over L layers gives (9). Thus the exponential-in-horizon factor is paid at segment scale τ, multiplied linearly by L. ∎ A.12 Canonical quotient in the approximate setting Proposition A.1 (Canonical quotient). Define canonical aggregated belief b¯[h]can(s)=1|[h]ε|∑h~∈[h]εbh~(s) b_[h]^can(s)= 1|[h]_ | _ h∈[h]_ b_ h(s). Then: (i) Per-step: |P¯can([h],a,[h⋅z])−P¯π([h],a,[h⋅z])|≤2ε|S|| P^can([h],a,[h· z])- P^π([h],a,[h· z])|≤ 2 |S|. (i) Trajectory: 1(PQcanπ,PQπ)≤2Tε|S||O|W_1(P_Q^can^π,P_Q^π^π)≤ 2T |S||O|. (i) Combined: 1(PQcanπ,PMπ)≤ε(1+2T|S||O|)W_1(P_Q^can^π,P_M^π)≤ (1+2T|S||O|). Proof. Within an ε -class, all observation laws agree to within ε in 1W_1. The mapping b↦P¯b([h],a,⋅)b P^b([h],a,·) is linear in b, so any convex combination lies in the convex hull of values P¯bh~\ P^b_ h\, which has diameter at most ε per observation z. Propagating through |S||S| states and accounting for the convex hull diameter gives (i). Part (i) follows by telescoping across T steps and |O||O| observations. Part (i) by the triangle inequality: 1(PQcanπ,PMπ)≤2Tε|S||O|+εW_1(P_Q^can^π,P_M^π)≤ 2T |S||O|+ . ∎ A.13 Lipschitz continuity of observation laws Lemma A.2. For any finite POMDP M, θ↦PMπθ P_M _θ is Lipschitz continuous from (Θm,ℓ1)( _m, _1) to (Δ(OT),TV)( (O^T),TV). Proof. Each entry PMπθ(o1,…,oT)P_M _θ(o_1,…,o_T) is a multilinear polynomial in θ, hence Lipschitz on the compact domain Θm _m. ∎ Appendix B Structural Controller-Subset Conditions This appendix records a stricter structural sufficient condition for small probe-envelope error. The main text certifies selected subsets operationally through the measured quantity δS _S; the results here explain one route by which δS _S can be small, but they are not the quantity verified in Table 5. The correct structural condition for why a small controller subset preserves the partition is not ordinary spectral rank—a matrix can have small effective rank yet contain a single controller column that changes the rowwise maximum on a critical history pair—but rather a max-preserving convex-anchor rank. Definition B.1 (δ-anchor controller family). A controller subset A⊆1,…,PA \1,…,P\ is a δ-anchor family if for every controller p there exist coefficients λa,p≥0 _a,p≥ 0 with ∑a∈Aλa,p=1 _a∈ A _a,p=1 such that ‖D:,p−∑a∈Aλa,pD:,a‖∞≤δ. \|D_:,p- _a∈ A _a,p\,D_:,a \|_∞≤δ. Theorem B.2 (Anchor-controller compression). If A is a δ-anchor family of size r, then ‖d−dA‖∞≤δ\|d-d_A\|_∞≤δ. Hence the ε -quotient built from A satisfies |VMπ−VM~Aπ|≤LRT(ε+δ)∀π∈Πm,T.|V_M^π-V_ M_A^π|≤ L_R\,T\,( +δ) ∀\,π∈ _m,T. If δ=0δ=0, the anchor family recovers the probe-exact partition. Proof. Fix a history-pair row u. For any controller p, Du,p≤∑a∈Aλa,pDu,a+δ≤maxa∈ADu,a+δ=dA(u)+δD_u,p≤ _a∈ A _a,p\,D_u,a+δ≤ _a∈ AD_u,a+δ=d_A(u)+δ. Taking the maximum over p: d(u)≤dA(u)+δd(u)≤ d_A(u)+δ. Since A⊆1,…,PA \1,…,P\, also dA(u)≤d(u)d_A(u)≤ d(u). Therefore 0≤d(u)−dA(u)≤δ0≤ d(u)-d_A(u)≤δ for all u, i.e. ‖d−dA‖∞≤δ\|d-d_A\|_∞≤δ. The value bound follows from Theorem 6.2. ∎ Remark B.3 (Anchor rank vs. spectral rank). The minimum δ-anchor family size is a convex-hull approximation notion, related to approximate nonnegative factorization rather than SVD. Since every column of D is nonnegative, spectral effective rank upper-bounds anchor rank, but the two can differ. Anchor rank is the structurally correct quantity because it controls the rowwise-max approximation that determines partition quality; effective rank is at most a possible surrogate for it. Appendix C Extended Related Work State abstraction in RL. Li, Walsh, and Littman [29] provide a taxonomy of MDP state abstractions. Abel et al. [1] developed agent-aware state abstraction, and Abel’s thesis [2] provides a comprehensive category-theoretic account. Our framework adds a new axis: abstraction parametrized by agent memory m and horizon T. POMDP model minimization. Dean and Givan [14] introduced homogeneous partitions for MDPs. Castro [10] formalized exact bisimulation for POMDPs. Even-Dar et al. [16] studied the value of information in partial observability. Carr et al. [9] recently applied bisimulation-based abstractions to POMDP verification, and Liu et al. [31] introduced structural conditions for tractable partially observable RL. Blackwell and Torgersen’s comparison-of-experiments viewpoint [6, 49] is also relevant in spirit, but our comparisons are closed-loop and indexed by bounded policy classes rather than static observation channels. POMDP planning algorithms. Point-based value iteration [40] made approximate POMDP solving practical by sampling belief points rather than exhaustively partitioning the belief simplex, as in earlier exact methods [46]. Our quotient construction is complementary: it reduces the state space upstream of any solver, so PBVI (or any planner) operates on a smaller model with formal approximation guarantees. Bisimulation metrics. Ferns et al. [17, 18] showed TV-based bisimulation is topologically fragile and introduced Wasserstein-based metrics. Extensions to scalable algorithms [19] and continuous spaces [11] followed. Calo et al. [8] recently showed that bisimulation metrics are optimal-transport distances, providing efficient Sinkhorn-based computation; Kemertas and Aumentado-Armstrong [27] extended metric learning to robust settings. Our framework shifts from state-level bisimulation to history-level indistinguishability conditioned on bounded agents. The Calo et al. result is complementary: their efficient OT computation applies to the state-level Wasserstein distance in the bisimulation fixed-point iteration, whereas our 1W_1 is computed over observation-sequence distributions conditional on histories. In principle, their Sinkhorn acceleration could speed up the per-pair 1W_1 computation in Algorithm 1 when |O|T|O|^T is large, since each pairwise distance is itself an OT problem; however, our current bottleneck is the number of history pairs times the number of FSCs, not the per-entry OT solve (which uses |O|T|O|^T-dimensional distributions that are small for the bounded-agent regimes we target). The connection becomes more promising in the sampling-based regime at larger scales. Finite-state controllers. Poupart and Boutilier [41] popularized FSCs for POMDPs. Hansen [22] and Amato et al. [3] developed complementary optimization methods for fixed-size FSCs. We use FSCs as the probe class determining abstraction granularity. Rate–distortion and information constraints. Classical rate–distortion [44, 5], rational inattention [45], and information-theoretic bounded rationality [21] all inform our framework. The key distinction: POMDPs are closed-loop, requiring directed information [33, 48] rather than static Shannon theory. Predictive state representations. PSRs [30], OOMs [25], controlled PSRs [7], and spectral learning of stochastic languages [4] define state via predictions of future observations. Our framework differs: (1) closed-loop vs. open-loop tests, (2) environment equivalence classes vs. state representations, (3) explicit parametrization by agent capacity (m,T)(m,T). Controlled PSRs already incorporate actions, so the distinction is not simply “action-aware” versus “action-free.” The sharper difference is what is being minimised: PSR/OOM methods seek a predictive statistic of small linear dimension (rank of a Hankel-style operator or its controlled analogue), whereas our construction fixes a bounded controller family and asks which histories are indistinguishable to that family in closed loop. The FSC memory budget (m,T)(m,T) therefore measures observer capacity rather than predictive state dimension. We do not claim a general ordering between these parameters: low predictive rank need not imply that the rowwise-max probe envelope is captured by a small FSC subset, and a small bounded-controller quotient does not by itself imply low spectral rank. The low-rank structure of the FSC distance tensor parallels Hankel matrix rank in PSR/OOM theory. Concretely, the PSR Hankel matrix Hij=P(ot+1:T=xj∣o1:t=xi)H_ij=P(o_t+1:T=x_j o_1:t=x_i) captures open-loop predictive rank, while our tensor D(i,j),p=1(Pπp(⋅∣hi),Pπp(⋅∣hj))D_(i,j),p=W_1(P _p(· h_i),P _p(· h_j)) captures closed-loop distinguishing rank. Since any open-loop test sequence is realizable by a constant-action FSC, open-loop predictive complexity is a plausible surrogate for small operational subset rank renvr_env (Conjecture 8.1). Making that link precise—whether directly or via stricter structural notions such as anchor rank—would convert PSR/OOM-style predictive structure into controller-subset certificates for our quotient construction. Appendix B makes the anchor-rank notion formal: it is the minimum number of predictive rows needed to preserve every rowwise supremum appearing in the probe envelope, which is exactly the max-preserving quantity required by the quotient argument and not something low Hankel rank alone guarantees. Probabilistic bisimulation. Larsen and Skou [28] introduced probabilistic bisimulation for labelled Markov chains, extended to metrics by Desharnais et al. [15]. Neural bisimulation. Gelada et al. [20] (DeepMDP), Zhang et al. [50] (deep bisimulation metrics), and Castro [12] scale bisimulation to high-dimensional observations by learning encoder networks that minimize a bisimulation-inspired loss. These methods operate in the model-free, continuous-state regime—complementary to our model-based, finite-state framework. A natural bridge is to view the canonical quotient as a well-defined theoretical target: a deep encoder that maps observations into representations preserving the bounded-interaction Wasserstein pseudometric would, by construction, respect the quotient’s equivalence classes. Conversely, our value bound (Theorem 3.6) applies to any approximate quotient, including one produced by a learned encoder, provided the merging error ε can be certified. The gap between the two paradigms is primarily one of scale and model access: deep methods handle rich observations without an explicit model, while our construction provides exact guarantees on small-to-medium problems where a model is available. Integrating the two—for example, using probe-based losses as an auxiliary objective in representation learning—is a promising direction for future work. Computational mechanics. ε -machines [13, 43] define minimal predictive models—our exact equivalence in the passive (m=0m=0) limit. We generalize to approximate merging (ε>0 >0) and interactive capacity (m≥1m≥ 1). Information bottleneck. The information bottleneck [51] compresses a variable X while preserving mutual information I(X;Y)I(X;Y). Our ε -quotient is the closed-loop interactive generalisation: the agent’s history plays the role of X, and the future observation law (conditional on the agent’s policy) plays the role of Y. The key difference is that our compression is policy-dependent and uses directed information rather than mutual information, reflecting the interactive structure of POMDPs. Communication complexity. Yao’s communication complexity framework [52] studies how much communication is needed for two parties to compute a joint function. In the m=0m=0 one-way variant, the sender’s optimal encoding is precisely the quotient that merges source symbols indistinguishable to the bounded receiver—recovering the optimal communication protocol as a special case of our quotient construction. Cognitive science. Miller’s “magical number seven” [53] and Cowan’s refined capacity of 4±14± 1 items [54] characterise working-memory limits in humans. A human with working memory m and attention span T is formally a finite-state controller; the quotient induced by (m,T)(m,T) represents the environmental distinctions that matter to that human. This connection suggests empirical predictions: humans should be behaviourally indifferent between situations in the same quotient class, testable via reaction-time or choice experiments. Summary comparison. Table 8 highlights the key axes along which our framework differs from state bisimulation metrics and predictive state representations. Table 8: Comparison of abstraction frameworks along key structural dimensions. Dimension State bisimulation PSRs / OOMs This work Abstraction target States Predictive statistics Observation histories Distinguishing power All policies / actions Open-loop test sequences Bounded (m,T)(m,T) controller family Comparison object One-step transitions Linear predictors Finite-horizon observation laws Loop type Open-loop (per-action) Open-loop Closed-loop Quotient output State partition Low-rank representation History partition → quotient POMDP Appendix D POMDP Morphisms and Canonical Quotient Construction Definition D.1 (POMDP morphism). A POMDP morphism ϕ:M1→M2φ M_1→ M_2 is a surjection ϕ:ℋ1↠ℋ2φ _1 _2 satisfying: (M1) ϕ([ϵ]1)=[ϵ]2φ([ε]_1)=[ε]_2 (initial-state preservation). (M2) PM1π(Ot+1:T∣C)=PM2π(Ot+1:T∣ϕ(C))P_M_1^π(O_t+1:T C)=P_M_2^π(O_t+1:T φ(C)) for all π,Cπ,C (observation-law compatibility). (M3) ϕ(δ1(C,a,z))=δ2(ϕ(C),a,z)φ( _1(C,a,z))= _2(φ(C),a,z) for all C,a,zC,a,z (transition compatibility). An isomorphism is a bijective morphism. Condition (M2) constrains maps between different POMDPs, not merely within a single quotient. Together with (M3), these correspond to a coalgebra homomorphism for the functor modelling combined transition-and-output structure [42, 37]. Remarks on the approximate setting. In the ε -approximate case, different aggregation weights produce genuinely different transition kernels. The canonical quotient (Proposition A.1) resolves this by using uniform weights with explicit error control. The effective dimension deff=exp(H(b))d_eff= (H(b)) can replace |S||S| in the bounds when beliefs are concentrated. Appendix E Worked Examples E.1 Tiger POMDP with m=1m=1, T=2T=2 Consider the Tiger problem: S=left,rightS=\left,right\, A=listenA=\listen\, O=L,RO=\L,R\, Z(left,listen,L)=0.85Z(left,listen,L)=0.85, uniform prior b0=(0.5,0.5)b_0=(0.5,0.5). With m=1m=1, T=2T=2, the single FSC node selects listen deterministically. After observing L: bL=(0.85,0.15)b_L=(0.85,0.15); after R: bR=(0.15,0.85)b_R=(0.15,0.85). PMπ(O2∣L)≠PMπ(O2∣R)P_M^π(O_2 L)≠ P_M^π(O_2 R): specifically, P(L∣L)=0.745P(L L)=0.745 vs. P(L∣R)=0.255P(L R)=0.255. So L≢1,2RL _1,2R and the operational exact-for-family quotient has 77 classes (no merging). At ε=0.5 =0.5: 1=TV=|0.745−0.255|=0.49<0.5W_1=TV=|0.745-0.255|=0.49<0.5, so L and R merge. The 0.50.5-quotient has 33 classes: [ϵ],[L,R],[O2]\[ε],[\L,R\],[O^2]\. E.2 Tiger pseudometric computation With m=1m=1, T=2T=2, full actions, a 11-node FSC chooses a fixed action distribution θ=(θL,θlisten,θR)θ=( _L, _listen, _R). The conditional future distributions differ by 0.70⋅θlisten0.70· _listen under the discrete metric. Maximizing sets θlisten=1 _listen=1, yielding D1,2(M|hL,M|hR)=0.49D_1,2^W(M|_h_L,M|_h_R)=0.49. E.3 Sensor grid (1W_1 vs. TV) A localization POMDP with S=O=1,…,5S=O=\1,…,5\, dO(o,o′)=|o−o′|/4d_O(o,o )=|o-o |/4. Histories h1=(o=2)h_1=(o=2) and h2=(o=3)h_2=(o=3) produce beliefs at grid positions 22 and 33. Under the discrete metric: TV≈0.57TV≈ 0.57 (large—all mismatches weighted equally). Under the grid metric: 1≈0.14W_1≈ 0.14 (small—mass shifts by one step). At ε=0.2 =0.2: 1W_1 merges, TV cannot—demonstrating the strict advantage of 1W_1 on structured observation spaces. Exact (ε=0 =0): 7 classes[ϵ][ε][L][L][R][R][LL][L][LR][LR][RL][RL][RR][R]LLRRLLRRLLRRε=0.5 =0.5: 3 classes[ϵ][ε][L,R][\L,R\][O2][O^2]L,RL,RL,RL,Rmerge Figure 3: Tiger POMDP quotient structures for m=1m=1, T=2T=2. Left: operational exact-for-family quotient (7 classes). Right: ε=0.5 =0.5 quotient merges L and R (3 classes). Appendix F Complexity Note and Open Problem The probe-exact algorithm in Section 6 is exponential in the horizon parameter T for two direct reasons. First, even before controller enumeration, the history tree contains ∑t=0T|O|t=Θ(|O|T) _t=0^T|O|^t= (|O|^T) nodes in the worst case. Second, the bounded-controller probe class contributes an additional factor of |A|mm|O||A|^mm^m|O|, so probe-exact distinguishability testing ranges over exponentially many history–controller interactions as T grows. This is sufficient to justify the paper’s calibration claims about practical tractability: the probe-exact quotient algorithms target bounded horizons, while longer-horizon results rely on layering, controller subsets, and sampling. It does not by itself establish a formal complexity lower bound for the decision problem “does there exist an FSC π∈Πm,T distinguishing histories h,h′?”``does there exist an FSC π∈ _m,T distinguishing histories h,h ?′ and we do not claim such a lower bound. The natural route would be a reduction from finite-horizon POMDP planning [38], but a complete proof would need to compile accumulated reward thresholds into a purely observational distinguishability instance and prove the required biconditional. We therefore record this as an open problem rather than a theorem claim. Appendix G Additional Experiments G.1 Execution Protocol and Resource Notes All timed tables in the main paper use the serial configuration of the experiment driver (--no-parallel); optional process-level parallelism is available for convenience but was disabled for all reported wall-clock numbers. The theorem-first exact tables are produced from python paper/generate_theory_first_tables.py. The operational quick suite is produced from python -m experiments.run_basic_results --profile quick --seed 7 --no-parallel, while the long-horizon package adds --include-hierarchical-scaling --max-horizon 10. Dependencies are the pinned requirements.txt stack (numpy, scipy, pandas, matplotlib); no GPU, cluster scheduler, or accelerator-specific settings are required. The “under 3 minutes” statement in the main reproducibility paragraph refers only to the theorem-first tables and the operational core main-paper subset (Tables 2 through 6) on the reported hardware. It does not include the heavier operational tracks in Tables 13, 14, 10, and 11, which are reported separately because they dominate runtime despite using the same pinned software stack and serial configuration. Table 9 makes that distinction explicit by separating core verification, long-horizon extension, and archival stress tracks. The large-|S||S| experiments are CPU-bound rather than state-tensor-memory-bound: the sampling-based meaningful-scale rows cache trajectories over the 1313-history (|O|=3|O|=3) or 111111-history (|O|=10|O|=10) trees listed in Table 13, and do not materialize a dense |S|×|S||S|×|S| object. For the largest reported m=2m=2 scaling row (Network Monitoring n=9n=9, |S|=512|S|=512, |O|=3|O|=3, T=2T=2), the dominant pair-by-FSC tensor has (132)×6,410=499,98013 2× 6,410=499,980 scalar distances, so the operational memory footprint is controlled by history and controller counts rather than raw state count. On the reported Apple M3 Pro / 36 GB RAM machine, these runs fit comfortably in memory; runtime, not memory pressure, is the practical bottleneck. G.2 Command-to-Table Mapping Theory-first exact tables. Running python paper/generate_theory_first_tables.py writes machine-readable artifacts under paper/generated/data/ and LaTeX tables under paper/generated/. Specifically, probe_family_comparison.csv and table_probe_family_comparison.tex feed Table 2; clock_aware_observation_planning.csv and table_observation_planning.tex feed Table 3; and clock_aware_latent_planning.csv together with table_latent_planning.tex feed Table 4. Operational quick suite. Running python -m experiments.run_basic_results --profile quick --seed 7 --no-parallel --output-dir <DIR> writes the operational CSV artifacts used for the main empirical tables. The files computational_profile.csv, sampling_variance.csv, and bootstrap_coverage.csv populate Appendix Tables 24, 26, and 27. The same quick-suite run emits the operational benchmark artifacts from which Tables 5, 6, 12, 7, 13, and 14 are assembled. For the paper’s reproduction contract, however, only the subset through Table 6 belongs to the fast core-verification tier; the heavier rows are treated as archival stress tracks even though they are produced by the same driver. Solver settings. All 1W_1 distances in the main pipeline are solved by scipy.optimize.linprog(method="highs") on normalized probability vectors with exact equality constraints for the transport marginals and nonnegative transport variables; no entropic regularization, Sinkhorn approximation, or early stopping is used. The bisimulation baseline in Appendix Table 18 uses the same HiGHS linear-program backend for state-level Wasserstein subproblems, together with 1010 fixed-point iterations and discount 0.90.9 before complete-linkage clustering. PBVI uses the finite-horizon implementation in experiments.analysis.pbvi_solve with horizon equal to the benchmark horizon, 5050 belief points sampled by random forward simulation from b0b_0, discount γ=1γ=1, and seed 4242; the quotient-planning comparison applies these identical settings to the original and quotient POMDPs so that the reported speedups isolate compression rather than planner retuning. Heavy operational tracks. The same quick-suite command writes meaningful_scale.csv and m2_medium_scale.csv, which populate Tables 13 and 14. These rows are reported separately in the runtime discussion because they dominate the wall-clock budget of the operational pipeline. For inspection without rerunning the heavy jobs, the repository includes artifacts/tier3/meaningful_scale.csv, artifacts/tier3/m2_medium_scale.csv, artifacts/tier3/verify_tier3_artifacts.py, and a short README.md explaining their provenance and table mapping. Long-horizon package. Running python -m experiments.run_basic_results --profile quick --include-hierarchical-scaling --max-horizon 10 --seed 7 --no-parallel --output-dir <DIR> adds hierarchical_t_scaling.csv, principal_fsc_horizon_scaling.csv, and the figures fig_runtime_vs_horizon_log.png and fig_layered_bound_vs_empirical.png. These populate Tables 10 and 11, and Figures 4 and 5. Reproduction tiers. Table 9: Three-tier reproduction contract. Tier I is the intended fast verification target for the paper’s core claims; Tiers I–I are optional extensions for stress-testing the operational pipeline. Tier Verification target Command / artifact path Serial budget and role I Theorem tables plus operational core through Table 6 pythonpaper/generate_theory_first_tables.py and python-mexperiments.run_basic_results--profilequick--seed7--no-parallel <3<3 min; intended reviewer verification target. I Long-horizon extension (Tables 10, 11, Figures 4, 5) Add --include-hierarchical-scaling--max-horizon10 to the operational driver ∼10 10 min serial; horizon-scaling narrative only. I Heaviest stress rows (Tables 13, 14) Same driver for rerunning; artifact-only: pythonartifacts/tier3/verify_tier3_artifacts.py 55–3030 s per row, up to 2 h for largest m=2m=2; archival. Verifier: <1<1 s. G.3 Archival Operational Stress Tracks This subsection collects the heavier operational rows that are useful for understanding the computational behaviour of Qm,TopQ^op_m,T but are intentionally not part of the paper’s core validation target. They remain relevant as appendix-only archival evidence because they stress the same pipeline under longer horizons, larger state spaces, or richer probe families. Long-horizon scaling via layering and calibrated subsets. To address horizon scalability directly, we evaluate the compositional construction of Theorem 5.6 on Tiger with long horizons. For m=1m=1, we compare monolithic computation against layered segments (τ=4τ=4 for T≤8T≤ 8, τ=5τ=5 for T=10T=10). For m=2m=2, we calibrate a controller subset at T=6T=6 and reuse it at larger horizons as an empirical calibrated-subset heuristic without a full δS _S certificate. Table 10: Operational direct vs. layered runtime on Tiger full-actions (m=1m=1, ε=0.5 =0.5, deterministic-stationary probe family). T Method Segment τ Layers L Runtime (s) Histories processed 4 Direct – 1 0.05 31 4 Layered 4 1 0.05 31 6 Direct – 1 0.96 127 6 Layered 4 2 0.05 38 8 Direct – 1 16.42 511 8 Layered 4 2 0.10 62 10 Direct – 1 287.36 2,047 10 Layered 5 2 0.44 126 Table 11: Operational exact-for-family and empirical calibrated-subset horizon scaling on Tiger full-actions (m=2m=2, ε=0.5 =0.5). The calibrated-subset rows reuse a k=10k=10 subset chosen at T=6T=6 and do not carry a full δS _S certificate. T Method FSCs used Runtime (s) Classes ARI vs. full 4 Full op.-exact 147 2.53 10 1.000 5 Full op.-exact 147 10.95 16 1.000 6 Full op.-exact 147 46.11 30 1.000 7 Full op.-exact 147 194.27 50 1.000 7 Calibrated subset (empirical) 10 12.96 50 0.9997 8 Calibrated subset (empirical) 10 53.69 77 – The layered curve in Table 10 demonstrates the intended complexity shift: monolithic runtime grows with the full history tree, while layered runtime tracks short segments. At T=10T=10, layering reduces runtime by roughly three orders of magnitude while preserving the operational error-accumulation narrative from Theorem 5.6. For m=2m=2, Table 11 shows that a calibrated subset (k=10k=10, chosen from a T=6T=6 calibration run) preserves near-operational-exact partition structure at T=7T=7 (ARI =0.9997=0.9997) and enables extension to T=8T=8 without full FSC enumeration. These long-horizon calibrated-subset runs are empirical scalability results: unlike Table 5, we do not report a full probe-gap certificate δS _S for them, and we do not present them as theorem-level guarantees. Figure 4: Operational runtime scaling with horizon (log scale): monolithic, layered, and empirical calibrated-subset tracks. Figure 5: Layered bound validation (Theorem 5.6). Each bar compares the empirical LHS distortion (blue) against the theoretical RHS bound (orange) for eight test cases spanning single-layer reduction, wrapper contraction (deterministic and stochastic), and long-horizon theorem bounds (T∈4,8,10T∈\4,8,10\). All checks satisfy LHS ≤ RHS. Tractability summary. Table 12 summarizes how the three scalability dimensions are addressed. The history dimension |O|T|O|^T is addressed by segmenting horizon into short layers (Theorem 5.6, Proposition 5.8), demonstrated up to T=10T=10. The FSC dimension is reduced by greedy selection: on the operational exact-for-family benchmarks, k=5k=5 recovers the full probe envelope after a posteriori certification (δS=0 _S=0), while on long-horizon Tiger a calibrated k=10k=10 subset provides a near-operational-exact empirical surrogate without a full probe-gap certificate. The state dimension is decoupled by sampling (0.300.30 s at |S|=100|S|=100, Table 6). Core benchmark suites remain lightweight and are the intended serial reproduction target; the stress tracks in this appendix are optional single-core extensions. Table 12: Scalability: each complexity dimension and how it is addressed, separating operational exact-for-family benchmark certification from empirical long-horizon calibrated subsets. Dimension Growth Technique Demonstrated States |S||S| O(|S|2)O(|S|^2) per belief Sampling-based 1W_1 |S|=4,096|S|=4,096 (sampling), |S|=100|S|=100 (sampling) FSCs |ℱ||F| |A|mm|O||A|^mm^m|O| Greedy FSC subsets Certified: 6,405→56,405→ 5, 147→5147→ 5 m=2m=2 scaling: 5,1935,193 FSCs on RockSample Empirical: 147→10147→ 10 calibrated subset Histories |O|T|O|^T Exp. in T Layered horizon decomposition Direct to T=10T=10; layered to T=20T=20 Observations |O||O| |O|T|O|^T histories δO _O-coarsening (Prop. 5.5) GridWorld 4→24→ 2 obs Large-state and high-memory stress rows. Table 13 records appendix-level archival rows at scales exceeding |S|=1000|S|=1000 or effective horizon T=20T=20. Sampling-based 1W_1 estimation decouples runtime from |S||S|, enabling direct computation on Network Monitoring with |S|=4,096|S|=4,096 states. The layered construction (Theorem 5.6) extends the effective horizon to T=20T=20 by composing five τ=4τ=4 segments, each computed independently via sampling. The observation alphabet |O||O| remains the true computational bottleneck: at |O|=10|O|=10, the history tree has 111111 nodes at depth 22 versus 1313 at |O|=3|O|=3. Bootstrap CI widths at this scale are ≤0.17≤0.17 (Table 13), comparable to medium-scale benchmarks (Table 6), confirming that 500500 trajectories provide reliable distance estimates even at |S|=4,096|S|=4,096. Table 13: Meaningful-scale experiments: sampling-based and layered quotient construction (m=1m=1, 500500 trajectories). The 95% CI column reports the bootstrap confidence interval on maxh,h′1 _h,h W_1 (1,0001,000 resamples); for the layered track, the CI is on the segment-level (τ=4τ=4) cache. Track Benchmark |S||S| |O||O| T Method ε=0 =0 ε=0.3 =0.3 Runtime (s) 95% CI on max1 _1 Scale-up Net. Mon. (n=12n=12) 4,096 3 2 Sampling 13 5 ∼5 5 [0.31, 0.43][0.31,\,0.43] Large |O||O| Random 2,000 10 2 Sampling 111 10 ∼30 30 [0.10, 0.20][0.10,\,0.20] Long T Net. Mon. (n=10n=10) 1,024 3 20 Layered 13 5 ∼25 25 [0.67, 0.84][0.67,\,0.84] Higher-memory probe-family scaling. Proposition 4.11 predicts that a richer probe family produces a finer partition. Table 14 illustrates this beyond the operational exact-for-family benchmarks of Table 5, using sampling-based 1W_1 estimation. On RockSample(4,4)(4,4) (|S|=257|S|=257, 99 actions, 33 observations), the m=2m=2 probe family (5,1935,193 FSCs) maintains 55 classes at ε=0.5 =0.5, while the m=1m=1 family (99 FSCs) collapses to 33. On Network Monitoring (n=4n=4, |S|=16|S|=16) at T=3T=3, m=2m=2 (1,6051,605 FSCs) sustains 1414 classes through ε=0.3 =0.3, while m=1m=1 (55 FSCs) drops to 66. On Network Monitoring (n=9n=9, |S|=512|S|=512), m=2m=2 (6,4106,410 FSCs) preserves 55 classes at ε=0.3 =0.3 while m=1m=1 (1010 FSCs) drops to 44. In all three benchmarks, the max pairwise 1W_1 increases under m=2m=2, confirming that additional controller memory exposes finer-grained behavioural differences (Proposition 4.11). These rows are reported as archival stress tests rather than as part of the core theorem-validation suite. Table 14: Probe-family scaling: m=1m=1 vs. m=2m=2 quotient class counts at medium scale (sampling-based, 500500 trajectories). The 95% CI column reports the bootstrap confidence interval on maxh,h′1 _h,h W_1 (1,0001,000 resamples). Benchmark |S||S| m T FSCs ε=0 =0 ε=0.1 =0.1 ε=0.3 =0.3 ε=0.5 =0.5 Runtime (s) 95% CI on max1 _1 RockSample(4,4)(4,4) 257 1 2 9 5 5 4 3 0.5 [0.35, 0.47][0.35,\,0.47] RockSample(4,4)(4,4) 257 2 2 5,193 5 5 5 5 321 [1.00, 1.00][1.00,\,1.00] Net. Mon. (n=4n=4) 16 1 3 5 14 9 6 5 1.1 [0.48, 0.66][0.48,\,0.66] Net. Mon. (n=4n=4) 16 2 3 1,605 14 14 14 6 353 [0.67, 0.84][0.67,\,0.84] Net. Mon. (n=9n=9) 512 1 2 10 5 5 4 3 11 [0.28, 0.40][0.28,\,0.40] Net. Mon. (n=9n=9) 512 2 2 6,410 5 5 5 3 6,802 [0.39, 0.49][0.39,\,0.49] G.4 Tiger Reproduction and GridWorld Capacity Sweep With m=1m=1, T=2T=2 on the listen-only Tiger POMDP, the experiment reproduces 1(P(⋅∣hL),P(⋅∣hR))=0.49W_1(P(· h_L),P(· h_R))=0.49, 77 operational exact classes at ε=0 =0, and 33 classes at ε=0.5 =0.5. The GridWorld capacity sweep below shows quotient class counts across memory bounds and thresholds. Table 15: Quotient class counts for GridWorld 3×33× 3 (|S|=9|S|=9, T=2T=2). Total histories: 2121. m ε Classes Compression Policies 1 0.0 6 0.29 5 1 0.2 5 0.24 5 1 0.35 3 0.14 5 1 0.5 3 0.14 5 2 0.0 6 0.29 6,405 2 0.2 6 0.29 6,405 2 0.35 6 0.29 6,405 2 0.5 3 0.14 6,405 G.5 Value-Function Error Bounds (Full) Table 16: Value-function error bounds across reward scales. Panel A: Tiger full actions with synthetic LR=1L_R=1 reward (tight bounds). Panel B: Tiger with standard reward LR=110L_R=110 (vacuous—bound exceeds reward range). Panel C: GridWorld 3×33×3 goal reward LR≈2L_R≈ 2 (moderate—informative bound at small ε ). All use m=1m=1, T=2T=2. The column LRTεL_RT is the provable bound from Theorem 3.6; the column LRTDL_RTD reports the tighter empirical proxy LR⋅T⋅Dm,TL_R· T· D_m,T^W, which is always valid but follows from the partition construction only when Dm,T≤εD_m,T^W≤ (observed in all tested configurations at ε>0 >0). ε Empirical error Dm,TD_m,T^W LRTεL_RT LRTDL_RTD Prop A.1 Panel A: Tiger, synthetic LR=1L_R=1 0.0 ≈0≈ 0 0.00 0.00 0.00 0.0 0.1 ≈0≈ 0 0.00 0.20 0.00 3.4 0.3 ≈0≈ 0 0.00 0.60 0.00 10.2 0.5 0.12 0.24 1.00 0.49 17.0 Panel B: Tiger, standard reward LR=110L_R=110 (vacuous) 0.0 0.00 0.00 0.00 0.00 0.0 0.1 0.00 0.00 22.0 0.00 374.0 0.3 0.00 0.00 66.0 0.00 1122.0 0.5 2.89 0.24 110.0 53.33 1870.0 Panel C: GridWorld 3×33×3, goal reward LR≈2L_R≈ 2 0.0 0.00 0.00 0.00 0.00 0.0 0.1 ≈0≈ 0 ≈0≈ 0 ≈0.4≈ 0.4 ≈0≈ 0 5.8 0.3 ≈0≈ 0 ≈0≈ 0 ≈1.2≈ 1.2 ≈0≈ 0 17.3 0.5 ≈0≈ 0 ≈0≈ 0 ≈2.0≈ 2.0 ≈0≈ 0 28.8 G.6 Horizon Gap Analysis As T increases from 22 to 1010 on Tiger (ε=0.5 =0.5), empirical value error remains small while the pseudometric bound stays informative. The canonical worst-case aggregation bound grows from 1717 (at T=2T=2) to 405405 (at T=10T=10), confirming its conservative worst-case nature. The non-monotone (sawtooth) pattern arises because the set of merged history classes changes discretely at each ε threshold, so per-class distortions can drop when a coarser partition happens to align better with the reward structure. G.7 Operational Probe Family Sanity Check Across all 147147 deterministic FSCs (m=2m=2, Tiger), the maximum 1W_1 between hL,hRh_L,h_R is 0.490.49. Among 200200 sampled stochastic FSCs (4040 per seed, seeds 7,42,123,256,999\7,42,123,256,999\), the per-seed maximum 1W_1 is 0.38±0.070.38± 0.07 (mean ± std, range 0.310.31–0.470.47)—no sampled stochastic stationary controller exceeds the deterministic maximum of 0.490.49 on this benchmark. This is a benchmark-specific sanity check for the operational stationary probe family only: Proposition 4.10 gives a separate clock-aware exact POMDP where stochastic stationary FSCs strictly outperform deterministic stationary ones. G.8 Observation Noise Sensitivity Table 17: Noise sensitivity (Tiger, m=1m=1, T=2T=2). Range over accuracy ∈0.70,0.75,0.80,0.85,0.90,0.95∈\0.70,0.75,0.80,0.85,0.90,0.95\. ε Min cl. Max cl. Min val. err. Max val. err. 0.0 7 7 0.000 0.000 0.2 5 7 0.000 0.000 0.4 3 7 0.000 0.108 0.6 3 3 0.058 0.145 G.9 Full Baseline Comparison Table 18: Full baseline comparison (m=1m=1, T=2T=2), both benchmarks. Benchmark Method ε Classes Val. err. Dm,TD_m,T^W Time (s) Tiger full actions ε -quotient 0.3 4 0.000 0.000 ∗ Truncation (d=1d=1) 0.3 5 0.000 0.000 <0.01<0.01 Random partition 0.3 3.7 0.041 0.082 <0.01<0.01 Belief-distance 0.3 6 0.000 0.000 <0.01<0.01 Bisimulation 0.3 6 0.000 0.000 0.05 ε -quotient 0.5 3 0.122 0.245 ∗ Truncation (d=1d=1) 0.5 5 0.000 0.000 <0.01<0.01 Random partition 0.5 3.0 0.122 0.245 <0.01<0.01 Belief-distance 0.5 5 0.000 0.000 <0.01<0.01 Bisimulation 0.5 5 0.000 0.000 0.05 GridWorld 3×33× 3 ε -quotient 0.3 4 0.099 0.092 ∗ Truncation (d=1d=1) 0.3 9 0.000 0.000 <0.01<0.01 Random partition 0.3 3.7 0.077 0.163 <0.01<0.01 Belief-distance 0.3 9 0.000 0.052 0.02 Bisimulation 0.3 3 0.104 0.166 0.10 ε -quotient 0.5 3 0.104 0.166 ∗ Truncation (d=1d=1) 0.5 9 0.000 0.000 <0.01<0.01 Random partition 0.5 3.0 0.104 0.166 <0.01<0.01 Belief-distance 0.5 6 0.099 0.111 0.02 Bisimulation 0.5 3 0.104 0.166 0.10 ∗ Cache construction dominated; per-ε partition is <0.01<0.01 s. G.10 Ablation Studies Table 19: Ablation studies (Tiger full actions, T=2T=2). Ablation Variant Classes (ε=0.3 =0.3) Note Metric 1W_1 (discrete dOd_O) 7 Default TV-equivalent 7 Same on Tiger (binary O) Memory m=1m=1 (3 FSCs) 7 Coarser m=2m=2 (147 FSCs) 14 Finer, 0 value error Approx. Full enum. (147 FSCs) 14 Exact Greedy k=5k=5 14 ARI =1.0=1.0, 2.1×2.1× faster G.11 Low-Rank Analysis Table 20: Effective rank of the FSC distinguishing matrix. Benchmark m Depth FSCs Rank (90%) Rank (95%) Rank (99%) Tiger (T=4T=4) 1 3 3 1 1 1 Tiger (T=4T=4) 2 3 147 3 4 7 Grid 3×33×3 (T=2T=2) 1 1 5 1 2 4 Grid 3×33×3 (T=2T=2) 2 1 6,405 2 3 5 G.12 Larger-Scale Results Table 21: Quotient class counts for larger POMDPs (m=1m=1). Total histories: 2121 (T=2T=2), 8585 (T=3T=3). Benchmark T ε=0 =0 0.10.1 0.20.2 0.30.3 0.50.5 0.60.6 Grid 5×55×5 2 6 6 5 4 3 3 Grid 5×55×5 3 22 16 12 9 6 5 Random |S|=20|S|=20 2 6 3 3 3 3 3 Random |S|=20|S|=20 3 22 4 4 4 4 4 G.13 Scaling and Timing Table 22: Scaling: wall-clock time vs. state-space size (GridWorld, T=2T=2, m=1m=1, ε=0.3 =0.3). Grid |S||S| Classes Compression Time (s) 3×33× 3 9 4 0.190.19 0.03 4×44× 4 16 4 0.190.19 0.04 5×55× 5 25 4 0.190.19 0.05 6×66× 6 36 4 0.190.19 0.07 Table 23: Wall-clock time per experiment (quick profile, single CPU core). Experiment Time (s) Tiger reproduction <0.1<0.1 Capacity sweep 0.50.5–1.01.0 Value loss bounds 0.30.3–0.50.5 Metric sensitivity 1.01.0–2.02.0 Baseline comparison 0.50.5–1.01.0 Low-rank analysis 0.50.5–2.02.0 Total <<20 G.14 Computational Bottleneck Breakdown Table 24: Pipeline stage breakdown (single CPU core, m=1m=1, T=2T=2). Distance cache (1W_1 LP solves) dominates in all non-trivial cases. Benchmark |S||S| m FSCs Enum (s) Cache (s) Cache % Tiger 2 1 3 <0.01<0.01 0.0040.004 99.099.0 GridWorld 3×33×3 9 1 5 <0.01<0.01 0.0340.034 99.899.8 RockSample(4,4) 257 1 9 <0.01<0.01 0.4720.472 100.0100.0 G.15 Sampling Convergence and Variance Table 25: Operational sampling convergence on GridWorld 3×33×3 (m=1m=1, T=2T=2, 55 replications per sample count, averaged over ε∈0,0.3,0.5 ∈\0,0.3,0.5\). Minimum ARI stabilizes by 100100 trajectories. Trajectories Mean ARI Min ARI Replications 50 0.991 0.961 5 100 0.994 0.971 5 250 0.994 0.971 5 500 0.998 0.971 5 1,000 0.994 0.971 5 Table 26: Partition stability: class counts across 1010 independent random seeds (GridWorld 10×1010×10, |S|=100|S|=100, m=1m=1, T=2T=2, 500500 trajectories). ε Mean classes Std Min Max 0.0 6.0 0.0 6 6 0.1 6.0 0.0 6 6 0.25 4.0 0.0 4 4 0.45 3.0 0.0 3 3 The zero variance at 500500 trajectories indicates that the sampling noise in the estimated 1W_1 distances is well below the complete-linkage clustering threshold at all tested ε values. Even at 5050 trajectories, mean ARI exceeds 0.990.99, and the minimum ARI stabilizes at 0.9710.971 by 100100 trajectories, confirming that the partition is robust to sampling noise. Remark G.1 (Sample complexity of empirical 1W_1). On a finite support of size K, the empirical 1W_1 distance converges at rate O(n−1/2)O(n^-1/2) in expectation [55], where n is the number of samples per distribution and K=|O|T−tK=|O|^T-t is the number of possible future observation sequences at depth t. For the bounded-agent regimes targeted here (|O|≤7|O|≤ 7, T≤4T≤ 4), K remains modest (at most |O|T=2,401|O|^T=2,401), and 500500 trajectories per (history, policy) pair suffice empirically (Table 25). The max-over-policies aggregation introduces a union-bound factor of |Π|| |; in practice, the greedy-selected subsets (|ΠS|≤10| _S|≤ 10) keep this overhead negligible. G.16 Bootstrap CI Coverage Validation Table 27: Empirical coverage of 95% bootstrap CIs on maxh,h′1 _h,h W_1 (GridWorld 3×33×3, m=1m=1, T=2T=2, 200200 replications). Trajectories Coverage Mean CI width 100 97.0%97.0\% 0.1990.199 250 96.5%96.5\% 0.1270.127 500 96.0%96.0\% 0.0900.090 Coverage is within 2%2\% of the nominal 95%95\% level at all sample sizes, confirming reliable uncertainty quantification for the max-distance statistic. G.17 Additional Benchmark Results Table 28: Quotient class counts on additional benchmarks (m=1m=1, T=2T=2). Total histories: 1313. Benchmark |S||S| |A||A| |O||O| ε=0 =0 ε=0.3 =0.3 ε=0.5 =0.5 Hallway (L=10L=10) 10 3 3 5 5 3 Hallway (L=20L=20) 20 3 3 5 5 3 Network (n=4n=4) 16 5 3 5 4 3 Network (n=5n=5) 32 6 3 5 4 3 Both benchmarks exhibit the expected monotonicity: class count is non-increasing in ε . Hallway’s chain topology produces identical compression at L=10L=10 and L=20L=20 (the cyclically assigned landmarks create equivalent observation structure at both scales). Network Monitoring shows slightly finer resolution (4 classes at ε=0.3 =0.3) due to the probing actions creating action-dependent observation structure. G.18 Downstream Planning Impact Table 29: Planning on original vs. quotient: value gap under exhaustive policy search (T=2T=2). Benchmark m ε Policies Classes Vorig∗V^*_orig Value gap Tiger 1 0.0 3 4 0.373 0.000 Tiger 1 0.3 3 4 0.373 0.000 Tiger 1 0.5 3 3 0.373 0.000 Tiger 2 0.3 147 4 0.373 0.000 Tiger 2 0.5 147 3 0.373 0.000 Hallway 1 0.0 3 5 0.262 0.000 Hallway 1 0.3 3 5 0.262 0.000 Hallway 1 0.5 3 3 0.262 0.082 The value gap (difference between the original-optimal and quotient-optimal policy values, both evaluated on the original POMDP) is zero at ε≤0.3 ≤ 0.3 for all settings. At ε=0.5 =0.5 on Hallway, the quotient selects a different policy with value gap 0.0820.082, consistent with the bound LRTε=1.0L_RT =1.0. The compression from 55 classes to 33 at ε=0.5 =0.5 would reduce the effective planning state space by 40%40\% for planners that operate on history equivalence classes. G.19 Initial-Belief Sensitivity Table 30: Partition stability under initial-belief perturbation (Tiger full actions, m=1m=1, T=2T=2). ARI measured against the uniform-belief (b0=[0.5,0.5]b_0=[0.5,0.5]) partition. b0(sL)b_0(s_L) ε=0 =0 (classes / ARI) ε=0.3 =0.3 (classes / ARI) ε=0.5 =0.5 (classes / ARI) 0.5 4 / 1.00 4 / 1.00 3 / 1.00 0.3 4 / 1.00 4 / 1.00 3 / 1.00 0.1 4 / 1.00 3 / 0.89 3 / 1.00 0.7 4 / 1.00 4 / 1.00 3 / 1.00 0.9 4 / 1.00 3 / 0.89 3 / 1.00 The partition is stable under moderate perturbations of b0b_0: ARI =1.0=1.0 for b0∈[0.3,0.7]b_0∈[0.3,0.7] at all ε . Only extreme beliefs (b0(sL)∈0.1,0.9b_0(s_L)∈\0.1,0.9\) at intermediate ε=0.3 =0.3 produce a different partition (3 vs. 4 classes, ARI =0.89=0.89), consistent with the continuity of belief posteriors in b0b_0. Appendix H Notation Reference Table 31: Principal notation. Symbol Meaning M=⟨S,A,O,P,Z,R,b0⟩M= S,A,O,P,Z,R,b_0 Finite POMDP S,A,OS,A,O State, action, observation sets P(s,a,s′)P(s,a,s ) Transition kernel ℙ(s′∣s,a)P(s s,a) Z(s′,a,o)Z(s ,a,o) Observation kernel ℙ(o∣s′,a)P(o s ,a) R(s,a)R(s,a) Reward function bt∈Δ(S)b_t∈ (S) Belief state at time t π=⟨N,α,β,n0⟩π= N,α,β,n_0 Stochastic FSC m Memory bound (max FSC nodes) T Finite horizon Πm,T _m,T Set of stochastic FSCs with ≤m≤ m nodes dOd_O Ground metric on observations δO _O Observation resolution threshold |Oδ||O_δ| δO _O-covering number of observation space Qm,T,δQ_m,T,δ Quotient POMDP under (m,T,δO)(m,T, _O)-bounded agents 1W_1 1-Wasserstein distance Dm,T(M,N)D_m,T^W(M,N) Closed-loop Wasserstein pseudometric h=(o1,…,ot)h=(o_1,…,o_t) Observation history ≡m,T _m,T Exact bounded-interaction equivalence [h][h], [h]ε[h]_ Equivalence class (exact-for-family / ε -approximate) Qm,T(M)Q_m,T(M) Quotient POMDP b¯[h] b_[h] Aggregated belief for class [h][h] VMπV_M^π Value of policy π in POMDP M