[Submitted on 14 Nov 2024 (v1), last revised 26 Oct 2026 (this version, v3)]
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.
Submission history
From: Wenlong Mou [view email]
[v1] Thu, 14 Nov 2024 19:00:00 UTC (70 KB)
[v2] Wed, 27 Nov 2024 23:19:41 UTC (62 KB)
[v3] Mon, 26 Oct 2026 18:55:11 UTC (196 KB)
