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

Abstract

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({\epsilon }^{-3})$, whose dependency on $\epsilon$ 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({\epsilon }^{-4})$, which matches the convergence rate of some recent actor-critic algorithms in the on-policy setting.

arXiv comment48 Pages; AISTATS 2022

References in corpus (27)

• Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor
• Addressing Function Approximation Error in Actor-Critic Methods
• Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• Finite-Sample Analysis of Proximal Gradient TD Algorithms
• On the Global Convergence Rates of Softmax Policy Gradient Methods
• AlgaeDICE: Policy Gradient from Arbitrary Experience
• Stochastic Variance Reduction Methods for Policy Evaluation
• Reducing Noise in GAN Training with Variance Reduced Extragradient
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• GenDICE: Generalized Offline Estimation of Stationary Values
• Information-Theoretic Considerations in Batch Reinforcement Learning
• Off-Policy Policy Gradient with State Distribution Correction
• Near-Optimal Algorithms for Minimax Optimization
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• A Finite Time Analysis of Two Time-Scale Actor Critic Methods
• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
• Momentum-Based Variance Reduction in Non-Convex SGD
• Off-Policy Evaluation via the Regularized Lagrangian
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Stochastic Recursive Momentum for Policy Gradient Methods
• Minimax Value Interval for Off-Policy Evaluation and Policy Optimization
• Variance-Reduced Off-Policy Memory-Efficient Policy Search
• Momentum-Based Policy Gradient Methods

Cited by in corpus (1)

• Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatch