mlsanityData to 14 Oct 2026

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

arXiv 2606.00427 ↗First posted 29 May 2026cs.LGcited by 0

On the map: Deep reinforcement learning methods → Deep RL algorithms and representations

Abstract (arXiv)

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 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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods. Builds on 7 of its 21 references that are in the map. First posted on arXiv 29 May 2026.

Builds on

7 of 21 references.

Closest ancestors · 1

Same direction, newest first

  1. 2026Impact of Connectivity on Laplacian Representations in Reinforcement Learning9 Mar

Other references · 6

  1. 2020Learning Invariant Representations for Reinforcement Learning without Reconstructioncited by 436
  2. 2023Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Taskscited by 327
  3. 2018Semi-parametric Topological Memory for Navigationcited by 209
  4. 2019Scalable methods for computing state similarity in deterministic Markov Decision Processescited by 133
  5. 2017A Laplacian Framework for Option Discovery in Reinforcement Learningcited by 110
  6. 2020Clustering with Tangles: Algorithmic Framework and Theoretical Guaranteescited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Stochastic Dynamics on Persistence Diagram Space via Reinforcement Learning
  2. 2024Geometric Active Exploration in Markov Decision Processes: the Benefit of Abstraction
  3. 2026Performance-Driven Environment Abstraction with Multi-Timescale Learning
  4. 2026From Connectivity to Rewards: Dense Reward Learning with Directed State Graphs
  5. 2026Cochain Perspectives on Temporal-Difference Signals for Learning Beyond Markov Dynamics
  6. 2026Compositional Behavioral Semantics for State Abstraction in Reinforcement Learning
  7. 2024Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective
  8. 2024Symbolic State Partitioning for Reinforcement Learning