2020

Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise

Kaledin, Maxim, Moulines, Eric, Naumov, Alexey et al.

Understand

Linear two-timescale stochastic approximation (SA) scheme is an important class of algorithms which has become popular in reinforcement learning (RL), particularly for the policy evaluation problem.

Recently, a number of works have been devoted to establishing the finite time analysis of the scheme, especially under the Markovian (non-i.i.d.) noise settings that are ubiquitous in practice.
In this paper, we provide a finite-time analysis for linear two timescale SA.
Our bounds show that there is no discrepancy in the convergence rate between Markovian and martingale noise, only the constants are affected by the mixing time of the Markov chain.

Built on

A stochastic approximation method
Herbert Robbins and Sutton Monro · 1951
Earlier work this paper cites.
Learning to predict by the methods of temporal differences
Richard S. Sutton · 1988
Earlier work this paper cites.
On the generation of markov decision processes
T. W. Archibald, K. I. M. McKinnon, and L. C. Thomas · 1995
Earlier work this paper cites.
Residual algorithms: Reinforcement learning with function approximation
Leemon Baird · 1995
Earlier work this paper cites.
Stochastic approximation with two time scales
Vivek S Borkar · 1997
Earlier work this paper cites.
An analysis of temporal-difference learning with function approximation
J. N. Tsitsiklis and B. Van Roy · 1997
Earlier work this paper cites.
Dynamics of stochastic approximation algorithms
Michel Benaïm · 1999
Earlier work this paper cites.
Stochastic approximation and recursive algorithms and applications , volume 35
Harold Kushner and G George Yin · 2003
Earlier work this paper cites.

Similar

Convergence rate of linear two-time-scale stochastic approximation
Vijay R. Konda and John N. Tsitsiklis · 2004
Cited alongside, same era.
Almost sure convergence of two time-scale stochastic approximation algorithms
Vladislav Tadic · 2004
Cited alongside, same era.
Convergence rate and averaging of nonlinear two-time-scale stochastic approximation algorithms
Abdelkader Mokkadem, Mariane Pelletier, et al · 2006
Cited alongside, same era.
Asymptotic analysis of temporal-difference learning algorithms with constant step-sizes
Vladislav Tadic · 2006
Cited alongside, same era.
Stochastic Approximation: A Dynamical Systems Viewpoint
Vivek S Borkar · 2008
Cited alongside, same era.
Advanced Mathematical Tools for Automatic Control Engineers: Deterministic Techniques
Alexander S. Poznyak · 2008
Cited alongside, same era.
Off-policy learning with eligibility traces: A survey
Matthieu Geist and Bruno Scherrer · 2014
Cited alongside, same era.
Finite-sample analysis of proximal gradient td algorithms
Bo Liu, Ji Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, and Marek Petrik · 2015
Cited alongside, same era.
Finite sample analyses for TD(0) with function approximation
Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor
Cited in the paper.
Finite sample analysis of two-timescale stochastic approximation with applications to reinforcement learning
Gal Dalal, Gugan Thoppe, Balázs Szörényi, and Shie Mannor
Cited in the paper.
A convergent o ⁡ ( n ) o(n) temporal-difference algorithm for off-policy learning with linear function approximation
Richard S Sutton, Hamid R Maei, and Csaba Szepesvári
Cited in the paper.
Fast gradient-descent methods for temporal-difference learning with linear function approximation
Richard S Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora
Cited in the paper.

Then

A finite time analysis of temporal difference learning with linear function approximation
Jalaj Bhandari, Daniel Russo, and Raghav Singal · 2018
Later among the works it cites.
Markov chains
Randal Douc, Eric Moulines, Pierre Priouret, and Philippe Soulier · 2018
Later among the works it cites.
Linear stochastic approximation: How far does constant step-size and iterate averaging go?
Chandrashekar Lakshminarayanan and Csaba Szepesvari · 2018
Later among the works it cites.
A tale of two-timescale reinforcement learning with the tightest finite-time bound
Original
Gal Dalal, Balazs Szorenyi, and Gugan Thoppe · 2019
Later among the works it cites.
Finite-time analysis and restarting scheme for linear two-time-scale stochastic approximation
Original
Thinh T Doan · 2019
Later among the works it cites.
Finite-time performance bounds and adaptive learning rate selection for two time-scale reinforcement learning
Harsh Gupta, R Srikant, and Lei Ying · 2019
Later among the works it cites.
Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning
R. Srikant and Lei Ying · 2019
Later among the works it cites.
Two time-scale off-policy td learning: Non-asymptotic analysis over markovian samples
Tengyu Xu, Shaofeng Zou, and Yingbin Liang · 2019
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…