mlsanityData to 14 Oct 2026

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

arXiv 2305.19001 ↗First posted 30 May 2023stat.ML cs.IT cs.LGcited by 16

Not on the map. Why?

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.

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

39 of 72 references.

References · 39

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2018Is Q-learning Provably Efficient?cited by 487
  3. 2015An Introduction to Matrix Concentration Inequalitiescited by 397
  4. 2020Is Pessimism Provably Efficient for Offline RL?cited by 364
  5. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 339
  6. 2016Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learningcited by 286
  7. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 279
  8. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  9. 2019A Theoretical Analysis of Deep Q-Learningcited by 215
  10. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  11. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 158
  12. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
27 more
  1. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 122
  2. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  3. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 119
  4. 2019Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processescited by 119
  5. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  6. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  7. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  8. 2020Off-Policy Evaluation via the Regularized Lagrangiancited by 86
  9. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 85
  10. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learningcited by 83
  11. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 68
  12. 2021Model Selection for Offline Reinforcement Learning: Practical Considerations for Healthcare Settingscited by 68
  13. 2020Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noisecited by 53
  14. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  15. 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
  16. 2019Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learningcited by 40
  17. 2019Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samplescited by 31
  18. 2019A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Boundcited by 31
  19. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 28
  20. 2021Optimal policy evaluation using kernel-based temporal difference methodscited by 24
  21. 2017Time series experiments and causal estimands: exact randomization tests and tradingcited by 21
  22. 2020Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithmscited by 19
  23. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  24. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  25. 2020Optimal oracle inequalities for solving projected fixed-point equationscited by 10
  26. 2021Minimax Off-Policy Evaluation for Multi-Armed Banditscited by 9
  27. 2021Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximationcited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 4; 2025: 5; 2026: 5.

16 papers.

Sort:

By area:

  1. 2023Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stabilitycited by 20
  2. 2023Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noisecited by 15
  3. 2024Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applicationscited by 7
  4. 2024SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learningcited by 7
  5. 2025A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximationcited by 6
  6. 2024Off-policy Evaluation with Deeply-abstracted Statescited by 4
  7. 2025A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averagingcited by 4
  8. 2025A Temporal Difference Method for Stochastic Continuous Dynamicscited by 3
  9. 2026A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averagingcited by 2
  10. 2025Accelerated Distributional Temporal Difference Learning with Linear Function Approximationcited by 1
  11. 2026Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterizationcited by 1
  12. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 1
4 more
  1. 2026Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Frameworkcited by 1
  2. 2024Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsizecited by 0
  3. 2025Convergence of TD(0) under Polynomial Mixing with Nonlinear Function Approximationcited by 0
  4. 2026Is Backpropagation Optimal? When Synthetic Gradients Improve Sample Efficiencycited by 0