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

Abstract

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/\sqrt{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.

arXiv commentAccepted by NeurIPS 2021

References in corpus (17)

• Spectral Normalization for Generative Adversarial Networks
• Convergence rate of linear two-time-scale stochastic approximation
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• Finite-Sample Analysis of Proximal Gradient TD Algorithms
• On the Global Convergence Rates of Softmax Policy Gradient Methods
• Implicit Regularization in Deep Learning
• Finite-Sample Analysis for SARSA with Linear Function Approximation
• Convergence rate and averaging of nonlinear two-time-scale stochastic approximation algorithms
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples
• Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization
• Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise
• Finite Sample Analysis of the GTD Policy Evaluation Algorithms in Markov Setting
• Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning
• Finite-Sample Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximation
• Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity
• Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis

Cited by in corpus (1)

• Online Robust Reinforcement Learning with Model Uncertainty