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

On Double Descent in Reinforcement Learning with LSTD and Random Features

ICLR 2024 · Reinforcement learning › Policy gradient and actor-critic · approach: Regularized scalable deep value learning · 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.

Analyzes regularized LSTD with random features in a double asymptotic regime (parameters and visited states growing at constant ratio), deriving deterministic limits for empirical and true MSBE that exhibit a double descent peak at N/m=1.

Problem

How network size (parameter/visited-state ratio) and l2-regularization affect TD value-function learning performance, including whether double descent occurs in RL as in supervised learning.

Approach

Applies random matrix theory in a double asymptotic regime (N, m, d to infinity at constant ratio) to regularized LSTD with random ReLU features, giving deterministic equivalents for the resolvent of a non-symmetric matrix (discount factor breaks positive-definiteness) and for empirical and true MSBE with correction terms that produce a double descent peak.

Key results

• Empirical and true MSBE from the asymptotic theory closely match numerical results averaged over 30 instances on Taxi-v3, gridworld and synthetic MRPs.
• True MSBE shows a double descent peak around N/m=1 for small l2-regularization (lambda=1e-9), while the empirical MSBE shows no double descent.
• The correction factor delta falls from about 1e7 for N<m to about 1e1 for N>m at lambda=1e-9 on Taxi-v3.

Measured effects reported in the paper

Surprising findings

• The empirical MSBE is not necessarily lower for over-parameterized models, and it is not an increasing function of l2-regularization.
• The discount factor gamma has little effect on the double descent in the MSBE.

Limitations

• Analysis restricted to on-policy policy evaluation with linear TD (regularized LSTD) and a single hidden layer random feature model in the lazy training regime.
• Theory is asymptotic; experiments use small fixed-size MRPs where the asymptotic predictions are assessed empirically.
• Assumes an assumption on the bounded eigenspectrum and an O(1/sqrt(m)) bound on the transition matrix approximation that are not fully proven in general.

Experimental setup

Datasets: Taxi-v3 synthetic ergodic MRP gridworld MRP (20x20 random policy)

Benchmarks: Taxi-v3 synthetic ergodic MRP gridworld MRP

Metrics: mean-squared Bellman error mean-squared value error correction factor delta

Baselines: empirical MSBE true MSBE

Builds on: regularized LSTD random features double descent analysis in supervised learning

Closest papers by meaning

• An Improved Finite-time Analysis of Temporal Difference Learning with Deep Neural Networks (ICML 2024 · similarity 0.89)
• The surprising efficiency of temporal difference learning for rare event prediction (NeurIPS 2024 · similarity 0.88)
• Discerning Temporal Difference Learning (AAAI 2024 · similarity 0.87)
• Reinforcement Learning Finetunes Small Subnetworks in Large Language Models (NeurIPS 2025 · similarity 0.87)
• Balancing Context Length and Mixing Times for Reinforcement Learning at Scale (NeurIPS 2024 · similarity 0.87)
• Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features (NeurIPS 2026 · similarity 0.87)