mlsanityData to 7 Oct 2026

Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis

arXiv 2003.07337 ↗First posted 16 Mar 2020stat.ML cs.LG math.OCcited by 41

Not on the map. Why?

Abstract (arXiv)

We address the problem of policy evaluation in discounted Markov decision processes, and provide instance-dependent guarantees on the ℓ_∞-error under a generative model. We establish both asymptotic and non-asymptotic versions of local minimax lower bounds for policy evaluation, thereby providing an instance-dependent baseline by which to compare algorithms. Theory-inspired simulations show that the widely-used temporal difference (TD) algorithm is strictly suboptimal when evaluated in a non-asymptotic setting, even when combined with Polyak-Ruppert iterate averaging. We remedy this issue by introducing and analyzing variance-reduced forms of stochastic approximation, showing that they achieve non-asymptotic, instance-dependent optimality up to logarithmic factors.

Key facts. Cited by 41 papers in the map (data through 7 Oct 2026). First posted on arXiv 16 Mar 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 9; 2023: 6; 2024: 8; 2025: 6; 2026: 4.

41 papers.

Sort:

By area:

  1. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
  2. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  3. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  4. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  5. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  6. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  7. 2022Stochastic first-order methods for average-reward Markov decision processescited by 30
  8. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  9. 2022Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizescited by 28
  10. 2021Optimal policy evaluation using kernel-based temporal difference methodscited by 24
  11. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  12. 2021Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learningcited by 21
29 more
  1. 2023Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stabilitycited by 20
  2. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  3. 2022Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Setscited by 18
  4. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolationcited by 17
  5. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
  6. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  7. 2022Optimal variance-reduced stochastic approximation in Banach spacescited by 14
  8. 2023Robust Markov Decision Processes without Model Estimationcited by 11
  9. 2023On the Statistical Benefits of Temporal Difference Learningcited by 8
  10. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  11. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  12. 2023Optimal Sample Complexity of Stable Discounted Markov Decision Processescited by 6
  13. 2022Instance-Dependent Confidence and Early Stopping for Reinforcement Learningcited by 5
  14. 2024On Bellman equations for continuous-time policy evaluation I: discretization and approximationcited by 4
  15. 2025A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averagingcited by 4
  16. 2022Krylov-Bellman boosting: Super-linear policy evaluation in general state spacescited by 2
  17. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  18. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  19. 2025Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Samplingcited by 1
  20. 2025Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Ratescited by 1
  21. 2026Multiscale replay: A robust algorithm for stochastic variational inequalities with a Markovian buffercited by 1
  22. 2024Stochastic Optimization with Constraints: A Non-asymptotic Instance-Dependent Analysiscited by 0
  23. 2024Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsizecited by 0
  24. 2024Variance-Reduced Cascade Q-learning: Algorithms and Sample Complexitycited by 0
  25. 2024To bootstrap or to rollout? An optimal and adaptive interpolationcited by 0
  26. 2025Accelerated Distributional Temporal Difference Learning with Linear Function Approximationcited by 0
  27. 2026Sharp asymptotic theory for Q-learning with LDTZ learning rate and its generalizationcited by 0
  28. 2026Is Backpropagation Optimal? When Synthetic Gradients Improve Sample Efficiencycited by 0
  29. 2026Fast and Robust Convergence Rate for TD(0) with Linear Function Approximation, Universal Learning Steps and I.I.D. Samplescited by 0