Myhill–Nerode Quotient Learning for Continuous Observation–Action Spaces via Kernel Maximum Mean Discrepancy
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 𝒪 × 𝒜 ⊆ ℝ^(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 (Blog (B/δ)/ε_(MMD)² + B²log (1/δ)) for an analysed variant (T) with one window per trajectory, in which the alphabet size |𝒞| of the finite bound is replaced by the MMD separation ε_(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 ≤ 16) and a Gaussian-mixture walk, but this uses n: with B chosen without n the adjusted Rand index drops on K-cycle (K ≥ 4) and the index is over-split. No baseline we implement (RKHS ε-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⁴ at B = 2, and merges all Gaussian-mixture classes at N ≤ 3000. We state which guarantee covers which procedure. On PO-MuJoCo the estimator returns 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 α = 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).