StructRL: Model-Free Reinforcement Learning with Replay Graphs
Organizations: Hamburg University of Applied Sciences (HAW Hamburg)
Abstract
StructRL turns the experience collected during reinforcement learning into an explicit replay graph. Once the graph contains a path to the task goal, dynamic programming selects actions on the observed part of the state space; these actions form a graph policy that is defined only where the required transitions have been observed. StructRL transfers these actions to model-free learners: as action preferences for a DQN Q-model and as target directions along shortest observed paths for a SAC actor. For DQN on three sparse-reward MiniGrid tasks, final success rises from 0.10 to 0.90 (DoorKey), 0.10 to 0.80 (KeyCorridor) and 0 to 0.50 (ObstructedMaze); plain DQN does not catch up with three times the budget. For SAC on continuous PointMaze, graph-derived direction labels raise final success from 0.17 to 1.0 on seven matched runs that reached the goal. Distilling the graph policy into a fresh Q-model gives a DoorKey 6x6 controller that reaches the goal from 91% of reachable states, against 38% for plain DQN. Scaling experiments identify three bottlenecks: incomplete graph support, structural aliasing, and loss of graph information in high-dimensional inputs.
Figures & tables
| Method | Graph built from | Use of the graph |
|---|---|---|
| SoRB [ 13 ] | replay observations, learned distances | waypoint planning for a goal-conditioned policy |
| TER [ 10 ] | replay transitions | order of replay backups |
| ERLAM [ 16 ] | episodic-memory states, observed transitions | value propagation; early guidance of a parametric model |
| Qgraph [ 17 ] | replay transitions, subgraph as simplified MDP | lower bounds that replace the TD target (QG-DDPG) |
| StructRL | observed edges between structural states | action rankings (DQN) and directions (SAC) as auxiliary losses; Bellman targets unchanged |
| DQN (discrete actions) | SAC (continuous actions) | |
|---|---|---|
| Graph value | reward-based recursion, Eq. ( 6 ) | unit-cost shortest observed path |
| Label | set of graph-optimal actions at | direction to the next cell on the path, goal position in the last cell |
| Loss on the learner | large-margin ranking loss next to the TD loss | squared direction loss on the actor mean |
| Name in text | Added information | Internal code |
|---|---|---|
| DQN baseline | none | plain |
| StructRL | replay graph and graph guidance | struct |
| StructRL+Prior | StructRL plus goal-distance prior | struct_ka |
| StructRL+Transfer | StructRL+Prior plus graph-action transfer | struct_mgkahg |
| SAC baseline | none | |
| StructRL-SAC | frontier support acquisition plus graph direction labels |
| Environment | Actions | Task | Purpose |
|---|---|---|---|
| DoorKey 6x6 | discrete (7) | pick up the key, open the door, reach the goal | sparse sequential discovery |
| KeyCorridor S3R2 | discrete (7) | find the key, open a locked door, pick up the object behind it | longer sparse sequence |
| ObstructedMaze 1Dl | discrete (7) | open a locked door with the visible key and pick up the object behind it | hard sparse discovery |
| UnlockPickup, KeyCorridor S3R3 | discrete (7) | unlock a door and pick up an object; larger corridor with three rooms | held-out tasks |
| PointMaze (M, Large) | continuous, 2-D force | move a ball through a maze to a goal cell | continuous sparse navigation |
| SearchGrid | discrete (5) | visit ordered subgoal cells in an grid with walls | controlled discovery family (planner only, no learner) |
| Task / evaluation | Metric | Baseline | StructRL result |
|---|---|---|---|
| DoorKey | final success | 0.10 | 0.90 |
| DoorKey | AUC | 0.01 | 0.41 |
| KeyCorridor S3R2 | final success | 0.10 | 0.80 |
| KeyCorridor S3R2 | AUC | 0.04 | 0.44 |
| ObstructedMaze | final success | 0.00 | 0.50 |
| ObstructedMaze | AUC | 0.00 | 0.23 |
| Task | Arm | Budget ( / ) | Seeds | Final | Final | Tail | Tail |
|---|---|---|---|---|---|---|---|
| DoorKey 6x6 | DQN baseline | 60k / 180k | 10 | 0.10 | 0.30 | 0.04 | 0.28 |
| StructRL | 60k / 180k | 10 | 0.90 | 1.00 | 0.86 | 0.92 | |
| paired tail difference StructRL baseline: | |||||||
| KeyCorridor S3R2 | DQN baseline | 150k / 450k | 10 | 0.10 | 0.00 | 0.10 | 0.00 |
| StructRL | 150k / 450k | 10 | 0.80 | 0.80 | 0.74 | 0.92 | |
| paired tail difference StructRL baseline: | |||||||
| Axis | Condition | Result |
|---|---|---|
| Task size | DoorKey 8x8 | Prior+margin vs plain: AUC ; vs StructRL: ; 10 seeds. |
| Task size | DoorKey 16x16 | 3 seeds: Q-model AUC 0 for all configurations; graph-only success 0.67; no claim beyond 8x8. |
| Structural | nodir , pos | AUC 0.00; graph-only 0.00; optimal-path conflicting classes 39% and 50%. |
| Nuisance input | 100 / 1000 dims | At 100: AUC vs no nuisance; at 1000: AUC 0.008 while graph-only remains 1.0. |
| Planning | up to 25k nodes | Total planning time per run at most 117 s; not the dominant tested bottleneck. |
Appendix figures & tables13 assets
Supplementary material from the paper’s appendix.
Appendix
| Task | Arm | Anchor | AUC | Final | AUC (StructRL arm) |
|---|---|---|---|---|---|
| DoorKey 6x6 | DQN baseline | 6/10 | 0.01 | 0.10 | +0.40 [+0.29,+0.50] |
| count-only control | 9/10 | 0.04 | 0.10 | +0.36 [+0.27,+0.46] | |
| random-direction control | 8/10 | 0.05 | 0.20 | +0.36 [+0.27,+0.45] | |
| discovery-only StructRL | 10/10 | 0.00 | 0.00 | +0.40 [+0.30,+0.50] | |
| StructRL | 10/10 | 0.41 | 0.90 | – | |
| KeyCorridor S3R2 | DQN baseline | 4/10 | 0.04 | 0.10 | +0.40 [+0.25,+0.54] |
| Task | Prior StructRL | Margin beyond prior | Prior+Margin StructRL |
|---|---|---|---|
| UnlockPickup | |||
| KeyCorridor S3R3 |
| Contrast | Mean difference [95% CI] | |
|---|---|---|
| Transfer: post-anchor AUC | 7 | |
| Prior: | k k | 10 |
| Direction: | k k | 10 |
| Overall post-anchor: | 6 | |
| Against plain SAC: eval AUC | 10 |
| Configuration | Q-model input | Stable | Final | AUC median [min,max] | Relapses | |
| DoorKey 6x6, 1000 nuisance dimensions, 60k steps (confirmation) | ||||||
| Full StructRL | joint Q-model | 10 | 0/10 | 0/10 | 0.00 [0.00,0.00] | 0 |
| Full StructRL | two-branch Q-model | 10 | 10/10 | 9/10 | 0.80 [0.44,0.96] | 18 |
| Full StructRL | -only Q-model | 10 | 10/10 | 9/10 | 0.84 [0.52,0.96] | 13 |
| DoorKey 6x6, no nuisance (F2) | ||||||
| Full StructRL | joint Q-model | 5 | 5/5 | 5/5 | 0.64 [0.52,0.80] | 0 |
| Configuration | Q-model input | Stable | Final | AUC median [min,max] | Relapses | |
| DoorKey 6x6, 1000 nuisance dimensions | ||||||
| DQN baseline | two-branch Q-model | 5 | 3/5 | 4/5 | 0.24 [0.00,0.44] | 2 |
| StructRL | two-branch Q-model | 5 | 5/5 | 3/5 | 0.72 [0.56,0.92] | 8 |
| Full StructRL | two-branch Q-model | 5 | 5/5 | 4/5 | 0.76 [0.48,0.80] | 20 |
| DoorKey 8x8, 1000 nuisance dimensions | ||||||
| DQN baseline | two-branch Q-model | 10 | 3/10 | 1/10 | 0.00 [0.00,0.52] | 6 |
| Arm | DoorKey | UnlockPickup | DoorKey |
|---|---|---|---|
| plain | 0.06 (7/10) | 0.00 (2/5) | 0.00 (3/5) |
| plain_tero | 0.13 (8/10) | 0.00 (0/5) | 0.00 (3/5) |
| struct | 0.46 (10/10) | 0.06 (5/5) | 0.06 (5/5) |
| struct_tero | 0.49 (10/10) | 0.17 (5/5) | 0.10 (5/5) |
| struct_mgkahg | 0.72 (10/10) | 0.30 (5/5) | 0.35 (5/5) |
| Contrast |
| StructRL | StructRL + goal prior + graph transfer | |||
|---|---|---|---|---|
| Controller | Steps | Steps | ||
| Online Q-model | 0.11 0.05 | – | 0.45 0.10 | – |
| Hard distilled, | 0.61 0.08 | 11.3 | 0.59 0.09 | 10.9 |
| Hard distilled, | 0.84 0.07 | 13.3 | 0.84 0.08 | 12.8 |
| Hard distilled, | 0.90 0.07 | 18.7 | 0.91 0.06 | 18.2 |
| Hard distilled, | 0.81 0.07 | 11.7 | 0.81 0.09 | 11.4 |
| Difference | StructRL | StructRL + goal prior + graph transfer |
|---|---|---|
| Hard distilled ( ) online Q-model | (10/10) | (9/10) |
| (hard distilled) | (10/10) | (10/10) |
| (hard distilled) | (10/10) | (10/10) |
| global | (0/10) | (1/10) |
| Global graph + random fallback | (9/10) | (8/10) |
| graph + random fallback | (7/10) | (8/10) |
| Controller | |
|---|---|
| Plain DQN (online) | 0.00 0.00 |
| Online Q-model | 0.22 0.10 |
| Hard distilled, | 0.41 0.06 |
| Hard distilled, | 0.75 0.04 |
| Hard distilled, | 0.86 0.04 |
| Hard distilled, | 0.75 0.04 |
| Controller | StructRL + goal prior + graph transfer | StructRL | DQN baseline |
|---|---|---|---|
| Graph + random fallback | 0.84 0.05 | 0.83 0.02 | – |
| Online Q-model, | 0.45 0.10 | 0.11 0.02 | 0.04 0.05 |
| Online Q-model, | 0.72 0.10 | 0.41 0.09 | 0.23 0.19 |
| Online Q-model, | 0.84 0.09 | 0.60 0.11 | 0.38 0.27 |
| Online Q-model, | 0.69 0.10 | 0.28 0.07 | – |
| Distilled, random labels, | 0.02 0.01 | 0.02 0.01 | – |
| Block | Seeds | Decision rule (summary) |
|---|---|---|
| Nuisance and transfer study | ||
| Two-branch confirmation | 1710–1719 | Two-branch stable success in seeds, joint Q-model , paired AUC interval excludes 0. |
| Task size, nuisance, DoorKey | 1720–1724; 1730–1734 | Descriptive; nuisance dimensions 0, 100, 5000. |
| DP head; gradient cosine and detach | 1740–1744; 1760–1764 | Adopt only if clearly better than the plain two-branch Q-model; gradient conflict only if the joint Q-model shows more negative cosines than the two-branch Q-model and its permuted control. |
| Graph necessity, / | 1780–1784; 1790–1799 | Graph episodes necessary if plain is stable in at most 3 of 10 seeds and struct in at least 8 of 10. |
| Automatic selection, versions 1–3 | 1800–1804; 1810–1814; 1820–1824 | stable and median AUC within 0.1 of the hand-built . |
| Parameter | Value |
|---|---|
| DQN base learner: shared | |
| Observation | fully observed grid, scaled by , flattened |
| Network | 2 hidden layers of 256 units, dueling heads, ReLU |
| Update rule | Double DQN, -step return with |
| Optimizer | Adam, learning rate |
| Minibatch size | 64 |
| Parameter | Value |
|---|---|
| SAC base learner | |
| Observation | position, velocity, goal position (6-dim.) |
| Networks | actor and two critics, 2 hidden layers of 256 units, ReLU |
| Optimizer | Adam, learning rate (actor, critics, entropy coefficient) |
| Minibatch size | 256 |
| Replay memory size | (all transitions) |