Adaptive Approximate Policy Iteration

Abstract

Model-free reinforcement learning algorithms combined with value function approximation have recently achieved impressive performance in a variety of application domains. However, the theoretical understanding of such algorithms is limited, and existing results are largely focused on episodic or discounted Markov decision processes (MDPs). In this work, we present adaptive approximate policy iteration (AAPI), a learning scheme which enjoys a $\tilde{O}(T^{2/3})$ regret bound for undiscounted, continuing learning in uniformly ergodic MDPs. This is an improvement over the best existing bound of $\tilde{O}(T^{3/4})$ for the average-reward case with function approximation. Our algorithm and analysis rely on online learning techniques, where value functions are treated as losses. The main technical novelty is the use of a data-dependent adaptive learning rate coupled with a so-called optimistic prediction of upcoming losses. In addition to theoretical guarantees, we demonstrate the advantages of our approach empirically on several environments.

arXiv commentAccepted at AISTATS 2021

References in corpus (15)

• Trust Region Policy Optimization
• Maximum a Posteriori Policy Optimisation
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Deep Exploration via Randomized Value Functions
• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• Optimization, Learning, and Games with Predictable Sequences
• Reinforcement and Imitation Learning via Interactive No-Regret Learning
• A unified view of entropy-regularized Markov decision processes
• A Theory of Regularized Markov Decision Processes
• Model-Free Linear Quadratic Control via Reduction to Expert Prediction
• Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP
• Frequentist Regret Bounds for Randomized Least-Squares Value Iteration
• Predictor-Corrector Policy Optimization
• A Modular Analysis of Adaptive (Non-)Convex Optimization: Optimism, Composite Objectives, and Variational Bounds
• Momentum in Reinforcement Learning

Cited by in corpus (7)

• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Online Learning for Unknown Partially Observable MDPs
• Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regret
• Optimization Issues in KL-Constrained Approximate Policy Iteration
• Improved Regret Bound and Experience Replay in Regularized Policy Iteration
• Learning Expected Reward for Switched Linear Control Systems: A Non-Asymptotic View