mlsanityData to 7 Oct 2026

Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation

arXiv 2104.02836 ↗First posted 7 Apr 2021cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

Temporal-difference learning with gradient correction (TDC) is a two time-scale algorithm for policy evaluation in reinforcement learning. This algorithm was initially proposed with linear function approximation, and was later extended to the one with general smooth function approximation. The asymptotic convergence for the on-policy setting with general smooth function approximation was established in [bhatnagar2009convergent], however, the finite-sample analysis remains unsolved due to challenges in the non-linear and two-time-scale update structure, non-convex objective function and the time-varying projection onto a tangent plane. In this paper, we develop novel techniques to explicitly characterize the finite-sample error bound for the general off-policy setting with i.i.d. or Markovian samples, and show that it converges as fast as mathcal O(1/√ T) (up to a factor of mathcal O(log T)). Our approach can be applied to a wide range of value-based reinforcement learning algorithms with general smooth function approximation.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 21 of its 42 references that are in the map. First posted on arXiv 7 Apr 2021.

Builds on

21 of 42 references.

References · 21

  1. 2018Spectral Normalization for Generative Adversarial Networkscited by 1,618
  2. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  3. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  4. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  5. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  6. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
  7. 2017Implicit Regularization in Deep Learningcited by 90
  8. 2019Finite-Sample Analysis for SARSA with Linear Function Approximationcited by 85
  9. 2020Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noisecited by 52
  10. 2019A Finite-Time Analysis of Q-Learning with Neural Network Function Approximationcited by 47
  11. 2019Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learningcited by 40
  12. 2020Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performancecited by 35
9 more
  1. 2020Finite-Sample Analysis of Proximal Gradient TD Algorithmscited by 32
  2. 2019Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samplescited by 31
  3. 2019A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Boundcited by 31
  4. 2020Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithmscited by 19
  5. 2020Finite-sample Analysis of Greedy-GQ with Linear Function Approximation under Markovian Noisecited by 17
  6. 2018Finite Sample Analysis of the GTD Policy Evaluation Algorithms in Markov Settingcited by 12
  7. 2020Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysiscited by 12
  8. 2019Finite-Sample Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximationcited by 9
  9. 2021Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexitycited by 7

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 2; 2023: 2; 2024: 3.

8 papers.

  1. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 95
  2. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
  3. 2024Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learningcited by 8
  4. 2024Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applicationscited by 7
  5. 2024Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Datacited by 4
  6. 2022Finite-Time Error Bounds for Greedy-GQcited by 3
  7. 2022Finite-Time Analysis of Fully Decentralized Single-Timescale Actor-Criticcited by 1
  8. 2023Gauss-Newton Temporal Difference Learning with Nonlinear Function Approximationcited by 0