Towards Parameter-Free Temporal Difference Learning

Yunxiang Li; Mark Schmidt; Reza Babanezhad; Sharan Vaswani

cs.LGMar 3, 2026

Towards Parameter-Free Temporal Difference Learning

Authors: Yunxiang Li, Mark Schmidt, Reza Babanezhad, Sharan Vaswani

Organizations: University of British Columbia · Samsung AI - Montreal · Simon Fraser University

Abstract

Temporal difference (TD) learning is a fundamental algorithm for estimating value functions in reinforcement learning. Recent finite-time analyses of TD with linear function approximation quantify its theoretical convergence rate. However, they often require setting the algorithm parameters using problem-dependent quantities that are difficult to estimate in practice -- such as the minimum eigenvalue of the feature covariance ( $ω$ ) or the mixing time of the underlying Markov chain ( $τ_{\text{mix}}$ ). In addition, some analyses rely on nonstandard and impractical modifications, exacerbating the gap between theory and practice. To address these limitations, we use an exponential step-size schedule with the standard TD(0) algorithm. We analyze the resulting method under two sampling regimes: independent and identically distributed (i.i.d.) sampling from the stationary distribution, and the more practical Markovian sampling along a single trajectory. In the i.i.d.\ setting, the proposed algorithm does not require knowledge of problem-dependent quantities such as $ω$ , and attains the optimal bias-variance trade-off for the last iterate. In the Markovian setting, we propose a regularized TD(0) algorithm with an exponential step-size schedule. The resulting algorithm achieves a comparable convergence rate to prior works, without requiring projections, iterate averaging, or knowledge of $τ_{\text{mix}}$ or $ω$ .

Figures & tables

Sampling	Step-size	Convergence rate	Parameters needed	Projection	Last or Average iterate convergence
i.i.d.	$O(t+1)^{-z},z\in(0,1)$ ( Dalal et al., 2018 )	$O\!\left(\exp\!\left(-\omega T^{1-z}\right)+1/T^{z}\right)$	None	No	Last
	$1/\sqrt{T}$ ( Bhandari et al., 2018 )	$O\!\left(\tfrac{\sigma^{2}}{\sqrt{T}}\right)$	None	No	Average
	$O(\omega)$ ( Bhandari et al., 2018 )	$O\!\left(\exp(-\omega^{2}T)+\sigma^{2}\right)$	$\omega$	No	Last
	$O\left(\frac{1}{1+t\,\omega}\right)$ ( Bhandari et al., 2018 )	$O\left(\frac{\sigma^{2}}{T\omega}\right)$	$\omega$	No	Last
	$O(1)$ ( Samsonov et al., 2024 )	$\tilde{O}\left(\exp\left(-\omega T\right)+\frac{\sigma^{2}}{\omega^{2}\,T}\right)$	None	No	Average
	$O\left(\frac{1}{T}^{\nicefrac{{t}}{{T}}}\right)$ ( Ours )	$\tilde{O}\left(\exp\left(-\omega T\right)+\frac{\sigma^{2}}{\omega^{2}T}\right)$	None	No	Last

Table 1: Comparison of our method and other methods.

\omega

is the smallest eigenvalue of the state feature covariance matrix,

T

is the number of updates,

\tau_{\text{mix}}

is the mixing time defined in Eq. 3 , and

m,\rho

are constants in Definition 4.1 , Our i.i.d. result and regularized TD(0) under Markovian sampling require no projections, no prior knowledge of

\tau_{\text{mix}}

\omega

, and no iterate averaging.

Explore similar work

Jun 4, 2026

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

In this paper, we study the finite-time behavior of the TD(0) temporal-difference method with linear function approximation (LFA). We consider on-policy independent and identically distributed (i.i.d.) samples, a constant learning step, and the Polyak-Juditsky averaging method. We establish a new convergence rate, for the Mean-Square Error (MSE) on the approximated function, that is (i) fast in the sense that it admits an optimal dependency in the number of iterations k (i.e., of order 1/k), (ii) robust to ill-conditioning: it only depends on an initial error and modelindependent constants and (iii) sharp up to a multiplicative constant lower than 11. In particular, it does not depend on the smallest eigenvalue of the uncentered covariance matrix of the linear parametrization, unlike all pre-existing O(1/k) rates in the TD(0) literature. We also introduce PCTD(0), a variant of TD(0), which benefits from better convergence properties under an additional assumption of strong mixing on the Markov Chain.

Ziad Kobeissi, Éloïse Berthier

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

Stochastic Approximation Temporal-Difference Learning Linear Function Approximation

Ask PDF

May 3, 2026

Bridging the Gap Between Average and Discounted TD Learning

The analysis of Temporal Difference (TD) learning in the average-reward setting faces notable theoretical difficulties because the Bellman operator is not contractive with respect to any norm. This complicates standard analyses of stochastic updates that are effective in discounted settings. Although a considerable body of literature addresses these challenges, existing theoretical approaches come with limitations. We introduce a novel algorithm designed explicitly for policy evaluation in the average-reward setting, utilizing sampling from two Markovian trajectories. Our proposed method overcomes previous limitations by guaranteeing convergence to the unique solution of a properly defined projected Bellman equation. Notably, and in contrast to earlier work, our convergence analysis is uniformly applicable to both linear function approximation and tabular settings and does not involve explicit dimension-dependent terms in its convergence bounds. These results align with what is known to hold in the discounted setting. Furthermore, our algorithm achieves improved dependence on the problem's condition number, reducing the sample complexity from quartic, as in prior literature, to quadratic scaling, and thus matching the efficiency seen in the discounted setting.

Haoxing Tian, Zaiwei Chen, Ioannis Ch. Paschalidis +1

Department of Electrical and Computer Engineering Boston University · Edwardson School of Industrial Engineering Purdue University

Reinforcement Learning Average-Reward RL Stochastic Approximation Policy Evaluation Temporal-Difference Learning Linear Function Approximation

Ask PDF

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.

Weichen Wu, Gen Li, Yuting Wei +1

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

Parameter Estimation Confidence Region Estimation Value Function Estimation Stochastic Approximation Policy Evaluation Temporal-Difference Learning+1

Ask PDF