Towards Parameter-Free Temporal Difference Learning

2026-03-03 · Yunxiang Li, Mark Schmidt, Reza Babanezhad, Sharan Vaswani arxiv

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 $ω$.

📄 PDF Abstract BibTeX arXiv:2603.02577

Code (0)

등록된 구현이 없습니다.

Tasks

Reinforcement Learning

Parameter-free Gradient Temporal Difference Learning

2021-05-10 · Andrew Jacobsen, Alan Chan

Reinforcement learning lies at the intersection of several challenges. Many applications of interest involve extremely large state spaces, requiring function approximation to enable tractable computation. In addition, th…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Sample Complexity and Overparameterization Bounds for Temporal Difference Learning with Neural Network Approximation

2021-03-02 · Semih Cayci, Siddhartha Satpathi, Niao He, R. Srikant

In this paper, we study the dynamics of temporal difference learning with neural network-based value function approximation over a general state space, namely, \emph{Neural TD learning}. We consider two practically used …

An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning

2015-03-14 · Richard S. Sutton, A. Rupam Mahmood, Martha White

In this paper we introduce the idea of improving the performance of parametric temporal-difference (TD) learning algorithms by selectively emphasizing or de-emphasizing their updates on different time steps. In particula…

Adaptive Lambda Least-Squares Temporal Difference Learning

2016-12-30 · Timothy A. Mann, Hugo Penedones, Shie Mannor, Todd Hester

Temporal Difference learning or TD($\lambda$) is a fundamental algorithm in the field of reinforcement learning. However, setting TD's $\lambda$ parameter, which controls the timescale of TD updates, is generally left up…

Reinforcement Learning

n-Step Temporal Difference Learning with Optimal n

2023-03-13 · Lakshmi Mandal, Shalabh Bhatnagar

We consider the problem of finding the optimal value of n in the n-step temporal difference (TD) learning algorithm. Our objective function for the optimization problem is the average root mean squared error (RMSE). We f…

Stochastic Optimization