cs.LGMar 29, 2026

Stability and Sensitivity Analysis of Relative Temporal-Difference Learning: Extended Version

Authors: Masoud S. Sakha, Rushikesh Kamalapurkar, Sean Meyn

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Relative temporal-difference (TD) learning was introduced to mitigate the slow convergence of TD methods when the discount factor approaches one by subtracting a baseline from the temporal-difference update. While this idea has been studied in the tabular setting, stability guarantees with function approximation remain poorly understood. This paper analyzes relative TD learning with linear function approximation. We establish stability conditions for the algorithm and show that the choice of baseline distribution plays a central role. In particular, when the baseline is chosen as the empirical distribution of the state-action process, the algorithm is stable for any non-negative baseline weight and any discount factor. We also provide a sensitivity analysis of the resulting parameter estimates, characterizing both asymptotic bias and covariance. The asymptotic covariance and asymptotic bias are shown to remain uniformly bounded as the discount factor approaches one.

Figures & tables

Figure 1: 3-state 2-action MDP model, with randomized policy. Variants of TD learning were performed with discount factor γ=0.99\gamma=0.99 , and step-size ( 11 ) with ρ=0.65\rho=0.65 and α0=2\alpha_{0}=2 .
Figure 2: Eigenvalues as a function of discount factor γ\gamma . One eigenvalue approaches zero for the algorithm using δr=0\delta_{\text{\sf r}}=0 .
Figure 3: Histograms of the scaled and centered parameter estimates for TD(0) and \upvarpi\upvarpi -RTD(0) in the finite state-action model using Polyak–Ruppert averaging. The red solid curves show the corresponding theoretical Gaussian approximations predicted by ( 4 ) and {Zji,m}\{\mathcal{Z}_{j}^{i,m}\} denote the samples used to form the histogram of the jj -th component.
Figure 4: Bias realized vs theory.
Figure 5: Squared-norm of normalized bias as a function of δr\delta_{\text{\sf r}} . The red dashed line is the predicted slope
Figure 6: Eigenvalues as a function of discount factor γ\gamma for the speed-scaling model.
Figure 7: Histograms of the scaled and centered parameter estimates for TD(0) and \upvarpi\upvarpi -RTD(0) in the speed-scaling model using Polyak–Ruppert averaging. The red solid curves show the corresponding theoretical Gaussian approximations predicted by ( 4 ) and {Zji,m}\{\mathcal{Z}_{j}^{i,m}\} denote the samples used to form the histogram of the jj -th component.

Explore similar work

CardsList

  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

  2. Fast and Robust Convergence Rate for TD(0) with Linear Function Approximation, Universal Learning Steps and I.I.D. Samples

    Jun 4, 2026Ziad Kobeissi, Éloïse BerthierStochastic ApproximationTemporal-Difference Learning

    L2S · L2S, INRIA Université Paris-Saclay, CentraleSupelec, Gif-sur-Yvette, France · U2IS +1

  3. Statistical Inference for Policy Evaluation with Temporal Difference Learning

    Oct 21, 2024Weichen Wu, Gen Li, Yuting Wei +1Parameter EstimationConfidence 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