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

• URL: http://arxiv.org/abs/2603.21399v1
• Date: Sun, 22 Mar 2026 20:59:31 GMT
• Title: The Myhill-Nerode Theorem for Bounded Interaction: Canonical Abstractions via Agent-Bounded Indistinguishability
• Abstract summary: 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.<n>For clock-aware probes, it is exactly decision-sufficient for objectives that depend only on the agent's observations and actions.<n> scalable deterministic-stationary experiments study a tractable coarsening with gap measured on small exact cases and explored empirically at larger scale.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Local verification cannot detect non-transportability: a cohomological theory of context preservation in agentic reasoning [0.0]
  Agentic AI systems routinely transport conclusions across biological, clinical and financial contexts.<n>We show that the emerging safeguard of local verification is structurally incomplete.<n>We quantify the distortion under unequal precision and supply the precision-whitened form that restores exactness.
  arXiv  Detail & Related papers  (2026-08-04T21:09:50Z)
• Information-theoretic limits on undetectable parameter-estimation attacks in continuous-variable quantum key distribution [1.7205106391379026]
  We formalize a certificate-forgery hypothesis test and identify its detectability with an information-theoretic rate.<n>Relative to a set $mathcalM$ of trusted observables, the forgery- detectability rate $g_mathcal M$ of a benign-statistics certificate is the missed-detection Stein exponent.
  arXiv  Detail & Related papers  (2026-07-25T23:36:36Z)
• Operationally induced preferred basis in unitary quantum mechanics [0.0]
  The preferred-basis problem and the definite-outcome aspect of the measurement problem persist even if the detector is modeled unitarily.<n>A change of mathematical type constitutes the core of the 'cut': a structurally necessary interface from group-based kinematics to set-based counting.
  arXiv  Detail & Related papers  (2026-01-26T17:22:03Z)
• A Sample Efficient Conditional Independence Test in the Presence of Discretization [54.047334792855345]
  Conditional Independence (CI) tests directly to discretized data can lead to incorrect conclusions.<n>Recent advancements have sought to infer the correct CI relationship between the latent variables through binarizing observed data.<n>Motivated by this, this paper introduces a sample-efficient CI test that does not rely on the binarization process.
  arXiv  Detail & Related papers  (2025-06-10T12:41:26Z)
• Graph Stochastic Neural Process for Inductive Few-shot Knowledge Graph Completion [63.68647582680998]
  We focus on a task called inductive few-shot knowledge graph completion (I-FKGC) Inspired by the idea of inductive reasoning, we cast I-FKGC as an inductive reasoning problem. We present a neural process-based hypothesis extractor that models the joint distribution of hypothesis, from which we can sample a hypothesis for predictions. In the second module, based on the hypothesis, we propose a graph attention-based predictor to test if the triple in the query set aligns with the extracted hypothesis.
  arXiv  Detail & Related papers  (2024-08-03T13:37:40Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  This paper establishes new convergence results for textitgeodesic strongly monotone games.<n>Our key result shows that RGD attains last-iterate linear convergence in a textitgeometry-agnostic fashion.<n>Overall, this paper presents the first geometry-agnostic last-iterate convergence analysis for games beyond the Euclidean settings.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Nonparametric Identifiability of Causal Representations from Unknown Interventions [63.1354734978244]
  We study causal representation learning, the task of inferring latent causal variables and their causal relations from mixtures of the variables. Our goal is to identify both the ground truth latents and their causal graph up to a set of ambiguities which we show to be irresolvable from interventional data.
  arXiv  Detail & Related papers  (2023-06-01T10:51:58Z)
• Causal Discovery via Conditional Independence Testing with Proxy Variables [35.3493980628004]
  The presence of unobserved variables, such as the latent confounder, can introduce bias in conditional independence testing. We propose a novel hypothesis-testing procedure that can effectively examine the existence of the causal relationship over continuous variables.
  arXiv  Detail & Related papers  (2023-05-09T09:08:39Z)
• Exploiting Independent Instruments: Identification and Distribution Generalization [3.701112941066256]
  We exploit the independence for distribution generalization by taking into account higher moments. We prove that the proposed estimator is invariant to distributional shifts on the instruments. These results hold even in the under-identified case where the instruments are not sufficiently rich to identify the causal function.
  arXiv  Detail & Related papers  (2022-02-03T21:49:04Z)
• Discovering Latent Causal Variables via Mechanism Sparsity: A New Principle for Nonlinear ICA [81.4991350761909]
  Independent component analysis (ICA) refers to an ensemble of methods which formalize this goal and provide estimation procedure for practical application. We show that the latent variables can be recovered up to a permutation if one regularizes the latent mechanisms to be sparse.
  arXiv  Detail & Related papers  (2021-07-21T14:22:14Z)
• Nested Counterfactual Identification from Arbitrary Surrogate Experiments [95.48089725859298]
  We study the identification of nested counterfactuals from an arbitrary combination of observations and experiments. Specifically, we prove the counterfactual unnesting theorem (CUT), which allows one to map arbitrary nested counterfactuals to unnested ones.
  arXiv  Detail & Related papers  (2021-07-07T12:51:04Z)
• Disentangling Observed Causal Effects from Latent Confounders using Method of Moments [67.27068846108047]
  We provide guarantees on identifiability and learnability under mild assumptions. We develop efficient algorithms based on coupled tensor decomposition with linear constraints to obtain scalable and guaranteed solutions.
  arXiv  Detail & Related papers  (2021-01-17T07:48:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.