mlsanityData to 14 Oct 2026

On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction

arXiv 2106.00993 ↗First posted 2 Jun 2021cs.LG cs.AIcited by 5

Not on the map. Why?

Abstract (arXiv)

In this paper, we study the convergence properties of off-policy policy improvement algorithms with state-action density ratio correction under function approximation setting, where the objective function is formulated as a max-max-min optimization problem. We characterize the bias of the learning objective and present two strategies with finite-time convergence guarantees. In our first strategy, we present algorithm P-SREDA with convergence rate O(ε-3), whose dependency on ε is optimal. In our second strategy, we propose a new off-policy actor-critic style algorithm named O-SPIM. We prove that O-SPIM converges to a stationary point with total complexity O(ε-4), which matches the convergence rate of some recent actor-critic algorithms in the on-policy setting.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 35 of its 43 references that are in the map. First posted on arXiv 2 Jun 2021.

Builds on

35 of 43 references.

References · 35

  1. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  2. 2018Addressing Function Approximation Error in Actor-Critic Methodscited by 2,417
  3. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,920
  4. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  5. 2015An Introduction to Matrix Concentration Inequalitiescited by 397
  6. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  7. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  8. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  9. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  10. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  11. 2019DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Correctionscited by 254
  12. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 227
23 more
  1. 2019AlgaeDICE: Policy Gradient from Arbitrary Experiencecited by 188
  2. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 177
  3. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  4. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 144
  5. 2020GenDICE: Generalized Offline Estimation of Stationary Valuescited by 122
  6. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 122
  7. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  8. 2018Stochastic Variance-Reduced Policy Gradientcited by 106
  9. 2020Off-Policy Evaluation via the Regularized Lagrangiancited by 86
  10. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 77
  11. 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 62
  12. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 60
  13. 2019An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradientcited by 59
  14. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 58
  15. 2019Off-Policy Policy Gradient with State Distribution Correctioncited by 43
  16. 2020Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithmscited by 43
  17. 2018An Off-policy Policy Gradient Theorem Using Emphatic Weightingscited by 34
  18. 2020Single-Timescale Actor-Critic Provably Finds Globally Optimal Policycited by 34
  19. 2020Finite-Sample Analysis of Proximal Gradient TD Algorithmscited by 32
  20. 2020Momentum-Based Policy Gradient Methodscited by 30
  21. 2020Stochastic Recursive Momentum for Policy Gradient Methodscited by 24
  22. 2020Minimax Value Interval for Off-Policy Evaluation and Policy Optimizationcited by 11
  23. 2020Variance-Reduced Off-Policy Memory-Efficient Policy Searchcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 2; 2023: 0; 2024: 0; 2025: 1; 2026: 1.

5 papers.

  1. 2021Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatchcited by 17
  2. 2022Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimizationcited by 7
  3. 2022Coordinate Ascent for Off-Policy RL with Global Convergence Guaranteescited by 1
  4. 2025Off-Policy Reinforcement Learning with Anytime Safety Guarantees via Robust Safe Gradient Flowcited by 0
  5. 2026Deep Weighted Bellman Residual Minimization for Q^* Estimationcited by 0