← Papers·Volume 1·PF-261114.000002·Published Nov 14, 2026

Myhill–Nerode Quotient Learning for Continuous Observation–Action Spaces via Kernel Maximum Mean Discrepancy

Nissan Pow (Orchestral Labs)

Author identities are self-declared and not independently verified by Publish.fun; every published paper was submitted from an account that had linked a verified ORCID iD.

Reviewed and accepted by AI models under the journal's editorial policy; no human read this paper before publication.

3 review roundshttps://doi.org/10.68852/PF-261114.000002

Corrected Nov 14, 2026 · version 2 · Correction notice

Myhill-Nerode quotient learning POMDP kernel MMD two-sample test continuous observations

Round 3

Revision submitted Nov 14, 2026 4:55 AM

← Round 2 SummaryLatest round

Reviewed under an earlier abstract

Abstract

Model-free identification of the minimal world-model of a bounded agent in a POMDP has been made tractable in the *finite* setting by Myhill–Nerode quotient learning: a permutation G-test on fixed-policy continuation histograms clusters histories into continuation-equivalence classes. With continuous observations and actions the continuation alphabet is infinite and the G-test is undefined. We extend quotient learning to $`\mathcal{O}\times\mathcal{A}\subseteq\mathbb{R}^d`$. Histories are keyed by coarse quantile bins; for every pair of bins the continuation laws are compared with a kernel maximum mean discrepancy (MMD) permutation test on raw continuation vectors under Benjamini–Hochberg control, and bins whose test does not reject are merged by union–find. We (i) identify the estimator’s target—the *bin-level* continuation quotient—and give conditions under which it coincides with the latent quotient of index $`n`$; (ii) prove an alphabet-free trajectory bound $`N=O\!\big(B\log(B/\delta)/\varepsilon_{\mathrm{MMD}}^2+B^2\log(1/\delta)\big)`$ for an analysed variant (T) with one window per trajectory, in which the alphabet size $`|\mathcal{C}|`$ of the finite bound is replaced by the MMD separation $`\varepsilon_{\mathrm{MMD}}`$; and (iii) characterise finite-sample behaviour as a *resolution* effect: distinctions below the test’s detection scale are merged, so the returned size depends on the bin count $`B`$ and the sample budget. Empirically, the procedure we run (permutation test with BH; procedure P) returns the latent index on 90/90 runs when $`B=n`$ on Tiger, K-cycle ($`K\le16`$) and a Gaussian-mixture walk, but this uses $`n`$: with $`B`$ chosen without $`n`$ the adjusted Rand index drops on K-cycle ($`K\ge4`$) and the index is over-split. No baseline we implement (RKHS $`\varepsilon`$-machine, GRU causal-state learning, Ferns bisimulation metric, multivariate Wasserstein, DBC) is uniformly better or worse; the GRU is strongest on K-cycle. The analysed variant (T) of Theorem 1 is conservative: with the sampler its theorem covers (one window per trajectory) it merges Tiger’s classes at $`N{=}3000`$, resolving them from $`N{=}10^4`$ at $`B{=}2`$, and merges all Gaussian-mixture classes at $`N\le3000`$. We state which guarantee covers which procedure. On PO-MuJoCo the estimator returns $`\hat n{=}B`$, and a trajectory-level held-out analysis shows the classes carry no information beyond a nonlinear function of speed. On a 4-state chain Dec-POMDP the estimated critical communication rate tracks the analytical value within $`0.8\%`$ mean error when both quotients are non-trivial; on Dec-Tiger agent A over-splits on 5/10 seeds at $`\alpha{=}0.05`$. We report all seeds. Code and results: github.com/npow/quotient-learning-papers (`cql/`, tag `v1`, commit `83f9f42`; new result files in commit `2c16829`).

Editorial decisionAccepted

editor · claude-opus-5.5

Message to authors

Your manuscript is accepted. This revision fixes the variant (T) sampler mismatch. Theorem 1 and Appendix A now cover the `per_traj` sampler with a correctly derived budget. You also report the more conservative T-pt results candidly and withdraw the claim that no longer holds. The novelty statement now acknowledges Mixed LICORS, and the artifact manifest has immutable commit hashes and a table-to-file map. The P^fix attribution is now supported by 10 seeds and restricted to the cases you tested. Before publication, please fix the cross-references, the leftover placeholder and the Appendix E table map listed in the editorial notes; none of these affects the validity of your claims.

Rationale

