Convergence Results For Q-Learning With Experience Replay
This work addresses a foundational issue in reinforcement learning by rigorously analyzing a commonly used heuristic, offering insights for researchers and practitioners in AI.
The paper tackles the problem of understanding the convergence properties of Q-learning with experience replay in tabular settings, providing a convergence rate guarantee and theoretical evidence for when replay improves performance, supported by experiments.
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.