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

• URL: http://arxiv.org/abs/2606.00427v1
• Date: Fri, 29 May 2026 23:29:49 GMT
• Title: Topology-Aware State Abstraction with Tangle Cores for Markov Decision Processes
• Abstract summary: State abstraction in reinforcement learning is usually formulated as a partition of states based on reward and transition similarity.<n>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.<n>We introduce emphtangle-core abstraction, based on graph tangles of empirical transition graphs.
• Score: 6.908972852063454
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• SemFlowRAG: Directed Semantic Flow from Abstraction to Evidence for Complex Reasoning [15.817479351881062]
  SemFlowRAG is a framework that reconstructs the flat retrieval space into a corpus-adaptive gradient semantic graph.<n>By quantifying the semantic abstractness of entities through the embedding variance of their associated passages, we transform static undirected edges into directed semantic constraints.<n>We show that SemFlowRAG effectively mitigates the probability black holes'' issue, outperforming existing baselines in both retrieval and downstream reasoning performance.
  arXiv  Detail & Related papers  (2026-06-26T08:40:08Z)
• Performance-Driven Environment Abstraction with Multi-Timescale Learning [14.594941665205148]
  We study performance-driven environment abstraction for decision-making in large Markov decision processes.<n>We model abstraction as a controlled approximation obtained by aggregating the state space.<n>For a fixed partition, we establish a performance guarantee that separates value-function approximation error from the loss introduced by action sharing.
  arXiv  Detail & Related papers  (2026-06-16T00:19:23Z)
• Adaptive state-action abstractions via rate-distortion [52.25810164390199]
  Reinforcement learning offers multiple techniques for building simple versions of complex tasks.<n>This paper proposes one such principle: refine the abstraction as soon as the learning error within it becomes comparable to the error induced by the abstraction itself.
  arXiv  Detail & Related papers  (2026-06-04T13:10:18Z)
• OcclusionFormer: Arranging Z-Order for Layout-Grounded Image Generation [49.49933361280724]
  We introduce OcclusionFormer, a novel framework that explicitly models Z-order priority by decoupling instances.<n>We also introduce a queried alignment loss that explicitly supervises individual instances and enhances semantic consistency.<n>The proposed method effectively reduces ambiguity in overlapping regions, enforces correct occlusion dependencies, and preserves structural integrity, leading to substantial accuracy gains across diverse scenes.
  arXiv  Detail & Related papers  (2026-05-20T16:10:44Z)
• Grouping Nodes With Known Value Differences: A Lossless UCT-based Abstraction Algorithm [64.43268969806098]
  A core challenge of Monte Carlo Tree Search (MCTS) is its sample efficiency, which can be improved by grouping state-action pairs.<n>We break with the paradigm of grouping value-equivalent states or state-action pairs and instead group states and state-action pairs with possibly different values.<n>We call this abstraction framework Known Value Difference Abstractions ( KVDA), which infers the value differences by analysis of the immediate rewards.
  arXiv  Detail & Related papers  (2025-10-29T11:03:44Z)
• Causal Abstractions, Categorically Unified [9.341830361844337]
  We present a categorical framework for relating causal models that represent the same system at different levels of abstraction.<n>Our approach unifies and generalizes previously considered causal abstractions.<n>We discuss how methods from mechanistic interpretability, such as circuit analysis and sparse autoencoders, fit within our framework.
  arXiv  Detail & Related papers  (2025-10-06T17:09:30Z)
• Causal Abstraction Inference under Lossy Representations [53.18851962820361]
  We introduce a new type of abstractions called projected abstractions that generalize existing definitions to accommodate lossy representations.<n>We show how to construct a projected abstraction from the low-level model and how it translates equivalent observational, interventional, and counterfactual causal queries from low to high-level.
  arXiv  Detail & Related papers  (2025-09-25T21:20:42Z)
• Aligning Graphical and Functional Causal Abstractions [0.0]
  Causal abstractions allow us to relate causal models on different levels of granularity.<n>Two methods for causal abstractions are common in the literature: (i) graphical abstractions, such as Cluster DAGs, which relate models on a structural level, and (ii) functional abstractions, like $alpha$-abstractions, which relate models by maps between variables and their ranges.
  arXiv  Detail & Related papers  (2024-12-22T16:11:25Z)
• Transitivity Recovering Decompositions: Interpretable and Robust Fine-Grained Relationships [69.04014445666142]
  Transitivity Recovering Decompositions (TRD) is a graph-space search algorithm that identifies interpretable equivalents of abstract emergent relationships. We show that TRD is provably robust to noisy views, with empirical evidence also supporting this finding.
  arXiv  Detail & Related papers  (2023-10-24T16:48:56Z)
• Self-Learning with Rectification Strategy for Human Parsing [73.06197841003048]
  We propose a trainable graph reasoning method to correct two typical errors in the pseudo-labels. The reconstructed features have a stronger ability to represent the topology structure of the human body. Our method outperforms other state-of-the-art methods in supervised human parsing tasks.
  arXiv  Detail & Related papers  (2020-04-17T03:51:30Z)
• Structured Prediction with Partial Labelling through the Infimum Loss [85.4940853372503]
  The goal of weak supervision is to enable models to learn using only forms of labelling which are cheaper to collect. This is a type of incomplete annotation where, for each datapoint, supervision is cast as a set of labels containing the real one. This paper provides a unified framework based on structured prediction and on the concept of infimum loss to deal with partial labelling.
  arXiv  Detail & Related papers  (2020-03-02T13:59:41Z)

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.