論文の概要: The Myhill-Nerode Theorem for Bounded Interaction: Canonical Abstractions via Agent-Bounded Indistinguishability

• arxiv url: http://arxiv.org/abs/2603.21399v1
• Date: Sun, 22 Mar 2026 20:59:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-24 19:11:39.399599
• Title: The Myhill-Nerode Theorem for Bounded Interaction: Canonical Abstractions via Agent-Bounded Indistinguishability
• Title（参考訳）: 境界相互作用のためのMyhill-Nerode理論:エージェント境界不明瞭性による標準的抽象化
• Authors: Anthony T. Nixon,
• Abstract要約: 有限状態コントローラの固定プローブ族は、観測履歴に擬似的に閉ループのワッサーシュタインを誘導し、家族内のコントローラが区別できないようなプローブ・エクサクタントなマージ履歴を誘導する。 時計を意識したプローブでは、エージェントの観察と行動にのみ依存する目的に対して、決定に十分である。 スケーラブルな決定論的定常実験は、小さな精度のケースで測定されたギャップで引き込み可能な粗大化を研究し、より大きなスケールで経験的に探索した。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: キャパシティ制限されたオブザーバは、その環境において正準商を誘導する: 有界なエージェントが区別できない2つの状況は、そのエージェントに対して同じである。 これを有限 POMDP に対して定式化する。 有限状態コントローラの固定プローブ族は、観測履歴に擬似的に閉ループのワッサーシュタインを誘導し、家族内のコントローラが区別できないようなプローブ・エクサクタントなマージ履歴を誘導する。 商は、ミヒル・ネローデの定理の正準、極小、一意的に有界な相互作用アナログである。 クロック対応プローブでは、エージェントの観察と行動にのみ依存する目的に対して、正確に決定に十分である。 主な定理対象は、時計を意識した「スケーラブルな決定論的定常実験」であり、小さな精度のケースで測定されたギャップで引き込み可能な粗さを研究し、より大きなスケールで経験的に探索した。 我々はTigerとGridWorldの定理レベルのクレームを検証する。 また,Tiger,GridWorld,RockSampleの運用ケーススタディを,正確なクロスシークレット証明書が存在しない場合の定理的証拠ではなく,近似行動と実行時の探索的診断として報告し,重度ストレステストは付録およびアーティファクトパッケージにアーカイブする。

関連論文リスト

• Operationally induced preferred basis in unitary quantum mechanics [0.0]
  検知器が一元的にモデル化された場合でも、好ましくも好ましくも、測定問題の定値出力面は持続する。 数学的タイプの変化は、グループベースの運動学からセットベースの数え上げまで、構造的に必要不可欠なインターフェイスである「カット」の中核を構成する。
  論文  参考訳（メタデータ） (2026-01-26T17:22:03Z)
• A Sample Efficient Conditional Independence Test in the Presence of Discretization [54.047334792855345]
  離散化されたデータに直接条件付き独立テスト(CI)は、誤った結論につながる可能性がある。 最近の進歩は、観測データをバイナライズすることで、潜伏変数間の適切なCI関係を推測することを目指している。 そこで本研究では,バイナライゼーションプロセスに依存しないサンプル効率のCIテストを提案する。
  論文  参考訳（メタデータ） (2025-06-10T12:41:26Z)
• Graph Stochastic Neural Process for Inductive Few-shot Knowledge Graph Completion [63.68647582680998]
  I-FKGC(inductive few-shot knowledge graph completion)と呼ばれる課題に焦点をあてる。 帰納的推論(inductive reasoning)の概念に着想を得て,I-FKGCを帰納的推論問題とした。 本稿では,仮説の連成分布をモデル化したニューラルプロセスに基づく仮説抽出器を提案する。 第2のモジュールでは、この仮説に基づいて、クエリセットのトリプルが抽出された仮説と一致するかどうかをテストするグラフアテンションベースの予測器を提案する。
  論文  参考訳（メタデータ） (2024-08-03T13:37:40Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  本稿では,テクスト幾何学的強単調ゲームに対する新たな収束結果を確立する。 我々のキーとなる結果は、RGDがテクスト幾何学的手法で最終定位線形収束を実現することを示しています。 全体として、ユークリッド設定を超えるゲームに対して、幾何学的に非依存な最終点収束解析を初めて提示する。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• Nonparametric Identifiability of Causal Representations from Unknown Interventions [63.1354734978244]
  本研究では, 因果表現学習, 潜伏因果変数を推定するタスク, およびそれらの変数の混合から因果関係を考察する。 我々のゴールは、根底にある真理潜入者とその因果グラフの両方を、介入データから解決不可能なあいまいさの集合まで識別することである。
  論文  参考訳（メタデータ） (2023-06-01T10:51:58Z)
• Causal Discovery via Conditional Independence Testing with Proxy Variables [35.3493980628004]
  潜伏した共同設立者のような未観測変数の存在は、条件付き独立テストにバイアスをもたらす可能性がある。 本研究では,連続変数に対する因果関係の存在を効果的に検証できる仮説テスト手法を提案する。
  論文  参考訳（メタデータ） (2023-05-09T09:08:39Z)
• Exploiting Independent Instruments: Identification and Distribution Generalization [3.701112941066256]
  我々は、より高い瞬間を考慮に入れ、分布一般化の独立性を利用する。 提案した推定器は楽器の分布シフトに不変であることを示す。 これらの結果は、楽器が因果関数を識別するのに十分な豊かでない場合においても成り立つ。
  論文  参考訳（メタデータ） (2022-02-03T21:49:04Z)
• Nested Counterfactual Identification from Arbitrary Surrogate Experiments [95.48089725859298]
  観測と実験の任意の組み合わせからネスト反事実の同定について検討した。 具体的には、任意のネストされた反事実を非ネストされたものへ写像できる反ファクト的非ネスト定理(英語版)(CUT)を証明する。
  論文  参考訳（メタデータ） (2021-07-07T12:51:04Z)
• Disentangling Observed Causal Effects from Latent Confounders using Method of Moments [67.27068846108047]
  我々は、軽度の仮定の下で、識別性と学習可能性に関する保証を提供する。 我々は,線形制約付き結合テンソル分解に基づく効率的なアルゴリズムを開発し,スケーラブルで保証可能な解を得る。
  論文  参考訳（メタデータ） (2021-01-17T07:48:45Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。