# Search on the Replay Buffer: Bridging Planning and Reinforcement Learning

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

## Key facts

- Cited by 194 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2019.

## Built on by (most cited first, 30 of 194)

- [Do As I Can, Not As I Say: Grounding Language in Robotic Affordances](https://mlsanity.com/paper/2204.01691/) (2022)
- [Inner Monologue: Embodied Reasoning through Planning with Language Models](https://mlsanity.com/paper/2207.05608/) (2022)
- [ProgPrompt: Generating Situated Robot Task Plans using Large Language Models](https://mlsanity.com/paper/2209.11302/) (2022)
- [Contrastive Learning as Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2206.07568/) (2022)
- [OGBench: Benchmarking Offline Goal-Conditioned RL](https://mlsanity.com/paper/2410.20092/) (2024)
- [RvS: What is Essential for Offline RL via Supervised Learning?](https://mlsanity.com/paper/2112.10751/) (2021)
- [Maximum Entropy RL (Provably) Solves Some Robust RL Problems](https://mlsanity.com/paper/2103.06257/) (2021)
- [Look Before You Leap: Unveiling the Power of GPT-4V in Robotic Vision-Language Planning](https://mlsanity.com/paper/2311.17842/) (2023)
- [Goal-Conditioned Reinforcement Learning: Problems and Solutions](https://mlsanity.com/paper/2201.08299/) (2022)
- [HIQL: Offline Goal-Conditioned RL with Latent States as Actions](https://mlsanity.com/paper/2307.11949/) (2023)
- [Goal-Conditioned Reinforcement Learning with Imagined Subgoals](https://mlsanity.com/paper/2107.00541/) (2021)
- [Large Language Models for Robotics: A Survey](https://mlsanity.com/paper/2311.07226/) (2023)
- [Discovering and Achieving Goals via World Models](https://mlsanity.com/paper/2110.09514/) (2021)
- [Actionable Models: Unsupervised Offline Reinforcement Learning of Robotic Skills](https://mlsanity.com/paper/2104.07749/) (2021)
- [Learning Language-Conditioned Robot Behavior from Offline Data and Crowd-Sourced Annotation](https://mlsanity.com/paper/2109.01115/) (2021)
- [Reward Shaping to Mitigate Reward Hacking in RLHF](https://mlsanity.com/paper/2502.18770/) (2025)
- [METRA: Scalable Unsupervised RL with Metric-Aware Abstraction](https://mlsanity.com/paper/2310.08887/) (2023)
- [COG: Connecting New Skills to Past Experience with Offline Reinforcement Learning](https://mlsanity.com/paper/2010.14500/) (2020)
- [Augmenting Reinforcement Learning with Behavior Primitives for Diverse Manipulation Tasks](https://mlsanity.com/paper/2110.03655/) (2021)
- [A Survey on Interpretable Reinforcement Learning](https://mlsanity.com/paper/2112.13112/) (2021)
- [Mobility VLA: Multimodal Instruction Navigation with Long-Context VLMs and Topological Graphs](https://mlsanity.com/paper/2407.07775/) (2024)
- [Compositional Reinforcement Learning from Logical Specifications](https://mlsanity.com/paper/2106.13906/) (2021)
- [Grounded Decoding: Guiding Text Generation with Grounded Models for Embodied Agents](https://mlsanity.com/paper/2303.00855/) (2023)
- [ReMEmbR: Building and Reasoning Over Long-Horizon Spatio-Temporal Memory for Robot Navigation](https://mlsanity.com/paper/2409.13682/) (2024)
- [Memory-Augmented Reinforcement Learning for Image-Goal Navigation](https://mlsanity.com/paper/2101.05181/) (2021)
- [A Survey on Model-based Reinforcement Learning](https://mlsanity.com/paper/2206.09328/) (2022)
- [No RL, No Simulation: Learning to Navigate without Navigating](https://mlsanity.com/paper/2110.09470/) (2021)
- [Horizon Reduction Makes RL Scalable](https://mlsanity.com/paper/2506.04168/) (2025)
- [Retrieval-Augmented Reinforcement Learning](https://mlsanity.com/paper/2202.08417/) (2022)
- [LoTa-Bench: Benchmarking Language-oriented Task Planners for Embodied Agents](https://mlsanity.com/paper/2402.08178/) (2024)

## Abstract (arXiv)

The history of learning for control has been an exciting back and forth between two broad classes of algorithms: planning and reinforcement learning. Planning algorithms effectively reason over long horizons, but assume access to a local policy and distance metric over collision-free paths. Reinforcement learning excels at learning policies and the relative values of states, but fails to plan over long horizons. Despite the successes of each method in various domains, tasks that require reasoning over long horizons with limited feedback and high-dimensional observations remain exceedingly challenging for both planning and reinforcement learning algorithms. Frustratingly, these sorts of tasks are potentially the most useful, as they are simple to design (a human only need to provide an example goal state) and avoid reward shaping, which can bias the agent towards finding a sub-optimal solution. We introduce a general control algorithm that combines the strengths of planning and reinforcement learning to effectively solve these tasks. Our aim is to decompose the task of reaching a distant goal state into a sequence of easier tasks, each of which corresponds to reaching a subgoal. Planning algorithms can automatically find these waypoints, but only if provided with suitable abstractions of the environment -- namely, a graph consisting of nodes and edges. Our main insight is that this graph can be constructed via reinforcement learning, where a goal-conditioned value function provides edge weights, and nodes are taken to be previously seen observations in a replay buffer. Using graph search over our replay buffer, we can automatically generate this sequence of subgoals, even in image-based environments. Our algorithm, search on the replay buffer (SoRB), enables agents to solve sparse reward tasks over one hundred steps, and generalizes substantially better than standard RL algorithms.