📊 statistics

Variance Reduction Based Experience Replay for Policy Optimization

This paper proposes Variance Reduction Experience Replay (VRER), a principled, algorithm-agnostic framework that selectively reuses informative historical samples to reduce policy gradient variance, offering rigorous finite-time convergence guarantees and demonstrating superior sample efficiency over state-of-the-art methods.

Original authors: Hua Zheng, Wei Xie, M. Ben Feng, Keilung Choy

Published 2026-08-14

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Hua Zheng, Wei Xie, M. Ben Feng, Keilung Choy

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to walk, play chess, or even balance a pole on a cart. In the world of science, this is called Reinforcement Learning (RL). It's a bit like training a dog: the robot tries something, gets a "treat" (a reward) if it does well, or a "scolding" (a penalty) if it messes up. Over time, it learns which actions lead to the best treats. But here's the catch: learning by trial and error is incredibly slow and expensive. If the robot is a real car or a medical device, you can't afford to crash it a million times just to learn a lesson.

To speed things up, scientists use a trick called Experience Replay. Instead of forgetting every mistake and success the moment it happens, the robot keeps a "diary" of its past adventures. Later, it can flip through this diary to learn from old experiences without having to go out and do them again. However, there's a problem with the old way of using this diary: it treats every single memory as equally important. It's like studying for a test by reading the entire history of the universe, including the boring parts, instead of focusing on the chapters that actually explain the math you need. This paper tackles that inefficiency, asking: How can we pick the absolute best memories to study, so the robot learns faster and doesn't get confused by old, outdated advice?

The Problem: A Diary Full of Noise

In the paper, the authors explain that when a robot learns, it generates a stream of data. Sometimes it tries a new strategy (a "policy"), and sometimes it sticks to an old one. The "Experience Replay" system stores these moments. But if you just grab random pages from the diary, you might end up studying a strategy the robot abandoned years ago. This is like trying to learn the latest video game moves by reading a strategy guide from 2010; the game has changed, and the old advice might actually hurt your score.

Furthermore, the math behind learning (called "policy gradients") can be very "noisy." Imagine trying to hear a whisper in a storm. The robot is trying to figure out the perfect direction to move, but the data is so jumpy and chaotic that it's hard to tell which way is truly better. The more noise there is, the slower the learning.

The Solution: The "Variance Reduction" Filter

The authors propose a new method called Variance Reduction Experience Replay (VRER). Think of VRER as a super-smart librarian for the robot's diary. Instead of letting the robot read every book, the librarian looks at the current lesson the robot is trying to learn and asks: "Which of these old memories will help the most without confusing the robot?"

The key idea is variance reduction. In plain English, "variance" is just a fancy word for "how much the data jumps around." If the data jumps a lot, the robot gets confused. VRER selectively picks only the memories that are stable and relevant to the current lesson. It filters out the noisy, chaotic, or outdated pages.

The paper introduces a clever way to do this. It doesn't just look at how old a memory is; it calculates how much that specific memory would reduce the "noise" in the robot's learning process. If a memory is too old or too different from what the robot is doing now, the librarian says, "Nope, that's too risky," and skips it. If a memory is just right, it gets a high priority.

How It Works: The "KL" Shortcut

To make this selection fast, the authors developed a mathematical shortcut. They realized that if the robot's current strategy is very similar to an old strategy, the old memory is probably safe to use. They use a measure called KL divergence (which is just a way of measuring the "distance" between two strategies) to decide.

Imagine you are learning to ride a bike. If you are currently wearing a helmet and riding on a flat path, a memory of you riding a bike with training wheels on a flat path is very useful. But a memory of you trying to ride a unicycle on a tightrope is probably too different and might confuse you. VRER checks this "distance" automatically. If the distance is small, it reuses the memory. If it's too big, it leaves it alone. This keeps the learning process smooth and steady.

What They Found: Faster, Smoother Learning

The authors tested their new method (which they call PG-VRER) on several classic robot challenges, like balancing a pole (CartPole) and making a robot hop (Hopper). They compared it against the standard ways of learning, using popular algorithms like PPO, TRPO, and A2C.

