2020

Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis

Khamaru, Koulik, Pananjady, Ashwin, Ruan, Feng et al.

Understand

We address the problem of policy evaluation in discounted Markov decision processes, and provide instance-dependent guarantees on the $\ell_\infty$-error under a generative model.

We establish both asymptotic and non-asymptotic versions of local minimax lower bounds for policy evaluation, thereby providing an instance-dependent baseline by which to compare algorithms.
Theory-inspired simulations show that the widely-used temporal difference (TD) algorithm is strictly suboptimal when evaluated in a non-asymptotic setting, even when combined with Polyak-Ruppert iterate averaging.
We remedy this issue by introducing and analyzing variance-reduced forms of stochastic approximation, showing that they achieve non-asymptotic, instance-dependent optimality up to logarithmic factors.

Built on

A stochastic approximation method
H. Robbins and S. Monro · 1951
Earlier work this paper cites.
Efficient nonparametric testing and estimation
C. Stein · 1956
Earlier work this paper cites.
An Introduction to Probability Theory and its Applications: Volume II
W. Feller · 1966
Earlier work this paper cites.
Local asymptotic minimax and admissibility in estimation
J. Hájek · 1972
Earlier work this paper cites.
Limits of experiments
L. Le Cam · 1972
Earlier work this paper cites.
Attainable accuracy of adaptation algorithms
Y. Z. Tsypkin and B. T. Polyak · 1974
Earlier work this paper cites.
Approximation dans les espaces métriques et théorie de l’estimation
L. Birgé · 1983
Earlier work this paper cites.
Geometrizing rates of convergence I
D. L. Donoho and R. C. Liu · 1987
Earlier work this paper cites.
Efficient estimators from a slowly convergent Robbins-Monro process
D. Ruppert · 1988
Earlier work this paper cites.
Learning to predict by the methods of temporal differences
R. S. Sutton · 1988
Earlier work this paper cites.
Geometrizing rates of convergence II
D. L. Donoho and R. C. Liu · 1991
Earlier work this paper cites.
Acceleration of stochastic approximation by averaging
B. T. Polyak and A. B. Juditsky · 1992
Earlier work this paper cites.
Convergence of stochastic iterative dynamic programming algorithms
T. Jaakkola, M. I. Jordan, and S. P. Singh · 1994
Earlier work this paper cites.
Residual algorithms: Reinforcement learning with function approximation
L. Baird · 1995
Earlier work this paper cites.
Dynamic Programming and Stochastic Control
D. Bertsekas · 1995
Earlier work this paper cites.
Dynamic Programming and Stochastic Control
D. P. Bertsekas · 1995
Earlier work this paper cites.
Neuro-Dynamic Programming
D. P. Bertsekas and J. N. Tsitsiklis · 1996
Earlier work this paper cites.

Similar

Analysis of temporal-difference learning with function approximation
J. N. Tsitsiklis and B. Van Roy · 1997
Cited alongside, same era.
Asymptotic Statistics
A. W. van der Vaart · 1998
Cited alongside, same era.
Essentials of Stochastic Processes
R. Durrett · 1999
Cited alongside, same era.
Finite-sample convergence rates for Q Q -learning and indirect algorithms
M. Kearns and S. Singh · 1999
Cited alongside, same era.
The ODE method for convergence of stochastic approximation and reinforcement learning
V. S. Borkar and S. P. Meyn · 2000
Cited alongside, same era.
Asymptotics in Statistics: Some Basic Concepts
L. Le Cam and G. L. Yang · 2000
Cited alongside, same era.
An adaptation theory for nonparametric confidence intervals
T. T. Cai and M. G. Low · 2004
Cited alongside, same era.
On the almost sure rate of convergence of linear stochastic approximation algorithms
V. B. Tadic · 2004
Cited alongside, same era.
Stochastic Approximation: A Dynamical Systems Viewpoint
V. S. Borkar · 2009
Cited alongside, same era.
Robust stochastic approximation approach to stochastic programming
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro · 2009
Cited alongside, same era.
Introduction to Nonparametric Estimation
A. B. Tsybakov · 2009
Cited alongside, same era.
Non-asymptotic analysis of stochastic optimization algorithms for machine learning
F. Bach and E. Moulines · 2011
Cited alongside, same era.

Then

Minimax regret bounds for reinforcement learning
M. G. Azar, I. Osband, and R. Munos · 2017
Later among the works it cites.
A finite time analysis of temporal difference learning with linear function approximation
Original
J. Bhandari, D. Russo, and R. Singal · 2018
Later among the works it cites.
Finite sample analyses for TD(0) with function approximation
G. Dalal, B. Szörényi, G. Thoppe, and S. Mannor · 2018
Later among the works it cites.
Open problem: The dependence of sample complexity lower bounds on planning horizon
N. Jiang and A. Agarwal · 2018
Later among the works it cites.
Linear stochastic approximation: How far does constant step-size and iterate averaging go?
C. Lakshminarayanan and C. Szepesvari · 2018
Later among the works it cites.
Near-optimal time and sample complexities for solving Markov decision processes with a generative model
A. Sidford, M. Wang, X. Wu, L. Yang, and Y. Ye · 2018
Later among the works it cites.
Reinforcement Learning: An Introduction
R. S. Sutton and A. G. Barto · 2018
Later among the works it cites.
Reinforcement learning: Theory and algorithms
A. Agarwal, N. Jiang, and S. M. Kakade · 2019
Later among the works it cites.
Finite-time performance of distributed temporal difference learning with linear function approximation
Original
T. T. Doan, S. T. Maguluri, and J. Romberg · 2019
Later among the works it cites.
Value function estimation in Markov reward processes: Instance-dependent ℓ ∞ \ell_{\infty} -bounds for policy evaluation
Original
A. Pananjady and M. J. Wainwright · 2019
Later among the works it cites.
Variance reduced policy evaluation with smooth function approximation
H.-T. Wai, M. Hong, Z. Yang, Z. Wang, and K. Tang · 2019
Later among the works it cites.
High-dimensional statistics: A non-asymptotic viewpoint
M. J. Wainwright · 2019
Later among the works it cites.
Stochastic approximation with cone-contractive operators: Sharp ℓ ∞ \ell_{\infty} -bounds for Q Q -learning
Original
M. J. Wainwright · 2019
Later among the works it cites.
Variance-reduced Q Q -learning is minimax optimal
Original
M. J. Wainwright · 2019
Later among the works it cites.
Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds
Original
A. Zanette and E. Brunskill · 2019
Later among the works it cites.
Reanalysis of variance reduced temporal difference learning
Original
T. Xu, Z. Wang, Y. Zhou, and Y. Liang · 2020
Closest in time.

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…