2020

Revisiting Fundamentals of Experience Replay

Fedus, William, Ramachandran, Prajit, Agarwal, Rishabh et al.

Understand

Experience replay is central to off-policy algorithms in deep reinforcement learning (RL), but there remain significant gaps in our understanding.

We therefore present a systematic and extensive analysis of experience replay in Q-learning methods, focusing on two fundamental properties: the replay capacity and the ratio of learning updates to experience collected (replay ratio).
Our additive and ablative studies upend conventional wisdom around experience replay -- greater capacity is found to substantially increase the performance of certain algorithms, while leaving others unaffected.
Counterintuitively we show that theoretically ungrounded, uncorrected n-step returns are uniquely beneficial while other techniques confer limited benefit for sifting through larger memory.

Built on

Dynamic Programming
Bellman, R · 1957
Earlier work this paper cites.
Learning from delayed rewards
Watkins, C · 1989
Earlier work this paper cites.
Self-improving reactive agents based on reinforcement learning, planning and teaching
Lin, L.-J · 1992
Earlier work this paper cites.
Q-learning
Watkins, C. J. and Dayan, P · 1992
Earlier work this paper cites.
Incremental multi-step q-learning
Peng, J. and Williams, R. J · 1994
Earlier work this paper cites.
Markov Decision Processes: Discrete Stochastic Dynamic Programming
Puterman, M. L · 1994
Earlier work this paper cites.
Neuro-Dynamic Programming
Bertsekas, D. P. and Tsitsiklis, J. N · 1996
Earlier work this paper cites.
Reinforcement learning: A survey
Kaelbling, L. P., Littman, M. L., and Moore, A. W · 1996
Earlier work this paper cites.
Eligibility traces for off-policy policy evaluation
Precup, D., Sutton, R. S., and Singh, S. P · 2000
Earlier work this paper cites.
Algorithms for reinforcement learning
Szepesvári, C · 2010
Earlier work this paper cites.
Box2D: A 2D physics engine for games, 2011
Catto, E · 2011
Earlier work this paper cites.
The Arcade Learning Environment: An evaluation platform for general agents
Bellemare, M. G., Naddaf, Y., Veness, J., and Bowling, M · 2013
Earlier work this paper cites.
Playing Atari with deep reinforcement learning
Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., and Riedmiller, M · 2013
Earlier work this paper cites.
Adam: A method for stochastic optimization
Kingma, D. P. and Ba, J · 2014
Earlier work this paper cites.
A new q ( λ \lambda ) with interim forward view and monte carlo equivalence
Sutton, R., Mahmood, A. R., Precup, D., and Hasselt, H · 2014
Earlier work this paper cites.
Deep recurrent Q-learning for partially observable MDPs
Hausknecht, M. and Stone, P · 2015
Earlier work this paper cites.
Human-level control through deep reinforcement learning
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg, S., and Hassabis, D · 2015
Earlier work this paper cites.

Similar

Prioritized experience replay
Schaul, T., Quan, J., Antonoglou, I., and Silver, D · 2015
Cited alongside, same era.
Dueling network architectures for deep reinforcement learning
Wang, Z., Schaul, T., Hessel, M., Van Hasselt, H., Lanctot, M., and De Freitas, N · 2015
Cited alongside, same era.
Unifying count-based exploration and intrinsic motivation
Bellemare, M., Srinivasan, S., Ostrovski, G., Schaul, T., Saxton, D., and Munos, R · 2016
Cited alongside, same era.
Q( λ \lambda ) with off-policy corrections
Harutyunyan, A., Bellemare, M. G., Stepleton, T., and Munos, R · 2016
Cited alongside, same era.
Reinforcement learning with unsupervised auxiliary tasks
Jaderberg, M., Mnih, V., Czarnecki, W. M., Schaul, T., Leibo, J. Z., Silver, D., and Kavukcuoglu, K · 2016
Cited alongside, same era.
Safe and efficient off-policy reinforcement learning
Munos, R., Stepleton, T., Harutyunyan, A., and Bellemare, M · 2016
Cited alongside, same era.
Deep reinforcement learning with double Q-learning
Van Hasselt, H., Guez, A., and Silver, D · 2016
Cited alongside, same era.
Sample efficient actor-critic with experience replay
Wang, Z., Bapst, V., Heess, N., Mnih, V., Munos, R., Kavukcuoglu, K., and de Freitas, N · 2016
Cited alongside, same era.
A distributional perspective on reinforcement learning
Bellemare, M. G., Dabney, W., and Munos, R · 2017
Cited alongside, same era.
A deeper look at experience replay
Zhang, S. and Sutton, R. S · 2017
Cited alongside, same era.
Dopamine: A research framework for deep reinforcement learning
Castro, P. S., Moitra, S., Gelada, C., Kumar, S., and Bellemare, M. G · 2018
Cited alongside, same era.
Distributional reinforcement learning with quantile regression
Dabney, W., Rowland, M., Bellemare, M. G., and Munos, R · 2018
Cited alongside, same era.

Then

Revisiting the Arcade Learning Environment: Evaluation protocols and open problems for general agents
Machado, M. C., Bellemare, M. G., Talvitie, E., Veness, J., Hausknecht, M., and Bowling, M · 2018
Later among the works it cites.
Organizing experience: A deeper look at replay mechanisms for sample-based planning in continuous state domains
Pan, Y., Zaheer, M., White, A., Patterson, A., and White, M · 2018
Later among the works it cites.
Reinforcement learning: An introduction
Sutton, R. S. and Barto, A. G · 2018
Later among the works it cites.
Deep reinforcement learning and the deadly triad
van Hasselt, H., Doron, Y., Strub, F., Hessel, M., Sonnerat, N., and Modayil, J · 2018
Later among the works it cites.
Reconciling λ \lambda -returns with experience replay
Daley, B. and Amato, C · 2019
Later among the works it cites.
Hyperbolic discounting and learning over multiple horizons
Fedus, W., Gelada, C., Bengio, Y., Bellemare, M. G., and Larochelle, H · 2019
Later among the works it cites.
Diagnosing bottlenecks in deep Q-learning algorithms
Fu, J., Kumar, A., Soh, M., and Levine, S · 2019
Later among the works it cites.
Recurrent experience replay in distributed reinforcement learning
Kapturowski, S., Ostrovski, G., Dabney, W., Quan, J., and Munos, R · 2019
Later among the works it cites.
Sample-efficient deep reinforcement learning via episodic backward update
Lee, S. Y., Sungik, C., and Chung, S.-Y · 2019
Later among the works it cites.
Remember and forget for experience replay
Novati, G. and Koumoutsakos, P · 2019
Later among the works it cites.
Importance resampling for off-policy prediction
Schlegel, M., Chung, W., Graves, D., Qian, J., and White, M · 2019
Later among the works it cites.
When to use parametric models in reinforcement learning?
van Hasselt, H. P., Hessel, M., and Aslanides, J · 2019
Later among the works it cites.
Experience replay optimization
Zha, D., Lai, K.-H., Zhou, K., and Hu, X · 2019
Later among the works it cites.
An optimistic perspective on offline reinforcement learning
Agarwal, R., Schuurmans, D., and Norouzi, M · 2020
Closest in time.
Combining Q-learning and search with amortized value estimates
Hamrick, J. B., Bapst, V., Sanchez-Gonzalez, A., Pfaff, T., Weber, T., Buesing, L., and Battaglia, P. W · 2020
Closest in time.
Ranking policy gradient
Lin, K. and Zhou, J · 2020
Closest in time.
Attentive experience replay
Sun, P., Zhou, W., and Li, H · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…