# The Myhill-Nerode Theorem for Bounded Interaction: Canonical Abstractions via Agent-Bounded Indistinguishability

arXiv: https://arxiv.org/abs/2603.21399 · HTML: https://mlsanity.com/paper/2603.21399/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 58 references that are in the map.
- First posted on arXiv 22 Mar 2026.

## Builds on (most cited first, 5 of 5)

- [Near Optimal Behavior via Approximate State Abstraction](https://mlsanity.com/paper/1701.04113/) (2017)
- [Towards Robust Bisimulation Metric Learning](https://mlsanity.com/paper/2110.14096/) (2021)
- [A Theory of Abstraction in Reinforcement Learning](https://mlsanity.com/paper/2203.00397/) (2022)
- [Solving POMDPs by Searching in Policy Space](https://mlsanity.com/paper/1301.7380/) (2013)
- [Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficiently](https://mlsanity.com/paper/2406.04056/) (2024)

## Built on by (most cited first, 3 of 3)

- [Remember the Decision, Not the Description: A Rate-Distortion Framework for Agent Memory](https://mlsanity.com/paper/2605.10870/) (2026)
- [Semantic Rate-Distortion for Bounded Multi-Agent Communication: Capacity-Derived Semantic Spaces and the Communication Cost of Alignment](https://mlsanity.com/paper/2604.09521/) (2026)
- [Minimal Recurrent Behavioral Memory for Imitation under Partial Observability](https://mlsanity.com/paper/2609.25757/) (2026)

## Abstract (arXiv)

Any capacity-limited observer induces a canonical quotient on its environment: two situations that no bounded agent can distinguish are, for that agent, the same. We formalise this for finite POMDPs. A fixed probe family of finite-state controllers induces a closed-loop Wasserstein pseudometric on observation histories and a probe-exact quotient merging histories that no controller in the family can distinguish. The quotient is canonical, minimal, and unique-a bounded-interaction analogue of the Myhill-Nerode theorem. For clock-aware probes, it is exactly decision-sufficient for objectives that depend only on the agent's observations and actions; for latent-state rewards, we use an observation-Lipschitz approximation bound. The main theorem object is the clock-aware quotient; scalable deterministic-stationary experiments study a tractable coarsening with gap measured on small exact cases and explored empirically at larger scale. We validate theorem-level claims on Tiger and GridWorld. We also report operational case studies on Tiger, GridWorld, and RockSample as exploratory diagnostics of approximation behavior and runtime, not as theorem-facing evidence when no exact cross-family certificate is available; heavier stress tests are archived in the appendix and artifact package.