Research map / Reinforcement learning / Policy gradient and actor-critic

Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features

NeurIPS 2026 · Reinforcement learning › Policy gradient and actor-critic · approach: Temporal-difference and discounting theory · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proves almost sure convergence of linear TD without linearly independent features, showing weight iterates reach a bounded set on which value estimates agree a.e. and establishing local stability of weights.

Problem

Linear TD convergence proofs traditionally require linearly independent features, an assumption that fails in many practical settings (neural features, continual learning, compatible features); the question is whether linear TD converges a.s. with arbitrary features.

Approach

Characterizes TD fixed points under arbitrary features (all fixed points yield the same value a.e.), analyzes the mean ODE via Jordan normal form and LaSalle's theorem to show trajectories converge and bounded invariant sets lie in the fixed-point set, then applies stochastic approximation theory to get weight convergence to a bounded invariant set, without modifying linear TD.

Key results

• Linear TD weight iterates are stable (sup_t ||w_t|| < infinity a.s.) under arbitrary features via a Lyapunov argument using energy U(w)=||w-w*||^2+||w*||^2.
• For any w0, the mean ODE trajectory converges to an initial-condition-dependent TD fixed point w_infinity(w0) in W*, and all TD fixed points give the same value a.e.
• Linear TD iterates converge a.s. (for a.e. state values) to a bounded invariant set of the mean ODE, which is contained in the TD fixed-point set; a local stability corollary holds along a convergent subsequence.

Limitations

• Full weight convergence to a single point is left open; only convergence to a bounded invariant set is established.
• Requires a compact state space and Poisson-equation and LIL assumptions on the Markov chain.

Experimental setup

Baselines: Tsitsiklis and Van Roy linear TD analysis Lakshminarayanan and Szepesvari (linearly independent features)

Builds on: linear TD(0) ODE method for stochastic approximation LaSalle's invariance principle Borkar-Meyn stability theorem

Closest papers by meaning

• Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features (NeurIPS 2025 · similarity 0.93)
• Towards Parameter-Free Temporal Difference Learning (ICML 2026 · similarity 0.92)
• TD Convergence: An Optimization Perspective (NeurIPS 2023 · similarity 0.92)
• A Unifying View of Linear Function Approximation in Off-Policy RL Through Matrix Splitting and Preconditioning (NeurIPS 2025 · similarity 0.89)
• An Improved Finite-time Analysis of Temporal Difference Learning with Deep Neural Networks (ICML 2024 · similarity 0.88)
• Discerning Temporal Difference Learning (AAAI 2024 · similarity 0.88)