Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features

Thanks for the thoughtful questions. We provide responses below and will include all the clarification in revision.

Motivation of the linearly dependent features.

Thank you for raising this sharp point. You are correct that in certain theoretical regimes, such as with infinite state spaces, features generated by a wide network can be linearly independent (Cai et al., 2019). However, in finite state-space settings (e.g., Atari games or Go game), the feature dimension $d$ of a modern wide network (in particular, very wide networks used in NTK literature) can easily exceed the number of states $|S|$. By basic linear algebra, this immediately implies that the feature vectors corresponding to the state space must be linearly dependent.

Moreover, even when the feature dimension $d$ does not exceed $|S|$, the learning process itself often induces strong correlations among features, as they adapt to the data and task. In fact, the challenge of handling linearly dependent features from learned representations was a key technical motivation for the analysis in Chung et al. (2019). Their work underscores that addressing this issue is a practical necessity.

Thus, our work provides crucial guarantees for a prevalent and often unavoidable scenario in modern reinforcement learning.

Ref:

Chung, W. et al. Two-Timescale Networks for Nonlinear Value Function Approximation. ICLR, 2019.

The experiments use constant learning rates while the theory uses diminishing ones.

Thank you for noting this discrepancy. We used constant learning rates as they are common in empirical studies. We agree that aligning our experiments with our theory is important and will add a new set of experiments with diminishing learning rates in the revision. Additionally, we will add a discussion showing that once we have the recursion in Lemma 5, our theoretical framework can be readily extended to the constant step-size setting (akin to Chen et al., 2021), demonstrating its broad applicability.

Ref:

Z. Chen et al. A Lyapunov theory for finite-sample guarantees of asynchronous Q-learning and TD-learning variants. arXiv preprint, 2021.

For the linear independence assumption, why not expand the state space or remove features to enforce it?

Thank you for these creative suggestions. We have considered similar approaches, but they introduce significant technical challenges that prevent their straightforward application.

Your idea of expanding the state space to enforce linear independence is intriguing. However, adding "null states" would likely break the irreducibility of the underlying Markov chain (Assumption 3.1), as these new states may not be reachable from the original set, or vice-versa. This would invalidate key parts of all previous analyses that rely on the mixing properties derived from a single, irreducible chain. If we modify the transition function to make them reachable, it would alter the stationary distribution and the effect of discounting, thereby changing the value function of existing states.

Alternatively, removing features to achieve linear independence is often impractical. This approach requires simultaneous access to all states, which becomes challenging in continual learning settings or prohibitively expensive with large state spaces. Such modifications present significant computational and data accessibility barriers in real-world applications.

Ref:

J. N. Tsitsiklis and B. Van Roy, Average cost temporal-difference learning. Proceedings of the 36th IEEE Conference on Decision and Control, 1997, pp. 498-502.

In terms of the rate of convergence ... they depend on other constants like $|S|$ and $d$.

Thank you for your careful reading of our theorem and for these important questions. Indeed, for the bound to guarantee convergence to zero, the exponent $\min(2\xi - 1, \lfloor \kappa_1\rfloor - 1)$ must be positive. Our result holds for any $\xi \in (0.5,1]$, so $2\xi-1>0$. Since $\kappa_1$ is proportional to the step-size coefficient $\alpha$ ($\kappa_1=\alpha C_7$, see Appendix C.5, and we recall that we use $\alpha_t = \alpha / t^\xi$), by choosing a sufficiently large $\alpha$, we can ensure $\lfloor\kappa_1\rfloor - 1 \ge 2\xi - 1$, meaning the convergence rate is determined by the exponent $2\xi - 1$. We will revise the theorem statement to clarify these conditions and eliminate ambiguity.

To place our result in context, prior work on linear Temporal Difference (TD) learning has established key benchmarks. Bhandari et al. (2018) reported a rate of $\mathcal{O}(1/\sqrt{T})$ for a constant step-size $\alpha_t = 1/\sqrt{T}$ and a faster $\mathcal{O}(1/t)$ rate for a decaying step-size $\alpha_t \propto 1/t$, while Srikant and Ying (2019) achieved $\mathcal{O}(1/T)$ for constant step-sizes. Our work, focusing on decaying step-sizes, derives a rate of $\mathcal{O}(1/t^{2\xi - 1})$ for $\alpha_t \propto \alpha/t^\xi$, where $\xi \in (0.5, 1]$ and $\alpha$ is sufficiently large. For $\xi = 1$, our $\mathcal{O}(1/t)$ rate matches the best-known rate for TD with decaying step-sizes and aligns with the standard convergence rate of Stochastic Gradient Descent (SGD). This demonstrates that relaxing the linear independence assumption does not compromise performance.

