# Policy evaluation from a single path: Multi-step methods, mixing and mis-specification

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 50 references that are in the map.
- First posted on arXiv 7 Nov 2022.

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

- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency](https://mlsanity.com/paper/2102.02981/) (2021)
- [Optimal and instance-dependent guarantees for Markovian linear stochastic approximation](https://mlsanity.com/paper/2112.12770/) (2021)
- [Optimal policy evaluation using kernel-based temporal difference methods](https://mlsanity.com/paper/2109.12002/) (2021)
- [An L2 Analysis of Reinforcement Learning in High Dimensions with Kernel and Neural Network Approximation](https://mlsanity.com/paper/2104.07794/) (2021)
- [Bellman Residual Orthogonalization for Offline Reinforcement Learning](https://mlsanity.com/paper/2203.12786/) (2022)
- [Adaptive Lambda Least-Squares Temporal Difference Learning](https://mlsanity.com/paper/1612.09465/) (2016)

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

- [Taming "data-hungry" reinforcement learning? Stability in continuous state-action spaces](https://mlsanity.com/paper/2401.05233/) (2024)
- [Localized exploration in contextual dynamic pricing achieves dimension-free regret](https://mlsanity.com/paper/2412.19252/) (2024)
- [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)

## Abstract (arXiv)

We study non-parametric estimation of the value function of an infinite-horizon γ-discounted Markov reward process (MRP) using observations from a single trajectory. We provide non-asymptotic guarantees for a general family of kernel-based multi-step temporal difference (TD) estimates, including canonical K-step look-ahead TD for K = 1, 2, ldots and the TD(λ) family for λ ∈ [0,1) as special cases. Our bounds capture its dependence on Bellman fluctuations, mixing time of the Markov chain, any mis-specification in the model, as well as the choice of weight function defining the estimator itself, and reveal some delicate interactions between mixing time and model mis-specification. For a given TD method applied to a well-specified model, its statistical error under trajectory data is similar to that of i.i.d. sample transition pairs, whereas under mis-specification, temporal dependence in data inflates the statistical error. However, any such deterioration can be mitigated by increased look-ahead. We complement our upper bounds by proving minimax lower bounds that establish optimality of TD-based methods with appropriately chosen look-ahead and weighting, and reveal some fundamental differences between value function estimation and ordinary non-parametric regression.