Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning
This work addresses the theoretical analysis of widely used algorithms in reinforcement learning, offering incremental improvements in understanding convergence and stepsize selection.
The paper tackled the finite sample analysis of two-timescale stochastic approximation algorithms, developing a novel recipe to provide the first concentration bound (lock-in probability) and introducing a new projection scheme to derive convergence rates for reinforcement learning algorithms like GTD(0), GTD2, and TDC.
Two-timescale Stochastic Approximation (SA) algorithms are widely used in Reinforcement Learning (RL). Their iterates have two parts that are updated using distinct stepsizes. In this work, we develop a novel recipe for their finite sample analysis. Using this, we provide a concentration bound, which is the first such result for a two-timescale SA. The type of bound we obtain is known as `lock-in probability'. We also introduce a new projection scheme, in which the time between successive projections increases exponentially. This scheme allows one to elegantly transform a lock-in probability into a convergence rate result for projected two-timescale SA. From this latter result, we then extract key insights on stepsize selection. As an application, we finally obtain convergence rates for the projected two-timescale RL algorithms GTD(0), GTD2, and TDC.