acceptodds
Under review as a conference paper at ICLR 2027

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.

Primary area:
reinforcement learning
Keywords:
reinforcement learning, state abstraction, Markov decision processes, graph tangles, topology-aware abstraction

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_GFz5OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces tangle-core abstractions, a topology-aware approach to discovering overlapping regions in empirical transition graphs. It provides extensive theoretical results, including value bounds and fixed-budget interface guarantees, clarifying when overlapping representations can improve decision-making. Empirical evaluations across several domains demonstrate favourable compression–return trade-offs compared with existing baselines, while diagnostic experiments identify the settings in which the approach is most effective.

Critical strengths
  1. The theoretical part is strong and helps clarify the context and scale of the paper.

  2. The proposed method is presented clearly, intuitively, and in a well-structured manner, making the overall framework, its key components, and their interactions easy to follow and understand. The paper coherently explains the methodological design and clearly motivates the role of each component within the broader approach. This clarity helps readers understand the underlying rationale and appreciate how the different components work together to achieve the intended objectives.

Critical weaknesses
  1. The paper would benefit from a more comprehensive analysis of the computational costs of tangle-core abstractions relative to competing methods, as such results are currently reported only for the Corridor-9 environment. Although the proposed framework demonstrates promising performance, its additional computational overhead may limit its practical applicability. The authors should therefore report and compare metrics such as training time or return-training time curves across tangle-core abstractions and baseline methods in more environments. If the performance gains are modest relative to the additional computational costs, the practical benefits of the proposed approach may be less substantial than the results suggest.

  2. The effectiveness and scalability of the proposed method would be better demonstrated by evaluating it on additional, more challenging discrete environments beyond those considered in the paper. Potential examples include larger MiniGrid MultiRoom and DoorKey environments, as well as procedurally generated navigation tasks with multiple goals, bottlenecks, and more complex topologies. Experiments across environments of increasing size and complexity would provide stronger evidence of the method's scalability and clarify whether its advantages persist in more challenging settings.

Questions for authors

Please refer to the Weaknesses section, as it reflects my main concerns and questions for the authors. Any additional clarifications would be appreciated. Regarding scalability, further experiments are not strictly necessary; additional intuition or empirical evidence would also help address my concerns.

1 comment
AuthorsOpenReview ↗

Response to Reviewer GFz5

Thank you for the positive assessment and the request for cost results. The table summarizes our answers, and the text after it gives the details.

Your pointOur answerWhere in the revision
Compute beyond Corridor-9Tangle construction takes 0.4–18.5 s across the main environments and 2.7–8.6 s on Taxi, MultiRoom-N6, and DoorKey. On sixteen rooms with matched execution, tangle cores break even after 76 queries against ground value iteration.Tables 3, 21, and 24
Larger MiniGrid environmentsMultiRoom-N6 and DoorKey-16×16 with the shared controller: 6 and 5 abstract states for tangle cores, against 57 and 46 for bisimulation, at a return lower by 0.4 and 0.6 points.Table 23
More intuitionThe introduction, Section 2, and Section 3 are rewritten, and Figure 1 shows the pipeline.Sections 1–3; Figure 1

Sixteen-room comparison. All methods share the ground data, the execution assistance, the compression-selection rule, and paired start and goal queries. Independently generated layouts are the replication units.

MethodNormalized returnConstruction (s)Planning per query (s)
Ground value iteration100.0%0.00.12
Detected-B, matched execution98.6%4.20.03
Tangle cores, matched execution98.4%7.60.02

Let a baseline have construction time CBC_B and planning time tBt_B, and let the tangle method have CTC_T and tT<tBt_T<t_B. Tangle cores then have the lower total cost once the number of queries exceeds (CT−CB)/(tB−tT)(C_T-C_B)/(t_B-t_T). This is 76 queries against ground value iteration and 340 against Detected-B. The comparison therefore concerns a tradeoff between return and amortized cost, not a single-query advantage. At a larger scale, the construction on a sparse graph of 25,000 states and 101,400 edges takes 171.4±9.7171.4\pm9.7 seconds and 2.1 GB on one AMD EPYC 7543 core (Section 3).

