Variance Reduction via Resampling and Experience Replay

• URL: http://arxiv.org/abs/2502.00520v1
• Date: Sat, 01 Feb 2025 18:46:08 GMT
• Title: Variance Reduction via Resampling and Experience Replay
• Authors: Jiale Han, Xiaowu Dai, Yuhua Zhu,
• Abstract summary: We present a theoretical framework that models experience replay using resampled $U$- and $V$-statistics.<n>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.<n>We extend the framework to kernel ridge regression, showing that the experience replay-based method reduces the computational cost from the traditional $O(n3)$ in time while simultaneously reducing variance.
• Score: 6.66746639974303
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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.

Related papers

• Observationally Informed Adaptive Causal Experimental Design [55.998153710215654]
  We propose Active Residual Learning, a new paradigm that leverages the observational model as a foundational prior.<n>This approach shifts the experimental focus from learning target causal quantities from scratch to efficiently estimating the residuals required to correct observational bias.<n> Experiments on synthetic and semi-synthetic benchmarks demonstrate that R-Design significantly outperforms baselines.
  arXiv  Detail & Related papers  (2026-03-04T06:52:37Z)
• Variance Reduction Based Experience Replay for Policy Optimization [3.7128732378843394]
  Variance Reduction Experience Replay (VRER) is a principled framework that selectively reuses informative samples to reduce variance in policy gradient estimation.<n>VRER is algorithm-agnostic and integrates seamlessly with existing policy optimization methods.<n>We show that VRER consistently accelerates policy learning and improves performance over state-of-the-art policy optimization algorithms.
  arXiv  Detail & Related papers  (2026-02-05T06:58:28Z)
• Beyond Imitation: Recovering Dense Rewards from Demonstrations [64.05543657441218]
  supervised fine-tuning is treated as a simple imitation learning process that only trains a policy to imitate expert behavior on datasets.<n>We prove that the SFT process does not just learn a policy, but also an implicit, dense, token-level reward model that explains the expert demonstrations.<n>Dense-Path REINFORCE consistently outperforms the original SFT models on instruction-following benchmarks.
  arXiv  Detail & Related papers  (2025-10-02T18:58:26Z)
• ExGRPO: Learning to Reason from Experience [82.83309610498446]
  Reinforcement learning from verifiable rewards (RLVR) is an emerging paradigm for improving the reasoning ability of large language models.<n>Standard on-policy training discards rollout experiences after a single update, leading to computational inefficiency and instability.<n>In this paper, we are the first to investigate what makes a reasoning experience valuable and identify rollout correctness and entropy as effective indicators of experience value.
  arXiv  Detail & Related papers  (2025-10-02T17:31:30Z)
• Nested-ReFT: Efficient Reinforcement Learning for Large Language Model Fine-Tuning via Off-Policy Rollouts [25.205293698698867]
  We introduce Nested-ReFT, where a subset of layers of the target model acts as the behavior model to generate off-policy completions during training.<n>Our theoretical analysis shows that Nested-ReFT yields unbiased gradient estimates with controlled variance.<n>Our empirical analysis demonstrates improved computational efficiency measured as tokens/sec across multiple math reasoning benchmarks and model sizes.
  arXiv  Detail & Related papers  (2025-08-13T18:37:46Z)
• Neural Active Learning Beyond Bandits [69.99592173038903]
  We study both stream-based and pool-based active learning with neural network approximations. We propose two algorithms based on the newly designed exploitation and exploration neural networks for stream-based and pool-based active learning.
  arXiv  Detail & Related papers  (2024-04-18T21:52:14Z)
• Enhancing Consistency and Mitigating Bias: A Data Replay Approach for Incremental Learning [100.7407460674153]
  Deep learning systems are prone to catastrophic forgetting when learning from a sequence of tasks. To mitigate the problem, a line of methods propose to replay the data of experienced tasks when learning new tasks. However, it is not expected in practice considering the memory constraint or data privacy issue. As a replacement, data-free data replay methods are proposed by inverting samples from the classification model.
  arXiv  Detail & Related papers  (2024-01-12T12:51:12Z)
• Actor Prioritized Experience Replay [0.0]
  Prioritized Experience Replay (PER) allows agents to learn from transitions sampled with non-uniform probability proportional to their temporal-difference (TD) error. We introduce a novel experience replay sampling framework for actor-critic methods, which also regards issues with stability and recent findings behind the poor empirical performance of PER. An extensive set of experiments verifies our theoretical claims and demonstrates that the introduced method significantly outperforms the competing approaches.
  arXiv  Detail & Related papers  (2022-09-01T15:27:46Z)
• Look Back When Surprised: Stabilizing Reverse Experience Replay for Neural Approximation [7.6146285961466]
  We consider the recently developed and theoretically rigorous reverse experience replay (RER) We show via experiments that this has a better performance than techniques like prioritized experience replay (PER) on various tasks.
  arXiv  Detail & Related papers  (2022-06-07T10:42:02Z)
• Convergence Results For Q-Learning With Experience Replay [51.11953997546418]
  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 iterations of replay. We also provide theoretical evidence showing when we might expect this to strictly improve performance, by introducing and analyzing a simple class of MDPs.
  arXiv  Detail & Related papers  (2021-12-08T10:22:49Z)
• Variance Reduction based Experience Replay for Policy Optimization [3.0790370651488983]
  Variance Reduction Experience Replay (VRER) is a framework for the selective reuse of relevant samples to improve policy gradient estimation. VRER forms the foundation of our sample efficient off-policy learning algorithm known as Policy Gradient with VRER.
  arXiv  Detail & Related papers  (2021-10-17T19:28:45Z)
• Taylor Expansion of Discount Factors [56.46324239692532]
  In practical reinforcement learning (RL), the discount factor used for estimating value functions often differs from that used for defining the evaluation objective. In this work, we study the effect that this discrepancy of discount factors has during learning, and discover a family of objectives that interpolate value functions of two distinct discount factors.
  arXiv  Detail & Related papers  (2021-06-11T05:02:17Z)
• Stratified Experience Replay: Correcting Multiplicity Bias in Off-Policy Reinforcement Learning [17.3794999533024]
  We show that deep RL appears to struggle in the presence of extraneous data. Recent works have shown that the performance of Deep Q-Network (DQN) degrades when its replay memory becomes too large. We re-examine the motivation for sampling uniformly over a replay memory, and find that it may be flawed when using function approximation.
  arXiv  Detail & Related papers  (2021-02-22T19:29:18Z)
• Revisiting Fundamentals of Experience Replay [91.24213515992595]
  We present a systematic and extensive analysis of experience replay in Q-learning methods. We focus on two fundamental properties: the replay capacity and the ratio of learning updates to experience collected.
  arXiv  Detail & Related papers  (2020-07-13T21:22:17Z)
• Experience Replay with Likelihood-free Importance Weights [123.52005591531194]
  We propose to reweight experiences based on their likelihood under the stationary distribution of the current policy. We apply the proposed approach empirically on two competitive methods, Soft Actor Critic (SAC) and Twin Delayed Deep Deterministic policy gradient (TD3)
  arXiv  Detail & Related papers  (2020-06-23T17:17:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.