Search on the Replay Buffer: Bridging Planning and Reinforcement Learning

By Benjamin Eysenbach, Ruslan Salakhutdinov, Sergey Levine. 2019

354 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Reinforcement Learning

Citations in the corpus

Do As I Can, Not As I Say: Grounding Language in Robotic Affordances (2022, methodology): “Machine learning has recently been applied to enable abstract task specification, allow general primitives, or relax constraints [67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78].”
Inner Monologue: Embodied Reasoning through Planning with Language Models (2022, background): “Traditionally, this problem has been solved through optimization [28, 29] or symbolic reasoning [24, 26], but more recently machine learning has been applied to aspects of the problem via learned representations, learned task-primitives, and more [30, 31, 32, 33, 34, 35, 36, 37, 38].”
Learning World Graphs to Accelerate Hierarchical Reinforcement Learning (2019, neutral): “Concurrently, [26] also proposes to plan a sequence of subgoals leading to a ﬁnal destination according to a graph abstraction of the world that is obtained via goal-conditioned policy.”
Towards Continual Reinforcement Learning: A Review and Perspectives (2020, background): “Interestingly, the close connection between experience replay and planning was also recently highlighted in the RL literature (Pan et al., 2018; Eysenbach, Salakhutdinov, and Levine, 2019).”
Learning to Reach Goals via Iterated Supervised Learning (2019, methodology): “Similar algorithmic procedures have also been studied in the context of learning models for planning [Pathak et al., 2018, Savinov et al., 2018, Eysenbach et al., 2019].”
Actionable Models: Unsupervised Offline Reinforcement Learning of Robotic Skills (2021, methodology): “Combining planning algorithms with goal-conditioned RL, as in some recent works (Eysenbach et al., 2019; Ichter et al., 2020), could be an exciting direction for addressing this limitation.”
Example-Driven Model-Based Reinforcement Learning for Solving Long-Horizon Visuomotor Tasks (2021, background): “Alternatively, a number of recent works have studied long horizon visual planning [52, 53, 73, 74, 75, 50, 76, 77, 78], often by combining a structured search approach with learned components like generative models [73, 50, 76] or distance functions [53, 34].”
Learning Language-Conditioned Robot Behavior from Offline Data and Crowd-Sourced Annotation (2021, methodology): “Many approaches have been applied to this domain, ranging from goal-conditioned modelfree learning [2, 63, 55, 64] with goal relabeling [61], model-based planning with a learned visual dynamics model [65, 66], to methods which combine the both [67].”
COG: Connecting New Skills to Past Experience with Offline Reinforcement Learning (2020, result): “In contrast to prior works that approach this problem from a hierarchical skill learning [7, 8] or planning perspective [9, 10], we show that this “understanding” can be acquired without any explicit predictive model or planning, simply via model-free RL.”
Learning to plan with uncertain topological maps (2020, neutral): “[16] also performs planning in 3D environments on a graph-based structure created from randomly sampled observations, with node distances estimated with value estimates.”
Learning to Visually Navigate in Photorealistic Environments Without any Supervision (2020, positive): “Finally, our approach is most related to a recent line of research that uses multiple stages of learning to build a set or graph of scene observations [10, 26, 27, 35].”
First return, then explore (2020, background): “Because goal-conditioned policies often struggle to reach far away states 37 , instead of training the policy to directly reach cells in the archive, the policy is trained to follow the best trajectory of cells that previously led to the selected state (Methods).”
Learning To Reach Goals Without Reinforcement Learning (2019, methodology): “TD3-HER requires signiﬁcantly more machinery than the relatively simple GCSL algorithm: it maintains a policy, a value function, a target policy, and a target value function, all which are required to prevent degradation of the learning procedure.”
Broadly-Exploring, Local-Policy Trees for Long-Horizon Task Planning (2020, background): “Search on the replay buffer (SoRB) [27] for example builds a searchable graph of the replay buffer given a learned distance metric for a goalconditioned policy.”
Value Function Spaces: Skill-Centric State Abstractions for Long-Horizon Reasoning (2021, background): “The combination of learned model-free policies with structures like graphs (Savinov et al., 2018; Eysenbach et al., 2019) and trees (Ichter et al., 2021) to plan over extended horizons has also been demonstrated to improve generalization and exploration.”
Hierarchical Foresight: Self-Supervised Learning of Long-Horizon Tasks via Visual Subgoal Generation (2019, background): “A number of recent works have explored reaching novel goals using only self-supervision (Finn & Levine, 2016; Eysenbach et al., 2019; Kurutach et al., 2018; Wang et al., 2019; Jayaraman et al., 2019; Nair et al., 2018a).”
RvS: What is Essential for Offline RL via Supervised Learning? (2021, methodology): “The tasks include 2D navigation with obstacles ( FourRooms , Eysenbach et al. [9]); two end-effector controlled Sawyer robotic arm tasks ( Door and Pusher , Nair et al. [31]); the Lunar Lander video game, which requires controlling thrusters to land a simulated Lunar Excursion Module ( Lander );…”
Hierarchical reinforcement learning for efficient exploration and transfer (2020, background): “Eysenbach et al. (2019) build distance estimates between pairs of states, and use the distance estimate to condition reinforcement learning in order to reach speciﬁc goals, which is similar to deﬁning temporally extended actions.”
Neural Topological SLAM for Visual Navigation (2020, background): “This includes spatial memories [17, 30] and topological approaches [8, 13, 34, 35, 42, 45].”