# High-probability sample complexities for policy evaluation with linear function approximation

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 72 references that are in the map.
- First posted on arXiv 30 May 2023.

## Builds on (most cited first, 30 of 39)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Doubly Robust Off-policy Value Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1511.03722/) (2015)
- [Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1604.00923/) (2016)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning](https://mlsanity.com/paper/2106.04895/) (2021)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2002.09516/) (2020)
- [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)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Off-Policy Evaluation via the Regularized Lagrangian](https://mlsanity.com/paper/2007.03438/) (2020)
- [Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity](https://mlsanity.com/paper/2202.13890/) (2022)
- [Settling the Sample Complexity of Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2204.05275/) (2022)
- [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020)
- [Model Selection for Offline Reinforcement Learning: Practical Considerations for Healthcare Settings](https://mlsanity.com/paper/2107.11003/) (2021)
- [Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2002.01268/) (2020)
- [Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis](https://mlsanity.com/paper/2003.07337/) (2020)
- [Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation](https://mlsanity.com/paper/2207.04475/) (2022)
- [Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning](https://mlsanity.com/paper/1907.06290/) (2019)
- [Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples](https://mlsanity.com/paper/1909.11907/) (2019)
- [A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound](https://mlsanity.com/paper/1911.09157/) (2019)

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

- [Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability](https://mlsanity.com/paper/2310.14286/) (2023)
- [Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2401.00364/) (2023)
- [Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications](https://mlsanity.com/paper/2401.09339/) (2024)
- [SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/2402.04114/) (2024)
- [A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximation](https://mlsanity.com/paper/2502.14172/) (2025)
- [Off-policy Evaluation with Deeply-abstracted States](https://mlsanity.com/paper/2406.19531/) (2024)
- [A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging](https://mlsanity.com/paper/2505.21796/) (2025)
- [A Temporal Difference Method for Stochastic Continuous Dynamics](https://mlsanity.com/paper/2505.15544/) (2025)
- [A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averaging](https://mlsanity.com/paper/2606.24981/) (2026)
- [Accelerated Distributional Temporal Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/2511.12688/) (2025)
- [Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization](https://mlsanity.com/paper/2602.11387/) (2026)
- [Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift](https://mlsanity.com/paper/2605.07104/) (2026)
- [Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework](https://mlsanity.com/paper/2605.31309/) (2026)
- [Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsize](https://mlsanity.com/paper/2407.10955/) (2024)
- [Convergence of TD(0) under Polynomial Mixing with Nonlinear Function Approximation](https://mlsanity.com/paper/2502.05706/) (2025)
- [Is Backpropagation Optimal? When Synthetic Gradients Improve Sample Efficiency](https://mlsanity.com/paper/2605.27946/) (2026)

## Abstract (arXiv)

This paper is concerned with the problem of policy evaluation with linear function approximation in discounted infinite horizon Markov decision processes. We investigate the sample complexities required to guarantee a predefined estimation error of the best linear coefficients for two widely-used policy evaluation algorithms: the temporal difference (TD) learning algorithm and the two-timescale linear TD with gradient correction (TDC) algorithm. In both the on-policy setting, where observations are generated from the target policy, and the off-policy setting, where samples are drawn from a behavior policy potentially different from the target policy, we establish the first sample complexity bound with high-probability convergence guarantee that attains the optimal dependence on the tolerance level. We also exhihit an explicit dependence on problem-related quantities, and show in the on-policy setting that our upper bound matches the minimax lower bound on crucial problem parameters, including the choice of the feature maps and the problem dimension.