Construction time in every environment. The tangle-core runtime is 0.8 s on FourRooms, 3.4 s on Corridor-9, 6.2 s on Multi-Goal, 18.5 s on Synthetic-Folding, 4.1 s per random maze, 5.5 s on MiniGrid, and 0.4 s on Chain-100 (Table 3). On Taxi, MultiRoom-N6, and DoorKey-16×16 it is 2.7 s, 8.6 s, and 6.9 s, and core discovery takes most of it (Table 24). Value iteration on the abstract model takes at most 0.08 s.

Larger MiniGrid domains. Every abstraction uses the same gateway controller.

EnvironmentMethodAbstract statesReturn / success
MultiRoom-N6Bisimulation57 ± 696.5 ± 0.6%
Spectral clustering16 ± 293.2 ± 1.1%
Detected-B8 ± 195.6 ± 0.8%
Tangle-Core6 ± 196.1 ± 0.7%
DoorKey-16×16Bisimulation46 ± 595.8 ± 0.7%
Spectral clustering12 ± 292.1 ± 1.3%
Detected-B7 ± 194.5 ± 0.9%
Tangle-Core5 ± 195.2 ± 0.8%

Tangle cores use far fewer abstract states than bisimulation at a slightly lower return. They use fewer states than Detected-B and spectral clustering at a higher return. This is a compression–return tradeoff, not an advantage in absolute return.

We hope the cost results help, and we would be glad to answer further questions.

Reviewer_A1kvOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

In this paper, the authors propose a novel state partitioning method for finite MDPs by using tangles cores to find abstractions where the tangle cores do not overlap whilst also discovering bottlenecks where they do. The authors use the proposed tangle-core approach for reinforcement learning state compression based returns using fewer state partitions than related baselines methods.

Critical strengths

In tabular bottleneck heavy domains, the tangle-core abstraction identifies partitions well.

Critical weaknesses

The writing and presentation quality is general poor throughout. It would have been a clear improvement to have had visualizations of the domains and tangle-cores/partitions, especially in domains such as mini-grid which is using a latent representation which can not be inferred from the current writing and presentation. It is not clear how effective the method would be comparatively in domains without substantial bottleneck elements or generally in many deep reinforcement learning setting such as robotic or Atari domains. There is missing related work and potential baselines from centrality measures which have been used to identify bottlenecks.

Questions for authors

In the tabular case where the graph is known, there are many methods which can (and have) been used to identify bottlenecks that have been applied to reinforcement learning such as betweenness centrality [1] and there are other related measures such as bridge centrality [2]. Can the authors include comparisons of their approach against these measures and discuss the related work.

The results include a latent construction of the tangle-cores in MiniGrid, can the authors discuss in more detail how this is obtained, and does this extend to other domains, such as those from D4RL[3]? A recent paper uses Laplacian representations based commute time estimates to estimate bottlenecks in robotic domains [4] called OGCRL, can the authors compare their tangle-core approach against the bottleneck discovery approach within OGCRL in one or two of the same robotic domains used in the OGCRL paper?

[1] Şimşek and Barto, Skill Characterization Based on Betweenness. In NeurIPS 2008.

[2] Jones et. al., Bridge Centrality: A Network Approach to Understanding Comorbidity. In Multivariate Behavioral Research, 2021.

[3] Fu et. al., D4RL: Datasets for Deep Data-Driven Reinforcement Learning, arXiv, 2024

[4] Liang et. al., Bottleneck-Guided Spectral Subgoals For Offline Goal-Conditioned RL, Forty-third International Conference on Machine Learning, 2026.

1 comment
AuthorsOpenReview ↗

Response to Reviewer A1kv