For the two constants, $\kappa_1$ would depend on the specific $A=X^\top D_\pi(\gamma P_\lambda -I) X$; $C_\text{thm1}$ relates to $\alpha_0, C_x, C_e$, and $\bar t$. Both constants depend on the state space size $|S|$ and the dimension $d$. Such dependencies on problem parameters like $|S|$ and $d$ are standard in the analysis of linear TD (Srikant and Ying (2019); Mitra (2025)).

Ref:

J. Bhandari, et al. A finite time analysis of temporal difference learning with linear function approximation. In Conference on Learning Theory, 2018.

R. Srikant and L. Ying. Finite-time error bounds for linear stochastic approximation and td learning. In Conference on Learning Theory, 2019.

Aritra Mitra. A simple finite-time analysis of td learning with linear function approximation. IEEE Transactions on Automatic Control, 2025.

Thanks for the thoughtful questions. We provide responses below and will include all the clarification in revision.

Could you clarify how your results for standard TD($\lambda$) complement or differ from the convergence analysis of gradient TD($\lambda$) in Chung et al. (2019), which also handles arbitrary features, even though it is in a nonlinear setting?

Thank you for this excellent question. While both Chung et al. (2019) and our work consider arbitrary features, they are fundamentally distinct.

First, their analysis provides an asymptotic result with a weaker convergence notion (liminf), whereas we establish explicit $L^2$ rates. They show convergence to a set of asymptotically stable equilibria without characterizing this set or proving its existence, a significant challenge in itself (cf. Wang and Zhang (2024)). In contrast, our work proves the non-emptiness of the solution set and provides rates of convergence to this well-defined set. Additionally, their algorithm requires a projection operator, while our analysis applies to the unmodified TD($\lambda$).

The second core distinction is that GTD is a stochastic gradient descent (SGD) method on the Mean-Squared Bellman Error, allowing it to leverage standard optimization theory. In contrast, TD($\lambda$) is a semi-gradient method. Its expected update is not the gradient of any objective function, making its analysis fundamentally more challenging. We provide stronger guarantees for this classic algorithm by addressing analytical challenges absent in the more structured GTD framework.

Given that the analysis is limited to the linear on-policy setting, what are the implications of your results for nonlinear function approximation, and could your techniques be extended to that more general setting?

Thank you for this forward-looking question. Our methodology is directly applicable to the off-policy setting, requiring only the standard adaptation of incorporating importance sampling ratios into the analysis.

An extension to nonlinear function approximation is also possible via the Neural Tangent Kernel framework (cf. Cai (2019)). This path linearizes a sufficiently wide neural network, and recasts the TD update as a linear recursion within a high-dimensional feature space (an RKHS). In principle, our finite-sample $L^2$ analysis could then be applied.

However, a direct application faces several technical challenges. For instance, rigorously bounding the spectrum of the kernel matrix under Markovian data and managing the computational overhead of kernel methods (e.g., using random features as in Rahimi and Recht (2008)) would require significant analytical extensions to account for new error terms and sampling complexities. A full treatment of these issues is beyond this paper's scope, but we believe our work provides a solid foundation for this exciting future research direction.

Ref:

Q. Cai, et al. Neural temporal-difference learning converges to global optima. In NeurIPS, 2019.

A. Rahimi and B. Recht. Random features for large-scale kernel machines. In NeurIPS, 2008.

Could you provide more discussion on the practical implications of your results, such as guidance on feature selection, learning rate tuning, or diagnosing convergence?

We appreciate this important practical question. Our theory offers direct guidance for practitioners. For feature selection, our analysis removes the strict requirement of linear independence, freeing practitioners to use correlated features, which is especially valuable in dynamic settings like continual learning. For learning rate tuning, our results support a step-size of the form $\alpha_t = \alpha / (t+t_0)^\xi$, suggesting an effective starting point with $\xi \in (0.5, 1]$ (e.g., closer to 1 for faster convergence) and then tuning $\alpha$ and $t_0$ for performance. Crucially, for diagnosing convergence, our theory advises monitoring the value estimate $Xw_t / (\mathbf{1}^\top Xw_t)$ for convergence to a unique solution, rather than the potentially drifting weight vector $w_t$. We will incorporate this guidance into the revised manuscript to highlight its utility.

