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

Authors

Publication Details

Published
2026-11-14
DOI
https://doi.org/10.68852/pf-261114.000002
Primary Topic
Reinforcement Learning in Robotics
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

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

Nissan Pow
Reinforcement Learning in Robotics
article

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

Nissan Pow
article en

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 𝒪 × 𝒜 ⊆ ℝ^(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).

Vol. 1
Reinforcement Learning in Robotics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon