Optimistic Policy Optimization with Bandit Feedback

Abstract

Policy optimization methods are one of the most widely used classes of Reinforcement Learning (RL) algorithms. Yet, so far, such methods have been mostly analyzed from an optimization perspective, without addressing the problem of exploration, or by making strong assumptions on the interaction with the environment. In this paper we consider model-based RL in the tabular finite-horizon MDP setting with unknown transitions and bandit feedback. For this setting, we propose an optimistic trust region policy optimization (TRPO) algorithm for which we establish $\tilde{O}(\sqrt{S^{2}A{H}^{4}K})$ regret for stochastic rewards. Furthermore, we prove $\tilde{O}(\sqrt{S^{2}A{H}^4}{K}^{2/3})$ regret for adversarial rewards. Interestingly, this result matches previous bounds derived for the bandit feedback case, yet with known transitions. To the best of our knowledge, the two results are the first sub-linear regret bounds obtained for policy optimization algorithms with unknown transitions and bandit feedback.

Accepted to ICML 2020

References in corpus (16)

• Continuous control with deep reinforcement learning
• Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor
• Trust Region Policy Optimization
• Empirical Bernstein Bounds and Sample Variance Penalization
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• Online Learning: A Modern Introduction Using Convex Optimization
• A unified view of entropy-regularized Markov decision processes
• A Theory of Regularized Markov Decision Processes
• Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy
• Online Convex Optimization in Adversarial Markov Decision Processes
• Approximate Policy Iteration Schemes: A Comparison
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes
• Explore no more: Improved high-probability regret bounds for non-stochastic bandits
• On Connections between Constrained Optimization and Reinforcement Learning

Cited by in corpus (7)

• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss
• Dynamic Regret of Policy Optimization in Non-stationary Environments
• Principled Exploration via Optimistic Bootstrapping and Backward Induction
• Optimization Issues in KL-Constrained Approximate Policy Iteration
• Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximation
• Reward is enough for convex MDPs