Thank you for the review and for the pointers to related work. The table summarizes our answers, and the text after it gives the details.

Your pointOur answerWhere in the revision
VisualizationsFigure 1 shows the pipeline and Figure 2 the returned FourRooms supports.Figures 1–2
Betweenness and bridge-centrality baselinesDetected-B ranks states by shortest-path betweenness, in the spirit of Şimşek and Barto (2008). New shortest-path and current-flow betweenness controls use 9–11, 27–31, and 19–22 abstract states on FourRooms, Corridor-9, and Multi-Goal, against 4, 9, and 8 for tangle cores, at equal or lower return.Section 5; Tables 8–9 and 26; Appendix A
MiniGrid latent detailsA convolutional VAE on the symbolic 16×16×3 grid with a 64-dimensional latent mean, and a 10-nearest-neighbor graph on the standardized means. Table 17 uses the lifted membership-weighted policy.Table 22 (Appendix C.11); Appendix C.1
D4RL and OGCRLOur evaluation covers tabular navigation, procedural grid environments, and latent MiniGrid abstractions. It does not establish performance on Atari, continuous-control robotics, or D4RL tasks, and Section 6 now says so. Appendix A positions D4RL.Section 6; Appendix A

Centrality baselines. Detected-B ranks nodes by normalized shortest-path betweenness on the empirical graph, deletes those above a threshold, and forms regions from the remaining components. It then either duplicates the detected interface nodes into adjacent regions or assigns them to one region. Its threshold uses the same held-out compression–return rule as our method. On 100 procedural layouts, the interface F1 of the returned cores is 0.91, against 0.78 for detected-bottleneck overlap and 0.54 for spectral clustering (Table 8). On Random Mazes, Detected-B-Overlap uses 17.9 states for 98.4% return, against 12.4 states and 98.6% for tangle cores. It also has 27 of 100 layouts below 98% return, against 21 (Table 9). Table 26 adds two controls that use the shared gateway controller. One ranks states by shortest-path betweenness and the other by current-flow betweenness. High-centrality states become interfaces, and the components left after their removal become the regions. Tangle cores use 4, 9, and 8 abstract states on FourRooms, Corridor-9, and Multi-Goal, against 9 and 11, 27 and 31, and 22 and 19 for the two controls. Their return is equal or higher: 99.0%, 99.2%, and 99.1%, against 98.7–99.0% for the controls.

Why tangles differ from centrality. Betweenness and bridge centrality rank individual states. Tangle cores instead orient every candidate low-order cut consistently and return overlapping regions. The overlap ablation shows why this matters: forcing a hard assignment drops Multi-Goal return from 97.1% to 89.3%, driven by a rise in local transition error to 0.38 (Table 2). Appendix A now discusses Şimşek and Barto (2008), bridge centrality, and offline navigation datasets such as D4RL.

MiniGrid latent model. The encoder takes the full 16×16×3 symbolic grid and applies three stride-2 convolutions with 32, 64, and 128 channels and ReLU. The latent is a 64-dimensional Gaussian mean, the decoder mirrors the encoder, and the objective is reconstruction plus a 10−310^{-3} KL penalty. Training uses Adam at learning rate 10−310^{-3}, batch size 256, and 100 epochs on 50,000 observations. The graph connects each frozen latent mean to its 10 nearest neighbors with Gaussian weights. The coordinates are standardized and the bandwidth is set to the median neighbor distance, both on fitting data only. The selected tangle order is 3 (Table 22).

We hope the added positioning and details address your concerns, and we would be glad to answer further questions.

Reviewer_LTo4OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes topology-aware state abstraction using overlapping tangle cores discovered from empirical transition graphs. It provides conditional value bounds and evaluates compression–return tradeoffs across tabular navigation tasks and learned representations.

Critical strengths

The motivation is clear: doorway and bottleneck states can belong to multiple regions. The overlap ablations and comparisons with detected bottlenecks help isolate this idea. The negative controls also provide useful evidence about where the method stops helping.

