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

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

Problem Statement
Policy evaluation is a fundamental challenge in reinforcement learning (RL). While Monte Carlo (MC) methods provide unbiased estimates of value functions, they suffer from high variance due to the need to average over full trajectories. Conversely, Temporal Difference (TD) learning utilizes bootstrapping (updating estimates based on other estimates) to reduce variance, but this introduces bias. The precise mechanism by which TD reduces variance, particularly in the online regime, and how it compares asymptotically to MC, has remained a subject of nuanced debate. Furthermore, while Direct Advantage Estimation (DAE) has shown empirical success in deep RL, its theoretical justification regarding variance reduction has been limited to convergence properties rather than a rigorous analysis of its variance bounds compared to standard TD.

Methodology
The authors analyze the variance of multi-step TD learning within a phased (synchronous) setting using tabular representations. This setting abstracts away complexities associated with asynchronous updates and stochastic approximations, allowing for a clearer isolation of variance mechanisms.

1. Variance Decomposition: The paper derives a recurrence relation for the variance of multi-step TD updates. By expanding this recursion, the authors compare the asymptotic variance of TD against MC estimators.
2. Control Variate Framework: The authors frame the advantage function ($A^\pi$) as a control variate for policy evaluation. They utilize the concept of regression-adjusted control variates, where the advantage function is estimated simultaneously with the value function to minimize the variance of the return estimator.
3. Direct Advantage Estimation (DAE): The paper analyzes DAE (Pan et al., 2022) as a constrained least-squares problem. By treating the advantage function estimates as nuisance parameters in a regression framework, the authors reformulate the DAE update rule to explicitly show its structure as a regression-adjusted control variate.
4. Empirical Validation: Theoretical claims are illustrated using carefully designed Chain MDP environments. These experiments vary the degree of stochasticity (reward masking, sticky transitions) and state-action coverage to test the asymptotic behaviors of MC, TD, and DAE under different conditions.

Key Contributions

1. Asymptotic Variance Bound of TD: The authors prove that in both phased (synchronous) and IID (asynchronous) settings, the asymptotic variance of multi-step TD learning is upper-bounded by that of Monte Carlo methods.

   • Mechanism: The paper identifies that TD reduces variance not merely by bias-variance tradeoff, but by effectively aggregating over a larger pool of independent trajectories. When bootstrapping states are diverse and weakly correlated, averaging their values reduces variance. Conversely, if bootstrapping states are identical (highly correlated), TD's variance reduction capability diminishes, and it asymptotically approaches the variance of MC.
   • Horizon Effect: For a fixed number of samples, shorter horizon updates (smaller $k$) incur less variance than single long-horizon updates.

2. DAE as Regression-Adjusted Control Variate: The paper demonstrates that the advantage function can serve as a control variate for MC estimators. It further establishes that Direct Advantage Estimation (DAE) is a form of regression-adjusted control variate that simultaneously estimates value and advantage functions.

   • Variance Bound: In the large-sample limit, DAE achieves a tighter upper bound on variance compared to standard TD. Specifically, the variance of DAE is bounded by the variance of an MC estimator adjusted by the advantage function (MC-A), which is itself lower than or equal to the variance of standard MC.

3. Empirical Illustrations:

   • In deterministic environments where bootstrapping states are identical, TD fails to reduce variance relative to MC, confirming the theoretical dependency on trajectory diversity.
   • In stochastic transition environments, TD exhibits the expected bias-variance tradeoff, and DAE converges rapidly (similar to Bellman iterations) because the advantage function fully explains the variance.
   • In reward masking scenarios (where reward variance cannot be explained by actions), DAE's advantage estimates cannot fully eliminate variance, resulting in a slight asymptotic gap compared to Bellman iterations, yet it still outperforms TD.
   • In low-coverage settings (undersampled action spaces), DAE may suffer from small-sample bias due to unreliable advantage estimates, yet it still converges to a lower Mean Squared Error (MSE) than TD, suggesting robustness even with imperfect control variates.

Results and Significance
The paper provides a rigorous theoretical explanation for the variance reduction capabilities of bootstrapping, moving beyond the intuitive "bias-variance tradeoff" to a mechanism based on trajectory aggregation. It clarifies that TD's superiority over MC is conditional on the diversity of the bootstrapping states.

Furthermore, the work offers a theoretical foundation for DAE, explaining its empirical success in deep RL by framing it as a control variate method. The results suggest that leveraging the advantage function as a control variate can theoretically achieve tighter variance bounds than standard TD.

Limitations and Scope
The authors note several limitations:

• The theoretical results are derived for phased and IID settings; generalization to realistic Markovian sampling schemes remains an open question.
• The analysis focuses on variance reduction; DAE incurs additional computational costs (solving least-squares) and storage requirements.
• The tight variance bounds for DAE rely on a large-sample approximation where control variate coefficients are optimal. While empirical results suggest benefits in small-sample regimes, a rigorous analysis of small-sample bias in DAE is left for future work.

The paper concludes that understanding the aggregation of independent trajectories is central to TD's variance reduction, and that control variate regression (via DAE) offers a principled path to further reduce variance in policy evaluation.