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 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.
Introduction
In robotics and control, a historical divide exists between planning algorithms and reinforcement learning (RL). Planning algorithms, such as A* or Dijkstra, are adept at reasoning over long horizons but require a known distance metric, a local policy, and a method to sample valid states—requirements that are difficult to satisfy with high-dimensional observations like raw camera images. Conversely, RL excels at handling high-dimensional inputs but struggles with long horizons and sparse rewards. Recent goal-conditioned RL methods learn to reach nearby goals but often fail as the distance increases.
We introduce Search on the Replay Buffer (SoRB), an algorithm that bridges this gap. SoRB treats previously visited states in the replay buffer as nodes in a graph and uses a learned goal-conditioned value function to estimate distances between them. This allows standard graph search to find waypoints through high-dimensional environments, enabling agents to reach distant goals that standard RL cannot solve.
Methodology
SoRB decomposes long-horizon tasks into a sequence of easier, short-horizon waypoint-reaching tasks through a four-step process:
- Goal-Conditioned RL as a Distance Metric: The agent is trained using off-policy RL with a constant -1 reward per step. Under this structure, the learned Q-value function represents the negative shortest-path distance between states.
- The Replay Buffer as a Graph: Every observation in the agent's replay buffer becomes a node in a directed graph. This uses the agent's past experiences as a non-parametric generative model of valid states.
- Graph Search: The learned Q-function predicts edge weights (distances) between nodes. Edges exceeding a threshold are ignored. Dijkstra's algorithm is then used to find the shortest path of waypoints from start to goal.
- Execution: The agent utilizes its learned local policy to navigate to the first waypoint, eventually targeting the goal directly when it is within reach.
Robustness Enhancements
To handle the challenges of learned distance metrics, SoRB incorporates two key features:
- Distributional RL: Standard Q-networks struggle with unreachable states. SoRB uses Distributional RL to shift probability mass into a "maximum distance" bin, providing a more graceful way to represent infinite distance.
- Ensembles: To prevent "wormholes"—where a neural network erroneously predicts two distant states are close—SoRB uses an ensemble of Q-networks. Aggregating these predictions allows the agent to robustly estimate uncertainty and avoid exploitative shortcuts in the graph.
Experiments and Results
We evaluated SoRB in 2D didactic environments (Point-U and Point-FourRooms) and visual navigation tasks using the SUNCG dataset, where agents navigate 3D houses using panoramic images.
- Horizon Extension: In 2D environments, SoRB successfully reaches goals over 100 steps away with high success rates, while baseline goal-conditioned RL fails completely for distant goals.
- Visual Navigation: On SUNCG image-based tasks, SoRB maintains a ~90% success rate for goals up to 20 steps away, significantly outperforming prior methods like HER and VIN, which drop to near 0% at that distance.
- Zero-Shot Generalization: When placed in completely unseen houses, SoRB reaches ~80% of goals 10 steps away, compared to less than 20% for standard RL. This demonstrates that search can fix RL's generalization problems by chaining reliable short-range trajectories.
Conclusion
SoRB demonstrates that the replay buffer can serve as a powerful abstraction for planning. By using RL-based distance estimates, we can integrate classical planning techniques into deep RL frameworks. While the method depends on the reliability of the underlying local policy and requires computational overhead for graph search, it provides a robust path forward for solving long-horizon, sparse-reward tasks in high-dimensional state spaces.
Summary updated