Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features
Zixuan Xie, Xinyu Liu *, Rohan Chandra, Shangtong Zhang · 2025
Read Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features by Zixuan Xie, Xinyu Liu *, Rohan Chandra, Shangtong Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-21391.txt.
Introduction
Zixuan Xie and co-authors give new accuracy guarantees for a classic learning algorithm in this 2025 paper. Temporal difference learning estimates the value of a policy from experience and is a base tool in reinforcement learning. Past rate proofs assumed the input features are independent, which often fails in practice.
The authors prove the first mean-square convergence rates for the method with fully general features, with no change to the algorithm and no added assumptions. The results cover both discounted and average-reward settings. Because general features can allow many solutions, they prove convergence to the whole solution set rather than one point, using a new approximation result.
Catalog record
| CREATOR | Zixuan Xie, Xinyu Liu *, Rohan Chandra, Shangtong Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 83 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-21391
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features Zixuan Xie, Xinyu Liu *, Rohan Chandra, Shangtong Zhang Abstract Linear TD( λ \lambda ) is one of the most fundamental reinforcement learning algorithms for policy evaluation. Previously, convergence rates are typically established under the assumption of linearly independent features, which does not hold in many practical scenarios. This paper instead establishes the first L 2 L^{2} convergence rates for linear TD( λ \lambda ) operating under arbitrary features, without making any algorithmic modification or additional assumptions. Our results apply to both the discounted and average-reward settings. To address the potential non-uniqueness of solutions resulting from arbitrary features, we develop a novel stochastic approximation result featuring convergence rates to the solution set instead of a single point. 1 Introduction Temporal difference learning (TD, Sutton (1988) ) is a fundamental algorithm in reinforcement learning (RL, Sutton and Barto (2018) ), enabling efficient policy evaluation by combining dynamic programming ( Bellman, 1966 ) with stochastic approximation (SA, Benveniste et al. (1990) ; Kushner and Yin (2003) ; Borkar (2009) ). Its linear variant, linear TD( \lambda ) ( Sutton, 1988 ) , emerges as a practical extension, employing linear function approximation to tackle large or continuous state spaces where tabular representations become impractical. Linear TD( \lambda ) takes the dot product between features and weights to compute the approximated value. Establishing theoretical guarantees for linear TD( \lambda ), particularly convergence rates, has been a major focus of research. Most existing works (Table 1 ), however, require the features used in linear TD to be linearly independent. As argued in Wang and Zhang (2024) , this assumption is impractical in many scenarios. For example, in continual learning with sequentially arriving data ( Ring, 1994 ; Khetarpal et al., 2022 ; Abel et al., 2023 ) , there is no way to rigorously verify whether the features are independent or not. See Wang and Zhang (2024) for more discussion on the restrictions of the feature independence assumptions. Furthermore, Dayan (1992) ; Tsitsiklis and Roy (1996) ; Tsitsiklis and Roy (1999) also outline the elimination of the linear independence assumption as a future research direction. While efforts have been made to eliminate the linear independence assumption ( Wang and Zhang, 2024 ) , they only provide asymptotic (almost sure) convergence guarantees in the discounted setting. By contrast, this paper establishes the first L^{2} convergence rates for linear TD( \lambda ) with arbitrary features in both discounted and average-reward settings . This success is enabled by a novel stochastic approximation result (Theorem 3 ) concerning the convergence rates to a solution set instead of a single point, driven by a novel Lyapunov function. This new result provides a unified approach applicable to both discounted (Theorem 1 ) and average-reward (Theorem 2 ) settings. Notably, we do not make any algorithmic modification and do not introduce any additional assumptions. Table 1 provides a detailed comparison of existing theoretical analyses for linear TD( \lambda ), contextualizing our contributions within the landscape of prior work. Setting Features Noise Type Rate Tsitsiklis and Roy (1996) \gamma<1 Independent Markovian Bhandari et al. (2018) \gamma<1 Independent Markovian \checkmark Lakshminarayanan and Szepesvári (2018) \gamma<1 Independent i.i.d. \checkmark Srikant and Ying (2019) \gamma<1 Independent Markovian \checkmark Wang and Zhang (2024) \gamma<1 Arbitrary Markovian Chen et al. (2025a) \gamma<1 Independent i.i.d. \checkmark Mitra (2025) \gamma<1 Independent Markovian \checkmark Theorem 1 \gamma<1 Arbitrary Markovian \checkmark Tsitsiklis and Roy (1999) \gamma=1 Independent Markovian Zhang et al. (2021c) \gamma=1 Independent Markovian \checkmark Chen et al. (2025b) \gamma=1 Independent Markovian \checkmark Theorem 2 \gamma=1 Arbitrary Markovian \checkmark Table 1: Comparison of finite-sample analyses for linear TD( \lambda ). “Setting” indicates the problem setting: \gamma<1 stands for the discounted setting and \gamma=1 stands for the average reward setting. “Features” describes assumptions on the features. “Independent” indicates linear independence is assumed. “Arbitrary” indicates no assumption is made on features. “Noise Type” indicates the data generation process: Markovian samples or independent and identically distributed (i.i.d.) samples. “Rate” is checked if a convergence rate is provided. 2 Background Notations. We use \langle x,y\rangle\doteq x^{\top}y to denote the standard inner product in Euclidean spaces and \norm{\cdot} to denote the \ell_{2} norm for vectors and the associated induced operator norm (i.e., the spectral norm) for matrices, unless stated otherwise. A function f is said to be L -smooth (w.r.t. \norm{\cdot} ) if \forall w,w^{\prime} , f(w^{\prime})\leq f(w)+\langle\nabla f(w),w^{\prime}-w\rangle+\frac{L}{2}\norm{w' - w}^{2} . For a matrix A , \operatorname{col}(A) denotes its column space, \ker(A) denotes its kernel, and A^{\dagger} denotes its Moore-Penrose inverse. When x is a point and U is a set, we denote d(x,U)\doteq\inf_{y\in U}\norm{x - y} as the Euclidean distance from x to U . For sets U,V , their Minkowski sum is U+V\doteq\{u+v\mid u\in U,v\in V\} ; and U^{\perp} denotes the orthogonal complement of U . We use \mathbf{0} and \mathbf{1} to denote the zero vector and the all-ones vector respectively, where the dimension is clear from context. For any square matrix A\in\mathbb{R}^{d\times d} (not necessarily symmetric), we say A is negative definite (n.d.) if there exists a \xi>0 such that x^{\top}Ax\leq-\xi\norm{x}^{2}\ \forall x\in\mathbb{R}^{d} . For any set E\subseteq\mathbb{R}^{d} , we say A is n.d. on E if there exists a \xi>0 such that x^{\top}Ax\leq-\xi\norm{x}^{2}\,\forall x\in E . A is negative semidefinite (n.s.d.) if \xi=0 in the above definition. Markov Decision Processes. We consider an infinite horizon Markov Decision Process (MDP, Bellman (1957) ) defined by a tuple (\mathcal{S},\mathcal{A},p,r,p_{0}) , where \mathcal{S} is a finite set of states, \mathcal{A} is a finite set of actions, p:\mathcal{S}\times\mathcal{S}\times\mathcal{A}\to\quantity[0,1] is the transition probability function, r:\mathcal{S}\times\mathcal{A}\to\mathbb{R} is the reward function, and p_{0}:\mathcal{S}\to[0,1] denotes the initial distribution. In this paper, we focus on the policy evaluation problem, where the goal is to estimate the value function of an arbitrary policy \pi:\mathcal{A}\times\mathcal{S}\to[0,1] . At the time step 0 , an initial state S_{0} is sampled from p_{0} . At each subsequent time step t , the agent observes state S_{t}\in\mathcal{S} , executes an action A_{t}\sim\pi(\cdot|S_{t}) , receives reward R_{t+1}\doteq r(S_{t},A_{t}) , and transitions to the next state S_{t+1}\sim p(\cdot|S_{t},A_{t}) . We use P_{\pi} to denote the state transition matrix induced by the policy \pi , i.e., P_{\pi}\quantity[s,s']=\sum_{a\in\mathcal{A}}\pi(a|s)p(s^{\prime}|s,a) . Let d_{\pi}\in\mathbb{R}^{|\mathcal{S}|} be the stationary distribution of the Markov chain induced by the policy \pi . We use D_{\pi} to denote the diagonal matrix whose diagonal is d_{\pi} . Linear Function Approximation. In this paper, we use linear function approximation to approximate value functions v_{\pi}:\mathcal{S}\to\mathbb{R} (to be defined shortly). We consider a feature mapping x:\mathcal{S}\to\mathbb{R}^{d} and a weight vector w\in\mathbb{R}^{d} . We then approximate v_{\pi}(s) with x(s)^{\top}w . We use X\in\mathbb{R}^{{\absolutevalue{\fS}}\times d} to denote the feature matrix, where the s -th row of X is x(s)^{\top} . The approximated state-value function across all states can then be represented as the vector Xw\in\mathbb{R}^{{\absolutevalue{\fS}}} . The goal is thus to find a w such that Xw closely approximates v_{\pi} . Discounted Setting. In the discounted setting, we introduce a discount factor \gamma\in[0,1) . The (discounted) value function v_{\pi}:\mathcal{S}\to\mathbb{R} for policy \pi is defined as \textstyle v_{\pi}(s)\doteq\mathbb{E}\quantity[\sum_{i=0}^\infty\gamma^i R_{t+i+1} \middle| S_t = s] . We define the Bellman operator \mathcal{T}:\mathbb{R}^{{\absolutevalue{\fS}}}\to\mathbb{R}^{{\absolutevalue{\fS}}} as \mathcal{T}v\doteq r_{\pi}+\gamma P_{\pi}v , where r_{\pi}\in\mathbb{R}^{{\absolutevalue{\fS}}} is the vector of expected immediate rewards