Convergence Results For Q-Learning With Experience Replay
Not on the map. Why?
Abstract (arXiv)
A commonly used heuristic in RL is experience replay (e.g.~citetlin1993reinforcement, mnih2015human), in which a learner stores and re-uses past trajectories as if they were sampled online. In this work, we initiate a rigorous study of this heuristic in the setting of tabular Q-learning. We provide a convergence rate guarantee, and discuss how it compares to the convergence of Q-learning depending on important parameters such as the frequency and number of replay iterations. We also provide theoretical evidence showing when we might expect this heuristic to strictly improve performance, by introducing and analyzing a simple class of MDPs. Finally, we provide some experiments to support our theoretical findings.
Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 11 of its 21 references that are in the map. First posted on arXiv 8 Dec 2021.
Builds on
11 of 21 references.
References · 11
- 2015Prioritized Experience Replaycited by 1,070
- 2016Sample Efficient Actor-Critic with Experience Replaycited by 185
- 2020Revisiting Fundamentals of Experience Replaycited by 171
- 2017A Deeper Look at Experience Replaycited by 104
- 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 93
- 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
- 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
- 2019Diagnosing Bottlenecks in Deep Q-learning Algorithmscited by 73
- 2018Sample-Efficient Deep Reinforcement Learning via Episodic Backward Updatecited by 29
- 2017The Effects of Memory Replay in Reinforcement Learningcited by 22
- 2019Boosting Soft Actor-Critic: Emphasizing Recent Experience without Forgetting the Pastcited by 16
Built on by
Citing papers per year: 2022: 2; 2023: 0; 2024: 1; 2025: 1; 2026: 1.
5 papers.
- 2022Understanding Deep Neural Function Approximation in Reinforcement Learning via ε-Greedy Explorationcited by 11
- 2022Introspective Experience Replay: Look Back When Surprisedcited by 3
- 2024Adaptive Opponent Policy Detection in Multi-Agent MDPs: Real-Time Strategy Switch Identification Using Running Error Estimationcited by 0
- 2025Approximation to Deep Q-Network by Stochastic Delay Differential Equationscited by 0
- 2026A Convergence Framework for Deep V-Learning: Error Propagation and Sharp Action-Gap Boundscited by 0
- 2026A Convergence Framework for Deep V-Learning: Error Propagation and Sharp Action-Gap Bounds16 Sep 2026
- 2025Approximation to Deep Q-Network by Stochastic Delay Differential Equations1 May 2025
- 2024Adaptive Opponent Policy Detection in Multi-Agent MDPs: Real-Time Strategy Switch Identification Using Running Error Estimation10 Jun 2024
- 2022Understanding Deep Neural Function Approximation in Reinforcement Learning via ε-Greedy Exploration15 Sep 2022
- 2022Introspective Experience Replay: Look Back When Surprised7 Jun 2022