A Finite-Time Analysis of TD Learning with Linear Function Approximation without Projections nor Strong Convexity

Wei-Cheng Lee, Francesco Orabona · 2025

Read A Finite-Time Analysis of TD Learning with Linear Function Approximation without Projections nor Strong Convexity by Wei-Cheng Lee, Francesco Orabona (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-2506-01052.txt.

Introduction

Wei-Cheng Lee and Francesco Orabona prove a convergence result for temporal difference learning, a core method in reinforcement learning. Their 2025 paper, whose head title stresses a robust rate, studies the method with linear function approximation. Past proofs in the hard setting leaned on an artificial step: projecting each update into a fixed bounded set.

The authors remove that crutch. They show the plain, unprojected method converges at the stated rate in expectation, even with Markovian noise in the data. No extra regularity condition is needed, only a small change to the learning rate. Their analysis finds a self-bounding trait in the updates, which keeps the iterates in line on its own. The result closes a problem left open since 2018.

Catalog record

CREATORWei-Cheng Lee, Francesco Orabona
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-01052

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Finite-Time Analysis of TD Learning with Linear Function Approximation without Projections nor Strong Convexity Wei-Cheng Lee, Francesco Orabona Abstract We investigate the finite-time convergence properties of Temporal Difference (TD) learning with linear function approximation, a cornerstone algorithm in reinforcement learning. While prior work has established convergence guarantees, these results typically rely on the assumption that each iterate is projected onto a bounded set or that the learning rate is set according to the unknown strong convexity constant—conditions that are both artificial and do not match the current practice. In this paper, we challenge the necessity of such assumptions and present a refined analysis of TD learning. We show that the simple projection-free variant converges with a rate of 𝒪 ~ ​ ( ‖ 𝜽 ∗ ‖ 2 2 T ) \tilde{\mathcal{O}}(\frac{\left\|{\bm{\theta}^{*}}\right\|^{2}_{2}}{\sqrt{T}}) , even in the presence of Markovian noise. Our analysis reveals a novel self-bounding property of the TD updates and exploits it to guarantee bounded iterates. 1 Introduction Temporal Difference (TD) learning, first introduced by Sutton 1988 , is a cornerstone of modern reinforcement learning. It provides a model-free approach for policy evaluation, estimating the value function of a given policy within a Markov Decision Process (MDP). The versatility of TD methods has led to their application in diverse domains, including games ( Silver et al. 2016 ) , robotics ( Gu et al. 2017 ) , and autonomous systems ( Chen et al. 2015 ) . At its core, TD learning iteratively updates value function estimates based on the difference between predictions at successive time steps. Despite its conceptual simplicity and widespread use, the theoretical analysis of TD learning, particularly with linear function approximation in large state spaces, presents considerable challenges. Early seminal work by Tsitsiklis and Van Roy 1996 established asymptotic convergence conditions by framing TD as a stochastic approximation algorithm. Instead, understanding the non-asymptotic behavior and finite-time performance of TD has been an active area of research more recently. Challenges primarily arise from the correlated nature of samples generated by the underlying Markov chain, which can introduce bias and dependencies into the learning updates. Several studies have provided finite-time analyses under various assumptions. For instance, analyses assuming i.i.d. samples ( Dalal et al. 2018 ; Lakshminarayanan and Szepesvari 2018 ) offered initial insights but did not fully capture the complexities of Markovian sampling. There are also efforts to analyze TD under Markovian noise. For example, Bhandari et al. 2018 provided a non-asymptotic analysis for TD with linear function approximation, but their results for the Markovian setting relied on projecting iterates onto a compact set. This projection step, while common in stochastic approximation for ensuring stability and simplifying analysis ( Kushner 2010 ) , can be a limitation as it modifies the standard algorithm and may not always be practical or desired. Instead, Srikant and Ying 2019 ; Mitra 2024 analyzed TD with a constant step-size without projections, but implicitly assuming knowledge of the strong convexity parameter of the objective function. Given that the TD algorithm is routinely used without such restrictions, one might wonder if the current analyses fail to fully grasp the nature of the TD update. Contributions. In this paper, for the first time we provide a finite-time analysis of TD(0) with linear function approximation under Markovian observations without the requirement of iterate projection . Our main contribution is to demonstrate that learning rates of the form \frac{1}{\sqrt{t}\ln^{2}T} are sufficient to guarantee a self-bounding property of TD: The iterate are constrained in expectation in a bounded domain around the optimal solution. Our analysis is fundamentally different from previous ones that aimed at proving that the update is a noisy contraction. We also show a convergence rate \tilde{\mathcal{O}}(\frac{\left\|{\bm{\theta}^{*}}\right\|^{2}}{\sqrt{T}}) for the objective function implicitly optimized by the TD algorithm, as defined in Liu and Olshevsky 2021 . 2 Related Work The initial theoretical understanding of how TD learning with linear function approximation converges over time was established in Tsitsiklis and Van Roy 1996 , which framed TD methods as types of stochastic approximation algorithms ( Kushner 2010 ) . However, this early work did not derive convergence rates in finite time. Subsequent research ( Korda and La 2015 ; Lakshminarayanan and Szepesvari 2018 ; Dalal et al. 2018 ) did provide these finite-time convergence rates. However, a significant limitation of these later studies was their reliance on the assumption that the data are drawn independently from the stationary distribution. In practice, data is usually collected sequentially from a single path through the Markov chain, introducing time-based correlations between samples. These correlations make analyzing even the basic TD(0) method challenging. Bhandari et al. 2018 offered the first finite-time analysis for TD learning using this more realistic Markovian (sequentially correlated) data, by drawing parallels to stochastic gradient descent. However, this analysis required a projection step in the algorithm to control the magnitude of the estimates of updates. Srikant and Ying 2019 was reportedly the first to provide finite-time mean-square error bounds for TD learning with linear function approximation under Markovian sampling without needing a projection step. This was achieved using a control-theoretic approach based on Lyapunov theory. While elegant, the analysis in Srikant and Ying 2019 relies on assuming a minimal curvature of the objective function, that might make the rate arbitrarily slow. A similar proof analysis with similar shortcomings was also done in Mitra 2024 . We discuss more in details these methods in Section 5 . We study the objective function proposed in Liu and Olshevsky 2021 , that extends the one used in prior work by adding a term that is proportional to the discount factor \gamma . Note that Liu and Olshevsky 2021 also provide finite-time convergence guarantees, but they also need a projection step to control the norm of the iterates. Our proof method is fundamentally different from previous ones, that aimed at establishing a contraction. Instead, we prove that the iterates are bounded because similar to the ones of SGD. In turn, SGD can have bounded iterates even for non-strongly convex objectives, as proved in, for example, Xiao 2010 ; Orabona and Pál 2021 ; Ivgi et al. 2023 for various update schemes and assumptions on the objective functions. 3 Notation and Assumptions This section reviews the required background on Markov Decision Processes (MDPs) and on temporal-difference learning with linear function approximation. For a comprehensive treatment of these topics, the reader may consult Mannor et al. 2022 . 3.1 Discounted Markov Decision Processes A discounted-reward MDP is a five-tuple (\mathcal{S},\mathcal{A},\bm{P},r,\gamma), where • \mathcal{S}=[n]\!:=\{1,2,\dots,n\} is a finite state space, • \mathcal{A} is a finite action space, • P(s^{\prime}\mid s,a) denotes the transition probability from state s to state s^{\prime} under action a , • r(s,a,s^{\prime})\in\mathbb{R}_{\geq 0} is a deterministic reward, and • \gamma\in(0,1) is the discount factor. A major goal of reinforcement learning is to find a policy that maximizes the expected discounted sum of rewards, \bm{V} . Policies and value functions. A stationary policy is a mapping \mu:\mathcal{S}\times\mathcal{A}\rightarrow[0,1] with \sum_{a}\mu(s,a)=1 for every state s . The value function associated with \mu is given by V^{\mu}(s)\;=\;\mathbb{E}_{\mu}\!\left[\sum_{t=0}^{\infty}\gamma^{t}\,r(s_{t},a_{t},s_{t+1})\right],\qquad s\in\mathcal{S}~. Induced Markov chain. A policy \mu induces the transition matrix P^{\mu}(s,s^{\prime})\;=\;\sum_{a\in\mathcal{A}}\mu(s,a)\,P(s^{\prime}\mid s,a),\qquad s,s^{\prime}\in\mathcal{S}~. Throughout, \mu -induced rewards are shortened to r(s,s^{\prime}):=\sum_{a}\mu(s,a)\,r(s,a,s^{\prime}) and are assumed bounded

Read the complete text