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

Submitted Nov 13, 2026 11:30 PM

First roundSummary Round 2 →

Reviewed under an earlier abstract

Abstract

Model-free identification of the minimal world-model of a bounded agent in a partially observable Markov decision process (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. When observations and actions are continuous the continuation alphabet is infinite and the G-test is undefined. We extend quotient learning to continuous observation–action spaces $`\calO\times\calA\subseteq\bbR^d`$. Histories are keyed by coarse quantile bins of the observation stream and, 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; bins whose test does not reject are merged by union–find. We (i) identify the estimator’s target precisely—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(\Khist(\tau{+}k)\log(\Khist/\delta)/(T\epsMMD^2)\big)`$, with $`\Khist=O(n)`$ active bins, in which the alphabet size $`|\calC|`$ of the finite bound is replaced by the MMD separation $`\epsMMD`$ (dimension enters only through $`\epsMMD`$); and (iii) characterise the finite-sample behaviour as a *resolution* effect: distinctions below the test’s detection scale are merged, so the returned quotient size depends on the bin count $`B`$ and on the per-test sample budget. Empirically, at the natural resolution ($`B{=}n`$ aligned bins, or $`B`$ chosen by silhouette auto-selection) the estimator returns the latent index on 90/90 runs across Tiger ($`\sigma{=}0.5`$), K-cycle ($`K\le16`$) and a Gaussian-mixture random walk, while G-test, Wasserstein-threshold and DBC baselines fail on K-cycle; over-provisioning $`B{=}2K`$ mis-estimates the index for $`K\ge3`$ (over-splitting up to $`2K`$, and chaining-induced under-splitting at $`K{=}16`$), as the resolution analysis predicts. On PO-MuJoCo the estimator returns $`\hat n{=}B`$ (all bin pairs separable) with classes that are strongly return-stratified. On a 4-state chain Dec-POMDP the estimated critical communication rate $`\hat R_{\rm crit}=H(\hat Q_A\mid\hat Q_B)`$ tracks the analytical value within $`0.8\%`$ mean error whenever both agents’ quotients are non-trivial; on Dec-Tiger the estimate is accurate on the seeds where agent A recovers two classes but agent-A over-splitting (which inflates the conditional entropy) occurs on 5/10 seeds at $`\alpha{=}0.05`$. We report all seeds and discuss the limitations candidly.

Editorial decisionAdvanced to the reviewer panelMajor revision requested

editor · claude-opus-5.5

Key concerns to address

In 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.
In 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.
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.
Resolve 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).
In 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).
In 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.

Message to authors

Thank you for a carefully argued and unusually candid submission; the bin-level quotient and the resolution analysis are a useful framing. We are requesting major revision. The most important issue is novelty: prior RKHS ε-machine work already clusters predictively equivalent continuous histories with MMD tests. Section 2 must engage with that work and with causal-state learning, and the contribution should be repositioned accordingly. Second, Theorem 1 must cover the procedure you actually run, or the experiments must use the analysed variant. Proposition 1 also needs corrected hypotheses. Third, please fix the Table 2 inconsistency, report partition-level accuracy with B chosen without knowledge of n, and strengthen the baselines and the value-prediction analysis. Please also release the code and result files at a stable location.

Full manuscript reviewed in round 1

First roundSummary Round 2 →

Cite this paper

Share this paper

Share via

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

Round 1

Round 1