The results were clear: VRER made the robots learn faster and more stably.

Speed: The robots reached their goals in fewer steps. For example, on the "CartPole" task, the A2C algorithm with VRER improved its score by over 100% compared to the version without it.
Stability: The learning curves were much smoother. Without VRER, the robots' performance would jump up and down wildly. With VRER, the progress was steady, like a calm river instead of a choppy sea.
Variance: The team measured the "noise" in the learning process and found that VRER significantly reduced it. The robots were less confused and more confident in their decisions.

The Trade-Off: Old vs. New

The paper also highlights a crucial balance, or trade-off. If you reuse too many old memories, you might introduce "bias"—basically, teaching the robot with outdated information that no longer applies. If you reuse too few, you miss out on valuable lessons and the learning stays slow and noisy.

The authors found that VRER automatically finds the sweet spot. It reuses enough old data to smooth out the noise but stops before it starts using "stale" advice that would throw the robot off course. They showed that if you force the robot to use too much old data (by making the "diary" too big or the selection rules too loose), the performance actually gets worse because the robot gets confused by the mismatch between its current self and its past self.

The Bottom Line

This paper doesn't just say "reusing data is good." It provides a rigorous, mathematically proven way to decide which data to reuse. It shows that by being selective and focusing on reducing the "noise" in the learning signal, we can teach robots much more efficiently. The method is flexible enough to work with different learning algorithms and doesn't require changing the core rules of how the robot learns.

In short, VRER is like giving the robot a pair of noise-canceling headphones and a highlighter. It blocks out the confusing static of the past and highlights only the most useful lessons, allowing the robot to learn complex skills faster and with fewer mistakes. The authors suggest that this approach could be a game-changer for any situation where learning is expensive or data is scarce, from self-driving cars to medical treatments, though they focus their proof on these simulated robot tasks.

Technical Summary: Variance Reduction Based Experience Replay for Policy Optimization

Problem Statement

Reinforcement learning (RL) for complex stochastic systems often suffers from low sample efficiency, particularly when historical data is scarce or expensive to generate (e.g., in healthcare or biopharmaceutical manufacturing). While experience replay (ER) and off-policy methods aim to improve sample efficiency by reusing past data, classical approaches treat all historical observations uniformly. This uniformity fails to account for the varying contributions of samples to learning.

Furthermore, existing variance-reduction techniques, such as importance sampling (IS), often suffer from high variance when the behavior policy (data collection) and target policy (optimization) differ significantly. Additionally, the theoretical understanding of experience replay remains limited, specifically regarding how Markovian dynamics (sample dependence), behavior-policy interdependencies, buffer sizes, and policy age affect the bias-variance trade-off in policy gradient estimation. Current methods often lack rigorous finite-time convergence guarantees that explicitly account for these dependencies.

Methodology

The authors propose Variance Reduction Experience Replay (VRER), a principled framework designed to selectively reuse informative historical samples to reduce the variance of policy gradient estimates without introducing excessive bias.

Core Framework: PG-VRER

VRER is algorithm-agnostic and integrates with existing policy optimization methods (e.g., PPO, TRPO, A2C) to form the Policy Gradient with VRER (PG-VRER) algorithm. The methodology operates as follows:

Buffer Management: A First-In-First-Out (FIFO) buffer stores historical policies ( $\theta_i$ ) and their associated trajectory segments ( $T_i$ ).
Selection Rule: Instead of reusing all data or data based solely on recency, VRER employs a selection criterion to identify a subset of historical policies ( $U_k$ $U_{k}$ ) for reuse at iteration $k$ $k$ .
- Variance-Based Selection (Rule 1): The primary criterion selects historical samples where the variance of the individual Likelihood Ratio (LR) or Clipped Likelihood Ratio (CLR) gradient estimator is bounded by a constant factor $c$ times the variance of the current on-policy gradient estimator.
- KL-Based Approximation (Rule 2): To ensure computational efficiency, the authors derive a local second-order approximation. This rule replaces the expensive bootstrap variance estimation with a threshold based on the Kullback-Leibler (KL) divergence between the current target policy and the historical behavior policy. This approximation leverages statistics (first and second moments) already maintained by optimizers like Adam.
Gradient Estimation: The selected historical samples are reweighted using likelihood ratios (or clipped ratios) to correct for distribution mismatch. The final gradient estimate is an average of the current on-policy samples and the selected, reweighted historical samples.
Bias-Variance Control: The framework explicitly manages the trade-off: reusing older samples reduces gradient variance but introduces estimation bias due to policy lag and state-distribution mismatch. The selection rules aim to maximize variance reduction while keeping bias within acceptable bounds.

