Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation
This provides a non-asymptotic convergence guarantee for a broad class of value-based RL algorithms, addressing a previously unsolved challenge due to non-linear and two-time-scale structures.
The paper tackles the problem of finite-sample analysis for two time-scale TDC with general smooth function approximation in reinforcement learning, establishing an error bound of O(1/√T) (up to a log factor) for off-policy settings with i.i.d. or Markovian samples.
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.