# Sub-Goal Trees -- a Framework for Goal-Based Reinforcement Learning

arXiv: https://arxiv.org/abs/2002.12361 · HTML: https://mlsanity.com/paper/2002.12361/

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2020.

## Built on by (most cited first, 29 of 29)

- [RT-1: Robotics Transformer for Real-World Control at Scale](https://mlsanity.com/paper/2212.06817/) (2022)
- [Goal-Conditioned Reinforcement Learning with Imagined Subgoals](https://mlsanity.com/paper/2107.00541/) (2021)
- [Monte Carlo Tree Diffusion for System 2 Planning](https://mlsanity.com/paper/2502.07202/) (2025)
- [Option-aware Temporally Abstracted Value for Offline Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2505.12737/) (2025)
- [Hierarchical Decision Transformer](https://mlsanity.com/paper/2209.10447/) (2022)
- [Hierarchical Imitation Learning with Vector Quantized Models](https://mlsanity.com/paper/2301.12962/) (2023)
- [Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search](https://mlsanity.com/paper/2206.00702/) (2022)
- [Transitive RL: Value Learning via Divide and Conquer](https://mlsanity.com/paper/2510.22512/) (2025)
- [Save the Good Prefix: Precise Error Penalization via Process-Supervised RL to Enhance LLM Reasoning](https://mlsanity.com/paper/2601.18984/) (2026)
- [Hybrid Search for Efficient Planning with Completeness Guarantees](https://mlsanity.com/paper/2310.12819/) (2023)
- [Advancing Autonomous VLM Agents via Variational Subgoal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2502.07949/) (2025)
- [Cascaded Diffusion Models for Neural Motion Planning](https://mlsanity.com/paper/2505.15157/) (2025)
- [Goal-conditioned Offline Reinforcement Learning through State Space Partitioning](https://mlsanity.com/paper/2303.09367/) (2023)
- [Abstract Demonstrations and Adaptive Exploration for Efficient and Stable Multi-step Sparse Reward Reinforcement Learning](https://mlsanity.com/paper/2207.09243/) (2022)
- [Goal-Conditioned Supervised Learning with Sub-Goal Prediction](https://mlsanity.com/paper/2305.10171/) (2023)
- [Generation of Geodesics with Actor-Critic Reinforcement Learning to Predict Midpoints](https://mlsanity.com/paper/2407.01991/) (2024)
- [Implicit Contact Diffuser: Sequential Contact Reasoning with Latent Point Cloud Diffusion](https://mlsanity.com/paper/2410.16571/) (2024)
- [Action-Sufficient Goal Representations](https://mlsanity.com/paper/2601.22496/) (2026)
- [Mollified Value Learning](https://mlsanity.com/paper/2602.23280/) (2026)
- [Adaptive Coarse-to-Fine Subgoal Refinement for Long-Horizon Offline Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2605.28127/) (2026)
- [Recursive Value Learning for Long-Horizon Offline Goal-Conditioned RL](https://mlsanity.com/paper/2609.02237/) (2026)
- [A Probabilistic Generative Model of Free Categories](https://mlsanity.com/paper/2205.04545/) (2022)
- [Multi-Task Option Learning and Discovery for Stochastic Path Planning](https://mlsanity.com/paper/2210.00068/) (2022)
- [Learning Top-k Subtask Planning Tree based on Discriminative Representation Pre-training for Decision Making](https://mlsanity.com/paper/2312.11027/) (2023)
- [Bidirectional-Reachable Hierarchical Reinforcement Learning with Mutually Responsive Policies](https://mlsanity.com/paper/2406.18053/) (2024)
- [DHP: Discrete Hierarchical Planning for Hierarchical Reinforcement Learning Agents](https://mlsanity.com/paper/2502.01956/) (2025)
- [GTRL: Grounding Divide-and-Conquer Value Learning with Temporal Differences](https://mlsanity.com/paper/2609.33259/) (2026)
- [Direction-Conditioned Policies for Online Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2610.05087/) (2026)
- [Acceptable Misalignment](https://mlsanity.com/paper/2610.16881/) (2026)

## Abstract (arXiv)

Many AI problems, in robotics and other domains, are goal-based, essentially seeking trajectories leading to various goal states. Reinforcement learning (RL), building on Bellman's optimality equation, naturally optimizes for a single goal, yet can be made multi-goal by augmenting the state with the goal. Instead, we propose a new RL framework, derived from a dynamic programming equation for the all pairs shortest path (APSP) problem, which naturally solves multi-goal queries. We show that this approach has computational benefits for both standard and approximate dynamic programming. Interestingly, our formulation prescribes a novel protocol for computing a trajectory: instead of predicting the next state given its predecessor, as in standard RL, a goal-conditioned trajectory is constructed by first predicting an intermediate state between start and goal, partitioning the trajectory into two. Then, recursively, predicting intermediate points on each sub-segment, until a complete trajectory is obtained. We call this trajectory structure a sub-goal tree. Building on it, we additionally extend the policy gradient methodology to recursively predict sub-goals, resulting in novel goal-based algorithms. Finally, we apply our method to neural motion planning, where we demonstrate significant improvements compared to standard RL on navigating a 7-DoF robot arm between obstacles.