New TD(0) algorithm achieves robust and fast rates with a single stepsize

A new paper by Wei-Cheng Lee and Francesco Orabona (arXiv:2606.24981) presents a significant advancement in reinforcement learning theory. They study linear TD(0) under Markovian sampling along a single trajectory and show that a simple unprojected version of the algorithm with Polyak-Ruppert (PR) averaging requires only a single stepsize schedule: η_t ∝ 1/(τ_mix log(t) √t), where τ_mix is the mixing time. This stepsize requires no prior knowledge of the curvature parameter ω, a major practical advantage.

The key result is a simultaneous high-probability convergence guarantee. The same stepsize yields both a robust curvature-free rate of Õ(τ_mix/√T) and a fast curvature-dependent rate of Õ(τ_mix²/(ω T)), with the bound taking the minimum of the two. Critically, the iterates are automatically and uniformly bounded with high probability without any projections or stability arguments based on ω. The technical core introduces a Poisson-equation toolkit for geometrically mixing Markov chains that decomposes Markov noise into a martingale term plus a controlled remainder, enabling a new self-bounding inductive argument for pathwise stability.