  A commonly used heuristic in RL is experience replay
(e.g.~\citet{lin1993reinforcement, 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.
