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

Abstract

In this paper, we establish the global optimality and convergence rate of an off-policy actor critic algorithm in the tabular setting without using density ratio to correct the discrepancy between the state distribution of the behavior policy and that of the target policy. Our work goes beyond existing works on the optimality of policy gradient methods in that existing works use the exact policy gradient for updating the policy parameters while we use an approximate and stochastic update step. Our update step is not a gradient update because we do not use a density ratio to correct the state distribution, which aligns well with what practitioners do. Our update is approximate because we use a learned critic instead of the true value function. Our update is stochastic because at each step the update is done for only the current state action pair. Moreover, we remove several restrictive assumptions from existing works in our analysis. Central to our work is the finite sample analysis of a generic stochastic approximation algorithm with time-inhomogeneous update operators on time-inhomogeneous Markov chains, based on its uniform contraction properties.

arXiv commentJournal of Machine Learning Research 2022. This version improves the JMLR camera-ready version by removing all the projection operators in the algorithms

References in corpus (16)

• Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor
• Reinforcement Learning and Control as Probabilistic Inference: Tutorial and Review
• Bridging the Gap Between Value and Policy Based Reinforcement Learning
• SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
• DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• On the Global Convergence Rates of Softmax Policy Gradient Methods
• Finite-Sample Analysis for SARSA with Linear Function Approximation
• Off-Policy Policy Gradient with State Distribution Correction
• Consistent On-Line Off-Policy Evaluation
• Expected Policy Gradients for Reinforcement Learning
• A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants
• Multi-step Reinforcement Learning: A Unifying Algorithm
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality
• Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm
• On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction