Research map / Learning theory and algorithms / Sample complexity
An Improved Finite-time Analysis of Temporal Difference Learning with Deep Neural Networks
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.
Improves the finite-time sample complexity of neural TD learning with L-layer networks under Markovian sampling from O(eps^-2) to O(eps^-1) via a subspace decomposition argument, and extends the result to minimax neural Q-learning for zero-sum Markov games.
Problem
Finite-sample analysis of neural temporal difference (TD) learning and Q-learning with multi-layer networks under non-i.i.d. Markovian sampling; existing bounds give O(eps^-2) sample complexity while O(eps^-1) is expected.
Approach
A subspace decomposition of parameters into range and kernel of the feature-covariance matrix Sigma_pi lets the analysis track the distance to a fixed point only in the range space, where the linearized Q-function is strongly convex, yielding O(1/T) convergence of the local linearization and hence O(eps^-1) sample complexity; the positive-definiteness assumption is relaxed to a minimum non-zero si
Key results
- Theoretical result: neural TD with L-layer networks achieves O(eps^-1) sample complexity under Markovian sampling, improving the O(eps^-2) bounds of prior work.
- Extends the analysis to minimax neural Q-learning for two-player zero-sum Markov games with O(eps^-1) sample complexity, relaxing strict positive definiteness to semi-definiteness.
- Experiments show larger width m yields faster TD convergence and the ratio sigma_max/sigma_min of Sigma_pi approaches a constant as m grows, supporting the assumption empirically.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed subspace analysis instead of the prior neural Q-learning analysis | L-layer neural Q-learning · Neural Q-learning sample complexity | sample complexity: \mathcal{O}(1/\epsilon^2) -> \mathcal{O}(1/\epsilon) | Helped |
| Increase network width | Neural TD learning · OpenAI Gym tasks | TD error | Helped |
Limitations
- Relies on strong assumptions: fast mixing of the Markov chain, stationary initial distribution, and a minimum non-zero singular value lower bound on Sigma_pi.
- Analysis restricted to a local linearization within a bounded set S_omega around initialization (lazy/NTK regime) with large width m.
- Experiments are small-scale two-layer ELU networks on simple discrete/grid-discretized environments, and Q-learning result requires an extra regularity assumption.
Experimental setup
Datasets: OpenAI Gym tasks (discrete and continuous state spaces)
Benchmarks: OpenAI Gym tasks (TD error convergence)
Metrics: TD error ratio of largest to smallest non-zero singular value of Sigm
Baselines: Neural TD O(eps^-2) analysis (two-layer ReLU) Neural TD O(eps^-2) analysis (L-layer ReLU) adaptive neural TD O(eps^{-2/(2-alpha)}) Neural Q-learning O(eps^-2) fitted Q-iteration O(eps^-1)
Builds on: neural TD finite-time analysis (O(eps^-2)) linear Q-learning finite-time analysis over-parameterized neural network optimization theory Bhandari et al. TD analysis under Markovian sampling
Closest papers by meaning
- Towards Parameter-Free Temporal Difference Learning (ICML 2026 · similarity 0.93)
- Finite-Time Analysis of Adaptive Temporal Difference Learning with Deep Neural Networks (NeurIPS 2022 · similarity 0.93)
- On Double Descent in Reinforcement Learning with LSTD and Random Features (ICLR 2024 · similarity 0.89)
- Discerning Temporal Difference Learning (AAAI 2024 · similarity 0.89)
- Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features (NeurIPS 2026 · similarity 0.88)
- The surprising efficiency of temporal difference learning for rare event prediction (NeurIPS 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.