mlsanityData to 7 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 4

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 4 papers in the map (data through 7 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,635
  2. 2018Addressing Function Approximation Error in Actor-Critic Methodscited by 2,302
  3. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,873
  4. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  5. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  6. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  7. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  8. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  9. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  10. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  11. 2019DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Correctionscited by 254
  12. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 226
23 more
  1. 2019AlgaeDICE: Policy Gradient from Arbitrary Experiencecited by 187
  2. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  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 141
  5. 2020GenDICE: Generalized Offline Estimation of Stationary Valuescited by 122
  6. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
  7. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  8. 2018Stochastic Variance-Reduced Policy Gradientcited by 103
  9. 2020Off-Policy Evaluation via the Regularized Lagrangiancited by 86
  10. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 75
  11. 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 61
  12. 2019An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradientcited by 58
  13. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 58
  14. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 56
  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 28
  21. 2020Stochastic Recursive Momentum for Policy Gradient Methodscited by 22
  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 7 Oct)

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

4 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 6
  3. 2022Coordinate Ascent for Off-Policy RL with Global Convergence Guaranteescited by 1
  4. 2026Deep Weighted Bellman Residual Minimization for Q^* Estimationcited by 0