Research map / Reinforcement learning / Policy gradient and actor-critic
Averaging $n$-step Returns Reduces Variance in Reinforcement Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that compound returns (weighted averages of n-step returns) with the same contraction modulus as an n-step return have strictly lower variance, and proposes Pilar, a two-bootstrap piecewise lambda-return that is cheap for minibatch replay and improves DQN and PPO sample efficiency.
Problem
Multistep returns such as n-step and lambda-returns speed up value learning, but their variance grows with length, and lambda-returns are costly to implement with minibatched experience replay in deep RL.
Approach
Derives a variance model for arbitrary compound returns under TD-error correlation assumptions, proves any compound return with the same effective n-step (contraction modulus or center of mass) has lower variance than the n-step return, and approximates the lambda-return with a two-bootstrap average (Pilar) whose TD-error weights are piecewise-constant.
Key results
- Pilars outperform n-step returns in 1 of 5 MinAtar games for n=3 and 3 of 5 games for n=5 (DQN).
- For PPO, lambda-returns significantly improve sample efficiency over n-step returns in seven of nine cases across three MuJoCo environments.
- In the random walk, lambda-returns with the same center of mass as n-step returns attain lower RMS error, with the gap widening as step size approaches 1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Average two n-step returns with Pilar instead of using an n-step return | DQN · MinAtar, n=3 (five games) | game score: 1 in 5 games (20%) | Mixed |
| Average two n-step returns with Pilar instead of using an n-step return | DQN · MinAtar, n=5 (five games) | game score: 3 in 5 games (60%) | Mixed |
| Use a lambda-return instead of an n-step return with the same contraction modulus | PPO · Half Cheetah, Hopper, and Walker 2D | sample efficiency: seven out of nine of the cases | Helped |
| Use a lambda-return instead of an n-step return with equal center of mass | TD learning · 19-state random walk | RMS value error | Helped |
| Use a lambda-return instead of an n-step return with equal center of mass | TD learning · 19-state random walk, small step sizes | learning rate | No clear effect |
| Use a lambda-return instead of an n-step return with equal contraction modulus | TD learning · Theoretical variance analysis | return variance | Helped |
Surprising findings
- Seaquest was the only MinAtar game where Pilar did not significantly outperform n-step returns.
Limitations
- Theory of linear TD does not extend automatically to nonlinear function approximators used in deep RL.
- Experiments do not isolate variance reduction as the cause of performance gains.
- Off-policy corrections are ignored in the deep RL experiments.
Experimental setup
Datasets: MinAtar MuJoCo random walk (19-state) gridworlds
Benchmarks: MinAtar Asterix MinAtar Breakout MinAtar Freeway MinAtar Seaquest MinAtar Space Invaders MuJoCo Half Cheetah MuJoCo Hopper MuJoCo Walker2D 19-state random walk
Metrics: area under learning curve 100-episode moving average return RMS value error
Baselines: n-step returns lambda-return PPO with n-step returns DQN with n-step returns
Builds on: TD(lambda) DQN PPO Generalized Advantage Estimation Peng's Q(lambda)
Closest papers by meaning
- Policy Evaluation for Variance in Average Reward Reinforcement Learning (ICML 2024 · similarity 0.87)
- Behaviour Policy Optimization: Provably Lower Variance Return Estimates for Off-Policy Reinforcement Learning (AAAI 2026 · similarity 0.86)
- Beyond Expected Return: Accounting for Policy Reproducibility When Evaluating Reinforcement Learning Algorithms (AAAI 2024 · similarity 0.86)
- Variance-Optimal State Resampling for Reinforcement Learning with Verifiable Rewards (NeurIPS 2026 · similarity 0.86)
- ContraDiff: Planning Towards High Return States via Contrastive Learning (ICLR 2025 · similarity 0.85)
- Exploiting the Replay Memory Before Exploring the Environment: Enhancing Reinforcement Learning Through Empirical MDP Iteration (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.