Topology-Aware State Abstraction with Tangle Cores for Markov Decision Processes
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 *tangle-core abstraction*, which discovers overlapping supports from consistently oriented low-order separations of empirical transition graphs and represents shared interfaces through a membership kernel. For the induced abstract MDP, we give a conditional value bound and connect its premises to auditable reward and transition diameters of the returned cores. A fixed-budget interface result identifies a setting where overlap avoids a boundary error of a two-state hard partition, separating representational capacity from recovery of the corresponding membership. Empirically, tangle-core abstractions achieve favorable compression–return tradeoffs against reward-aware, learned, topological-map, and graph-partitioning baselines in bottlenecked tabular domains, procedural mazes, and MiniGrid representations. Diagnostics and topology-poor controls delimit this advantage. These results position graph tangles as a topology-aware support-discovery prior for decision problems with coherent regions and shared interfaces.
est. 32% chance this paper gets accepted at ICLR 2027.
What do you think this paper will get?
All positions stay anonymous.