A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound

Abstract

Policy evaluation in reinforcement learning is often conducted using two-timescale stochastic approximation, which results in various gradient temporal difference methods such as GTD(0), GTD2, and TDC. Here, we provide convergence rate bounds for this suite of algorithms. Algorithms such as these have two iterates, ${\theta }_n$ and $w_n,$ which are updated using two distinct stepsize sequences, ${\alpha }_n$ and ${\beta }_n,$ respectively. Assuming ${\alpha }_n=n^{-\alpha }$ and ${\beta }_n=n^{-\beta }$ with $1>\alpha >\beta >0,$ we show that, with high probability, the two iterates converge to their respective solutions ${\theta }^{\ast }$ and $w^{\ast }$ at rates given by $\Vert {\theta }_n-{\theta }^{\ast }\Vert =\tilde{O}(n^{-\alpha /2})$ and $\Vert w_n-w^{\ast }\Vert =\tilde{O}(n^{-\beta /2});$ here, $\tilde{O}$ hides logarithmic terms. Via comparable lower bounds, we show that these bounds are, in fact, tight. To the best of our knowledge, ours is the first finite-time analysis which achieves these rates. While it was known that the two timescale components decouple asymptotically, our results depict this phenomenon more explicitly by showing that it in fact happens from some finite time onwards. Lastly, compared to existing works, our result applies to a broader family of stepsizes, including non-square summable ones.

References in corpus (4)

• Convergence rate of linear two-time-scale stochastic approximation
• Finite-Sample Analysis of Proximal Gradient TD Algorithms
• Convergence rate and averaging of nonlinear two-time-scale stochastic approximation algorithms
• Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning

Cited by in corpus (4)

• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
• Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms