# Convergence Results For Q-Learning With Experience Replay

arXiv: https://arxiv.org/abs/2112.04213 · HTML: https://mlsanity.com/paper/2112.04213/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 21 references that are in the map.
- First posted on arXiv 8 Dec 2021.

## Builds on (most cited first, 11 of 11)

- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [Sample Efficient Actor-Critic with Experience Replay](https://mlsanity.com/paper/1611.01224/) (2016)
- [Revisiting Fundamentals of Experience Replay](https://mlsanity.com/paper/2007.06700/) (2020)
- [A Deeper Look at Experience Replay](https://mlsanity.com/paper/1712.01275/) (2017)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Diagnosing Bottlenecks in Deep Q-learning Algorithms](https://mlsanity.com/paper/1902.10250/) (2019)
- [Sample-Efficient Deep Reinforcement Learning via Episodic Backward Update](https://mlsanity.com/paper/1805.12375/) (2018)
- [The Effects of Memory Replay in Reinforcement Learning](https://mlsanity.com/paper/1710.06574/) (2017)
- [Boosting Soft Actor-Critic: Emphasizing Recent Experience without Forgetting the Past](https://mlsanity.com/paper/1906.04009/) (2019)

## Built on by (most cited first, 5 of 5)

- [Understanding Deep Neural Function Approximation in Reinforcement Learning via ε-Greedy Exploration](https://mlsanity.com/paper/2209.07376/) (2022)
- [Introspective Experience Replay: Look Back When Surprised](https://mlsanity.com/paper/2206.03171/) (2022)
- [Adaptive Opponent Policy Detection in Multi-Agent MDPs: Real-Time Strategy Switch Identification Using Running Error Estimation](https://mlsanity.com/paper/2406.06500/) (2024)
- [Approximation to Deep Q-Network by Stochastic Delay Differential Equations](https://mlsanity.com/paper/2505.00382/) (2025)
- [A Convergence Framework for Deep V-Learning: Error Propagation and Sharp Action-Gap Bounds](https://mlsanity.com/paper/2609.18782/) (2026)

## 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.