Critical weaknesses
  1. The residual audit does not match the stated definitions. FourRooms has four cores with uniform nonzero memberships of at least (1/4). Table 13 reports (d_r=1), so two states with rewards 0 and 1 share a core. If that core’s abstract reward is (h), their reconstruction errors are at least (h/4) and ((1-h)/4). The maximum residual is therefore at least 0.125, whereas the table reports 0.003. Are these occupancy-averaged errors? If so, they cannot be substituted into Theorem 3 to obtain the certificates in Table 10.
  2. The equivalence in Definition 1 is false for overlapping vertex separations. Three big sides can intersect only at separator vertices while the corresponding small sides cover the entire graph. Which condition does the implementation check? This needs to be resolved before the returned cores can be assessed.
  3. The execution protocol is missing a key detail. How is the abstract policy converted into actions in the original environment? With one core per room, interior states have identical memberships. The paper needs to explain how within-room navigation is handled and whether any local controller or options are used.
Questions for authors

Please address the questions raised in the Weaknesses section. These concerns are the main reasons for my current rating, and resolving them could change my assessment.

3 comments
AuthorsOpenReview ↗

Response to Reviewer LTo4 – Part 1

Thank you for the review. The table summarizes how the revision resolves the issues.

Your pointOur answerWhere in the revision
Table 10's residuals cannot be uniform residualsCorrect. They are averages under the construction occupancy μ\mu. Remark 1 gives the uniform floor qxqy/(qx+qy)q_xq_y/(q_x+q_y), which is 1/8 at memberships of 1/4. BB is now a plug-in diagnostic, and Proposition 9 gives the bounds that averaged residuals support.Section 4; Section 5; Tables 10, 13, and 20
The "equivalently" in Definition 1 is falseCorrect. The condition is a common vertex of the strict big sides Bi∖AiB_i\setminus A_i. Section 2 gives the star counterexample, and the code checks the corrected condition.Section 2; Section 3
How actions are executed within roomsA shared gateway controller. The planner picks the next core, and the controller moves by shortest path toward the nearest interface, so interior states of one room can take different actions. All methods in these tables share it.Section 5; Appendix C.1

Residuals and certificates. Your bound is right. Suppose a core contains states xx and yy whose rewards for the same action are 0 and 1, with memberships qxq_x and qyq_y. Then the uniform reward residual is at least qxqy/(qx+qy)q_xq_y/(q_x+q_y) (Remark 1). This is 1/8 at memberships of 1/4 and 1/2 at full membership, so the 0.003 in Table 10 cannot be a uniform residual. Table 10 averages residuals under the occupancy μ\mu of the construction data, which is the weighting used to fit the abstract model, and the revision labels it so. Its BB is therefore a plug-in diagnostic, not a certificate.

The new Proposition 9 states what averaged residuals do support. Part (a) bounds the ν\nu-average value error of a fixed policy with residuals averaged under that policy's discounted occupancy dνπd^\pi_\nu. Part (b) bounds the return lost by the consistent-action policy. Part (c) covers any stationary deterministic policy, including the gateway controller below, by adding the action gap g(s)=∑jq(j∣s)[V^⋆(j)−Q^⋆(j,π(s))].g(s)=\sum_jq(j\mid s)\bigl[\hat V^\star(j)-\hat Q^\star(j,\pi(s))\bigr]. Residuals averaged under μ\mu qualify only after multiplication by max⁡sdνπ(s)/μ(s)\max_sd^\pi_\nu(s)/\mu(s). Table 20 reports the residuals under the executed controller's occupancy, for example 0.0022 and 0.0054 in FourRooms and 0.0030 and 0.0071 in Corridor-9. The action-gap term of part (c) needs the executed-action gap, which the audit of Table 20 does not compute. Table 25 reports a related diagnostic at γ=0.99\gamma=0.99. The margin between the best and second-best abstract actions averages 0.024–0.084 across the navigation domains. States whose active cores share no maximizing action make up at most 2.7% of the occupancy there, against 8.4% on Chain-100.

