Research map / Reinforcement learning / Visual and representation RL
Breadth-First Exploration on Adaptive Grid for Reinforcement Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes BEAG, a grid-based graph planner for goal-conditioned RL that tracks both achieved and unattained subgoals on an adaptively refined grid to enable breadth-first subgoal exploration.
Problem
Graph-based planners for goal-conditioned RL build graphs only from achieved subgoals, ignoring unattainable ones, so agents waste many attempts on impossible subgoals in sparse, long-horizon tasks.
Approach
Manage all achieved and unattained subgoals on a grid graph that adaptively discretizes the goal space; edges to subgoals that repeatedly fail are removed, and grid refinement is applied locally around unattainable nodes, yielding breadth-first exploration on a coarse grid before fine refinement.
Key results
- BEAG achieves high success rates across AntMaze and Reacher3D environments under the fixed initial state and goal setting, where baselines (HIRO, HIGL, DHRL, PIG) generally fail in most environments.
- BEAG spends virtually zero attempts on unattainable subgoals in U-maze, whereas DHRL repeatedly attempts subgoals over the wall.
- BEAG succeeds in bottleneck-maze through adaptive grid refinement, and its performance is consistent across fixed and random goal settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use BEAG instead of prior graph-based RL baselines | goal-conditioned RL · fixed-goal AntMaze and Reacher3D-wall | success rate | Helped |
| use BEAG instead of prior graph-based RL baselines | goal-conditioned RL · random-goal U-maze, S-maze, Reacher3D-wall, and bottleneck-maze | success rate | Helped |
| set the initial grid interval to 1 rather than 2 (ablation) | BEAG · U-maze | success rate | Hurt |
| set the initial grid interval to 8 rather than 2 or 4 (ablation) | BEAG · U-maze | success rate | Mixed |
| set the failure threshold τt to 100 steps (ablation) | BEAG · U-maze | success rate | Hurt |
| set the failure threshold τt to 400 steps (ablation) | BEAG · U-maze | success rate | Hurt |
| set the failure count threshold τn to 1 (ablation) | BEAG · U-maze | success rate | Hurt |
| replace the grid graph with a random graph of 50 nodes (ablation) | BEAG · U-maze | success rate | Hurt |
| replace the grid graph with a random graph of 100 nodes (ablation) | BEAG · U-maze | success rate | Mixed |
| replace the grid graph with a random graph, using 150 nodes (ablation) | BEAG · U-maze | success rate | No clear effect |
Surprising findings
- Previous graph-based planners such as DHRL succeed under random goal sampling largely because sampled goals reveal feasible regions, and they fail under the fixed-goal setting.
Limitations
- Number of grid nodes grows exponentially with goal-space dimension K, raising computational cost.
- Failure thresholds (τt, τn) may misclassify attainable subgoals as unattainable in stochastic environments.
- Evaluated only on MuJoCo AntMaze and Reacher3D environments with low-dimensional goal spaces.
Experimental setup
Benchmarks: AntMaze U-maze-easy U-maze-moderate U-maze bottleneck-maze S-maze pi-maze complex-maze Reacher3D-wall
Metrics: success rate
Baselines: HIRO HIGL DHRL PIG
Builds on: HIRO SoRB DHRL HIGL PIG
Closest papers by meaning
- Adaptive Quasimetric Mapping : Principled Topological Abstraction for Robust Offline Goal-Conditioned Navigation (ICML 2026 · similarity 0.89)
- Exploring the Edges of Latent State Clusters for Goal-Conditioned Reinforcement Learning (NeurIPS 2024 · similarity 0.86)
- Scalable Online Exploration via Coverability (ICML 2024 · similarity 0.86)
- Graph-Assisted Stitching for Offline Hierarchical Reinforcement Learning (ICML 2025 · similarity 0.86)
- Decoupling Exploration and Policy Optimization: Uncertainty Guided Tree Search for Hard Exploration (NeurIPS 2026 · similarity 0.86)
- Diffusion Subgoal Planning for Long-Horizon Offline Goal-Conditioned Reinforcement Learning (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.