arXiv:2606.00427cs.LG2026-06

用拓扑结构识别共享接口,实现更精准的状态抽象。

Topology-Aware State Abstraction with Tangle Cores for Markov Decision Processes

  • 基于图缠结构造重叠状态抽象,捕捉门、枢纽等共享接口。
  • 在瓶颈环境上压缩率提升20%-40%,回报损失更低。
  • 适合导航、图决策等具有共享接口结构的问题。

强化学习中的状态抽象通常基于奖励与转移相似性进行状态划分,但忽略了导航、图结构和层次决策中常见的共享接口模式(如门、枢纽、瓶颈)。本文提出“纠缠核抽象”(tangle-core abstraction),基于经验转移图的图缠结构建重叠状态抽象。该方法从一致方向的低阶分离中提取抽象状态,并通过成员核表示共享接口,而非硬划分。在显式动作一致性条件下,证明了诱导的重叠抽象马尔可夫决策过程具有值保持性;揭示了内部同质性/边界泄漏误差分解,并定量证明了硬划分会引入可避免的边界误差。实验表明,在含瓶颈的表格化域、程序生成迷宫及MiniGrid环境中,该方法在压缩率-回报权衡上优于奖励感知、学习型、拓扑地图和图划分基线。同时识别出转移拓扑无信息时的失效情形,此时缠结预测收益有限。结果表明,图缠结是具有共享接口结构决策问题的有效拓扑感知抽象先验。

原文摘要 · Abstract (English)

State abstraction in reinforcement learning is usually formulated as a partition of states based on reward and transition similarity. This excludes a common structural pattern in navigation, graph, and hierarchical decision problems: interface states such as doors, hubs, and bottlenecks naturally participate in more than one region. We introduce \emph{tangle-core abstraction}, an overlapping state-abstraction framework based on graph tangles of empirical transition graphs. The method constructs abstract states from consistently oriented low-order separations and represents shared interfaces through a membership kernel rather than a hard partition. We give value-preservation guarantees for the induced overlapping abstract MDP under an explicit action-consistency condition, identify an interior-homogeneity/boundary-leakage error decomposition, and prove a quantitative interface-overlap result showing when hard partitions incur an avoidable boundary error. Empirically, tangle-core abstractions achieve favorable compression--return tradeoffs against reward-aware, learned, topological-map, and graph-partitioning baselines across bottlenecked tabular domains, procedurally generated mazes, and MiniGrid representations. We also identify a clear failure regime in which transition topology is uninformative, where tangles predictably offer little benefit. These results position graph tangles as an effective topology-aware abstraction prior for decision problems with shared interface structure.

状态抽象拓扑学习强化学习图结构

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。