Definition 1. You are right that the inclusive version is weaker. Since V∖Ai=Bi∖AiV\setminus A_i=B_i\setminus A_i, the condition that three small sides do not cover VV is equivalent to a common vertex of the strict big sides. In a star with center oo and leaves a,b,ca,b,c, the separations (V∖{i},{o,i})(V\setminus\{i\},\{o,i\}) have inclusive big sides that all contain oo, yet their small sides cover VV. The implementation checks the corrected condition on the candidate family. An orientation is pruned as soon as three of its small sides cover the vertex set. Each maximal orientation must also have small sides with empty intersection, which is the non-triviality condition. Both checks concern the candidate family, as Section 3 states.

AuthorsOpenReview ↗

Response to Reviewer LTo4 – Part 2

Execution within rooms. You are right that a rule giving one action per membership vector would give every interior cell of a room the same action. The reported returns do not use that rule. In Tables 1, 2, 4, 5, 7–9, 11, 12, and 15, the abstract planner selects the next target core on its greedy route to the goal. The gateways are the doorway, overlap, or interface states that connect the current core to that target. The controller computes shortest-path distances in the empirical support graph, moves toward the nearest reachable gateway, and replans after every transition. Once the goal core is active, it routes directly to the goal, and ties use a fixed action ordering. Interior states with the same membership can therefore take different actions. Bisimulation, DeepMDP, spectral clustering, METIS, Louvain, TOMA, Detected-B, and tangle cores share the controller, the start distribution, the tie rule, and the replanning schedule. Only the abstraction and its plan differ. Tabular domains start uniformly over reachable nonterminal, non-goal states. The controller is a stationary deterministic policy, so Proposition 9(c) applies to it. Two experiments use the lifted primitive policy instead, and Appendix C.1 now says so. The Chain MDP runs (Tables 6 and 19) take the smallest-index maximizer of ∑jq(j∣s)Q^⋆(j,a)\sum_jq(j\mid s)\hat Q^\star(j,a). The MiniGrid results in Table 17 use the same membership-weighted policy without gateway assistance, and they record every state where the active cores share no maximizing action.

We hope these corrections resolve the issues you raised, and we would be glad to answer further questions.

Thank you for the clarifications. Several of my concerns have been addressed. The correction to Definition 1 using the strict big sides resolves the equivalence issue. The shared gateway controller explains how different states within the same room can take different actions in the main experiments. The authors have also acknowledged that the average residuals in Tables 10 and 13 cannot be directly used in Theorem 3 and revised the text accordingly.

I still have two questions.

First, Table 17 uses the membership-weighted primitive policy without gateway assistance. It reports four cores corresponding to the four rooms and a return of 96.8%. If states inside the same room have identical membership vectors, this policy should select the same action at those states. How does it handle navigation within a room? Please clarify whether the membership vectors actually differ across these states. A few examples showing the memberships and selected actions at different positions and orientations, or an execution trajectory, would help.

Second, Proposition 9(c) requires the executed-action gap, which has not been reported. The margin between the best and second-best abstract actions in Table 25 is a different quantity. Could you report the required gap and the resulting full error bound? If the experiments are intended only as residual diagnostics, please make that limitation clear.

