Variance Reduction Based Experience Replay for Policy Optimization
Organizations: Department of Mechanical and Industrial Engineering, Northeastern University, Boston, USA · Department of Statistics and Actuarial Science, University of Waterloo, Waterloo, Canada
Abstract
Effective reinforcement learning (RL) for complex stochastic systems requires leveraging historical data to improve sample efficiency and accelerate policy optimization. However, classical experience replay treats all past observations uniformly and fails to account for their varying contributions to learning. To address this limitation, we propose Variance Reduction Experience Replay (VRER), a principled framework that selectively reuses informative samples to reduce the variance of policy gradient estimates. VRER is algorithm-agnostic and can be integrated with existing policy optimization methods, yielding the sample-efficient off-policy algorithm, Policy Gradient with VRER (PG-VRER). To provide rigorous theoretical guarantees, we develop a novel analysis framework for experience replay that explicitly accounts for dependencies induced by Markovian dynamics and behavior-policy interactions. Using this framework, we establish finite-time convergence guarantees for PG-VRER and characterize a fundamental bias-variance trade-off: reusing older samples reduces gradient variance but may introduce greater estimation bias. Extensive experiments show that VRER consistently accelerates learning and outperforms state-of-the-art policy optimization algorithms
Figures & tables
| CartPole | Hopper | Inverted Pendulum | Lunar Lander | |
|---|---|---|---|---|
| PPO | 327.84 ± 8.97 | 135.72 ± 7.92 | 977.48 ± 10.02 | 224.43 ± 8.08 |
| PPO-VRER | 468.19 ± 5.06 | 168.96 ± 12.49 | 996.35 ± 1.41 | 255.57 ± 3.44 |
| TRPO | 489.34 ± 2.62 | 700.52 ± 11.64 | 916.39 ± 11.55 | 139.17 ± 4.22 |
| TRPO-VRER | 494.09 ± 3.14 | 864.12 ± 9.79 | 962.76 ± 3.63 | 184.16 ± 9.26 |
| A2C | 197.4 ± 3.35 | 47.75 ± 0.62 | 158.86 ± 3.71 | -221.99 ± 11.25 |
| A2C-VRER | 411.46 ± 6.4 | 80.58 ± 0.67 | 737.22 ± 19.62 | -186.53 ± 4.88 |
| Selection Constant ( ) | PPO - (PPO-VRER) | TRPO - (TRPO-VRER) | A2C - (A2C-VRER) |
|---|---|---|---|
| 1.001 | 6.94 ± 6.30 | -5.58 ± 11.33 | 1.09 ± 0.30 |
| 1.02 | 16.07 ± 2.60 | 2.23 ± 6.62 | 1.51 ± 0.18 |
| 1.04 | 24.42 ± 3.51 | 3.62 ± 4.68 | 1.37 ± 0.20 |
| 1.06 | 25.32 ± 3.39 | 4.81 ± 2.10 | 1.47 ± 0.16 |
| 1.08 | 24.01 ± 3.44 | 3.14 ± 6.45 | 1.45 ± 0.12 |
| 1.10 | 23.80 ± 4.07 | 5.84 ± 5.35 | 1.45 ± 0.17 |
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
| Parameter | CartPole | Hopper | Inv. Pendulum | Lunar Lander |
|---|---|---|---|---|
| A2C | ||||
| Learning rate | 0.0003 | 0.0003 | 0.0003 | 0.0003 |
| Num-envs | 24 | 24 | 64 | 48 |
| n-steps | 16 | 16 | 16 | 16 |
| Clip norm | 0.2 | 0.2 | 0.2 | 0.2 |
| Entropy coef | 0.01 | 0.01 | 0.01 | 0.01 |
| Selection Constant | Reuse Ratio | Average Reward of One Million Steps | ||||
|---|---|---|---|---|---|---|
| PPO-VRER | TRPO-VRER | A2C-VRER | PPO-VRER | TRPO-VRER | A2C-VRER | |
| 1.001 | 0.00 ± 0.00 | 0.14 ± 0.01 | 0.16 ± 0.00 | 372.65 ± 17.98 | 434.93 ± 14.57 | 100.20 ± 3.51 |
| 1.02 | 0.34 ± 0.02 | 0.10 ± 0.00 | 0.13 ± 0.02 | 443.03 ± 5.52 | 449.11 ± 5.66 | 99.64 ± 5.01 |
| 1.04 | 0.86 ± 0.01 | 0.12 ± 0.01 | 0.22 ± 0.02 | 432.77 ± 11.13 | 443.40 ± 4.92 | 106.07 ± 6.82 |
| 1.06 | 0.94 ± 0.01 | 0.14 ± 0.02 | 0.24 ± 0.02 | 425.5 ± 8.44 | 444.52 ± 6.13 | 107.98 ± 6.66 |
| 1.08 | 0.95 ± 0.02 | 0.15 ± 0.02 | 0.28 ± 0.02 | 403.78 ± 20.90 | 429.76 ± 17.28 | 123.58 ± 9.34 |
Experience Replay
Experience replay stores and reuses past examples or trajectories to improve learning efficiency, stability, and retention across tasks.
See all 48 papers