Research map / Reinforcement learning / Policy gradient and actor-critic
Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features
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.
Gives the first L2 finite-sample rates for linear TD(lambda) with arbitrary (possibly linearly dependent) features in discounted and average-reward settings, via a new SA result converging to a solution set using distance-to-set Lyapunov function.
Problem
Finite-sample convergence of linear TD(lambda) policy evaluation when features are linearly dependent, so the solution set of the projected Bellman equation may be non-unique and average-reward solutions may not even be known to exist.
Approach
Uses the squared distance to the solution set, L(w)=1/2 d(w,W*)^2, as Lyapunov function (1-smooth, gradient = w - projection), with a feature decomposition X = X1 + 1 theta^T for the average-reward case, and a general SA theorem for convergence to possibly unbounded convex sets, without any algorithmic change.
Key results
- Theorem gives E[d(w_t,W*)^2] rate O(ln t / t) for xi=1 in discounted setting with arbitrary features, matching full-rank analyses.
- Average-reward TD(lambda) with arbitrary features obtains E[(J_t - J)^2 + d(w_t, W̄*)^2] convergence rate under large c_beta.
- Simulation on rank-3 features in a 15-state Boyan chain shows weight convergence to a set.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow arbitrary, potentially linearly dependent features | Linear TD(λ) in the discounted setting · Discounted setting (γ < 1) | L² convergence rate: \mathcal{O}(\ln t/t) | Helped |
| Allow arbitrary, potentially linearly dependent features | Average-reward linear TD(λ) · Average-reward setting (γ = 1) | L² convergence rate | Helped |
| Use distance to the solution set as the Lyapunov function | Linear TD(λ) analysis with arbitrary features · Discounted setting (γ < 1) | L² convergence rate | Helped |
| Use a feature-matrix decomposition separating the constant-vector component | Average-reward linear TD(λ) analysis · Average-reward setting (γ = 1) | L² convergence rate | Helped |
Limitations
- Focuses only on linear function approximation; neural networks left for future work
- Only L2 convergence rates; almost sure, Lp, and high-probability bounds not established
- Requires large alpha, t0, or c_beta for constants to satisfy conditions
Experimental setup
Datasets: variant of Boyan's chain (15 states, 5 actions)
Benchmarks: variant of Boyan's chain
Metrics: distance to solution set convergence curves
Baselines: Patil et al. 2023 linear TD analysis Zhang et al. 2021 TD with arbitrary features (asymptotic) Tsitsiklis and Van Roy 1997 Chen et al. 2023 average-reward TD
Builds on: TD(lambda) linear TD(lambda) finite-sample analyses Tsitsiklis and Van Roy linear TD analysis Zhang et al. almost-sure convergence with arbitrary features
Closest papers by meaning
- Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features (NeurIPS 2026 · similarity 0.93)
- Finite Sample Analyses for TD(0) With Function Approximation (AAAI 2018 · similarity 0.91)
- A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximation (NeurIPS 2025 · similarity 0.89)
- A Unifying View of Linear Function Approximation in Off-Policy RL Through Matrix Splitting and Preconditioning (NeurIPS 2025 · similarity 0.88)
- The surprising efficiency of temporal difference learning for rare event prediction (NeurIPS 2024 · similarity 0.87)
- Policy Evaluation for Variance in Average Reward Reinforcement Learning (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.