2020

Reanalysis of Variance Reduced Temporal Difference Learning

Xu, Tengyu, Wang, Zhe, Zhou, Yi et al.

Understand

Temporal difference (TD) learning is a popular algorithm for policy evaluation in reinforcement learning, but the vanilla TD can substantially suffer from the inherent optimization variance.

A variance reduced TD (VRTD) algorithm was proposed by Korda and La (2015), which applies the variance reduction technique directly to the online TD learning with Markovian samples.
In this work, we first point out the technical errors in the analysis of VRTD in Korda and La (2015), and then provide a mathematically solid analysis of the non-asymptotic convergence of VRTD and its variance reduction performance.
We show that VRTD is guaranteed to converge to a neighborhood of the fixed-point solution of TD at a linear convergence rate.

Built on

Neural temporal-difference learning converges to global optima
Original
Cai, Q., Yang, Z., Lee, J. D., and Wang, Z. (2019) · 1905
Earlier work this paper cites.
Characterizing the exact behaviors of temporal difference learning algorithms using Markov jump linear system theory
Original
Hu, B. and Syed, U. A. (2019) · 1906
Earlier work this paper cites.
SVRG for policy evaluation with fewer gradient evaluations
Original
Peng, Z., Touati, A., Vincent, P., and Precup, D. (2019) · 1906
Earlier work this paper cites.
A multistep Lyapunov approach for finite-time analysis of biased stochastic approximation
Original
Wang, G., Li, B., and Giannakis, G. B. (2019) · 1909
Earlier work this paper cites.
Learning to predict by the methods of temporal differences
Sutton, R. S. (1988) · 1988
Earlier work this paper cites.
Q-learning
Dayan, P. and Watkins, C. (1992) · 1992
Earlier work this paper cites.
On-line Q-learning Using Connectionist Systems
Rummery, G. A. and Niranjan, M. (1994) · 1994
Earlier work this paper cites.
Neuro-dynamic programming: An overview
Bertsekas, D. P. and Tsitsiklis, J. N. (1995) · 1995
Earlier work this paper cites.
Analysis of temporal-diffference learning with function approximation
Tsitsiklis, J. N. and Van Roy, B. (1997) · 1997
Earlier work this paper cites.
On the convergence of temporal-difference learning with linear function approximation
Tadić, V. (2001) · 2001
Earlier work this paper cites.
A convergent o(n) algorithm for off-policy temporal-difference learning with linear function approximation
Sutton, R. S., Szepesvári, C., and Maei, H. R. (2008) · 2008
Earlier work this paper cites.

Similar

Fast gradient-descent methods for temporal-difference learning with linear function approximation
Sutton, R. S., Maei, H. R., Precup, D., Bhatnagar, S., Silver, D., Szepesvári, C., and Wiewiora, E. (2009) · 2009
Cited alongside, same era.
Gradient temporal-difference learning algorithms
Maei, H. R. (2011) · 2011
Cited alongside, same era.
Batch reinforcement learning
Lange, S., Gabel, T., and Riedmiller, M. (2012) · 2012
Cited alongside, same era.
Accelerating stochastic gradient descent using predictive variance reduction
Johnson, R. and Zhang, T. (2013) · 2013
Cited alongside, same era.
SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives
Defazio, A., Bach, F., and Lacoste-Julien, S. (2014) · 2014
Cited alongside, same era.
Subgaussian concentration inequalities for geometrically ergodic Markov chains
Dedecker, J. and Gouëzel, S. (2015) · 2015
Cited alongside, same era.
On TD (0) with function approximation: Concentration bounds and a centered variant with exponential convergence
Korda, N. and La, P. (2015) · 2015
Cited alongside, same era.
Finite-sample analysis of proximal gradient td algorithms
Liu, B., Liu, J., Ghavamzadeh, M., Mahadevan, S., and Petrik, M. (2015) · 2015
Cited alongside, same era.
OpenAI Gym
Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W. (2016) · 2016
Cited alongside, same era.
Dynamics of stochastic approximation with Markov iterate-dependent noise with the stability of the iterates not ensured
Original
Karmakar, P. and Bhatnagar, S. (2016) · 2016
Cited alongside, same era.
Stochastic variance reduction methods for policy evaluation
Du, S. S., Chen, J., Li, L., Xiao, L., and Zhou, D. (2017) · 2017
Cited alongside, same era.
Finite sample analyses for TD (0) with function approximation
Dalal, G., Szörényi, B., Thoppe, G., and Mannor, S. (2018a)
Cited in the paper.

Then

Two time-scale stochastic approximation with controlled Markov noise and off-policy temporal-difference learning
Karmakar, P. and Bhatnagar, S. (2017) · 2017
Later among the works it cites.
Finite time bounds for temporal difference learning with function approximation: Problems with some “state-of-the-art” results
Narayanan, C. and Szepesvári, C. (2017) · 2017
Later among the works it cites.
Finite sample analysis of the GTD policy evaluation algorithms in Markov setting
Wang, Y., Chen, W., Liu, Y., Ma, Z.-M., and Liu, T.-Y. (2017) · 2017
Later among the works it cites.
On convergence of some gradient-based temporal-differences algorithms for off-policy learning
Original
Yu, H. (2017) · 2017
Later among the works it cites.
A finite time analysis of temporal difference learning with linear function approximation
Bhandari, J., Russo, D., and Singal, R. (2018) · 2018
Later among the works it cites.
Linear stochastic approximation: How far does constant step-size and iterate averaging go?
Lakshminarayanan, C. and Szepesvari, C. (2018) · 2018
Later among the works it cites.
Target-based temporal difference learning
Lee, D. and He, N. (2019) · 2019
Later among the works it cites.
Finite-time error bounds for linear stochastic approximation and TD learning
Srikant, R. and Ying, L. (2019) · 2019
Later among the works it cites.
Two time-scale off-policy td learning: Non-asymptotic analysis over markovian samples
Xu, T., Zou, S., and Liang, Y. (2019) · 2019
Later among the works it cites.
Finite-sample analysis for sarsa with linear function approximation
Zou, S., Xu, T., and Liang, Y. (2019) · 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…