Thanks for the thoughtful questions. We provide responses below and will include all the clarification in revision.

Please discuss the obtained convergence rates in light of the literature

The convergence rate of linear TD with linearly independent features has been previously studied. In particular, Bhandari et al. (2018) established a rate of $\mathcal{O}(1/\sqrt{T})$ for a constant step-size $\alpha_t = \frac{1}{\sqrt{T}}$ and a faster $\mathcal{O}(1/t)$ rate for a decaying step-size $\alpha_t \propto 1/t$. Srikant and Ying (2019) provided an $\mathcal{O}(1/T)$ rate for the constant step-size setting. Our work focuses on the decaying step-size case, providing a rate of $\mathcal{O}(1/t^{\min(2\xi-1, \lfloor\kappa_1\rfloor-1)})$ for $\alpha_t \propto \alpha/t^\xi$, where $\xi \in (0.5, 1]$.

Since $\kappa_1$ is proportional to the step-size coefficient $\alpha$ ($\kappa_1=\alpha C_7$, see Appendix C.5), by choosing a sufficiently large $\alpha$, we can ensure $\lfloor\kappa_1\rfloor - 1 \ge 2\xi - 1$, meaning the convergence rate is determined by the exponent $2\xi - 1$. Therefore, for the standard choice of $\xi=1$, our rate becomes $\mathcal{O}(1/t)$. This result matches the best-known rate for TD with decaying step-sizes and aligns with the standard rate for Stochastic Gradient Descent (SGD). This indicates that relaxing the linear independence assumption does not hurt the convergence rate.

Ref:

J. Bhandari, et al. A finite time analysis of temporal difference learning with linear function approximation. In Conference on Learning Theory, 2018.

R. Srikant and L. Ying. Finite-time error bounds for linear stochastic approximation and td learning. In Conference on Learning Theory, 2019.

Please discuss the tightness of the obtained bounds

Admittedly, we did not prove the tightness of our bounds. But as discussed above, our rate matches the best-known rate for TD and the standard rate for SGD (the optimal $\mathcal{O}(1/t)$ rate of SGD for strongly convex problems under standard assumptions), despite our relaxed assumptions.Furthermore, Kane (2023) highlights the exponential hardness of RL with linear function approximation, supporting the significance of our polynomial rates as a state-of-the-art benchmark.

Ref:

D. Kane, et al. Exponential hardness of reinforcement learning with linear function approximation. In Conference on Learning Theory, 2023.

Please clarify the intent of the experiment and how it connects with the results.

Our experiments serve two key purposes.

First, they provide the first empirical verification for linear TD($\lambda$) with dependent features, a gap left by recent theoretical work (cf. Wang & Zhang (2024)). Our experiments fill this critical gap by demonstrating empirical convergence in both discounted and average-reward settings using linearly dependent features. As noted by Sutton and Barto (2018, p. 282), Emphatic TD’s “variance on Baird’s counterexample is so high that consistent experimental results are nearly unattainable,” although ETD's theoretical convergence has been well established. So we believe it is important to verify that linear TD with linearly dependent features does converge empirically.

Second, our plots offer a novel perspective by visualizing convergence to a solution set ($d(w_t, W^*)$), rather than a single point. This directly illustrates the behavior predicted by our theory for the arbitrary feature case and showcases the algorithm's stability via small standard errors.

To further strengthen the paper, we will add experiments with decaying step-sizes to match our theory. We choose to use constant step size in the current version mostly to better align with practices. There is no difficulty in extending our analysis to constant step size. In particular, once we have the recursion in Lemma 5, the convergence rate with a constant step size can be easily established using standard techniques (cf. Chen et al. (2021)).

Ref:

R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT press, 2018.

Z. Chen et al. A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants. arXiv preprint, 2021.

Thanks for the thoughtful questions. We provide responses below and will include all the clarification in revision.

Lack of optimality.

