Topology-Aware State Abstraction with Tangle Cores for Markov Decision Processes
About
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 benchmarks
| Task | Dataset | Result | Rank | |
|---|---|---|---|---|
| State Abstraction | Corridor-Rooms-9 | Abstraction Size (≥ 90% Return)6 | 7 | |
| State Abstraction | FourRooms | Abstract State Count4 | 7 | |
| State Abstraction | taxi | Abstract State Count (|S|)11 | 7 | |
| Abstraction construction and value iteration | Corridor-Rooms-9 | Construction Time (s)3.4 | 7 | |
| State Abstraction | Corridor-9 | Abstract State Count9 | 7 | |
| State Abstraction | Multi-Goal | Abstract State Count8 | 7 | |
| State Abstraction | Synth-Fold | Abstract State Count10 | 7 | |
| State Abstraction | Corridor-Rooms-4 (|S|=64) | Abstract State Count4 | 7 | |
| State Abstraction | Corridor-Rooms-9 (|S|=196) | Abstract State Count9 | 7 | |
| State Abstraction | Corridor-Rooms 16 (|S|=400) | |S|16 | 7 |