A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak–Ruppert Averaging

Wei-Cheng Lee, Francesco Orabona · 2026

Read A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak–Ruppert Averaging by Wei-Cheng Lee, Francesco Orabona (2026) 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-2606-24981.txt.

Introduction

Wei-Cheng Lee and Francesco Orabona prove that one stepsize schedule is enough for temporal difference learning. TD(0), a reinforcement learning algorithm, runs on data from a Markov trajectory. Their version is plain: no projection step, with Polyak Ruppert averaging of the iterates. The stepsize shrinks like one over the square root of time, adjusted by the chain's mixing time and a log factor. Crucially, it needs no knowledge of the curvature parameter that earlier analyses used.

Two results follow with high probability. The iterates stay bounded, with no projection and no stability argument based on curvature. The averaged estimate then converges at the better of two rates: a curvature free rate, and a faster one when curvature is favourable. A Poisson equation toolkit for mixing chains does the work, splitting Markov noise into a martingale part plus a remainder, and a self bounding induction gives pathwise stability.

Catalog record

CREATORWei-Cheng Lee, Francesco Orabona
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE126 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.24981

Browse the full library · About the Tower of Babel

Full text

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

A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak–Ruppert Averaging Wei-Cheng Lee, Francesco Orabona Abstract We study linear TD(0) under Markovian sampling, where data are generated along a single trajectory. We provide high-probability guarantees for a plain unprojected TD(0) algorithm with Polyak–Ruppert (PR) averaging, using a single stepsize schedule η t ∝ 1 / ( τ mix ​ log ⁡ ( t ) ​ t ) \eta_{t}\propto 1/(\tau_{\mathrm{mix}}\log(t)\,\sqrt{t}) that depends on mixing time but requires no prior knowledge of the curvature parameter ω \omega . Our first result shows that such a choice of the stepsize guarantees that the TD(0) iterates are automatically and uniformly bounded with high probability , without projections and without any stability argument based on ω \omega . Building on this result, we establish a simultaneous high-probability convergence guarantee for the PR average: the same stepsize yields both a robust curvature-free 𝒪 ~ ​ ( τ mix / T ) \widetilde{\mathcal{O}}(\tau_{\mathrm{mix}}/\sqrt{T}) rate and a fast curvature-dependent 𝒪 ~ ​ ( τ mix 2 / ( ω ​ T ) ) \widetilde{\mathcal{O}}(\tau_{\mathrm{mix}}^{2}/(\omega T)) rate, with the bound taking the minimum of the two. The core technical ingredient is a Poisson-equation toolkit for geometrically mixing Markov chains, which decomposes Markov noise into a martingale term plus a controlled remainder and enables a new self-bounding inductive argument for pathwise stability. Keywords: Reinforcement Learning, Temporal Difference Learning, Finite-Time Analysis, Markovian Noise, Stochastic Approximation 1 Introduction Temporal-difference (TD) learning is one of the central algorithmic primitives in reinforcement learning, used for policy evaluation and as a building block for control methods such as actor–critic. When the state space is large, TD is typically combined with function approximation; in the linear case, the resulting TD(0) recursion admits a clean stochastic-approximation interpretation and converges asymptotically under standard conditions ( 32 ; 33 ; 9 ) . Despite this classical theory, obtaining finite-time , high-probability guarantees for TD(0) remains challenging, especially in the practically relevant Markovian sampling regime where data are generated along a single trajectory. A major obstacle is that TD(0) is not a standard stochastic gradient method: Even in the linear setting, the update is generally biased and non-symmetric, and the noise is temporally correlated. Moreover, the magnitude of the TD(0) updates depends on the magnitude of the iterates. Therefore, existing non-asymptotic analyses rely on additional structure to control the iterates. One common approach is to enforce boundedness via projections onto a known ball ( 1 , e.g.,) , which simplifies concentration arguments but changes the algorithm and requires a priori knowledge of a suitable radius (often tied implicitly to the problem curvature). A second approach is to exploit a contractive/curvature structure of the mean dynamics to argue stability without projections; however, this typically yields stepsize conditions or stability bounds that depend on an unknown curvature parameter, which becomes arbitrarily slow when the curvature is arbitrarily small. Ideally, one would like to use a single stepsize rule that simultaneously allows us to obtain rates that are (i) robust (curvature-free) and (ii) fast when curvature is favorable. Such a stepsize would adapt to the better of the robust and fast high-probability upper bounds, without prior knowledge of the curvature. Robust and fast rates. To explain the distinction between robust and fast rates, we first briefly describe the potential function we study ( 22 ; 16 ) (formally introduced later in ( 2 )), which naturally captures the TD fixed point error under Markovian sampling. This potential always has positive curvature \omega>0 , so one can hope for a ‘‘fast’’ rate of order 1 1 1 The notation \widetilde{\mathcal{O}} suppresses logarithmic factors.. \widetilde{\mathcal{O}}(\frac{1}{\omega T}) (up to mixing and logarithmic factors). On the other hand, even without curvature assumptions, one can always achieve a “robust” rate of order \widetilde{\mathcal{O}}(\frac{1}{\sqrt{T}}) , again up to mixing and logs. It is obvious that, in the finite-time regime, one rate can be better than the other depending on \omega , so both rates should be pursued in different situations. Now, prior work typically achieves these two regimes with different stepsize choices and additional algorithmic modifications ( 1 , e.g.,) . Moreover, the projection-free high-probability analyses under Markovian noise that we are aware of rely on stability arguments whose constants deteriorate with \omega ( 27 ; 6 , e.g.,) . As far as we know, obtaining both rates simultaneously with high probability with a single stepsize choice that is independent of \omega and without projections has not previously been established for TD(0) . In particular, the key technical difficulty in achieving such a result is to control the random iterates, \bm{\theta}_{t} , pathwise . Without projections, the update magnitude scales with \|\bm{\theta}_{t}\| , and a naive concentration analysis becomes circular: to bound the error one needs bounded updates, but bounded updates require bounded iterates. Moreover, the need to obtain robust rates (i.e., independent of \omega ) rules out any strategy that shows that the iterates are bounded through a contractive argument based on \omega . Our approach: a self-bounding argument via Poisson equations. In this paper, we show that a simple stepsize, proportional to \frac{1}{\tau_{\mathrm{mix}}\log t\sqrt{t}} and independent of \omega , guarantees that TD(0) achieves both fast and robust rates with high probability. Our main technical novelty to circumvent the above issues is a new self-bounding argument that closes this loop with high probability without appealing to curvature \omega and without artificial projections. Concretely, we develop a Poisson-equation toolkit for geometrically mixing Markov chains that decomposes additive Markov noise into a martingale term plus a controlled remainder. This decomposition allows us to control the Markovian bias terms that appear in the basic potential expansion of TD, and to run an induction in which boundedness at times \leq t-1 implies boundedness at time t . The resulting uniform bound on \sup_{t}\ \|\bm{\theta}_{t}\| holds with high probability and is independent of the curvature \omega . Once boundedness is established, we can analyze the convergence guarantee. The bounded-iterates event provides the missing ingredient needed to control the quadratic variation of the martingale terms (again through the Poisson decomposition), yielding high-probability bounds for the averaged iterate \bar{\bm{\theta}}_{T} . Importantly, the same stepsize delivers: • a curvature-free robust rate of \widetilde{\mathcal{O}}(\frac{1}{\sqrt{T}}) , through a classic averaged-stochastic-gradient-descent-like analysis, as one would expect from the choice of the stepsize; • a curvature-dependent fast rate \widetilde{\mathcal{O}}(1/(\omega T)) , without requiring \omega to set the stepsize, thanks to a Polyak–Ruppert averaging analysis. 2 Related Work In this section, we briefly survey the main results on the convergence guarantees for TD learning with linear function approximation, as well as the main tools we use in our proofs. Later, in Section 5 , we will give a detailed comparison in terms of convergence rates. Early convergence results for TD learning with linear function approximation trace back to 33 , who interpreted TD updates through the lens of stochastic approximation ( 9 ) . While foundational, that theory is largely asymptotic and does not yield explicit non-asymptotic rates. Finite-time guarantees were later developed in a sequence of works ( 8 ; 10 ; 5 ) , but these analyses typically assume i.i.d. samples drawn from the stationary distribution. This assumption sidesteps the temporal dependence present in

Read the complete text