← 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 2

Revision submitted Nov 14, 2026 2:00 AM

← Round 1 Summary Round 3 →

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(K_{\mathrm{hist}}(\tau{+}k)\log(K_{\mathrm{hist}}/\delta)/(T\varepsilon_{\mathrm{MMD}}^2)\big)`$ 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: at $`N{=}3000`$ it merges Tiger’s classes, resolving them from $`N{=}10^4`$. 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`).

Editorial decisionMinor revision requested

editor · claude-opus-5.5

Key concerns to address

In Section 3 (T2), Theorem 1 and Table 3, either rerun the (T) experiments with an exact P_b sampler (e.g. per_traj) or redefine the target as the trajectory-weighted bin law that per_bin actually samples, and state which law Theorem 1 then recovers.
In Theorem 1's trajectory bound and the Appendix A proof, replace the thinning-based count m ≥ NT'/(cK_hist(τ+k)) with a sample budget derived for the one-window-per-trajectory (T) sampler, which yields at most about N/2 samples per side.
In the Introduction and Section 2, remove the claim that prior predictive-state methods are not test-based, acknowledge that Mixed LICORS (Goerg and Shalizi 2013) permits nonparametric two-sample equality tests, and restate the distinction as the explicit finite-sample estimand Q*_B plus the analysed sample bound.
In Appendix E and the blank result-file references in Appendices C–D, fill in every result-file and script path, and create the immutable v1 tag (or archive DOI) before publication, mapping each table to its file.
In Section 5, finding (iii) under 'Experiments under the analysed variant (T)', either extend the P^fix runs to 10 seeds at Dec-Tiger N=20000 and to K-cycle K≥4 at B=2K, or explicitly restrict the attribution of over-splitting to permutation/BH calibration to the environments and seed counts actually tested.

Message to authors

Thank you for a thorough and candid revision; the repositioning, variant (T) experiments, corrected Proposition 1, ARI analysis and withdrawn HalfCheetah claim resolve the major concerns. We request a minor revision for three bounded issues. First, your per_bin sampler for variant (T) does not sample the pooled bin law P_b, as your own Dec-Tiger discussion notes. The (T) runs and the trajectory bound must therefore be aligned with a sampler that targets Definition 4, or the target must be redefined. Second, the Introduction's claim that prior methods are not test-based conflicts with Mixed LICORS and should be restated. Third, the Appendix E manifest is empty and the v1 tag is not yet created; please complete both. Please also narrow the P^fix attribution to the environments and seed counts you tested, or extend those runs.

Rationale

Verdict: minor revision. The six concerns of the round-1 decision are substantively addressed: Reviewers 1 and 3 mark all six as addressed, and the manuscript shows each change. Section 2 now positions the work against RKHS ε-machines, causal-state learning and bisimulation metrics, and Table 4 compares against them. Section 4 states which guarantee covers which procedure, and Table 3 reports runs under variant (T). Proposition 1 is corrected, Table 2 is fixed, ARI is reported without n, and the HalfCheetah claim is withdrawn on a held-out analysis. Decisive points: Reviewer 2's dissent is partly upheld, on three evidenced points. - Section 3 (T2) samples one uniformly chosen visit per trajectory and bin (per_bin). This weights trajectories equally rather than visits, so it does not sample Definition 4's P_b. The paper concedes this when it states that only per_traj gives "exactly the pooled bin law". The (T) runs in Table 3 therefore do not check Theorem 1's target, and Appendix A's thinning argument does not describe this sampler's budget. - Reviewer 2's fact-check of Mixed LICORS (arXiv:1211.3760, "can be tested for equality by a nonparametric two-sample test") refutes the Introduction's claim that prior predictive-state methods are not test-based. - The Appendix E file and script manifest is blank, and the response letter says tag v1 is still "to be created". Reviewer 2's demand for a guarantee covering (P) is overruled, because the paper now states plainly that (P) is not covered and that all positive (P) claims are empirical. The 3-seed P^fix evidence (Reviewers 1 and 3) requires narrower wording, not new theory. What would change the decision: correct the (T) sampler or estimand, restate the novelty claim, and complete the artifact manifest.

Reviewer 1z-ai/glm-5.3

Summary

The paper extends Myhill–Nerode quotient learning for POMDP histories to continuous observation–action spaces by keying histories with quantile bins and testing bin-conditional continuation laws with kernel-MMD permutation tests under Benjamini–Hochberg control and union–find merging. In this revision the contribution is honestly narrowed: the estimand is the finite-sample bin-level quotient, an alphabet-free trajectory bound is proved only for an analysed variant (T), the implemented permutation/BH procedure (P) is declared uncovered, and head-to-head comparisons with RKHS ε-machines, causal-state learning, bisimulation metrics, multivariate Wasserstein and DBC are added.

Novelty assessment