The revisions have addressed several of my original concerns. I would consider raising my score if these remaining points are resolved.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We thank the reviewers. Reviewer LTo4 identified three issues that bear on correctness, and the revision resolves each of them. Reviewer GFz5 asked for cost beyond Corridor-9, and Reviewer A1kv asked for baselines, details, and visualizations. The main changes are as follows.

  • Definition 1 and the implemented predicate now agree. The "equivalently" in Definition 1 now uses the strict big sides Bi∖AiB_i\setminus A_i, and a star graph shows why the inclusive version is weaker (Section 2). The implementation checks the corrected condition. An orientation is pruned as soon as three of its small sides cover the vertex set, and each maximal orientation must have small sides with empty intersection (Section 3).
  • The returns come from a shared gateway controller, now specified in the paper. In Tables 1, 2, 4, 5, 7–9, 11, 12, and 15, the abstract planner picks the next core on its route to the goal. A local controller then moves by shortest path toward the nearest interface of that core and replans after every transition. Bisimulation, DeepMDP, spectral clustering, METIS, Louvain, TOMA, Detected-B, and tangle cores share the controller, the start distribution, the tie rule, and the replanning schedule (Section 5 and Appendix C.1). The returns therefore measure abstraction quality inside a hierarchical navigation system.
  • Table 10's residuals are averages, and the theory now says what averages support. Table 10 averages the residuals under the occupancy μ\mu of the construction data, so its BB is a plug-in diagnostic. Remark 1 shows that uniform residuals are large under sparse rewards. The new Proposition 9 bounds value and return error with residuals averaged under the evaluated policy's own occupancy. Its part (c) covers any stationary deterministic controller, including the gateway controller, at the cost of an action-gap term (Section 4). Table 20 reports the residuals under the executed controller's occupancy.
  • Cost on larger layouts. On sixteen-room layouts with matched execution, tangle cores reach 98.4% return, against 98.6% for Detected-B and 100% for ground value iteration. They take 7.6 s to build, against 4.2 s for Detected-B, and they plan each query in 0.02 s, against 0.03 s and 0.12 s. Tangle cores therefore have the lower total cost after 76 queries against ground value iteration and after 340 against Detected-B (Table 21). On MultiRoom-N6 and DoorKey-16×16, tangle cores use 6 and 5 abstract states, against 57 and 46 for bisimulation, at a return lower by 0.4 and 0.6 points (Table 23).

Revisions at a glance

ChangeRequested byWhere in the revision
Corrected "equivalently" in Definition 1, with a counterexampleLTo4Section 2
The predicate that the implementation checksLTo4Section 3
Execution protocol: shared gateway controller and start distributionsLTo4Section 5; Appendix C.1
Tables 10 and 13 labeled as construction-occupancy averagesLTo4Section 5; Tables 10 and 13
Floor on uniform residuals under sparse rewardsLTo4Remark 1
Occupancy-weighted value and return bounds, including any stationary controllerLTo4Proposition 9
Residuals under the executed controller's occupancyLTo4Table 20 (Appendix C.9)
Sixteen-room comparison of construction and planning costGFz5Table 21 (Appendix C.10)
MiniGrid latent model and graph constructionA1kvTable 22 (Appendix C.11)
MultiRoom-N6 and DoorKey-16×16GFz5Table 23 (Appendix C.12)
Construction time by environment and by componentGFz5Table 3; Table 24 (Appendix C.13)
Betweenness, bridge centrality, and D4RL in related workA1kvAppendix A
Shortest-path and current-flow betweenness controlsA1kvTable 26 (Appendix C.15)
Scope statement: tabular, procedural, and latent MiniGrid domains, not Atari, robotics, or D4RLA1kvSection 6
Action margins and action-conflict occupancy of the abstract modelLTo4Table 25 (Appendix C.14)
Plain-English rewrite of the main textallSections 1–6

What the evidence supports

The evidence supports tangle cores as a prior for support discovery in navigation and graph problems with coherent regions and narrow interfaces. Inside the shared hierarchical controller, they compress more than reward-aware and graph-partitioning baselines at matched return (Tables 1, 4, 5, 7–9, and 23). Topology-poor controls show where they do not help (Tables 6 and 12). The evaluation does not cover Atari, continuous-control robotics, or D4RL. The value theorem is conditional: it needs uniform residuals and action consistency, and Proposition 9 states which averaged residuals give valid bounds. The sixteen-room comparison shows a tradeoff between return and amortized cost, not a single-query advantage.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.