On the Variance of Temporal Difference Learning and its Reduction Using Control Variates

This paper investigates the variance properties of temporal difference (TD) learning and explores how to reduce this variance using control variates. While TD learning is a cornerstone of reinforcement learning, its variance reduction mechanisms—often attributed to bootstrapping—are complex and not fully understood in the online regime. The authors seek to provide a rigorous theoretical framework for why TD performs well and how it compares to Monte Carlo (MC) methods and more advanced techniques like Direct Advantage Estimation (DAE).

The authors analyze TD learning within a phased (synchronous) setting, which allows them to isolate the effects of bootstrapping from the complexities of asynchronous updates. They derive a recurrence relation for the variance of multi-step TD and compare it to MC estimators. Furthermore, they frame DAE—a method that simultaneously estimates value and advantage functions—as a form of regression-adjusted control variate. By treating the advantage function as a control variate, they demonstrate that DAE can effectively explain away portions of the variance that standard TD cannot.

The study establishes two primary results. First, it proves that the asymptotic variance of multi-step TD is bounded above by that of MC methods, confirming that TD is generally more stable. It also shows that shorter horizon updates incur less variance for a fixed number of samples. Second, the authors demonstrate that DAE is a form of control variate regression. Because the advantage function serves as an optimal control variate, DAE achieves a strictly tighter variance bound than standard TD in the large-sample limit. These findings provide a theoretical justification for the empirical performance gains observed in previous applications of DAE.