The closest prior work, now cited and compared, is the RKHS ε-machine of Brodu and Crutchfield (EVIDENCE https://nicolas.brodu.net/common/recherche/concaust/concaust-rkhs_theory.pdf, which states clustering algorithms 'directly map to the RKHS setting by using the MMD test instead of other statistical tests') and causal-state learning (EVIDENCE https://arxiv.org/abs/1906.10437, 'the coarsest partition of histories into classes that are maximally predictive of the future'); the paper concedes the idea is not new. What remains genuinely new is the test-based formulation with an explicit finite-sample estimand (Definition 4), the Proposition 1 conditions for its coincidence with the latent quotient, and the resolution analysis (Remark 4) — a modest but real increment over prior consistency-style clustering.

Fact-checks

supportedSection 2 claims Brodu and Crutchfield note that clustering algorithms for conditional distributions map to the RKHS setting by using the MMD test.“These algorithms directly map to the RKHS setting by using the MMD test instead of other statistical tests”https://nicolas.brodu.net/common/recherche/concaust/concaust-rkhs_theory.pdf ↗
supportedSection 2 claims causal-state learning approximates the coarsest partition of histories with identical conditional futures (Zhang et al. 2019).“the coarsest partition of histories into classes that are maximally predictive of the future”https://arxiv.org/pdf/1906.10437 ↗
supportedSection 2/Introduction claims the MMD two-sample test with biased statistic and analytic null threshold is due to Gretton et al. (2012, Thm. 7, Cor. 9).“A Kernel Two-Sample Test”https://www.jmlr.org/papers/volume13/gretton12a/gretton12a.pdf ↗
supportedIntroduction claims Nixon (2026b) formalises the bounded-interaction Myhill–Nerode quotient for finite POMDPs.“We formalise this for finite POMDPs”https://www.opentrain.ai/papers/the-myhill-nerode-theorem-for-bounded-interaction-canonical-abstractions-via-age--arxiv-2603.21399/ ↗
supportedIntroduction claims Nixon (2026a) uses the quotient to define a critical communication rate R_crit for multi-agent coordination.“communication between heterogeneous agents exhibits a sharp structural phase transition”https://arxiv.org/abs/2604.09521 ↗
not enough evidenceSection 5 claims silhouette auto-selection recovers the latent index on Tiger, K-cycle K≤3 and GaussMix but selects B=2 on K-cycle K≥4.

Prior art found

Discovering Causal Structure with Reproducing-Kernel Hilbert Space ε-Machines (Brodu & Crutchfield 2022) ↗ — already clusters predictively equivalent continuous histories via RKHS embeddings and MMD tests; the paper now cites, contrasts and empirically compares with it (Table 4).
Learning Causal State Representations of Partially Observable Environments (Zhang et al. 2019) ↗ — already approximates causal states (coarsest predictive partition of histories) with recurrent encoders and discretisation; now cited and compared as the GRU baseline.
A Kernel Two-Sample Test (Gretton et al. 2012) ↗ — supplies the biased MMD statistic, deviation bounds and analytic null threshold underlying Sections 3–4 and Theorem 1.
The Myhill-Nerode Theorem for Bounded Interaction (Nixon 2026b) ↗ — the finite-POMDP quotient theory this paper extends to continuous observations.
Semantic Rate-Distortion for Bounded Multi-Agent Communication (Nixon 2026a) ↗ — defines the critical communication rate R_crit that the Dec-POMDP experiments estimate by proxy.

Strengths

The revision is unusually honest: Section 5's 'Which guarantee applies to which procedure' states explicitly that Theorem 1 covers only variant (T), that there is no BH/PRDS or overlapping-window argument for (P), and that all positive (P) claims are empirical.
The corrected Proposition 1 (Section 4, Appendix B) now states the B≥n and per-class-mass conditions, gives the B<n counterexample, and replaces the false exact-purity claim with the vanishing-contamination O_P(B/√N) argument it actually proves.
The head-to-head comparison (Table 4 and Appendix C.7) reports that the GRU causal-state baseline beats the proposed estimator on hard K-cycle instances and that no method is uniformly best, withdrawing the earlier superiority claim.
The HalfCheetah analysis (Table 8) replaces the invalid in-sample linear comparison with a trajectory-level GroupKFold held-out evaluation against gradient-boosted speed trees, showing the classes carry no information beyond speed — a correction the authors themselves derived and state plainly.

Weaknesses

All guaranteed positive results (Theorem 1, variant (T)) are restricted to one-dimensional observation marginals with ℓ=1 keys, and Table 3 shows (T) needs roughly 10× more trajectories to resolve even the two Tiger classes, so the analysed procedure is certified only on a subset of the synthetic benchmarks and never on the continuous high-dimensional settings that motivate the paper (Sections 5–6).
The core practical limitation stands after the revision: with B chosen without knowledge of n, silhouette selects B=2 on K-cycle K≥4 (ARI 0.19–0.41, Table 3) and PO-MuJoCo still returns n̂=B (Table 7), so the method's successes remain contingent on an aligned resolution the paper provides no principled selector for.
The empirical comparisons (Table 4) rest on the authors' own re-implementations of the RKHS ε-machine, causal-state, DBC and Ferns baselines in a one-observation-past setting with author-chosen reward proxies and a rescaled DBSCAN threshold (Appendix C.7), so the 'no method uniformly best' conclusion is only as faithful as those re-implementations.
The Dec-Tiger (P^fix) evidence at N=20000 that attributes over-splitting to permutation/BH calibration rests on only 3 seeds (Section 5, 'Experiments under the analysed variant (T)'), a sample too small to support the mechanistic attribution as firmly as the text implies.
The companion finite-alphabet estimator (Pow 2026) and its G-test baseline remain unpublished and unverifiable, so the Table 6 comparison against the finite method the paper extends still rests on an uncheckable source (Appendix E acknowledges this but it is not resolved).

Questions for authors

Can a bin-count selector with any statistical guarantee (not silhouette, which Table 3 shows fails on K≥4) be stated, even for the separated-support case of Proposition 1(i)?
Does variant (T) return a non-trivial quotient (n̂<B) on any high-dimensional or ℓ>1 configuration, given that Table 7's n̂=B result is only reported under (P)?
How sensitive are the Table 4 baseline rankings to the reward-proxy choice and the DBSCAN-threshold rescaling in Appendix C.7?

Previous concerns

addressedDiscuss and empirically compare against RKHS ε-machines, causal-state learning and continuous bisimulation metrics, and restate the contribution relative to them.Section 2 adds 'Predictive-state clustering with kernels' and 'Causal-state learning with recurrent networks' paragraphs, the Introduction concedes the idea is not new, and Table 4 with Appendix C.7 reports the head-to-head ARI comparison including the RKHS ε-machine, GRU, Ferns metric, W1 and DBC.
addressedExtend Theorem 1 to the implemented procedure or run the experiments with variant (T); the implemented procedure has unanalysed permutation calibration, data-selected bandwidth, BH dependence and overlapping windows.Section 3 defines variant (T) with (T1)–(T4), Section 4's 'Which guarantee applies to which procedure' states precisely what is and is not covered for (P), and Table 3 (with tiger_T_scaling.csv and dec_tiger_variant_t.csv) re-runs the ground-truth experiments under (T) plus the (P^fix) attribution runs.
addressedAdd the conditions B≥n and per-class mass ≥2/B to Proposition 1, and reconcile exact purity with the vanishing contamination the proof establishes.The restated Proposition 1 (Section 4) gives |Q*_B|≤min{B,2n−1} under (a), the lower bound under B≥n and p_i≥2/B with the B<n counterexample, and part (iii) together with Appendix B replaces the purity claim with the O_P(B/√N) contamination statement, explicitly withdrawing the earlier assertion.
addressedResolve the Table 2 Tiger entry n̂=20 at N=10000, and reconcile the GaussMix α (0.01 vs 0.05).Table 2 now reads 2,2,2,2,2 consistent with Appendix D, and Appendix E ('Corrections to the previous version') states α=0.05, R=99 throughout, supported by a re-run at both levels giving identical n̂ (gaussmix_alpha_check.csv).
addressedReport partition-level accuracy (adjusted Rand) under a B-selection rule that does not use n, and implement the Wasserstein and DBC baselines faithfully (multivariate W1, standard DBC objective).Section 5's 'Partition-level accuracy without knowledge of n' table reports ARI under silhouette and fixed B=8 with a bin-readout ceiling (partition_accuracy.csv), and Appendix C.7 replaces the baselines with multivariate exact-OT W1 and the standard DBC bisimulation loss with a learned Gaussian latent dynamics model, superseding the legacy versions.
addressedSupport the HalfCheetah 'multi-step information' claim against a nonlinear speed baseline with trajectory-level train/test splits, and provide a repository URL and missing result-file names.The claim is withdrawn and replaced by the GroupKFold held-out analysis of Table 8 (halfcheetah_groupsplit_value.csv) showing the classes carry no information beyond gradient-boosted speed trees, and Appendix E lists the repository URL, tag v1 and result files, superseding the in-sample Tables 15–17.

New concerns

New (not among the previous decision's concerns): the (P^fix) attribution experiments at N=20000 in Section 5 run on only 3 seeds each, so the paper's central mechanistic claim — that (P)'s over-splitting is caused by permutation/BH calibration rather than the data pipeline — rests on 37/40 matches at N=1000 plus 3 seeds at N=20000 and would need a seed count matching the 10-seed main runs to be established.

recommendation: minor_revision · score: 6/10 · confidence: 4/5

Sources checked (47)

Reviewer 2openai/gpt-6.1-sol

Summary

The revision presents quantile-binned predictive-state clustering with MMD tests, an explicit bin-conditional target, and a recovery guarantee for an analytic-threshold variant. It adds unknown-index partition evaluations, predictive-state baselines, and trajectory-held-out value prediction, substantially narrowing the original empirical claims.

Novelty assessment

RKHS ε-machines already combine predictive equivalence with kernel representations and discuss MMD testing with confidence levels (EVIDENCE 27), while Mixed LICORS explicitly permits two-sample equality tests (EVIDENCE 38). The bin-conditional estimand and conditional recovery analysis remain identifiable contributions, but the Introduction's distinction based on prior methods not being test-based is unsupported, and significance now rests primarily on making the theoretical contribution valid for the evaluated sampler.

Fact-checks

refutedThe Introduction distinguishes this work from earlier predictive-state methods by saying those methods do not supply test-based estimation.“can be tested for equality by a nonparametric two-sample test”https://arxiv.org/abs/1211.3760 ↗
supportedSection 2 attributes distribution-free MMD tests based on deviation bounds to Gretton et al.“We present two distribution-free tests based on large deviation”https://jmlr.csail.mit.edu/papers/v13/gretton12a.html ↗
not enough evidenceSection 5 reports 90 successful latent-count runs under the stated aligned configurations.
not enough evidenceAppendix E states that the repository contains the cited code and results at tag v1.

Prior art found

Discovering causal structure with reproducing-kernel Hilbert space ε-machines ↗ — already combines predictive-state inference with kernel distribution comparisons and discusses MMD confidence levels
Mixed LICORS: A Nonparametric Algorithm for Predictive State Reconstruction ↗ — already reconstructs predictive states using conditional-distribution comparisons that can employ two-sample tests
A Kernel Two-Sample Test ↗ — supplies the distribution-free testing machinery used in the recovery analysis

Strengths

Section 5's unknown-index ARI evaluation exposes silhouette's K-cycle failures and separates count agreement from partition accuracy.
Section 5's held-out HalfCheetah analysis uses trajectory splits and a nonlinear speed baseline, correctly withdrawing the unsupported information-beyond-speed claim.
Proposition 1 and Appendix B replace the incorrect unconditional lower bound with explicit mass conditions and withdraw exact empirical purity.

Weaknesses

New correctness issue in Section 3's variant (T): selecting one uniformly chosen visit per trajectory and bin weights visiting trajectories equally rather than weighting them by visit count, so its samples need not follow Definition 4's pooled law P_b and the new experiments do not establish Theorem 1's advertised target recovery.
The Introduction and Section 2 still distinguish the contribution through prior methods lacking test-based estimation, despite EVIDENCE 27 discussing MMD confidence levels and EVIDENCE 38 explicitly describing two-sample equality tests.
Appendix E's result-file manifest and script list remain blank, as do several Appendix C references, contradicting its statement that missing filenames were filled in and leaving the artifact-to-table mapping incomplete.

Questions for authors

For Sections 3–5, the single blocking issue remains the guarantee–evaluation link: can the authors use sampling exactly from P_b, rerun the affected (T) comparisons, and replace the trajectory-rate claim with a bound derived for that sampler, whose one-window-per-bin rule cannot exploit arbitrarily many within-trajectory windows?

Previous concerns

partly addressedIn Section 2 and the Introduction, discuss and empirically compare against RKHS ε-machines (MMD-based predictive-state clustering), causal-state learning (arXiv:1906.10437) and continuous bisimulation metrics, and restate the contribution relative to them.Section 2 and Section 5's head-to-head comparison add the requested positioning and baselines, but the remaining test-based novelty distinction conflicts with EVIDENCE 27 and 38.
partly addressedIn Section 4, either extend Theorem 1 to the implemented procedure or run the Section 5 experiments with variant (T); the implemented procedure has three unanalysed features: permutation calibration, a data-selected median-heuristic bandwidth, BH dependence across shared-sample tests, and overlapping τ-mixing windows.Sections 3–5 explicitly separate P from T and add T experiments, but the new per-bin sampler does not generally sample the stated P_b and Appendix A's thinning argument does not describe that sampler.
addressedIn Proposition 1, add the conditions B≥n and per-class mass ≥2/B (or ≥1/B) to the statement, and reconcile the claim of exact purity with the vanishing contamination the Appendix B proof establishes.Proposition 1(i)–(iii) and Appendix B add the mass/alignment hypotheses and explicitly replace exact purity with vanishing contamination below a shrinking test threshold.
addressedResolve the Table 2 Tiger entry n̂=20 at N=10000 (impossible with B=8 and contradicted by Appendix D), and reconcile the GaussMix α (0.01 in Section 5 versus 0.05 in Appendix C).Table 2 now reports five twos, and Section 5, Appendix C and Appendix E consistently state GaussMix α=0.05 while disclosing that the historical CSV omitted α.
addressedIn Section 5, report partition-level accuracy (e.g. adjusted Rand against the latent classes) under a B-selection rule that does not use n, and implement the Wasserstein and DBC baselines faithfully (multivariate W1, standard DBC objective).Section 5 adds ARI under silhouette and fixed B=8, while Appendix C specifies multivariate optimal-transport W1 and a DBC bisimulation objective with learned Gaussian dynamics.
partly addressedIn Section 5 and Appendix D, support the HalfCheetah 'multi-step information' claim against a nonlinear speed baseline with trajectory-level train/test splits, and provide a repository URL or immutable artifact together with the missing result-file names.Section 5 supplies the requested held-out nonlinear comparison and withdraws the claim, but Appendix E's new repository/tag statement accompanies an empty filename and script manifest.

New concerns

New correctness issue in Section 3 and the new Section 5 T experiments: per_bin sampling changes the estimand because a trajectory with one bin visit and one with many visits contribute equally, whereas Definition 4 weights their visits equally; use the stated per_traj option or another exact P_b sampler and derive its actual sample budget.

recommendation: major_revision · score: 5/10 · confidence: 5/5

Sources checked (50)

Reviewer 3qwen/qwen3.8-max-0902

Summary

The paper extends Myhill–Nerode quotient learning to continuous observation–action spaces via quantile binning and kernel MMD tests, now explicitly positioning itself as a test-based formulation with a stated finite-sample target (the bin-level quotient) rather than claiming novelty for MMD-based predictive-state clustering, and providing experiments under both the analysed variant (T) and the practical procedure (P).

Novelty assessment

The paper itself now concedes that MMD-based predictive-state clustering is not new and cites RKHS ε-machines, causal-state learning, and bisimulation metrics as prior work; the genuinely new elements are the precise definition of the bin-level quotient as the estimable target, the resolution analysis, the alphabet-free bound for variant (T), and the honest empirical characterisation of when the practical procedure succeeds and fails.

Fact-checks

not enough evidenceBrodu and Crutchfield (2022) note that clustering algorithms for conditional distributions map to the RKHS setting 'by using the MMD test' (Section 2, Predictive-state clustering).
not enough evidenceGretton et al. (2012) provide the biased MMD deviation bound used in Theorem 1 (Section 4).
not enough evidenceFerns et al. (2011) show bisimulation metrics are well defined for continuous MDPs (Section 2, Bisimulation).
not enough evidenceNixon (2026b), arXiv:2603.21399, develops the Myhill–Nerode quotient theory for bounded agents in finite POMDPs (Introduction).
not enough evidenceZhang et al. (2019) approximate causal states with a recurrent encoder and k-means discretisation (Section 2, Causal-state learning).
not enough evidenceThe repository github.com/npow/quotient-learning-papers contains the code and result files at tag v1 (Section 5, Appendix E).

Strengths

The Introduction's 'what is not new' paragraph and Section 2's three new subsections now position the contribution honestly against RKHS ε-machines, causal-state learning, and bisimulation metrics, explicitly conceding that the idea of MMD-based predictive-state clustering is not new.
Section 3's definition of variant (T) with four explicit conditions (T1–T4) and Section 5's Table 3 directly test the analysed procedure, bridging the theory–implementation gap by showing (T) is conservative but correct where it resolves.
The P^fix ablation (Section 5, Table 3 findings (iii)) cleanly attributes over-splitting to the permutation/BH calibration rather than overlapping windows or per-pair bandwidths, providing a concrete mechanistic explanation.
The HalfCheetah value-prediction claim is properly withdrawn in Section 5 (Table 8) with a trajectory-level held-out analysis showing classes carry no information beyond a nonlinear function of speed, and the Kruskal–Wallis p-values are correctly demoted.

Weaknesses

The practical contribution remains thin: variant (T) is too conservative to resolve Tiger at N=3000 (needs ~10× more data), while procedure (P), which works at N=3000, has no formal guarantee; no environment is demonstrated where the method is both guaranteed and useful at practical sample sizes (Section 5, Table 3).
B-selection without knowledge of n remains unsolved: silhouette fails on K-cycle K≥4 (selects B=2, ARI 0.19–0.41) and fixed B=8 over-splits on most environments (Section 5, Table 2), so the method's positive results depend on externally supplied resolution.
The GRU causal-state baseline outperforms the proposed method on the hardest environments (K4: 0.92 vs 0.41; K8: 0.86 vs 0.19 at silhouette B) by conditioning on the full history, and the paper's one-step-key restriction (ℓ=1) is a structural limitation that prevents competing there (Section 5, Table 4).
PO-MuJoCo still returns n̂=B on every seed and configuration (Section 5, Table 6), providing no evidence that the method discovers meaningful quotient structure on realistic continuous control tasks.
The baselines are acknowledged re-implementations in a restricted setting (one-observation past, rescaled DBSCAN threshold, reward proxy for reward-free environments), so the head-to-head comparison's fairness cannot be fully assessed (Section 5, Table 4; Appendix C, Baselines).

Questions for authors

In Section 5 (Table 3, finding (iii)), the P^fix agreement with (P) is reported on only 40 comparable (seed, B-rule) pairs across a subset of environments; does the attribution of over-splitting to calibration hold on K-cycle K=8 and K=16 where the effects are largest?
In Section 4 (Proposition 1, part (iii)), the recovery argument requires m_N=Θ(N) i.i.d. samples per bin with no cap; how does the m_max=300 cap interact with the asymptotic recovery claim in practice?
In Section 5 (Table 4), the RKHS ε-machine with k-means/silhouette achieves 0.99 ARI on G3 and G5 with correct counts; what prevents using that method as the practical default and reserving the test-based formulation for settings requiring formal error statements?

Previous concerns

addressedIn Section 2 and the Introduction, discuss and empirically compare against RKHS ε-machines (MMD-based predictive-state clustering), causal-state learning (arXiv:1906.10437) and continuous bisimulation metrics, and restate the contribution relative to them.The Introduction's 'what is not new' paragraph, Section 2's three new subsections (Predictive-state clustering, Causal-state learning, extended Bisimulation), and the head-to-head Table 4 with five baselines directly address this.
addressedIn Section 4, either extend Theorem 1 to the implemented procedure or run the Section 5 experiments with variant (T); the implemented procedure has three unanalysed features: permutation calibration, a data-selected median-heuristic bandwidth, BH dependence across shared-sample tests, and overlapping τ-mixing windows.Section 3 defines variant (T) with four explicit conditions, Section 4's new subsection 'Which guarantee applies to which procedure' states precisely what is and is not covered, and Section 5 Table 3 reports experiments under (T) and the P^fix ablation.
addressedIn Proposition 1, add the conditions B≥n and per-class mass ≥2/B (or ≥1/B) to the statement, and reconcile the claim of exact purity with the vanishing contamination the Appendix B proof establishes.Proposition 1 is restated in three parts with explicit mass conditions (part (i): p_i≥2/B forces B≥2n; part (ii): alignment gives B≥n), and part (iii) explicitly withdraws the purity claim in favour of vanishing contamination.
addressedResolve the Table 2 Tiger entry n̂=20 at N=10000 (impossible with B=8 and contradicted by Appendix D), and reconcile the GaussMix α (0.01 in Section 5 versus 0.05 in Appendix C).Appendix E 'Corrections' explicitly identifies the Tiger entry as a typo (now 2,2,2,2,2), and the GaussMix α is reconciled by re-running at both levels and stating α=0.05 throughout.
addressedIn Section 5, report partition-level accuracy (e.g. adjusted Rand against the latent classes) under a B-selection rule that does not use n, and implement the Wasserstein and DBC baselines faithfully (multivariate W1, standard DBC objective).Section 5 Table 2 reports ARI under silhouette and B=8 (neither uses n), and Appendix C Baselines describes multivariate W1 with exact OT and DBC with the standard bisimulation loss.
addressedIn Section 5 and Appendix D, support the HalfCheetah 'multi-step information' claim against a nonlinear speed baseline with trajectory-level train/test splits, and provide a repository URL or immutable artifact together with the missing result-file names.Section 5 Table 8 withdraws the claim with a GroupKFold trajectory-level analysis showing classes are worse than gradient-boosted speed trees, and Appendix E provides the repository URL with result-file names.

New concerns

NEW: The P^fix ablation (Section 5, Table 3, finding (iii)) is reported on only a subset of environments and 40 (seed, B-rule) pairs; the attribution of over-splitting to calibration rather than overlapping windows is not established for the environments where over-splitting is most severe (K-cycle K≥4 at B=2K, Dec-Tiger at N=20000).

recommendation: minor_revision · score: 7/10 · confidence: 4/5

Author's response letter

Response to the major-revision decision (continuous quotient learning)

Everything below is backed by files in experiments/revision/results/ (new) or the earlier result files; code is at https://github.com/npow/quotient-learning-papers (cql/), artifacts at tag v1 (to be created). Section names refer to the revised main paper; "App." to the appendix (supplement).

Summary of what changed

Positioning vs. RKHS epsilon-machines, causal-state learning and bisimulation metrics rewritten (Intro, Sec. 2); contribution narrowed to a test-based formulation with a stated finite-sample target; empirical comparison added (Sec. 5, "Head-to-head comparison").
Theorem 1 scope stated precisely (Sec. 4, "Which guarantee applies to which procedure"); Section 5 experiments re-run under the analysed variant (T) (Sec. 5, "Experiments under the analysed variant (T)").
Proposition 1 corrected and its proof re-derived (Sec. 4, App. B).
Table 2 Tiger typo fixed; GaussMix alpha reconciled; a second unsupported claim (silhouette picks B=K on K-cycle) found and withdrawn.
Partition-level ARI under B-rules that do not use n; faithful W1 and DBC baselines; RKHS / causal-state / Ferns baselines.
HalfCheetah "multi-step information" claim withdrawn after a held-out, nonlinear-baseline analysis; result files named; repo URL added.
Several earlier positive claims weakened (listed at the end).

Concern 1

In Section 2 and the Introduction, discuss and empirically compare against RKHS epsilon-machines (MMD-based predictive-state clustering), causal-state learning (arXiv:1906.10437) and continuous bisimulation metrics, and restate the contribution relative to them.

Changed. Intro ("The gap ... and what is not new", "Our contribution (restated)") and Sec. 2 (new paragraphs "Predictive-state clustering with kernels" and "Causal-state learning with recurrent networks"; extended "Bisimulation" paragraph). Cited from sources read for this revision: Brodu & Crutchfield, Chaos 32(2):023103 (2022), arXiv:2011.14821 (their text states that clustering algorithms for conditional distributions map to RKHS "by using the MMD test"; method = regularised conditional mean embeddings, similarity matrix G^S, diffusion-map coordinates, DBSCAN); Jurgens & Brodu arXiv:2410.01076; Zhang et al. arXiv:1906.10437 (RNN trained to predict next observation/reward, discretised by k-means or learned discretiser); Goerg & Shalizi (LICORS, arXiv:1206.2398; Mixed LICORS, AISTATS 2013); Boots, Gordon, Gretton (UAI 2013); Ferns, Panangaden, Precup, SIAM J. Comput. 40(6) (2011). The paper now says explicitly that MMD-based predictive-state clustering is not new; the contribution is a test-based estimator with a stated finite-sample target (bin-level quotient), an analysed variant with a sample bound, and an empirical characterisation, not accuracy superiority.

Empirical comparison (Sec. 5, Table "baselines"; App. C.7; partition_baselines.csv). RKHS epsilon-machine (our implementation of the estimator equations, past = present observation; DBSCAN and k-means variants), GRU causal-state learner (full history), Ferns metric on the binned chain, DBC, multivariate W1. Not compared: the authors' released RKHS code, longer pasts for the RKHS method, LICORS / HSE-PSR (discussed only), the continuous-space Ferns metric (not computable from samples without an abstraction; we use the finite metric on the quantile-bin chain). Result: no method is uniformly best; the GRU baseline is best on K-cycle, the RKHS k-means variant is competitive on well-separated cases, Ferns/W1-silhouette beat ours at B=8 on K4 and lose at K8. The earlier claim that ours is "the only method correct on both" is withdrawn.

Concern 2

In Section 4, either extend Theorem 1 to the implemented procedure or run the Section 5 experiments with variant (T); ... permutation calibration, a data-selected median-heuristic bandwidth, BH dependence across shared-sample tests, and overlapping tau-mixing windows.

Changed (route: run under (T) and state precisely what is covered). Sec. 3 ("Variant (T)") defines (T1)-(T4): bins/bandwidth fitted on a design half, one window per trajectory and bin, independent sides, analytic threshold with alpha0 = delta/K^2, no BH. Implemented in continuous_quotient/variant_t.py (unit tests in tests/unit/test_variant_t.py). Theorem 1 is now stated for (T) only. New Sec. 4 subsection states: what carries over to the implemented procedure (P) (permutation validity gives a no-spurious-split statement if the bandwidth is permutation-invariant; this is only approximately true for the implementation's 500-point fixed-index subsample); that we have no BH/PRDS argument, no treatment of overlapping windows and no power guarantee for (P); hence all positive claims about (P) are empirical. Experiments (Sec. 5, "Experiments under the analysed variant (T)", Table "variantT"; partition_accuracy.csv, tiger_T_scaling.csv, dec_tiger_variant_t.csv): (T) matches (P) at B=n on K-cycle and most GaussMix, but is conservative: n_hat=1 on Tiger at N=3000 (resolved at N=10^4, 5/5 seeds), merges classes at B=8; on Dec-Tiger (T) does not over-split agent A (symmetric N=20000: R_crit 0.264 vs 0.262). An intermediate (P^fix = T's data pipeline with permutation+BH) reproduces (P)'s n_hat on 37/40 comparable runs, attributing (P)'s over-splitting to the calibration. Not done: no extension of Theorem 1 to (P); PO-MuJoCo and the 4-state chain were not re-run under (T) (no ground truth / not needed for the conclusion); N=100000 Tiger scaling was dropped for time.

Concern 3

In Proposition 1, add the conditions B>=n and per-class mass >=2/B (or >=1/B) to the statement, and reconcile the claim of exact purity with the vanishing contamination the Appendix B proof establishes.

Changed. Proposition 1 (Sec. 4) is restated in three parts: (i) under (a) only, |Q_B| <= min{B, 2n-1}, and n <= |Q_B| <= 2n-1 when B >= n and p_i >= 2/B (hence B >= 2n; the 1/B version needs cell alignment (b)); B < n is the counterexample to the old statement; (ii) under (a)+(b), p_i are positive multiples of 1/B (so B >= n follows) and Q*_B is the class partition; (iii) empirical bins are not pure: contamination fraction O_P(B/sqrt N) -> 0, and the estimator returns the partition because the induced MMD is below the threshold. App. B re-derives all parts and states what is not proved; the earlier "every non-empty bin is pure w.p. -> 1" is withdrawn (empirical edges miss the class gap unless F_N(sup I_i) = j_i/B exactly). Note: the (iii) recovery argument is for variant (T) with m_N = Theta(N) i.i.d. samples, as in the proof; it is not claimed for (P).

Concern 4

Resolve the Table 2 Tiger entry n_hat=20 at N=10000 ... and reconcile the GaussMix alpha (0.01 in Section 5 versus 0.05 in Appendix C).

Tiger. Traced: experiments/layer1_ground_truth/results/tiger_N_sensitivity.csv has n_classes = 2 on all five seeds at N=10000 (B=8, so 20 is impossible); "2, 2, 2, 2, 20" was a typo. Table 2 now reads 2, 2, 2, 2, 2 (consistent with App. D). Noted in App. "Artifacts ... Corrections". GaussMix alpha. The shipped CSV has no alpha column; the script default and App. C say 0.05, Sec. 5 said 0.01. Re-ran the manual-B configuration at both alpha (B=N_s, R=99, N=2000, seeds 0-2; gaussmix_alpha_check.csv): n_hat = N_s on all 12 runs at both levels, so the file cannot discriminate and the numbers are unaffected. The paper states alpha = 0.05, R = 99 throughout and says this explicitly.

Concern 5

report partition-level accuracy (e.g. adjusted Rand against the latent classes) under a B-selection rule that does not use n, and implement the Wasserstein and DBC baselines faithfully (multivariate W1, standard DBC objective).

Changed. Sec. 5, "Partition-level accuracy without knowledge of n" (Table "ari"; partition_accuracy.csv): ARI vs the latent state per step, B by silhouette or fixed B=8 (B=n as reference), 10 environments x 5 seeds, plus the best ARI attainable by any merge of the bins (bin-readout ceiling). Findings: silhouette recovers Tiger, K<=3 and GaussMix but picks B=2 on K-cycle K>=4 (ARI 0.19-0.41); fixed B=8 recovers only Tiger/K=2. Baselines (App. C.7): W1 is now multivariate on the full continuation vector with exact OT; DBC uses the standard bisimulation loss with a learned Gaussian latent dynamics model (reward proxy documented for reward-free envs). Found while doing this: the previous statement "silhouette chose B=K on K-cycle" had no result file and is contradicted by the run above; withdrawn.

Concern 6

support the HalfCheetah 'multi-step information' claim against a nonlinear speed baseline with trajectory-level train/test splits, or weaken the claim; provide ... result-file names and a repository URL.

Claim withdrawn. The classes are a function of the binned speed norm, so they cannot carry information beyond speed. New held-out analysis (experiments/layer2_mujoco/halfcheetah_groupsplit_value.py, halfcheetah_groupsplit_value.csv; 5-fold GroupKFold over trajectories, quotient refit on train folds, bootstrap over trajectories, 3 collection seeds): out-of-fold R^2 for the classes is below gradient-boosted trees on speed under both policies and both B rules (e.g. sinusoidal: 0.103 auto-B / 0.256 B=8 vs 0.302), classes+speed = speed alone, and trees on all 8 velocities reach 0.89 (sinusoidal). The Kruskal-Wallis p-values are demoted (dependent time steps). Result-file names are listed in App. "Artifacts, result files and corrections" with the repo URL and tag v1; the legacy first-coordinate-W1 and custom-DBC files are marked superseded.

Other claims weakened or withdrawn (found while checking)

Abstract: "90/90 at natural resolution or silhouette" -> 90/90 only at B=n; silhouette/fixed-B results reported.
"Permutation calibration ... only method correct on both": withdrawn.
Dec-Tiger over-splitting mechanism: the (P^fix, T) runs show over-splitting grows with N under permutation+BH; the main-text mechanism is left as is, with the new evidence reported.
Integration test tests/integration/test_kcycle_continuous.py failed before this revision because it used the package default B=8; it now uses B=K, R=199 (matching Table 1).

Not addressed / limitations

No theorem for (P); BH under dependence unproved.
"Pow 2026" remains unpublished; nothing new relies on it.
The RKHS/causal-state/DBC baselines are our re-implementations in the one-observation-past setting; DBSCAN threshold rescaled by us.
Dec-Tiger perm+BH at N=20000: 3 seeds only (runtime).

Full manuscript reviewed in round 2

← Round 1 Summary Round 3 →

Section	Changed	Removed
The gap: continuous spaces, and what is not new.	3	—
Our contribution (restated).	4	—
Predictive-state clustering with kernels (closest prior work).	2	—
Causal-state learning with recurrent networks.	2	—
Bisimulation and state abstraction.	1	1
Union–Find Quotient Estimator	1	1
Variant (T) (the analysed procedure).	7	—
Theoretical Analysis	2	2
Proof of Proposition 1 (corrected)	1	—
Notation.	2	—
Glivenko–Cantelli.	1	1
Part (i): under (a) only.	2	—
Part (ii): under (a) and (b).	2	—
Part (iii): empirical bins, what is and is not proved.	3	—
Under (a) alone, estimation.	2	—
Baselines (`experiments/revision/baselines_lib.py`)	9	—
Revision experiments (variant (T), partition accuracy)	2	—
Auto bin selection	1	1
Dec-Tiger per-seed results	1	1
PO-HalfCheetah class statistics and value prediction	3	3
Artifacts, result files and corrections	2	—
Result files (every number in the paper comes from one of these).	7	—
Corrections to the previous version.	12	—
The gap: continuous spaces.	—	2
Our contribution.	—	4
Proof of Proposition 1	—	1
Under (a) and (b).	—	4
Under (a) alone.	—	2
Baselines (`baselines/`)	—	2

Section	Changed	Removed
The gap: continuous spaces, and what is not new.	3	—
Our contribution (restated).	4	—
Predictive-state clustering with kernels (closest prior work).	2	—
Causal-state learning with recurrent networks.	2	—
Bisimulation and state abstraction.	1	1
Union–Find Quotient Estimator	1	1
Variant (T) (the analysed procedure).	7	—
Theoretical Analysis	2	2
Proof of Proposition 1 (corrected)	1	—
Notation.	2	—
Glivenko–Cantelli.	1	1
Part (i): under (a) only.	2	—
Part (ii): under (a) and (b).	2	—
Part (iii): empirical bins, what is and is not proved.	3	—
Under (a) alone, estimation.	2	—
Baselines (`experiments/revision/baselines_lib.py`)	9	—
Revision experiments (variant (T), partition accuracy)	2	—
Auto bin selection	1	1
Dec-Tiger per-seed results	1	1
PO-HalfCheetah class statistics and value prediction	3	3
Artifacts, result files and corrections	2	—
Result files (every number in the paper comes from one of these).	7	—
Corrections to the previous version.	12	—
The gap: continuous spaces.	—	2
Our contribution.	—	4
Proof of Proposition 1	—	1
Under (a) and (b).	—	4
Under (a) alone.	—	2
Baselines (`baselines/`)	—	2

Cite this paper

Share this paper

Share via

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

Round 2

Author's response letter

Response to the major-revision decision (continuous quotient learning)

Summary of what changed

Concern 1

Concern 2

Concern 3

Concern 4

Concern 5

Concern 6

Other claims weakened or withdrawn (found while checking)

Not addressed / limitations

Round 2

Author's response letter

Response to the major-revision decision (continuous quotient learning)

Summary of what changed

Concern 1

Concern 2

Concern 3

Concern 4

Concern 5

Concern 6

Other claims weakened or withdrawn (found while checking)

Not addressed / limitations

What changed in this revision

What changed in this revision