StructRL Extracts Transferable Policies from Replay Graphs

Summary:StructRL turns reinforcement-learning experience into an explicit replay graph. Once the graph contains a path to the goal, dynamic programming extracts actions from the observed state space and transfers them as DQN action preferences or SAC directional labels. The approach substantially improves sparse-reward MiniGrid performance and enables a distilled DoorKey 6×6 controller to reach the goal from 91% of reachable states. The paper also identifies three scaling bottlenecks: incomplete graph

---

Core Idea: Turning Replay Experience into a Queryable State Graph

StructRL does not train an additional dynamics model. Instead, it organizes the states, actions, and rewards encountered by an agent into an explicit replay graph. Nodes represent distinguishable states, while edges represent observed transitions. Once the graph contains a path to the goal, dynamic programming searches the observed subgraph for a shortest route and extracts its action sequence.

The result is not a globally defined policy. It is a locally supported graph policy: an action is considered reliable only when the transitions required to justify it have already been observed. The central assumption is that replay trajectories encode not only training samples but also an implicit map of the environment's reachable state structure.

Integration with Model-Free Reinforcement Learning

StructRL converts the graph policy into two forms of supervision:

• DQN: Actions along an optimal graph path provide preferences that guide the Q-model's targets or value distribution.
• SAC: Directions along the path become continuous-action target labels for policy or behavior learning.

This preserves the online sampling behavior of DQN and SAC while allowing replay data to perform structural induction. Compared with simply enlarging the neural network, the additional cost comes from graph storage, node matching, and shortest-path computation. Compared with learning an explicit dynamics model, it avoids predicting unobserved transitions.

Experimental Results

Across three sparse-reward MiniGrid tasks, StructRL raised DQN's final success rate from 0.10 to 0.90 on DoorKey, from 0.10 to 0.80 on KeyCorridor, and from 0 to 0.50 on ObstructedMaze. Plain DQN failed to catch up even when given three times the training budget.

On the continuous-control PointMaze task, graph-derived directional labels increased final success from 0.17 to 1.0. This result, however, is based on only seven matched runs that reached the goal, so the sample size is small.

The most informative result comes from policy distillation. After distilling the graph policy into a fresh Q-model, the DoorKey 6×6 controller reached the goal from 91% of reachable states, compared with 38% for plain DQN. The graph therefore appears to provide a behavioral prior that can be compressed into broader state coverage rather than merely a hint for the current trajectory.

Engineering Trade-offs: Structural Priors Are Not Free

The paper identifies three direct bottlenecks:

1. Incomplete graph support: If a transition required for the goal path has never been observed, dynamic programming cannot cross the missing edge. Insufficient exploration can therefore restrict the policy to a small local region.
2. Structural aliasing: In visual or high-dimensional inputs, different physical states may map to identical or nearly identical nodes, causing incorrect merges or edges. Reliable state identification and deduplication directly determine graph quality.
3. Loss of graph information in high-dimensional inputs: Even when scalar states can be represented accurately, visually similar observations may correspond to different topological positions, amplifying structural aliasing.

Graph construction also introduces storage and update costs. State keys must be retained, and the edge table grows with the number of transitions. If approximate nearest-neighbor matching is used for nodes, it adds computation and a risk of false connections. A production implementation should report node counts, edge counts, duplicate-state rates, reachable-state coverage, and graph-construction latency rather than final success rate alone.

Interpreting the Evaluation

The results cover discrete sparse-reward navigation and continuous PointMaze, but they do not yet establish universal gains in image-based control, robotic manipulation, or large-scale environments. In particular, the PointMaze result of 1.0 success is based on only seven matched runs that reached the goal; it should not be interpreted as a high-confidence population-level success rate.

StructRL also changes the learning signal relative to plain DQN. Comparisons should therefore keep network size, optimization budget, environment instances, and random seeds matched. DoorKey 6×6's 91% state coverage is more engineering-relevant than endpoint success alone, although larger grids may stress graph growth.

Practical Deployment Guidance

StructRL is best suited to environments with sparse rewards, explicit topology, and stable state discretization, such as grid navigation, path planning, and discrete graph environments. Before integration, developers should verify that states can be mapped reliably to nodes, that the graph covers enough goal-directed transitions, and that erroneous node merging does not corrupt the policy.

A practical workflow is to build the graph from raw discrete states, generate pseudo-labels through dynamic programming, and then train or fine-tune a Q-model. Perception encoders, candidate-node retrieval, and approximate graph matching should be explored only after the discrete-state baseline is verified. Every extension should be compared with an equal-budget structure-free baseline and report endpoint success, reachable-state coverage, graph overhead, and the distribution of failures.

---

Source: ArXiv Machine Learning (cs.LG) (2026-11-13)

— END —

Tags: #StructRL Follow #Reinforcement Learning Follow #Replay Graphs Follow #Sparse Rewards Follow #DQN Follow