Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning

Abstract

Recent theoretical work studies sample-efficient reinforcement learning (RL) extensively in two settings: learning interactively in the environment (online RL), or learning from an offline dataset (offline RL). However, existing algorithms and theories for learning near-optimal policies in these two settings are rather different and disconnected. Towards bridging this gap, this paper initiates the theoretical study of policy finetuning, that is, online RL where the learner has additional access to a "reference policy" $\mu$ close to the optimal policy ${\pi }_{\star }$ in a certain sense. We consider the policy finetuning problem in episodic Markov Decision Processes (MDPs) with $S$ states, $A$ actions, and horizon length $H$. We first design a sharp offline reduction algorithm -- which simply executes $\mu$ and runs offline policy optimization on the collected dataset -- that finds an $\epsilon$ near-optimal policy within $\tilde{O}(H^{3}S{C}^{\star }/{\epsilon }^2)$ episodes, where $C^{\star }$ is the single-policy concentrability coefficient between $\mu$ and ${\pi }_{\star }$. This offline result is the first that matches the sample complexity lower bound in this setting, and resolves a recent open question in offline RL. We then establish an $\Omega (H^{3}S\min \{C^{\star },A\}/{\epsilon }^2)$ sample complexity lower bound for any policy finetuning algorithm, including those that can adaptively explore the environment. This implies that -- perhaps surprisingly -- the optimal policy finetuning algorithm is either offline reduction or a purely online RL algorithm that does not use $\mu$. Finally, we design a new hybrid offline/online algorithm for policy finetuning that achieves better sample complexity than both vanilla offline reduction and purely online RL algorithms, in a relaxed setting where $\mu$ only satisfies concentrability partially up to a certain time step.

Published in NeurIPS 2021

References in corpus (21)

• Solving Rubik's Cube with a Robot Hand
• Conservative Q-Learning for Offline Reinforcement Learning
• MOPO: Model-based Offline Policy Optimization
• MOReL : Model-Based Offline Reinforcement Learning
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Information-Theoretic Considerations in Batch Reinforcement Learning
• Deployment-Efficient Reinforcement Learning via Model-Based Offline Optimization
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Model-based Reinforcement Learning and the Eluder Dimension
• Provably Good Batch Reinforcement Learning Without Great Exploration
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Is Pessimism Provably Efficient for Offline RL?
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison
• Near-Optimal Reinforcement Learning with Self-Play
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• MUSBO: Model-based Uncertainty Regularized and Sample Efficient Batch Optimization for Deployment Constrained Reinforcement Learning
• Nearly Horizon-Free Offline Reinforcement Learning

Cited by in corpus (2)

• When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?
• Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximation