Towards Parameter-Free Temporal Difference Learning

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 ($\omega$) or the mixing time of the underlying Markov chain ($\tau_\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 the knowledge of problem-dependent quantities such as $\omega$, 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 $\tau_\text{mix}$ or $\omega$.

Many modern AI systems learn by trial and error, and to do so they must constantly judge how promising their current situation is. A classic, widely used way to learn these judgments is temporal difference learning. Like most learning methods, it has a step size controlling how big a step it takes each time it updates an estimate. Setting this step size well normally requires knowing hidden features of the problem that are hard to measure in advance, making the method finicky to tune. Existing approaches either assume these unknown quantities are available, or rely on workarounds that practitioners rarely use. We show that a simple recipe avoids all of this: start with a moderate step and steadily shrink it over time. This removes the need to know any hidden problem features while still learning quickly, and our guarantee applies to the final estimate the method returns, which is exactly what is used in practice, rather than an average of past estimates. We prove this mathematically and confirm it in experiments, making a core building block of reinforcement learning easier and more reliable to use.