English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Stochastic approximation (SA) is an iterative algorithm to find the fixedpoint of an operator given noisy samples of this operator. SA appears in manyareas such as optimization and Reinforcement Learning (RL). When implemented inpractice, the noise that appears in the update of RL algorithms is naturallyMarkovian. Furthermore, in some settings, such as gradient TD, SA is employedin a two-time-scale manner. The mix of Markovian noise along with thetwo-time-scale structure results in an algorithm which is complex to analyzetheoretically. In this paper, we characterize a tight convergence bound for theiterations of linear two-time-scale SA with Markovian noise. Our results showthe convergence behavior of this algorithm given various choices of step sizes.Applying our result to the well-known TDC algorithm, we show the first$O(1/\epsilon)$ sample complexity for the convergence of this algorithm,outperforming all the previous work. Similarly, our results can be applied toestablish the convergence behavior of a variety of RL algorithms, such asTD-learning with Polyak averaging, GTD, and GTD2.

Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noise