Temporal-Difference Learning

Overview

Temporal-difference (TD) learning studies how to estimate future rewards and improve decisions by updating predictions from the difference between a current estimate and a bootstrapped next-step target. Its methods range from tabular and linear TD with eligibility traces to deep Q-learning, distributional critics, and multi-step or off-policy updates, used in prediction, control, and policy evaluation. Current work develops sharper convergence and uncertainty guarantees for single-trajectory, Markovian data while extending TD to long-horizon, multi-agent, and partially observed settings. A central tension is that bootstrapping makes learning data-efficient, but function approximation, off-policy sampling, and moving targets can cause bias or instability; balancing stability, speed, and accurate credit assignment remains open.

Latest papers

93 papers14 papers in the last four weeks, down 7% on the four weeks before. 0.1% of all new papers.

Nov 14, 2024

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

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.
Oct 21, 2024

Statistical Inference for Policy Evaluation with Temporal Difference Learning

We investigate the statistical properties of Temporal Difference (TD) learning with Polyak-Ruppert averaging, arguably one of the most widely used algorithms in reinforcement learning, for the task of estimating the parameters of the optimal linear approximation to the value function. Assuming independent samples, we make three theoretical contributions that improve upon the current state-of-the-art results: (i) we establish refined high-dimensional Berry-Esseen bounds over the class of convex sets, achieving faster rates than the best known results, and (ii) we propose and analyze a novel, computationally efficient online plug-in estimator of the asymptotic covariance matrix; (iii) we derive sharper high probability convergence guarantees that depend explicitly on the asymptotic variance and hold under weaker conditions than those adopted in the literature. These results enable the construction of confidence regions and simultaneous confidence intervals for the linear parameters of the value function approximation, with guaranteed finite-sample coverage. We demonstrate the applicability of our theoretical findings through numerical experiments.
Oct 9, 2024

Deep End-to-End Survival Analysis with Temporal Consistency

In this study, we present a novel Survival Analysis algorithm designed to efficiently handle large-scale longitudinal data. Our approach draws inspiration from Reinforcement Learning principles, particularly the Deep Q-Network paradigm, extending Temporal Learning concepts to Survival Regression. A central argument in our method relies on temporal consistency, a recursive consistency condition between survival predictions made at consecutive states. Our framework introduces a delayed target network that decouples the generation of temporally consistent training targets from model updates, providing a more stable training signal while enabling mini-batch optimization and end-to-end training. Additionally, it supports arbitrarily complex architectures, enabling the modeling of intricate temporal dependencies. Through numerous experiments we provide empirical evidence demonstrating our framework's ability to exploit temporal consistency across datasets of varying sizes. Moreover, our algorithm outperforms benchmarks on datasets with long sequences, demonstrating its ability to capture long-term patterns. Finally, ablation studies show that the degree of target delay has a substantial effect on predictive performance and training variability. Across two distinct survival model families, delayed target updates consistently improve over the same-timescale baseline.