A Simple Finite-Time Analysis of TD Learning with Linear Function Approximation

Aritra Mitra

Abstract We study the finite-time convergence of TD learning with linear function approximation under Markovian sampling. Existing proofs for this setting either assume a projection step in the algorithm to simplify the analysis, or require a fairly intricate argument to ensure stability of the iterates. We ask: Is it possible to retain the simplicity of a projection-based analysis without actually performing a projection step in the algorithm? Our main contribution is to show this is possible via a novel two-step argument. In the first step, we use induction to prove that under a standard choice of a constant step-size $\alpha$, the iterates generated by TD learning remain uniformly bounded in expectation. In the second step, we establish a recursion that mimics the steady-state dynamics of TD learning up to a bounded perturbation on the order of $O(\alpha^2)$ that captures the effect of Markovian sampling. Combining these pieces leads to an overall approach that considerably simplifies existing proofs. We conjecture that our inductive proof technique will find applications in the analyses of more complex stochastic approximation algorithms, and conclude by providing some examples of such applications.

Introduction

Temporal Difference (TD) learning is a fundamental algorithm in Reinforcement Learning (RL), specifically for the task of policy evaluation—estimating the cumulative reward an agent will receive by following a specific strategy. To handle the high-dimensional state spaces common in real-world applications, TD learning is frequently paired with linear function approximation.

Despite its widespread use, providing a rigorous finite-time analysis of TD learning has historically been challenging. Researchers typically face two major hurdles: Markovian sampling and stability. Unlike independent and identically distributed (i.i.d.) data, Markovian data is temporally correlated, which complicates the mathematical convergence proofs. Furthermore, to ensure the algorithm doesn't diverge, many theoretical analyses assume a "projection step"—a constraint that forces parameters to stay within a bounded region. However, practitioners rarely use this step, creating a gap between theory and practice.

Methodology: A Novel Inductive Argument

This paper bridges the gap by introducing a simplified, two-step inductive proof technique that analyzes the standard, unprojected TD learning algorithm. The approach avoids the need for complex Lyapunov functions or advanced control theory, providing a more accessible "recipe" for convergence analysis.

1. Uniform Boundedness via Induction

The first step addresses the stability problem. Instead of forcing boundedness through a projection operator, the author uses induction to prove that the iterates remain bounded in expectation. By assuming that previous iterates were bounded, the author demonstrates that for a sufficiently small constant step-size $\alpha$, the subsequent update will also remain bounded. This inductive hypothesis effectively controls the potential for the algorithm to "blow up" during the learning process.

2. Steady-State Recursion

Once boundedness is established, the TD update is decomposed into three primary components:

  • The Signal: An exponentially decaying term representing the progress toward the optimal solution.
  • The Noise: A variance term standard in stochastic optimization.
  • The Markovian Disturbance: A term capturing the temporal correlations in the data.

By leveraging the "mixing time" of the Markov chain—the time it takes for data correlations to dissipate—the author proves that this disturbance is small, specifically on the order of $O(\alpha^2)$. This allows the analysis to follow a logic similar to that of standard Stochastic Gradient Descent (SGD).

Key Theoretical Results

The paper formalizes these insights through several key theorems:

  • Theorem 1 (Boundedness): Establishes that with a constant step-size $\alpha$ inversely proportional to the mixing time $\tau$, the expected squared error of the parameters remains uniformly bounded for all time $t$.
  • Theorem 2 (Convergence Rate): Shows that TD learning converges exponentially fast to a "noise ball" around the optimal solution, where the radius of the ball is proportional to the step-size $\alpha$.
  • Theorem 3 (Iterate Averaging): Introduces a weighted averaging scheme for the parameters that achieves a finer convergence rate, representing a new contribution to the TD learning literature.

Furthermore, the author demonstrates that this inductive technique is generalizable, extending beyond TD(0) to the entire TD($\lambda$) family and certain variants of Q-learning.

Discussion and Future Work

The primary strength of this work lies in its simplicity. By treating Markovian noise as a bounded disturbance to a stable system, the proof becomes highly adaptable to other "noisy" RL scenarios, such as systems with communication errors or time-varying delays.

However, some practical hurdles remain. The optimal step-size $\alpha$ depends on knowing the system's mixing time and smallest eigenvalue, parameters that are often unknown in real-world settings. Additionally, while the analysis is robust for linear function approximation, extending this inductive technique to non-linear approximators (like deep neural networks) or more complex two-time-scale algorithms (like Actor-Critic) remains an open challenge for future research.

Summary updated

Abstract

We study the finite-time convergence of TD learning with linear function approximation under Markovian sampling. Existing proofs for this setting either assume a projection step in the algorithm to simplify the analysis, or require a fairly intricate argument to ensure stability of the iterates. We ask: \textit{Is it possible to retain the simplicity of a projection-based analysis without actually performing a projection step in the algorithm?} Our main contribution is to show this is possible via a novel two-step argument. In the first step, we use induction to prove that under a standard choice of a constant step-size $\alpha$, the iterates generated by TD learning remain uniformly bounded in expectation. In the second step, we establish a recursion that mimics the steady-state dynamics of TD learning up to a bounded perturbation on the order of $O(\alpha^2)$ that captures the effect of Markovian sampling. Combining these pieces leads to an overall approach that considerably simplifies existing proofs. We conjecture that our inductive proof technique will find applications in the analyses of more complex stochastic approximation algorithms, and conclude by providing some examples of such applications.
BibTeX
@article{mitra2025simple,
  author = {Aritra Mitra},
  title = {{A Simple Finite-Time Analysis of TD Learning with Linear Function Approximation}},
  journal = {IEEE Trans. Automatic Control},
  year = {2025},
  url = {https://openreview.net/forum?id=pRSlhlTy6e},
}
Figure