Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
复制标题
DOI：
--
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Tengyang Xie;Nan Jiang;Huan Wang;Caiming Xiong;Yu Bai
中科院分区：
文献类型：
--
作者：
Tengyang Xie;Nan Jiang;Huan Wang;Caiming Xiong;Yu Bai
最近的理论工作在两种环境中广泛研究了样本有效的强化学习（RL）：在环境中交互式学习（在线RL）或从离线数据集学习（离线RL）。然而，现有的算法和理论学习接近最优的政策，在这两个设置是相当不同的和断开。为了弥合这一差距，本文启动了政策微调的理论研究，即在线强化学习，学习者有额外的访问“参考政策”$\mu$接近最优政策$\pi_\星星$在一定意义上。我们考虑的政策微调问题，情节马尔可夫决策过程（MDP）与$S$状态，$A$行动，和地平线长度$H$。我们首先设计了一个急剧的离线约简算法--它简单地执行$\mu$并在收集的数据集上运行离线策略优化--它在$\widetilde{O}（H^3SC ^\星星/\varepsilon^2）$ episodes内找到一个$\varepsilon$接近最优的策略，其中$C^\星星$是$\mu$和$\pi_\星星$之间的单一策略集中系数。这个离线结果是第一个匹配此设置中的样本复杂度下限的结果，并解决了离线RL中最近的一个未决问题。然后，我们建立了一个$\Omega（H^3S\min\{C^\星星，A\}/\varepsilon^2）$样本复杂度下限的任何政策微调算法，包括那些可以自适应地探索环境。这意味着--也许令人惊讶的是--最优策略微调算法要么是离线约简，要么是不使用$\mu$的纯在线RL算法。最后，我们设计了一个新的混合离线/在线算法的政策微调，实现更好的样本复杂度比香草离线减少和纯在线RL算法，在一个宽松的设置，$\mu$只满足集中性部分达到一定的时间步长。
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 $\varepsilon$ near-optimal policy within $\widetilde{O}(H^3SC^\star/\varepsilon^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^3S\min\{C^\star, A\}/\varepsilon^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.