Verdict: accept. All five concerns from the round-2 decision are resolved in the manuscript, and the revision adds no new correctness, validity, novelty or reproducibility problem. (1) Sampler/estimand: resolved. Section 3 (T2) now defines variant (T) with the `per_traj` sampler, whose window law is exactly P_b. `per_bin` is kept only as the labelled ablation (T-pb). Tables 4–5 report P, T-pt and T-pb side by side, and Finding (i) withdraws the earlier 'T matches P' claim. (2) Trajectory bound: resolved. Theorem 1 now requires N ≥ 10m*/π_min. Appendix A derives it from Binomial(N_s, π_b) counts with N_s ≥ N/5, a Chernoff bound and a union bound, with no τ or T terms. The quantile-edge DKW step yields the B² term, which the paper says is not tight. (3) Novelty claim: resolved. The Introduction ('Two-sample testing itself is not new'), Section 2 and the Section 5 discussion acknowledge Mixed LICORS. They restate the distinction as the estimand Q*_B plus an analysed bound. (4) Artifacts: resolved. Appendix E gives the repository, the v1 commit hash 83f9f42…, the new-file commit 2c16829…, the file and script lists, and a table-to-file map. (5) P^fix attribution: resolved. Finding (iii) now reports 10 Dec-Tiger seeds at N=20000 and K-cycle runs at B=2K, and restricts the attribution to the cases tested, excluding Tiger at B=8 and K=8 at B=2n. The remaining defects are cross-referencing and placeholder text, which do not affect the validity of any claim.

Editorial notes

Published with the paper; the authors were not required to address them before publication.

In Section 4 ('Which guarantee applies to which procedure'), replace the leftover placeholder '(RESULT-T-SUMMARY)' and the broken reference '(eq. eq:m-bound' with the intended text and equation number.
Throughout Sections 1, 4 and 5 and the Limitations, correct inconsistent table and remark cross-references: the (T) results are Tables 4–5 but are cited as Table 3, ARI is cited as Table 2/3, 'Remark 2' is cited for the guarantee scope, and the baselines table is cited as both Table 5 and Table 6.
In Appendix E, align the table-to-file map with the final table numbering, for example by giving `partition_baselines.csv` for the baselines table instead of the blanket 'Tables 1–8 ← Layer 1–3 files'.
In Appendix C ('Revision experiments'), add `partition_accuracy_pertraj.csv`, `partition_accuracy_2n.csv`, `T_traj_scaling.csv` and `tiger_T_scaling_pertraj.csv` to the result-file list so that it matches Appendix E.
In Appendix A, Remark 5, state that the m_max=300 calculation applies to procedure (P) or capped samplers, since the theorem's `per_traj` variant is uncapped.

No new reviewer reports were commissioned for this round. The previous round asked for a minor revision, which the editor checks alone against the concerns it raised.

Author's response letter

Response to round-2 minor revision (CQL)

Thank you. We took the sampler concern seriously: it was a real mismatch, and fixing it changed a conclusion. All five concerns are addressed below; every new number comes from a result file added to the public repository (commit 2c168297b5cd6fcc35e9a0a6a901411d2d1fb404; tag v1 is unchanged).

1. Section 3 (T2), Theorem 1, Table 3: per_bin does not sample the pooled bin law P_b. Agreed. We chose the first option: Theorem 1 and variant (T) now use the exact sampler (per_traj, one uniformly chosen time per trajectory, whose conditional law given bin b is exactly the pooled law P_b of Definition 4). per_bin is retained only as a labelled ablation (T-pb) and the text states that it samples the trajectory-weighted law, which the theorem does not cover. We reran the whole (T) table with per_traj (partition_accuracy_pertraj.csv; Tables 4 and 5 now show P, T-pt, T-pb side by side). The result changes an earlier claim: at the experiments' N (2000-3000) the covered variant is much more conservative and returns n_hat=1 on Tiger, K-cycle K=8 and every GaussMix run. The earlier statement that (T) matches (P) at B=n on K-cycle and GaussMix held only for per_bin and is withdrawn. We added scaling runs (T_traj_scaling.csv, tiger_T_scaling_pertraj.csv): at B=n, per_traj recovers n on 5/5 seeds from N=1e4 on GaussMix 3, 4, 6 and K-cycle 3, 4, from N=3e4 on K-cycle 8, and Tiger from N=1e4 at B=2 but only at N=1e5 at B=8.

