2021

Accelerated and instance-optimal policy evaluation with linear function approximation

Li, Tianjiao, Lan, Guanghui, Pananjady, Ashwin

Understand

We study the problem of policy evaluation with linear function approximation and present efficient and practical algorithms that come with strong optimality guarantees.

We begin by proving lower bounds that establish baselines on both the deterministic error and stochastic error in this problem.
In particular, we prove an oracle complexity lower bound on the deterministic error in an instance-dependent norm associated with the stationary distribution of the transition kernel, and use the local asymptotic minimax machinery to prove an instance-dependent lower bound on the stochastic error in the i.i.d.
observation model.

Built on

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.
Learning to predict by the methods of temporal differences
R. S. Sutton · 1988
Earlier work this paper cites.
On optimality of Krylov’s information when solving linear operator equations
A. S. Nemirovsky · 1991
Earlier work this paper cites.
Information-based complexity of linear operator equations
A. S. Nemirovsky · 1992
Earlier work this paper cites.
Acceleration of stochastic approximation by averaging
B. T. Polyak and A. B. Juditsky · 1992
Earlier work this paper cites.
Reinforcement learning: A survey
L. P. Kaelbling, M. L. Littman, and A. W. Moore · 1996
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.
The ODE method for convergence of stochastic approximation and reinforcement learning
V. S. Borkar and S. P. Meyn · 2000
Earlier work this paper cites.
Asymptotics in statistics: Some basic concepts
L. Le Cam and G. L. Yang · 2000
Earlier work this paper cites.
Introductory lectures on convex optimization: A basic course , volume 87
Y. Nesterov · 2003
Earlier work this paper cites.
On the almost sure rate of convergence of linear stochastic approximation algorithms
V. B. Tadic · 2004
Earlier work this paper cites.
A convergent incremental gradient method with a constant step size
D. Blatt, A. O. Hero, and H. Gauchman · 2007
Earlier work this paper cites.
Stochastic approximation: A dynamical systems viewpoint , volume 48
V. S. Borkar · 2009
Earlier work this paper cites.
Fast gradient-descent methods for temporal-difference learning with linear function approximation
R. S. Sutton, H. R. Maei, D. Precup, S. Bhatnagar, D. Silver, C. Szepesvári, and E. Wiewiora · 2009
Earlier work this paper cites.
Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation
Original
G. Kotsalis, G. Lan, and T. Li · 2011
Earlier work this paper cites.
Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learning
Original
G. Kotsalis, G. Lan, and T. Li · 2011
Earlier work this paper cites.

Similar

Accelerating stochastic gradient descent using predictive variance reduction
R. Johnson and T. Zhang · 2013
Cited alongside, same era.
Reinforcement learning in robotics: A survey
J. Kober, J. A. Bagnell, and J. Peters · 2013
Cited alongside, same era.
Policy evaluation with temporal differences: A survey and comparison
C. Dann, G. Neumann, and J. Peters · 2014
Cited alongside, same era.
SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives
A. Defazio, F. Bach, and S. Lacoste-Julien · 2014
Cited alongside, same era.
Markov decision processes: discrete stochastic dynamic programming
M. L. Puterman · 2014
Cited alongside, same era.
A proximal stochastic gradient method with progressive variance reduction
L. Xiao and T. Zhang · 2014
Cited alongside, same era.
On TD (0) with function approximation: Concentration bounds and a centered variant with exponential convergence
N. Korda and P. La · 2015
Cited alongside, same era.
Stochastic variance reduction methods for policy evaluation
S. S. Du, J. Chen, L. Li, L. Xiao, and D. Zhou · 2017
Cited alongside, same era.
Minimizing finite sums with the stochastic average gradient
M. Schmidt, N. Le Roux, and F. Bach · 2017
Cited alongside, same era.
A finite time analysis of temporal difference learning with linear function approximation
J. Bhandari, D. Russo, and R. Singal · 2018
Cited alongside, same era.
Linear stochastic approximation: How far does constant step-size and iterate averaging go?
C. Lakshminarayanan and C. Szepesvári · 2018
Cited alongside, same era.
Stochastic variance-reduced policy gradient
M. Papini, D. Binaghi, G. Canonaco, M. Pirotta, and M. Restelli · 2018
Cited alongside, same era.

Then

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.
Variance-reduced Q {Q} -learning is minimax optimal
Original
M. J. Wainwright · 2019
Later among the works it cites.
Estimating the mixing time of ergodic Markov chains
G. Wolfer and A. Kontorovich · 2019
Later among the works it cites.
Breaking the sample size barrier in model-based reinforcement learning with a generative model
G. Li, Y. Wei, Y. Chi, Y. Gu, and Y. Chen · 2020
Later among the works it cites.
Optimal oracle inequalities for solving projected fixed-point equations
Original
W. Mou, A. Pananjady, and M. J. Wainwright · 2020
Later among the works it cites.
What are the statistical limits of offline rl with linear function approximation?
Original
R. Wang, D. P. Foster, and S. M. Kakade · 2020
Later among the works it cites.
Reanalysis of variance reduced temporal difference learning
Original
T. Xu, Z. Wang, Y. Zhou, and Y. Liang · 2020
Later among the works it cites.
A Lyapunov theory for finite-sample guarantees of asynchronous Q-learning and TD-learning variants
Original
Z. Chen, S. T. Maguluri, S. Shakkottai, and K. Shanmugam · 2021
Closest in time.
Optimal policy evaluation using kernel-based temporal difference methods
Original
Y. Duan, M. Wang, and M. J. Wainwright · 2021
Closest in time.
On the stability of random matrix product with Markovian noise: Application to linear stochastic approximation and TD learning
Original
A. Durmus, E. Moulines, A. Naumov, S. Samsonov, and H. T. Wai · 2021
Closest in time.
Is q-learning minimax optimal? a tight sample complexity analysis
Original
G. Li, C. Cai, Y. Chen, Y. Gu, Y. Wei, and Y. Chi · 2021
Closest in time.
Variance-aware off-policy evaluation with linear function approximation
Y. Min, T. Wang, D. Zhou, and Q. Gu · 2021
Closest in time.
Optimal and instance-dependent guarantees for Markovian linear stochastic approximation
W. Mou, A. Pananjady, M. J. Wainwright, and P. L. Bartlett · 2021
Closest in time.
Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
Y. Ouyang and Y. Xu · 2021
Closest in time.
Instance-dependent ℓ ∞ \ell_{\infty} -bounds for policy evaluation in tabular reinforcement learning
A. Pananjady and M. J. Wainwright · 2021
Closest in time.
Exponential lower bounds for batch reinforcement learning: Batch rl can be exponentially harder than online rl
A. Zanette · 2021
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…