# Optimal policy evaluation using kernel-based temporal difference methods

arXiv: https://arxiv.org/abs/2109.12002 · HTML: https://mlsanity.com/paper/2109.12002/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 59 references that are in the map.
- First posted on arXiv 24 Sep 2021.

## Builds on (most cited first, 14 of 14)

- [Doubly Robust Off-policy Value Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1511.03722/) (2015)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling](https://mlsanity.com/paper/1906.03393/) (2019)
- [Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes](https://mlsanity.com/paper/1908.08526/) (2019)
- [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020)
- [Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learning](https://mlsanity.com/paper/2001.10742/) (2020)
- [Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis](https://mlsanity.com/paper/2003.07337/) (2020)
- [A Kernel Loss for Solving the Bellman Equation](https://mlsanity.com/paper/1905.10506/) (2019)
- [Accountable Off-Policy Evaluation With Kernel Bellman Statistics](https://mlsanity.com/paper/2008.06668/) (2020)
- [Randomized sketches for kernels: Fast and optimal non-parametric regression](https://mlsanity.com/paper/1501.06195/) (2015)
- [Early stopping for kernel boosting algorithms: A general analysis with localized complexities](https://mlsanity.com/paper/1707.01543/) (2017)
- [Practical Kernel-Based Reinforcement Learning](https://mlsanity.com/paper/1407.5358/) (2014)
- [An L2 Analysis of Reinforcement Learning in High Dimensions with Kernel and Neural Network Approximation](https://mlsanity.com/paper/2104.07794/) (2021)
- [Optimal oracle inequalities for solving projected fixed-point equations](https://mlsanity.com/paper/2012.05299/) (2020)

## Built on by (most cited first, 24 of 24)

- [On Well-posedness and Minimax Optimal Rates of Nonparametric Q-function Estimation in Off-policy Evaluation](https://mlsanity.com/paper/2201.06169/) (2022)
- [On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2211.13208/) (2022)
- [Accelerated and instance-optimal policy evaluation with linear function approximation](https://mlsanity.com/paper/2112.13109/) (2021)
- [Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theory](https://mlsanity.com/paper/2202.04970/) (2022)
- [Pseudo-Labeling for Kernel Ridge Regression under Covariate Shift](https://mlsanity.com/paper/2302.10160/) (2023)
- [High-probability sample complexities for policy evaluation with linear function approximation](https://mlsanity.com/paper/2305.19001/) (2023)
- [Sample Complexity of Nonparametric Off-Policy Evaluation on Low-Dimensional Manifolds using Deep Networks](https://mlsanity.com/paper/2206.02887/) (2022)
- [Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Data](https://mlsanity.com/paper/2411.03810/) (2024)
- [A Complete Characterization of Linear Estimators for Offline Policy Evaluation](https://mlsanity.com/paper/2203.04236/) (2022)
- [Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learning](https://mlsanity.com/paper/2310.20007/) (2023)
- [Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency](https://mlsanity.com/paper/2301.06240/) (2023)
- [Instance-Dependent Confidence and Early Stopping for Reinforcement Learning](https://mlsanity.com/paper/2201.08536/) (2022)
- [Perturbational Complexity by Distribution Mismatch: A Systematic Analysis of Reinforcement Learning in Reproducing Kernel Hilbert Space](https://mlsanity.com/paper/2111.03469/) (2021)
- [Policy evaluation from a single path: Multi-step methods, mixing and mis-specification](https://mlsanity.com/paper/2211.03899/) (2022)
- [VIPeR: Provably Efficient Algorithm for Offline RL with Neural Function Approximation](https://mlsanity.com/paper/2302.12780/) (2023)
- [The Optimal Approximation Factors in Misspecified Off-Policy Value Function Estimation](https://mlsanity.com/paper/2307.13332/) (2023)
- [Taming "data-hungry" reinforcement learning? Stability in continuous state-action spaces](https://mlsanity.com/paper/2401.05233/) (2024)
- [Krylov-Bellman boosting: Super-linear policy evaluation in general state spaces](https://mlsanity.com/paper/2210.11377/) (2022)
- [Optimal Estimation of Off-Policy Policy Gradient via Double Fitted Iteration](https://mlsanity.com/paper/2202.00076/) (2022)
- [Inference on Time Series Nonparametric Conditional Moment Restrictions Using General Sieves](https://mlsanity.com/paper/2301.00092/) (2022)
- [Sampling Complexity of TD and PPO in RKHS](https://mlsanity.com/paper/2509.24991/) (2025)
- [A Unifying View of Coverage in Linear Off-Policy Evaluation](https://mlsanity.com/paper/2601.19030/) (2026)
- [Is Offline Decision Making Possible with Only Few Samples? Reliable Decisions in Data-Starved Bandits via Trust Region Enhancement](https://mlsanity.com/paper/2402.15703/) (2024)
- [Generalized Fitted Q-Iteration with Clustered Data](https://mlsanity.com/paper/2510.03912/) (2025)

## Abstract (arXiv)

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 L2(μ)-norm, where μ denotes the stationary distribution of the underlying Markov chain. Our analysis imposes no assumptions on the transition operator of the Markov chain, but rather only conditions on the reward function and population-level kernel LSTD solutions. We use empirical process theory techniques to derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator, as well as the instance-dependent variance of the Bellman residual error. In addition, we prove minimax lower bounds over sub-classes of MRPs, which shows that our rate is optimal in terms of the sample size n and the effective horizon H = (1 - γ)-1. Whereas existing worst-case theory predicts cubic scaling (H3) in the effective horizon, our theory reveals that there is in fact a much wider range of scalings, depending on the kernel, the stationary distribution, and the variance of the Bellman residual error. Notably, it is only parametric and near-parametric problems that can ever achieve the worst-case cubic scaling.