Compound Returns Reduce Variance in Reinforcement Learning

TL;DR — We prove that compound returns (averages of n-step returns) reduce variance without increasing bias. We propose PiLaR, an efficient approximation of the lambda-return, and show that it improves the sample efficiency of n-step DQN.

Abstract

Multistep returns such as $n$-step returns are commonly used to improve the sample efficiency of deep reinforcement learning (RL). Variance becomes the limiting factor in the length of the returns; looking too far into the future increases uncertainty and reverses the benefit of multistep learning. In our work, we study the ability of compound returns---weighted averages of $n$-step returns---to reduce variance. The $\lambda$-return, used by TD($\lambda$), is the most well-known compound return. We prove for the first time that any compound return with the same contraction rate as a given $n$-step return has strictly lower variance when experiences are not perfectly correlated. Because the $\lambda$-return is expensive to implement in deep RL, we also introduce an approximation called Piecewise $\lambda$-Return (PiLaR), formed by averaging two $n$-step returns, that offers similar variance reduction while being efficient to implement with minibatched experience replay. We conduct experiments showing PiLaRs can train Deep Q-Networks faster than $n$-step returns with little additional computational cost.