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.
- Nodes as Observations: Every state or image the agent has seen before is treated as a potential "waypoint" (a node in the graph).
- 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.
- 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.
- 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.
- 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