Abstract: Experience replay is a foundational technique in reinforcement learning that enhances learning stability by storing past experiences in a replay buffer and reusing them during training. Despite its practical success, its theoretical properties remain underexplored. In this paper, we present a theoretical framework that models experience replay using resampled $U$- and $V$-statistics, providing rigorous variance reduction guarantees. We apply this framework to policy evaluation tasks using the Least-Squares Temporal Difference (LSTD) algorithm and a Partial Differential Equation (PDE)-based model-free algorithm, demonstrating significant improvements in stability and efficiency, particularly in data-scarce scenarios. Beyond policy evaluation, we extend the framework to kernel ridge regression, showing that the experience replay-based method reduces the computational cost from the traditional $O(n^3)$ in time to as low as $O(n^2)$ in time while simultaneously reducing variance. Extensive numerical experiments validate our theoretical findings, demonstrating the broad applicability and effectiveness of experience replay in diverse machine learning tasks.
Introduction
Experience Replay (ER)—the practice of storing past transitions in a buffer and re-sampling them for training—has become a cornerstone of modern Reinforcement Learning (RL). From the early successes of DQN to the sophisticated architectures of AlphaGo, ER is credited with breaking temporal correlations and stabilizing the learning process. However, despite its ubiquity, the theoretical underpinnings of ER have remained largely anecdotal. Practitioners often treat the replay buffer as a "black box," relying on empirical tuning for buffer size ($n$) and replay ratio ($B$).
This work provides a formal mathematical understanding of ER by connecting it to the statistical theory of resampled $U$- and $V$-statistics. We demonstrate that ER is not merely a heuristic for data decorrelation but a fundamental variance-reduction technique. By averaging over multiple resampled "mini-histories," the resulting estimator achieves significantly higher stability than one trained on the full dataset a single time.
A Unified Statistical Framework
We bridge the gap between RL and classical statistics by modeling the ER process as a resampling procedure. Specifically, we frame ER as the computation of incomplete $U$-statistics (sampling subsets without replacement) or $V$-statistics (sampling with replacement).
Consider a general learning function $h_k$ that takes $k$ data points as input. The ER estimate is defined as the average of this function over $B$ random subsets of size $k$ drawn from a buffer of size $n$. This formulation allows us to leverage established statistical tools to derive asymptotic variance guarantees. A key insight from our theory is the "Buffer Size Paradox": for a fixed replay ratio $B$, the buffer size $n$ cannot be arbitrarily large without diminishing returns. Variance reduction is most effective when the ratio $n/(Bk)$ is small; if the buffer grows too large relative to the replay frequency, the statistical benefits of resampling are diluted.
Policy Evaluation: LSTD and PDE-based Approaches
We applied this framework to two distinct policy evaluation algorithms: the classic Least-Squares Temporal Difference (LSTD) and a novel Partial Differential Equation (PDE)-based model-free algorithm designed for continuous-time RL.
In both cases, the ER-based estimators demonstrated significantly tighter confidence intervals compared to the original methods. As shown in the comparison below, the $U$- and $V$-statistics methods produce value function estimates with much lower variance, particularly in the regions of the state space where data might be sparse.
Beyond RL: Efficient Kernel Ridge Regression
The benefits of the ER framework extend to supervised learning, specifically Kernel Ridge Regression (KRR) in Reproducing Kernel Hilbert Spaces (RKHS). Traditional KRR requires matrix inversion, leading to a computational complexity of $O(n^3)$. By applying our ER framework, we can average over smaller subsamples of size $k$, reducing the complexity to $O(n^2)$.
Remarkably, this reduction in complexity does not come at the cost of accuracy. In our experiments, the ER-based $U$-statistic method was orders of magnitude faster (e.g., 0.1s vs 3s for $n=250$) while simultaneously achieving lower variance and Mean Squared Error (MSE) than the standard $O(n^3)$ approach. The following figure illustrates the consistent variance reduction achieved across different sample sizes.
Conclusion and Future Directions
Our work establishes a rigorous foundation for Experience Replay, proving its efficacy as a variance reduction tool across both reinforcement and supervised learning. While our current framework assumes uniform sampling, future work will explore the theoretical properties of Prioritized Experience Replay (PER). Additionally, extending these variance guarantees from policy evaluation to the "control" problem (policy improvement) remains a vital next step for the field. The resampling framework also holds promise for distributed learning environments, where it could guide the selection of the most informative data subsets.
Summary updated