Theoretical Analysis

The paper develops a novel analysis framework for experience replay that explicitly accounts for:

Markovian Noise: Sample dependencies induced by the Markovian nature of the environment.
Behavior-Policy Interdependence: Dependencies arising from the sequence of evolving policies used to collect data.
Finite-Time Convergence: The authors establish finite-time convergence guarantees for PG-VRER. They characterize the convergence rate as a function of the learning rate, mixing rate of the environment, buffer size, and the correlation between reused samples.

Key Contributions

VRER Framework: A new, algorithm-agnostic framework for policy gradient optimization that accelerates learning by selectively reusing historical samples based on a variance-reduction criterion.
Novel Theoretical Framework: A rigorous finite-time convergence analysis for experience replay that explicitly models sample dependencies (Markovian noise) and behavior-policy interdependencies. This analysis quantifies how buffer size, policy age, and mixing rates influence the fundamental bias-variance trade-off.
Convergence Guarantees: Establishment of finite-time convergence guarantees for the PG-VRER algorithm, demonstrating that the method converges under specific conditions regarding buffer scaling and mixing rates.
Practical Approximation: The derivation of a low-cost, KL-based selection rule that approximates the exact variance-based selection, making the method scalable for online implementation without requiring expensive bootstrap variance estimation.

Experimental Results

Extensive empirical studies were conducted on benchmark control tasks (CartPole, Hopper, Inverted Pendulum, Lunar Lander) using three state-of-the-art algorithms: PPO, TRPO, and A2C.

Performance Improvement: VRER consistently accelerated learning and improved final performance across all tested algorithms and tasks.
- A2C: Showed remarkable enhancements in convergence speed and stability, with average reward improvements up to 364% on the Inverted Pendulum task.
- PPO: Demonstrated enhanced stability and accelerated convergence.
- TRPO: Consistently outperformed standard TRPO with smoother learning dynamics.
Variance Reduction: Empirical diagnostics confirmed that VRER significantly reduces the relative variance of policy gradient estimates compared to standard on-policy methods.
Sensitivity Analysis: The method proved robust to variations in buffer size ( $B$ ) and the selection constant ( $c$ ), though optimal settings varied slightly by algorithm (e.g., A2C benefited from larger buffers, while PPO preferred moderate reuse).
Approximation Validity: The KL-based selection rule (Rule 2) was shown to produce rankings and reuse sets highly correlated with the exact variance-based rule (Rule 1) after the initial training transient, validating its use as a practical surrogate.

Significance and Claims

The paper claims that VRER addresses a critical gap in reinforcement learning by providing a controllable bias-variance replay mechanism. Unlike previous methods that either ignore the variance of historical samples or rely on heuristics, VRER provides a principled approach to sample selection.

The authors emphasize that their work offers the first rigorous theoretical understanding of how experience replay interacts with Markovian dynamics and policy updates to affect convergence. They argue that VRER is not merely a heuristic but a method grounded in finite-time convergence theory that explicitly balances the trade-off between reusing data to reduce variance and avoiding stale data that introduces bias.

The significance of the work lies in its ability to improve sample efficiency in complex stochastic systems without requiring structural changes to existing policy optimization algorithms, making it a versatile tool for accelerating RL training in data-scarce or high-cost environments. The authors modestly note that while VRER reduces variance, aggressive reuse can increase bias, and future research should focus on strategies that directly optimize the mean squared error of gradient estimators.