Thank you for this point. The convergence rate of linear TD with linearly independent features has been previously studied. In particular, Bhandari et al. (2018) established a rate of $\mathcal{O}(1/\sqrt{T})$ for a constant step-size $\alpha_t = \frac{1}{\sqrt{T}}$ and a faster $\mathcal{O}(1/t)$ rate for a decaying step-size $\alpha_t \propto 1/t$. Srikant and Ying (2019) provided an $\mathcal{O}(1/T)$ rate for the constant step-size setting. Our work focuses on the decaying step-size case, providing a rate of $\mathcal{O}(1/t^{\min(2\xi-1, \lfloor\kappa_1\rfloor-1)})$ for $\alpha_t \propto \alpha/t^\xi$, where $\xi \in (0.5, 1]$.

Since $\kappa_1$ is proportional to the step-size coefficient $\alpha$ ($\kappa_1=\alpha C_7$, see Appendix C.5), by choosing a sufficiently large $\alpha$, we can ensure $\lfloor\kappa_1\rfloor - 1 \ge 2\xi - 1$, meaning the convergence rate is determined by the exponent $2\xi - 1$. Therefore, for the standard choice of $\xi=1$, our rate becomes $\mathcal{O}(1/t)$. This result matches the best-known rate for TD with decaying step-sizes and aligns with the standard rate for Stochastic Gradient Descent (SGD). This indicates that relaxing the linear independence assumption does not hurt the convergence rate. While the question of strict optimality remains open (Kane, 2023), our rate establishes a strong benchmark for state-of-the-art performance in this setting.

Ref:

J. Bhandari, et al. A finite time analysis of temporal difference learning with linear function approximation. In Conference on Learning Theory, 2018.

R. Srikant and L. Ying. Finite-time error bounds for linear stochastic approximation and td learning. In Conference on Learning Theory, 2019.

D. Kane, et al. Exponential hardness of reinforcement learning with linear function approximation. In Conference on Learning Theory, 2023.

Weakness of parameter-dependent optimal step sizes and whether your analysis will carry over if Polyak-Ruppert averaging is additionally used.

Thank you for these insightful questions. We agree that incorporating Polyak-Ruppert averaging is a promising path to achieving parameter-free rates, and we believe the techniques from the cited works (Patil et al. (2023); Naskar et al. (2024)) are applicable to our setting. In the current manuscript, due to page limits, we focus on establishing the first $L^2$ rates for this general setting to clearly present our core contribution. We are grateful for this excellent suggestion and will add a discussion on this promising direction in our revision, acknowledging your valuable pointer.

Do you think your analysis will carry over to (tabular) Q-learning?

Thank you for this question. Our work focuses on the challenge of linearly dependent features, which does not arise in standard tabular $Q$-learning due to its full-rank (e.g., one-hot) representations.

The more relevant extension is to linear $Q$-learning, where our methodology shows significant potential. Recent breakthroughs establish that linear $Q$-learning iterates converge to a bounded set (cf. Meyn (2024); Liu (2025)), rather than to a single point. This makes our techniques for analyzing convergence to a solution set directly applicable to the problem.

However, our approach alone is not sufficient. The key challenge is the max operator in the $Q$-learning update, which breaks the crucial (semi-)contraction properties leveraged in our on-policy analysis. Therefore, a full analysis of linear $Q$-learning would require combining our set-valued convergence tools with new methods designed to handle the non-linear dynamics introduced by the max operator.

Ref:

S. Meyn. The Projected Bellman Equation in Reinforcement Learning. IEEE Transactions on Automatic Control, 2024.

X. Liu, et al. Linear $Q$-Learning Does Not Diverge in $L^2$: Convergence Rates to a Bounded Set. International Conference on Machine Learning, 2025.

How do you think your work advances the current state of the art?

Thank you for this crucial question. Our primary contribution lies in policy evaluation, where we establish the first $L^2$ convergence rates for linear TD($\lambda$) with arbitrary features. This strengthens a fundamental building block of RL, as reliable policy evaluation with provable convergence properties is a prerequisite for effective control in algorithms like policy iteration and actor-critic.

The important papers you cited (Patterson (2024); Young and Sutton (2020); Gopalan and Thoppe (2022)) highlight critical challenges in control that arise from the interaction with function approximation. We view these as vital research opportunities. A rigorous understanding of the evaluation component, which our work provides, is a necessary first step to formally analyze and address the instabilities they discuss.

We will expand our discussion in the revised manuscript to better connect our foundational results to these important control-focused challenges. Thank you for the valuable pointers.