Search on the Replay Buffer: Bridging Planning and Reinforcement Learning

Ben Eysenbach, Ruslan Salakhutdinov, Sergey Levine

TL;DR

Search on the Replay Buffer (SoRB) is a hybrid algorithm that uses a reinforcement learning agent's own memory—its replay buffer—as a map for long-range planning. By treating past observations as nodes in a graph and using a learned value function to estimate the "distance" between them, SoRB allows agents to solve complex, long-horizon tasks that stump traditional RL.

The Challenge of Long-Horizon Reasoning

Reinforcement Learning (RL) is excellent at mastering "local" control, such as learning how to move a robotic joint or navigate a single room, especially when dealing with high-dimensional inputs like raw images. However, RL notoriously struggles with long-horizon reasoning. If a goal is hundreds of steps away and rewards are sparse (only given at the very end), a standard RL agent often fails to connect its current state to the distant goal.

On the other hand, classical planning algorithms (like Dijkstra’s or A*) are great at long-range navigation but usually require a pre-defined map, a perfect distance metric, and a way to handle "low-level" control. In complex environments, such as a 3D house seen through a camera, we don't have a map, and "distance" isn't just a straight line—it's the number of actions required to get from point A to point B.

The authors aim to bridge this gap: How can we give an RL agent the "foresight" of a planner without losing its ability to handle raw, high-dimensional observations?

Methods: Turning Memory into a Map

The core idea of SoRB is to turn the agent's replay buffer (the database of its past experiences) into a searchable graph.

The SoRB process: (a) Start and goal, (b) Replay buffer states as nodes, (c) Edges based on Q-value distances, (d) Planned path.
  1. Nodes as Observations: Every state or image the agent has seen before is treated as a potential "waypoint" (a node in the graph).
  2. Edges as Distances: The authors use a goal-conditioned Q-function to estimate how many steps it takes to get from one observation to another. If the agent thinks it can reach state B from state A in fewer than a certain number of steps ($MAXDIST$), it draws a "road" (an edge) between them.
  3. Distributional RL: To get accurate distance estimates, the method employs distributional RL. Instead of predicting a single average reward, the network predicts a probability distribution over how many steps a goal is away. This is crucial for representing "infinite" distance for unreachable states.
Distributional RL predicting distance to goal.
  1. Ensembles for Robustness: To prevent "wormholes"—where an agent mistakenly thinks two distant states are close (e.g., two sides of a thin wall)—they use an ensemble of value functions. The agent only trusts a path if multiple networks agree it's short.
  2. Planning via Search: When given a distant goal, the agent runs Dijkstra’s algorithm over this graph to find a sequence of subgoals. It then uses its local RL policy to hop from one waypoint to the next until it reaches the final destination.

Key Insights

  • The Replay Buffer is a Map: We usually think of the replay buffer as just training data. This paper realizes it's actually a non-parametric model of the environment's "walkable" space.
  • Q-Values are Distances: In a goal-conditioned setting with a reward of -1 per step, the Q-value is mathematically equivalent to the negative distance to the goal. This allows the RL agent to "self-generate" the weights for its own planning graph.
  • Decomposing the Hard into the Easy: Instead of trying to learn one massive, perfect policy that can go anywhere, SoRB learns a "local" policy that is very good at short distances and lets graph search handle the "global" logic.
  • Risk-Aware Planning: By using ensembles, the agent becomes "pessimistic" about shortcuts. This prevents the planner from trying to walk through walls just because a single neural network had a fluke prediction.

Evaluation and Results

The authors evaluated SoRB on two main types of environments: simple 2D navigation tasks and complex Visual Navigation (SUNCG) using 3D house layouts with high-dimensional observations.

  • Massive Horizon Extension: In 2D tasks, standard RL success rates drop to near zero once the goal is more than 60 steps away. SoRB maintains nearly 100% success even at 120 steps.
  • Superior Visual Navigation: In the 3D house environment, SoRB achieved a 90% success rate for distant goals, while state-of-the-art baselines like SPTM (Semi-Parametric Topological Memory) and VIN (Value Iteration Networks) struggled to break 50%.
  • Zero-Shot Generalization: When placed in a brand-new house, SoRB can navigate effectively just by taking a few random actions to populate its "map" (replay buffer) and then using its pre-trained distance-estimator to plan. It reached goals 10 steps away in new houses 80% of the time, whereas standard RL failed almost entirely (under 20%).

Limitations and Future Work

While powerful, SoRB has a few limitations. As the replay buffer grows, the graph becomes larger, and searching a graph with hundreds of thousands of nodes could eventually become a computational bottleneck. Additionally, the planner can only find paths through states it has already visited; if the agent hasn't explored a specific hallway, it can't plan a route through it.

Finally, the current method assumes the environment is static. Adapting this to dynamic environments (where doors might open/close or obstacles move) remains an open challenge. Future work could involve "distilling" the graph search back into the policy itself to make the agent even faster and more integrated.

Summary updated

Abstract

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 relative values of states, but fails to plan over long horizons. Despite the successes of each method on various tasks, long horizon, sparse reward tasks with 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 injecting bias through reward shaping. We introduce a general-purpose control algorithm that combines the strengths of planning and reinforcement learning to effectively solve these tasks. Our main idea is to decompose the task of reaching a distant goal state into a sequence of easier tasks, each of which corresponds to reaching a particular subgoal. We use goal-conditioned RL to learn a policy to reach each waypoint and to learn a distance metric for search. 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 hundreds of steps, and generalizes substantially better than standard RL algorithms.
BibTeX
@inproceedings{eysenbach2019search,
  author = {Ben Eysenbach and Ruslan Salakhutdinov and Sergey Levine},
  title = {{Search on the Replay Buffer: Bridging Planning and Reinforcement Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=UVBYIrfjxI},
}
Figure