Source-linked AI summary
Search on the Replay Buffer: Bridging Planning and Reinforcement Learning
Benjamin Eysenbach, Ruslan Salakhutdinov, Sergey Levine
TL;DR
Long-horizon sparse-reward tasks remain difficult because planning struggles with high-dimensional observations and reinforcement learning struggles with distant goals. SoRB combines goal-conditioned reinforcement learning with graph search over replay-buffer observations to generate and execute subgoals. It substantially improves distant-goal navigation, including image-based tasks, and generalizes to unseen environments.
Problem
Long-horizon tasks with sparse feedback and high-dimensional observations remain challenging because planning and reinforcement learning each have important limitations.
Method
SoRB uses a goal-conditioned value function to weight a graph whose nodes are replay-buffer observations, then searches the graph for subgoals executed by the learned policy.
Results
SoRB is substantially more successful than standard reinforcement learning at reaching distant goals and solves long-horizon navigation in image-based environments.
Takeaways & Limitations
Graph search over previously visited states can boost goal-conditioned reinforcement learning and support generalization to unseen environments.
Abstract
from arXiv · showhide
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.
1 Introduction
Planning handles long horizons but struggles with high-dimensional observations, while reinforcement learning handles observations yet often fails on distant goals. SoRB combines both by planning through replay-buffer observations as subgoals.
- Planning algorithms support long-horizon tasks but require state sampling, distance estimation, and local policies that are difficult in image-based settings.
- Goal-conditioned RL reaches nearby goals but its performance degrades quickly as the number of steps to distant goals increases.
- SoRB decomposes long-horizon sparse-reward tasks into easier goal-reaching tasks linked by subgoals found through shortest-path search over previously visited states.
- SoRB uses a goal-conditioned policy and value function to generate waypoint plans from replay-buffer observations, including in image-based environments.
- SoRB substantially improves distant-goal success, supports image-based long-horizon navigation without a map or odometry, and generalizes to unseen environments.
2 Bridging Planning and Reinforcement Learning
SoRB turns a replay buffer into a weighted directed graph whose nodes are observations and whose edges use goal-conditioned RL distance estimates. Graph search supplies waypoints, and the learned policy executes them sequentially.
- SoRB addresses planning requirements by sampling states from the replay buffer while learning distances and local control policies with reinforcement learning.
- Goal-conditioned RL learns a policy and Q-function that map current and goal states to actions and expected cumulative reward.
- With reward −1 per step, the value and Q-functions equal negative shortest-path distances to the goal.
- The replay-buffer graph uses observations as nodes and predicted distances as directed edge weights, omitting edges longer than MAXDIST.
- Dijkstra’s algorithm finds a shortest waypoint path after start and goal states are temporarily added to the graph.
- The search policy repeatedly selects a planned waypoint and uses the goal-conditioned policy to reach it.
3 Better Distance Estimates
SoRB’s planning quality depends on accurate distance estimates. Distributional reinforcement learning and value-function ensembles are introduced to make those estimates more reliable for graph search.
- The method develops two techniques—distributional RL and ensembles of value functions—to improve distance estimates used for search.
- Distributional RL represents distance predictions as value distributions whose Bellman targets shift across bins until the goal is reached.
- At the goal, the distributional target places all probability mass in bin 0; otherwise, it shifts the predicted distribution and combines terminal-bin mass.
- Accurate distances are essential because an underestimated distance between distant states can create a graph-search “wormhole” that assumes teleportation.
4 Related Work
Related work spans classical planning, goal-conditioned reinforcement learning, hierarchical reinforcement learning, and model-based reinforcement learning. SoRB combines planning with learned goal-reaching policies for high-dimensional tasks.
- Planning Algorithms: Classical planning solves long-horizon tasks but assumes efficient valid-state sampling, distance estimation, and local policies for nearby states.
- Planning Algorithms: SoRB replaces these planning assumptions by sampling replay-buffer states and learning distances and policies with reinforcement learning.
- Goal-Conditioned RL: Goal-conditioned policies take a current state and goal state as input and predict actions to reach the goal or planned waypoints.
- Hierarchical RL: Hierarchical RL jointly or separately uses primitive skills and higher-level sequencing policies to complete complex tasks.
- Model Based RL: Model-based RL incorporates planning through value prediction, learned representations from dynamics, or policies trained on learned dynamics models.
5 Experiments
Experiments show that SoRB combines goal-conditioned control with graph search to reach distant goals in 2D and image-based navigation, while accurate distance estimates are central to its performance and generalization.
- 5.1 Didactic Example: 2D Navigation: SoRB reaches goals over 100 steps away in simple 2D navigation with little drop in success rate, unlike the goal-conditioned policy alone.SoRB uses the same goal-conditioned policy for graph search and waypoint execution, and can temporarily move away from the goal to navigate hallways.
- 5.2 Planning over Images for Visual Navigation: 90%: SoRB continues reaching visual-navigation goals with approximately this probability as goal distance increases, whereas prior methods degrade quickly.Goals range from 2 to 20 steps, with success defined as reaching within 1 meter within 100 steps; SPTM performs second best but substantially worse.
- 5.3 Comparison with Semi-Parametric Topological Memory: 22% higher AUC: SoRB predicts distances that better reflect reachability than SPTM across five random seeds.Both methods learn comparable policies, so the difference in success is attributed to the accuracy of their learned distance metrics rather than their waypoint policies.
- 5.4 Better Distance Estimates: 10 - 20% increase: ensembles improve success for goals at least 10 steps away, while removing distributional RL makes SoRB perform worse than a random policy.These ablations identify distributional RL and ensembles of value functions as important ingredients for accurate distance estimates.
- 5.5 Generalizing to New Houses: 80%: SoRB reaches almost this fraction of goals 10 steps away in held-out SUNCG houses, compared with less than 20% for goal-conditioned RL.At 20 steps, SoRB reaches 40% of goals while goal-conditioned RL is near 0%; results are consistent across three random seeds.
6 Discussion and Future Work
SoRB combines goal-conditioned RL with graph search over replay-buffer states to plan long-horizon navigation, including image-based tasks. The paper discusses computational efficiency, experimental settings, and future extensions to improve learning and planning.
- 6 Discussion and Future Work: SoRB combines graph search with goal-conditioned RL to solve long-horizon, sparse-reward tasks.The method decomposes distant-goal navigation into easier subgoal-reaching problems over previously visited states.
- 6 Discussion and Future Work: Future work targets joint improvement of graph search and goal-conditioned policies, alongside more sophisticated planning methods.The paper specifically mentions policy distillation, better Q-value estimates, and planners beyond Dijkstra.
- 6 Discussion and Future Work: Cached shortest-path computation reduces value-function queries from O(|B|^2) to O(|B|).The implementation amortizes computation across policy calls using cached pairwise distances and Floyd–Warshall.
- 6 Discussion and Future Work: The visual-navigation experiments use SUNCG houses, panoramic RGB or depth observations, and four directional actions.Goals are sampled nearby in 80% of episodes, and episodes terminate within 1 meter of the goal or after 20 steps.
C Ablation Experiments
The ablations identify distributional RL and ensemble value functions as important components of SoRB, while reducing replay-buffer size has limited impact within the tested range.
- C Ablation Experiments: MAXDIST is important to SoRB’s success, whereas decreasing buffer size has little effect.The sensitivity experiment varies buffer size and the maximum edge distance separately.
- C Ablation Experiments: 10x smaller replay buffers cause no discernible performance drop in the tested experiment.The authors still expect performance to decline if the buffer is reduced further.
- C Ablation Experiments: Distributional RL is a key component: removing it makes SoRB perform worse than a random policy.The authors attribute this component’s usefulness partly to its distance-compatible value update and implicit clipping.
E Failed Experiments
Additional experiments tested goal relabelling, search-derived Q-value lower bounds, and TD3-style ensemble aggregation; these alternatives did not improve the main method in the reported trials.
- E Failed Experiments: Goal relabelling hurt the non-search policy and had no effect on the search policy.
- E Failed Experiments: Search-derived lower bounds on target Q-values slowed learning in initial experiments.The approach replaced target-network distances with the minimum of target-network and search-path distances.
- E Failed Experiments: TD3-style aggregation was explored as an alternative to taking the maximum expected distance across critics.The experiment was motivated by the stability of TD3 and sought to use the distributional critics more fully.
- E Failed Experiments: Unless otherwise noted, baselines used SoRB’s hyperparameters without tuning.
F.1 Search on the Replay Buffer
Table 1 lists the hyperparameters used for SoRB.
- F.1 Search on the Replay Buffer: Table 1 presents the hyperparameters for SoRB.
F.2 Value Iteration Networks
Table 2 lists the hyperparameters used for the Value Iteration Network (VIN).
- Table 2 reports VIN hyperparameters.
- The table is associated with Tamar et al. (2016).
- The section identifies the table as a reference for VIN configuration.
F.3 Semi-Parametric Topological Memory
The SPTM section reports its hyperparameters and describes extensive tuning of the search-related settings.
- The authors tuned l on goal-reaching without search before fixing its value.
- They then conducted over 1000 experiments varying M, sreach, and the edge-addition threshold.
- Table 3 reports hyperparameters for SPTM.