有限观察者下,不可区分状态可合并,形成最小唯一抽象。
The Myhill-Nerode Theorem for Bounded Interaction: Canonical Abstractions via Agent-Bounded Indistinguishability
- 基于有限控制器族定义可观测历史的伪度量,合并不可区分路径。
- 精确商空间对时钟感知目标完全充分,误差可控在观察利普希茨范围内。
- 适用于资源受限智能体建模,尤其适合分析策略简化与近似行为。
任何容量受限的观察者都会在其环境上诱导出一个规范的等价类:两个无法被有限智能体区分的状态,对该智能体而言是相同的。我们针对有限POMDP形式化了这一思想。一组固定的有限状态控制器构成的探测族,定义了观测历史上的闭环Wasserstein伪度量,并生成一个探测精确的商空间,该空间将所有无法被该族中任一控制器区分的历史合并。该商空间具有规范性、最小性和唯一性——是有限交互情形下的Myhill-Nerode定理。对于时钟感知探测器,该商空间对仅依赖于观测和动作的目标是精确决策充分的;对于隐状态奖励,我们采用观测利普希茨逼近界。核心定理对象为时钟感知商空间;可扩展的确定性平稳实验研究了一种可处理的粗粒化,其差距通过小规模精确案例测量,并在更大规模上进行实证探索。我们在Tiger和GridWorld上验证了定理级命题。此外,还在Tiger、GridWorld和RockSample上报告了操作性案例研究,作为近似行为与运行时间的探索性诊断,而非无跨族确证时的定理支撑证据;更重的压力测试已归档于附录与成果包中。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。