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

• URL: http://arxiv.org/abs/2606.20357v1
• Date: Thu, 18 Jun 2026 15:20:10 GMT
• Title: On the Variance of Temporal Difference Learning and its Reduction Using Control Variates
• Abstract summary: We show that one of the mechanisms behind variance reduction is by effectively aggregating over a larger number of independent trajectories.<n>We numerically illustrate the behaviors of Monte Carlo estimators with carefully designed environments.
• Score: 54.916555668983726
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We analyze the variance of temporal difference (TD) learning using the phased setting with tabular representation, and show that one of the mechanisms behind its ability to reduce variance is by effectively aggregating over a larger number of independent trajectories. Based on this insight, we demonstrate that (1) the variance of TD is asymptotically bounded from above by Monte Carlo (MC) estimators, and (2) shorter horizon updates incurs less variance for a fixed number of samples. Beyond TD, we show that Direct Advantage Estimation (DAE), a method for estimating the advantage function, can be seen as a type of regression-adjusted control variate, which achieves a tighter bound on the variance compared to TD in the large-sample limit. Finally, we numerically illustrate the behaviors of these estimators with carefully designed environments.

Related papers

• Causal vs. Anticausal merging of predictors [57.26526031579287]
  We study the differences arising from merging predictors in the causal and anticausal directions using the same data.<n>We use Causal Maximum Entropy (CMAXENT) as inductive bias to merge the predictors.
  arXiv  Detail & Related papers  (2025-01-14T20:38:15Z)
• STATE: A Robust ATE Estimator of Heavy-Tailed Metrics for Variance Reduction in Online Controlled Experiments [22.32661807469984]
  We develop a novel framework that integrates the Student's t-distribution with machine learning tools to fit heavy-tailed metrics. By adopting a variational EM method to optimize the loglikehood function, we can infer a robust solution that greatly eliminates the negative impact of outliers. Both simulations on synthetic data and long-term empirical results on Meituan experiment platform demonstrate the effectiveness of our method.
  arXiv  Detail & Related papers  (2024-07-23T09:35:59Z)
• TIC-TAC: A Framework for Improved Covariance Estimation in Deep Heteroscedastic Regression [109.69084997173196]
  Deepscedastic regression involves jointly optimizing the mean and covariance of the predicted distribution using the negative log-likelihood. Recent works show that this may result in sub-optimal convergence due to the challenges associated with covariance estimation. We study two questions: (1) Does the predicted covariance truly capture the randomness of the predicted mean? Our results show that not only does TIC accurately learn the covariance, it additionally facilitates an improved convergence of the negative log-likelihood.
  arXiv  Detail & Related papers  (2023-10-29T09:54:03Z)
• On the Statistical Benefits of Temporal Difference Learning [6.408072565019087]
  Given a dataset on actions and resulting long-term rewards, a direct estimation approach fits value functions. We show that an intuitive inverse trajectory pooling coefficient completely characterizes the percent reduction in mean-squared error of value estimates. We prove that there can be dramatic improvements in estimates of the difference in value-to-go for two states.
  arXiv  Detail & Related papers  (2023-01-30T21:02:25Z)
• Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation [44.27439128304058]
  We study the finite-time behaviour of the popular temporal difference (TD) learning algorithm when combined with tail-averaging. We derive finite time bounds on the parameter error of the tail-averaged TD iterate under a step-size choice.
  arXiv  Detail & Related papers  (2022-10-12T04:37:54Z)
• Double Control Variates for Gradient Estimation in Discrete Latent Variable Models [32.33171301923846]
  We introduce a variance reduction technique for score function estimators. We show that our estimator can have lower variance compared to other state-of-the-art estimators.
  arXiv  Detail & Related papers  (2021-11-09T18:02:42Z)
• Regularizing Variational Autoencoder with Diversity and Uncertainty Awareness [61.827054365139645]
  Variational Autoencoder (VAE) approximates the posterior of latent variables based on amortized variational inference. We propose an alternative model, DU-VAE, for learning a more Diverse and less Uncertain latent space.
  arXiv  Detail & Related papers  (2021-10-24T07:58:13Z)
• VarGrad: A Low-Variance Gradient Estimator for Variational Inference [9.108412698936105]
  We show that VarGrad offers a favourable variance versus trade-off compared to other state-of-the-art estimators on a discrete VAE.
  arXiv  Detail & Related papers  (2020-10-20T16:46:01Z)
• Estimating Gradients for Discrete Random Variables by Sampling without Replacement [93.09326095997336]
  We derive an unbiased estimator for expectations over discrete random variables based on sampling without replacement. We show that our estimator can be derived as the Rao-Blackwellization of three different estimators.
  arXiv  Detail & Related papers  (2020-02-14T14:15:18Z)
• Reanalysis of Variance Reduced Temporal Difference Learning [57.150444843282]
  A variance reduced TD (VRTD) algorithm was proposed by Korda and La, which applies the variance reduction technique directly to the online TD learning with Markovian samples. We show that VRTD is guaranteed to converge to a neighborhood of the fixed-point solution of TD at a linear convergence rate.
  arXiv  Detail & Related papers  (2020-01-07T05:32:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.