CoChat
Sign Up
PreprintCited by 123Reinforcement Learning in RoboticsAI-based Problem Solving and PlanningArtificial Intelligence in Games

Search on the Replay Buffer: Bridging Planning and Reinforcement Learning

Open access
Eysenbach, Benjamin, Salakhutdinov, Ruslan, Levine, Sergey·2019·arXiv
DOI 10.48550/arxiv.1906.05253arXiv 1906.05253
Open this paper in CoChat — free accountOpen PDF

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1906.05253

Cites

6 of 6 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Techniques patterned after episodic memory have been explored in machine learning literature.

    “Techniques patterned after or inspired by episodic memory have been explored in the machine learning literature.”

    From Episodic Memory in AI Agents Poses Risks that Should be Studied and Mitigated (2025) · cites this paper as [18]

    The Introduction (p. 1) describes a machine-learning technique that uses previously visited states from a replay buffer to plan a sequence of subgoals. This supports the claim that techniques using stored experiences have been explored, but the paper does not describe its method as patterned after or inspired by episodic memory. (LLM, conf=0.76)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 56

  1. Agrawal, P., Nair, A. V., Abbeel, P., Malik, J., and Levine, S. (2016). Learning to poke by poking: Experiential learning of intuitive physics. In Advances in Neural Information Processing Systems , pages 5074-5082.
  2. Amos, B., Jimenez, I., Sacks, J., Boots, B., and Kolter, J. Z. (2018). Differentiable mpc for end-to-end planning and control. In Advances in Neural Information Processing Systems , pages 8289-8300.
  3. Anderson, P., Wu, Q., Teney, D., Bruce, J., Johnson, M., S¨ underhauf, N., Reid, I., Gould, S., and van den Hengel, A. (2018). Vision-and-language navigation: Interpreting visually-grounded navigation instructions in real environments. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition , pages 3674-3683.
  4. Andrychowicz, M., Wolski, F., Ray, A., Schneider, J., Fong, R., Welinder, P., McGrew, B., Tobin, J., Abbeel, O. P., and Zaremba, W. (2017). Hindsight experience replay. In Advances in Neural Information Processing Systems , pages 5048-5058.
  5. Bacon, P.-L., Harb, J., and Precup, D. (2017). The option-critic architecture. In Thirty-First AAAI Conference on Artificial Intelligence .
  6. Bellemare, M. G., Dabney, W., and Munos, R. (2017). A distributional perspective on reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning-Volume 70 , pages 449-458. JMLR. org.
  7. Bickel, P. J., Freedman, D. A., et al. (1981). Some asymptotic theory for the bootstrap. The annals of statistics , 9(6):1196-1217.
  8. Chiang, H.-T. L., Faust, A., Fiser, M., and Francis, A. (2019). Learning navigation behaviors end-to-end with autorl. IEEE Robotics and Automation Letters , 4(2):2007-2014.
  9. Choset, H. M., Hutchinson, S., Lynch, K. M., Kantor, G., Burgard, W., Kavraki, L. E., and Thrun, S. (2005). Principles of robot motion: theory, algorithms, and implementation . MIT press.
  10. Chua, K., Calandra, R., McAllister, R., and Levine, S. (2018). Deep reinforcement learning in a handful of trials using probabilistic dynamics models. In Advances in Neural Information Processing Systems , pages 4759-4770.
  11. Drummond, C. (2002). Accelerating reinforcement learning by composing solutions of automatically identified subtasks. Journal of Artificial Intelligence Research , 16:59-104.
  12. Faust, A., Ramirez, O., Fiser, M., Oslund, K., Francis, A., Davidson, J., and Tapia, L. (2018). Prm-rl: Long-range robotic navigation tasks by combining reinforcement learning and sampling-based planning. In Proc. IEEE Int. Conf. Robot. Autom. (ICRA) , pages 5113-5120, Brisbane, Australia.
  13. Finn, C. and Levine, S. (2017). Deep visual foresight for planning robot motion. In 2017 IEEE International Conference on Robotics and Automation (ICRA) , pages 2786-2793. IEEE.
  14. Florensa, C., Degrave, J., Heess, N., Springenberg, J. T., and Riedmiller, M. (2019). Self-supervised learning of image embedding for continuous control. arXiv preprint arXiv:1901.00943 . · arXiv
  15. Fox, R., Krishnan, S., Stoica, I., and Goldberg, K. (2017). Multi-level discovery of deep options. arXiv preprint arXiv:1703.08294 . · arXiv
  16. Frans, K., Ho, J., Chen, X., Abbeel, P., and Schulman, J. (2017). Meta learning shared hierarchies. arXiv preprint arXiv:1710.09767 . · arXiv
  17. Gupta, S., Davidson, J., Levine, S., Sukthankar, R., and Malik, J. (2017). Cognitive mapping and planning for visual navigation. arXiv preprint arXiv:1702.03920 , 3. · arXiv
  18. Hadar, J. and Russell, W. R. (1969). Rules for ordering uncertain prospects. The American Economic Review , 59(1):25-34.
  19. Kaelbling, L. P. (1993a). Hierarchical learning in stochastic domains: Preliminary results. In Proceedings of the tenth international conference on machine learning , volume 951, pages 167-173.
  20. Kaelbling, L. P. (1993b). Learning to achieve goals. In IJCAI , pages 1094-1099. Citeseer.
  21. Kulkarni, T. D., Narasimhan, K., Saeedi, A., and Tenenbaum, J. (2016). Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation. In Advances in neural information processing systems , pages 3675-3683.
  22. Kurutach, T., Clavera, I., Duan, Y., Tamar, A., and Abbeel, P. (2018). Model-ensemble trust-region policy optimization. arXiv preprint arXiv:1802.10592 . · arXiv
  23. Lakshminarayanan, B., Pritzel, A., and Blundell, C. (2017). Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in Neural Information Processing Systems , pages 6402-6413.
  24. Lau, M. and Kuffner, J. J. (2005). Behavior planning for character animation. In Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation , pages 271-280. ACM.
  25. LaValle, S. M. (2006). Planning algorithms . Cambridge university press.
  26. Lee, L., Parisotto, E., Chaplot, D. S., Xing, E., and Salakhutdinov, R. (2018). Gated path planning networks. arXiv preprint arXiv:1806.06408 . · arXiv
  27. Levine, S., Lee, Y., Koltun, V., and Popovi´ c, Z. (2011). Space-time planning with parameterized locomotion controllers. ACM Transactions on Graphics (TOG) , 30(3):23.
  28. Levy, A., Platt, R., and Saenko, K. (2019). Hierarchical reinforcement learning with hindsight. In International Conference on Learning Representations .
  29. Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. (2015). Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.02971 . · arXiv
  30. Lynch, C., Khansari, M., Xiao, T., Kumar, V., Tompson, J., Levine, S., and Sermanet, P. (2019). Learning latent plans from play. arXiv preprint arXiv:1903.01973 . · arXiv
  31. Mirowski, P., Pascanu, R., Viola, F., Soyer, H., Ballard, A. J., Banino, A., Denil, M., Goroshin, R., Sifre, L., Kavukcuoglu, K., et al. (2016). Learning to navigate in complex environments. arXiv preprint arXiv:1611.03673 . · arXiv
  32. Nagabandi, A., Kahn, G., Fearing, R. S., and Levine, S. (2018). Neural network dynamics for model-based deep reinforcement learning with model-free fine-tuning. In 2018 IEEE International Conference on Robotics and Automation (ICRA) , pages 7559-7566. IEEE.
  33. Oh, J., Guo, X., Lee, H., Lewis, R. L., and Singh, S. (2015). Action-conditional video prediction using deep networks in atari games. In Advances in neural information processing systems , pages 2863-2871.
  34. Osband, I., Blundell, C., Pritzel, A., and Van Roy, B. (2016). Deep exploration via bootstrapped dqn. In Advances in neural information processing systems , pages 4026-4034.
  35. Pardo, F., Tavakoli, A., Levdik, V., and Kormushev, P. (2017). Time limits in reinforcement learning. arXiv preprint arXiv:1712.00378 . · arXiv
  36. Parr, R. and Russell, S. J. (1998). Reinforcement learning with hierarchies of machines. In Advances in neural information processing systems , pages 1043-1049.
  37. Pong, V., Gu, S., Dalal, M., and Levine, S. (2018). Temporal difference models: Model-free deep rl for model-based control. arXiv preprint arXiv:1802.09081 . · arXiv
  38. Racani` ere, S., Weber, T., Reichert, D., Buesing, L., Guez, A., Rezende, D. J., Badia, A. P., Vinyals, O., Heess, N., Li, Y., et al. (2017). Imagination-augmented agents for deep reinforcement learning. In Advances in neural information processing systems , pages 5690-5701.
  39. Savinov, N., Dosovitskiy, A., and Koltun, V. (2018a). Semi-parametric topological memory for navigation. arXiv preprint arXiv:1803.00653 . · arXiv
  40. Savinov, N., Raichuk, A., Marinier, R., Vincent, D., Pollefeys, M., Lillicrap, T., and Gelly, S. (2018b). Episodic curiosity through reachability. arXiv preprint arXiv:1810.02274 . · arXiv
  41. Schaul, T., Horgan, D., Gregor, K., and Silver, D. (2015). Universal value function approximators. In International Conference on Machine Learning , pages 1312-1320.
  42. Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. (2015a). Trust region policy optimization. In International Conference on Machine Learning , pages 1889-1897.
  43. Schulman, J., Moritz, P., Levine, S., Jordan, M., and Abbeel, P. (2015b). High-dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv:1506.02438 . · arXiv
  44. Shah, P., Fiser, M., Faust, A., Kew, J. C., and Hakkani-Tur, D. (2018). Follownet: Robot navigation by following natural language directions with deep reinforcement learning. arXiv preprint arXiv:1805.06150 . · arXiv
  45. Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. (2016). Mastering the game of go with deep neural networks and tree search. nature , 529(7587):484.
  46. S ¸ ims ¸ek, ¨ O., Wolfe, A. P., and Barto, A. G. (2005). Identifying useful subgoals in reinforcement learning by local graph partitioning. In Proceedings of the 22nd international conference on Machine learning , pages 816-823. ACM.
  47. Song, S., Yu, F., Zeng, A., Chang, A. X., Savva, M., and Funkhouser, T. (2017). Semantic scene completion from a single depth image. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition , pages 1746-1754.
  48. Srinivas, A., Jabri, A., Abbeel, P., Levine, S., and Finn, C. (2018). Universal planning networks. arXiv preprint arXiv:1804.00645 . · arXiv
  49. Sutton, R. S. (1990). Integrated architectures for learning, planning, and reacting based on approximating dynamic programming. In Machine Learning Proceedings 1990 , pages 216-224. Elsevier.
  50. Tamar, A., Wu, Y., Thomas, G., Levine, S., and Abbeel, P. (2016). Value iteration networks. In Advances in Neural Information Processing Systems , pages 2154-2162.
  51. Vezhnevets, A. S., Osindero, S., Schaul, T., Heess, N., Jaderberg, M., Silver, D., and Kavukcuoglu, K. (2017). Feudal networks for hierarchical reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning-Volume 70 , pages 3540-3549. JMLR. org.
  52. Watkins, C. J. and Dayan, P. (1992). Q-learning. Machine learning , 8(3-4):279-292.
  53. Watter, M., Springenberg, J., Boedecker, J., and Riedmiller, M. (2015). Embed to control: A locally linear latent dynamics model for control from raw images. In Advances in neural information processing systems , pages 2746-2754.
  54. Williams, R. J. (1992). Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning , 8(3-4):229-256.
  55. Wu, Y., Tucker, G., and Nachum, O. (2018). The laplacian in rl: Learning representations with efficient approximations. arXiv preprint arXiv:1810.04586 . · arXiv
  56. Zhu, Y., Mottaghi, R., Kolve, E., Lim, J. J., Gupta, A., Fei-Fei, L., and Farhadi, A. (2017). Target-driven visual navigation in indoor scenes using deep reinforcement learning. In Robotics and Automation (ICRA), 2017 IEEE International Conference on , pages 3357-3364. IEEE.

Cited by

Sorted by citations

Authors
Eysenbach, B., Salakhutdinov, R., & Levine, S.
Affiliations
  • Carnegie Mellon University (US)
  • Google (United States) (US)
  • University of California, Berkeley (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2019
Volume
32
Pages
15220-15231
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1906.05253
arXiv
1906.05253
OpenAlex
W2950885698
Cited by
123
References
6
Citations by year
2026: 1 · 2025: 11 · 2024: 34 · 2023: 24 · 2022: 19 · 2021: 25 · 2020: 9
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Science Foundation
  • Office of Naval Research (N000141812861)
  • Air Force Research Laboratory
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
  • Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
  • Physical Sciences › Computer Science › Artificial Intelligence › Artificial Intelligence in Games
Keywords
long-horizon control, sparse rewards, subgoal decomposition, graph search, replay buffer, waypoint generation

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review