2021

Optimal policy evaluation using kernel-based temporal difference methods

Duan, Yaqi, Wang, Mengdi, Wainwright, Martin J.

Understand

We study methods based on reproducing kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process (MRP).

We study a regularized form of the kernel least-squares temporal difference (LSTD) estimate; in the population limit of infinite data, it corresponds to the fixed point of a projected Bellman operator defined by the associated reproducing kernel Hilbert space.
The estimator itself is obtained by computing the projected fixed point induced by a regularized version of the empirical operator; due to the underlying kernel structure, this reduces to solving a linear system involving kernel matrices.
We analyze the error of this estimate in the $L^2(\mu)$-norm, where $\mu$ denotes the stationary distribution of the underlying Markov chain.

Built on

Some results on Tchebycheffian spline functions
G. Kimeldorf and G. Wahba · 1971
Earlier work this paper cites.
The variance of discounted markov decision processes
M. J. Sobel · 1982
Earlier work this paper cites.
Optimal global rates of convergence for non-parametric regression
C. J. Stone · 1982
Earlier work this paper cites.
Instrumental variables regression with independent observations
H. White · 1982
Earlier work this paper cites.
Learning to predict via the methods of temporal differences
R. S. Sutton · 1988
Earlier work this paper cites.
Computing the eigenvalues and eigenvectors of symmetric arrowhead matrices
D. O’leary and G. Stewart · 1990
Earlier work this paper cites.
Dynamic programming and optimal control
D. P. Bertsekas, D. P. Bertsekas, D. P. Bertsekas, and 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.
Linear least-squares algorithms for temporal difference learning
S. J. Bradtke and A. G. Barto · 1996
Earlier work this paper cites.
Analysis of temporal-diffference learning with function approximation
J. N. Tsitsiklis and B. Van Roy · 1997
Earlier work this paper cites.
Empirical Processes in M M -Estimation
S. van de Geer · 2000
Earlier work this paper cites.
Smoothing spline ANOVA models
C. Gu · 2002
Earlier work this paper cites.
Geometric parameters of kernel machines
S. Mendelson · 2002
Earlier work this paper cites.
Kernel-based reinforcement learning
D. Ormoneit and Ś. Sen · 2002
Earlier work this paper cites.
Policy search in kernel Hilbert space
J. A. Bagnell and J. Schneider · 2003
Earlier work this paper cites.
Instrumental variable estimation of non-parametric models
W. K. Newey and J. L. Powell · 2003
Earlier work this paper cites.
Reproducing kernel Hilbert spaces in probability and statistics
A. Berlinet and C. Thomas-Agnan · 2004
Earlier work this paper cites.

Similar

Kernel methods for pattern analysis
J. Shawe-Taylor, N. Cristianini, et al · 2004
Cited alongside, same era.
Markov decision processes: Discrete stochastic dynamic programming
M. L. Puterman · 2005
Cited alongside, same era.
Consistency of support vector machines and other regularized kernel machines
I. Steinwart · 2005
Cited alongside, same era.
Learning bounds for kernel regression using effective data dimensionality
T. Zhang · 2005
Cited alongside, same era.
Finite-time bounds for fitted value iteration
R. Munos and C. Szepesvari · 2008
Cited alongside, same era.
Kernelized value function approximation for reinforcement learning
G. Taylor and R. Parr · 2009
Cited alongside, same era.
Econometric Analysis of Cross Section and Panel Data
J. M. Wooldridge · 2010
Cited alongside, same era.
Error bounds for approximations from projected linear equations
H. Yu and D. P. Bertsekas · 2010
Cited alongside, same era.
Dynamic programming and optimal control 3rd edition, volume ii
D. P. Bertsekas · 2011
Cited alongside, same era.
Modelling transition dynamics in MDPs with RKHS embeddings
S. Grunewalder, G. Lever, L. Baldassarre, M. Pontil, and A. Gretton · 2012
Cited alongside, same era.
Minimax-optimal rates for sparse additive models over kernel classes via convex programming
G. Raskutti, M. J. Wainwright, and B. Yu · 2012
Cited alongside, same era.
Practical kernel-based reinforcement learning
A. M. S. Bareeto, D. Precup, and J. Pineau · 2016
Cited alongside, same era.

Then

Reinforcement learning: An introduction
R. S. Sutton and A. G. Barto · 2018
Later among the works it cites.
A kernel loss for solving the Bellman equation
Y. Feng, L. Li, and Q. Liu · 2019
Later among the works it cites.
Efficiently breaking the curse of horizon: Double reinforcement learning in infinite-horizon processes
N. Kallus and M. Uehara · 2019
Later among the works it cites.
High-dimensional statistics: A non-asymptotic viewpoint
M. J. Wainwright · 2019
Later among the works it cites.
Early stopping for kernel boosting algorithms: A general analysis with localized complexities
Y. Wei, F. Yang, and M. J. Wainwright · 2019
Later among the works it cites.
Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling
T. Xie, Y. Ma, and Y.-X. Wang · 2019
Later among the works it cites.
A theoretical analysis of deep Q-learning
J. Fan, Z. Wang, Y. Xie, and Z. Yang · 2020
Later among the works it cites.
Accountable off-policy evaluation with kernel Bellman statistics
Y. Feng, T. Ren, Z. Tang, and Q. Liu · 2020
Later among the works it cites.
Double reinforcement learning for efficient off-policy evaluation in markov decision processes
N. Kallus and M. Uehara · 2020
Later among the works it cites.
Policy evaluation in continuous MDPs with efficient kernelized gradient temporal difference
A. Koppel, G. Warnell, E. Stump, P. Stone, and A. Ribeiro · 2020
Later among the works it cites.
On linear stochastic approximation: Fine-grained Polyak-Ruppert and non-asymptotic concentration
W. Mou, C. J. Li, M. J. Wainwright, P. L. Bartlett, and M. I. Jordan · 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.
Instance-dependent ℓ ∞ \ell_{\infty} -bounds for policy evaluation in tabular reinforcement learning
A. Pananjady and M. J. Wainwright · 2020
Later among the works it cites.
Asymptotically efficient off-policy evaluation for tabular reinforcement learning
Original
M. Yin and Y.-X. Wang · 2020
Later among the works it cites.
Is temporal difference learning optimal? An instance-dependent analysis
K. Khamaru, A. Pananjady, F. Ruan, M. J. Wainwright, and M. I. Jordan · 2021
Closest in time.
An L 2 {L}^{2} analysis of reinforcement learning in high dimensions with kernel and neural network approximation
Original
J. Long, J. Han, and W. E · 2021
Closest in time.
Sample complexity of offline reinforcement learning with deep relu networks
Original
T. Nguyen-Tang, S. Gupta, H. Tran-The, S. Venkatesh, et al · 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…