Temporal difference learning adapts to incomplete coverage: an oracle inequality over subgraphs

Wenlong Mou; Jian Qian

cs.LGNov 14, 2024

Temporal difference learning adapts to incomplete coverage: an oracle inequality over subgraphs

Authors: Wenlong Mou, Jian Qian

Organizations: Department of Statistical Sciences, University of Toronto · Department of EECS, Massachusetts Institute of Technology

Abstract

Temporal difference (TD) and Monte Carlo (MC) are two fundamental principles for value function estimation in reinforcement learning. TD is asymptotically efficient for value estimation, whereas MC requires only adequate target visitation. We show that these advantages are automatically combined by ordinary TD in the tabular setting. We identify the subgraph Bellman variance, arising from bootstrapping within a subgraph and rollouts outside it, as a fundamental quantity connecting the MC and efficient TD benchmarks. With independent trajectories, we prove a non-asymptotic oracle inequality: the mean squared error of full TD is bounded by this variance divided by the sample size for every sufficiently covered subgraph containing the target, up to a higher-order remainder whose occupancy dependence is confined to that subgraph. No subgraph is supplied to the algorithm. TD thus adapts without selecting a subgraph or requiring global coverage. A finite-sample minimax lower bound shows that the asymptotic variance of TD need not be attainable before rare states are adequately observed. Experimental studies examine the transition between these variance scales and its dependence on visitation structure.

Figures & tables

Figure 1: A changing finite-sample variance scale on a random graph with

10^{5}

states. Left: empirical

n\,\mathrm{MSE}

for TD and first-visit MC, their asymptotic variances, and the subgraph Bellman variance for

G_{n}^{(2)}

(defined in Subsection 3.2 ). Bands show

1.96

Monte Carlo standard errors on either side of the empirical means, using

4000

independent datasets at each sample size. All variance benchmarks are computed numerically from the population model. Right: the fraction of all states observed, averaged over datasets, and the expected number of visits to

G_{n}^{(2)}

divided by the expected total number of visits for a trajectory starting at the target. The latter is computed from the population model and counts repeated visits and the initial visit. TD’s effective variance decreases as the comparison subgraph retains more of the target’s future.

Model	States $d$	Graph or queue parameters	Initial distribution	Stop probability
Scale-free	$10^{3}$ , $10^{4}$ , $10^{5}$	Barabási–Albert; attachment $3$	Uniform	$0.1$
Small-world	$10^{4}$	Connected Watts–Strogatz; initial degree $6$ , rewiring $0.1$	Uniform	$0.1$
Lattice	$10^{4}$	$100\times 100$ grid; nearest neighbors, no wraparound	Uniform on a $10\times 10$ corner block	$0.01$
Tandem queue	$1681$	Two buffers of size $40$ ; arrival $0.3$ , service $0.35$ per station	Uniform	$0.01$

Table 1: MRP families used in the experiments. Termination occurs independently after each reward; queue event probabilities are conditional on survival.

Figure 2: State-space size and the approach to the TD asymptotic variance. Each panel averages five Barabási–Albert instances, with the most visited state as target and

1000

datasets per sample size and instance. Solid curves show mean instance-normalized errors for TD and first-visit MC; the dashed curve shows the mean population subgraph variance ratio for

c=2

. Both coordinates are averaged at common doubling stages. Shading gives pointwise

95\%

Monte Carlo confidence intervals conditional on the fixed instances (Appendix D ). The dotted line is the TD benchmark

1

. Both axes are logarithmic.

Figure 3: Finite-sample errors under four visitation structures. The target is the most visited state. The normalization, curve encodings, and

1000

-dataset replication protocol are the same as in Figure 2 . Each method has one mean curve with a pointwise

95\%

Monte Carlo confidence band. The lattice instances share a transition kernel and differ in reward means; the queue has one instance. A long transition occurs for the scale-free targets, while the other models approach the TD benchmark earlier.

Model	Proper subgraph / total	Median	Range
Scale-free, $d=10^{5}$	$6/8$	$1.4414$	$[1.0792,\,1.5585]$
Scale-free, $d=10^{4}$	$13/24$	$1.4204$	$[0.9999,\,1.5660]$
Small-world	$0/15$	$\widehat{V}_{G}=\widehat{V}_{\rm TD}$
Lattice	$15/15$	$1.0000$	$[0.9999,\,1.0004]$
Tandem queue	$0/5$	$\widehat{V}_{G}=\widehat{V}_{\rm TD}$

Table 2: MSE of the explicit subgraph estimator relative to full TD, using

c=2

and the most visited target. The second column counts design points with

G_{n}^{(2)}\neq\mathcal{S}

out of all points in the indicated experiment. Medians and ranges summarize only those proper-subgraph points, across instances and sample sizes; they are not confidence intervals. The other points have

G_{n}^{(2)}=\mathcal{S}

, so the estimators coincide. Each ratio uses paired datasets:

4000

per point in the first row and

1000

in the remaining rows.

Temporal-Difference Learning

Temporal-difference learning estimates values by bootstrapping from later predictions, enabling online learning and control from sequential experience.

See all 82 papers

On the Variance of Temporal Difference Learning and its Reduction Using Control Variates
Jun 18, 2026Hsiao-Ru Pan, Bernhard SchölkopfValue Function Estimation Temporal-Difference Learning
Max Planck Institute for Intelligent Systems, Tübingen · ELLIS Institute Tübingen · ETH Zürich
Statistical Inference for Policy Evaluation with Temporal Difference Learning
Oct 21, 2024Weichen Wu, Gen Li, Yuting Wei +1Parameter Estimation Confidence Region Estimation
The Voleon Group, New York, NY, USA · Department of Statistics, The Chinese University of Hong Kong, Hong Kong SAR. · Department of Statistics and Data Science, The Wharton School, University of Pennsylvania, Philadelphia, PA, USA. +1
Towards Parameter-Free Temporal Difference Learning
Mar 3, 2026Yunxiang Li, Mark Schmidt, Reza Babanezhad +1Temporal-Difference Learning
University of British Columbia · Samsung AI - Montreal · Simon Fraser University

Jun 18, 2026J/K move · Enter open · S save

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

Hsiao-Ru Pan, Bernhard Schölkopf

Max Planck Institute for Intelligent Systems, Tübingen · ELLIS Institute Tübingen · ETH Zürich

Value Function Estimation Temporal-Difference Learning Variance Reduction

Open paper AskPDF arXiv

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.

Abstract

Temporal-Difference Learning

Explore similar work

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

Statistical Inference for Policy Evaluation with Temporal Difference Learning

Towards Parameter-Free Temporal Difference Learning