Provably Efficient Exploration in Policy Optimization

Abstract

While policy-based reinforcement learning (RL) achieves tremendous successes in practice, it is significantly less understood in theory, especially compared with value-based RL. In particular, it remains elusive how to design a provably efficient policy optimization algorithm that incorporates exploration. To bridge such a gap, this paper proposes an Optimistic variant of the Proximal Policy Optimization algorithm (OPPO), which follows an ``optimistic version'' of the policy gradient direction. This paper proves that, in the problem of episodic Markov decision process with linear function approximation, unknown transition, and adversarial reward with full-information feedback, OPPO achieves $\tilde{O}(\sqrt{d^2{H}^{3}T})$ regret. Here $d$ is the feature dimension, $H$ is the episode horizon, and $T$ is the total number of steps. To the best of our knowledge, OPPO is the first provably efficient policy optimization algorithm that explores.

We have fixed a technical issue in the first version of this paper. We remark the technical assumption of the linear MDP in this version of the paper is different from that in the first version

References in corpus (14)

• Trust Region Policy Optimization
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• A Theoretical Analysis of Deep Q-Learning
• A Theory of Regularized Markov Decision Processes
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy
• Variance-reduced $Q$-learning is minimax optimal
• Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Comments on the Du-Kakade-Wang-Yang Lower Bounds
• Exploration-Enhanced POLITEX

Cited by in corpus (4)

• Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss