mlsanityData to 7 Oct 2026

Variance-Reduced Conservative Policy Iteration

arXiv 2212.06283 ↗First posted 12 Dec 2022cs.LG cs.AIcited by 2

Not on the map. Why?

Abstract (arXiv)

We study the sample complexity of reducing reinforcement learning to a sequence of empirical risk minimization problems over the policy space. Such reductions-based algorithms exhibit local convergence in the function space, as opposed to the parameter space for policy gradient algorithms, and thus are unaffected by the possibly non-linear or discontinuous parameterization of the policy class. We propose a variance-reduced variant of Conservative Policy Iteration that improves the sample complexity of producing a varepsilon-functional local optimum from O(varepsilon-4) to O(varepsilon-3). Under state-coverage and policy-completeness assumptions, the algorithm enjoys varepsilon-global optimality after sampling O(varepsilon-2) times, improving upon the previously established O(varepsilon-3) sample requirement.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 26 of its 39 references that are in the map. First posted on arXiv 12 Dec 2022.

Builds on

26 of 39 references.

References · 26

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2015Trust Region Policy Optimizationcited by 2,503
  3. 2015Prioritized Experience Replaycited by 1,070
  4. 2019Introduction to Online Convex Optimizationcited by 793
  5. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  6. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  7. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  8. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  9. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  10. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  11. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  12. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 143
14 more
  1. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  2. 2018Stochastic Variance-Reduced Policy Gradientcited by 103
  3. 2016Variance Reduction for Faster Non-Convex Optimizationcited by 72
  4. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
  5. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 58
  6. 2015A Universal Catalyst for First-Order Optimizationcited by 54
  7. 2016Stochastic Frank-Wolfe Methods for Nonconvex Optimizationcited by 40
  8. 2020Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitationscited by 39
  9. 2017Neon2: Finding Local Minima via First-Order Oraclescited by 36
  10. 2019One Sample Stochastic Frank-Wolfecited by 32
  11. 2017First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Timecited by 29
  12. 2013Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimizationcited by 19
  13. 2019Deep Conservative Policy Iterationcited by 14
  14. 2021A Boosting Approach to Reinforcement Learningcited by 12

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 1.

2 papers.

  1. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
  2. 2024Sample-Efficient Agnostic Boostingcited by 3