mlsanityData to 7 Oct 2026

Stochastic Variance Reduction Methods for Policy Evaluation

arXiv 1702.07944 ↗First posted 25 Feb 2017cs.LG cs.AI cs.SYcited by 56

Not on the map. Why?

Abstract (arXiv)

Policy evaluation is a crucial step in many reinforcement-learning procedures, which estimates a value function that predicts states' long-term value under a given policy. In this paper, we focus on policy evaluation with linear function approximation over a fixed dataset. We first transform the empirical policy evaluation problem into a (quadratic) convex-concave saddle point problem, and then present a primal-dual batch gradient method, as well as two stochastic variance reduction methods for solving the problem. These algorithms scale linearly in both sample size and feature dimension. Moreover, they achieve linear convergence even when the saddle-point problem has only strong concavity in the dual variables but no strong convexity in the primal variables. Numerical experiments on benchmark problems demonstrate the effectiveness of our methods.

Key facts. Cited by 56 papers in the map (data through 7 Oct 2026). First posted on arXiv 25 Feb 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

56 papers.

Sort:

By area:

  1. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  2. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  3. 2021Fault-Tolerant Federated Reinforcement Learning with Theoretical Guaranteecited by 52
  4. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  5. 2021Breaking the Deadly Triad with a Target Networkcited by 47
  6. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  7. 2021Instrumental Variable Value Iteration for Causal Offline Reinforcement Learningcited by 35
  8. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 35
  9. 2021Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimizationcited by 31
  10. 2022Accelerated Single-Call Methods for Constrained Min-Max Optimizationcited by 31
  11. 2021Average-Reward Off-Policy Policy Evaluation with Function Approximationcited by 30
  12. 2023Certified Minimax Unlearning with Generalization Rates and Deletion Capacitycited by 29
38 more
  1. 2021A Generalized Projected Bellman Error for Off-policy Value Estimation in Reinforcement Learningcited by 26
  2. 2021Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Constructioncited by 22
  3. 2022The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimizationcited by 20
  4. 2022Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusioncited by 19
  5. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  6. 2022Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalitiescited by 18
  7. 2021Bayesian Bellman Operatorscited by 16
  8. 2021Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Couplingcited by 16
  9. 2022Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methodscited by 14
  10. 2022Stability and Generalization for Markov Chain Stochastic Gradient Methodscited by 14
  11. 2022Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimizationcited by 13
  12. 2021Truncated Emphatic Temporal Difference Methods for Prediction and Controlcited by 10
  13. 2021Quasi-Newton Methods for Saddle Point Problems and Beyondcited by 10
  14. 2022Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimizationcited by 10
  15. 2022SGDA with shuffling: faster convergence for nonconvex-PL minimax optimizationcited by 8
  16. 2023A first-order augmented Lagrangian method for constrained minimax optimizationcited by 8
  17. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
  18. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  19. 2021Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexitycited by 7
  20. 2023Revisiting a Design Choice in Gradient Temporal Difference Learningcited by 7
  21. 2021DIPPA: An improved Method for Bilinear Saddle Point Problemscited by 6
  22. 2021On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correctioncited by 4
  23. 2022Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimizationcited by 4
  24. 2023Toward Efficient Gradient-Based Value Estimationcited by 4
  25. 2023Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditionscited by 4
  26. 2024Second-Order Min-Max Optimization with Lazy Hessianscited by 4
  27. 2022Decentralized Stochastic Variance Reduced Extragradient Methodcited by 3
  28. 2022Distributed saddle point problems for strongly concave-convex functionscited by 3
  29. 2023Multi-Bellman operator for convergence of Q-learning with linear function approximationcited by 3
  30. 2022Policy Learning and Evaluation with Randomized Quasi-Monte Carlocited by 2
  31. 2022Stability and Generalization of Differentially Private Minimax Problemscited by 2
  32. 2022Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimizationcited by 2
  33. 2023Backstepping Temporal Difference Learningcited by 2
  34. 2023A new Gradient TD Algorithm with only One Step-size: Convergence Rate Analysis using L-λ Smoothnesscited by 2
  35. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  36. 2026Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusionscited by 2
  37. 2026An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascentcited by 2
  38. 2022Gradient Descent Temporal Difference-difference Learningcited by 1

50 most cited of 56 All 56 (JSON)