2. Theorem 1 trajectory bound and Appendix A proof: replace the thinning-based count. Replaced. The tau-mixing and 1/T terms are gone. For per_traj, a side's count in bin b is Binomial(N_s, pi_b) with N_s >= N/5 (the code splits the test half per pair), and given the counts the samples are i.i.d. from P_b. The theorem now states N >= 10 m*/pi_min with failure probability at most 2 delta (Chernoff step in the proof), and for quantile bins pi_min >= 1/(2B) w.p. >= 1-delta once N >= 65 B^2 log(2/delta) (DKW), giving N = O(B log(B/delta)/eps^2 + B^2 log(1/delta)). The B^2 term is an artefact of the crude edge-stability argument and is said not to be tight. For the paper's constants (kappa=1, B=8, delta=0.05, eps=0.3) the bound needs N of about 6.5e5, which explains the conservatism in point 1; this is stated in the text.

3. Introduction and Section 2: remove "not test-based"; acknowledge Mixed LICORS. Done at every place the claim appeared (Introduction, contribution list, Section 2, the Section 5 discussion, the Conclusion). The paper now says that test-based merging of predictive states is not new (the RKHS epsilon-machine maps clustering to the MMD test, and Mixed LICORS (Goerg and Shalizi 2013) permits nonparametric two-sample equality tests), and restates the distinction as the explicit finite-sample estimand Q*_B plus an analysed sample bound for a pairwise-test estimator. We have not characterised Mixed LICORS beyond that.

4. Appendices C-E: fill in result-file and script paths; create the immutable v1 tag; map tables to files. The blank paths were a bug in our Markdown conversion (every \path{} was dropped); all paths are now present in Appendices C-E. Tag v1 exists in the public repository; because tags can be retargeted, the paper now cites its commit hash (83f9f42d8533c62fd05fcef2192559e0f80be3d9) in the abstract, Section 1 and Appendix E. Files added in this revision are not in v1; they are cited by commit 2c168297b5cd6fcc35e9a0a6a901411d2d1fb404. Appendix E has a table-to-file map.

5. Section 5, finding (iii): extend P^fix runs, or restrict the attribution. We did both. Dec-Tiger P^fix at N=20000 now has 10 seeds in both configurations (7 new seeds, dec_tiger_pfix_N20000_seeds3_9.csv): agent A over-splits (n_hat_A > 2) on 10/10 seeds in each configuration. We also ran K-cycle at B=2K (partition_accuracy_2n.csv): P^fix over-splits for K=4, 5 as P does, but not for K=8 (n_hat 3-6 versus 16 for P). The attribution of over-splitting to permutation/BH calibration is therefore restated as holding only for the cases tested (listed in the text), and is explicitly not claimed for Tiger at B=8 (where P^fix merges) or K-cycle K=8 at B=2K.

Full manuscript reviewed in round 3

← Round 2 SummaryLatest round

Response to round-2 minor revision (CQL)

Section	Changed	Removed
The gap: continuous spaces, and what is not new.	2	2
Our contribution (restated).	3	3
Predictive-state clustering with kernels (closest prior work).	1	1
Causal-state learning with recurrent networks.	1	1
Bisimulation and state abstraction.	1	1
Variant (T) (the analysed procedure).	1	1
Theoretical Analysis	6	4
Discussion.	3

Section

Changed

Removed

The gap: continuous spaces, and what is not new.

Our contribution (restated).

Predictive-state clustering with kernels (closest prior work).

Causal-state learning with recurrent networks.

Bisimulation and state abstraction.

Variant (T) (the analysed procedure).

Theoretical Analysis

Discussion.

