mlsanityData to 14 Oct 2026

Accelerated and instance-optimal policy evaluation with linear function approximation

arXiv 2112.13109 ↗First posted 24 Dec 2021stat.ML cs.LG math.OCcited by 18

Not on the map. Why?

Abstract (arXiv)

We study the problem of policy evaluation with linear function approximation and present efficient and practical algorithms that come with strong optimality guarantees. We begin by proving lower bounds that establish baselines on both the deterministic error and stochastic error in this problem. In particular, we prove an oracle complexity lower bound on the deterministic error in an instance-dependent norm associated with the stationary distribution of the transition kernel, and use the local asymptotic minimax machinery to prove an instance-dependent lower bound on the stochastic error in the i.i.d. observation model. Existing algorithms fail to match at least one of these lower bounds: To illustrate, we analyze a variance-reduced variant of temporal difference learning, showing in particular that it fails to achieve the oracle complexity lower bound. To remedy this issue, we develop an accelerated, variance-reduced fast temporal difference algorithm (VRFTD) that simultaneously matches both lower bounds and attains a strong notion of instance-optimality. Finally, we extend the VRFTD algorithm to the setting with Markovian observations, and provide instance-dependent convergence results. Our theoretical guarantees of optimality are corroborated by numerical experiments.

Key facts. Cited by 18 papers in the map (data through 14 Oct 2026). Builds on 28 of its 55 references that are in the map. First posted on arXiv 24 Dec 2021.

Builds on

28 of 55 references.

References · 28

  1. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 402
  2. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  3. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  4. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  5. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 136
  6. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  7. 2018Stochastic Variance-Reduced Policy Gradientcited by 106
  8. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  9. 2014A Proximal Stochastic Gradient Method with Progressive Variance Reductioncited by 78
  10. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 76
  11. 2019Variance-reduced Q-learning is minimax optimalcited by 73
  12. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 58
16 more
  1. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  2. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
  3. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  4. 2018Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimizationcited by 40
  5. 2020Simple and optimal methods for stochastic variational inequalities, I: operator extrapolationcited by 35
  6. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  7. 2021Optimal and instance-dependent guarantees for Markovian linear stochastic approximationcited by 33
  8. 2017Mixing time estimation in reversible Markov chains from a single sample pathcited by 27
  9. 2019Estimating the Mixing Time of Ergodic Markov Chainscited by 25
  10. 2021Optimal policy evaluation using kernel-based temporal difference methodscited by 24
  11. 2020Reanalysis of Variance Reduced Temporal Difference Learningcited by 23
  12. 2020Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learningcited by 23
  13. 2021On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learningcited by 23
  14. 2014On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergencecited by 22
  15. 2021Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learningcited by 22
  16. 2020Optimal oracle inequalities for solving projected fixed-point equationscited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 3; 2023: 4; 2024: 2; 2025: 5; 2026: 3.

18 papers.

Sort:

By area:

  1. 2022Stochastic first-order methods for average-reward Markov decision processescited by 32
  2. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  3. 2023Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stabilitycited by 20
  4. 2022Optimal variance-reduced stochastic approximation in Banach spacescited by 17
  5. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
  6. 2023Accelerated stochastic approximation with state-dependent noisecited by 11
  7. 2022A Complete Characterization of Linear Estimators for Offline Policy Evaluationcited by 7
  8. 2023First-order Policy Optimization for Robust Policy Evaluationcited by 7
  9. 2024SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learningcited by 7
  10. 2025A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximationcited by 6
  11. 2024Strongly-polynomial time and validation analysis of policy gradient methodscited by 5
  12. 2025Estimating stationary mass, frequency by frequencycited by 4
6 more
  1. 2025A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averagingcited by 4
  2. 2025Auto-exploration for online reinforcement learningcited by 3
  3. 2026Multiscale replay: A robust algorithm for stochastic variational inequalities with a Markovian buffercited by 2
  4. 2025Accelerated Distributional Temporal Difference Learning with Linear Function Approximationcited by 1
  5. 2026Value Mirror Descent for Reinforcement Learningcited by 1
  6. 2026Is Backpropagation Optimal? When Synthetic Gradients Improve Sample Efficiencycited by 0