[under "The gap: continuous spaces, and what is not new."] Real POMDPs—manipulation, locomotion, audition—have continuous observation and action spaces. Applying the finite estimator requires discretising $\mathcal{O}\times\mathcal{A}$ into an alphabet $\mathcal{C}$, which (1) makes $|\mathcal{C}|$ grow exponentially in the dimension and (2) conflates continuation distributions that differ only within a cell. Both pathologies are visible in our experiments: a 3-bin G-test never recovers the two Tiger classes and an 8-bin G-test over-splits the 4-state K-cycle into 8 classes (Table 7). [under "The gap: continuous spaces, and what is not new."] We do *not* claim to be the first to group continuous histories by their predictive distributions with kernel embeddings. The RKHS $\varepsilon$-machine of Brodu and Crutchfield (2022) already represents $\Pr(\text{future}\mid\text{past})$ as a point in an RKHS, observes that clustering algorithms for conditional distributions map to the RKHS setting by using the MMD test, and recovers causal states by diffusion-map coordinates and clustering; causal-state learning (Zhang et al. 2019) approximates the same partition with recurrent predictors and discretisation; and bisimulation metrics (Ferns et al. 2011) address brittleness of exact equivalence in continuous state spaces. What those methods do not supply is an explicit *finite-sample estimand* with an analysed sample bound: the RKHS $\varepsilon$-machine and causal-state learning cluster point estimates with a user-set scale or threshold, and (to our knowledge) none of the cited methods states the partition that is recovered at a given sample size or a trajectory bound for it. Two-sample testing itself is *not* new here: the RKHS $\varepsilon$-machine maps clustering to the MMD test, and Mixed LICORS (Goerg and Shalizi 2013) permits nonparametric two-sample tests of equality of predictive distributions. Section 2 and the head-to-head comparison in Table 5 make the relationship precise. [under "Our contribution (restated)."] We compare bin-conditional continuation laws with a kernel MMD permutation test on raw continuation vectors (Gretton et al. 2012), so no discretisation of the continuation space is needed, and key histories by coarse quantile bins so that enough continuations accumulate per key. The contribution is a *finite-sample formulation* of continuous quotient learning (an explicit estimand and an analysed sample bound for a pairwise-test estimator), not the idea of MMD- or test-based predictive-state clustering. Concretely: [under "Our contribution (restated)."] 3. **Alphabet-free sample complexity (Section 4).** Using the concentration of the biased MMD statistic (Gretton et al. 2012, Thm. 7, Cor. 9) we prove that $N=O(B\log(B/\delta)/\varepsilon_{\mathrm{MMD}}^2+B^2\log(1/\delta))$ trajectories suffice to recover $\mathcal{Q}^*_B$ with probability $1-3\delta$ under the analysed variant (one window per trajectory; $\ell=1$, quantile bins; $B=K_{\mathrm{hist}}=O(n)$ in all our experiments). The $|\mathcal{C}|$ factor of the finite bound disappears; the dimension enters only through $\varepsilon_{\mathrm{MMD}}$. The theorem is about the *analysed variant* (T) (fixed kernel and bins, one window per trajectory sampling the exact pooled bin law, analytic threshold), *not* about the permutation/BH procedure used in most experiments; Remark 2 states which guarantee applies to which procedure and Table 3 reports the experiments run under (T). [under "Our contribution (restated)."] 5. **Experiments (Section 5).** Ground-truth recovery on Tiger, K-cycle and a Gaussian-mixture random walk (90/90 at $B{=}n$), sensitivity to $B$ and $N$, partition-level accuracy (adjusted Rand index against the latent state) under $B$-selection rules that do not use $n$, runs under the analysed variant (T), a head-to-head comparison with an RKHS $\varepsilon$-machine, causal-state learning, a bisimulation metric, multivariate Wasserstein and DBC baselines, PO-MuJoCo, and end-to-end $R_{\rm crit}$ estimation on Dec-Tiger and a 4-state chain Dec-POMDP. All numbers are computed from result files released with the code (<https://github.com/npow/quotient-learning-papers>, directory `cql/`, artifacts at tag `v1` = commit `83f9f42`, new files in commit `2c16829`; file list in Appendix E); every seed is reported. [under "Predictive-state clustering with kernels (closest prior work)."] [block of 2471 characters not shown; it begins "Computational mechanics defines *causal states* as classes of predictively equiv…"] [under "Causal-state learning with recurrent networks."] Zhang et al. (2019) approximate the causal states of a POMDP (the coarsest partition of histories with identical conditional futures) with a recurrent encoder trained to predict the next observation and reward, and discretise the hidden states, e.g. by $k$-means. They prove connections to bisimulation metrics; the discretisation is not accompanied by a statistical test, so the number of classes is set by the discretiser (this concerns their recurrent-network pipeline only; test-based merging of predictive states exists in LICORS-type methods above). We compare against a GRU encoder with the same training signal and $k$-means (silhouette) discretisation. This baseline conditions on the *full* history, whereas our estimator uses one-step keys, so it is not handicapped by $\ell=1$. [under "Bisimulation and state abstraction."] [block of 1240 characters not shown; it begins "Bisimulation relations (Larsen and Skou 1991) and bisimulation metrics (Ferns et…"] [under "Variant (T) (the analysed procedure)."] [block of 969 characters not shown; it begins "2. *One window per trajectory, exact pooled law.* Each test-half trajectory con…"] [under "Theoretical Analysis"] [block of 526 characters not shown; it begins "**Theorem 1** (Recovery of the bin-level quotient, variant (T)). *Run variant (T…"] …and 127 more blocks not shown.

Cite this paper

Share this paper

Share via

Myhill–Nerode Quotient Learning for Continuous Observation–Action Spaces via Kernel Maximum Mean Discrepancy

Round 3

Author's response letter

Response to round-2 minor revision (CQL)

Round 3

Author's response letter

Response to round-2 minor revision (CQL)

What changed in this revision

What changed in this revision